Multi-agent Path Planning with Obstacle Penalty Factor

doi:10.16182/j.issn1004731x.joss.23-0397

Abstract

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)

CLC Number:

TP242

Yan Xingyu, Li Dayan, Wang Niya, Zhang Kaixiang, Mao Jianlin. Multi-agent Path Planning with Obstacle Penalty Factor[J]. Journal of System Simulation, 2024, 36(3): 673-685.

Figures/Tables 20

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Table 1

Fig. 7

Fig. 8

Table 2

Table 3

Fig. 9

Fig. 10

Fig. 11

Table 4

Table 5

Fig. 12

Fig. 13

Fig. 14

Fig. 15

References 18

1	乔乔, 王艳, 纪志成. 基于冲突搜索算法的多机器人路径规划[J]. 系统仿真学报, 2022, 34(12): 2659-2669.
	Qiao Qiao, Wang Yan, Ji Zhicheng. Multi-robot Path Planning Based on CBS Algorithm[J]. Journal of System Simulation, 2022, 34(12): 2659-2669.
2	Stern Roni, Sturtevant Nathan, Felner Ariel, et al. Multi-agent Pathfinding: Definitions, Variants, and Benchmarks[C]//Twelfth Annual Symposium on Combinatorial Search. Palo Alto, CA, USA: AAAI Press, 2019: 151-158.
3	Zheng Yi, Ravi S, Kline E, et al. Conflict-based Search for the Virtual Network Embedding Problem[C]//Proceedings of the Thirty-second International Conference on Automated Planning and Scheduling. Palo Alto, CA, USA: AAAI Press, 2022: 423-433.
4	张凯翔, 毛剑琳, 向凤红, 等. 基于讨价还价博弈机制的B-IHCA*多机器人路径规划算法[J]. 自动化学报, 2023, 49(7): 1483-1497.
	Zhang Kaixiang, Mao Jianlin, Xiang Fenghong, et al. B-IHCA*, a Bargaining Game Based Multi-agent Path Finding Algorithm[J]. Acta Automatica Sinica, 2023, 49(7): 1483-1497.
5	Huang Taoan, Dilkina B, Koenig S. Learning Node-Selection Strategies in Bounded-suboptimal Conflict-based Search for Multi-agent Path Finding[C]//Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems. Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems, 2021: 611-619.
6	Li Jiaoyang, Chen Zhe, Harabor D, et al. MAPF-LNS2: Fast Repairing for Multi-agent Path Finding via Large Neighborhood Search[C]//Proceedings of the 36th AAAI Conference on Artificial Intelligence. Palo Alto, CA, USA: AAAI Press, 2022: 10256-10265.
7	Standley T, Korf R. Complete Algorithms for Cooperative Pathfinding Problems[C]//Proceedings of the Twenty-second International Joint Conference on Artificial Intelligence. Palo Alto, CA, USA: AAAI Press, 2011: 668-673.
8	Ma Hang, Harabor D, Stuckey P J, et al. Searching with Consistent Prioritization for Multi-agent Path Finding[C]//Proceedings of the Thirty-third AAAI Conference on Artificial Intelligence and Thirty-first Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence. Palo Alto, CA, USA: AAAI Press, 2019: 7643-7650.
9	Phillips M, Likhachev M. SIPP: Safe Interval Path Planning for Dynamic Environments[C]//2011 IEEE International Conference on Robotics and Automation. Piscataway, NJ, USA: IEEE, 2011: 5628-5635.
10	Surynek Pavel. Multi-goal Multi-agent Path Finding via Decoupled and Integrated Goal Vertex Ordering[C]//Proceedings of the AAAI Conference on Artificial Intelligence. Palo Alto, CA, USA: AAAI Press, 2021: 12409-12417.
11	Sharon Guni, Stern Roni, Felner Ariel, et al. Conflict-based Search for Optimal Multi-agent Pathfinding[J]. Artificial Intelligence, 2015, 219: 40-66.
12	宣志玮, 毛剑琳, 张凯翔. CBS框架下面向复杂地图的低拓展度A^*算法[J]. 电子学报, 2022, 50(8): 1943-1950.
	Xuan Zhiwei, Mao Jianlin, Zhang Kaixiang. Low-expansion A^* Algorithm Based on CBS Framework for Complex Map[J]. Acta Electronica Sinica, 2022, 50(8): 1943-1950.
