Solving the Multiagent Pathfinding Problem with Time-Expanded Networks

References

• Adamo T, Baldacci R, Ghiani G, Guerriero E (2025) Solving the multiagent pathfinding problem with time-expanded networks. https://doi.org/10.1287/ijoc.2024.0951.cd, https://github.com/INFORMSJoC/2024.0951.Google Scholar
• Adamo T, Bektaş T, Ghiani G, Guerriero E, Manni E (2018) Path and speed optimization for conflict-free pickup and delivery under time windows. Transportation Sci. 52(4):739–755.Link, Google Scholar
• Andreychuk A (2020) Multi-agent path finding with kinematic constraints via conflict based search. Kutznetzov SO, Panov AI, Yakovlev KS, eds. Artificial Intelligence RCAI 2020 (Springer, Cham, Switzerland), 29–45.Google Scholar
• Andreychuk A, Yakovlev K, Surynek P, Atzmon D, Stern R (2022) Multi-agent pathfinding with continuous time. Artificial Intelligence 305(September):29–45.Google Scholar
• Atzmon D, Diei A, Rave D (2019) Multi-train path finding. Proc. Internat. Sympos. Combin. Search 10(1):125–129.Crossref, Google Scholar
• Barták R, Zhou NF, Stern R, Boyarski E, Surynek P (2017) Modeling and solving the multi-agent pathfinding problem in Picat. 2017 IEEE 29th Internat. Conf. Tools Artificial Intelligence (ICTAI) (IEEE, New York), 959–966.Google Scholar
• Bennewitz M, Burgard W, Thrun S (2002) Finding and optimizing solvable priority schemes for decoupled path planning techniques for teams of mobile robots. Robotics Autonomous Systems 41(2–3):89–99.Crossref, Google Scholar
• Boland NL, Savelsbergh MW (2019) Perspectives on integer programming for time-dependent models. Trans. Oper. Res. 27(2):147–173.Google Scholar
• Boland N, Hewitt M, Marshall L, Savelsbergh M (2017) The continuous-time service network design problem. Oper. Res. 65(5):1303–1321.Link, Google Scholar
• Boland N, Hewitt M, Marshall L, Savelsbergh M (2018) The price of discretizing time: A study in service network design. EURO J. Transportation Logist. 8(5):195–216.Google Scholar
• Caimi G, Chudak F, Fuchsberger M, Laumanns M, Zenklusen R (2011) A new resource-constrained multicommodity flow model for conflict-free train routing and scheduling. Transportation Sci. 45(2):212–227.Link, Google Scholar
• Corréa AI, Langevin A, Rousseau LM (2007) Scheduling and routing of automated guided vehicles: A hybrid approach. Comput. Oper. Res. 34(6):1688–1707.Crossref, Google Scholar
• Desaulniers G, Langevin A, Riopel D, Villeneuve B (2003) Dispatching and conflict-free routing of automated guided vehicles: An exact approach. Internat. J. Flexible Manufacturing Systems 15(4):309–331.Crossref, Google Scholar
• Engineer FG, Nemhauser GL, Savelsbergh MWP (2011) Dynamic programming-based column generation on time-expanded networks: Application to the dial-a-flight problem. INFORMS J. Comput. 23(1):105–119.Link, Google Scholar
• Erdmann M, Lozano-Perez T (1987) On multiple moving objects. Algorithmica 2(November):477–521.Crossref, Google Scholar
• Fragapane G, De Koster R, Sgarbossa F, Strandhagen JO (2021) Planning and control of autonomous mobile robots for intralogistics: Literature review and research agenda. Eur. J. Oper. Res. 294(2):405–426.Crossref, Google Scholar
• Gómez RN, Hernández C, Baier JA (2021) A compact answer set programming encoding of multi-agent pathfinding. IEEE Access 9:26886–26901.Crossref, Google Scholar
• He E, Boland N, Nemhauser G, Savelsbergh M (2020) Time-dependent shortest path problems with penalties and limits on waiting. INFORMS J. Comput. 33(3):997–1014.Link, Google Scholar
• He EY, Boland N, Nemhauser G, Savelsbergh M (2022) Dynamic discretization discovery algorithms for time-dependent shortest path problems. INFORMS J. Comput. 34(2):1086–1114.Link, Google Scholar
• Hönig W, Kiesel S, Tinka A, Durham J, Ayanian N (2018) Conflict-based search with optimal task assignment. Proc. 17th Internat. Conf. Autonomous Agents MultiAgent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 757–765.Google Scholar
• IBM (2023) User’s manual for CPLEX, v22.1.1. Accessed December 1, 2024, https://www.ibm.com/docs/en/icos/22.1.1.Google Scholar
• Krishnamurthy NN, Batta R, Karwan MH (1993) Developing conflict-free routes for automated guided vehicles. Oper. Res. 41(6):1077–1090.Link, Google Scholar
• LaValle SM (2006) Planning Algorithms (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Li J, Harabor D, Stuckey PJ, Felner A, Ma H, Koenig S (2019a) Disjoint splitting for multi-agent path finding with conflict-based search. Proc. Internat. Conf. Automated Planning Scheduling 29(1):279–283.Crossref, Google Scholar
• Li J, Surynek P, Felner A, Ma H, Kumar TS, Koenig S (2019b) Multi-agent path finding for large agents. Proc. AAAI Conf. Artificial Intelligence 33(01):7627–7634.Crossref, Google Scholar
• Liu Y, Yu Y, Zhang Y, Baldacci R, Tang J, Luo X, Sun W (2023) Branch-cut-and-price for the time-dependent green vehicle routing problem with time windows. INFORMS J. Comput. 35(1):14–30.Link, Google Scholar
• Ma H, Li J, Kumar TKS, Koenig S (2017a) Lifelong multi-agent path finding for online pickup and delivery tasks. Preprint, submitted May 30, https://arxiv.org/abs/1705.10868.Google Scholar
• Ma H, Yang J, Cohen L, Kumar TK, Koenig S (2017b) Feasibility study: Moving non-homogeneous teams in congested video game environments. Proc. AAAI Conf. Artificial Intelligence Interactive Digital Entertainment 13(1):270–272.Crossref, Google Scholar
• Miyamoto T, Inoue K (2016) Local and random searches for dispatch and conflict-free routing problem of capacitated AGV systems. Comput. Indust. Engrg. 91(January):1–9.Crossref, Google Scholar
• Morris R, Chang ML, Archer R, Cross EV, Thompson S, Franke J, Garrett R, Malik W, McGuire K, Hemann G (2015) Self-driving aircraft towing vehicles: A preliminary report. Proc. Workshops 29th AAAI Conf. Artificial Intelligence (AAAI, Washington, DC), 1–8.Google Scholar
• Scherr YO, Hewitt M, Neumann Saavedra BA, Mattfeld DC (2020) Dynamic discretization discovery for the service network design problem with mixed autonomous fleets. Transportation Res. Part B Methodological 141(November):164–195.Crossref, Google Scholar
• Sharon G, Stern R, Felner A, Sturtevant NR (2015) Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence 219(February):40–66.Crossref, Google Scholar
• Sharon G, Stern R, Goldenberg M, Felner A (2013) The increasing cost tree search for optimal multi-agent pathfinding. Artificial Intelligence 195(February):470–495.Crossref, Google Scholar
• Siek JG, Lee LQ, Lumsdaine A (2001) The Boost Graph Library: User Guide and Reference Manual (Pearson Education, New York).Google Scholar
• Silver D (2005) Cooperative pathfinding. Proc. AAAI Conf. Artificial Intelligence Interactive Digital Entertainment 1(1):117–122.Crossref, Google Scholar
• Standley T (2010) Finding optimal solutions to cooperative pathfinding problems. Proc. AAAI Conf. Artificial Intelligence 24(1):173–178.Crossref, Google Scholar
• Stern R (2019) Multi-agent path finding—An overview. Osipov GS, Panov AI, Yakovlev KS, eds. Artificial Intelligence: 5th RAAI Summer School, Dolgoprudny, Russia, July 4–7, 2019, Tutorial Lectures (Springer, Cham, Switzerland), 96–115.Crossref, Google Scholar
• Stern R, Sturtevant N, Felner A, Koenig S, Ma H, Walker T, Li J, et al. (2019) Multi-agent pathfinding: Definitions, variants, and benchmarks. Proc. Internat. Sympos. Combin. Search 10(1):151–158.Crossref, Google Scholar
• Wagner G, Choset H (2015) Subdimensional expansion for multirobot path planning. Artificial Intelligence 219(February):1–24.Crossref, Google Scholar
• Walker TT, Sturtevant NR, Felner A (2018) Extended increasing cost tree search for non-unit cost domains. Lang J, ed. Proc. 27th Internat. Joint Conf. Artificial Intelligence (International Joint Conferences on Artificial Intelligence, Stockholm), 534–540.Google Scholar
• Wurman PR, D’Andrea R, Mountz M (2008) Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI Magazine 29(1):1–9.Google Scholar
• Yu J, LaValle S (2013) Structure and intractability of optimal multi-robot path planning on graphs. Proc. AAAI Conf. Artificial Intelligence 27(1):1443–1449.Crossref, Google Scholar
• Yu J, Rus D (2015) Pebble motion on graphs with rotations: Efficient feasibility tests and planning algorithms. Akin H, Amato N, Isler V, van der Stappen A, eds. Algorithmic Foundations of Robotics XI, Springer Tracts in Advanced Robotics, vol. 107 (Springer, Cham, Switzerland), 729–746.Crossref, Google Scholar