Internals

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

MultiAgentPathFinding.BenchmarkAgent — Type
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.Reservation — Type
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).

source
MultiAgentPathFinding.Reservation — Method
Reservation(solution::Solution, mapf::MAPF)

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

Conflicts are computed within mapf.

source
MultiAgentPathFinding._download_tracker_solutions — Method
_download_tracker_solutions(instance)

Download every known best solution for instance from the MAPF tracker API and assemble them into a DataFrame with the same columns as the discontinued per-instance solution CSV files.

source
MultiAgentPathFinding._expand_plan — Method
_expand_plan(plan)

Expand a run-length encoded solution plan such as "2rdr2d2r", as returned by the MAPF tracker API, into one character per move ("rrdrddrr"), as expected when parsing solution plans.

source
MultiAgentPathFinding._tracker_results — Method
_tracker_results(scenario_id; page_size)

Fetch every instance (agent count) of a tracker scenario, together with its best known solution, handling the API's pagination transparently.

source
MultiAgentPathFinding._tracker_scenarios — Method
_tracker_scenarios(instance)

List the scenario records for instance (e.g. "empty-8-8") from the MAPF tracker API, each one containing (among other things) its Mongo "id", "scen_type" and "type_id".

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

source
MultiAgentPathFinding.cell_color — Method
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.

source
MultiAgentPathFinding.is_individually_feasible — Method
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.

source
MultiAgentPathFinding.occupy! — Method
occupy!(reservation::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::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_solution — Method
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)
source
MultiAgentPathFinding.replace_weights — Method
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.

source
MultiAgentPathFinding.vectorize_weights — Method
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.

source