﻿ 启发式多无人机协同路网持续监视轨迹规划
 文章快速检索 高级检索

1. 西北工业大学 航天学院, 西安 710072;
2. 西北工业大学 航天飞行动力学技术重点实验室, 西安 710072

Cooperation path planning of multi-UAV in road-network continuous monitoring
WANG Tong1,2, HUANG Panfeng1,2, DONG Gangqi1,2
1. School of Astronautics, Northwestern Polytechnical University, Xi'an 710072, China;
2. National Key Laboratory of Aerospace Flight Dynamics, Northwestern Polytechnical University, Xi'an 710072, China
Abstract: In this paper, the problem of continuous monitoring of rotor UAVs in road-network environment is studied. Based on the optimization principle, the multi-UAVs road-network continuous monitoring problem is defined. By simplifying the discrete process for environment, considering the detection accuracy of sensors, and introducing uncertainty measurement, a model for road-network continuous monitoring is constructed. To address the particularity of path planning in continuous monitoring, a heuristic multi-UAVs cooperative path planning algorithm is designed. The theoretical analysis and simulation comparison verify the feasibility, accuracy, and generality of the proposed algorithm in multi-UAVs road-network continuous monitoring. As an extension of road-network patrolling method, this algorithm can not only provide a solution for the continuous monitoring task of road-network, but also be applied to the persistent data collection and continuous coverage tasks based on the graph model.
Keywords: heuristic algorithm    multi-UAVs    cooperation    sensor coverage    road-network    continuous monitoring

1 路网持续监视问题建模 1.1 问题描述

1.2 环境离散化模型

1.3 监视指标构建

 ${f_{\rm{c}}} = \left\{ {\begin{array}{*{20}{l}} 1&{d \le {d_{\rm{c}}}}\\ {\left( {{d_{\rm{c}}} - d} \right)/\left( {{d_1} - {d_{\rm{c}}}} \right) + 1}&{{d_{\rm{c}}} < d \le {d_1}}\\ 0&{d > {d_1}} \end{array}} \right.$ （1）

 ${F_{{\rm{c}}i}} = \prod\limits_{r = 1}^{{R_i}} {\left( {1 - {f_{{\rm{c}}r}}} \right)}$ （2）

 ${t_{{\rm{a}}i}} = {t_k} - {t_{{\rm{lv}}i}}$ （3）

 ${\delta _i} = {\sigma _i}\left( {{t_k} - {t_{{\rm{lv}}i}}} \right)\prod\limits_{r = 1}^{{R_i}} {\left( {1 - {f_{{\rm{c}}r}}} \right)}$ （4）

1.4 不确定度归一化

 $\delta _i^N = {\sigma _i}\left( {{t_k} - {t_{1{\rm{v}}i}}} \right)\prod\limits_{r = 1}^{{R_i}} {\left( {1 - {f_{{\rm{c}}r}}} \right)} /{t_{{\rm{lim}}}}$ （5）

1.5 问题公式化

 ${C_1} = \frac{1}{N}\sum\limits_{i = 1}^N {\delta _{ji}^N}$ （6）

2 多无人机持续监视轨迹规划

2.1 决策量设计

 ${A_{ir}} = \delta _i^N - {q_w}d_{\min }^r/\left( {{\sigma _i}{v_r}{t_{\lim }}} \right)$ （7）

 图 1 可覆盖最短路 Fig. 1 Shortest observable path

2.2 单无人机轨迹规划方法

1) 决策简化：为简化决策难度，规定当无人机抵达监测点时才进行规划，规划后将沿着此方向一直移动直至下一监测点。由于实际数值离散精度原因，当无人机实际位置到监测点位置的距离dr≤0.5vrdt时，则无人机抵达，其中，dt为算法的规划时间步长。

2) 折返抑制：由于路网的复杂拓扑结构，无法准确判断无人机原路返回是否不利于减小整体监视不确定度，因此允许无人机原路折返，但根据各点的度dgi确定无人机在该点的折返概率，取折返的概率Pb满足：

 ${p_{\rm{b}}} = \left\{ {\begin{array}{*{20}{l}} 1&{{d_{{\rm{g}}i}} = 1}\\ {0.4/{d_{{\rm{g}}i}}}&{{d_{{\rm{g}}i}} > 1} \end{array}} \right.$ （8）

3) 防止停留：当无人机在某监测点停留时，系统将随机指定该点所有连接的边中的一个，作为下一时刻的前进方向。

