Workshop on Multi-Agent Path Finding
10 July, 2016
Submissions Due: April 18, 2016
This workshop addresses the problem of multi-agent path finding where the goal is to compute a path for multiple agents from an initial configuration to a goal configuration without colliding with other agents, while at the same time optimizing a cost function such as total distance traveled. The past five years have seen the rise of provably correct algorithms for multi-agent path finding which can find optimal solutions to problems that were previously only solvable via heuristic methods. These algorithms fall into three broad categories; search based algorithms, which intelligently generate low-dimensional representations of the very high-dimensional multi-agent path finding problem; rule based algorithms, which compose simple behaviors to generate paths for even densely packed systems; and AI based approaches, which recast the multi-agent path finding problem as a canonical problem in AI for which advanced planners exist. The purpose of this workshop is to gather the foremost designers of multi-agent algorithms in each of these categories, and practitioners who operate large multi-agent systems in a common forum. Topics to be covered, but are not limited to, include
Boolean satisfiability approaches
Network and topology-based approaches
Managing large configuration spaces
Target assignment for multi-agent path finding
Task scheduling for multi-agent systems
Robust plan execution for multi-agent systems
Practical uses and implementations of multi-agent path systems
Liron Cohen, Tansel Uras, Sven Koenig. Feasibility Study: Using Highways for Bounded-Suboptimal Multi-Agent Path Finding First published SOCS-2015
Liang He, Jia Pan, Dinesh Manocha. Reciprocal Multi-Agent Navigation with Dynamic Group Behaviors
Luowei Zhou, Pei Yang, Chunlin Chen. Multi-agent Reinforcement Learning with Sparse Ineractions by Negotiation and Knowledge Transfer
Pavel Surynek, Ariel Felner, Roni Stern, Eli Boyarski. Efficient SAT Approach to Multi-Agent Path Finding under the Sum of Costs Objective Submitted to ECAI 2016
Hang Ma, Sven Koenig, Nora Ayanian, Liron Cohen, Wolfgang Honig, T. K. Satish Kumar, Tansel Uras, Hong Xu. "Overview: Generalizations of Multi-Agent Path Finding to Real-World Scenarios"
Hang Ma, Craig Tovey, Guni Sharon, T. K. Satish Kumar, Sven Koenig. Multi-Agent Path Finding with Payload Transfers and the Package-Exchange Robot-Routing Problem First published AAAI 2016
Hang Ma, Sven Koenig Optimal Target Assignment and Path Finding for Teams of Agents First published AAMAS 2016
Wolfgang Hoenig, T. K. Satish Kumar, Liron Cohen, Hang Ma, Hong Xu, Nora Ayanian, Sven Koenig. Multi-Agent Path Finding with Kinematic Constraints First accepted ICAPS 2016
Konstantin Yakovlev, Anton Andreychuk. Resolving Spatial-Time Conflicts In A Set Of Any-angle Or Angle-constrained Grid Paths
Julio Godoy, Ioannis Karamouzas, Stephen J. Guy, Maria Gini. C-Nav: Implicit Coordination in Crowded Multi-Agent Navigation
Roi Yehoshua, Noa Agmon. Multi-Robot Adversarial Coverage
6 page full papers in IJCAI format, one additional page may be used for references formatting information
2 page short papers
Primary Contact is Glenn Wagner.
Kostas Bekris, of Rutgers University, USA
Tye Brady of Amazon Robotics, USA
Howie Choset at Carnegie Mellon University, USA
Ariel Felner at Ben-Gurion University in Israel
Sven Koenig at USC, USA
Vijay Kumar at UPENN, USA
Pavel Surynek of Charles University in Prague, Czech Republic
Glenn Wagner at Carnegie Mellon, USA.
An introductory session will provide problem definitions, survey existing directions and propose a general terminology.
Oral presentations of selected papers from the submissions. The idea is to give a mini-tutorial of key works in the state of the art, two talks in the morning, two after lunch and then two after a break. Times may vary.
A poster session, including a poster highlights session.
Previous / Related Workshops
AAAI-2012 First International Workshop on Multi-Agent Path Finding addresses the state of the art in the area four years prior. Given the importance of this topic, we felt it was necessary to have another workshop to both update the state of the art and bring practitioners of the field together for a day.