The following article is an extended abstract submitted as part of AAAI’s Faculty Highlights Program. Read the full-length article at this link: https://onlinelibrary.wiley.com/doi/10.1002/aaai.12069

Intelligent Planning for Large-Scale Multi-Agent Systems

Hang Ma
Simon Fraser University

This article summarizes the New Faculty Highlights talk with the same title at AAAI 2021.

Intelligent agents such as different types of robots will soon become an integral part of our daily lives. In real-world multi-agent systems, the most fundamental challenges are assigning tasks to multiple agents and planning collision-free paths for the agents. This article surveys four directions of our research on using intelligent planning techniques for the above coordination problems.

For real-world applications of large-scale multi-agent systems, the most fundamental challenges include assigning tasks to agents and planning paths for the agents to reach task locations. Agents must avoid collisions in a congested environment while reaching their task locations as promptly as possible and completing a large number of tasks as quickly as possible. In the artificial intelligence community, much attention has been placed on a simplified version of the path-planning problem, known as Multi-Agent Path Finding (MAPF) (Ma and Koenig, 2017; Stern et al., 2019; Ma, 2022). The problem of MAPF is to plan collision-free paths for multiple agents to their target vertices in discrete time steps on a given graph. This article surveys four research directions that address concerns arising in generalizing MAPF techniques to the above real-world applications of large-scale multi-agent systems (Ma et al., 2016a).

Improved MAPF Algorithms

MAPF is NP-hard to solve optimally (Surynek, 2010; Yu and LaValle, 2013). In our theoretical study (Ma et al., 2016b), we further provide a constant-factor inapproximability result. Nevertheless, the state-of-the-art MAPF algorithm Conflict-Based Search (CBS) (Sharon et al., 2015) can compute optimal MAPF solutions for dozens of agents in a few minutes of computation time. We have explored several directions to make CBS even more efficient (Felner et al., 2018; Li et al., 2019b,a,c, 2020a). We experimentally demonstrates that the combination of the above directions results in an improved version of CBS that is up to 4 orders of magnitude faster and can thus compute solutions for up to 30 times more agents within one minute of computation time than CBS (Li et al., 2021b). We have also explored other directions to make MAPF algorithms more suitable for practical applications, including suboptimal MAPF algorithms (Cohen et al., 2018; Ma et al., 2019a), MAPF with deadlines (Ma et al., 2018b,a), MAPF for large-size agents with different geometric shapes and volumes (Li et al., 2019d), and MAPF for game characters moving in a desired formation (Li et al., 2020b).

Safe Execution of MAPF Solutions

We have studied a variant of MAPF where each agent is delayed and stays in its current vertex with a given probability whenever it intends to move to another vertex during plan execution (Ma, Kumar, and Koenig, 2017). We leveraged insights from this research to win the NeurIPS-20 Flatland Challenge1, a railway scheduling competition held at the top machine learning conference NeurIPS 2020 (Li et al., 2021a). We have also extended the above idea to a hierarchical framework (Ma et al., 2017a) for generating and executing MAPF solutions for real-world multi-robot systems. This framework makes use of a novel efficient procedure (Ho¨ nig et al., 2016a) to transform a MAPF solution to a continuous-time

plan-execution schedule that can be safely executed on real robots.

Combined Target Assignment and Path Finding

We have developed an optimal algorithm that simultaneously assigns target vertices to multiple agents and plans collision-free paths to their target vertices (Ma and Koenig, 2016). Experimentally, the algorithm can compute optimal solutions for more than 400 agents in minutes of runtime. In our empirical study (Ho¨ nig et al., 2016b), we apply our algorithm to solve a formation control problem where drones in different colors move to desired locations to display an English word in 3D space with each letter in a unique color.

 

Long-term Task and Path Planning

We have generalized the above one-shot problems, where agents stop moving when they have all reached their target vertices, to a long-term problem, where we need to repeatedly assign incoming tasks to a set of agents and plan paths for them. We have developed both online (Ma et al., 2017b, 2019b) and offline (Liu et al., 2019) algorithms and applied them to an automated sortation center (Kou et al., 2020) where the robots need to move to sorting stations to obtain express parcels for delivery. Experimental results on an industrial simulator with real-world data show that our algorithms can make decisions for 350 agents in no more than 2 seconds of computation time and improve throughput of a sortation center by up to 12%.

 

Summary

