室内仓储物流机器人路径规划研究

摘 要：在室内仓储运营过程中，物流机器人取代人力配送成为物流行业的主流发展趋势。在仓储物流机器人系统中，一方面，要求通信、传感器等硬件模块具备良好性能；另一方面，路径规划也十分关键，决定了物流机器人的配送效率。因此，研究室内仓储物流机器人的路径规划具有重要意义。文章分析了传统A*算法的原理及存在的局限性，针对其局限性，采用了单行道方式和转弯惩罚项，基于改进A*算法提出一种室内仓储物流机器人路径规划方法，并提出在固定环境中投入合适机器人数量的策略，以期通过科学、合理的机器人路径规划提高物流仓库的工作效率和机器人系统的运行效率。

关键词：室内仓储；物流机器人；路径规划；A*算法

中图分类号：F272.3 文献标志码：A DOI：10.13714/j.cnki.1002-3100.2024.20.038

Abstract： In the indoor warehousing operation， logistics robots replaces the human distribution and becomes the mainstream development trend of logistics industry. In warehousing logistics robot system， on the one hand， it is required that communication， sensors and other hardware modules have good performance. On the other hand， the path planning is also crucial， which determines the distribution efficiency of logistics robots. Therefore， the study of the path planning of indoor warehousing logistics robots is of great significance. This article analyzes the principle and limitations of traditional A* algorithm. In response to these limitations， a one-way approach and a penalty for turning are adopted. Based on the improved A* algorithm， this article puts forward a path planning method of indoor warehousing logistics robots and a strategy for investing an appropriate number of robots in a fixed environment. It aims to improve the working efficiency of logistics warehouse and the operation efficiency of the robot system through the scientific and reasonable robot path planning .

Key words： indoor warehousing; logistics robot; path planning; A* algorithm

1 传统A*算法

常见的全局路径规划经典算法包括Dijkstra算法、A*算法、RRT算法等。其中，A*算法采用启发函数在二维栅格地图上搜索出一种更优路径。在搜索过程中，A*算法会不断计算搜索节点的总代价，按照总代价优先级选择代价最小的节点，直至搜索到目标节点结束。A*算法通过代价函数f（n）对搜索方向进行启发性控制，在确定待拓展结点和范围后，再以其中最小代价函数值的结点为当前结点，且与当前结点互相连接的其他结点的代价函数也会随之更新，直至搜索至目标结点[1]。A*算法的具体执行流程如下：第一步，进行二维栅格建模，设定起始点与终点标号，创建开放列表及关闭列表；第二步，将起点作为父节点加入关闭列表，关闭列表中还包括起点周围八个方向的非障碍物节点，再计算列表中每个节点的实际距离、启发函数、总代价等；第三步，计算出开放列表中总代价最小的节点，并将其作为父节点，将原父节点移入关闭列表；第四步，将新的父节点周围八个方向的非障碍物节点加入开放列表，并重新计算实际距离；第五步，判断当前父节点是否为终点，如判断结果为“是”，则算法结束，对目标节点的父节点进行逆序输出，得出A*算法规划的路径；如判断结果为“否”，则重复执行第三步[2]。A*算法可以通过计算节点的总代价得到一条最短路径，但是二维栅格地图尺寸越大，需要重复搜索的无用节点就越多，会降低算法的搜索效率。因此，基于A*算法的全局路径规划仅是物流机器人在环境地图中规划出的参考路径，与机器人在实际环境中行进的最终路径存在较大差异，尤其是生成环境需要大范围地图，栅格基数过于庞大，不仅会影响全局路径规划的效率，而且室内仓储物流环境始终处于动态状态，系统需要频繁搜索障碍物以规划局部路径。因此，需要对传统A*算法进行改进，以简化搜索流程、提高路径规划效率、提高物流机器人的运行效率。

2 基于改进A*的寻路算法设计

虽然A*算法简单、方便，但是上文中也提到，其仅适用于结点个数多、求解最短路径的场景中，在室内仓储物流这类特殊应用场景中需要引入转角及单行道约束，并减少系统拥塞及机器人碰撞的机率。具体设计思路如下。

2.1 减少机器人碰撞策略

