Internals

struct 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

struct LazySwappingConflicts

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

struct LazyVertexConflicts

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

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

• arrival_vertices_crossings::Dict{Int64, Vector{Tuple{Int64, Int64}}}: v -> [(t2, a1), (t2, a2)] where the ai are additional agents visiting vertex v at times ti, once it is already owned as an arrival vertex

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). The same goes for arrival crossings.

Reservation(
    solution::Solution,
    mapf::MAPF
) -> MultiAgentPathFinding.Reservation

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

Conflicts are computed within mapf.

Reservation() -> MultiAgentPathFinding.Reservation

Create an empty Reservation.

arrive!(
    reservation::MultiAgentPathFinding.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
) -> ColorTypes.RGB{FixedPointNumbers.N0f8}

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{Int64},
    g::SimpleWeightedGraphs.SimpleWeightedGraph
) -> Bool

Check that 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::MultiAgentPathFinding.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::MultiAgentPathFinding.Reservation,
    t::Integer,
    v::Integer
) -> Any

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

is_safe_vertex_to_stop(
    reservation::MultiAgentPathFinding.Reservation,
    t::Integer,
    v::Integer
) -> Union{Missing, Bool}

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

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

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

occupy!(
    reservation::MultiAgentPathFinding.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{Int64},
    g::SimpleWeightedGraphs.SimpleWeightedGraph
) -> Any

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

read_benchmark_scenario(
    scen::BenchmarkScenario
) -> Vector{MultiAgentPathFinding.BenchmarkAgent}

Read a scenario from an automatically downloaded text file.

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

update_reservation!(
    reservation::MultiAgentPathFinding.Reservation,
    path::Vector{Int64},
    a::Integer,
    mapf::MAPF
)

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