API reference
Only exported names are part of the API.
MultiAgentPathFinding
— ModuleMultiAgentPathFinding
A package for Multi-Agent Path Finding instances and algorithms.
Exports
Structures
MultiAgentPathFinding.MAPF
— Typestruct MAPF{G<:Graphs.AbstractGraph{Int64}, M, VC, EC}
Instance of a Multi-Agent Path Finding problem with custom conflict rules.
Fields
g::Graphs.AbstractGraph{Int64}
: underlying graphedge_costs::Any
: edge costs, typically stored as a matrixdepartures::Vector{Int64}
: agent departure verticesarrivals::Vector{Int64}
: agent arrival verticesdeparture_times::Vector{Int64}
: agent departure timesvertex_conflicts::Any
: dict-like object linking vertices to their incompatibility setedge_conflicts::Any
: dict-like object linking edges (as tuples) to their incompatibility set
Note
Agents appear at their departure vertex when the departure time comes, and they disappear as soon as they have reached the arrival vertex.
MultiAgentPathFinding.TimedPath
— Typestruct TimedPath
Temporal path through a graph.
Fields
tdep::Int64
: departure timepath::Vector{Int64}
: sequence of vertices
MultiAgentPathFinding.Solution
— Typestruct Solution
Store one TimedPath
for each agent of a MAPF
.
Fields
timed_paths::Dict{Int64, TimedPath}
MultiAgentPathFinding.Reservation
— Typestruct Reservation
Keep track of which vertices and edges are known to be occupied and by whom.
It does not have to be a physical occupation: some agent might be occupying a related vertex or edge which generates a conflict.
Fields
single_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
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).
Access
MultiAgentPathFinding.nb_agents
— Functionnb_agents(mapf::MAPF) -> Int64
Count the number of agents in mapf
.
MultiAgentPathFinding.select_agents
— Functionselect_agents(
mapf::MAPF,
agents::AbstractVector{<:Integer}
) -> MAPF
Select a subset of agents in mapf
and return a new MAPF
.
Feasibility and cost
MultiAgentPathFinding.path_cost
— Functionpath_cost(
timed_path::TimedPath,
a::Integer,
mapf::MAPF
) -> Any
Sum the costs of all the edges in timed_path
. Costs are computed within mapf
for agent a
.
MultiAgentPathFinding.solution_cost
— Functionsolution_cost(solution::Solution, mapf::MAPF) -> Any
Sum the costs of all the paths in solution
. Costs are computed within mapf
for each agent.
MultiAgentPathFinding.is_feasible
— Functionis_feasible(solution::Solution, mapf::MAPF; verbose) -> Bool
Check whether solution
is both individually and collectively feasible (correct paths and no conflicts).
MultiAgentPathFinding.find_conflict
— Functionfind_conflict(
solution::Solution,
mapf::MAPF
) -> Union{Nothing, EdgeConflict, VertexConflict}
Find a conflict in solution
for mapf
.
MultiAgentPathFinding.VertexConflict
— Typestruct VertexConflict
Temporal vertex conflict between two agents (for debugging purposes).
Fields
t::Int64
: timev::Int64
: vertexa1::Int64
: first agenta2::Int64
: second agent
MultiAgentPathFinding.EdgeConflict
— Typestruct EdgeConflict
Temporal edge conflict between two agents (for debugging purposes).
Fields
t::Int64
: timeu::Int64
: edge sourcev::Int64
: edge destinationa1::Int64
: first agenta2::Int64
: second agent
Basic algorithms
MultiAgentPathFinding.dijkstra_by_arrival
— Functiondijkstra_by_arrival(
mapf::MAPF;
show_progress,
threaded
) -> Dict{Int64, V} where V<:(MultiAgentPathFinding.ShortestPathTree{Int64})
Run backward_dijkstra
from each arrival vertex of mapf
.
Returns a dictionary of ShortestPathTree
, one by arrival vertex.
MultiAgentPathFinding.independent_dijkstra
— Functionindependent_dijkstra(
mapf::MAPF;
show_progress,
threaded,
spt_by_arr
) -> Solution
Compute independent shortest paths for each agent of mapf
.
Returns a Solution
.
MultiAgentPathFinding.cooperative_astar
— Functioncooperative_astar(mapf::MAPF; ...) -> Solution
cooperative_astar(
mapf::MAPF,
agents::AbstractVector{<:Integer};
show_progress,
threaded,
spt_by_arr
) -> Solution
Solve a MAPF problem mapf
for a set of agents
with the cooperative A* algorithm of Silver (2005), see https://ojs.aaai.org/index.php/AIIDE/article/view/18726. The A* heuristic is given by independent_dijkstra
.
Returns a Solution
.
Local search
MultiAgentPathFinding.feasibility_search
— Functionfeasibility_search(
mapf::MAPF;
feasibility_timeout,
neighborhood_size,
conflict_price,
conflict_price_increase,
show_progress,
threaded,
spt_by_arr
) -> Tuple{Solution, Dict}
Run independent_dijkstra
and then reduce the number of conflicts with a variant of the MAPF-LNS2 algorithm from Li et al. (2022), see https://ojs.aaai.org/index.php/AAAI/article/view/21266.
Returns a tuple containing a Solution
and a dictionary of statistics.
MultiAgentPathFinding.optimality_search
— Functionoptimality_search(mapf::MAPF; ...) -> Tuple{Solution, Dict}
optimality_search(
mapf::MAPF,
agents;
optimality_timeout,
neighborhood_size,
show_progress,
threaded,
spt_by_arr
) -> Tuple{Solution, Dict}
Run cooperative_astar
on mapf
and then reduce the total path cost with the MAPF-LNS algorithm from Li et al. (2021), see https://www.ijcai.org/proceedings/2021/568.
Returns a tuple containing a Solution
and a dictionary of statistics.
MultiAgentPathFinding.double_search
— Functiondouble_search(mapf::MAPF; ...) -> Tuple{Solution, Dict}
double_search(
mapf::MAPF,
agents;
feasibility_timeout,
optimality_timeout,
neighborhood_size,
conflict_price,
conflict_price_increase,
show_progress,
threaded,
spt_by_arr
) -> Tuple{Solution, Dict}
Combine feasibility_search
and optimality_search
, see https://pastel.hal.science/tel-04053322.
Returns a tuple containing a Solution
and a dictionary of statistics.
Benchmarks
MultiAgentPathFinding.read_benchmark
— Functionread_benchmark(
map_name::AbstractString,
scenario_name::AbstractString;
check
) -> MAPF{SimpleWeightedGraphs.SimpleWeightedGraph{Int64, Float64}, SparseArrays.SparseMatrixCSC{Float64, Int64}, MultiAgentPathFinding.LazyVertexConflicts, MultiAgentPathFinding.LazySwappingConflicts}
Create a MAPF
instance by reading a map ("something.map"
) and scenario ("something.scen"
) from files.
See possible names at https://movingai.com/benchmarks/mapf/index.html (data will be downloaded automatically).
MultiAgentPathFinding.list_map_names
— Functionlist_map_names() -> Vector{String}
List available maps from the benchmark set.
MultiAgentPathFinding.list_scenario_names
— Functionlist_scenario_names() -> Vector{String}
List available scenarios from the benchmark set.
Internals
MultiAgentPathFinding.LazyEdgeConflicts
— Typestruct LazyEdgeConflicts
Lazy dict-like storage for the mapping (u, v) -> [(u, v)]
.
MultiAgentPathFinding.LazySwappingConflicts
— Typestruct LazySwappingConflicts
Lazy dict-like storage for the mapping (u, v) -> [(v, u)]
.
MultiAgentPathFinding.LazyVertexConflicts
— Typestruct LazyVertexConflicts
Lazy dict-like storage for the mapping v -> [v]
.
MultiAgentPathFinding.MAPFBenchmarkProblem
— Typestruct MAPFBenchmarkProblem
Encode one agent of a MAPF scenario.
Fields
index::Int64
bucket::Int64
map_path::String
width::Int64
height::Int64
start_i::Int64
start_j::Int64
goal_i::Int64
goal_j::Int64
optimal_length::Float64
MultiAgentPathFinding.ShortestPathTree
— Typestruct ShortestPathTree{V, W}
Storage for the result of Dijkstra's algorithm run backwards.
Fields
children::Vector
: successor of each vertex in a shortest pathdists::Vector
: distance of each vertex to the arrival
MultiAgentPathFinding.arrival_time
— Methodarrival_time(timed_path::TimedPath) -> Int64
Return the departure time of timed_path
plus its number of edges.
MultiAgentPathFinding.arrival_vertex
— Methodarrival_vertex(timed_path::TimedPath) -> Int64
Return the last vertex of timed_path
.
MultiAgentPathFinding.backward_dijkstra
— Methodbackward_dijkstra(g::Graphs.AbstractGraph, edge_costs; arr)
Run Dijkstra's algorithm backward on graph g
from arrival vertex arr
, with specified edge_costs
.
Returns a ShortestPathTree
where distances can be nothing
.
MultiAgentPathFinding.benchmark_cell_color
— Methodbenchmark_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.(map_matrix)
in the REPL.
MultiAgentPathFinding.build_path_astar
— Methodbuild_path_astar(
parents::Dict,
arr::Integer,
tarr::Integer
) -> TimedPath
Build a TimedPath
from a dictionary of temporal parents
, going backward from arr
which was reached at tarr
.
MultiAgentPathFinding.build_path_from_tree
— Methodbuild_path_from_tree(
spt::MultiAgentPathFinding.ShortestPathTree{V},
dep::Integer,
arr::Integer,
tdep::Integer
) -> TimedPath
Build a TimedPath
from a ShortestPathTree
, going from dep
to arr
and starting at time tdep
.
MultiAgentPathFinding.count_conflicts
— Methodcount_conflicts(solution::Solution, mapf::MAPF) -> Int64
Count the number of conflicts in solution
for mapf
.
MultiAgentPathFinding.departure_time
— Methoddeparture_time(timed_path::TimedPath) -> Int64
Return the departure time of timed_path
.
MultiAgentPathFinding.departure_vertex
— Methoddeparture_vertex(timed_path::TimedPath) -> Int64
Return the first vertex of timed_path
.
MultiAgentPathFinding.edge_at_time
— Methodedge_at_time(
timed_path::TimedPath,
t::Integer
) -> Tuple{Any, Any}
Return the edge crossed by timed_path
at a given time t
, throws an error if it does not exist.
MultiAgentPathFinding.edge_cost
— Methodedge_cost(edge_costs::AbstractMatrix, u, v)
edge_cost(edge_costs::AbstractMatrix, u, v, a, t)
Return the cost of edge (u, v)
for agent a
at time t
when the cost storage edge_costs
is a matrix (hence agent- and time-independent).
This method, as well as Base.eltype
, must be overridden for other storage formats.
MultiAgentPathFinding.exists_in_graph
— Methodexists_in_graph(
timed_path::TimedPath,
g::Graphs.AbstractGraph
) -> Bool
Check that timed_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::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::Reservation,
t::Integer,
v::Integer
) -> Bool
Check whether vertex v
is occupied at time t
in a reservation.
MultiAgentPathFinding.map_from_scenario
— Methodmap_from_scenario(scenario_name::AbstractString) -> String
Return the map associated with a benchmark scenario.
MultiAgentPathFinding.occupy!
— Methodoccupy!(
reservation::Reservation,
a::Integer,
t::Integer,
v::Integer
)
Update reservation
so that agent a
occupies vertex v
at time t
.
MultiAgentPathFinding.occupy!
— Methodoccupy!(
reservation::Reservation,
a::Integer,
t::Integer,
u::Integer,
v::Integer
)
Update reservation
so that agent a
occupies edge (u, v)
at time t
.
MultiAgentPathFinding.parse_benchmark_map
— Methodparse_benchmark_map(
map_matrix::Matrix{Char}
) -> Tuple{SimpleWeightedGraphs.SimpleWeightedGraph{Int64, Float64}, Dict{Tuple{Int64, Int64}, Int64}}
Create a sparse grid graph from a map specified as a matrix of characters.
MultiAgentPathFinding.parse_benchmark_scenario
— Methodparse_benchmark_scenario(
scenario::Vector{MultiAgentPathFinding.MAPFBenchmarkProblem},
coord_to_vertex::Dict
) -> Tuple{Vector{Int64}, Vector{Int64}}
Turn a scenario into vectors of departure and arrival vertices.
MultiAgentPathFinding.random_neighborhood
— Methodrandom_neighborhood(
mapf::MAPF,
neighborhood_size::Integer
) -> AbstractArray
Return a random subset of agents with a given size.
MultiAgentPathFinding.read_benchmark_map
— Methodread_benchmark_map(map_name::AbstractString) -> Matrix{Char}
Read a map matrix from a text file.
Returns a Matrix{Char}
.
MultiAgentPathFinding.read_benchmark_scenario
— Methodread_benchmark_scenario(
scenario_name::AbstractString,
map_name::AbstractString
) -> Vector{MultiAgentPathFinding.MAPFBenchmarkProblem}
Read a scenario from a text file, and check that it corresponds to a given map.
Returns a Vector{MAPFBenchmarkProblem}
.
MultiAgentPathFinding.reinsert_agents!
— Methodreinsert_agents!(
solution::Solution,
backup_solution::Solution
) -> Solution
Reinsert the set of agents from backup_solution
into solution
.
MultiAgentPathFinding.remove_agents!
— Methodremove_agents!(
solution::Solution,
agents::AbstractVector{<:Integer}
) -> Solution
Remove a set of agents from solution
and return a backup_solution
containing only them.
MultiAgentPathFinding.scenarios_from_map
— Methodscenarios_from_map(
map_name::AbstractString
) -> Vector{String}
List the scenarios associated with a benchmark map.
MultiAgentPathFinding.temporal_astar
— Methodtemporal_astar(
::MultiAgentPathFinding.HardConflicts,
g::Graphs.AbstractGraph,
edge_costs;
a,
dep,
arr,
tdep,
reservation,
heuristic,
max_nodes
)
Apply temporal A* to graph g
, with specified edge costs.
Keyword arguments
a
: agentdep
: departure vertexarr
: arrival vertextdep
: departure timereservation
: reservation indicating occupied vertices and edges at various timesheuristic
: indexable giving an underestimate of the remaining distance toarr
max_nodes
: maximum number of nodes in the search tree, defaults tonv(g)^3
MultiAgentPathFinding.temporal_astar
— Methodtemporal_astar(
::MultiAgentPathFinding.SoftConflicts,
g::Graphs.AbstractGraph,
edge_costs;
a,
dep,
arr,
tdep,
reservation,
heuristic,
conflict_price,
max_nodes
)
Apply a bi-objective variant of temporal A* to graph g
with specified edge_costs
.
The objective is to minimize a weighted combination of (1) the number of conflicts and (2) the path cost.
Keyword arguments
a
,dep
,arr
,tdep
,reservation
,heuristic
,max_nodes
: seetemporal_astar
.conflict_price
: price given to the number of conflicts in the objective
MultiAgentPathFinding.update_reservation!
— Methodupdate_reservation!(
reservation::Reservation,
timed_path::TimedPath,
a::Integer,
mapf::MAPF
)
Add the vertices and edges occupied by a timed path to a reservation.
MultiAgentPathFinding.vertex_at_time
— Methodvertex_at_time(timed_path::TimedPath, t::Integer) -> Any
Return the vertex visited by timed_path
at a given time t
, throws an error if it does not exist.
Index
MultiAgentPathFinding
MultiAgentPathFinding.EdgeConflict
MultiAgentPathFinding.LazyEdgeConflicts
MultiAgentPathFinding.LazySwappingConflicts
MultiAgentPathFinding.LazyVertexConflicts
MultiAgentPathFinding.MAPF
MultiAgentPathFinding.MAPFBenchmarkProblem
MultiAgentPathFinding.Reservation
MultiAgentPathFinding.ShortestPathTree
MultiAgentPathFinding.Solution
MultiAgentPathFinding.TimedPath
MultiAgentPathFinding.VertexConflict
MultiAgentPathFinding.arrival_time
MultiAgentPathFinding.arrival_vertex
MultiAgentPathFinding.backward_dijkstra
MultiAgentPathFinding.benchmark_cell_color
MultiAgentPathFinding.build_path_astar
MultiAgentPathFinding.build_path_from_tree
MultiAgentPathFinding.cooperative_astar
MultiAgentPathFinding.count_conflicts
MultiAgentPathFinding.departure_time
MultiAgentPathFinding.departure_vertex
MultiAgentPathFinding.dijkstra_by_arrival
MultiAgentPathFinding.double_search
MultiAgentPathFinding.edge_at_time
MultiAgentPathFinding.edge_cost
MultiAgentPathFinding.exists_in_graph
MultiAgentPathFinding.feasibility_search
MultiAgentPathFinding.find_conflict
MultiAgentPathFinding.independent_dijkstra
MultiAgentPathFinding.is_collectively_feasible
MultiAgentPathFinding.is_feasible
MultiAgentPathFinding.is_individually_feasible
MultiAgentPathFinding.is_occupied_edge
MultiAgentPathFinding.is_occupied_vertex
MultiAgentPathFinding.list_map_names
MultiAgentPathFinding.list_scenario_names
MultiAgentPathFinding.map_from_scenario
MultiAgentPathFinding.nb_agents
MultiAgentPathFinding.occupy!
MultiAgentPathFinding.occupy!
MultiAgentPathFinding.optimality_search
MultiAgentPathFinding.parse_benchmark_map
MultiAgentPathFinding.parse_benchmark_scenario
MultiAgentPathFinding.path_cost
MultiAgentPathFinding.random_neighborhood
MultiAgentPathFinding.read_benchmark
MultiAgentPathFinding.read_benchmark_map
MultiAgentPathFinding.read_benchmark_scenario
MultiAgentPathFinding.reinsert_agents!
MultiAgentPathFinding.remove_agents!
MultiAgentPathFinding.scenarios_from_map
MultiAgentPathFinding.select_agents
MultiAgentPathFinding.solution_cost
MultiAgentPathFinding.temporal_astar
MultiAgentPathFinding.temporal_astar
MultiAgentPathFinding.update_reservation!
MultiAgentPathFinding.vertex_at_time