Thesis summary: optimal multi-agent pathfinding algorithms
作者： Guni Sharon
DOI:
关键词:
摘要: The multi-agent path finding (MAPF) problem is a generalization of the single-agent for κ > 1 agents. It consists graph and number For each agent, unique start state goal are given, task to find paths all agents from their states states, under constraint that cannot collide during movements. In many cases there an additional minimizing cumulative cost function such as sum time steps required every agent reach its goal. my research providing new methods solve MAPF optimally provide theoretical understandings will help choose best solver given instance.
acm.org 参考文章(11)
Nathan Sturtevant, Ariel Felner, Roni Stern, Guni Sharon, Conflict-based search for optimal multi-agent path finding national conference on artificial intelligence. pp. 563- 569 ,(2012)
Guni Sharon, Roni Stern, Meir Goldenberg, Ariel Felner, The increasing cost tree search for optimal multi-agent pathfinding Artificial Intelligence. ,vol. 195, pp. 470- 495 ,(2013) , 10.1016/J.ARTINT.2012.11.006
Lucia Pallottino, Vincenzo G. Scordio, Antonio Bicchi, Emilio Frazzoli, Decentralized Cooperative Policy for Conflict Resolution in Multivehicle Systems IEEE Transactions on Robotics. ,vol. 23, pp. 1170- 1183 ,(2007) , 10.1109/TRO.2007.909810
Maren Bennewitz, Wolfram Burgard, Sebastian Thrun, Finding and optimizing solvable priority schemes for decoupled path planning techniques for teams of mobile robots Robotics and Autonomous Systems. ,vol. 41, pp. 89- 99 ,(2002) , 10.1016/S0921-8890(02)00256-7
A. Srinivasan, T. Ham, S. Malik, R.K. Brayton, Algorithms for discrete function manipulation international conference on computer aided design. pp. 92- 95 ,(1990) , 10.1109/ICCAD.1990.129849
K. Dresner, P. Stone, A multiagent approach to autonomous intersection management Journal of Artificial Intelligence Research. ,vol. 31, pp. 591- 656 ,(2008) , 10.1613/JAIR.2502
Ariel Felner, Roni Tzvi Stern, Guni Sharon, Meir Goldenberg, Pruning Techniques for the Increasing Cost Tree Search for Optimal Multi-agent Pathfinding annual symposium on combinatorial search. ,(2011)
Nathan Sturtevant, Ariel Felner, Roni Stern, Guni Sharon, Partial domain search tree for constraint-satisfaction problems national conference on artificial intelligence. pp. 125- 127 ,(2013)
Ariel Felner, Roni Stern, Guni Sharon, Max Barer, Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem european conference on artificial intelligence. pp. 961- 962 ,(2014) , 10.3233/978-1-61499-419-0-961
Nathan R. Sturtevant, Ariel Felner, Roni Stern, Guni Sharon, Meta-Agent Conflict-Based Search For Optimal Multi-Agent Path Finding. SOCS. ,(2012)