劉晨，陳洋*，符浩

基于值函數(shù)迭代的持續(xù)監(jiān)測(cè)無(wú)人機(jī)路徑規(guī)劃

劉晨1，2，陳洋1，2*，符浩3

（1.武漢科技大學(xué) 機(jī)器人與智能系統(tǒng)研究院，武漢 430081； 2.冶金自動(dòng)化與檢測(cè)技術(shù)教育部工程研究中心（武漢科技大學(xué)），武漢 430081； 3.武漢科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，武漢 430081）（ ? 通信作者電子郵箱chenyag@wust.edu.cn）

使用無(wú)人機(jī)（UAV）持續(xù)監(jiān)測(cè)指定區(qū)域可以起到威懾入侵破壞、及時(shí)發(fā)現(xiàn)異常等作用，然而固定的監(jiān)測(cè)規(guī)律容易被入侵者發(fā)現(xiàn)，因此需要設(shè)計(jì)UAV飛行路徑的隨機(jī)算法。針對(duì)以上問(wèn)題，提出一種基于值函數(shù)迭代（VFI）的UAV持續(xù)監(jiān)測(cè)路徑規(guī)劃算法。首先，合理選擇監(jiān)測(cè)目標(biāo)點(diǎn)的狀態(tài)，并分析各監(jiān)測(cè)節(jié)點(diǎn)的剩余時(shí)間；其次，結(jié)合獎(jiǎng)勵(lì)/懲罰收益和路徑安全性約束構(gòu)建該監(jiān)測(cè)目標(biāo)點(diǎn)對(duì)應(yīng)狀態(tài)的值函數(shù)，在VFI算法過(guò)程中基于原則和輪盤選擇隨機(jī)選擇下一節(jié)點(diǎn)；最后，以所有狀態(tài)的值函數(shù)增長(zhǎng)趨于飽和為目標(biāo)，求解UAV持續(xù)監(jiān)測(cè)路徑。仿真實(shí)驗(yàn)結(jié)果表明，所提算法獲得的信息熵為0.905 0，VFI運(yùn)行時(shí)間為0.363 7 s，相較于傳統(tǒng)蟻群算法（ACO），所提算法的信息熵提升了216%，運(yùn)行時(shí)間降低了59%，隨機(jī)性與快速性均有所提升，驗(yàn)證了具有隨機(jī)性的UAV飛行路徑對(duì)提高持續(xù)監(jiān)測(cè)效率具有重要意義。

路徑規(guī)劃；持續(xù)監(jiān)測(cè)；值迭代；輪盤選擇；原則

0 引言

出于公共安全、環(huán)境保護(hù)、科學(xué)研究等目的，人們需要對(duì)某些區(qū)域進(jìn)行長(zhǎng)期觀察、測(cè)量和數(shù)據(jù)采集，從而為系統(tǒng)決策提供支撐，即持續(xù)監(jiān)測(cè)問(wèn)題。人工監(jiān)測(cè)經(jīng)常受天氣、地理環(huán)境、熟練程度等影響，導(dǎo)致監(jiān)測(cè)效率低、質(zhì)量差、成本高，劣勢(shì)逐步擴(kuò)大。無(wú)人機(jī)（Unmanned Aerial Vehicle， UAV）具有飛行穩(wěn)定、飛行范圍廣、運(yùn)行成本較低等優(yōu)勢(shì)，同時(shí)還能與無(wú)人車相結(jié)合構(gòu)成自主監(jiān)測(cè)與數(shù)據(jù)處理系統(tǒng)，使用無(wú)人機(jī)或無(wú)人車執(zhí)行監(jiān)測(cè)任務(wù)能克服上述人工監(jiān)測(cè)的缺陷。但是使用無(wú)人機(jī)執(zhí)行持續(xù)監(jiān)測(cè)任務(wù)時(shí)，為防止入侵者輕易發(fā)現(xiàn)監(jiān)測(cè)路徑規(guī)律，需要提高無(wú)人機(jī)飛行路線的隨機(jī)性和監(jiān)測(cè)規(guī)律的安全性。本文旨在尋找一個(gè)有策略的、安全的持續(xù)監(jiān)測(cè)路徑計(jì)算方法，從而實(shí)現(xiàn)持續(xù)監(jiān)測(cè)任務(wù)的要求。

