2.765

2022影响因子

(CJCR)

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

留言板

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

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

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

陈梦清 陈洋 陈志环 赵新刚

陈梦清, 陈洋, 陈志环, 赵新刚. 路网约束下异构机器人系统路径规划方法. 自动化学报, 2023, 49(4): 718−730 doi: 10.16383/j.aas.c200806
引用本文: 陈梦清, 陈洋, 陈志环, 赵新刚. 路网约束下异构机器人系统路径规划方法. 自动化学报, 2023, 49(4): 718−730 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, 2023, 49(4): 718−730 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, 2023, 49(4): 718−730 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 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 Researcher 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

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

    Fig.  5  Simulation of a simple road network

    图  6  简单路网的仿真结果

    Fig.  6  Simulation results on the simple road network

    图  7  复杂路网仿真

    Fig.  7  Simulation of a complex road network

    图  8  复杂路网仿真结果

    Fig.  8  Simulation results on the complex road network

    图  9  复杂路网交通中断时的仿真结果

    Fig.  9  Simulation results on the complex road network in case interruption

    图  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 each time

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

    Fig.  15  Path planning results of drone visiting multi-points each time

    表  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  简单路网仿真中无人机的约束违反量 (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.127100.1280.0009
    ${\tilde {\boldsymbol{q}}_2}({{\boldsymbol{q}}_4})$0.159900.1600.0001
    ${\tilde {\boldsymbol{q} }_3}({ {\boldsymbol{q} }_3})$0.161300.1600.0013
    ${\tilde {\boldsymbol{q}}_4}({{\boldsymbol{q}}_2})$0.139200.1400.0008
    ${\tilde {\boldsymbol{q}}_5}({{\boldsymbol{q}}_1})$0.053300.0520.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.085900.0860.0001
    ${\tilde {\boldsymbol{q}}_2}({{\boldsymbol{q}}_5})$0.076100.0760.0001
    ${\tilde {\boldsymbol{q}}_3}({{\boldsymbol{q}}_3})$0.048200.0480.0002
    ${\tilde {\boldsymbol{q}}_4}({{\boldsymbol{q}}_1})$0.233100.2240.0091
    ${\tilde {\boldsymbol{q}}_5}({{\boldsymbol{q}}_2})$0.066800.0660.0008
    ${\tilde {\boldsymbol{q}}_6}({{\boldsymbol{q}}_6})$0.107800.1080.0002
    ${\tilde {\boldsymbol{q}}_7}({{\boldsymbol{q}}_7})$0.164300.1640.0003
    ${\tilde {\boldsymbol{q}}_8}({{\boldsymbol{q}}_{10}})$0.104200.1040.0002
    ${\tilde {\boldsymbol{q}}_9}({{\boldsymbol{q}}_9})$0.086300.0860.0003
    ${\tilde {\boldsymbol{q}}_{10}}({{\boldsymbol{q}}_8})$0.108400.1080.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.133800.1340.0002
    ${\tilde {\boldsymbol{q}}_2}({\boldsymbol{q}}_4)$0.213700.2140.0003
    ${\tilde {\boldsymbol{q}}_3}({\boldsymbol{q}}_3)$0.189900.1900.0001
    ${\tilde {\boldsymbol{q}}_4}({\boldsymbol{q}}_1)$0.224400.2240.0004
    ${\tilde {\boldsymbol{q}}_5}({\boldsymbol{q}}_2)$0.076600.0760.0006
    ${\tilde {\boldsymbol{q}}_6}({\boldsymbol{q}}_6)$0.107000.1060.0010
    ${\tilde {\boldsymbol{q}}_7}({\boldsymbol{q}}_7)$0.162500.1620.0005
    ${\tilde {\boldsymbol{q}}_8}({\boldsymbol{q}}_{10})$0.091000.0920.0010
    ${\tilde {\boldsymbol{q}}_9}({\boldsymbol{q}}_{9})$0.098100.0980.0001
    ${\tilde {\boldsymbol{q}}_{10}}({\boldsymbol{q}}_{8})$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.82500.2453
    MACO-PSO331.26570.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.078400.0760.0024
    ${\tilde {\boldsymbol{q}}_2}({\boldsymbol{q}}_5)$0.067000.0660.0010
    ${\tilde {\boldsymbol{q}}_3}({\boldsymbol{q}}_{11})$0.094100.0900.0041
    ${\tilde {\boldsymbol{q}}_4}({\boldsymbol{q}}_{12})$0.05790.19210.0580.0001
    ${\tilde {\boldsymbol{q}}_5}({\boldsymbol{q}}_3)$0.054400.0540.0004
    ${\tilde {\boldsymbol{q}}_6}({\boldsymbol{q}}_1)$0.25120.00120.2460.0052
    ${\tilde {\boldsymbol{q}}_7}({\boldsymbol{q}}_2)$0.066900.0660.0009
    ${\tilde {\boldsymbol{q}}_8}({\boldsymbol{q}}_6)$0.115000.1140.0010
    ${\tilde {\boldsymbol{q}}_9}({\boldsymbol{q}}_7)$0.136800.1360.0008
    ${\tilde {\boldsymbol{q}}_{10}}({\boldsymbol{q}}_{10})$0.086300.0860.0003
    ${\tilde {\boldsymbol{q}}_{11}}({\boldsymbol{q}}_{13})$0.103300.0880.0153
    ${\tilde {\boldsymbol{q}}_{12}}({\boldsymbol{q}}_{14})$0.130300.1200.0103
    ${\tilde {\boldsymbol{q}}_{13}}({\boldsymbol{q}}_9)$0.079800.0780.0018
    ${\tilde {\boldsymbol{q}}_{14}}({\boldsymbol{q}}_8)$0.106800.1060.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.081100.08000.0011
    ${\tilde {\boldsymbol{q}}_2}({\boldsymbol{q}}_5,{\boldsymbol{q}}_{11})$0.111500.11200.0005
    ${\tilde {\boldsymbol{q}}_3}({\boldsymbol{q}}_{12},{\boldsymbol{q}}_{3})$0.062000.06300.0010
    ${\tilde {\boldsymbol{q}}_4}({\boldsymbol{q}}_1)$0.246000.24400.0020
    ${\tilde {\boldsymbol{q}}_5}({\boldsymbol{q}}_2)$0.068000.06800
    ${\tilde {\boldsymbol{q}}_6}({\boldsymbol{q}}_6)$0.109900.11000.0001
    ${\tilde {\boldsymbol{q}}_6}({\boldsymbol{q}}_7)$0.145800.14600.0002
    ${\tilde {\boldsymbol{q}}_8}({\boldsymbol{q}}_{10},{\boldsymbol{q}}_{13})$0.112200.11200.0002
    ${\tilde {\boldsymbol{q}}_9}({\boldsymbol{q}}_{14},{\boldsymbol{q}}_{9})$0.145800.14600.0002
    ${\tilde {\boldsymbol{q}}_{10}}({\boldsymbol{q}}_8)$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(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.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 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
  • 加载中
图(15) / 表(8)
计量
  • 文章访问数:  1577
  • HTML全文浏览量:  375
  • PDF下载量:  349
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-09-29
  • 录用日期:  2021-03-19
  • 网络出版日期:  2021-05-08
  • 刊出日期:  2023-04-20

目录

    /

    返回文章
    返回