一种双阶段多智能体路径规划算法

A Two-stage Multi-agent Path Planning Algorithm

多智能体路径规划旨在解决多个智能体在同一工作空间内生成无碰撞路径的问题,是智能体无人化工作的关键支撑技术。基于回溯思想和自适应局部避障策略,提出了一种双阶段多智能体路径规划算法。在全局路径规划阶段,基于回溯思想改进的RRT*(rapidly-exploring random trees star)算法(back tracking rapidly-exploring random trees star,BT-RRT*),减少无效父节点,并确保各智能体生成优化的无碰撞路径。在协作避障阶段,智能体依据自身的任务优先级制定局部避障策略,避开动态障碍物和其他智能体。实验结果表明,该算法可成功寻找较优路径,还可降低避障时间。

Multi-agent path planning aims at solving the problem of multi-agent generating collision free paths in the same workspace.It is a key supporting technology for agents to work without humanization.Based on the idea of backtracking and adaptive local obstacle avoidance strategy,a two-stage multi-agent path planning algorithm was proposed.In the global path planning stage,the improved RRT*(rapidly-exploring random trees star)algorithm(back tracking rapidly-exploring random trees star,BT-RRT*)based on the idea of backtracking reduces invalid parent nodes and ensures that each agent generates an optimized collision free path.In the cooperative obstacle avoidance stage,the agent formulates local obstacle avoidance strategy according to its own task priority,avoiding dynamic obstacles and other agents.Experimental results show that the algorithm can find the optimal path successfully and reduce the obstacle avoidance time.