API reference

MultiAgentPathFinding

A package for Multi-Agent Path Finding instances and algorithms.

Exports

• EdgeConflict
• MAPF
• Reservation
• Solution
• TimedPath
• VertexConflict
• cooperative_astar
• dijkstra_by_arrival
• double_search
• feasibility_search
• find_conflict
• independent_dijkstra
• is_feasible
• list_map_names
• list_scenario_names
• nb_agents
• optimality_search
• path_cost
• read_benchmark
• select_agents
• solution_cost

struct MAPF{G<:Graphs.AbstractGraph{Int64}, M, VC, EC}

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

Fields

• g::Graphs.AbstractGraph{Int64}: underlying graph

• edge_costs::Any: edge costs, typically stored as a matrix

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

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

• departure_times::Vector{Int64}: agent departure times

• vertex_conflicts::Any: dict-like object linking vertices to their incompatibility set

• edge_conflicts::Any: dict-like object linking edges (as tuples) to their incompatibility set

Note

Agents appear at their departure vertex when the departure time comes, and they disappear as soon as they have reached the arrival vertex.

struct TimedPath

Temporal path through a graph.

Fields

• tdep::Int64: departure time

• path::Vector{Int64}: sequence of vertices

struct Solution

Store one TimedPath for each agent of a MAPF.

Fields

• timed_paths::Dict{Int64, TimedPath}

struct Reservation

Keep track of which vertices and edges are known to be occupied and by whom.

It does not have to be a physical occupation: some agent might be occupying a related vertex or edge which generates a conflict.

Fields

• single_occupied_vertices::Dict{Tuple{Int64, Int64}, Int64}: (t, v) -> a where a is the only agent occupying v at time t

• single_occupied_edges::Dict{Tuple{Int64, Int64, Int64}, Int64}: (t, u, v) -> a where a is the only agent occupying (u, v) at time t

• multi_occupied_vertices::Dict{Tuple{Int64, Int64}, Vector{Int64}}: (t, v) -> [a1, a2] where a1, a2 are the multiple agents occupying v at time t

• multi_occupied_edges::Dict{Tuple{Int64, Int64, Int64}, Vector{Int64}}: (t, u, v) -> [a1, a2] where a1, a2 are the multiple agents occupying (u, v) at time t

Note

The split between single and multi is done for efficiency reasons: there will be many more single_occupied than multi_occupied, so allocating a set for all of these would be wasteful (and using Union{Int, Set{Int}} would be type-unstable).

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.

path_cost(
    timed_path::TimedPath,
    a::Integer,
    mapf::MAPF
) -> Any

Sum the costs of all the edges in timed_path. Costs are computed within mapf for agent a.

