webmaster: Sven Koenig

IJCAI-20 Workshop on Multi-Agent Path Finding


Multi-Agent Path Finding (MAPF) is the problem of computing collision-free paths for a team of agents from their current locations to given destinations in a known environment. Application examples include autonomous aircraft towing vehicles, automated warehouse systems, office robots, and game characters in video games. Solving the MAPF problem optimally is NP-hard for many objectives, such as minimizing the sum of the travel costs or the makespan, and can even be NP-hard to approximate. Yet, practical systems must find high-quality collision-free paths for the agents quickly because shorter paths result in higher throughput or lower operating costs (since fewer agents are required).

In recent years, many researchers have explored different variants of the MAPF problem as well as different approaches with different properties. Also, different applications have been studied in artificial intelligence, robotics, and theoretical computer science. The purpose of this workshop is to bring these researchers together to present their research, discuss future research directions, and cross-fertilize the different communities. Researchers and practitioners whose research might apply to MAPF or who might be able to use MAPF techniques in their research are welcome.

Information for Presenters and Participants

The workshop will be held in a Zoom meeting. To join the Zoom meeting, please visit the virtual conference https://www.virtualchair.net/events/ijcai-pricai-2020 and go to Room Red Wing-North 4. A quick way to find the room is to use the calendar function on the left toolbar to find the room for Workshop W11. Once you are in the room, take a seat and press ‘X’ on your keyboard to join the Zoom meeting.

Each presentation will be 10 minutes long including questions. Live presenters are asked to speak for 8-9 minutes and leave 1-2 minutes for questions. We will stream a 10-minute recorded video for presenters unable to attend. There will be a 10-minute break after every hour, allowing more detailed discussions to take place in break out rooms.

Program and Schedule

Date: January 7th, 2021 (UTC)

Time Start (UTC)Time End (UTC)TitleAuthors
08:0008:50Invited talk: Multi-Agent Path Finding for Robotics: Progress and ChallengesWolfgang Hönig
09:0009:20Community Discussion
09:2009:30Learning to Resolve Conflicts for Multi-Agent Path Finding with Conflict-Based SearchTaoan Huang, Sven Koenig and Bistra Dilkina
09:3009:40A Distributed Solver for Multi-Agent Path Finding ProblemsPoom Pianpak, Tran Cao Son, Z O. Toups and William Yeoh
09:4009:50Nested ECBS for Bounded Suboptimal Multi-Agent Path FindingShao-Hung Chan, Jiaoyang Li, Daniel Harabor, Peter J. Stuckey, Graeme Gange, Liron Cohen and Sven Koenig
10:0010:10Exact Approaches to the Multi-Agent Collective Construction ProblemEdward Lam, Peter J. Stuckey, Sven Koenig and T. K. Satish Kumar
10:1010:20winPIBT: Extended Prioritized Algorithm for Iterative Multi-agent Path FindingKeisuke Okumura, Yasumasa Tamura and Xavier Défago
10:2010:30A Declarative Method for Dynamic MAPFAysu Bogatarkan, Volkan Patoglu and Esra Erdem
10:3010:40Dynamic Multi-Agent Path Finding based on Conflict Resolution using Answer Set ProgrammingBasem Atiq, Volkan Patoglu and Esra Erdem
10:4010:50Explanation Generation for Multi-Modal MAPF with Optimal Resource UtilizationAysu Bogatarkan and Esra Erdem
11:1011:20f-Cardinal Conflicts in Conflict-Based SearchEli Boyarski, Pierre Le Bodic, Peter J. Stuckey and Ariel Felner
11:2011:30Multi-Directional Heuristic SearchDor Atzmon, Jiaoyang Li, Ariel Felner, Eliran Nachmani, Shahaf Shperberg, Nathan Sturtevant and Sven Koenig
11:3011:40Safe Multi-Agent Pathfinding with Time UncertaintyTomer Shahar, Shashank Shekhar, Dor Atzmon, Abdallah Saffidine, Brendan Juba and Roni Stern
11:4011:50Optimality in Online Multi-agent Path FindingJonathan Morag, Roni Stern, Ariel Felner, Dor Atzmon and Eli Boyarski
12:0012:10Pushing the Envelope: From Discrete to Continuous Movements in Multi-Agent Path Finding via Lazy EncodingsPavel Surynek
12:1012:20On Modelling Multi-Agent Path Finding as a Classical Planning ProblemJindřich Vodrážka, Roman Barták and Jiří Švancara
12:2012:30A Distributed Pareto-based Path Planning Algorithm for Autonomous Unmanned Aerial VehiclesNader S. Labib, Grégoire Danoy, Matthias R. Brust and Pascal Bouvry
12:3012:40Train Unit Shunting and Servicing: a Real-Life Application of Multi-Agent Path FindingJesse Mulderij, Bob Huisman, Denise Tönissen, Koos van der Linden and Mathijs de Weerdt
12:4012:50Negotiated Path Planning for Non-Cooperative Multi-Robot SystemsAnna Gautier, Bruno Lacerda, Nick Hawes and Michael Wooldridge
12:5013:00Research Challenges and Opportunities in Multi-Agent Path Finding and Multi-Agent Pickup and Delivery ProblemsOren Salzman and Roni Stern

