Internals

BenchmarkAgent

Encode one agent of a MAPF scenario.

Fields

• agent::Int64

• bucket::Int64

• width::Int64

• height::Int64

• start_i::Int64

• start_j::Int64

• goal_i::Int64

• goal_j::Int64

• optimal_length::Float64

DijkstraStorage

Fields

• parents::Vector

• dists::Vector

• heap::DataStructures.BinaryHeap

LazySwappingConflicts()

Lazy dict-like storage for the mapping (u, v) -> [(u, v),] (which also forbids (v, u) since the graph is undirected).

LazyVertexConflicts()

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

NoConflictFreePathError

Exception to return when no conflict-free path is found.

Fields

• dep::Int64: path departure vertex

• arr::Int64: path arrival vertex

NoPathError

Exception to return when no path is found.

Fields

• dep::Int64: path departure vertex

• arr::Int64: path arrival vertex

Path

Shortcut for Vector{Int}.

A path is represented by the vector of visited vertices, one per time step.

Reservation

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

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

Each undirected edge (u, v) is represented as (min(u, v), max(u, v)) in the dictionary keys.

Fields

• max_time::Base.RefValue{Int64}: the maximum time of an occupation inside

• 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

• arrival_vertices::Dict{Int64, Tuple{Int64, Int64}}: v -> (t, a) where a is the agent whose arrival vertex is v and who owns it starting at time t (necessary for stay-at-target behavior)

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

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

Compute a Reservation based on the vertices and edges occupied by solution.

Conflicts are computed within mapf.

Reservation()

Create an empty Reservation.

TemporalAstarStorage

Fields

• parents::Dict{Tuple{T, V}, Tuple{T, V}} where {T, V}

• dists::Dict{Tuple{T, V}} where {T, V}

• heap::DataStructures.BinaryHeap

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

Update reservation so that agent a arrives vertex v at time t and never moves again.

cell_color(c::Char)

Give a color object corresponding to the type of cell.

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

exists_in_graph(path::Vector{Int}, g::SimpleWeightedGraph)

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

extend!(reservation::Reservation, new_max_time::Integer)

Extend reservation so that it stretches until new_max_time.

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

Check whether solution contains any conflicts between agents.

Return a Bool.

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

Check whether solution is feasible when agents are considered separately (i.e. whether each individual path is correct).

Return a Bool.

is_occupied_edge(reservation::Reservation, t::Integer, u::Integer, v::Integer)

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

is_occupied_vertex(reservation::Reservation, t::Integer, v::Integer)

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

is_safe_vertex_to_stop(reservation::Reservation, t::Integer, v::Integer)

Check whether vertex v is safe to stop time t in a reservation, which means that no one else crosses it afterwards.

neighbors_and_weights(g::SimpleWeightedGraph, u::Integer)

Jointly iterate over the neighbors and the corresponding edge weights, more efficiently than in SimpleWeightedGraphs.jl.

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.

path_cost(path::Vector{Int}, g::SimpleWeightedGraph)

Sum the costs of all the edges in path within mapf.

read_benchmark_scenario(scen::BenchmarkScenario)

Read a scenario from an automatically downloaded text file.

Return a Vector{BenchmarkAgent}.

read_benchmark_solution(scen::BenchmarkScenario)

Read a solution from an automatically downloaded text file.

Return a named tuple (; lower_cost, solution_cost, paths_coord_list) where:

• lower_cost is a (supposedly) proven lower bound on the optimal cost
• solution_cost is the cost of the provided solution
• paths_coord_list is a vector of agent trajectories, each one being encoded as a vector of coordinate tuples (i, j) (with (1, 1) as the upper-left corner)

replace_weights(graph::SimpleWeightedGraph, new_weights_vec::AbstractVector)

Return a new SimpleWeightedGraph where the weight values have been replaced by new_weights_vec, following the vectorization convention of vectorize_graph.

In other words, replace_weights(graph, vectorize_weights(graph)) == graph.

update_reservation!(reservation::Reservation, path::Path, a::Integer, mapf::MAPF)

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

vectorize_weights(graph::SimpleWeightedGraph)

Return the vector of non-zero weight values in the upper triangle of the adjacency matrix graph.weights.

For each edge (i, j) with i <= j, this allows returning only w[i, j] and discarding w[j, i], so that duplicate information is removed. Thus it is different from nonzeros(graph.weights) which keeps the duplicates.

Edges are ordered by increasing j and then by increasing i.