Cannata等［1］、Portugal等［2］和Machado等［3］在研究持續(xù)監(jiān)測(cè)問(wèn)題時(shí)，提出了閑置時(shí)間的概念，并將它作為算法性能指標(biāo)應(yīng)用于多機(jī)器人巡邏問(wèn)題。閑置時(shí)間指巡邏的某個(gè)時(shí)刻與目標(biāo)點(diǎn)被訪問(wèn)時(shí)刻之間的時(shí)間差。Pasqualetti等［4］優(yōu)化協(xié)同巡邏算法最小更新時(shí)間，最小更新時(shí)間指機(jī)器人兩次訪問(wèn)同一個(gè)位置時(shí)的時(shí)間間隔。Elmaliach等［5］提出了以一定頻率巡邏和訪問(wèn)任務(wù)點(diǎn)，根據(jù)任務(wù)區(qū)域中需要訪問(wèn)的任務(wù)點(diǎn)構(gòu)建封閉路徑，通過(guò)優(yōu)化路徑實(shí)現(xiàn)優(yōu)化目標(biāo)點(diǎn)被訪問(wèn)的頻率的目標(biāo)。Chen等［6］在研究持續(xù)監(jiān)測(cè)問(wèn)題時(shí)，提出一種多蟻群優(yōu)化（Overdue-aware Multiple Ant Colony Optimization， OMACO）算法，運(yùn)用目標(biāo)排他機(jī)制求解多無(wú)人機(jī)合作的最優(yōu)飛行路徑。

近年來(lái)，強(qiáng)化學(xué)習(xí)在自動(dòng)駕駛［7］、機(jī)器視覺［8-9］、自然語(yǔ)言處理［10-11］和推薦搜索系統(tǒng)［12］等領(lǐng)域應(yīng)用廣泛，研究者也開始將強(qiáng)化學(xué)習(xí)和路徑規(guī)劃結(jié)合。Bellman等［13］提出貝爾曼方程和動(dòng)態(tài)規(guī)劃的概念，根據(jù)動(dòng)態(tài)系統(tǒng)的狀態(tài)和值函數(shù)確定函數(shù)方程，通過(guò)求解該方程得到最優(yōu)控制解。值迭代是一種動(dòng)態(tài)規(guī)劃方法，原理是利用獎(jiǎng)懲機(jī)制學(xué)習(xí)，每個(gè)狀態(tài)都執(zhí)行獎(jiǎng)賞值最大的動(dòng)作，使整個(gè)過(guò)程累積的值最大，從而獲得最優(yōu)策略。馬爾可夫決策過(guò)程（Markov Decision Process， MDP）是動(dòng)態(tài)規(guī)劃的離散隨機(jī)版，通過(guò)類似“試錯(cuò)”的機(jī)制使方程迭代求解。部分可觀測(cè)馬爾可夫決策過(guò)程（Partially Observable Markov Decision Process， POMDP）是處理不確定條件下決策問(wèn)題的通用框架之一，其中也涉及值迭代算法的應(yīng)用與改進(jìn)，代表性的算法包括基于點(diǎn)的值迭代、前向搜索值迭代和啟發(fā)式搜索值迭代，這些算法通常能夠得到最優(yōu)或近似最優(yōu)的策略［14］?；邳c(diǎn)的值迭代［15］是經(jīng)典的基于密度標(biāo)準(zhǔn)擴(kuò)展探索點(diǎn)集的算法。前向搜索值迭代算法［16］采用了基于值函數(shù)的近似求解方案，根據(jù)最優(yōu)值函數(shù)上界選擇最優(yōu)動(dòng)作探索最優(yōu)可達(dá)信念點(diǎn)集，保證收斂到全局最優(yōu)。然而這些算法在大規(guī)模問(wèn)題上存在收斂效率低的缺陷。啟發(fā)式搜索值迭代［17］采用基于MDP的近似解法，根據(jù)MDP的策略在信念點(diǎn)集形成的空間中選擇最優(yōu)的動(dòng)作，降低了求解復(fù)雜度，提高了計(jì)算效率。啟發(fā)式概率值迭代算法相較于主流的基于密度的近似解法能更有效地利用模型信息［18］，相較于基于單一界的近似解法具有更好的收斂效果，相較于基于復(fù)合界的解法收斂更快。房俊恒［19］針對(duì)大規(guī)模POMDP問(wèn)題，提出了一種改進(jìn)的啟發(fā)式搜索值迭代算法。該算法以可達(dá)性作為啟發(fā)式準(zhǔn)則搜索具有重大價(jià)值的可信狀態(tài)點(diǎn)，局部更新這些點(diǎn)的值函數(shù)，獲得了有效的近似優(yōu)化策略。

Washington等［20］提出了一種簡(jiǎn)化狀態(tài)值迭代算法，利用MDP的結(jié)構(gòu)求解最優(yōu)策略，并將它應(yīng)用于求解持續(xù)監(jiān)測(cè)問(wèn)題。Bethke等［21］提出一個(gè)多智能體持續(xù)監(jiān)視問(wèn)題的MDP建模方法，討論了一種由貝葉斯模型估計(jì)器與MDP結(jié)合的自適應(yīng)機(jī)制，并驗(yàn)證了這種自適應(yīng)機(jī)制在持續(xù)監(jiān)視問(wèn)題中的性能優(yōu)勢(shì)。Jeong等［22］提出一種生成任務(wù)流的方法，目標(biāo)是使持續(xù)監(jiān)視區(qū)域的不確定性盡可能保持在較低的水平；實(shí)驗(yàn)結(jié)果展示了算法具有較小的不確定性，但監(jiān)視任務(wù)的執(zhí)行過(guò)程中仍存在循環(huán)軌跡的現(xiàn)象。

