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

A Two-stage Multi-agent Path Planning Algorithm

作　　者：李庆华[1,2] 王佳慧 李海明 冯超 LI Qing-hua;WANG Jia-hui;LI Hai-ming;FENG Chao(School of Electronics and Information Engineering (Department of Physics), Qilu University of Technology (Shandong Academy of Sciences), Jinan 250353, China;Jinan Engineering Laboratory of Human-machine Intelligent Cooperation, Jinan 250353, China;School of Electrical Engineering and Automation, Qilu University of Technology (Shandong Academy of Sciences), Jinan 250353, China)

机构地区：[1]齐鲁工业大学(山东省科学院)电子信息学院(大学物理教学部),济南250353 [2]济南市人机智能协同工程实验室,济南250353 [3]齐鲁工业大学(山东省科学院)电气工程与自动化学院,济南250353

出　　处：《科学技术与工程》2021年第22期9425-9431,共7页Science Technology and Engineering

基　　金：国家自然科学基金(61701270);齐鲁工业大学(山东省科学院)青年博士合作基金(2017BSHZ008)。

摘　　要：多智能体路径规划旨在解决多个智能体在同一工作空间内生成无碰撞路径的问题,是智能体无人化工作的关键支撑技术。基于回溯思想和自适应局部避障策略,提出了一种双阶段多智能体路径规划算法。在全局路径规划阶段,基于回溯思想改进的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.

关 键 词：多智能体 路径规划 BT-RRT*(back tracking rapidly-exploring random trees star)算法 优先级 局部避障 

分 类 号：TN966[电子电信—信号与信息处理]