仓储机器人的工作环境为室内物流仓库，通常需要多个机器人同时运行，以提高仓储物流工作效率，但传统A*算法仅考虑单纯的路径长度，无法满足实际工作需要。机器人的能耗与其工作状态有直接相关性，运行过程中强调时间最短、能耗最低、最实用。因此，需要进行合理的任务分配以减少机器人能耗。如果用Tr表示机器人运行时间长度，则可通过下式计算得出[3]。

Tr=Tl+Tt+Tw

式中，Tl为机器人直线行驶时间，速度恒定条件下该值与路径长度呈正相关；Tt为机器人转向时消耗时间，角度恒定条件下该值与转向角度呈正相关；Tw为机器人等待时间，任务分配、卸货取货时间、环境拥塞程度等指标会影响该值。

如果物流仓库采用单个机器人，无需考虑任务分配时间，外部工作人员的工作效率决定了机器人的取货卸货时间。因此，只需考虑环境拥塞的等待时间。但在实际的仓储环境中往往需要多个机器人，以提高仓储物流工作效率，就会产生相向碰撞、侧向碰撞、同向碰撞等问题。其中，相向碰撞是两个机器人占用同一条路径相向而行导致的；侧向碰撞则是多个机器人同时占用转角位置，或者机器人分别行驶于各自当前路径，但有一定机率发生侧向碰撞；同向碰撞通常是由于机器人行进速度相同，但外因导致其中一个机器人短暂停留而发生碰撞。碰撞是导致室内机器人系统拥塞的主要因素。为解决这一问题，建议采用单行道方式，如图1所示。

该单行道约束的方式用有向图取代无向图。A*算法在搜索过程中会按照特定的方向拓展，能够提高机器人运行的有序性，虽然在某种程度上增加了路径长度，但是却可以减少碰撞[4]。

2.2 减少机器人转向策略

上文中提到，机器人转向时间会影响机器人转向时的消耗时间。因此，路径规划还需要减少机器人的转向次数，以减少转向角度，避免机器人频繁转向而降低运行效率。针对该问题，可以在A*算法中引入转弯惩罚项。在计算当前搜索节点的转弯惩罚项时，要获得两点之间的最短路径，并达到路径能够保证相对平滑且减少转弯的目的。通过得到起点s与终点e形成的向量se→→→，以及前节点n、终点e形成的向量ne→→→，两个向量围成的平行四边形的面积便表示转弯惩罚项，即计算上述两个向量的叉积即可得到路径最短，同时避免路径有较多转角的问题[5]。引入转弯惩罚项后，综合考虑了路径的长度和角度，以减少转向角度，提高机器人的工作效率。

3 基于改进A*算法的室内仓储物流机器人路径规划策略

实际物流仓库中投入的机器人数量越多、环境越狭窄，机器人发生碰撞的机率就越大。机器人自身带有传感器，可以使其在遇到障碍时停止行进，以避免碰撞，但在实际的路径规划设计时，需要考虑如何在固定的环境中投放合适的机器人数量，既要保证物流仓库的工作效率，又要提高机器人系统的运行效率。

3.1 机器人拥塞概率计算

在实际运行过程中，机器人在某个位置的停留时间、在对应区域范围内的机器人数量决定了机器人发生碰撞的机率，即机器人停留的时间越长，区域范围内的机器人数量越多，机器人碰撞的概率越高，发生拥塞的机率也越大。可根据下式对仓储环境发生拥塞的概率进行计算[6]。

Pt=1-e-kt*tstay

Pr=1-e-kr*Nr

Ppre=Pt*Pr

GPi，j=GPi，j，last+Ppir，je

式中，tstay为机器人在某位置停留时间；

Nr为该区域一定范围内的机器人数量；

Pt为由时间导致的预测拥塞概率；

Pr为机器人数量导致的预测拥塞概率，通过乘积表征最终概率；

d为机器人位于某栅格的距离；

θ为机器人转向角度；

v为机器人速度；

w为机器人角速度；

kt、kr为参数。

将每次栅格点（i，j）处预测的拥塞概率累加到原始拥塞概率地图GPlast中的（i，j）点处，即可获得拥塞概率地图GP。

3.2 多机器人任务调度策略