上述循環(huán)軌跡產(chǎn)生的原因是：在路徑規(guī)劃問(wèn)題中無(wú)人機(jī)需在滿足約束的前提下從起點(diǎn)運(yùn)動(dòng)到達(dá)終點(diǎn)，無(wú)人機(jī)在采用值迭代方法學(xué)習(xí)路網(wǎng)信息生成最優(yōu)飛行路徑時(shí)，通常只能得到唯一最優(yōu)解，將它融入持續(xù)監(jiān)測(cè)任務(wù)中，求解得出的無(wú)人機(jī)路徑將是已知起點(diǎn)到某個(gè)終點(diǎn)之間路徑段的無(wú)限循環(huán)。為了防止持續(xù)監(jiān)測(cè)任務(wù)被入侵破壞，不能采用循環(huán)路徑執(zhí)行任務(wù)，因此本文提出持續(xù)監(jiān)測(cè)路徑規(guī)劃算法需要滿足隨機(jī)性要求。陳佳等［23］運(yùn)用信息熵決定蟻群之間的行動(dòng)，如合作或是競(jìng)爭(zhēng)，提高了算法的多樣性。

本文圍繞持續(xù)監(jiān)測(cè)路徑規(guī)劃，在路網(wǎng)和等待時(shí)間的約束下，提出一種基于值函數(shù)迭代（Value Function Iteration， VFI）的無(wú)人機(jī)持續(xù)監(jiān)測(cè)路徑規(guī)劃算法，尋找一條具有較高安全性的監(jiān)測(cè)路徑。值迭代求解方法能快速收斂，求得最優(yōu)策略近似解；因此，設(shè)計(jì)并運(yùn)用值函數(shù)進(jìn)行迭代學(xué)習(xí)，設(shè)計(jì)有剩余時(shí)間約束的即時(shí)收益，結(jié)合未來(lái)收益，在對(duì)每個(gè)狀態(tài)執(zhí)行獎(jiǎng)賞最大的動(dòng)作時(shí)，結(jié)合具有隨機(jī)性的輪盤選擇，求出隨機(jī)性強(qiáng)的持續(xù)監(jiān)測(cè)路徑最優(yōu)解，使路徑具有一定的安全性。針對(duì)給定的初始狀態(tài)能夠輸出每次的訪問(wèn)節(jié)點(diǎn)，滿足收斂閾值的要求。

本文的主要工作包括：

1）考慮持續(xù)監(jiān)測(cè)路網(wǎng)和剩余時(shí)間約束，結(jié)合獎(jiǎng)勵(lì)和懲罰收益，設(shè)計(jì)值函數(shù)建立無(wú)人機(jī)持續(xù)監(jiān)測(cè)路徑規(guī)劃模型。

2）運(yùn)用具有隨機(jī)性的輪盤選擇的方法，解決無(wú)人機(jī)監(jiān)測(cè)路徑循環(huán)問(wèn)題，在持續(xù)監(jiān)測(cè)路徑選擇下一目標(biāo)點(diǎn)時(shí)，采取原則隨機(jī)選擇其他目標(biāo)點(diǎn)方法，使用輪盤選擇。

3）運(yùn)用信息熵評(píng)價(jià)持續(xù)監(jiān)測(cè)路徑的隨機(jī)性，其中，每個(gè)目標(biāo)點(diǎn)的熵使用不同訪問(wèn)周期出現(xiàn)的概率進(jìn)行計(jì)算，再通過(guò)求取所有目標(biāo)點(diǎn)的熵的均值評(píng)估持續(xù)監(jiān)測(cè)路徑隨機(jī)性。

1 問(wèn)題描述

本文假設(shè)持續(xù)監(jiān)測(cè)任務(wù)由一架旋翼無(wú)人機(jī)完成。為了方便分析，可以將旋翼無(wú)人機(jī)視為轉(zhuǎn)彎半徑為0、勻速飛行的質(zhì)點(diǎn)。已知所有待監(jiān)測(cè)目標(biāo)點(diǎn)構(gòu)成的拓?fù)渚W(wǎng)絡(luò)和各目標(biāo)點(diǎn)的最大允許監(jiān)測(cè)周期，其中，目標(biāo)點(diǎn)的最大允許監(jiān)測(cè)周期指無(wú)人機(jī)相鄰兩次監(jiān)測(cè)同一個(gè)目標(biāo)點(diǎn)之間的最大允許時(shí)間間隔。如果無(wú)人機(jī)在該時(shí)間間隔之內(nèi)未能到達(dá)相應(yīng)目標(biāo)點(diǎn)，表示監(jiān)測(cè)任務(wù)失敗。

