Tutorial
using Graphs
using MultiAgentPathFinding
using CairoMakie
Instance creation
A MAPF
instance can be created from any undirected graph. Agents are specified by their departure and arrival vertex.
graph = cycle_graph(10)
departures = [1, 3]
arrivals = [4, 1]
mapf = MAPF(graph, departures, arrivals)
Multi-Agent Path Finding problem with 10 vertices, 10 edges and 2 agents
By default, vertex and swapping conflicts are forbidden, and the agents stay at their arrival vertex. Another constructor is available that works with a grid and lists of coordinate tuples instead.
Solution algorithms
You can compute independent shortest paths with independent_dijkstra
as follows:
bad_solution = independent_dijkstra(mapf)
Solution([[1, 2, 3, 4], [3, 2, 1]])
The resulting object is a Solution
, with one path per agent. As you can see from the output of is_feasible
, this solution has a conflict:
is_feasible(bad_solution, mapf)
false
To identify it, just call find_conflict
:
find_conflict(bad_solution, mapf)
Conflict at time 2 on vertex 2 between agents 1 and 2
Prioritized planning with cooperative_astar
helps you obtain a solution without conflict, at least when the instance is easy enough:
good_solution = cooperative_astar(mapf)
Solution([[1, 2, 3, 4], [3, 4, 5, 6, 7, 8, 9, 10, 1]])
is_feasible(good_solution, mapf)
true
You can then evaluate its total path length with sum_of_costs
:
sum_of_costs(good_solution, mapf)
11.0
Of course that value depends on the agent ordering chosen for prioritized planning:
better_solution = cooperative_astar(mapf, [2, 1])
sum_of_costs(better_solution, mapf)
9.0
Benchmark dataset
To download and parse an instance from the standard MAPF benchmarks, just specify the name of its map and the details of its scenario inside a BenchmarkScenario
:
instance = "Berlin_1_256"
scen_type = "even"
type_id = 1
agents = 100
scen = BenchmarkScenario(; instance, scen_type, type_id, agents)
BenchmarkScenario("Berlin_1_256", "even", 1, 100)
Then, the MAPF
constructor will prompte you before downloading the necessary files:
bench_mapf = MAPF(scen; allow_diagonal_moves=true)
Multi-Agent Path Finding problem with 47540 vertices, 225704 edges and 100 agents
You can visualize an instance with plot_mapf
:
plot_mapf(scen; display_grid=false)

Best known solutions are also available for some instances thanks to the website Tracking Progress in MAPF. The Solution
constructor will automatically download the necessary data:
small_scen = BenchmarkScenario(; instance="empty-8-8", scen_type="even", type_id=1, agents=32)
benchmark_solution_best = Solution(small_scen)
Solution([[1, 9], [44, 45, 46, 47], [16, 24, 32, 31, 30, 38, 46, 54, 53], [6, 14, 13, 21, 29, 30, 38, 46, 54, 62, 61], [25, 26, 27, 28, 20, 12, 13, 14], [3, 4, 5, 13, 21], [32, 40, 39, 38, 46, 54, 53, 52, 51, 43, 42], [56, 55, 54, 53, 52, 51, 59, 58], [11, 10], [20, 21, 22, 23, 24] … [62, 63, 64, 56, 48], [43, 42, 34, 33], [64, 56, 48, 40, 32, 31, 23], [29, 30, 31, 39], [36, 28, 20, 12, 13, 14, 15], [27, 35, 43, 51, 59, 58, 57], [40, 48, 47, 55], [49, 57, 58, 59, 60], [52, 52, 51, 50, 42, 34, 26], [8, 7]])
The solution files for some instances can be very large (tens of GBs), so think before you validate the download.
For these grid instances, solutions can be visualized at any point in their time span, or recorded as an animation:
plot_mapf(small_scen, benchmark_solution_best; video_path=joinpath(@__DIR__, "solution.mp4"))