多移动机器人路径规划方法研究

2020-02-25

福建质量管理 2020年11期

(北京物资学院北京 101149)

引言

近年来随着电子商务和物联网技术的快速发展，使得物流业变得越来越智能化。与此同时，由于电商平台企业的物流业务呈现出多品类、高频次、小批量的特点，京东、亚马逊等电商企业将智能化的移动机器人投入到仓储作业的运营中，用来提升拣选效率，降低拣选成本。然而如何对多个移动机器人进行路径规划，实现作业的高效协同是目前亟待解决的问题[1]。

一、多移动机器人路径规划问题

路径规划问题[2]简言之就是让机器人遵照某种性能指标(例如距离，时间等)作出从初始环境到达目标环境的最优的路径。路径规划的结果评价标准体现在三个方面：机器人可执行路线是否存在；遇到冲突时，机器人是否能够完成无碰撞路径；机器人执行的路径是否为最优路径。

多移动机器人路径规划问题(Multi-Robot Path Finding，MRPF)是指，在同时存在静态和动态障碍物的工作空间中，为每台机器人都规划出一条从起点到目标点的最优路径，令所有机器人的完成任务时间最短。同时还要保证机器人与障碍物之间、机器人与机器人之间不发生碰撞。

二、多移动机器人路径规划方法研究

目前国内外相关学者对多移动机器人路径规划方法进行了许多相关的研究，主要可以分为三类：解耦的MRPF方法、耦合的MRPF方法、基于强化学习的MRPF方法。

(一)基于解耦的多移动机器人路径规划方法

基于解耦的多机器人路径规划方法主要步骤分为两个阶段：第一阶段，为每个机器人计算一条无碰撞路径，不考虑环境中其它机器人的运动，可以使用单机器人路径规划算法，如Dijistra算法、A*算法或智能优化算法等；第二阶段，利用交通规则解决移动机器人间的冲突问题。

基于解耦的多移动机器人路径规划方法的优点是：计算复杂性低、鲁棒性好。其缺陷在于当场景中机器人数量较大时，极易产生冲突和拥堵，造成复杂的路径再规划问题。

相关的研究有：Khorshid[3]等针对解耦算法无法保证最优解及完备解方面，提出了一种树搜索GTD(Graph-to-Tree Decompositon)算法以保证解的完备。沈博闻[4]在其研究中将物流机器人所承担的物流任务进行分解后，考虑其路径代价与时间代价的基础上修正A*算法，实现特殊环境特殊道路规则约束下的仓储机器人路径规划。

(二)基于耦合的多机器人路径规划方法

基于耦合的多机器人路径规划即在有限时间步内，每一个机器人搜索一条与其它机器人无冲突路径，且需要保证所有机器人路径代价之和最小。其多将路网抽象为图结构，能够实现移动机器人间的“紧密协调和最优协调”，规划的路径通常是最优(次优)及完备的解。

基于耦合的多移动机器人路径规划优点是：能够保障找到最优解(次优解)或完备解，且当存在较多的机器人时，其路径规划已经考虑多机器人之间的无冲突问题，避免了复杂的路径再次规划问题。缺点是当随着机器人数量的增加，机器人运动的状态空间复杂度呈指数级增长，其解的复杂程度较高，难以满足实时应用需要。

相关的研究有：Sharon[5]提出了一种基于CBS(Conflict-Based Search)算法,采用了两阶段搜索算法以降低算法复杂性，CBS算法类似多数耦合方法，能够保证最优解，与其它耦合算法进行比较，CBS算法针对狭窄空间应用效果较好。泰应鹏[6]提出一种基于时间窗模型的动态路径规划方法，以实现多AGV的动态路径规划。通过对时间窗的排布和更新解决了多AGV在路径规划中的碰撞冲突问题，并通过动态更改道路权重,重新对路径进行规划,实现了实时避障。

(三)基于强化学习的多移动机器人路径规划方法

强化学习中的Q-Learning算法因无需环境的先验知识，并且不依赖于模型直接利用与环境交互获得的数据改善自身的行为，该算法更具有通用性，逐渐成为路径规划领域的重要研究热点。强化学习的目标是要通过奖赏与惩罚来对当前的问题得到一个最好的解决策略，对好的策略进行奖赏，对坏的策略进行惩罚，不断的强化这个过程，最终得到一个最好的策略。

基于强化学习的多移动机器人路径规划优点是：不需要精确的环境模型，具有较好的鲁棒性；具有强大的自适应性与学习能力。缺点是该方法中的某些算法更适合用来解决中等规模的强化学习问题，例如Q-Learning算法。因此需要根据实际情况来选择合适的算法。

相关的研究有：郑延斌等[7]提出了一种基于分层强化学习及人工势场的多Agent路径规划算法，首先将多Agent的运行环境虚拟为一个人工势能场，根据先验知识确定每点的势能值，它代表最优策略可获得的最大回报，其次利用分层强化学习方法的无环境模型学习进行策略更新。王毅然等[8]以复杂任务下多个智能体路径规划问题为研究对象，提出一种基于强化学习的多Agent路径规划方法。该方法采用无模型的在线Q学习算法，多个Agent不断重复“探索-学习-利用”过程，积累历史经验评估动作策略并优化决策，完成未知环境下的多Agent的路径规划任务。

(四)展望

本文对多移动机器人路径规划方法进行了总结，列举了三种方法的国内外研究文献，分析了各自的优缺点，基于以上分析可以发现，基于强化学习的多移动机器人路径规划研究方法因具有较好的鲁棒性、强大的自适应性与学习能力，更可能被广泛的应用，与此同时，将深度学习和强化学习结合进行多机器人路径规划研究已成为新的发展趋势。