無(wú)人機(jī)監(jiān)測(cè)過(guò)程應(yīng)當(dāng)滿足以下要求：

1）盡可能提高各個(gè)待監(jiān)測(cè)節(jié)點(diǎn)的訪問(wèn)頻率；

2）相鄰兩次到達(dá)同一個(gè)目標(biāo)點(diǎn)實(shí)施監(jiān)測(cè)的間隔時(shí)間不允許超過(guò)該目標(biāo)點(diǎn)的最大允許監(jiān)測(cè)周期；

3）監(jiān)測(cè)路徑具有較強(qiáng)的隨機(jī)性。

為了獲得無(wú)人機(jī)最優(yōu)的監(jiān)測(cè)路徑，不允許無(wú)人機(jī)持續(xù)停留在任意一個(gè)目標(biāo)節(jié)點(diǎn)的位置。

2 持續(xù)監(jiān)測(cè)路徑規(guī)劃模型

城市街道大多是直線形成的矩形區(qū)域，因此本文也簡(jiǎn)化成矩形路網(wǎng)。將待監(jiān)測(cè)區(qū)域內(nèi)的街道設(shè)定為無(wú)人機(jī)持續(xù)監(jiān)測(cè)任務(wù)的目標(biāo)點(diǎn)。整個(gè)持續(xù)監(jiān)測(cè)區(qū)域包含多個(gè)目標(biāo)點(diǎn)，每個(gè)目標(biāo)點(diǎn)都擁有各自的最大允許監(jiān)測(cè)周期。因此，每個(gè)目標(biāo)點(diǎn)都有一個(gè)表征它的距離發(fā)生監(jiān)測(cè)逾期事件的時(shí)間間隔的參數(shù)，稱為監(jiān)測(cè)剩余時(shí)間。剩余時(shí)間越少，該目標(biāo)點(diǎn)被監(jiān)測(cè)的需求越迫切。為防止無(wú)人機(jī)的持續(xù)監(jiān)測(cè)規(guī)律被入侵者獲取，需尋找到安全可靠的持續(xù)監(jiān)測(cè)策略，完成對(duì)這一區(qū)域的持續(xù)監(jiān)測(cè)任務(wù)。

建立路徑規(guī)劃模型的思路如下：確定無(wú)人機(jī)的每一個(gè)狀態(tài)，對(duì)每個(gè)可能的下一目標(biāo)點(diǎn)計(jì)算選擇此點(diǎn)后達(dá)到下一個(gè)狀態(tài)的期望價(jià)值；比較選擇哪個(gè)目標(biāo)點(diǎn)達(dá)到的狀態(tài)的期望值函數(shù)最大，將這個(gè)期望值函數(shù)作為當(dāng)前狀態(tài)的值函數(shù)，并循環(huán)執(zhí)行這個(gè)步驟，直到值函數(shù)收斂。

2.1　狀態(tài)向量與動(dòng)作空間

2.2　收益函數(shù)

其中sgn為符號(hào)函數(shù)。

2.3　值函數(shù)

無(wú)人機(jī)決策的目的是期望得到一個(gè)行動(dòng)策略集，但是無(wú)人機(jī)的決策和行動(dòng)的獎(jiǎng)勵(lì)不能實(shí)時(shí)對(duì)應(yīng)。因此，需要定義一個(gè)更為有效的函數(shù)，即值函數(shù)［24］，描述決策和行動(dòng)的獎(jiǎng)勵(lì)。當(dāng)前狀態(tài)的值函數(shù)不僅可以橫向地與其他狀態(tài)比較，也可以縱向地與其他策略比較，從而在后續(xù)的迭代過(guò)程中找到最佳策略，形成行動(dòng)策略集。

更新后的狀態(tài)：

式（7）中，各節(jié)點(diǎn)剩余時(shí)間的計(jì)算如下：

2.4　監(jiān)測(cè)路徑的隨機(jī)性

持續(xù)監(jiān)測(cè)任務(wù)通常要求監(jiān)測(cè)方案具有一定的隨機(jī)性，以防止外界獲得監(jiān)測(cè)規(guī)律伺機(jī)破壞，因此有必要在優(yōu)化監(jiān)測(cè)路徑的同時(shí)，提升無(wú)人機(jī)監(jiān)測(cè)路徑的隨機(jī)性。本文通過(guò)計(jì)算監(jiān)測(cè)路徑的信息熵評(píng)估監(jiān)測(cè)路徑的隨機(jī)性。信息熵常被用作一個(gè)系統(tǒng)的信息含量的量化指標(biāo)，它表示整個(gè)系統(tǒng)的所有信息量的一種期望：系統(tǒng)越復(fù)雜，出現(xiàn)不同情況的種類越多，每種情況出現(xiàn)概率越小，隨機(jī)性越強(qiáng)，信息熵越大；系統(tǒng)越簡(jiǎn)單，出現(xiàn)情況種類越少，每種情況出現(xiàn)概率越大，隨機(jī)性越弱，信息熵越小。

