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

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