Our ongoing research is to develop a deeper theoretical understanding of using MAPF algorithms for long-term autonomy of real-world multi-agent systems (Ma, 2021), a learning-based distributed MAPF algorithm (Ma, Luo, and Ma, 2021), and algorithms that can jointly solve MAPF and complex task-planning problems (Zhong et al., 2022; Xu et al., 2022). We hope that researchers working in this area can benefit from the insights provided in this article.

 

Notes

 

1https://discourse.aicrowd.com/t/neurips-2020-flatland-winners/4010

References

Cohen, L.; Greco, M.; Ma, H.; Hernandez, C.; Felner, A.; Kumar, T. K. S.; and Koenig, S. 2018. Anytime focal search with applications. In International Joint Conference on Artificial Intelligence, 1434–1441.

Felner, A.; Li, J.; Boyarski, E.; Ma, H.; Cohen, L.; Kumar, T. K. S.; and Koenig, S. 2018. Adding heuristics to conflict-based search for multi-agent pathfinding. In International Conference on Automated Planning and Scheduling, 83–87.

Ho¨ nig, W.; Kumar, T. K. S.; Cohen, L.; Ma, H.; Xu, H.; Ayanian, N.; and Koenig, S. 2016a. Multi-agent path finding with kinematic constraints. In International Conference on Automated Planning and Scheduling, 477–485.

Ho¨ nig, W.; Kumar, T. K. S.; Ma, H.; Ayanian, N.; and Koenig, S. 2016b. Formation change for robot groups in occluded environments. In IEEE/RSJ International Conference on Intelligent Robots and System, 4836–4842.

Kou, N. M.; Peng, C.; Ma, H.; Kumar, T. K. S.; and Koenig, S. 2020. Idle time optimization for target assignment and path finding in sortation centers. In AAAI Conference on Artificial Intelligence, 9925–9932.

Li, J.; Boyarski, E.; Felner, A.; Ma, H.; and Koenig, S. 2019a. Improved heuristics for multi-agent path finding with conflict-based search. In International Joint Conference on Artificial Intelligence, 442–449.

Li, J.; Harabor, D.; Stuckey, P. J.; Felner, A.; Ma, H.; and Koenig, S. 2019b. Disjoint splitting for conflict-based search for multi-agent path finding. In International Conference on Automated Planning and Scheduling, 279–283.

Li, J.; Harabor, D.; Stuckey, P. J.; Ma, H.; and Koenig, S. 2019c. Symmetry-breaking constraints for grid-based multi-agent path finding. In AAAI Conference on Artificial Intelligence, 6087–6095.

Li, J.; Surynek, P.; Felner, A.; Ma, H.; Kumar, T. K. S.; and Koenig, S. 2019d. Multi-agent path finding for large agents. In AAAI Conference on Artificial Intelligence, 7627–7634.

 

Li, J.; Gange, G.; Harabor, D.; Stuckey, P. J.; Ma, H.; and Koenig, S. 2020a. New techniques for pairwise symmetry breaking in multi-agent path finding. In International Conference on Automated Planning and Scheduling, 193–201.

Li, J.; Sun, K.; Ma, H.; Felner, A.; Kumar, T. K. S.; and Koenig, S. 2020b. Moving agents in formation in congested environments. In International Conference on Autonomous Agents and Multiagent Systems, 726–734.

Li, J.; Chen, Z.; Zheng, Y.; Chan, S.-H.; Harabor, D.; Stuckey, P. J.; Ma, H.; and Koenig, S. 2021a. Scalable rail planning and replanning: Winning the 2020 flatland challenge. In International Conference on Automated Planning and Scheduling, 477–485.

Li, J.; Harabor, D.; Stuckey, P. J.; Ma, H.; Gange, G.; and Koenig, S. 2021b. Pairwise symmetry reasoning for multi-agent path finding search. Artifical Intelligence 301:103574.

Liu, M.; Ma, H.; Li, J.; and Koenig, S. 2019. Target assignment and path planning for multi-agent pickup and delivery. In International Conference on Autonomous Agents and Multiagent Systems, 2253–2255.

Ma, H., and Koenig, S. 2016. Optimal target assignment and path finding for teams of agents. In International Conference on Autonomous Agents and Multiagent Systems, 1144–1152.

Ma, H., and Koenig, S. 2017. AI buzzwords explained: Multi-agent path finding (MAPF). AI Matters 3(3):15–19.

Ma, H.; Koenig, S.; Ayanian, N.; Cohen, L.; Ho¨ nig, W.; Kumar, T. K. S.; Uras, T.; Xu, H.; Tovey, C.; and Sharon, G. 2016a. Overview: Generalizations of multi-agent path finding to real-world scenarios. In IJCAI-16 Workshop on Multi-Agent Path Finding.