無(wú)人機(jī)在得到行動(dòng)策略集后，每個(gè)目標(biāo)點(diǎn)被訪問(wèn)的次數(shù)不同，同一目標(biāo)點(diǎn)每次訪問(wèn)的時(shí)間間隔不相同，因此持續(xù)監(jiān)測(cè)路徑中目標(biāo)點(diǎn)的訪問(wèn)周期是一組離散數(shù)。本文運(yùn)用信息熵評(píng)價(jià)這一組離散數(shù)，信息熵值越高，訪問(wèn)每個(gè)目標(biāo)點(diǎn)的時(shí)刻越隨機(jī)，持續(xù)監(jiān)測(cè)路徑隨機(jī)性越強(qiáng)。信息熵函數(shù)如下：

3 模型迭代求解

值迭代算法運(yùn)行初期，節(jié)點(diǎn)被逐漸訪問(wèn)，無(wú)法判斷有多少種狀態(tài)向量以及對(duì)應(yīng)的值函數(shù)產(chǎn)生。隨著迭代次數(shù)的增加，狀態(tài)向量逐漸增多。本文采用值迭代和輪盤選擇結(jié)合的方法：

3.1　下一節(jié)點(diǎn)的選擇策略

對(duì)于下一目標(biāo)點(diǎn)的選擇，90%概率選擇獎(jiǎng)勵(lì)收益最大的目標(biāo)點(diǎn)，10%概率使用輪盤選擇其他目標(biāo)點(diǎn)。基于輪盤選擇的方法的基本思想是：各個(gè)目標(biāo)節(jié)點(diǎn)的選擇概率與它最大允許監(jiān)測(cè)周期和剩余時(shí)間有關(guān)。剩余時(shí)間越少、與最大允許監(jiān)測(cè)周期的差值越大，被選擇的概率越高。具體操作如下：

3.2　迭代終止條件

3.3　算法流程

本文針對(duì)持續(xù)監(jiān)測(cè)問(wèn)題，建立了基于剩余時(shí)間約束的值迭代優(yōu)化模型。在求解時(shí)，首先確定無(wú)人機(jī)的初始節(jié)點(diǎn)，其次根據(jù)式（2）初始化各節(jié)點(diǎn)監(jiān)測(cè)的剩余時(shí)間，最后得到初始狀態(tài)向量。在執(zhí)行持續(xù)監(jiān)測(cè)任務(wù)過(guò)程中，通過(guò)值函數(shù)的迭代優(yōu)化，當(dāng)值函數(shù)達(dá)到收斂條件時(shí)，停止迭代，得到無(wú)人機(jī)最優(yōu)監(jiān)測(cè)策略。

算法的具體步驟如下：

1）初始化各節(jié)點(diǎn)最大允許監(jiān)測(cè)周期和狀態(tài)向量。無(wú)人機(jī)從節(jié)點(diǎn)1開始執(zhí)行監(jiān)測(cè)任務(wù)，即當(dāng)=1時(shí)，式（1）變?yōu)椋?/p>

4）重復(fù)步驟2）～3）搜索無(wú)人機(jī)路徑，直至值函數(shù)更新量小于給定的收斂閾值。

算法偽代碼見算法1。

算法1 無(wú)人機(jī)值函數(shù)迭代。

循環(huán)開始：

綜上所述，無(wú)人機(jī)每從一個(gè)監(jiān)測(cè)節(jié)點(diǎn)移動(dòng)到下一監(jiān)測(cè)節(jié)點(diǎn)后，將移動(dòng)后的節(jié)點(diǎn)重置為當(dāng)前節(jié)點(diǎn)，繼續(xù)按照要求尋找移動(dòng)路徑，最終完成持續(xù)監(jiān)測(cè)任務(wù)，并為無(wú)人機(jī)規(guī)劃一條安全的監(jiān)測(cè)路徑。

4 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證本文提出的持續(xù)監(jiān)測(cè)無(wú)人機(jī)路徑規(guī)劃算法的有效性，基于Matlab軟件仿真，分別設(shè)計(jì)了簡(jiǎn)單路網(wǎng)和復(fù)雜路網(wǎng)進(jìn)行對(duì)比分析。本文算法與傳統(tǒng)旅行商問(wèn)題（Traveling Salesman Problem， TSP）中的經(jīng)典遺傳算法（Genetic Algorithm， GA）、模擬退火（Simulated Annealing， SA）算法和蟻群算法（Ant Colony Optimization， ACO）對(duì)比。GA通過(guò)變異和交叉體現(xiàn)生物遺傳的多樣性；ACO通過(guò)種群間信息素的傳遞體現(xiàn)集群的智能協(xié)作；SA體現(xiàn)經(jīng)典溫度變化規(guī)律。簡(jiǎn)單路網(wǎng)的仿真參數(shù)如表1所示。

表1　仿真參數(shù)

