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)
Example block output

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]])
Warning

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"))