13	Li Jiaoyang, Ruml W, Koenig S. EECBS: A Bounded-suboptimal Search for Multi-agent Path Finding[C]//Proceedings of the AAAI Conference on Artificial Intelligence. Palo Alto, CA, USA: AAAI Press, 2021: 12353-12362.
14	Li Jiaoyang, Harabor D, Stuckey P J, et al. Disjoint Splitting for Multi-agent Path Finding with Conflict-based Search[C]//Proceedings of the Twenty-ninth International Conference on Automated Planning and Scheduling. Palo Alto, CA, USA: AAAI Press, 2019: 279-283.
15	Kottinger J, Almagor Shaull, Lahijanian M. Conflict-based Search for Explainable Multi-agent Path Finding[C]//Proceedings of the Thirty-second International Conference on Automated Planning and Scheduling. Palo Alto, CA, USA: AAAI Press, 2022: 692-700.
16	Li Jiaoyang, Harabor D, Stuckey P J, et al. Symmetry-breaking Constraints for Grid-based Multi-agent Path Finding[C]//Proceedings of the Thirty-third AAAI Conference on Artificial Intelligence and Thirty-first Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence. Palo Alto, CA, USA: AAAI Press, 2019: 747.
17	Greshler Nir, Gordon Ofir, Salzman Oren, et al. Cooperative Multi-agent Path Finding: Beyond Path Planning and Collision Avoidance[C]//2021 International Symposium on Multi-robot and Multi-agent Systems (MRS). Piscataway, NJ, USA: IEEE, 2021: 20-28.
18	Sturtevant N R. Benchmarks for Grid-based Pathfinding[J]. IEEE Transactions on Computational Intelligence and AI in Games, 2012, 4(2): 144-148.

算法	时间/s	二叉树CT	A*拓展节点
CBS	0.250	4	17 712
CBS-OBSC	0.217	2	12 336

机器人数量	算法类型
机器人数量	CBS	CBS-DS	CBS-SIPP	CBS-OBSC	CBS-DS-OBSC
20	1 005.583	1 005.583	1 005.583	1 005.583	1 005.583
25	1 245.833	1 245.833	1 245.833	1 245.750	1 245.750
30	1 514.083	1 514.083	1 513.583	1 514.000	1 514.000
35	1 768.750	1 768.750	1 768.250	1 768.667	1 768.667
40	1 983.417	1 983.417	1 982.917	1 983.833	1 983.833
45	2 220.833	2 220.833	2 220.833	2 220.750	2 220.750
50	2 465.250	2 465.250	2 465.250	2 465.167	2 465.167
55	—	2 735.417	2 735.417	2 735.333	2 735.333

机器人数量	算法类型
机器人数量	CBS	CBS-DS	CBS-SIPP	CBS-OBSC	CBS-DS-OBSC
20	0.750	0.750	0.833	0.750	0.750
25	1.583	1.583	1.667	2.000	2.000
30	2.417	2.417	2.750	3.000	3.000
35	3.333	3.333	3.667	4.250	4.167
40	8.033	6.750	6.750	9.000	9.083
45	10.083	9.000	8.083	7.917	8.000
50	45.167	26.583	19.500	16.000	12.833
55	—	219.167	386.167	111.083	35.500

机器人数量	算法类型
机器人数量	CBS	CBS-DS	CBS-SIPP	CBS-OBSC	CBS-DS-OBSC
15	651.091	651.091	651.091	650.909	650.909
20	890.000	890.000	890.000	889.818	889.818
25	1 109.091	1 109.091	1 109.091	1 108.909	1 108.909
30	1 305.273	1 305.273	1 304.455	1 305.000	1 305.000
35	1 509.182	1 509.182	1 508.455	1 508.909	1 508.909
40	1 737.909	1 737.909	1 737.182	1 737.636	1 737.636
45	1 949.455	1 949.455	1 949.455	1 949.182	1 949.182
50	2 171.000	2 171.000	2 171.000	2 170.727	2 170.727

机器人数量	算法类型
机器人数量	CBS	CBS-DS	CBS-SIPP	CBS-OBSC	CBS-DS-OBSC
15	1.636	1.455	1.273	1.000	1.000
20	4.909	4.545	4.727	4.364	4.182
25	5.545	5.182	5.273	4.727	5.182
30	8.455	8.091	7.091	7.091	6.727
35	10.364	8.636	9.727	9.636	9.545
40	26.273	21.273	16.636	11.727	12.364
45	26.000	23.182	100.909	16.545	16.727
50	52.818	87.182	111.182	42.364	29.455