This paper proposes a suboptimal space–time conflict-based search algorithm (CBS) based on improved jump point search (JSCBS) to address the problem of fast path generation in multi-agent pathfinding (MAPF). Recognizing the limitation of the original CBS method in effectively utilizing lower layer information during upper layer search, this algorithm incorporates the concept of information sharing between upper layer and low layer. Accordingly, the hierarchical conflict avoidance framework of recursive constraint expansion is proposed to improve the efficiency of the search process. The framework introduces extended space–time conflict information of the lower layer into the upper layer algorithm, and guides the upper constraint tree to avoid expanding in the direction of conflict. In order to increase the quality of the path and the efficiency of the search, the jump point search algorithm (JPS) replaces the A* algorithm in the lower layer algorithm. The simulation results show that the search efficiency of JSCBS algorithm is better than that of CBS algorithm and ECBS algorithm under different scene settings, and this advantage is more obvious with the increase of search space.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Research on CBS-Based Multi-AGV Logistics Path Planning in Aviation Manufacturing Workshops

  • Weichen Guan,
  • Qi Sun,
  • Yangjun Pi,
  • Zhiqiang Li

摘要

This paper proposes a suboptimal space–time conflict-based search algorithm (CBS) based on improved jump point search (JSCBS) to address the problem of fast path generation in multi-agent pathfinding (MAPF). Recognizing the limitation of the original CBS method in effectively utilizing lower layer information during upper layer search, this algorithm incorporates the concept of information sharing between upper layer and low layer. Accordingly, the hierarchical conflict avoidance framework of recursive constraint expansion is proposed to improve the efficiency of the search process. The framework introduces extended space–time conflict information of the lower layer into the upper layer algorithm, and guides the upper constraint tree to avoid expanding in the direction of conflict. In order to increase the quality of the path and the efficiency of the search, the jump point search algorithm (JPS) replaces the A* algorithm in the lower layer algorithm. The simulation results show that the search efficiency of JSCBS algorithm is better than that of CBS algorithm and ECBS algorithm under different scene settings, and this advantage is more obvious with the increase of search space.