1、【208】第45卷 第02期 2023-02收稿日期：2021-12-13作者简介：胡晓（1997-），女，重庆人，硕士研究生，研究方向为多机器人系统控制、调度和仿真。基于运动学-反向可恢复A*算法的移动机器人拣货系统路径规划研究Research on path planning of robotic mobile fulfillment system based on kinematic reverse resumable A*algorithm胡 晓1*，陈传军2，刘利波2，陈佳梁2，翁 迅3HU Xiao1*，CHEN Chuan-jun2，LIU Li-bo2，CHEN Jia-lia
2、ng2，WENG Xun3（1.北京邮电大学 人工智能学院，北京 100876;2.北自所（北京）科技发展股份有限公司，北京 100120;3.北京邮电大学 现代邮政学院（自动化学院），北京 100876）摘 要：在具有高度动态特性的移动机器人拣货系统中，路径规划算法的性能决定了机器人集群执行任务的实际效率。通过将系统中多个机器人的协同路径规划问题转化为多智能体路径规划问题MAPF，基于引入运动学特性的时间窗分层协作A*算法RRA*-WHCA*，提出了一种改进算法KRRA*-WHCA*。针对经典反向可恢复A*算法RRA*缺乏考虑机器人转弯时间等运动学特性的问题，引入辅助坐标系和标准计数对照表对
3、最小转弯时间进行精准求解，通过加入最小转弯时间优化了预估代价的评价方式，使算法可以快速找到最优路径，提高了整体WHCA*算法的寻路效果。仿真结果表明，KRRA*-WHCA*算法相比RRA*-WHCA*算法，在机器人平均行驶距离相似的情况下，有效降低了最大完工时间和平均任务完成时间，显著提高了整个系统的作业效率。关键词：移动机器人拣货系统；路径规划；多智能体；A*算法中图分类号：F252；O224 文献标志码：A 文章编号：1009-0134(2023)02-0208-060 引言移动机器人拣货系统（Robotic mobile fulfillment system，RMFS），具有高拣选效率、
4、高准确率、高容错率、可扩展性强和部署快速等特点，可以大幅提高拣选作业效率并降低人工成本，已经被广泛应用于仓储物流领域。随着仓库订单拣选作业量的爆发式增长，数量庞大的机器人被应用于RMFS，使其具有了高动态性、高随机性和大规模等作业特点1。大量机器人共享同样的工作环境虽然提高了系统的作业效率，但是在进行路径规划时也产生了资源竞争问题：机器人之间相互争夺路径资源会产生碰撞、冲突、堵塞和死锁等问题，严重影响生产效率和安全性。因此，多机器人的路径规划问题是移动机器人拣货系统大规模应用的瓶颈和技术难点。目前，专门针对移动机器人拣货系统的多机器人路径规划问题研究还较少。李昆鹏等2对任务分配、路径规划和冲突
5、协调问题进行了协同优化，设计了两阶段算法进行调度：第一阶段利用基于数学模型或基于货架优先级的算法进行任务分配，根据机器人行驶规则生成初始行驶路径；第二阶段根据初始路径，使用碰撞检测及避免方法协调机器人间的冲突，得到无冲突的调度方案。在遇到突发情况时进行实时重调度，仿真结果表明该方法可以成功调度100个机器人。孙阳君和赵宁3研究了基于动态调度的协同优化，使用禁忌搜索算法对模型进行求解得到预调度方案，并设计了遇到动态事件时的重调度方案。杨友良等4在任务分配的评价函数中引入了路径规划的拥堵系数来辅助决策。余娜娜等5首先使用基于优先级的派遣规则方法进行任务分配，然后设计了可以反映实时交通拥堵情况的栅格
6、阻塞度，将栅格阻塞度引入A*算法中进行路径规划，并使用预约表进行冲突协调。张丹露等6根据分层地图的优点提出了动态加权地图，每两个交叉路口之间的货架构成一个区域，利用预约时间表上机器人的位置信息来预测区域内的拥堵程度并得到每条边上的动态权重，使用改进的A*算法利用动态权重进行路径规划。王云峰等7设计了一种短期状态预测模型，按时间轴进行模拟来预测短期内各路段上机器人的通行量，并建立评价函数辅助路径规划算法优化已有路径方案。张中伟等8通过引入时间窗检测冲突类型并考虑多种因素设计动态优先级，提出了一种基于动态优先级策略的多机器人无冲突路径规划方法。该方法并基于动态优先级来消减冲突，提高了系统完成任务的
7、效率。张新艳和邹亚圣9通过在预估代价中引入转弯的惩罚函数，提出了一种引入时间因子的改进A*算法来减少转弯次数，并结合时间窗和优先级策略为多机器人规划无碰撞路径。综上所述，协同优化由于考虑了多种运行决策问题的影响，可以产生更好的调度效果，但是随着机器人数第45卷 第02期 2023-02【209】量的增加，计算复杂度也越来越高。部分研究通过评估交通状态、预测冲突和引入时间窗等方法来改进路径规划算法，但是在最底层的多机器人路径规划问题中，缺少考虑RMFS中特殊的机器人运动学特性对算法的影响。RMFS多机器人路径规划问题属于多智能体路径规划问题（Multi-Agent Path Finding Pr
8、oblem，MAPF）。MAPF是给定一组具有各自起始位置和目标位置的智能体，在没有冲突的条件下，为每个智能体规划一种由各自起点到终点的路由方式，使得所有智能体的最长路由时间（或者所有智能体的路由时间之和）最短。终身多智能体路径规划问题（Lifelong Multi-Agent Path Finding Problem，LMAPF）是MAPF的一个变体，即各智能体到达其目标位置后不断前往新的目标位置10。在RMFS的作业流程中，机器人完成当前搬运任务后并不会永远停留在原地，因为系统中不断有新订单到达，空闲机器人会被分配新的搬运任务，前往下一个搬运任务起点。因此，RMFS多机器人路径规划问题可以
9、应用LMAPF理论去解决。常用的MAPF算法包括CBS（Conflict-Based Search）11、ECBS（Enhanced Conflict-Based Search）12、CA*（Cooperative A*）13、PBS（Priority-Based Search）14和HCA*（Hierarchical Cooperative A*）13等。时间窗分层协作A*算法（Windowed Hierarchical Cooperative A*，WHCA*）是在HCA*算法的基础上引入时间窗思想的LMAPF求解器，它对于每一个待规划的机器人，采用空间时间A*（Space Time A*
10、，STA*）算法在已规划路径形成的预约表中进行三维路径搜索，得到各机器人的无冲突路径；在STA*的启发式函数中应用一个忽略时间维度和预约表的抽象层次结构，采用反向可恢复A*（Reverse Resumable A*，RRA*）算法在抽象层次结构中进行二维路径搜索，得到当前位置到目标位置的完美预估代价，从而在保证STA*搜索质量的同时提高了算法的搜索速度。针对RMFS系统中机器人加减速时间、转弯时间不可忽略的问题，Merschformann等15在现有WHCA*算法的STA*部分加入连续时间内的运动学约束，并对原有离散的预约表数据结构进行了修正；但在RRA*的预估代价中仅考虑了加减速时间的影响，
11、导致整体WHCA*算法求解质量不佳。因此，本文在RRA*的基础上提出了运动学-反向可恢复A*算法（Kinematic Reverse Resumable A*，KRRA*），通过精确计算机器人的最小转弯时间，优化预估代价的评价方式，提高RRA*算法的求解质量，进而优化整体WHCA*的寻路效果。1 WHCA*算法原理1.1 整体框架WHCA*（Windowed Hierarchical Cooperative A*）是在HCA*算法的基础上加上时间窗思想的LMAPF求解器，其算法流程如下：首先，每个机器人的优先级在算法开始时设置为0。算法搜索重复直到在规定时间内为每个机器人找到路径或迭代次数达到
12、给定的迭代极限。在每次迭代中，使用“固定保留”初始化预约表。“固定保留”是指对于每个已经移动（得到路径）的机器人，在其到达下一个计划停止节点之前需要保留的节点。然后，基于三个标准对机器人进行排序。第一个标准是机器人的优先级。第二个标准是机器人是否携带货架，携带货架的机器人是首选的，因为它们不能在其他货架下方移动，即它们具有较少的可行路径到达目标点。第三个标准是机器人相距目标点的距离，优先选择更接近目标节点的机器人。在此基础上，按照标准依次选择一个机器人进行路径规划，更新其封锁集合：将当前没有接到搬运任务的机器人的当前位置作为封锁节点存储在封锁集合中；对于携带货架的机器人，所有其他货架的存储节点
13、都在封锁集合中。使用STA*算法扩展路径，以满足连续时间内运动学约束的行驶时间作为起始节点到扩展节点的实际代价，以RRA*计算得到的“抽象距离”作为扩展节点到目标节点的预估代价。“抽象距离”的计算方法为：若扩展节点在RRA*的关闭列表中，则“抽象距离”等于RRA*中对应节点的实际代价；否则以扩展节点为新的目标节点重新调用RRA*算法，若此时RRA*寻路失败则“抽象距离”为无穷大，若寻路成功则“抽象距离”为RRA*中对应节点的实际代价。如果STA*找路径，则根据路径的“节点-时间窗”占用信息更新预约表；若找不到当前机器人的无冲突路径，则增加该机器人的优先级，选择下一个机器人继续重复以上过程。若所
14、有机器人都已找到路径或者算法达到迭代次数，算法停止。1.2 RRA*算法逻辑STA*算法在计算扩展节点的预估代价h时调用RRA*算法，使得预估代价更加贴近于最优路径下扩展节点到目标节点的真实代价，减少了STA*在搜索过程中对于一些非必要节点的扩展，加快了STA*的搜索速度。如算法1所示。第118行为循环主体，循环结束条件为Open队列为空。第19行表示RRA*寻路失败，返回false程序结束。进入循环后，第2行将Open队列的中f值最小的节点curNode出队。第3行将curNode加入Closed集合。第414行负责后继结点的扩展。第4行表示遍历curNode的所有后继结点中不在Closed
15、集合中的部分，记每次遍历的节点为successor，需要注意的是，这里的后继结点是在反向图中扩展得到的。第5行表示获取到达successor节点的真实代价successor.g，即在考虑运动学约束（加减速、转弯）的条件下，机器人从初始节点运动到successor节点的行驶时间。第6行表示获取successor节点到目标节点target的预估代价successor.h，即在考虑加减速的条件下，机器人在【210】第45卷 第02期 2023-02successor节点与target节点之间的直线上行驶的时间。第713行根据不同的情况对Open队列进行更新，具体来说，若successor不在Open
16、队列中，则将successor入队；若successor已经在Open队列中且新的f值比原有successor的f值小，则用新的f值更新Open队列successor的f值。第1517为算法终止判断条件，若当前节点curPoint为目标节点target，则返回true程序结束。算法1：RRA*1 while Open do2 curNode Open.Dequeue()3 Closed curNode4 for all successor GetReverseSuccessors(curNode)and successor Closed do5 successor.g CalculateG(successor)6 successor.h TimeToMove(EuclideanDistance(successor,target)7 f successor.g+successor.h8 if successor Open then9 Open.Enqueue(successor,f)10 end if11 if successor Open and f Open.GetCost(succ
