2.624

2020影响因子

(CJCR)

  • 中文核心
  • EI
  • 中国科技核心
  • Scopus
  • CSCD
  • 英国科学文摘

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

路网约束下异构机器人系统路径规划方法

陈梦清 陈洋 陈志环 赵新刚

陈梦清, 陈洋, 陈志环, 赵新刚. 路网约束下异构机器人系统路径规划方法. 自动化学报, 2021, x(x): 1−13 doi: 10.16383/j.aas.c200806
引用本文: 陈梦清, 陈洋, 陈志环, 赵新刚. 路网约束下异构机器人系统路径规划方法. 自动化学报, 2021, x(x): 1−13 doi: 10.16383/j.aas.c200806
Chen Meng-Qing, Chen Yang, Chen Zhi-Huan, Zhao Xin-Gang. Path planning for heterogeneous robot system with road network constraints. Acta Automatica Sinica, 2021, x(x): 1−13 doi: 10.16383/j.aas.c200806
Citation: Chen Meng-Qing, Chen Yang, Chen Zhi-Huan, Zhao Xin-Gang. Path planning for heterogeneous robot system with road network constraints. Acta Automatica Sinica, 2021, x(x): 1−13 doi: 10.16383/j.aas.c200806

路网约束下异构机器人系统路径规划方法

doi: 10.16383/j.aas.c200806
基金项目: 国家自然科学基金(61573263, 62073250)资助
详细信息
    作者简介:

    陈梦清:2020年获得武汉科技大学硕士学位. 主要研究方向为移动机器人路径规划. E-mail: cm1803759221@163.com

    陈洋:武汉科技大学教授. 2012年获得中国科学院沈阳自动化研究所博士学位. 主要研究方向为移动机器人建模, 规划与控制. 本文通信作者. E-mail: chenyag@wust.edu.cn

    陈志环:武汉科技大学副教授. 2017年获得华中科技大学博士学位. 主要研究方向:为智能优化算法, 机器人控制等. E-mail: czh@wust.edu.cn

    赵新刚:中国科学院沈阳自动化研究所研究员. 2008 年获得中国科学院沈阳自动化研究所博士学位. 主要研究方向为智能机器人系统. E-mail: zhaoxingang@sia.cn

Path Planning for Heterogeneous Robot System With Road Network Constraints