簡(jiǎn)單路網(wǎng)如圖1所示，各節(jié)點(diǎn)的最大允許監(jiān)測(cè)周期與坐標(biāo)如表2所示。無(wú)人機(jī)初始狀態(tài)向量的節(jié)點(diǎn)位于節(jié)點(diǎn)1。

圖1　持續(xù)監(jiān)測(cè)路網(wǎng)

表2　各節(jié)點(diǎn)位置及其最大允許監(jiān)測(cè)周期

4.1　持續(xù)監(jiān)測(cè)路徑

圖2　收斂閾值

圖3　基于VFI的持續(xù)監(jiān)測(cè)路徑

無(wú)人機(jī)監(jiān)測(cè)時(shí)，若選擇不同的初始點(diǎn)，VFI算法得到的概率矩陣有微小差異。以初始點(diǎn)分別為節(jié)點(diǎn)1和10為例，得到的概率矩陣灰度圖如圖4所示。雖然圖4（a）和圖4（b）的灰度值略有不同，但趨勢(shì)和主要特征完全一致。因此，無(wú)人機(jī)每一步?jīng)Q策時(shí)基于最大概率得到的路徑點(diǎn)相同，這表明即使巡檢時(shí)初始點(diǎn)不同，仍然會(huì)獲得穩(wěn)定的相同的最優(yōu)路徑。

圖4　初始點(diǎn)為1和10時(shí)概率矩陣灰度圖

4.2　持續(xù)監(jiān)測(cè)結(jié)果隨機(jī)優(yōu)化

表3　持續(xù)監(jiān)測(cè)路徑對(duì)比

圖5中部分狀態(tài)向量的值函數(shù)差值大于0.3，原因?yàn)樵摖顟B(tài)向量的值函數(shù)首次更新差值較大且迭代過(guò)程中出現(xiàn)次數(shù)較少，同時(shí)說(shuō)明了其他狀態(tài)多次被訪問(wèn)、個(gè)別狀態(tài)很少被訪問(wèn)，排除了持續(xù)監(jiān)測(cè)路徑循環(huán)路徑的可能。

圖5　三條路徑的收斂曲線

圖6為3條優(yōu)化監(jiān)測(cè)路徑的部分片段。在整個(gè)持續(xù)監(jiān)測(cè)路徑中，3條路徑迭代10步之后，路徑節(jié)點(diǎn)出現(xiàn)局部循環(huán)情況，但它們對(duì)應(yīng)的收斂曲線圖中展現(xiàn)出重復(fù)的狀態(tài)少于21個(gè)，原因?yàn)椋籂顟B(tài)定義由11個(gè)變量構(gòu)成，狀態(tài)維度為11，迭代過(guò)程運(yùn)算量較大，在前期少量迭代學(xué)習(xí)時(shí)，僅有的節(jié)點(diǎn)數(shù)無(wú)法滿足隱藏的大量狀態(tài)的匹配。在迭代訓(xùn)練之后，持續(xù)監(jiān)測(cè)路徑的隨機(jī)性顯著提高，其中路徑3的隨機(jī)性最好，存在循環(huán)的路徑段僅第6至8步3個(gè)目標(biāo)點(diǎn)，路徑1中有第8至17步8個(gè)目標(biāo)點(diǎn)，路徑2中有第3至8步6個(gè)目標(biāo)點(diǎn)，存在循環(huán)的路徑目標(biāo)點(diǎn)越多，隨機(jī)性越差。使用信息熵驗(yàn)證基于值函數(shù)迭代持續(xù)監(jiān)測(cè)路徑的隨機(jī)性，熵值越大，路徑中的隨機(jī)性越強(qiáng)。

圖6　三條優(yōu)化的監(jiān)測(cè)路徑

不同算法生成的路徑如表4所示，將VFI算法生成的路徑1～3用VFI-1、VFI-2、VFI-3表示。

表4　不同持續(xù)監(jiān)測(cè)算法的路徑結(jié)果對(duì)比

VFI算法具有以下幾個(gè)優(yōu)點(diǎn)：

1）步驟簡(jiǎn)潔。VFI算法迭代學(xué)習(xí)一次完整路徑，沒有ACO中多次迭代完整路徑，也沒有GA的種群初始化。

2）調(diào)參數(shù)量少。VFI算法需要提前設(shè)定3個(gè)參數(shù)，GA、ACO和SA分別需要提前設(shè)定4、5和4個(gè)參數(shù)。

3）收斂快。VFI算法遵循獎(jiǎng)勵(lì)收益最大原則迭代學(xué)習(xí)一次完整路徑。GA編碼復(fù)雜，需要對(duì)問(wèn)題和對(duì)應(yīng)最優(yōu)解編碼，影響收斂速度。ACO使用隨機(jī)選擇，有助于尋找全局最優(yōu)解，但收斂慢。SA中溫度下降速度越慢，搜索時(shí)間越長(zhǎng)，可以獲得更優(yōu)的解，因此收斂較慢，否則可能跳過(guò)最優(yōu)解。

