Abstract: In order to obtain the high-quality collision free path of multi-robots, a multi-robot bilevel programming algorithm based on improved A* algorithm and conflict coordination strategy is proposed. Firstly, in the first layer of the algorithm, the heuristic function of the traditional A* algorithm is improved by introducing the dynamic weight factor combined with planned path information to avoid its blind search, so as to speed up the search speed. Through the screening mechanism and Bezier curve, the actual turning times of the robot are reduced and planned path is smoothed, and then the initial path of a single robot is obtained. Secondly, in the second layer of the algorithm, the time dimension is introduced based on the two-dimensional path to establish the robot path time map, so as to predict the conflict between robots. Finally, the conflict coordination strategy is used to coordinate the conflicts between robots and between robots and dynamic obstacles. The experimental results show that the bilevel programming algorithm can effectively reduce planned path search time and the number of turns, and obtain the smooth and collision free navigation path of each robot.

Key words: multi-robot, path planning, improved A* algorithm, conflict coordination strategy

摘要： 为了得到多机器人的高质量无碰撞路径，提出一种基于改进A*算法和冲突协调策略的多机器人双层规划算法。在算法的第一层，通过引入结合路径信息的动态权重因子改进传统A*算法的启发函数，避免其盲目搜索，从而加快搜索速度；通过筛选机制和Bezier曲线，减少机器人实际转弯次数并平滑路径，进而得到单机器人的初始路径。在算法的第二层，在二维路径基础上引入时间维度，建立机器人路径时间图，从而预测机器人之间的冲突。通过冲突协调策略对机器人与机器人之间、机器人与动态障碍物之间产生的冲突进行协调。实验结果表明，双层规划算法能够有效地减少路径搜索时间和转弯次数，得到各机器人平滑无碰撞的导航路径。

关键词: 多机器人, 路径规划, 改进A*算法, 冲突协调策略