Funds: Supported by National Natural Science Foundation of China (61573263, 62073250)
More Information
    Author Bio:

    CHEN Meng-Qing She received her master degree from Wuhan University of Science and Technology in 2020. Her main research interest is mobile robot path planning

    CHEN Yang Professor at Wuhan University of Science and Technology. He received his Ph.D. degree from Shenyang Institute of Automation, Chinese Academy of Sciences in 2012. His research interest covers mobile robot modeling, planning and control. Corresponding author of this paper

    CHEN Zhi-Huan Associate Professor at Wuhan University of Science and Technology. He received his Ph.D. degree from Huazhong University of Science and Technology in 2017. His research interest covers intelligent optimization algorithm and robot control

    ZHAO Xin-Gang Professor at Shenyang Institute of Automation, Chinese Academy of Sciences. He received his Ph.D. degree from Shenyang Institute of Automation, Chinese Academy of Sciences in 2008. His main research interest is intelligent robot systems

  • 摘要: 由无人机和地面移动机器人组成的异构机器人系统在协作执行任务时, 可以充分发挥两类机器人各自的优势. 无人机运动灵活, 但通常续航能力有限; 地面机器人载荷多, 适合作为无人机的着陆平台和移动补给站, 但运动受路网约束. 本文研究这类异构机器人协作路径规划问题. 为了降低完成任务的时间代价, 本文提出一种由蚁群算法和遗传算法相结合的两步法对地面机器人和无人机的路线进行解耦, 同时规划地面机器人和无人机的路线. 第一步使用蚁群算法为地面机器人搜索可行路线. 第二步对无人机的最优路径建模, 采用遗传算法求解并将无人机路径长度返回至第一步中, 用于更新路网的信息素参数, 从而实现异构协作系统路径的整体优化. 为了进一步降低无人机的飞行时间代价, 还研究了无人机在其续航能力内连续完成多任务的协作路径规划问题. 最后通过大量仿真实验验证了所提方法的有效性.
  • 图  1  本文的研究思路

    Fig.  1  Main idea of this study

    图  2  自动更换电池装置

    Fig.  2  Automatic battery replacement device

    图  3  路网约束下异构机器人系统示意图

    Fig.  3  Schematic diagram of heterogeneous robot system with road network constraints

    图  4  两步法的实现流程

    Fig.  4  Two-step strategy implementation process

    图  5  (a)简单路网, (b)简单路网的拓扑图

    Fig.  5  (a) Simple road network, (b) Simple road network topology

    图  6  (a) 地面车和无人机的路径规划结果, (b) 地面车路径收敛曲线, (c) 无人机飞行距离收敛曲线

    Fig.  6  (a) Path planning results of the ground vehicle and drone, (b) Convergence curve of the path of the ground vehicle, (c) Convergence curve of the UAV flight distance

    图  7  (a) 复杂路网, (b)复杂路网的拓扑

    Fig.  7  (a) Complex road network, (b) The topology of the complex road network

    图  8  (a) 地面车和无人机的路径规划结果, (b) 地面车路径收敛曲线, (c) 无人机飞行距离收敛曲线

    Fig.  8  (a) Path planning results of the ground vehicle and UAV, (b) Convergence curve of the ground vehicle path, (c) Convergence curve of the UAV flight distance

    图  9  (a) 地面车和无人机的路径规划结果, (b) 地面车路径收敛曲线, (c) 无人机飞行距离收敛曲线

    Fig.  9  (a) Path planning results of the ground vehicle and the UAV, (b) Convergence curve of the ground vehicle path, (c) Convergence curve of the UAV flight distance

    图  10  简单路网下的算法性能对比

    Fig.  10  Performance comparison with simple road network

    图  11  复杂路网下的算法性能对比

    Fig.  11  Performance comparison with complex road network

    图  12  一个染色体实例

    Fig.  12  A chromosome sample

    图  13  染色体的可行交叉变异位置

    Fig.  13  Feasible positions of cross and mutation within a chromosome

    图  14  无人机一次访问一个目标点的路径规划结果

    Fig.  14  Path planning results of drone visiting one point at once

    图  15  无人机一次访问多个目标点的路径规划结果 ((a)地面车与无人机的路径规划结果; (b) 地面车路径收敛曲线; (c) 无人机飞行距离收敛曲线)

    Fig.  15  Path planning results of drone visiting multi-points at once ((a) Path planning results of the ground vehicle and the UAV; (b) Convergence curve of the ground vehicle path; (c) Convergence curve of the UAV flight distance)

    表  1  code2的一个编码实例

    Table  1  A sample of code2

    code1 基因值2314
    code2 基因值156278104350461666692
    $\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  无人机的约束违反量(小时)

    Table  2  UAV constraint violations (h)

    目标点无人机
    用时ta
    约束(9)违反量
    max(taU, 0)
    地面车
    耗时tg
    时间差
    |tatg|
    ${\tilde {\boldsymbol{q}}_1}$(${{\boldsymbol{q}}_5}$)0.127100.12800.0009
    ${\tilde {\boldsymbol{q}}_2}$(${{\boldsymbol{q}}_4}$)0.159900.160.0001
    ${\tilde {\boldsymbol{q}}_3}$(${{\boldsymbol{q}}_3}$)0.161300.160.0013
    ${\tilde {\boldsymbol{q}}_4}$(${{\boldsymbol{q}}_2}$)0.139200.140.0008
    ${\tilde {\boldsymbol{q}}_5}$(${{\boldsymbol{q}}_1}$)0.053300.0520.0013
    下载: 导出CSV

    表  3  无人机的约束违反量(小时)

    Table  3  UAV constraint violations (h)

    目标点无人机
    用时ta
    约束(9)违反量
    max(taU, 0)
    地面车
    耗时tg
    时间差
    |tatg|
    ${\tilde {\boldsymbol{q}}_1}$(q4)0.085900.0860.0001
    ${\tilde {\boldsymbol{q}}_2}$(q5)0.076100.0760.0001
    ${\tilde {\boldsymbol{q}}_3}$(q3)0.048200.0480.0002
    ${\tilde {\boldsymbol{q}}_4}$(q1)0.233100.2240.0091
    ${\tilde {\boldsymbol{q}}_5}$(q2)0.066800.0660.0008
    ${\tilde {\boldsymbol{q}}_6}$(q6)0.107800.1080.0002
    ${\tilde {\boldsymbol{q}}_7}$(q7)0.164300.1640.0003
    ${\tilde {\boldsymbol{q}}_8}$(q10)0.104200.1040.0002
    ${\tilde {\boldsymbol{q}}_9}$(q9)0.086300.0860.0003
    ${\tilde {\boldsymbol{q}}_{10}}$(q8)0.108400.1080.0004
    下载: 导出CSV

    表  4  无人机的约束违反量(小时)

    Table  4  UAV constraint violations (h)

    目标点无人机
    用时ta
    约束(9)违反量
    max(taU, 0)
    地面车
    耗时tg
    时间差
    |tatg|
    ${\tilde {\boldsymbol{q}}_1}$(q5)0.133800.1340.0002
    ${\tilde {\boldsymbol{q}}_2}$(q4)0.213700.2140.0003
    ${\tilde {\boldsymbol{q}}_3}$(q3)0.189900.190.0001
    ${\tilde {\boldsymbol{q}}_4}$(q1)0.224400.2240.0004
    ${\tilde {\boldsymbol{q}}_5}$(q2)0.076600.0760.0006
    ${\tilde {\boldsymbol{q}}_6}$(q6)0.10700.1060.001
    ${\tilde {\boldsymbol{q}}_7}$(q7)0.162500.1620.0005
    ${\tilde {\boldsymbol{q}}_8}$(q10)0.09100.0920.001
    ${\tilde {\boldsymbol{q}}_9}$(q9)0.098100.0980.0001
    ${\tilde {\boldsymbol{q}}_{10}}$(q8)0.107400.1080.0006
    下载: 导出CSV

    表  5  简单路网中的比较结果

    Table  5  Comparison results in simple road network

    算法名称最优代价值平均运行时间 (s)
    MACO-GA56.84790.1832
    MACO-PSO87.69160.3628
    下载: 导出CSV

    表  6  复杂路网中的比较结果

    Table  6  Comparison results in complex road network

    算法名称最优代价值平均运行时间(s)
    MACO-GA116.8250.2453
    MACO-PSO331.26570.4873
    下载: 导出CSV

    表  7  无人机的约束违反量(单位: 小时)

    Table  7  UAV constraint violations (Unit: h)

    目标点无人机
    用时ta
    约束(9)违反量
    max(taU, 0)
    地面车
    耗时tg
    时间差
    |tatg|
    ${\tilde {\boldsymbol{q}}_1}$(q4)0.078400.0760.0024
    ${\tilde {\boldsymbol{q}}_2}$(q5)0.06700.0660.001
    ${\tilde {\boldsymbol{q}}_3}$(q11)0.094100.090.0041
    ${\tilde {\boldsymbol{q}}_4}$(q12)0.05790.19210.0580.0001
    ${\tilde {\boldsymbol{q}}_5}$(q3)0.054400.0540.0004
    ${\tilde {\boldsymbol{q}}_6}$(q1)0.25120.00120.2460.0052
    ${\tilde {\boldsymbol{q}}_7}$(q2)0.066900.0660.0009
    ${\tilde {\boldsymbol{q}}_8}$(q6)0.11500.1140.001
    ${\tilde {\boldsymbol{q}}_9}$(q7)0.136800.1360.0008
    ${\tilde {\boldsymbol{q}}_{10}}$(q10)0.086300.0860.0003
    ${\tilde {\boldsymbol{q}}_{11}}$(q13)0.103300.0880.0153
    ${\tilde {\boldsymbol{q}}_{12}}$(q14)0.130300.120.0103
    ${\tilde {\boldsymbol{q}}_{13}}$(q9)0.079800.0780.0018
    ${\tilde {\boldsymbol{q}}_{14}}$(q8)0.106800.1060.0008
    下载: 导出CSV

    表  8  无人机的约束违反量(小时)

    Table  8  UAV constraint violations ( h)

    目标点无人机
    用时ta
    约束(9)违反量
    max(taU, 0)
    地面车
    耗时tg
    时间差
    |tatg|
    ${\tilde {\boldsymbol{q}}_1}$(q4)0.081100.080.0011
    ${\tilde {\boldsymbol{q}}_2}$(q5, q11)0.111500.1120.0005
    ${\tilde {\boldsymbol{q}}_3}$(q12, q3)0.06200.0630.001
    ${\tilde {\boldsymbol{q}}_4}$(q1)0.24600.24400.0020
    ${\tilde {\boldsymbol{q}}_5}$(q2)0.06800.0680.0000
    ${\tilde {\boldsymbol{q}}_6}$(q6)0.109900.110.0001
    ${\tilde {\boldsymbol{q}}_6}$(q7)0.145800.1460.0002
    ${\tilde {\boldsymbol{q}}_8}$(q10, q13)0.112200.1120.0002
    ${\tilde {\boldsymbol{q}}_9}$(q14, q9)0.145800.1460.0002
    ${\tilde {\boldsymbol{q}}_{10}}$(q8)0.106700.10620.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.c200964

    Wu 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(14): 1615−1625.
    [7] Ding Y, 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 2020 IEEE International Conference on Systems, Man, and Cybernetics. USA: 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. Piscataway, 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.c190400

    LI 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 European Control Conference, 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
  • 加载中
计量
  • 文章访问数:  613
  • HTML全文浏览量:  81
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-09-29
  • 录用日期:  2021-03-19
  • 网络出版日期:  2021-05-08

目录

    /

    返回文章
    返回