Ma, H.; Tovey, C.; Sharon, G.; Kumar, T. K. S.; and Koenig, S. 2016b. Multi-agent path finding with payload transfers and the package-exchange robot-routing problem. In AAAI Conference on Artificial Intelligence, 3166–3173.

Ma, H.; Ho¨ nig, W.; Cohen, L.; Uras, T.; Xu, H.; Kumar, T. K. S.; Ayanian, N.; and Koenig, S. 2017a. Overview: A hierarchical framework for plan generation and execution in multi-robot systems. IEEE Intelligent Systems 32(6):6–12.

Ma, H.; Li, J.; Kumar, T. K. S.; and Koenig, S. 2017b. Lifelong multi-agent path finding for online pickup and delivery tasks. In International Conference on Autonomous Agents and Multiagent Systems, 837–845.

Ma, H.; Wagner, G.; Felner, A.; Li, J.; Kumar, T. K. S.; and Koenig, S. 2018a. Multi-agent path finding with deadlines. In International Joint Conference on Artificial Intelligence, 417–423.

Ma, H.; Wagner, G.; Felner, A.; Li, J.; Kumar, T. K. S.; and Koenig, S. 2018b. Multi-agent path finding with deadlines: Preliminary results. In International Conference on Autonomous Agents and Multiagent Systems, 2004–2006.

Ma, H.; Harabor, D.; Stuckey, P. J.; Li, J.; and Koenig, S. 2019a. Searching with consistent prioritization for multi-agent path finding. In AAAI Conference on Artificial Intelligence, 7643–7650.

Ma, H.; Ho¨ nig, W.; Kumar, T. K. S.; Ayanian, N.; and Koenig, S. 2019b. Lifelong path planning with kinematic constraints for multi-agent pickup and delivery. In AAAI Conference on Artificial Intelligence, 7651–7658.

Ma, H.; Kumar, T. K. S.; and Koenig, S. 2017. Multi-agent path finding with delay probabilities. In AAAI Conference on Artificial Intelligence, 3605–3612.

Ma, Z.; Luo, Y.; and Ma, H. 2021. Distributed heuristic multi-agent path finding with communication. In IEEE International Conference on Robotics and Automation, (in press).

Ma, H. 2021. A competitive analysis of online multi-agent path finding. In

International Conference on Automated Planning and Scheduling, 234–242.

 

Ma, H. 2022. Graph-based multi-robot path finding and planning. Current Robotics Reports 1–8.

Sharon, G.; Stern, R.; Felner, A.; and Sturtevant, N. R. 2015. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence 219:40–66.

Stern, R.; Sturtevant, N. R.; Felner, A.; Koenig, S.; Ma, H.; Walker, T. T.; Li, J.; Atzmon, D.; Cohen, L.; Kumar, T. K. S.; Boyarski, E.; and Barta´k, R. 2019.

Multi-agent pathfinding: Definitions, variants, and benchmarks. In International Symposium on Combinatorial Search, 151–159.

Surynek, P. 2010. An optimization variant of multi-robot path planning is intractable. In AAAI Conference on Artificial Intelligence, 1261–1263.

Xu, Q.; Li, J.; Koenig, S.; and Ma, H. 2022. Multi-goal multi-agent pickup and delivery. In IEEE/RSJ International Conference on Intelligent Robots and System, in press.

Yu, J., and LaValle, S. M. 2013. Structure and intractability of optimal multi-robot path planning on graphs. In AAAI Conference on Artificial Intelligence, 1444–1449.

Zhong, X.; Li, J.; Koenig, S.; and Ma, H. 2022. Optimal and bounded-suboptimal multi-goal task assignment and path finding. In IEEE International Conference on Robotics and Automation, 10731–10737.

 

Hang Ma is an Assistant Professor in the School of Computing Science at Simon Fraser University. His research interests lie in the intersection of artificial intelligence, robotics, and machine learning. Specifically, he is interested in topics on automated planning, multi-agent/robot systems, spatio-temporal and constraint reasoning, and applications of probabilistic methods. His research work has won multiple awards, including the ICAPS 2016 Outstanding Paper Award in the Robotics Track, a runner-up for the 2020 Victor Lesser Distinguished Dissertation Award, the ICAPS 2021 Best Dissertation Award, and the ICAPS 2021 Best System Demonstration Award.