关键词: 轻载环境, 多机器人路径规划, 惩罚因子, 基于冲突搜索算法, 约束树

Abstract:

In light load environments, complex obstacle areas will exacerbate local conflicts between agents, leading to a decrease in path solving efficiency. This paper proposes a multi-agent path planning (MAPF) method with obstacle penalty factors in light load environments. First, in the low-level single machine planning process based on the conflict-based search (CBS) algorithm framework, by judging the distribution type of surrounding obstacles that are about to expand the agent's position, corresponding obstacle penalty factors are assigned to them; then, the penalty factors in the path planning process are accumulated and used as the heuristic value of single machine planning to select the path; finally, combined with the upper-level conflict resolution strategy of the CBS algorithm framework, MAPF and conflict coordination are performed. The results show that in a light load environment with a 10% obstacle distribution, the proposed algorithm has a solving time of about 81.38%~83.67% of that of the CBS algorithm, and the expansion amount of the constraint tree (CT) is 60.14%~71.66% of that of the CBS algorithm. Simulation in Gazebo has shown that this method can reduce the number of passes through complex obstacle areas.

Key words: light load environment, multi-agent path finding (MAPF), penalty factor, conflict-based search (CBS), constraint tree (CT)