引用本文

陈梦清, 陈洋, 陈志环, 赵新刚. 路网约束下异构机器人系统路径规划方法. 自动化学报, 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

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c200806

关键词

异构机器人系统，路径规划，路网约束，两步法 

摘要

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

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

文章导读

空中无人机 (Unmanned aerial vehicles, UAV) 和地面机器人在自己的工作领域内都可以发挥很好的作用, 但是都各有优缺点. 如, 微型无人机行动自由、视野开阔, 在搜索和检测目标方面具有不可替代的优势, 但是无人机单次续航时间通常有限. 地面机器人具有智能驾驶、载荷能力强、续航时间长的特点, 缺点是只能在道路网络中行驶, 视野严重受限. 因此, 若将空中无人机与地面移动机器人结合构成异构协作系统, 让地面车作为无人机的着陆平台及能量补给站, 可以取长补短、优势互补, 大大拓展机器人系统代替人类完成任务的能力[1-5]. 由无人机和地面机器人组成的异构系统在任务调度、目标跟踪、定位与抓捕、合作建图、持续监测以及物流配送等方面都有广泛的应用前景[6-10]. 本文对这一类异构机器人系统的路径规划问题展开研究.

目前对异构机器人系统的路径规划研究主要有两类, 一类是同时规划无人机和地面车的路线; 另一类是仅规划无人机的路线. 在第1类中, 不考虑地面车的运动范围, 即假设地面是完全空旷的, 允许地面车在二维平面上做任意运动, 同时规划地面车和无人机的路线. 第2类在第1类的研究基础上, 考虑实际环境中道路的限制, 但是事先为地面车选择一条路径, 然后仅规划无人机的路线, 通常约定无人机只允许在目标点或道路节点处起飞或降落.

对于第1类, 不考虑地面机器人运动范围的研究, 很多是关于带有无人机的旅行商问题(Travelling salesman problem, TSP)或者广义旅行商问题的研究[11-12]. Murray等[13]和Ha等[14]研究异构机器人系统的包裹投递, 允许无人机在客户处起飞或降落, 客户既可以被无人机访问, 也可以由地面车访问, 但是一次仅访问一个客户. 针对文献[13]研究的问题, Ham[15]允许地面车和无人机一次访问多个目标点. Klauco等[5]在允许无人机一次访问多个目标点的基础上, 优化了目标点的访问顺序. Agatz等[11]研究了地面车和无人机合作的TSP问题, 基于局部搜索和动态规划方法提出了一种启发式算法, 并将结果与小规模案例的最优解进行了比较. Freitas等[12]的研究中允许目标点由地面车或无人机访问, 提出了一种混合启发式方法, 得到了无人机和地面车共同访问目标点的路径. Klauco等[16]研究异构机器人系统的包裹投递问题, 并将研究的问题简化为混合整数规划问题. 陈洋等[17]给目标点加入邻域约束, 无人机只需要到达目标点的邻域, 进一步节省了完成任务的时间.

第2类研究结合了道路的实际情况, 地面车的运动受到路面障碍物或者建筑物的约束, 因而假定地面车选择了一条固定的路线, 在此情形下仅需规划无人机的路线. 现有研究只能限定无人机在特定位置起飞或降落. 例如: Ham[15]首先研究了地面车路径固定情形下的无人机路径规划问题. Maini等[18]研究了异构机器人系统在复杂环境中测绘的应用, 由于地面道路错综复杂, 需要为地面车事先选择一条道路, 允许无人机一次访问多个测绘点. Carlsson等[19]研究了异构机器人系统进行物流配送的路径规划问题. 在地面车路径已知的基础上, 提出一种启发式方法求得无人机的路线. Mathew等[20]将地面车的路径限制在一条道路上, 然后为无人机选择一些确定的地点, 在这些确定点处选择无人机的起飞点和降落点, 从而得到无人机的路线.

现实中的车辆必须在道路上行驶. 因此本文的研究给异构机器人系统加入地面路网的约束, 使研究更接近实际情况. 由于人为给定地面车的路径会破坏异构机器人整体的最优性能, 因此本文将两者的路径计算放入同一个优化模型中, 不仅规划无人机的路径, 而且同时规划地面车的路径. 由Carlsson等[19]的研究可知, 当允许无人机在道路上随时起降时可降低时间成本, 因此本文的研究允许无人机在地面车上根据需要随时起飞, 进一步减少飞行时间和所需能量. 并且, 为了进一步缩短无人机的总飞行距离以节省能量, 本文考虑允许无人机在其续航时间范围内连续访问多个目标点.

由于地面车和无人机的路线之间相互耦合, 且由于地面路网的复杂性, 地面车的路线难以使用传统方法建立约束表达式对耦合关系进行描述, 因此本文提出使用蚁群算法(Ant colony optimization, ACO)和遗传算法(Genetic algorithm, GA)相结合的“两步法”对地面移动机器人和无人机的路径进行求解, 两步之间通过信息素建立桥梁, 达到全局优化的目标, 研究思路如图1所示. 本文的贡献主要包括两个方面: 1) 建立了异构机器人在路网约束下的路径规划模型; 2) 提出一种两步法求解异构机器人系统的路径规划方法.

图 1  本文的研究思路

图 2  自动更换电池装置

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

本文所研究的系统由一架无人机和一辆无人地面车组成, 其中地面车负载能力强并可以携带足够多的能量或物资, 其能量在执行任务的过程中不会耗尽, 而无人机的续航能力有限, 它在执行任务的过程中需要返回地面车上充电或更换电池. 地面车在路网中行驶, 由无人机去访问位于路网附近的目标点. 所有目标访问完成后, 无人机降落在地面车上一起运动到给定的终点.

本文考虑实际环境中道路网络的限制, 仅允许地面车在道路网络中行驶, 为了缩短完成任务的时间, 不仅规划无人机的路径, 还同时为地面车规划路径. 本文提出采用蚁群算法和遗传算法相结合的两步法解决了上述问题, 分别在3种不同的环境中验证了所提方法的有效性. 为了进一步缩短任务时间, 还研究了允许无人机每次出勤时连续访问多个目标点的路径规划问题.

由于要满足无人机的续航时间约束以及无人机与地面车无需互相等待的约束, 目标点的数量不宜过多. 如果目标点数目过多, 可能会引起无人机起降坐标点过于拥挤, 从而使得无人机需要等待地面车. 未来的工作中将考虑加入多个无人机来解决该问题. 虽然本文的方法在异构机器人协作规划中表现出优势, 但还没有得到实物验证. 后续工作将重点关注本文方法在空地异构协作机器人中的物理实现以及在协作投递、巡逻和监测领域的应用.

作者简介

陈梦清

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