2.3 多无人机协作决策方法

1) 减少轨迹重复：无人机经过某边或即将经过某边时，向其他无人机报告，其他无人机在规划时将尽量减少经过此边的概率。

2) 分散布局：无人机选中目标点后，通知其他无人机，其他无人机将远离该目标点。

 算法1  多无人机协同路网持续监视算法 Load  G=(V, E)，fc，σ=[σ1, σ2, …, σN] Input   T，R，Δt，vr，X0r，tlim Output  无人机轨迹XTr 1  计算各监视点的完全覆盖点 2  for  任务期T内的每隔规划步长dt取j 3  δiN≤每个监视点的归一化不确定度 4  for  每个无人机r 5    报告自身位置与前进方向 6    if  抵达某个监视点 7      获取其他无人机的位置与前进方向 8      减小轨迹重复 9      分散布局 10      寻找max Air的监视点 11      计算去往max Air处的可覆盖最短路 12      if 新方向与原方向相反 13      折返抑制 14      elseif  无人机停留 15      防止停留 16        选定新方向 17     往新方向移动
2.4 算法复杂度分析

3 仿真与结果 3.1 性能评价指标

1) 平均不确定度指每个时步中所有监测点的归一化不确定度的平均值，计算方法见式(6)。

2) 最大间隔时间是从稳定监视状态至任务结束，各监视点的归一化不确定度的最大值。其中，无人机的稳定监视状态为无人机至少完成一次全区域覆盖后的时间。

3) 平均不确定度均值是从稳定监视状态至任务结束，区域内各点归一化不确定度的均值：

 ${C_3} = \frac{1}{{T - {t_{\rm{w}}} + 1}}\sum\limits_{j = {t_{\rm{w}}}}^T {\delta _j^N}$ （9）

4) 平均不确定度方差是从稳定监视状态至任务结束，区域内各点归一化不确定度的标准差：

 ${C_4} = \sqrt {\frac{1}{{T - {t_{\rm{w}}} + 1}}\sum\limits_{j = {t_{\rm{w}}}}^T {{{\left( {\delta _j^N - {C_3}} \right)}^2}} }$ （10）
3.2 仿真结果

 图 2 路网模型图 Fig. 2 Model of road-network

3.2.1 算法的准确性

 图 3 不同场景下的平均不确定度 Fig. 3 Average value of uncertainty in different conditions

 路网编号 监视权重 完全探测范围dc/m 最大不确定度C2 平均不确定度均值C3 平均不确定度方差C4 G1 AW 10 0.625 8 0.143 8 0.016 1 100 0.581 6 0.082 2 0.017 0 200 0.454 6 0.027 9 0.012 1 SW 10 0.763 8 0.151 0 0.017 5 100 0.605 2 0.084 4 0.015 6 200 0.550 4 0.028 1 0.011 7 G2 AW 10 0.532 8 0.141 6 0.019 6 100 0.395 4 0.048 9 0.009 3 200 0.313 8 0.020 4 0.011 3 SW 10 0.773 0 0.145 6 0.015 1 100 0.468 5 0.054 9 0.010 5 200 0.365 2 0.021 5 0.011 8 G2 AW 10 0.417 4 0.134 8 0.010 2 100 0.496 6 0.062 8 0.011 0 200 0.367 6 0.013 3 0.005 3 SW 10 0.633 7 0.148 7 0.009 7 100 0.523 8 0.070 0 0.012 1 200 0.553 0 0.013 9 0.005 3

3.2.2 算法的通用性

 图 4 G1模型中不同监视权重下的最大不确定度 Fig. 4 Maximum uncertainty of G1 with different conditions
3.2.3 算法的有效性

 图 5 不同协作模式下的算法性能 Fig. 5 Performance criteria in different cooperation modes
3.2.4 算法的可扩展性

 图 6 无人机数目变化对算法性能的影响 Fig. 6 Variation of performance criteria with number of UAVs