Invited Talk

Title: Multi-Agent Path Finding for Robotics: Progress and Challenges

Abstract: One of the major real-world applications of multi-agent path finding (MAPF) is to enable robots to operate intelligently in dense and cluttered environments. In the first part of this talk, I will introduce common MAPF variants and algorithms as a general introduction to the workshop. Those variants traditionally simplify the properties of the agents/robots. In the second part of the talk, I'll focus on the application of MAPF algorithms to robotics. Some of the major robot-specific challenges include kinematics (physical extent), dynamics (ability to move over time), interaction between robots, operation over long time horizons, and ability to react to unforeseen, dynamic changes in the environment. I will summarize the progress we have made so far with respect to applying MAPF algorithms to robots and discuss interesting future endeavors.

Bio: Wolfgang Hönig is currently a guest researcher at the California Institute of Technology, USA (Caltech) and he will be leading a new research group at Technical University Berlin, Germany starting in Spring 2021. He was a postdoctoral scholar at Caltech in the aerospace robotics and control laboratory 2019/2020 and holds a Ph.D. in Computer Science from the University of Southern California (USC), a Diploma in Computer Science from the Technical University Dresden, Germany, and an M.S. in Computer Science (Intelligent Robotics) from USC. His research focuses on enabling large teams of physical robots to collaboratively solve real-world tasks, combining methods from artificial intelligence and robotics.

Organizing Committee

  • Edward Lam, Monash University, (edward.lam@monash.edu)
  • Jiaoyang Li, University of Southern California, (jiaoyanl@usc.edu)
  • Dor Atzmon, Ben-Gurion University, (dorat@post.bgu.ac.il)
  • Thayne Walker, University of Denver, (thayne.walker@du.edu)

PC Members

  • Roman Barták, Charles University
  • Eli Boyarski, Ben-Gurion University of the Negev
  • Ariel Felner, Ben-Gurion University of the Negev
  • Daniel Harabor, Monash University
  • Wolfgang Hönig, California Institute of Technology
  • Sven Koenig, University of Southern California
  • T. K. Satish Kumar, University of Southern California
  • Hang Ma, Simon Fraser University
  • Roni Stern, Ben Gurion University of the Negev
  • Pavel Surynek, Czech Technical University in Prague
  • Glenn Wagner, Carnegie Mellon University
  • Han Zhang, University of Southern California

Important dates

  • Paper submission deadline: 23:59 on September 4th, 2020 (UTC-12)
  • Paper notification: September 25th, 2020
  • Final version: December 14th, 2020
  • Workshop: January 7th, 2021

Information for authors

Submission page: https://easychair.org/conferences/?conf=womapf20
Format: Any format is acceptable.
Page limitation: There is no limit on the number of pages.

All submissions that relate to collision-free path planning or navigation for multiple agents are welcome, including but not limited to:

  • Search-, rule-, reduction-, reactive-, and learning-based MAPF planners
  • Combination of MAPF and task allocation/scheduling
  • Combination of MAPF and execution monitoring
  • Variants and generalizations of the MAPF problem
  • Application domains for MAPF planners
  • Actual applications of MAPF planners
  • Customization of MAPF planners for actual robots (including kinematic constraints)
  • Standardization of MAPF terminology and benchmarks

Submissions can contain relevant work in all possible stages, including work that was recently published, is under submission elsewhere, was only recently finished, or is still ongoing. Authors of papers published or under submission elsewhere are encouraged to submit these papers or short versions (including abstracts) of them to the workshop to educate other researchers about their work, as long as resubmissions are clearly labeled to avoid copyright violations. Position papers and surveys are also welcome. Submissions will go through a light review process to ensure a fit with the topic of the workshop and acceptable quality. Non-archival workshop notes will be produced containing the material presented at the workshop.

(last updated in 2019)