-
摘要: 由无人机(Unmanned aerial vehicles, UAV)和地面移动机器人组成的异构机器人系统在协作执行任务时, 可以充分发挥两类机器人各自的优势. 无人机运动灵活, 但通常续航能力有限; 地面机器人载荷多, 适合作为无人机的着陆平台和移动补给站, 但运动受路网约束. 本文研究这类异构机器人系统协作路径规划问题. 为了降低完成任务的时间代价, 提出一种由蚁群算法(Ant colony optimization, ACO)和遗传算法(Genetic algorithm, GA)相结合的两步法对地面机器人和无人机的路线进行解耦, 同时规划地面机器人和无人机的路线. 第1步使用蚁群算法为地面机器人搜索可行路线. 第2步对无人机的最优路径建模, 采用遗传算法求解并将无人机路径长度返回至第1步中, 用于更新路网的信息素参数, 从而实现异构协作系统路径的整体优化. 另外, 为了进一步降低无人机的飞行时间代价, 研究了无人机在其续航能力内连续完成多任务的协作路径规划问题. 最后, 通过大量仿真实验验证了所提方法的有效性.Abstract: The heterogeneous robot system, composed of unmanned aerial vehicles (UAVs) and ground mobile robots, can give full play to the respective advantages of the two types of robots when performing tasks in cooperation. UAVs have the characteristics of flexibility, but they usually have limited endurance. Ground robots can bear large loads and are suitable for use as landing platforms and mobile replenishment stations for UAVs, but their movement is constrained by the road network. This paper studies the cooperative path planning of the heterogeneous robot systems. In order to reduce the time cost of the task, this paper proposes a two-step strategy combining ant colony optimization (ACO) and genetic algorithm (GA) to decouple the routes of mobile robot and UAV, and plans the routes of mobile robot and UAV at the same time. In the first step, ant colony optimization is used to search for feasible routes of the mobile robot. In the second step, we derive the model of the UAV＇s optimal path and use the genetic algorithm to solve it. The UAV path length is returned to the first step to update the pheromone in the road network. Then, we realize the overall optimization of the heterogeneous collaborative system path. In order to further reduce the flight time cost of UAVs, this paper also studies the problem of cooperative path planning for UAVs to continuously complete multiple tasks within their endurance capabilities. Finally, a large number of simulation experiments verify the effectiveness of the proposed method.
-
Key words:
- Heterogeneous robot systems /
- path planning /
- road network constraint /
- two-step strategy
-
图 3 路网约束下异构机器人系统示意图
Fig. 3 Schematic diagram of heterogeneous robot system with road network constraints
图 9 复杂路网交通中断时的仿真结果
Fig. 9 Simulation results on the complex road network in case interruption
图 13 染色体的可行交叉变异位置
Fig. 13 Feasible positions of cross and mutation within a chromosome
图 14 无人机一次访问一个目标点的路径规划结果
Fig. 14 Path planning results of drone visiting one point each time
图 15 无人机一次访问多个目标点的路径规划结果
Fig. 15 Path planning results of drone visiting multi-points each time
表 1 code2的一个编码示例
Table 1 A sample of code2
编码对象 编码内容 code1 基因值 2 3 1 4 code2 基因值 15 62 78 104 350 461 666 692 $\boldsymbol{\alpha } $, $\boldsymbol{\beta } $为1
的元素${\alpha } _{15, 2}$ ${\beta } _{62, 2}$ ${\alpha } _{78, 3}$ ${\beta }_{104, 3}$ ${\alpha } _{350, 1}$ ${\beta }_{461, 1}$ ${\alpha }_{666, 4}$ ${\beta }_{692, 4}$ 
下载: 导出CSV
表 2 简单路网仿真中无人机的约束违反量 (h)
Table 2 UAV constraints violations in the simulation of the simple road network (h)
目标点 无人机
用时$t_a $约束(9)违反量
$\max(t_a-U,0) $地面车
耗时$t_g $时间差
$|t_a-t_g| $${\tilde {\boldsymbol{q}}_1}({{\boldsymbol{q}}_5})$ 0.1271 0 0.128 0.0009 ${\tilde {\boldsymbol{q}}_2}({{\boldsymbol{q}}_4})$ 0.1599 0 0.160 0.0001 ${\tilde {\boldsymbol{q} }_3}({ {\boldsymbol{q} }_3})$ 0.1613 0 0.160 0.0013 ${\tilde {\boldsymbol{q}}_4}({{\boldsymbol{q}}_2})$ 0.1392 0 0.140 0.0008 ${\tilde {\boldsymbol{q}}_5}({{\boldsymbol{q}}_1})$ 0.0533 0 0.052 0.0013
下载: 导出CSV
表 3 复杂路网仿真中无人机的约束违反量 (h)
Table 3 UAV constraint violations in the simulation of the complex road network (h)
目标点 无人机
用时$ t_a $约束(9)违反量
$\max(t_a-U,0) $地面车
耗时$t_g $时间差
$ |t_a-t_g| $${\tilde {\boldsymbol{q}}_1}({{\boldsymbol{q}}_4})$ 0.0859 0 0.086 0.0001 ${\tilde {\boldsymbol{q}}_2}({{\boldsymbol{q}}_5})$ 0.0761 0 0.076 0.0001 ${\tilde {\boldsymbol{q}}_3}({{\boldsymbol{q}}_3})$ 0.0482 0 0.048 0.0002 ${\tilde {\boldsymbol{q}}_4}({{\boldsymbol{q}}_1})$ 0.2331 0 0.224 0.0091 ${\tilde {\boldsymbol{q}}_5}({{\boldsymbol{q}}_2})$ 0.0668 0 0.066 0.0008 ${\tilde {\boldsymbol{q}}_6}({{\boldsymbol{q}}_6})$ 0.1078 0 0.108 0.0002 ${\tilde {\boldsymbol{q}}_7}({{\boldsymbol{q}}_7})$ 0.1643 0 0.164 0.0003 ${\tilde {\boldsymbol{q}}_8}({{\boldsymbol{q}}_{10}})$ 0.1042 0 0.104 0.0002 ${\tilde {\boldsymbol{q}}_9}({{\boldsymbol{q}}_9})$ 0.0863 0 0.086 0.0003 ${\tilde {\boldsymbol{q}}_{10}}({{\boldsymbol{q}}_8})$ 0.1084 0 0.108 0.0004
下载: 导出CSV
表 4 交通中断仿真中无人机的约束违反量 (h)
Table 4 UAV constraint violations in the simulation with traffic interruption (h)
目标点 无人机
用时$t_a $约束(9)违反量
$\max(t_a-U,0)$地面车
耗时$t_g $时间差
$|t_a-t_g| $${\tilde {\boldsymbol{q}}_1}({\boldsymbol{q}}_5)$ 0.1338 0 0.134 0.0002 ${\tilde {\boldsymbol{q}}_2}({\boldsymbol{q}}_4)$ 0.2137 0 0.214 0.0003 ${\tilde {\boldsymbol{q}}_3}({\boldsymbol{q}}_3)$ 0.1899 0 0.190 0.0001 ${\tilde {\boldsymbol{q}}_4}({\boldsymbol{q}}_1)$ 0.2244 0 0.224 0.0004 ${\tilde {\boldsymbol{q}}_5}({\boldsymbol{q}}_2)$ 0.0766 0 0.076 0.0006 ${\tilde {\boldsymbol{q}}_6}({\boldsymbol{q}}_6)$ 0.1070 0 0.106 0.0010 ${\tilde {\boldsymbol{q}}_7}({\boldsymbol{q}}_7)$ 0.1625 0 0.162 0.0005 ${\tilde {\boldsymbol{q}}_8}({\boldsymbol{q}}_{10})$ 0.0910 0 0.092 0.0010 ${\tilde {\boldsymbol{q}}_9}({\boldsymbol{q}}_{9})$ 0.0981 0 0.098 0.0001 ${\tilde {\boldsymbol{q}}_{10}}({\boldsymbol{q}}_{8})$ 0.1074 0 0.108 0.0006
下载: 导出CSV
表 5 简单路网中的比较结果
Table 5 Comparison results in simple road network
算法名称 最优代价值 平均运行时间 (s) MACO-GA 56.8479 0.1832 MACO-PSO 87.6916 0.3628
下载: 导出CSV
表 6 复杂路网中的比较结果
Table 6 Comparison results in complex road network
算法名称 最优代价值 平均运行时间 (s) MACO-GA 116.8250 0.2453 MACO-PSO 331.2657 0.4873
下载: 导出CSV
表 7 无人机每次访问单个目标点时的约束违反量 (h)
Table 7 UAV constraint violations when it is allowed to visit one point each time (h)
目标点 无人机
用时$t_a $约束(9)违反量
$\max(t_a-U,0) $地面车
耗时$t_g $时间差
$|t_a-t_g| $${\tilde {\boldsymbol{q}}_1}({\boldsymbol{q}}_4)$ 0.0784 0 0.076 0.0024 ${\tilde {\boldsymbol{q}}_2}({\boldsymbol{q}}_5)$ 0.0670 0 0.066 0.0010 ${\tilde {\boldsymbol{q}}_3}({\boldsymbol{q}}_{11})$ 0.0941 0 0.090 0.0041 ${\tilde {\boldsymbol{q}}_4}({\boldsymbol{q}}_{12})$ 0.0579 0.1921 0.058 0.0001 ${\tilde {\boldsymbol{q}}_5}({\boldsymbol{q}}_3)$ 0.0544 0 0.054 0.0004 ${\tilde {\boldsymbol{q}}_6}({\boldsymbol{q}}_1)$ 0.2512 0.0012 0.246 0.0052 ${\tilde {\boldsymbol{q}}_7}({\boldsymbol{q}}_2)$ 0.0669 0 0.066 0.0009 ${\tilde {\boldsymbol{q}}_8}({\boldsymbol{q}}_6)$ 0.1150 0 0.114 0.0010 ${\tilde {\boldsymbol{q}}_9}({\boldsymbol{q}}_7)$ 0.1368 0 0.136 0.0008 ${\tilde {\boldsymbol{q}}_{10}}({\boldsymbol{q}}_{10})$ 0.0863 0 0.086 0.0003 ${\tilde {\boldsymbol{q}}_{11}}({\boldsymbol{q}}_{13})$ 0.1033 0 0.088 0.0153 ${\tilde {\boldsymbol{q}}_{12}}({\boldsymbol{q}}_{14})$ 0.1303 0 0.120 0.0103 ${\tilde {\boldsymbol{q}}_{13}}({\boldsymbol{q}}_9)$ 0.0798 0 0.078 0.0018 ${\tilde {\boldsymbol{q}}_{14}}({\boldsymbol{q}}_8)$ 0.1068 0 0.106 0.0008
下载: 导出CSV
表 8 允许无人机每次访问多个目标点时的约束违反量 (h)
Table 8 UAV constraint violations when it is allowed to visit multi-points each time (h)
目标点 无人机
用时$t_a $约束(9)违反量
$\max(t_a-U,0) $地面车
耗时$t_g $时间差
$|t_a-t_g| $${\tilde {\boldsymbol{q}}_1}({\boldsymbol{q}}_4)$ 0.0811 0 0.0800 0.0011 ${\tilde {\boldsymbol{q}}_2}({\boldsymbol{q}}_5,{\boldsymbol{q}}_{11})$ 0.1115 0 0.1120 0.0005 ${\tilde {\boldsymbol{q}}_3}({\boldsymbol{q}}_{12},{\boldsymbol{q}}_{3})$ 0.0620 0 0.0630 0.0010 ${\tilde {\boldsymbol{q}}_4}({\boldsymbol{q}}_1)$ 0.2460 0 0.2440 0.0020 ${\tilde {\boldsymbol{q}}_5}({\boldsymbol{q}}_2)$ 0.0680 0 0.0680 0 ${\tilde {\boldsymbol{q}}_6}({\boldsymbol{q}}_6)$ 0.1099 0 0.1100 0.0001 ${\tilde {\boldsymbol{q}}_6}({\boldsymbol{q}}_7)$ 0.1458 0 0.1460 0.0002 ${\tilde {\boldsymbol{q}}_8}({\boldsymbol{q}}_{10},{\boldsymbol{q}}_{13})$ 0.1122 0 0.1120 0.0002 ${\tilde {\boldsymbol{q}}_9}({\boldsymbol{q}}_{14},{\boldsymbol{q}}_{9})$ 0.1458 0 0.1460 0.0002 ${\tilde {\boldsymbol{q}}_{10}}({\boldsymbol{q}}_8)$ 0.1067 0 0.1062 0.0005
下载: 导出CSV
-
[1] Garone E, Naldi R, Casavola A, Frazzoli E. Cooperative mission planning for a class of carrier-vehicle systems. In: Proceedings of the 49th IEEE Conference on Decision and Control (CDC). Atlanta, Georgia, USA: IEEE, 2010. 1354–1359 [2] 武文亮, 周兴社, 沈博, 赵月. 集群机器人系统特性评价研究综述. 自动化学报, 2022, 48(5): 1153−1172 doi: 10.16383/j.aas.c200964Wu Wen-Liang, Zhou Xing-She, Shen Bo, Zhao Yue. A review of swarm robotic systems property evaluation research. Acta Automatica Sinica, 2022, 48(5): 1153−1172 doi: 10.16383/j.aas.c200964 [3] Ulmer M W, Thomas B W. Same-day delivery with heterogeneous fleets of drones and vehicles. Networks, 2018, 72(4): 475-505. doi: 10.1002/net.21855 [4] Mario M, Leonardo C, Michele O, Dell’Orco M. En route truck–drone parcel delivery for optimal vehicle routing strategies. IET Intelligent Transport Systems, 2018, 12(4): 253-261. doi: 10.1049/iet-its.2017.0227 [5] Klauco M, Blažek S, Kvasnica M. An optimal path planning problem for heterogeneous multi-vehicle systems. International Journal of Applied Mathematics and Computer Science, 2016, 26(2): 297-308. doi: 10.1515/amcs-2016-0021 [6] Wang T, Huang P F, Dong G Q. Modeling and path planning for persistent surveillance by unmanned ground vehicle. IEEE Transactions on Automation Science and Engineering, 2021, 18(4): 1615−1625 [7] Ding Y L, Xin B, Zhang H, Chen J. A memetic algorithm for curvature-constrained path planning of messenger UAV in air-ground coordination. In: Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics (SMC). Toronto, ON, Canada: IEEE, 2020. 1465–1472 [8] Ramasamy M, Ghose D. Learning-based preferential surveillance algorithm for persistent surveillance by unmanned aerial vehicles. In: Proceedings of the International Conference on Unmanned Aircraft Systems (ICUAS). Arlington, VA, USA: IEEE, 2016. 1032–1040 [9] 李勇, 李坤成, 孙柏青, 张秋豪, 王义娜, 杨俊友. 智能体Petri网融合的多机器人-多任务协调框架. 自动化学报, 2021, 47(8): 2029−2049. https://doi.org/10.16383/j.aas.c190400. doi: 10.16383/j.aas.c190400LI Yong, LI Kun-Cheng, SUN Bai-Qing, ZHANG Qiu-Hao, WANG Yi-Na, YANG Jun-You. Multi-robot multi-task coordination framework based on the integration of intelligent agent and Petri net. Acta Automatica Sinica, 2021, 47(8): 2029−2049. doi: 10.16383/j.aas.c190400 [10] Sun G, Zhou R, Di B, Dong Z, Wang Y. A Novel Cooperative path planning for multi-robot persistent coverage with obstacles and coverage period constraints. Sensors, 2019, 19(9), 1994: 1-28. doi: 10.1109/JSEN.2019.2897439 [11] Agatz N, Bouman P, Schmidt M. Optimization approaches for the traveling salesman problem with drone. Transportation Science, 2018, 52(4): 965-981. doi: 10.1287/trsc.2017.0791 [12] De Freitas J C, Penna P H. A variable neighborhood search for flying sidekick traveling salesman problem. International Transactions in Operational Research, 2019, 27(1): 267-290. [13] Murray C C, Chu A G. The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery. Transportation Research Part C-emerging Technologies, 2015, 54(54): 86-109. [14] Ha Q M, Deville Y, Pham Q D, Hoàng Hàc M. On the min-cost traveling salesman problem with drone. Transportation Research Part C-emerging Technologies, 2018, 86: 597-621. doi: 10.1016/j.trc.2017.11.015 [15] Ham A. Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming. Transportation Research, 2018, 91: 1-14. [16] Klauco M, Blazek S, Kvasnica M, Fikar M. Mixed-integer SOCP formulation of the path planning problem for heterogeneous multi-vehicle systems. In: Proceedings of the European Control Conference (ECC). Strasbourg, France: IEEE, 2014. 1474–1479 [17] 陈洋, 谭艳平, 程磊, 吴怀宇. 邻域约束下空地异构机器人系统路径规划方法. 机器人, 2017, 39(1): 1-7.Chen Yang, Tan Yan-Ping, Cheng Lei, Wu Huai-Yu. Path planning for a heterogeneous aerial-ground robot system with neighbourhood constraints. Robot, 2017, 39(1): 1-7. [18] Maini P, Sundar K, Singh M, Rathinam S, Sujit P B. Cooperative aerial–ground vehicle route planning with fuel constraints for coverage applications. IEEE Transactions on Aerospace and Electronic Systems, 2019, 55(6): 3016-3028. doi: 10.1109/TAES.2019.2917578 [19] Carlsson J G, Song S. Coordinated logistics with a truck and a drone. Management Science, 2018, 64(9): 4052-4069. doi: 10.1287/mnsc.2017.2824 [20] Mathew N, Smith S L, Waslander S L. Planning paths for package delivery in heterogeneous multirobot teams. IEEE Transactions on Automation Science and Engineering, 2015, 12(4): 1298-1308. doi: 10.1109/TASE.2015.2461213 -
计量
- 文章访问数: 1760
- HTML全文浏览量: 472
- PDF下载量: 388
- 被引次数: 0
