Core Types and Methods

PathNode{S,A}

Includes current state s, action a, next state sp

Path{S,A,C}

Encodes a motion plan as a sequence of PathNode{S,A}s

get_s

Get the first state in a PathNode.

get_a

Get the action in a PathNode.

get_sp

Get the next state in a PathNode.

LowLevelSolution{S,A,T,C}

Contains a list of agent paths and the associated costs. Params:

• S is the state type
• A is the action type
• T is the cost type
• C is the cost model type

Elements:

• paths::Vector{Path{S,A,T}} is the vector of paths
• costs::Vector{T} is the vector of costs, one per path
• cost::T is the total cost for the entire solution

is_goal(env,s)

Returns true if state s satisfies the goal condition of environment env

get_possible_actions(env::E <: AbstractLowLevelEnv{S,A,C}, s::S)

return type must support iteration

get_next_state(env::E <: AbstractLowLevelEnv{S,A,C}, s::S, a::A)

returns a next state s

get_transition_cost(env::E <: AbstractLowLevelEnv{S,A,C},s::S,a::A,sp::S)
get_transition_cost(env,s,a)
get_transition_cost(h,env,s,a,p)

return scalar cost for transitioning from s to sp via a

get_path_cost(env::E <: AbstractLowLevelEnv{S,A,C},path::Path{S,A,C})

get the cost associated with a search path so far

get_heuristic_cost(env::E <: AbstractLowLevelEnv{S,A,C},state::S)
get_heuristic_cost(h,env,s)
get_heuristic_cost(h,s)

get a heuristic "cost-to-go" from state

build_env(mapf::AbstractMAPF, node::ConstraintTreeNode, idx::Int)

Constructs a new low-level search environment for a conflict-based search mapf solver

state_match(s1::S,s2::S)

returns true if s1 and s2 match (not necessarily the same as equal)

violates_constraints(env::E <: AbstractLowLevelEnv{S,A,C},
    path::Path{S,A,C},s::S,a::A,sp::S)

returns true if taking action a from state s violates any constraints associated with env

check_termination_criteria(env::E <: AbstractLowLevelEnv{S,A,C}, cost,
    path::Path{S,A,C}, s::S)

returns true if any termination criterion is satisfied

MAPF

A MAPF is a Multi Agent Path Finding problem. It consists of an environment, env, through which a group of agents may navigate, as well as a list of start and goal states in that environment. Note that this is the labeled case, where each agent has a specific assigned destination.

Elements:

• env::E - the base environment
• starts::Vector{S} - the vector of initial states
• starts::Vector{G} - the vector of goals

get_initial_cost(model)

Part of cost model interface. Defaults to zero.

get_infeasible_cost(model)

Part of cost model interface. Defaults to zero.

add_heuristic_cost(cost_model,heuristic_model,cost,h_cost)

Defines the output heuristic cost that results from combining the current path cost cost with a heuristic "cost-to-go" h_cost. Gener

accumulate_cost(model,current_cost,transition_cost)

Defines the way that a transition_cost updates the current_cost of a Path.

aggregate_costs(model, costs::Vector{T}) where {T}

Defines how costs from multiple distinct paths are combined into a single cost for the whole solution. For example, the aggregation function for a SumOfTravelTime objective is the sum of individual cost.

MetaCostModel

Defines the cost-updating behavior of MetaCost for MetaAgent applications.

TravelTime <: LowLevelCostModel{Float64}

Cost model that assigns cost equal to the duration of a path.

TravelDistance <: LowLevelCostModel{Float64}

Cost model that assigns cost equal to the length (distance) of a path.

`NullHeuristic`

`PerfectHeuristic`

The Perfect Heuristic stores the exact distance between any vertex in a
graph to all goal vertices specified during construction. The distances are
stored in `dists`, a dictionary which maps a goal vertex `v` to a vector of
distances from any other vertex in `1:nv(G)` to `v`.

An example of how to access the distance from vertex `v1` to goal `v2`:
`get_heuristic_cost(h,v1,v2) = h.dists[v2][v1]`

EnvDistanceHeuristic

A convenience struct that allows for the distance matrix to be stored in env instead of the heuristic struct.

MultiStagePerfectHeuristic

