机器学习驱动的多智能体路径搜寻算法综述

doi:10.15960/j.cnki.issn.1007-6093.2023.04.006

摘要/Abstract

摘要：

多智能体路径搜寻(Multi-agent Path Finding, MAPF)问题是多智能体系统中的核心基本问题, 被广泛应用于自动化智能仓储、自动驾驶、群体机器人等实际场景。从问题属性来看, 其关键难点在于多个智能体能够同时沿着路径行驶, 同时保证不发生碰撞, 属于NP-难组合优化问题。然而, 上述现实世界应用需要算法能够在较短的计算时间内为大量智能体搜索高质量的无碰撞路径, 更短的路径将导致更高的系统吞吐量以及更低的操作成本, 给经典MAPF运筹算法带来了极大挑战。因此, 近年来大量工作开始聚焦于使用机器学习方法赋能多智能体路径搜寻问题的研究, 以期加快求解速度、提升求解质量。本文综述内容包括三部分, 包括MAPF问题的核心概念、优化目标、基准任务, 经典MAPF算法的问题建模、核心思想、算法优劣, 并从机器学习赋能程度从低到高分别介绍一系列机器学习赋能的MAPF算法, 并给出具体的示意图和伪代码。本文还总结了机器学习驱动的多智能体路径搜寻算法目前面临的主要挑战, 并提出未来潜在研究方向, 以期可帮助领域内的研究者, 并促进机器学习方法在经典多智能体路径搜寻领域的发展。

关键词: 机器学习, 多智能体路径搜寻, 多智能体强化学习

Abstract:

The Multi-agent Path Finding (MAPF) problem is a core fundamental issue in multi-agent systems and has been widely applied in practical scenarios such as automated intelligent warehousing, autonomous driving, and swarm robotics. From the perspective of problem attributes, the key difficulty lies in enabling multiple intelligent agents to travel along paths simultaneously while ensuring no collisions occur, making it an NP-hard combinatorial optimization problem. However, the aforementioned realworld applications require algorithms to find high-quality, collision-free paths for a large number of intelligent agents within a short computation time. Shorter paths lead to higher system throughput and lower operating costs, presenting significant challenges for classical MAPF optimization algorithms. As a result, in recent years, numerous studies have begun focusing on using machine learning methods to empower MAPF research, aiming to accelerate solution speed and improve solution quality. This paper presents a comprehensive review in three parts, including the core concepts, optimization objectives, and benchmark tasks of the MAPF problem. It also covers the problem modeling, core ideas, and strengths and weaknesses of traditional MAPF algorithms. Additionally and most importantly, this paper introduces a series of machine learning-empowered MAPF algorithms with varying degrees of machine learning involvement, providing corresponding schematic diagrams and pseudocode. This paper further summarizes the major challenges currently faced by machine learning-driven MAPF algorithms and proposes potential future research directions. This is intended to assist researchers in the field and promote the development of machine learning methods in the classical MAPF domain.

Key words: machine learning, multi-agent pathfinding, multi-agent reinforcement learning

中图分类号:

O221.2

王祥丰, 李文浩. 机器学习驱动的多智能体路径搜寻算法综述[J]. 运筹学学报, 2023, 27(4): 106-135.

Xiangfeng WANG, Wenhao LI. Machine learning-driven multi-agent pathfinding: An overview[J]. Operations Research Transactions, 2023, 27(4): 106-135.

图/表 10

图1

图2

图3

图4

图5

图6

图7

图8

图9

表1

参考文献 119

