引言

MAPF是对不同起始位置的多个智能体到他们各自目标位置的路径规划问题，关键约束是在保证智能体之间互相不碰撞的前提下到达目标位置，并保证路径规划的速度和质量。MAPF在实际场景中有许多应用，如大型仓库管理［1-2］、数字游戏［3］、火车调度［4］、城市道路网络［5］、多机器人系统［6］等，更多实际应用可参考文献［7］。近年来，越来越多的团队对MAPF展开研究［8-11］，MAPF取得了突破性进展，尤其是基于强化学习(Reinforcement Learning, RL)方法应用到MAPF问题中取得了较好效果，国内对MAPF问题的研究也越来越浓厚。

求解MAPF的最优解已经被证明是NPHard问题［12］。传统方法将MAPF规约为其他已解决的问题如SAT［13］,或使用基于搜索的算法来解决，经典方法有增强的搜索［14］、基于冲突的搜索［15］以及改进的变体［16］等。然而，随着环境的动态变化和智能体数量的增加，搜索空间巨大对传统MAPF算法构成挑战。基于搜索的MAPF算法通过引入优先规划、大领域搜索和复杂的启发式函数来优化改进MAPF算法，前沿的算法有EECBS［17］、CCBS［18］、MOA*［19］、MAPFMLLNS［20］。这些算法能解决3 000多个智能体规模的MAPF问题，而且规划效率和质量较高，但这些集中式规划算法不能实时规划路径，可扩展性差。最近，分散式执行的强化学习方法应用于解决MAPF问题表现出较大的潜力，每个智能体根据局部观察分散执行策略。

RL智能体在大型环境中和环境互动时，只有达到目标才可以获取奖励，而到达目标的过程中奖励稀疏，学习效率不高，训练时间长，智能体还可能陷入死胡同。PRIMAL(Pathfinding via Reinforcement and Imitation MultiAgent Learning)［21］采取集中式MAPF规划器生成专家演示路径，训练过程中结合了模仿学习和强化学习，加速了学习过程，但计算比较耗时，求解质量还需提高。G2RL(Globally Guided RL)［22］给予每个智能体额外的奖励遵循单智能体最短路径，但这可能会误导智能体，因为到达目标位置的路径不是唯一的，这会影响智能体和其他智能体之间的协调合作。DHC(Distributed Heuristic multiagent path finding with Communication)［23］使用多条潜在路径作为智能体路径的启发式输入，并采用图卷积网络来加强智能体之间的通信，促进智能体之间的显式协调，但学习速度较慢。为了解决上述问题，本文提出了基于强化学习和模仿学习的启发式多智能体路径规划算法(Heuristic multi-agent path planning via Imitation and Reinforcement Learning, HIRL)，在智能体的观察中加入额外的目标向量，并嵌入从目标源到智能体的多条潜在最短路径作为神经网络的输入，使用模仿学习来促进智能体之间的隐式协调，引入目标牵引的奖励函数来鼓励智能体进行有效的探索，当智能体向目标方向移动时给予正奖励。智能体依据自己的局部观察来做出决策，不需要学习联合动作值，因此具有很好的可扩展性。本文采用的主要方法如下：

（1）采用模仿学习框架加速智能体学习，促进智能体之间的隐式协调，而不需要智能体之间的显式通信。

（2）采用智能体到目标位置的方向向量作为智能体观察的额外信息。

（3）引入目标牵引的奖励函数，鼓励智能体朝着目标方向进行有效的探索。

（4）嵌入了从目标源到智能体多条最短路径作为神经网络的输入，能更有效地避免智能体之间的冲突和死锁情况发生。

（5）使用部分可观察的环境，智能体根据有限视野的观察决策行动，更加符合现实世界的环境。

本文详细内容请下载：

https://www.chinaaet.com/resource/share/2000006161

作者信息：

郭传友，刘志飞，田景志，刘先忠

(中国人民解放军61150部队，陕西榆林719000)