Stores multiple lookup tables corresponding to different stages of a Path- Finding search. Each stage has a different goal. The heuristic value at a particular stage must reflect not just the distance to the next goal but the length of the path through all remaining goals.

AStar

A* Path Planner. Fields:

• logger
• replan : if true, planner will replan with an empty conflict table following timeout.

CBSSolver

Path planner that employs Conflict-Based Search.

MetaAgentCBS_Solver

Path planner that employs Meta Agent Conflict-Based Search

PIBTPlanner{C}

Planner based on Priority Inheritance with BackTracking.

Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding Okumura et al, IJCAI 2019 https://www.ijcai.org/Proceedings/2019/0076.pdf

solve!(solver, args ...)

Run the algorithm represented by solver on an instance of a Multi-Agent Path-Finding problem.

reset_solver!(solver)

Resets iteration counts and start times, in addition to best cost and lower bound.

hard_reset_solver!(solver)

To be called when no information (other than iteration and time limits) needs to be stored.

SolverLogger

A logger type for keeping track of thing like runtime, iterations, optimality gap (including upper and lower bound), etc. The following methods allow for accessing and modifying the SolverLogger's fields, and are extended to solver types that wrap a SolverLogger:

iterations(logger) iterationlimit(logger) maxiterations(logger) starttime(logger) runtimelimit(logger) deadline(logger) JuMP.lowerbound(logger) bestcost(logger) verbosity(logger) verbosity(val::Int) debug(logger) solver_status(logger)

setiterations!(solver,val) incrementiterationcount!(logger::SolverLogger) setiterationlimit!(solver,val) setmaxiterations!(solver,val) setstarttime!(solver,val) setruntimelimit!(solver,val) setdeadline!(solver,val) setlowerbound!(solver,val) setlowerbound!(logger::SolverLogger{C},val::C) where {C} setlowerbound!(logger::SolverLogger{NTuple{N,T}},val::R) where {N,T<:Real,R<:Real} setlowerbound!(logger::SolverLogger{T},val::R) where {T<:Tuple,R<:Real} setbestcost!(solver,val) setbestcost!(logger::SolverLogger,val) setbestcost!(logger::SolverLogger{NTuple{N,T}},val::R) where {N,T<:Real,R<:Real} setbestcost!(logger::SolverLogger{T},val::R) where {T<:Tuple,R<:Real} setverbosity!(solver,val) setdebug!(solver,val)

The following methods facilitate control flow based on solver status. checktime(logger) enforcetimelimit!(logger) checkiterations(logger) enforceiterationlimit!(logger)

SolverWrapper

An abstract type whose concrete instances must have a solver field.

FeatureExtractor

Abstract type for features that may be reported about the solution to a PC-TAPF or sequential task assignment problem

extract_feature(solution,extractor,solution,solve_time)

Function must be implemented to extract features from solutions Args:

• solver (pc_tapf solver)
• extractor <: FeatureExtractor
• solution <: SearchEnv
• timer_results::NamedTuple{t,bytes,gctime,memallocs}

profile_solver!(solver,mapf)

Profile solver on mapf: Returns

• solution, timer_results

load_problem(loader,filename)

Generic function that allows a problem instance to be retrived/constructed from loader (which may cache information) and filename::String (which points to a problem file).

write_results(loader,solver_config,prob,problem_file,results)

Write results results of profiling solver_config.solver on problem prob of name problem_name. Can be overloaded to dispatch on problem type when applicable.

run_profiling(config,loader)

Profile the performance of one or more solvers on a set of problems defined by files in a directory. Args:

• config: A named tuple or struct with at least the following fields:
  • problem_dir::String : path to problem files.
  • solver_configs : A vector of objects, each of which has the fields:
    • solver : a solver complying with the CRCBS interface.
    • results_path::String : path at which to store results.
  • feats : A vector of Feature objects, which defines the specific
  features to be extracted and saved.
• Loader: Any kind of cache on which load_problem(loader,problem_file) can be called.

init_dataframe(feats::Tuple)

Instantiate an empty dataframe based on the names and types of feature extractors in feats.

construct_results_dataframe(loader,solver_config,config_template)

Compile results at solver_config.results_path into a DataFrame based on the features stored in solver_config.feats

construct_results_dataframe(loader,solver_config,config_template)

Compile results at solver_config.results_path into a DataFrame based on the features stored in solver_config.feats