API reference

These symbols are part of the public API, their existence and behavior is guaranteed until the next breaking release.

Structures

MultiAgentPathFinding.MAPF — Type
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

source

Access

Feasibility and cost

MultiAgentPathFinding.sum_of_conflicts — Function
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.

source
MultiAgentPathFinding.is_feasible — Function
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.

source
MultiAgentPathFinding.VertexConflict — Type
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

source
MultiAgentPathFinding.EdgeConflict — Type
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

source

Basic algorithms

MultiAgentPathFinding.cooperative_astar — Function
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.
source

Benchmarks

MultiAgentPathFinding.BenchmarkScenario — Type
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

source
MultiAgentPathFinding.read_benchmark_map — Function
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.

source
MultiAgentPathFinding.parse_benchmark_map — Function
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).

source

Visualization

MultiAgentPathFinding.plot_mapf — Function
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.

Warning

To use this function, first load a Makie.jl backend, like CairoMakie.jl (for static visualization / animation recording) or GLMakie.jl (for interactive exploration).

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
source