在实际工作场景中，多个机器人在物流仓库自主移动，携带货架至固定终点，在该工作场景中有N个机器人，并对机器人进行编号，即Ri（i=1，2，3，……，N）。这些机器人需要完成M个任务，每个任务也有特定编号，即Ti（i=1，2，3，……，M），在特定时间tj（j=0，1，2，……）处，如何为任务Ti找到合适的机器人Ri执行对应任务是获得更高的工作效率、解决任务调度问题的关键[7]。良好的任务调度可实现资源的高效分配，室内仓储工作环境中，多机器人调度包括集中式调度与分布式调度两种。其中，分布式调度更符合人类思维，但是要求机器人能够自主决策，每个机器人都熟知工作环境、拥有环境地图，准确判断每个机器人的位置。以目前的技术而言，其在物理实现上还存在难度。集中式调度通过核心调度机构进行调度，即在核心调度机构中输入环境地图，由核心机构进行统一调度，机器人仅执行即可，大大降低了对机器人的要求。物流仓库机器人通过任务编号执行任务。在此情况下，机器人的调度需要考虑两个问题：一是任务生成后调度合适的机器人，减少机器人无效移动;二是考虑机器人到达卸货点后如何选择空位置放置货架。针对该类问题，可以引进贪心策略，即在调度合适的机器人方面，调度对象为到达任务点时间最短且可用于调度的机器人。路径长度、环境拥塞程度决定了机器人的运行时间，具体选择策略符合下式[8]。

式中，T xpath为从当前任务点机器人x按路径path运动可能花费的时间；Rx为对于当前任务代价最小的机器人。

针对机器人到达卸货点后如何选择空位置放置货架的问题，在对应任务编号生成后卸货点的位置就已经固定，即机器人在完成任务过程中搬离货架与搬入货架总路径长度相同，任务量M不变，所有机器人行走的路径和不变，在路径规划时只需避开拥塞程度高的区域即可，优先选择拥塞程度低的区域放置货架。具体选择策略符合下式[9]：

式中，为机器人按路径path行进到处货架的开销；Pi，j为货架最终停放位置。

4 结 语

综上所述，在室内仓储物流机器人运行系统中，任务调度、路径规划均是重要内容，会对机器人的工作效率产生决定性影响。高效的任务调度及科学的路径规划是保证机器人系统稳定性、智能性的核心要素。本文提出一种基于改进A*算法的机器人路径规划方案，以减少机器人的碰撞和转向，并结合室内仓储物流工作场景计算机器人拥塞概率，提出多机器人任务调度策略TECel3IeRed7fBxmR90dlpgnsqfyyvsaoFUd/uWIW7Q=，以解决传统A*算法存在的问题，优化机器人路径规划方案，提高机器人的工作效率。

参考文献：

[1] 邓星，张竞丹，邵海见，等．基于改进人工蜂群进化算法的移动机器人路径规划与仿真分析[J]．江苏科技大学学报（自然科学版），2020，34（2）：66-71.

[2] 石志刚，梅松，邵毅帆，等．基于人工势场法的移动机器人路径规划研究现状与展望[J]．中国农机化学报，2021，42（12）：182-188.

[3] 王成，任佳，张育．基于改进蚁群算法的无人船路径规划研究[J]．海南大学学报（自然科学版），2021，39（3）：242-250.

[4] 张松灿，普杰信，司彦娜，等．蚁群算法在移动机器人路径规划中的应用综述[J]．计算机工程与应用，2020，56（8）：10-19.

[5] 周超，谷玉海，任斌．基于一种改进A～*算法的移动机器人路径规划研究[J]．重庆理工大学学报（自然科学），2021，35（5）：127-134.

[6] 槐创锋，郭龙，贾雪艳，等．改进A*算法与动态窗口法的机器人动态路径规划[J]．计算机工程与应用，2021，57（8）：244-248.

[7] 张松灿，普杰信，司彦娜，等．蚁群算法在移动机器人路径规划中的应用综述[J]．计算机工程与应用，2020，56（8）：10-19.

[8] 谢春丽，高胜寒，孙学志．融合改进A～*算法和贝塞尔曲线优化的路径规划算法[J]．重庆理工大学学报（自然科学），2022，36（7）：177-187.

[9] 龚鹏，李文博，马庆升，等．基于改进A～*算法的无人车路径规划研究[J]．组合机床与自动化加工技术，2023（3）：17-20，24.