一种基于改进冲突搜索的多机器人路径规划算法  

A multi-robot path finding algorithm based on improved conflict search

作　　者：张洪琳 吴耀华[1] 胡金昌 张健[1] ZHANG Hong-lin;WU Yao-hua;HU Jin-chang;ZHANG Jian(School of Control Science and Engineering,Shandong University,Jinan 250061,China;Business School,Shandong Normal University,Jinan 250013,China)

机构地区：[1]山东大学控制科学与工程学院,济南250061 [2]山东师范大学商学院,济南250013

出　　处：《控制与决策》2023年第5期1327-1335,共9页Control and Decision

基　　金：山东省自然科学基金项目(ZR2020MF085);山东省自然科学基金青年项目(ZR2022QF109);国家自然科学基金项目(62273204)。

摘　　要：针对智能仓储环境下多载位自主移动机器人集群拣选-配送路径规划问题,提出一种改进型基于冲突搜索的多智能体路径规划算法.在模型方面,采用多载位机器人替代KIVA机器人,建立以最小化拣选-配送时间以及无效路径比为目标的数学规划模型.在算法方面,首先,提出一种基于优先级规则的多智能体冲突消解加速策略;然后,设计基于动态规划的单机器人拣选序列优化算法;最后,设计考虑转向惩罚的增强A^(*)算法搜索机器人最优路径.实验结果表明:所提出模型与KIVA系统相比有较大优越性;所提出算法能够有效缩短拣选-配送时间、减少无效路径时间.An improved multi-agent path finding algorithm based on the conflict search algorithm is proposed for the path planning problem of picking-delivery with mobile robot clusters in the smart storage environment.In terms of the model,a mathematical planning model with the objective of minimizing the picking-delivery time and the invalid path ratio is established by using multi-carrier robots instead of KIVA robots.In terms of the algorithm,firstly a priority rule-based multi-intelligent conflict resolution acceleration strategy is proposed.Then a single-robot picking sequence optimization algorithm based on dynamic planning is designed.Finally,an enhanced A^(*)algorithm with the consideration of turning penalty is proposed to search for the optimal robot path.The experimental results show that the proposed model is superior to the KIVA system.The proposed algorithm can effectively shorten the picking-delivery time and reduce the invalid path time.

关 键 词：多智能体路径规划 基于冲突的搜索 多载位机器人 冲突消解 最小路径时间 路径规划 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]