基于值函數迭代的持續監測無人機路徑規劃

劉晨，陳洋*，符浩

基于值函數迭代的持續監測無人機路徑規劃

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

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

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

路徑規劃；持續監測；值迭代；輪盤選擇；原則

0 引言

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

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

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

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

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

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

本文的主要工作包括：

1）考慮持續監測路網和剩余時間約束，結合獎勵和懲罰收益，設計值函數建立無人機持續監測路徑規劃模型。

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

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

1 問題描述

本文假設持續監測任務由一架旋翼無人機完成。為了方便分析，可以將旋翼無人機視為轉彎半徑為0、勻速飛行的質點。已知所有待監測目標點構成的拓撲網絡和各目標點的最大允許監測周期，其中，目標點的最大允許監測周期指無人機相鄰兩次監測同一個目標點之間的最大允許時間間隔。如果無人機在該時間間隔之內未能到達相應目標點，表示監測任務失敗。

無人機監測過程應當滿足以下要求：

1）盡可能提高各個待監測節點的訪問頻率；

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

3）監測路徑具有較強的隨機性。

為了獲得無人機最優的監測路徑，不允許無人機持續停留在任意一個目標節點的位置。

2 持續監測路徑規劃模型

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

建立路徑規劃模型的思路如下：確定無人機的每一個狀態，對每個可能的下一目標點計算選擇此點后達到下一個狀態的期望價值；比較選擇哪個目標點達到的狀態的期望值函數最大，將這個期望值函數作為當前狀態的值函數，并循環執行這個步驟，直到值函數收斂。

2.1　狀態向量與動作空間

2.2　收益函數

其中sgn為符號函數。

2.3　值函數

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

更新后的狀態：

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

2.4　監測路徑的隨機性

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

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

3 模型迭代求解

值迭代算法運行初期，節點被逐漸訪問，無法判斷有多少種狀態向量以及對應的值函數產生。隨著迭代次數的增加，狀態向量逐漸增多。本文采用值迭代和輪盤選擇結合的方法：

3.1　下一節點的選擇策略

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

3.2　迭代終止條件

3.3　算法流程

本文針對持續監測問題，建立了基于剩余時間約束的值迭代優化模型。在求解時，首先確定無人機的初始節點，其次根據式（2）初始化各節點監測的剩余時間，最后得到初始狀態向量。在執行持續監測任務過程中，通過值函數的迭代優化，當值函數達到收斂條件時，停止迭代，得到無人機最優監測策略。

算法的具體步驟如下：

1）初始化各節點最大允許監測周期和狀態向量。無人機從節點1開始執行監測任務，即當=1時，式（1）變為：

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

算法偽代碼見算法1。

算法1 無人機值函數迭代。

循環開始：

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

4 實驗與結果分析

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

表1　仿真參數

簡單路網如圖1所示，各節點的最大允許監測周期與坐標如表2所示。無人機初始狀態向量的節點位于節點1。

圖1　持續監測路網

表2　各節點位置及其最大允許監測周期

4.1　持續監測路徑

圖2　收斂閾值

圖3　基于VFI的持續監測路徑

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

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

4.2　持續監測結果隨機優化

表3　持續監測路徑對比

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

圖5　三條路徑的收斂曲線

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

圖6　三條優化的監測路徑

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

表4　不同持續監測算法的路徑結果對比

VFI算法具有以下幾個優點：

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

2）調參數量少。VFI算法需要提前設定3個參數，GA、ACO和SA分別需要提前設定4、5和4個參數。

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

4.3　實際路網仿真實驗

圖7　部分城區地圖及對應的實際路網

根據圖7（b）監測路網展開仿真實驗，結果如圖8～9所示。整個程序響應時間為0.575 9 s，信息熵為1.576 3，表明在短時間內得到隨機性強的持續監測路徑。

圖8　實際路網下監測路徑的收斂曲線

圖9　實際路網下的最優持續監測路徑

5 結語

隨著網絡中目標點增多，狀態向量維數也會增加，采用單架無人機監測可能無法滿足每個目標點的最大允許監測周期，因此，未來工作將研究多無人機的協作持續監測問題。

[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］. 蘇州：蘇州大學， 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] 陳佳，游曉明，劉升，等. 結合信息熵的多種群博弈蟻群算法［J］. 計算機工程與應用， 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；

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

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

TP242；TP18

A

2023?01?15。