4.3　實(shí)際路網(wǎng)仿真實(shí)驗(yàn)

圖7　部分城區(qū)地圖及對(duì)應(yīng)的實(shí)際路網(wǎng)

根據(jù)圖7（b）監(jiān)測(cè)路網(wǎng)展開仿真實(shí)驗(yàn)，結(jié)果如圖8～9所示。整個(gè)程序響應(yīng)時(shí)間為0.575 9 s，信息熵為1.576 3，表明在短時(shí)間內(nèi)得到隨機(jī)性強(qiáng)的持續(xù)監(jiān)測(cè)路徑。

圖8　實(shí)際路網(wǎng)下監(jiān)測(cè)路徑的收斂曲線

圖9　實(shí)際路網(wǎng)下的最優(yōu)持續(xù)監(jiān)測(cè)路徑

5 結(jié)語(yǔ)

隨著網(wǎng)絡(luò)中目標(biāo)點(diǎn)增多，狀態(tài)向量維數(shù)也會(huì)增加，采用單架無(wú)人機(jī)監(jiān)測(cè)可能無(wú)法滿足每個(gè)目標(biāo)點(diǎn)的最大允許監(jiān)測(cè)周期，因此，未來(lái)工作將研究多無(wú)人機(jī)的協(xié)作持續(xù)監(jiān)測(cè)問(wèn)題。

[1] CANNATA G， SGORBISSA A. A minimalist algorithm for multirobot continuous coverage［J］. IEEE Transactions on Robotics， 2011， 27（2）： 297-312.

[2] PORTUGAL D， ROCHA R P. Multi-robot patrolling algorithms： examining performance and scalability［J］. Advanced Robotics， 2013， 27（5）： 325-336.

[3] MACHADO A， RAMALHO G， ZUCKER J D， et al. Multi-agent patrolling： an empirical analysis of alternative architectures［C］// Proceedings of the 2002 International Workshop on Multi-Agent Systems and Agent-Based Simulation， LNCS 2581. Berlin： Springer， 2003： 155-170.

[4] PASQUALETTI F， FRANCHI A， BULLO F. On cooperative patrolling： optimal trajectories， complexity analysis， and approximation algorithms［J］. IEEE Transactions on Robotics， 2012， 28（3）： 592-606.

[5] ELMALIACH Y， AGMON N， KAMINKA G A. Multi-robot area patrol under frequency constraints［J］. Annals of Mathematics and Artificial Intelligence， 2009， 57（3/4）： 293-320.

[6] CHEN Y， SHU Y， HU M， et al. Multi-UAV cooperative path planning with monitoring privacy preservation［J］. Applied Sciences， 2022， 12（23）： No.12111.

[7] ZHANG H， ZHAO J， WANG R， et al. Multi-objective reinforcement learning algorithm and its application in drive system［C］// Proceedings of the 34th Annual Conference of IEEE Industrial Electronics. Piscataway： IEEE， 2008： 274-279.

[8] OH J， GUO X， LEE H， et al. Action-conditional video prediction using deep networks in Atari games［C］// Proceedings of the 28th International Conference on Neural Information Processing Systems — Volume 2. Cambridge： MIT Press， 2015： 2863-2871.

[9] CAICEDO J C， LAZEBNIK S. Active object localization with deep reinforcement learning［C］// Proceedings of the 2015 IEEE International Conference on Computer Vision. Piscataway： IEEE， 2015： 2488-2496.

[10] LEWIS M， YARATS D， DAUPHIN Y， et al. Deal or no deal？ end-to-end learning of negotiation dialogues［C］// Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing. Stroudsburg， PA： ACL， 2017： 2443-2453.

[11] WEISZ G， BUDZIANOWSKI P， SU P H， et al. Sample efficient deep reinforcement learning for dialogue systems with large action spaces［J］. IEEE/ACM Transactions on Audio， Speech， and Language Processing， 2018， 26（11）： 2083-2097.

[12] DERHAMI V， PAKSIMA J， KHAJAH H. Web pages ranking algorithm based on reinforcement learning and user feedback［J］. Journal of AI and Data Mining， 2015， 3（2）： 157-168.

[13] BELLMAN R. On the theory of dynamic programming［J］. Proceedings of the National Academy of Sciences of the United States of America， 1952， 38（8）： 716-719.

[14] BRAVO R Z B， LEIRAS A， CYRINO OLIVEIRA F L. The use of UAV s in humanitarian relief： an application of POMDP-based methodology for finding victims［J］. Production and Operations Management， 2019， 28（2）： 421-440.

[15] BURKS L， AHMED N， LOEFGREN I， et al. Collaborative human-autonomy semantic sensing through structured POMDP planning［J］. Robotics and Autonomous Systems， 2021， 140： No.103753.

