Solving simultaneous target assignment and path planning efficiently with time-independent execution

Wurman, 2008, Coordinating hundreds of cooperative, autonomous vehicles in warehouses, AI Mag. MacAlpine, 2015, Scram: scalable collision-avoiding role assignment with minimal-makespan for formational positioning Turpin, 2014, Goal assignment and trajectory planning for large teams of interchangeable robots, Auton. Robots, 10.1007/s10514-014-9412-1 Hönig, 2018, Trajectory planning for quadrotor swarms, IEEE Trans. Robot., 10.1109/TRO.2018.2853613 Alonso-Mora, 2012, Image and animation display with multiple mobile robots, Int. J. Robot. Res., 10.1177/0278364912442095 Gerkey, 2004, A formal analysis and taxonomy of task allocation in multi-robot systems, Int. J. Robot. Res., 10.1177/0278364904045564 Kuhn, 1955, The hungarian method for the assignment problem Stern, 2019, Multi-agent pathfinding: definitions, variants, and benchmarks Yu, 2013, Structure and intractability of optimal multi-robot path planning on graphs Ma, 2016, Multi-agent path finding with payload transfers and the package-exchange robot-routing problem Yu, 2013, Multi-agent path planning and network flow Surynek, 2009, A novel approach to path planning for multiple robots in bi-connected graphs Wang, 2011, Mapp: a scalable multi-agent path planning algorithm with tractability and completeness guarantees, J. Artif. Intell. Res. de Wilde, 2014, Push and rotate: cooperative multi-agent path planning, J. Artif. Intell. Res. Okumura, 2022, Priority inheritance with backtracking for iterative multi-agent path finding, Artif. Intell., 10.1016/j.artint.2022.103752 Okumura, 2023, Lacam: search-based algorithm for quick multi-agent pathfinding Okumura, 2021, Iterative refinement for real-time multi-robot path planning Li, 2021, Anytime multi-agent path finding via large neighborhood search Okumura, 2021, Time-independent planning for multiple moving agents Gross, 1959 Okumura, 2022, Solving simultaneous target assignment and path planning efficiently with time-independent execution Kornhauser, 1984 Adler, 2015, Efficient multi-robot motion planning for unlabeled discs in simple polygons Surynek, 2010, An optimization variant of multi-robot path planning is intractable Ma, 2016, Optimal target assignment and path finding for teams of agents Barták, 2021, From classical to colored multi-agent path finding Wagner, 2012, Subdimensional expansion and optimal task reassignment Nguyen, 2017, Generalized target assignment and path finding using answer set programming Hönig, 2018, Conflict-based search with optimal task assignment Henkel, 2019, An optimal algorithm to solve the combined task allocation and path finding problem Sharon, 2015, Conflict-based search for optimal multi-agent pathfinding, Artif. Intell., 10.1016/j.artint.2014.11.006 Erdem, 2013, A general formal framework for pathfinding problems with multiple agents Barer, 2014, Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem Ma, 2017, Lifelong multi-agent path finding for online pickup and delivery tasks Liu, 2019, Task and path planning for multi-agent pickup and delivery Chen, 2021, Integrated task assignment and path planning for capacitated multi-agent pickup and delivery, IEEE Robot. Autom. Lett., 10.1109/LRA.2021.3074883 Călinescu, 2008, Reconfigurations in graphs and grids, SIAM J. Discrete Math., 10.1137/060652063 Goraly, 2010, Multi-color pebble motion on graphs, Algorithmica, 10.1007/s00453-009-9290-7 Oh, 2015, A survey of multi-agent formation control, Automatica, 10.1016/j.automatica.2014.10.022 Alonso-Mora, 2011, Multi-robot system for artistic pattern formation Wang, 2020, Shape formation in homogeneous swarms using local task swapping, IEEE Trans. Robot. Aakash, 2022, It costs to get costs! A heuristic-based scalable goal assignment algorithm for multi-robot systems Burkard, 1991, Lexicographic bottleneck problems, Oper. Res. Lett., 10.1016/0167-6377(91)90018-K Solovey, 2016, On the hardness of unlabeled multi-robot motion planning, Int. J. Robot. Res., 10.1177/0278364916672311 Čáp, 2016, Provably safe and deadlock-free execution of multi-robot plans under delaying disturbances Ma, 2017, Multi-agent path finding with delay probabilities Okumura, 2023, Offline time-independent multiagent path planning, IEEE Trans. Robot., 10.1109/TRO.2023.3258690 Kameyama, 2021, Active modular environment for robot navigation Altisen, 2019, Introduction to distributed self-stabilizing algorithms, 10.1007/978-3-031-02013-1 Michael, 2008, Distributed multi-robot task assignment and formation control Choi, 2009, Consensus-based decentralized auctions for robust task allocation, IEEE Trans. Robot. Hopcroft, 1973, An n̂5/2 algorithm for maximum matchings in bipartite graphs, SIAM J. Comput., 10.1137/0202019 Ford, 1956, Maximal flow through a network, Can. J. Math., 10.4153/CJM-1956-045-5 Ahuja, 1993 Dijkstra, 1959, A note on two problems in connexion with graphs, Numer. Math., 10.1007/BF01386390 Avis, 1983, A survey of heuristics for the weighted matching problem, Networks, 10.1002/net.3230130404 Silver, 2005, Cooperative pathfinding Sturtevant, 2012, Benchmarks for grid-based pathfinding, IEEE Trans. Comput. Intell. AI Games, 10.1109/TCIAIG.2012.2197681 Han, 2022, Optimizing space utilization for more effective multi-robot path planning K. Okumura, Improving lacam for scalable eventually optimal multi-agent pathfinding, arXiv preprint, 2023. Yu, 2016, Optimal multirobot path planning on graphs: complete algorithms and effective heuristics, IEEE Trans. Robot., 10.1109/TRO.2016.2593448 Surynek, 2016, Efficient sat approach to multi-agent path finding under the sum of costs objective G‘omez, 2020, Solving sum-of-costs multi-agent pathfinding with answer-set programming