API reference

struct MAPF{W, VC, EC}

Instance of a Multi-Agent Path Finding problem with custom conflict rules.

Constructors

MAPF(
    graph::AbstractGraph,
    departures::Vector{Int},
    arrivals::Vector{Int};
    vertex_conflicts=LazyVertexConflicts(),
    edge_conflicts=LazyEdgeConflicts()
)

Fields

• graph::SimpleWeightedGraphs.SimpleWeightedGraph{Int64, W} where W: underlying weighted graph

• departures::Vector{Int64}: agent departure vertices

• arrivals::Vector{Int64}: agent arrival vertices

• vertex_conflicts::Any: indexable object linking vertices to their incompatibility set

• edge_conflicts::Any: indexable object linking edges (as tuples) to their incompatibility set

struct Solution

Store one path for each agent of a MAPF.

Fields

• paths::Vector{Vector{Int64}}

nb_agents(mapf::MAPF) -> Int64

Count the number of agents in mapf.

select_agents(
    mapf::MAPF,
    agents::AbstractVector{<:Integer}
) -> MAPF

Select a subset of agents in mapf and return a new MAPF.

sum_of_costs(solution::Solution, mapf::MAPF) -> Any

Sum the costs of all the paths in solution. Costs are computed within mapf for each agent.

is_feasible(solution::Solution, mapf::MAPF; verbose) -> Bool

Check whether solution is both individually and collectively feasible (correct paths and no conflicts).

find_conflict(
    solution::Solution,
    mapf::MAPF
) -> Union{Nothing, EdgeConflict, VertexConflict}

Find a conflict in solution for mapf.

struct VertexConflict

Temporal vertex conflict between two agents (for debugging purposes).

Fields

• t::Int64: time

• v::Int64: vertex

• a1::Int64: first agent

• a2::Int64: second agent

struct EdgeConflict

Temporal edge conflict between two agents (for debugging purposes).

Fields

• t::Int64: time

• u::Int64: edge source

• v::Int64: edge destination

• a1::Int64: first agent

• a2::Int64: second agent

independent_dijkstra(mapf::MAPF) -> Solution

Compute independent shortest paths for each agent of mapf.

Returns a Solution where some paths may be empty if the vertices are not connected.

cooperative_astar(mapf::MAPF) -> Solution
cooperative_astar(
    mapf::MAPF,
    agents::AbstractVector{<:Integer}
) -> Solution

Solve a MAPF problem mapf for a set of agents with the cooperative A* algorithm of Silver (2005), see https://ojs.aaai.org/index.php/AIIDE/article/view/18726.

Returns a Solution where some paths may be empty if the vertices are not connected.

list_instances() -> Vector{SubString{String}}

List available maps from the benchmark set.

BenchmarkScenario

Identify a specific benchmark map and scenario from the Sturtevant MAPF benchmarks.

Fields

• instance::String: name of the instance

• scen_type::String: type of scenario, random or even

• type_id::Int64: id of the scenario among those with the same type

• agents::Union{Nothing, Int64}: number of agents included

read_benchmark_map(
    instance_name::AbstractString
) -> Matrix{Char}

Read a map from an automatically downloaded text file.

Return a Matrix{Char}.

parse_benchmark_map(
    grid::AbstractMatrix;
    allow_diagonal_moves
) -> @NamedTuple{graph::SimpleWeightedGraphs.SimpleWeightedGraph{Int64, Float64}, coord_to_vertex::Dict{Tuple{Int64, Int64}, Int64}, vertex_to_coord::Vector{Tuple{Int64, Int64}}}

Create a sparse grid graph from a map specified as a matrix of characters.

Return a named tuple (; graph, coord_to_vertex, vertex_to_coord), where the last two items map between integer graph vertices v and coordinate tuples (i, j).

passable_cell(c::Char)

Determine if a cell is passable terrain or not.

plot_mapf(scen::BenchmarkScenario; ...) -> Makie.Figure
plot_mapf(
    scen::BenchmarkScenario,
    solution::Union{Nothing, Solution};
    time,
    video_path,
    frames_per_move,
    frames_per_second,
    display_grid,
    display_targets
) -> Makie.Figure

Visualize a solution for one of the grid benchmark instances at a given time step.

If a solution and video_path are provided, the entire animation will be recorded and saved there.