Internals

These symbols are not part of the public API, their existence or behavior can change without a breaking release.

MultiAgentPathFinding.BenchmarkAgentType
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

source
MultiAgentPathFinding.ReservationType
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.

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

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

Conflicts are computed within mapf.

source
MultiAgentPathFinding.arrive!Method
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.

source
MultiAgentPathFinding.cell_colorMethod
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.

source
MultiAgentPathFinding.exists_in_graphMethod
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.

source
MultiAgentPathFinding.is_occupied_edgeMethod
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.

source
MultiAgentPathFinding.is_safe_vertex_to_stopMethod
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.

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

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

source
MultiAgentPathFinding.occupy!Method
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.

source
MultiAgentPathFinding.read_benchmark_solutionMethod
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)
source
MultiAgentPathFinding.update_reservation!Method
update_reservation!(
    reservation::MultiAgentPathFinding.Reservation,
    path::Vector{Int64},
    a::Integer,
    mapf::MAPF
)

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

source