1	Stern R, Sturtevant N, Felner A, et al. Multi-agent pathfinding: Definitions, variants, and benchmarks[J]. 2019, arXiv: 1906.08291.
2	QiuT,ChengY.Applications and challenges of deep reinforcement learning in multi-robot path planning[J].Journal of Electronic Research and Application,2021,5(6):25-29. doi: 10.26689/jera.v5i6.2809
3	MaH.Graph-based multi-robot path finding and planning[J].Current Robotics Reports,2022,3(3):77-84. doi: 10.1007/s43154-022-00083-8
4	HönigW,KieselS,TinkaA,et al.Persistent and robust execution of MAPF schedules in warehouses[J].IEEE Robotics and Automation Letters,2019,4(2):1125-1131. doi: 10.1109/LRA.2019.2894217
5	Li J, Tinka A, Kiesel S, et al. Lifelong multi-agent path finding in large-scale warehouses[C]//Association for the Advancement of Artificial Intelligence, 2021.
6	Varambally S, Li J, Koenig S. Which MAPF model works best for automated warehousing?[C]//Symposium on Combinatorial Search, 2022.
7	WenL,LiuY,LiH.CL-MAPF: Multi-agent path finding for car-like robots with kinematic and spatiotemporal constraints[J].Robotics and Autonomous Systems,2022,150,103997. doi: 10.1016/j.robot.2021.103997
8	Huang T, Liu J, Zhou X, et al. V2X cooperative perception for autonomous driving: Recent advances and challenges[J]. 2023, arXiv: 2310.03525.
9	ChandraR,MaligiR,AnantulaA,et al.Optimal and efficient multiagent path finding with strategic agents for social navigation[J].IEEE Robotics and Automation Letters,2023,
10	Calderón-Arce C, Solis-Ortega R, Bustillos-Lewis T. Path planning on static environments based on exploration with a swarm robotics and RRG algorithms[C]//2018 IEEE 38th Central America and Panama Convention, 2018: 1-6.
11	Calderón-ArceC,Solis-OrtegaR.Swarm robotics and rapidly exploring random graph algorithms applied to environment exploration and path planning[J].International Journal of Advanced Computer Science and Applications,2019,10(5)
12	FeketeS P,KeldenichP,KosfeldR,et al.Connected coordinated motion planning with bounded stretch[J].Autonomous Agents and Multi-Agent Systems,2023,37(2):43. doi: 10.1007/s10458-023-09626-5
13	Zhang Y, Qian Y, Yao Y, et al. Learning to cooperate: Application of deep reinforcement learning for online AGV path finding[C]//International Joint Conference on Autonomous Agents and Multi-Agent Systems, 2020.
14	Kou N M, Peng C, Ma H, et al. Idle time optimization for target assignment and path finding in sortation centers[C]//Association for the Advancement of Artificial Intelligence, 2020.
15	Kou N M, Peng C, Yan X, et al. Multi-agent path planning with non-constant velocity motion[C]//International Joint Conference on Autonomous Agents and Multi-Agent Systems, 2019.
16	Guo T, Yu J. Sub-1.5 time-optimal multi-robot path planning on grids in polynomial time[J]. 2022, arXiv: 2201.08976.
17	Shi D, Tong Y, Zhou Z, et al. Adaptive task planning for large-scale robotized warehouses[C]//International Conference On Data Engineering, 2022.
18	Li W, Chen H, Jin B, et al. Multi-agent path finding with prioritized communication learning[C]//International Conference on Robotics and Automation, 2022.
19	Shi D, Zhou N, Tong Y, et al. Collision-aware route planning in warehouses made efficient: A strip-based framework[C]//International Conference on Data Engineering, 2023.
20	Surynek P. Towards optimal cooperative path planning in hard setups through satisfiability solving[C]//Pacific Rim International Conference on Artificial Intelligence, 2012.
21	YuJ,LaValleS M.Optimal multirobot path planning on graphs: Complete algorithms and effective heuristics[J].IEEE Transactions on Robotics,2016,32(5):1163-1177. doi: 10.1109/TRO.2016.2593448
22	Gómez R N, Hernández C, Baier J A. Solving sum-of-costs multi-agent pathfinding with answer-set programming[C]//Association for the Advancement of Artificial Intelligence, 2020.
23	Luna R, Bekris K E. Push and swap: Fast cooperative path-finding with completeness guarantees[C]//International Joint Conference on Artificial Intelligence, 2011.
24	De Wilde B, Ter Mors A W, Witteveen C. Push and rotate: Cooperative multiagent path planning[C]//International Foundation for Autonomous Agents and Multiagent Systems, 2013.
25	YuJ.Average case constant factor time and distance optimal multi-robot path planning in well-connected environments[J].Autonomous Robots,2020,44(3-4):469-483. doi: 10.1007/s10514-019-09858-z
26	Standley T. Finding optimal solutions to cooperative pathfinding problems[C]//Association for the Advancement of Artificial Intelligence, 2010.
27	Wagner G, Choset H. A complete multirobot path planning algorithm with performance bounds[C]//Institute of Electrical and Electronics Engineers, 2011.
28	Ferner C, Wagner G, Choset H. Optimal multirobot path planning in low dimensional search spaces[C]//International Conference on Robotics and Automation, 2013.
29	Surynek P. An optimization variant of multi-robot path planning is intractable[C]//Association for the Advancement of Artificial Intelligence, 2010.
30	Yu J, LaValle S. Structure and intractability of optimal multi-robot path planning on graphs[C]//Association for the Advancement of Artificial Intelligence, 2013.
31	Sartoretti G, Koenig S, Choset H. A combined learning-and search-based approach to complete multi-agent path finding[C]//International Joint Conference on Artificial Intelligence, 2019.
32	Paul S, Deshmukh J V. Multi agent path finding using evolutionary game theory[J]. 2022, arXiv: 2212.02010.
33	SartorettiG,KerrJ,ShiY,et al.Primal: Pathfinding via reinforcement and imitation multi-agent learning[J].IEEE Robotics and Automation Letters,2019,4(3):2378-2385. doi: 10.1109/LRA.2019.2903261
34	Reijnen R, Zhang Y, Nuijten W, et al. Combining deep reinforcement learning with search heuristics for solving multi-agent path finding in segment-based layouts[C]//Symposium Series on Computational Intelligence, 2020.
35	Liu Z, Chen B, Zhou H, et al. Mapper: Multi-agent path planning with evolutionary reinforcement learning in mixed dynamic environments[C]//Institute of Electrical and Electronics Engineers, 2020.
36	Huang T, Dilkina B, Koenig S. Learning node-selection strategies in bounded suboptimal conflict-based search for multi-agent path finding[C]//International Joint Conference on Autonomous Agents and Multi-Agent Systems, 2021.
37	SkrynnikA,YakovlevaA,DavydovV,et al.Hybrid policy learning for multiagent pathfinding[J].IEEE Access,2021,9,126034-126047. doi: 10.1109/ACCESS.2021.3111321
38	Huang T, Li J, Koenig S, et al. Anytime multi-agent path finding via machine learning-guided large neighborhood search[C]//Association for the Advancement of Artificial Intelligence, 2022.
39	Abreu N. Efficient deep learning for multi agent pathfinding[C]//Association for the Advancement of Artificial Intelligence, 2022.
40	Guan H, Gao Y, Zhao M, et al. AB-mapper: Attention and BicNet based multi-agent path planning for dynamic environment[C]//Institute of Electrical and Electronics Engineers, 2022.
41	Ma H, Tovey C, Sharon G, et al. Multi-agent path finding with payload transfers and the package-exchange robot-routing problem[C]//Association for the Advancement of Artificial Intelligence, 2016.
42	Felner A, Stern R, Shimony S, et al. Search-based optimal solvers for the multiagent pathfinding problem: Summary and challenges[C]//Annual Symposium on Combinatorial Search, 2017.
43	Surynek P, Felner A, Stern R, et al. An empirical comparison of the hardness of multi-agent path finding under the makespan and the sum of costs objectives[C]//Annual Symposium on Combinatorial Search, 2016.
44	Barták R, Zhou N F, Stern R, et al. Modeling and solving the multi-agent pathfinding problem in picat[C]//International Conference on Tools with Artificial Intelligence, 2017.
45	Ma H, Harabor D, Stuckey P J, et al. Searching with consistent prioritization for multi-agent path finding[C]//Association for the Advancement of Artificial Intelligence, 2019.
46	Ma H, Wagner G, Felner A, et al. Multi-agent path finding with deadlines[C]//International Joint Conference on Artificial Intelligence, 2018.
47	SturtevantN R.Benchmarks for grid-based pathfinding[J].IEEE Transactions on Computational Intelligence and AI in Games,2012,4(2):144-148. doi: 10.1109/TCIAIG.2012.2197681
48	MaH,KoenigS.AI buzzwords explained: Multi-agent path finding[J].AI Matters,2017,3(3):15-19. doi: 10.1145/3137574.3137579
49	Cohen L, Greco M, Ma H, et al. Anytime focal search with applications[C]//International Joint Conference on Artificial Intelligence, 2018.
50	Cohen L, Uras T, Koenig S. Feasibility study: Using highways for bounded-suboptimal multi-agent path finding[C]//Annual Symposium on Combinatorial Search, 2015.
51	Ma H, Hönig W, Kumar T S, et al. Lifelong path planning with kinematic constraints for multi-agent pickup and delivery[C]//Association for the Advancement of Artificial Intelligence, 2019.
52	Švancara J, Vlk M, Stern R, et al. Online multi-agent pathfinding[C]//Association for the Advancement of Artificial Intelligence, 2019.
53	GebserM,ObermeierP,OttoT,et al.Experimenting with robotic intra-logistics domains[J].Theory and Practice of Logic Programming,2018,18(3-4):502-519. doi: 10.1017/S1471068418000200
54	Erdem E, Kisa D, Oztok U, et al. A general formal framework for pathfinding problems with multiple agents[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2013, 27(1): 290-296.
55	Surynek P, Felner A, Stern R, et al. Efficient SAT approach to multi-agent path finding under the sum of costs objective[C]//European Conference on Artificial Intelligence, 2016.
56	Surynek P, Felner A, Stern R, et al. Modifying optimal SAT-based approach to multi-agent path-finding problem to suboptimal variants[C]//Annual Symposium on Combinatorial Search, 2017.
57	Surynek P. Reduced Time-expansion graphs and goal decomposition for solving cooperative path finding sub-optimally[C]//International Joint Conference on Artificial Intelligence, 2015.
58	Wang J, Li J, Ma H, et al. A new constraint satisfaction perspective on multiagent path finding: Preliminary results[C]//International Joint Conference on Autonomous Agents and Multi-Agent Systems, 2019.
59	Han S D, Yu J. Integer programming as a general solution methodology for path-based optimization in robotics: Principles, best practices, and applications[C]//Institute of Electrical and Electronics Engineers, 2019.
60	Sajid Q, Luna R, Bekris K. Multi-agent pathfinding with simultaneous execution of single-agent primitives[C]//Annual Symposium on Combinatorial Search, 2012.
61	Khorshid M, Holte R, Sturtevant N. A polynomial-time algorithm for nonoptimal multi-agent pathfinding[C]//Annual Symposium on Combinatorial Search, 2011.
62	Masehian E, Nejad A H. Solvability of multi robot motion planning problems on trees[C]//Institute of Electrical and Electronics Engineers, 2009.
63	Surynek P. A novel approach to path planning for multiple robots in bi-connected graphs[C]//International Conference on Robotics and Automation, 2009.
64	BoteaA,BonusiD,SurynekP.Solving multi-agent path finding on strongly biconnected digraphs[J].Journal of Artificial Intelligence Research,2018,62,273-314. doi: 10.1613/jair.1.11212
65	GoldenbergM,FelnerA,SternR,et al.Enhanced partial expansion A$.*$[J].Journal of Artificial Intelligence Research,2014,50,141-187. doi: 10.1613/jair.4171
66	WagnerG,ChosetH.Subdimensional expansion for multirobot path planning[J].Artificial intelligence,2015,219,1-24. doi: 10.1016/j.artint.2014.11.001
67	Silver D. Cooperative pathfinding[C]//Proceedings of the First Artificial Intelligence and Interactive Digital Entertainment Conference, 2005.
68	Sturtevant N, Buro M. Improving collaborative pathfinding using map abstraction[C]//Proceedings of the First Artificial Intelligence and Interactive Digital Entertainment Conference, 2006.
69	Wang K H C, Botea A, et al. Fast and memory-efficient multi-agent pathfinding[C]//The International Conference on Automated Planning and Scheduling. 2008, 8: 380-387.
70	Bnaya Z, Felner A. Conflict-oriented windowed hierarchical cooperative A$.$[C]//International Conference on Robotics and Automation*, 2014.
71	Sigurdson D, Bulitko V, Yeoh W, et al. Multi-agent pathfinding with real-time heuristic search[C]//IEEE Conference on Computational Intelligence and Games, 2018.
72	OkumuraK,MachidaM,DéfagoX,et al.Priority inheritance with backtracking for iterative multi-agent path finding[J].Artificial Intelligence,2022,310,103752. doi: 10.1016/j.artint.2022.103752
73	Li J, Chen Z, Harabor D, et al. Anytime multi-agent path finding via large neighborhood search[C]//International Joint Conference on Artificial Intelligence, 2021.
74	Shaw P. Using constraint programming and local search methods to solve vehicle routing problems[C]//International Conference on Principles and Practice of Constraint Programming, 1998.
75	Li J, Chen Z, Harabor D, et al. MAPF-LNS2: Fast repairing for multi-agent path finding via large neighborhood search[C]//Association for the Advancement of Artificial Intelligence, 2022.
76	SharonG,SternR,GoldenbergM,et al.The increasing cost tree search for optimal multi-agent pathfinding[J].Artificial intelligence,2013,195,470-495. doi: 10.1016/j.artint.2012.11.006
77	SharonG,SternR,FelnerA,et al.Conflict-based search for optimal multi-agent pathfinding[J].Artificial Intelligence,2015,219,40-66. doi: 10.1016/j.artint.2014.11.006
78	Boyarski E, Felner A, Stern R, et al. Icbs: The improved conflict-based search algorithm for multi-agent pathfinding[C]//Annual Symposium on Combinatorial Search, 2015.
79	Felner A, Li J, Boyarski E, et al. Adding heuristics to conflict-based search for multi-agent path finding[C]//The International Conference on Automated Planning and Scheduling, 2018.
80	Li J, Felner A, Boyarski E, et al. Improved heuristics for multi-agent path finding with conflict-based search[C]//International Joint Conference on Artificial Intelligence, 2019.
81	Li J, Harabor D, Stuckey P J, et al. Disjoint splitting for multi-agent path finding with conflict-based search[C]//The International Conference on Automated Planning and Scheduling, 2019.
82	Boyarski E, Felner A, Harabor D, et al. Iterative-deepening conflict-based search[C]//International Joint Conference on Artificial Intelligence, 2021.
83	Li J, Harabor D, Stuckey P J, et al. Symmetry-breaking constraints for gridbased multi-agent path finding[C]//Association for the Advancement of Artificial Intelligence, 2019.
84	LiJ,HaraborD,StuckeyP J,et al.Pairwise symmetry reasoning for multi-agent path finding search[J].Artificial Intelligence,2021,301,103574. doi: 10.1016/j.artint.2021.103574
85	ZhangH,LiJ,SurynekP,et al.Multi-agent path finding with mutex propagation[J].Artificial Intelligence,2022,311,103766. doi: 10.1016/j.artint.2022.103766
86	Barer M, Sharon G, Stern R, et al. Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem[C]//Annual Symposium on Combinatorial Search, 2014.
87	Cohen L, Uras T, Kumar T S, et al. Improved solvers for bounded-suboptimal multi-agent path finding[C]//International Joint Conference on Artificial Intelligence, 2016.
88	Li J, Ruml W, Koenig S. Eecbs: A bounded-suboptimal search for multi-agent path finding[C]//Association for the Advancement of Artificial Intelligence, 2021.
89	Surynek P. Unifying search-based and compilation-based approaches to multiagent path finding through satisfiability modulo theories[C]//Annual Symposium on Combinatorial Search, 2019.
90	Gange G, Harabor D, Stuckey P J. Lazy CBS: Implicit conflict-based search using lazy clause generation[C]//The International Conference on Automated Planning and Scheduling, 2019.
91	LamE,Le BodicP,HaraborD,et al.Branch-and-cut-and-price for multi-agent path finding[J].Computers and Operations Research,2022,144,105809. doi: 10.1016/j.cor.2022.105809
92	Lam E, Le Bodic P. New valid inequalities in branch-and-cut-and-price for multiagent path finding[C]//The International Conference on Automated Planning and Scheduling, 2020.
93	WangK,BoteaA.MAPP: A scalable multi-agent path planning algorithm with tractability and completeness guarantees[J].Journal of Artificial Intelligence Research,2011,42,55-90.
94	Ryan M. Constraint-based multi-robot path planning[C]//International Conference on Robotics and Automation, 2010.
95	Ederer I. Enhancing meta-agent conflict-based search for the multi-agent pathfinding problem with informed merging and heuristics[D]. Republik Österreich: Technische Universität Wien, 2021.
96	Langlois S T. Decentralized multiagent metareasoning applications in task allocation and path finding[D]. Maryland: University of Maryland, College Park, 2021.
97	Zhang S, Li J, Huang T, et al. Learning a priority ordering for prioritized planning in multi-agent path finding[C]//Annual Symposium on Combinatorial Search, 2022.
98	Okumura K, Yonetani R, Nishimura M, et al. CTRMs: Learning to construct cooperative timed roadmaps for multi-agent path planning in continuous spaces[C]//International Joint Conference on Autonomous Agents and Multi-Agent Systems, 2022.
99	Ren J, Sathiyanarayanan V, Ewing E, et al. MAPFAST: A deep algorithm selector for multi agent path finding using shortest path embeddings[C]//International Joint Conference on Autonomous Agents and Multi-Agent Systems, 2021.
100	Kaduri O, Boyarski E, Stern R. Algorithm selection for optimal multi-agent pathfinding[C]//The International Conference on Automated Planning and Scheduling, 2020.
101	Sigurdson D, Bulitko V, Koenig S, et al. Automatic algorithm selection in multiagent pathfinding[J]. 2019, arXiv: 1906.03992.
102	Ren J, Sathiyanarayanan V, Ewing E, et al. Automatic optimal multi-agent path finding algorithm selector[C]//Association for the Advancement of Artificial Intelligence, 2021.
103	Alkazzi J M, Rizk A, Salomon M, et al. MAPFASTER: A faster and simpler take on multi-agent path finding algorithm selection[C]//Institute of Electrical and Electronics Engineers, 2022.
104	DamaniM,LuoZ,WenzelE,et al.PRIMAL$_2$: Pathfinding via reinforcement and imitation multi-agent learning-lifelong[J].IEEE Robotics and Automation Letters,2021,6(2):2666-2673. doi: 10.1109/LRA.2021.3062803
105	Virmani L, Ren Z, Rathinam S, et al. Subdimensional expansion using attention-based learning for multi-agent path finding[J]. 2021, arXiv: 2109.14695.
106	WangB,LiuZ,LiQ,et al.Mobile robot path planning in dynamic environments through globally guided reinforcement learning[J].IEEE Robotics and Automation Letters,2020,5(4):6932-6939. doi: 10.1109/LRA.2020.3026638
107	Chen L, Wang Y, Miao Z, et al. Multi-agent path finding using imitation-reinforcement learning with transformer[C]//IEEE International Conference on Robotics and Biomimetics, 2022.
108	Wang Y, Xiang B, Huang S, et al. SCRIMP: Scalable communication for reinforcement-and imitation-learning-based multi-agent pathfinding[J]. 2023, arXiv: 2303.00605.
109	Bignoli A. Graph attentional neural network in multi-agent pickup and delivery problems[D]. Milano: Politecnico di Milano, 2022.
110	Li Q, Gama F, Ribeiro A, et al. Graph neural networks for decentralized multirobot path planning[C]//Institute of Electrical and Electronics Engineers, 2020.
111	LiQ,LinW,LiuZ,et al.Message-aware graph attention networks for large-scale multi-robot path planning[J].IEEE Robotics and Automation Letters,2021,6(3):5533-5540. doi: 10.1109/LRA.2021.3077863
112	Sinkar M, Izhan M, Nimkar S, et al. Multi-agent path finding using dynamic distributed deep learning model[C]//The IEEE International Conference on Communication, Information and Computing Technology, 2021.
113	Ma J, Lian D. Attention-cooperated reinforcement learning for multi-agent path planning[C]//Database Systems for Advanced Applications, 2022.
114	Ma Z, Luo Y, Ma H. Distributed heuristic multi-agent path finding with communication[C]//International Conference on Robotics and Automation, 2021.
115	MaZ,LuoY,PanJ.Learning selective communication for multi-agent path finding[J].IEEE Robotics and Automation Letters,2021,7(2):1455-1462.
116	Ye Z, Li Y, Guo R, et al. Multi-agent pathfinding with communication reinforcement learning and deadlock detection[C]//International Conference on Intelligent Robotics and Applications, 2022.
117	Xu Y, Li Y, Liu Q, et al. Multi-agent pathfinding with local and global guidance[C]//International Conference on Networking, Sensing and Control, 2021.
118	Davydov V, Skrynnik A, Yakovlev K, et al. Q-mixing network for multi-agent pathfinding in partially observable grid environments[C]//The Royal Australian Chemical Institute, 2021.
119	Van Knippenberg M, Holenderski M, Menkovski V. Time-constrained multi-agent path finding in non-lattice graphs with deep reinforcement learning[C]//Asian Conference on Machine Learning, 2021.

算法	候选经典算法
Kaduri等人^[100]	基于A* 的搜索算法^{[26, 65]}、分层MAPF算法^{[76-78, 80]}
Sigurdson等人^[101]	解耦MAPF算法^{[67, 69, 71]}
Ren等人^{[99, 102]}	分层MAPF算法^{[77, 79-80]}、布尔可满足性建模方法^[55]、整数线性规划建模方法^[91]
Alkazzi等人^[103]	分层MAPF算法^{[77, 79-80]}、布尔可满足性建模方法^[55]、整数线性规划建模方法^[91]

[1]	邵虎, 卓越, 刘鹏杰, 邵枫. 城市交通流量估计的运筹学方法[J]. 运筹学学报, 2023, 27(2): 27-48.
[2]	华贇, 王祥丰, 金博. 面向城市交通信号优化的多智能体强化学习综述[J]. 运筹学学报, 2023, 27(2): 49-62.
[3]	张慧灵, 徐洋, 徐姿. 分块凸-非凹极小极大问题的交替近端梯度算法[J]. 运筹学学报, 2022, 26(4): 64-74.
[4]	徐姿, 张慧灵. 非凸极小极大问题的优化算法与复杂度分析[J]. 运筹学学报, 2021, 25(3): 74-86.
[5]	陈征, 高岩. 控制系统生存核的逼近算法[J]. 运筹学学报, 2013, 17(4): 24-32.