API reference

MAPF

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=LazySwappingConflicts()
)

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

Solution

Store one path for each agent of a MAPF.

Fields

• paths::Vector{Vector{Int64}}

nb_agents(mapf::MAPF)

Count the number of agents in mapf.

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

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

sum_of_costs(solution::Solution, mapf::MAPF)

Sum the costs of all the paths in solution.

Costs are computed within mapf for each agent.

sum_of_conflicts(solution::Solution, mapf::MAPF)

Sum the number of conflict-inducing moves for each agent.

It doesn't matter how many other agents are involved in the conflict, or whether it is a vertex or a edge conflict (or both). If a move is infeasible due to a conflict, it counts as one.

is_feasible(solution::Solution, mapf::MAPF; verbose=false)

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

Return a Bool.

find_conflict(solution::Solution, mapf::MAPF)

Find a conflict in solution for mapf.

Return either nothing, a VertexConflict or an EdgeConflict.

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

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)

Compute independent shortest paths for each agent of mapf.

Return a Solution or error if one of the paths doesn't exist.

cooperative_astar(
    mapf::MAPF,
    agents::AbstractVector{<:Integer}=1:nb_agents(mapf);
    conflict_price::Union{Nothing,Real}=nothing,
)

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.

Return a Solution while handling conflicts in a soft or hard way:

• If isnothing(conflict_price), an error will be thrown whenever A* fails to find a conflict-free path given the reservation of previous agents.
• If conflict_price isa Real, each move where an agent encounters a vertex or edge conflict with previous agents will be penalized with the provided price and added to the path cost. The arrival vertex must still be feasible.

list_instances()

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)

Read a map from an automatically downloaded text file.

Return a Matrix{Char} where each character describes the type of one cell.

parse_benchmark_map(grid::AbstractMatrix)

Create a sparse grid graph from a map specified as a matrix (e.g. obtained from read_benchmark_map). Each element of the grid can be either

• a Bool, in which case false denotes passable terrain and true denotes an obstacle
• a Char, in which case '.' denotes passable terrain and '@' denotes an obstacle

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) (with (1, 1) as the upper-left corner).

passable_cell(c::Char)

Determine if a cell is passable terrain or not.

plot_mapf(
    scen::BenchmarkScenario,
    scolution::Union{Solution,Nothing}=nothing;
    kwargs...
)

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.

Keyword arguments

The default values of keyword arguments are not part of the public API.

• video_path::Union{String,Nothing}
• frames_per_move::Integer
• frames_per_second::Integer
• display_grid::Bool
• display_targets::Bool