[16] AKBARINASAJI S， KAVAKLIOGLU C， BA?AR A， et al. Partially observable Markov decision process to generate policies in software defect management［J］. Journal of Systems and Software， 2020， 163： No.110518.

[17] HORáK K， BO?ANSKY B， PéCHOU?EK M. Heuristic search value iteration for one-sided partially observable stochastic games［C］// Proceedings of the 31st AAAI Conference on Artificial Intelligence. Palo Alto， CA： AAAI Press， 2017：558-564.

[18] LIU F， HUA X， JIN X. A hybrid heuristic value iteration algorithm for POMDP［C］// Proceedings of the IEEE 28th International Conference on Tools with Artificial Intelligence. Piscataway： IEEE， 2016： 304-310.

[19] 房俊恒. 基于點(diǎn)的值迭代算法在POMDP問(wèn)題中的研究［D］. 蘇州：蘇州大學(xué)， 2015： 25-35.（FANG J H. Research on point-based value iteration algorithms in POMDP domains［D］. Suzhou： Soochow University， 2015： 25-35.）

[20] WASHINGTON P H， SCHWAGER M. Reduced state value iteration for multi-drone persistent surveillance with charging constraints［C］// Proceedings of the 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems. Piscataway： IEEE， 2021： 6390-6397.

[21] BETHKE B， BERTUCCELLI L， HOW J P. Experimental demonstration of adaptive MDP-based planning with model uncertainty［C］// Proceedings of the 2008 AIAA Guidance， Navigation and Control Conference and Exhibit. Reston， VA： AIAA， 2008： No.6322.

[22] JEONG B M， HA J S， CHOI H L. MDP-based mission planning for multi-UAV persistent surveillance［C］// Proceedings of the 14th International Conference on Control， Automation and Systems. Piscataway： IEEE， 2014： 831-834.

[23] 陳佳，游曉明，劉升，等. 結(jié)合信息熵的多種群博弈蟻群算法［J］. 計(jì)算機(jī)工程與應(yīng)用， 2019， 55（16）：170-178.（CHEN J， YOU X M， LIU S， et al. Entropy-game based multi-population ant colony optimization［J］. Computer Engineering and Applications， 2019， 55（16）：170-178.）

[24] HA M， WANG D， LIU D. Generalized value iteration for discounted optimal control with stability analysis［J］. Systems and Control Letters， 2021， 147： No.104847.

UAV path planning for persistent monitoring based on value function iteration

LIU Chen1，2， CHEN Yang1，2*， FU Hao3

（1，，430081，；2（），430081，；3，，430081，）

The use of Unmanned Aerial Vehicle （UAV） to continuously monitor designated areas can play a role in deterring invasion and damage as well as discovering abnormalities in time， but the fixed monitoring rules are easy to be discovered by the invaders. Therefore， it is necessary to design a random algorithm for UAV flight path. In view of the above problem， a UAV persistent monitoring path planning algorithm based on Value Function Iteration （VFI） was proposed. Firstly， the state of the monitoring target point was selected reasonably， and the remaining time of each monitoring node was analyzed. Secondly， the value function of the corresponding state of this monitoring target point was constructed by combining the reward/penalty benefit and the path security constraint. In the process of the VFI algorithm， the next node was selected randomly based onprinciple and roulette selection. Finally， with the goal that the growth of the value function of all states tends to be saturated， the UAV persistent monitoring path was solved. Simulation results show that the proposed algorithm has the obtained information entropy of 0.905 0， and the VFI running time of 0.363 7 s. Compared with the traditional Ant Colony Optimization （ACO）， the proposed algorithm has the information entropy increased by 216%， and the running time decreased by 59%，both randomness and rapidity have been improved. It is verified that random UAV flight path is of great significance to improve the efficiency of persistent monitoring.

path planning; persistent monitoring; value iteration; roulette selection;principle

This work is partially supported by National Natural Science Foundation of China （62173262， 62073250）.

LIU Chen， born in 1998， M. S. candidate. His research interests include robot navigation and path planning.

CHEN Yang， born in 1980， Ph. D.， professor. His research interests include modeling， planning and control of mobile robots.

FU Hao， born in 1988， Ph. D.， lecturer. His research interests include multi-robot reinforcement learning.

1001-9081（2023）10-3290-07

10.11772/j.issn.1001-9081.2022091464

2022?09?30；

2023?01?13；

國(guó)家自然科學(xué)基金資助項(xiàng)目（62173262，62073250）。

劉晨（1998—），男，湖北洪湖人，碩士研究生，主要研究方向：機(jī)器人導(dǎo)航與路徑規(guī)劃； 陳洋（1980—），男，湖北荊門人，教授，博士，主要研究方向：移動(dòng)機(jī)器人建模、規(guī)劃與控制； 符浩（1988—），男，湖南桃江人，講師，博士，主要研究方向：多機(jī)器人強(qiáng)化學(xué)習(xí)。

TP242；TP18

A

2023?01?15。