webmaster: Sven Koenig

Learn all about Multi-Agent Path Finding (MAPF)


This page can be edited directly by you. If you are a researcher and would like to add data on the performance of your MAPF algorithms on the MAPF benchmark instances, then please email Nathan Sturtevant for the password, click "Login" (in the bottom menu), enter the password, and click "Edit" (in the bottom menu) to add your data to this page! (The password is needed to protect the page from edits by spam bots.)

The best format for benchmark results is up to the community. Some suggestions:

  • Please divide any results into sections by the problem definition being used.
  • Add citations to papers for all results added.
  • When old results are improved upon, maintain previous results to keep a history of improvements (which is especially important if the improvements are small).


Problem Definition:


  • Agents disappear at goal
  • Wait times fixed (=1)
  • Agent shape=Circle,r=1/(2sqrt2) [following allowed]
  • 2^k neighborhoods (4,8,16,32)
  • Time resolution 1/10

random MAPF Benchmarks

Type Map Total Solved for Connectivity
4 8 16 32
City Berlin_1_256     2,4731  
Boston_0_256     3,0271  
Paris_1_256     2,8331  
DAO brc202d     1,7011  
den312d     8491  
den520d     1,6531  
lak303d     1,0351  
orz900d     1,5071  
ost003d     1,1391  
Dragon Age 2 ht_chantry     1,2211  
ht_mansion_n     1,2511  
lt_gallowstemplar     1,3251  
w_woundedcoast     2,0311  
Open empty-16-16     4231  
empty-32-32     8391  
empty-48-48     1,0791  
Open+ obstacles random-32-32-10     6891  
random-32-32-20     7651  
random-64-64-10     1,2611  
random-64-64-20     1,1351  
Maze maze-32-32-2     4471  
maze-32-32-4     3391  
maze-128-128-10     9811  
maze-128-128-2     6011  
Room room-32-32-4     4891  
room-64-64-16     7091  
room-64-64-8     4191  


Extended Increasing Cost Tree Search for Non-Unit Cost Domains

Failure Criteria:

  • Time exceeds 30 seconds
  • Resident memory size exceeds 16GB

Compute Resources:

  • 2.8 GHz cpu (single-threaded)

Algorithm Enhancements:

  • Extensions for non-unit costs
  • Pairwise pruning

(last updated in 2022)