4 结论

1) 定义了无人机路网持续监视问题，建立了基于传感器监视准确度的持续监视问题模型，提出了协同持续监视轨迹规划算法。

2) 所提算法对基于间隔时间的多机器人巡逻问题和基于传感器监视准确度的路网持续监视问题具有通用性。

3) 所提算法具有离线和在线规划能力，解决了多无人机协同路网持续监视轨迹规划问题，同时也为基于图模型的持续数据采集、连续覆盖等任务提供了一种有效的解决方案。

 [1] RASMUSSEN S, KALYANAM K, KINGSTON D. Field experiment of a fully autonomous multiple UAV/UGS intruder detection and monitoring system[C]//2016 International Conference on Unmanned Aircraft Systems (ICUAS), 2016. [2] TROTTA A, FELICE M D, MONTORI F, et al. Joint coverage, connectivity, and charging strategies for distributed UAV networks[J]. IEEE Transactions on Robotics, 2018, 34(4): 883-900. Click to display the text [3] GARCIA A P, ROLDAN J J, BARRIENTOS A. Monitoring traffic in future cities with aerial swarms:Developing and optimizing a behavior-based surveillance algorithm[J]. Cognitive Systems Research, 2019, 54: 273-286. Click to display the text [4] ABBASI F, MESBAHI A, VELNI J M. A new voronoi-based blanket coverage control method for moving sensor networks[J]. IEEE Transactions on Control Systems Technology, 2019, 27(1): 409-417. Click to display the text [5] ROLDAN J J, GARCIA A P, GARZON M, et al. Heterogeneous multi-robot system for mapping environmental variables of greenhouses[J]. Sensors, 2016, 16(7): 1018. Click to display the text [6] KHAN A, RINNER B, CAVALLARO A. Cooperative robots to observe moving targets:Review[J]. IEEE Transactions on Cybernetics, 2018, 48(1): 187-198. Click to display the text [7] KOLLING A, KLEINER A, CARPIN S. Coordinated search with multiple robots arranged in line formations[J]. IEEE Transactions on Robotics, 2018, 34(2): 459-473. Click to display the text [8] THAKOOR O, GARG J, NAGI R. Multiagent UAV routing:A game theory analysis with tight price of anarchy bounds[J]. IEEE Transactions on Automation Science and Engineering, 2019, 17(11): 1-17. Click to display the text [9] NIGAM N, BIENIAWSKI S, KROO I, et al. Control of multiple UAVs for persistent surveillance:Algorithm and flight test results[J]. IEEE Transactions on Control Systems Technology, 2012, 20(5): 1236-1251. Click to display the text [10] 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. Click to display the text [11] TOKEKAR P, HOOK J V, MULLA D, et al. Sensor planning for a symbiotic UAV and UGV system for precision agriculture[J]. IEEE Transactions on Robotics, 2016, 32(6): 1498-1511. Click to display the text [12] PORTUGAL D, ROCHA R. A survey on multi-robot patrolling algorithms[M]. Berlin: Springer, 2011. [13] ALAMDARI S, FATA E, SMITH S L. Persistent monitoring in discrete environments:Minimizing the maximum weighted latency between observations[J]. The International Journal of Robotics Research, 2014, 33(1): 138-154. Click to display the text [14] YANOVSKI V, WAGNER I A, BRUCKSTEIN A M. A distributed ant algorithm for protect efficiently patrolling a network[J]. Algorithmica, 2003, 37(3): 165-186. Click to display the text [15] CHEN H, CHENG T, WISE S. Developing an online cooperative police patrol routing strategy[J]. Computers, Environment and Urban Systems, 2017, 62: 19-29. Click to display the text [16] PASQUALETTI F, DURHAM J W, BULLO F. Cooperative patrolling via weighted tours:Performance analysis and distributed algorithms[J]. IEEE Transactions on Robotics, 2012, 28(5): 1181-1188. Click to display the text [17] CHEVALEYRE Y. Theoretical analysis of the multi-agent patrolling problem[C]//IEEE/WIC/ACM International Conference on Intelligent Agent Technology. Piscataway: IEEE Press, 2004. [18] WIANDT B, SIMON V. Autonomous graph partitioning for multi-agent patrolling problems[C]//Federated Conference on Computer Science and Information Systems, 2018. [19] CHEN H, CHENG T, YE X. Designing efficient and balanced police patrol districts on an urban street network[J]. International Journal of Geographical Information Science, 2019, 33(2): 269-290. Click to display the text [20] TURNER J, MENG Q, SCHAEFER G, et al. Distributed task rescheduling with time constraints for the optimization of total task allocations in a multi-robot system[J]. IEEE Transactions on Cybernetics, 2018, 48(9): 2583-2597. Click to display the text [21] ARSLAN O, KODITSCHEK D E. Sensor-based reactive navigation in unknown convex sphere worlds unknown convex sphere worlds[J]. The International Journal of Robotics Research, 2019, 38(2-3): 196-223. Click to display the text [22] AZEVEDO S P, SILVA S R, NAZARIO R A. Reducing the range of perception in multi-agent patrolling strategies[J]. Journal of Intelligent & Robotic Systems, 2018, 91(2): 219-231. Click to display the text [23] WAGNER I A, ALTSHULER Y, YANOVSKI V, et al. Cooperative cleaners:A study in ant robotics[J]. The International Journal of Robotics Research, 2008, 27(1): 127-151. Click to display the text [24] PARK C, KIM Y, JEONG B. Heuristics for determining a patrol path of an unmanned combat vehicle[J]. Computers & Industrial Engineering, 2012, 63(1): 150-160. Click to display the text [25] HOSHINO S, ISHIWATA T. Probabilistic surveillance by mobile robot for unknown intruders[C]//2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Piscataway: IEEE Press, 2015. [26] CHEN S, WU F, SHEN L, et al. Decentralized patrolling under constraints in dynamic environments[J]. IEEE Transactions on Cybernetics, 2016, 46(12): 3364-3376. Click to display the text [27] PORTUGAL D, ROCHA R P. Cooperative multi-robot patrol with Bayesian learning[J]. Autonomous Robots, 2016, 40(5): 929-953. Click to display the text [28] PITA J, JAIN M, ORDONEZ F, et al. Using game theory for Los Angeles airport security[J]. AI Magazine, 2009, 30(1): 43-57. Click to display the text [29] BOGERT K, DOSHI P. Multi-robot inverse reinforcement learning under occlusion with estimation of state transitions[J]. Artificial Intelligence, 2018, 263: 46-73. Click to display the text [30] HUANG L, ZHOU M, HAO K, et al. A survey of multi-robot regular and adversarial patrolling[J]. IEEE/CAA Journal of Automatica Sinica, 2019, 6(4): 894-903. Click to display the text [31] YU J, KARAMAN S, RUS D. Persistent monitoring of events with stochastic arrivals at multiple stations[J]. IEEE Transactions on Robotics, 2015, 31(3): 521-535. Click to display the text [32] CHEN H, CHENG T, SHAWE T J. A balanced route design for min-max multiple-depot rural postman problem(MMMDRPP):A police patrolling case[J]. International Journal of Geographical Information Science, 2018, 32(1): 169-190. Click to display the text [33] WALLAR A, PLAKU E, SOFGE D A. Reactive motion planning for unmanned aerial surveillance of risk-sensitive areas[J]. IEEE Transactions on Automation Science and Engineering, 2015, 12(3): 969-980. Click to display the text [34] SRIVASTAVA V, PASQUALETTI F, BULLO F. Stochastic surveillance strategies for spatial quickest detection[J]. The International Journal of Robotics Research, 2013, 32(12): 1438-1458. Click to display the text [35] NIGAM N. The multiple unmanned air vehicle persistent surveillance problem:A review[J]. Machines, 2014, 2(1): 13-69. Click to display the text
http://dx.doi.org/10.7527/S1000-6893.2019.23753

0

#### 文章信息

WANG Tong, HUANG Panfeng, DONG Gangqi

Cooperation path planning of multi-UAV in road-network continuous monitoring

Acta Aeronautica et Astronautica Sinica, 2020, 41(S1): 723753.
http://dx.doi.org/10.7527/S1000-6893.2019.23753