Internals
These symbols are not part of the public API, their existence or behavior can change without a breaking release.
MultiAgentPathFinding.BenchmarkAgent
— Typestruct 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
MultiAgentPathFinding.LazySwappingConflicts
— Typestruct LazySwappingConflicts
Lazy dict-like storage for the mapping (u, v) -> [(u, v),]
(which also forbids (v, u)
since the graph is undirected).
MultiAgentPathFinding.LazyVertexConflicts
— Typestruct LazyVertexConflicts
Lazy dict-like storage for the mapping v -> [v]
.
MultiAgentPathFinding.Reservation
— Typestruct 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 insidesingle_occupied_vertices::Dict{Tuple{Int64, Int64}, Int64}
:(t, v) -> a
wherea
is the only agent occupyingv
at timet
single_occupied_edges::Dict{Tuple{Int64, Int64, Int64}, Int64}
:(t, u, v) -> a
wherea
is the only agent occupying(u, v)
at timet
multi_occupied_vertices::Dict{Tuple{Int64, Int64}, Vector{Int64}}
:(t, v) -> [a1, a2]
wherea1, a2
are the multiple agents occupyingv
at timet
multi_occupied_edges::Dict{Tuple{Int64, Int64, Int64}, Vector{Int64}}
:(t, u, v) -> [a1, a2]
wherea1, a2
are the multiple agents occupying(u, v)
at timet
arrival_vertices::Dict{Int64, Tuple{Int64, Int64}}
:v -> (t, a)
wherea
is the agent whose arrival vertex isv
and who owns it starting at timet
(necessary for stay-at-target behavior)arrival_vertices_crossings::Dict{Int64, Vector{Tuple{Int64, Int64}}}
:v -> [(t2, a1), (t2, a2)]
where theai
are additional agents visiting vertexv
at timesti
, 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.
MultiAgentPathFinding.Reservation
— MethodReservation(
solution::Solution,
mapf::MAPF
) -> MultiAgentPathFinding.Reservation
Compute a Reservation
based on the vertices and edges occupied by solution
.
Conflicts are computed within mapf
.
MultiAgentPathFinding.Reservation
— MethodReservation() -> MultiAgentPathFinding.Reservation
Create an empty Reservation
.
MultiAgentPathFinding.arrive!
— Methodarrive!(
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.
MultiAgentPathFinding.cell_color
— Methodcell_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.
MultiAgentPathFinding.exists_in_graph
— Methodexists_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.
MultiAgentPathFinding.is_collectively_feasible
— Methodis_collectively_feasible(
solution::Solution,
mapf::MAPF;
verbose
) -> Bool
Check whether solution
contains any conflicts between agents.
MultiAgentPathFinding.is_individually_feasible
— Methodis_individually_feasible(
solution::Solution,
mapf::MAPF;
verbose
) -> Bool
Check whether solution
is feasible when agents are considered separately.
MultiAgentPathFinding.is_occupied_edge
— Methodis_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.
MultiAgentPathFinding.is_occupied_vertex
— Methodis_occupied_vertex(
reservation::MultiAgentPathFinding.Reservation,
t::Integer,
v::Integer
) -> Any
Check whether vertex v
is occupied at time t
in a reservation.
MultiAgentPathFinding.is_safe_vertex_to_stop
— Methodis_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.
MultiAgentPathFinding.occupy!
— Methodoccupy!(
reservation::MultiAgentPathFinding.Reservation,
a::Integer,
t::Integer,
v::Integer
)
Update reservation
so that agent a
occupies vertex v
at time t
.
MultiAgentPathFinding.occupy!
— Methodoccupy!(
reservation::MultiAgentPathFinding.Reservation,
a::Integer,
t::Integer,
u::Integer,
v::Integer
)
Update reservation
so that agent a
occupies edge (u, v)
at time t
.
MultiAgentPathFinding.path_cost
— Methodpath_cost(
path::Vector{Int64},
g::SimpleWeightedGraphs.SimpleWeightedGraph
) -> Any
Sum the costs of all the edges in path
within mapf
.
MultiAgentPathFinding.read_benchmark_scenario
— Methodread_benchmark_scenario(
scen::BenchmarkScenario
) -> Vector{MultiAgentPathFinding.BenchmarkAgent}
Read a scenario from an automatically downloaded text file.
Returns a Vector{BenchmarkAgent}
.
MultiAgentPathFinding.read_benchmark_solution
— Methodread_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 costsolution_cost
is the cost of the provided solutionpaths_coord_list
is a vector of agent trajectories, each one being encoded as a vector of coordinate tuples(i, j)
MultiAgentPathFinding.update_reservation!
— Methodupdate_reservation!(
reservation::MultiAgentPathFinding.Reservation,
path::Vector{Int64},
a::Integer,
mapf::MAPF
)
Add the vertices and edges occupied by a path to a reservation.