solution_cost(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

dijkstra_by_arrival(
    mapf::MAPF;
    show_progress,
    threaded
) -> Dict{Int64, V} where V<:(MultiAgentPathFinding.ShortestPathTree{Int64})

Run backward_dijkstra from each arrival vertex of mapf.

Returns a dictionary of ShortestPathTree, one by arrival vertex.

independent_dijkstra(
    mapf::MAPF;
    show_progress,
    threaded,
    spt_by_arr
) -> Solution

Compute independent shortest paths for each agent of mapf.

Returns a Solution.

cooperative_astar(mapf::MAPF; ...) -> Solution
cooperative_astar(
    mapf::MAPF,
    agents::AbstractVector{<:Integer};
    show_progress,
    threaded,
    spt_by_arr
) -> 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. The A* heuristic is given by independent_dijkstra.

Returns a Solution.

feasibility_search(
    mapf::MAPF;
    feasibility_timeout,
    neighborhood_size,
    conflict_price,
    conflict_price_increase,
    show_progress,
    threaded,
    spt_by_arr
) -> Tuple{Solution, Dict}

Run independent_dijkstra and then reduce the number of conflicts with a variant of the MAPF-LNS2 algorithm from Li et al. (2022), see https://ojs.aaai.org/index.php/AAAI/article/view/21266.

Returns a tuple containing a Solution and a dictionary of statistics.

optimality_search(mapf::MAPF; ...) -> Tuple{Solution, Dict}
optimality_search(
    mapf::MAPF,
    agents;
    optimality_timeout,
    neighborhood_size,
    show_progress,
    threaded,
    spt_by_arr
) -> Tuple{Solution, Dict}

Run cooperative_astar on mapf and then reduce the total path cost with the MAPF-LNS algorithm from Li et al. (2021), see https://www.ijcai.org/proceedings/2021/568.

Returns a tuple containing a Solution and a dictionary of statistics.

double_search(mapf::MAPF; ...) -> Tuple{Solution, Dict}
double_search(
    mapf::MAPF,
    agents;
    feasibility_timeout,
    optimality_timeout,
    neighborhood_size,
    conflict_price,
    conflict_price_increase,
    show_progress,
    threaded,
    spt_by_arr
) -> Tuple{Solution, Dict}

Combine feasibility_search and optimality_search, see https://pastel.hal.science/tel-04053322.

Returns a tuple containing a Solution and a dictionary of statistics.

read_benchmark(
    map_name::AbstractString,
    scenario_name::AbstractString;
    check
) -> MAPF{SimpleWeightedGraphs.SimpleWeightedGraph{Int64, Float64}, SparseArrays.SparseMatrixCSC{Float64, Int64}, MultiAgentPathFinding.LazyVertexConflicts, MultiAgentPathFinding.LazySwappingConflicts}

Create a MAPF instance by reading a map ("something.map") and scenario ("something.scen") from files.

See possible names at https://movingai.com/benchmarks/mapf/index.html (data will be downloaded automatically).

list_map_names() -> Vector{String}

List available maps from the benchmark set.

list_scenario_names() -> Vector{String}

List available scenarios from the benchmark set.

struct LazyEdgeConflicts

Lazy dict-like storage for the mapping (u, v) -> [(u, v)].

struct LazySwappingConflicts

Lazy dict-like storage for the mapping (u, v) -> [(v, u)].

struct LazyVertexConflicts

Lazy dict-like storage for the mapping v -> [v].

struct MAPFBenchmarkProblem

Encode one agent of a MAPF scenario.

Fields

• index::Int64

• bucket::Int64

• map_path::String

• width::Int64

• height::Int64

• start_i::Int64

• start_j::Int64

• goal_i::Int64

• goal_j::Int64

• optimal_length::Float64

struct ShortestPathTree{V, W}

Storage for the result of Dijkstra's algorithm run backwards.

Fields

• children::Vector: successor of each vertex in a shortest path

• dists::Vector: distance of each vertex to the arrival

arrival_time(timed_path::TimedPath) -> Int64

Return the departure time of timed_path plus its number of edges.

arrival_vertex(timed_path::TimedPath) -> Int64

Return the last vertex of timed_path.

backward_dijkstra(g::Graphs.AbstractGraph, edge_costs; arr)

Run Dijkstra's algorithm backward on graph g from arrival vertex arr, with specified edge_costs.

Returns a ShortestPathTree where distances can be nothing.

benchmark_cell_color(
    c::Char
) -> ColorTypes.RGB{FixedPointNumbers.N0f8}

Give a color object corresponding to the type of cell.

To visualize a map in VSCode, just run cell_color.(map_matrix) in the REPL.

build_path_astar(
    parents::Dict,
    arr::Integer,
    tarr::Integer
) -> TimedPath

Build a TimedPath from a dictionary of temporal parents, going backward from arr which was reached at tarr.

build_path_from_tree(
    spt::MultiAgentPathFinding.ShortestPathTree{V},
    dep::Integer,
    arr::Integer,
    tdep::Integer
) -> TimedPath

Build a TimedPath from a ShortestPathTree, going from dep to arr and starting at time tdep.

count_conflicts(solution::Solution, mapf::MAPF) -> Int64

Count the number of conflicts in solution for mapf.

departure_time(timed_path::TimedPath) -> Int64

Return the departure time of timed_path.

departure_vertex(timed_path::TimedPath) -> Int64

Return the first vertex of timed_path.

edge_at_time(
    timed_path::TimedPath,
    t::Integer
) -> Tuple{Any, Any}

Return the edge crossed by timed_path at a given time t, throws an error if it does not exist.

edge_cost(edge_costs::AbstractMatrix, u, v)
edge_cost(edge_costs::AbstractMatrix, u, v, a, t)

Return the cost of edge (u, v) for agent a at time t when the cost storage edge_costs is a matrix (hence agent- and time-independent).

This method, as well as Base.eltype, must be overridden for other storage formats.

exists_in_graph(
    timed_path::TimedPath,
    g::Graphs.AbstractGraph
) -> Bool

Check that timed_path is feasible in the graph g, i.e. that all vertices and edges exist.

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

Check whether solution contains any conflicts between agents.

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

Check whether solution is feasible when agents are considered separately.

is_occupied_edge(
    reservation::Reservation,
    t::Integer,
    u::Integer,
    v::Integer
) -> Bool

Check whether edge (u, v) is occupied at time t in a reservation.

is_occupied_vertex(
    reservation::Reservation,
    t::Integer,
    v::Integer
) -> Bool

Check whether vertex v is occupied at time t in a reservation.

map_from_scenario(scenario_name::AbstractString) -> String

Return the map associated with a benchmark scenario.

occupy!(
    reservation::Reservation,
    a::Integer,
    t::Integer,
    v::Integer
)

Update reservation so that agent a occupies vertex v at time t.

occupy!(
    reservation::Reservation,
    a::Integer,
    t::Integer,
    u::Integer,
    v::Integer
)

Update reservation so that agent a occupies edge (u, v) at time t.

parse_benchmark_map(
    map_matrix::Matrix{Char}
) -> Tuple{SimpleWeightedGraphs.SimpleWeightedGraph{Int64, Float64}, Dict{Tuple{Int64, Int64}, Int64}}

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

parse_benchmark_scenario(
    scenario::Vector{MultiAgentPathFinding.MAPFBenchmarkProblem},
    coord_to_vertex::Dict
) -> Tuple{Vector{Int64}, Vector{Int64}}

Turn a scenario into vectors of departure and arrival vertices.

random_neighborhood(
    mapf::MAPF,
    neighborhood_size::Integer
) -> AbstractArray

Return a random subset of agents with a given size.

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

Read a map matrix from a text file.

Returns a Matrix{Char}.

read_benchmark_scenario(
    scenario_name::AbstractString,
    map_name::AbstractString
) -> Vector{MultiAgentPathFinding.MAPFBenchmarkProblem}

Read a scenario from a text file, and check that it corresponds to a given map.

Returns a Vector{MAPFBenchmarkProblem}.

reinsert_agents!(
    solution::Solution,
    backup_solution::Solution
) -> Solution

Reinsert the set of agents from backup_solution into solution.

remove_agents!(
    solution::Solution,
    agents::AbstractVector{<:Integer}
) -> Solution

Remove a set of agents from solution and return a backup_solution containing only them.

scenarios_from_map(
    map_name::AbstractString
) -> Vector{String}

List the scenarios associated with a benchmark map.

temporal_astar(
    ::MultiAgentPathFinding.HardConflicts,
    g::Graphs.AbstractGraph,
    edge_costs;
    a,
    dep,
    arr,
    tdep,
    reservation,
    heuristic,
    max_nodes
)

Apply temporal A* to graph g, with specified edge costs.

Keyword arguments

• a: agent
• dep: departure vertex
• arr: arrival vertex
• tdep: departure time
• reservation: reservation indicating occupied vertices and edges at various times
• heuristic: indexable giving an underestimate of the remaining distance to arr
• max_nodes: maximum number of nodes in the search tree, defaults to nv(g)^3

temporal_astar(
    ::MultiAgentPathFinding.SoftConflicts,
    g::Graphs.AbstractGraph,
    edge_costs;
    a,
    dep,
    arr,
    tdep,
    reservation,
    heuristic,
    conflict_price,
    max_nodes
)

Apply a bi-objective variant of temporal A* to graph g with specified edge_costs.

The objective is to minimize a weighted combination of (1) the number of conflicts and (2) the path cost.

Keyword arguments

• a, dep, arr, tdep, reservation, heuristic, max_nodes: see temporal_astar.
• conflict_price: price given to the number of conflicts in the objective

update_reservation!(
    reservation::Reservation,
    timed_path::TimedPath,
    a::Integer,
    mapf::MAPF
)

Add the vertices and edges occupied by a timed path to a reservation.

vertex_at_time(timed_path::TimedPath, t::Integer) -> Any

Return the vertex visited by timed_path at a given time t, throws an error if it does not exist.