劉晨，陳洋*，符浩

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

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

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

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

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

0 引言

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

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

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

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

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

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

本文的主要工作包括：

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

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

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

1 問題描述

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

無人機監(jiān)測過程應(yīng)當(dāng)滿足以下要求：

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

2）相鄰兩次到達同一個目標(biāo)點實施監(jiān)測的間隔時間不允許超過該目標(biāo)點的最大允許監(jiān)測周期；

3）監(jiān)測路徑具有較強的隨機性。

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

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

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

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

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

2.2　收益函數(shù)

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

2.3　值函數(shù)

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

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

式（7）中，各節(jié)點剩余時間的計算如下：

2.4　監(jiān)測路徑的隨機性

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

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

3 模型迭代求解

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

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

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

3.2　迭代終止條件

3.3　算法流程

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

算法的具體步驟如下：

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

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

算法偽代碼見算法1。

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

循環(huán)開始：

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

4 實驗與結(jié)果分析

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

表1　仿真參數(shù)

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

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

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

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

圖2　收斂閾值

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

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

圖4　初始點為1和10時概率矩陣灰度圖

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

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

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

圖5　三條路徑的收斂曲線

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

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

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

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

VFI算法具有以下幾個優(yōu)點：

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

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

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

4.3　實際路網(wǎng)仿真實驗

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

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

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

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

5 結(jié)語

隨著網(wǎng)絡(luò)中目標(biāo)點增多，狀態(tài)向量維數(shù)也會增加，采用單架無人機監(jiān)測可能無法滿足每個目標(biāo)點的最大允許監(jiān)測周期，因此，未來工作將研究多無人機的協(xié)作持續(xù)監(jiā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] 房俊恒. 基于點的值迭代算法在POMDP問題中的研究［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］. 計算機工程與應(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；

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

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

TP242；TP18

A

2023?01?15。