API Reference

AbstractCostModel{T}

AbstractLowLevelEnv{S,A,C}

Defines a prototype environment for low level search (searching for a path for a single agent).

S is the State type, A is the action type, and C is the cost type. All three must be default constructible (i.e. you can call S(), A() and C() without throwing errors)

In general, a concrete subtype of AbstractLowLevelEnv may include a graph whose edges are traversed by agents.

CompositeCostModel{T}

Combines multiple cost models in a specific order (i.e., to use for cascaded tie-breaking).

A lookup table to store all conflicts that have been detected

ConflictTableHeuristic{T<:Union{HardConflictTable,SoftConflictTable}} <: LowLevelSearchHeuristic{Float64}

Heuristic model based on conflicts between paths.

A node of a constraint tree. Each node has a set of constraints, a candidate solution (set of robot paths), and a cost

DeadlineCost

Identical to TravelTime, except for the behavior of add_heuristic_cost.

addheuristiccost: c = max(0.0, t + Δt - deadline)

DiscreteStateTable

Stores constraints for a discrete state space

EnvDeadlineCost

Deadlines come from an external environment

FullCostModel{F,T,M<:AbstractCostModel{T}} <: AbstractCostModel{T}

The FullCostModel defines all the behavior required for running CBS-based algorithms.

Elements:

• f::F must be callable, and defines how a vector of path costs (e.g., the paths of a solution) should be combined into a single cost that reflects the cost of the entire path group together
• model::M<:AbstractCostModel{T} defines how the cost is computed during low

level search (when individual paths are being compared against each other).

GraphEnv{S,A,C} <: AbstractLowLevelEnv{S,A,C}

An abstract environment type whose concrete subtypes comply with a standard interface.

HardConflictTable

Stores a lookup table of planned paths for all agents. When agent i queries the table, table.paths[i] (the existing path plan for agent i) must be subtracted so that the agent does not try to avoid conflicts with itself.

LowLevelCostModel{C}

The low level cost model defines the objective to be optimized by the solver at the low level. An optimal low level solver will return a path if a feasible path exists) of minimal cost under the objective specified by the associated LowLevelCostModel. The parameter C defines the cost_type of the objective. The following functions must be implemented for a LowLevelCostModel to be used:

• get_initial_cost(model::LowLevelCostModel,env) - returns

the initial_cost for a path

• get_transition_cost(model::LowLevelCostModel{C},path::Path,s::S,a::A, sp::S) where {S,A,C} - defines the cost associated with taking action a from state s to arrive in state sp according to the objective defined by model given that s is the "tip" of path.
• accumulate_cost(model::LowLevelCostModel{C}, current_cost::C, transition_cost::C) - defines how cost accumulates as new PathNodes are added to a Path.

LowLevelSearchHeuristic{C} <: AbstractCostModel{C}

Abstract type of a heuristic that returns cost of type C.

MetaCost

MetaCost maintaining separate costs for individual agents that have been combined into a MetaAgent.

• independent_costs::Vector{T} a vector of costs, 1 per agent
• total_cost::T the total cost, which reflects the combined cost (its interpretation depends on the MetaCostModel used to define cost- upating behavior)

MetaSolution{S}

Wrapper for a LowLevelSolution that allows for keeping track of groups.

MultiDeadlineCost

Combines multiple deadlines according to some specified aggregation function.

MultiStageEnvDistanceHeuristic <: LowLevelSearchHeuristic{Float64}

m.dists[i][stage] stores the distance from that stage's goal to the final stage's goal for agent i. The heuristic cost is computed as follows:

h = get_heuristic_cost(m.h,env,s) + cost_from_stage()

NullCost <: LowLevelCostModel{Float64}

Cost equal to 0.0.

PIBTCache{S,A}

Contains info to be passed along through recursive calls to the PIBT algorithm for multi-agent path planning. Info to be stored:

• current state of each agent (should be lined up at the same time step)
• priority of each agent
• the planned action (and associated next state) for each agent
• the search environment for each agent, which contains e.g., the agent's goal, costmodel, heuristicmodel, etc.
• a conflict table of sorts to indicate which states/actions are reserved
• countdown flags that identify which paths are "active". If pibt is operating

on a "ragged" plan, where some paths have been planned further into the future than others, it needs to ensure that planning does not continue for a given path until all of the other paths have "caught up" to it.

PIBTReservationTable

ReservationTable

Data structure for reserving resources over a time interval. The table stores a vector of reservations for each resource. When a new reservation is added to the table, it is inserted into the reservation vector associated to the requested resource.

ResourceReservation

r::ResourceReservation encodes a that resource r.resource is reserved by agent r.agent_id over time interval r.interval.

construct_empty_lookup_table(graph,T::Int)

Returns a soft lookup table to encode possible paths for each agent through graph. The argument T defines the time horizon of the lookup table.

SoftConflictTable

SolverException

Custom exception type for tracking solver timeouts, etc.

TransformCostModel{T,M<:LowLevelCostModel{T}} <: LowLevelCostModel{T}

Applies a transformation to an underlying cost model. e.g., TransformCostModel(c->2*c, TravelTime())

astar!(env,startstate)

A generic implementation of the A* search algorithm that operates on an Environment and initial state.

args:

• env::E <: AbstractLowLevelEnv
• start_state

The following methods must be implemented:

• is_goal(env::E,s::S)
• checkterminationcriteria(env::E,cost::C,path::Path{S,A,C},state::S)
• getpossibleactions(env::E,s::S)
• getnextstate(env::E,s::S,a::A,sp::S)
• gettransitioncost(env::E,s::S,a::A)
• violates_constraints(env::E,s::S,path::Path{S,A,C})

The internal loop of the A* algorithm.

# g(n) = cost of the path from the start node to n,
# h(n) = heuristic estimate of cost from n to goal
# f(n) = g(n) + h(n)

action_space_trait(env)

Defaults to DiscreteSpace

helper to insert conflicts into ConflictTable

Adds a CBSConstraint to a DiscreteConstraintTable

adds a CBSConstraint to a ConstraintTreeNode

add_fat_path_to_table(CAT,fat_path)

add_to_path!(path,env,s,a,sp)

Adds the new (s,a,sp) tuple and its cost (under env) to path.

a special version of aggregate_costs for the meta_env

Conflict-Based Search

Sharon et al 2012
https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/viewFile/5062/5239

cbs_branch!(solver,mapf,node,conflict,priority_queue)

Part of CBS interface. Defaults to splitting on the conflict and adding two nodes to the priority_queue, where each of the child nodes has one of the new complementary constraints.

cbs_bypass!(solver,mapf,node,conflict,priority_queue)

Part of CBS interface. Defaults to false, but can be overridden to modify the priority_queue and/or bypass the branching step of CBS

cbs_update_conflict_table!(solver,mapf,node,constraint)

Allows for flexible conflict-updating dispatch. This function is called within within the default cbs_branch!() method.

combine_agents(conflict_table, groups::Vector{Vector{Int}})

Helper for merging two (meta) agents into a meta-agent

compute_heuristic_cost(env,cost,sp)

Defaults to add_heuristic_cost(env,cost,get_heuristic_cost(env,sp)) Can be overridden so that state info can inform the heuristic cost directly.

compute_path_cost(model,env,path,i)

Compute the cost of a path from scratch.

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_empty_lookup_table(G,T::Int)

Returns an empty lookup table.

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

Helper for displaying Paths

count_conflicts(conflict_table::ConflictTable,i::Int,j::Int)

helper for counting the number of conflicts between agent i and agent j

create_reservations(env::GraphEnv,s,a,sp,t=-1)

Generates three reservations as follows

t0 = get_t(s)
tF = get_t(sp)
t_mid = (t0+tF)/2
reservations = [
    ResourceReservation{Int}(s_idx,get_agent_id(env),   (t0,    t_mid)),
    ResourceReservation{Int}(a_idx,get_agent_id(env),   (t0,    tF)),
    ResourceReservation{Int}(sp_idx,get_agent_id(env),  (t_mid, tF)),
]

In this way, the reservations for one path node will not interfere with those for the next path node.

create_reservation(env,s,a,sp)

Must be overriden for environment env and the relevant state / action types.

default_solution(solver, mapf::AbstractMAPF)

Defines what is returned by the solver in case of failure to find a feasible solution.

deserialize(env,idx,t=-1)

Decodes an integer encoding of a state or action of type state_type(env) or action_type(env)

Checks for an ActionConflict between two Paths at time t

Detect an ActionConflict between two path nodes. Must be overridden for each specific path class

add detected conflicts to conflict table

add detected conflicts to conflict table

detect conflicts between paths

Populates a ConflictTable with all conflicts that occur in a given vector of paths. Conflict checking is performed in a pairwise fashion between all paths.

args:

• conflict_table a ConflictTable to store the detected conflicts
• paths: a list of Paths, one for each individual agent
• idxs (optional) a list of agent ids for which to check collisions against all other agents

Checks for a StateConflict between two Paths at time t

Detect a StateConflict between two path nodes. Must be overridden for each specific path class

extend_path!(path,T)

Extends path to match a given length T by adding PathNodes corresponding to waiting at the final state.

args:

• path the path to be extended
• the desired length of the new path

extend_path(path,T)

Extends a copy of path to match a given length T by adding PathNodes corresponding to waiting at the final state.

args:

• path the path to be extended
• the desired length of the new path

generates a Vector of (State or Action) Constraints from a conflict

get_a

Get the action in a PathNode.

get_agent_idxs(solver,node,mapf,constraint)

Part of CBS interface. Defaults to return the index of a single agent affected by a constraint. Can be overridden to return the index of e.g., a "meta-agent" (group of agents).

get_conflict_index(cache,i,s,a,sp)

Returns the index of an agent that currently occupies sp, or -1 if there is no such agent.

get_conflicting_paths

Operates over a lookup table and returns a dictionary mapping path index to the time index at which the conflict occurred

helper for retrieving conflicts associated with agents i and j

retrieve constraints corresponding to this node and this path

Override this method for when the cost model has arguments

get_fat_path(G,D,start_vtx,goal_vtx)

returns a fat path through G from start_vtx to goal_vtx. Each set of vertices in the fat path contains all vertices with distance d1 from startvtx and distance d2 to goalvtx, where d1+d2 == the length of the shortest path(s) from start_vtx to goal_vtx

G is a graph, D is the distance matrix

get_fat_path_cost(model,nodes)

Returns a scalar cost value depending on typeof(model) and length(nodes).

get_fat_path_cost(m::FlatFPCost,nodes) = 1.0
get_fat_path_cost(m::NormalizedFPCost,nodes) = 1.0/length(nodes)

get_infeasible_cost(model)

Part of cost model interface. Defaults to zero.

get_infeasible_solution

get_initial_cost(model)

Part of cost model interface. Defaults to zero.

get_initial_solution

get_level_set_nodes(env,s,threshold,cost=get_initial_cost(env))

Returns a vector of PathNodes, where the heuristic cost (according to env) of each node falls below threshold.

get_mdd_graph(env,s,threshold,cost=get_initial_cost(env))

Construct a multi-level decision diagram (MDD) graph.

get_next_conflict(conflict_table::ConflictTable)

Returns the next conflict (temporally) that occurs in a conflict table

returns the PathNode (s,a,s') corresponding to step t of path

If t is greater than the length of path, the PathNode returned is (s,wait(s),s) corresponding to waiting at that node of the path.

path[t] is the path node that begins at t-1 and terminates at t

get_s

Get the first state in a PathNode.

get_sp

Get the next state in a PathNode.

handle_solver_exception

Takes care of printing SolverExceptions

hard_reset_solver!(solver)

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

has_constraint(env,table,c::CBSConstraint)

init_dataframe(feats::Tuple)

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

switch places

congested

almost switch corners. With the fat path heuristic, the paths should be:
- Robot 1: [1,5,9,13,14,15]
- Robot 2: [16,12,8,4,3,2]

init_mapf_5

PIBT demo from paper. CBS fails to solve it even with 80000 iterations.

PIBT demo from paper

init_mapf_7

Robot 3 has to get past robots 1 and 2.

init_mapf_8

Robots 1 and 2 have to get past robots 3 and 4. Requires about 660 iterations of regular CBS.

initialize_child_search_node(parent_node::ConstraintTreeNode)

Initialize a new ConstraintTreeNode with the same solution and constraints as the parent node

initialize_root_node

Construct an empty ConstraintTreeNode from a AbstractMAPF instance

is_available

Returns false if the proposed reservation is not available to any of the agent_ids

is_consistent(solution,mapf)

Check if solution satisfies start and end constraints

Checks if a conflict is valid

low_level_search!(
    solver,
    mapf::AbstractMAPF,
    node::ConstraintTreeNode,
    idxs=collect(1:num_agents(mapf)),
    path_finder=a_star!)

Returns a low level solution for a MAPF with constraints. The heuristic
function for cost-to-go is user-defined and environment-specific

num_actions(env)

Returns the cardinality of the single agent state space for an environment. If the state and action spaces are finite and discrete, a discrete constraint table may be used for fast lookup.

num_states(env)

Returns the cardinality of the single agent state space for an environment. If the state and action spaces are finite and discrete, a discrete constraint table may be used for fast lookup.

partially_set_path!

Only replaces the cached path from start_time to length(path). Useful if you want the remainder of the cached path to stay in the lookup table (i.e. for repairing an existing plan).

pibt_priority_law(solver,mapf,cache,i)

Returns a value that will determine the priority of agent i relative to other agents. A lower value means higher priority.

pibt_step!(solver,mapf,i,j=-1)

i is the id of the higher priority agent, j is the index of the lower priority agent.

populate_soft_lookup_table!(CAT,start_times,start_vtxs,goal_vtxs)

profile_solver!(solver,mapf)

Profile solver on mapf: Returns

• solution, timer_results

recompute_cost

Recompute the cost of path (according to env), beginning from initial cost c0.

reconstruct path by working backward from the terminal state

Removes a CBSConstraint to a DiscreteConstraintTable

reserve!(table,reservation)

Attempts to add a reservation to the table. If the reservation conflicts with an existing reservation, does nothing and returns false. If successful, returns true.

reserved_by

Returns the IDs of agents who have reserved a resource within a specific time window.

reset_solver!(solver)

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

Fills undecided with all active agents (inactive agents have already selected their actions)

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.

search_constraints(env,table,n::PathNode)

Returns all CBSConstraints and CBSConstraints that match n, regardless of time.

serialize(env,state,t=-1)

Encodes a state or action as an integer

Sets a CBSConstraint value in a DiscreteConstraintTable

soft_reset_solver!(solver)

Resets iteration counts and start times.

solve!(solver, args ...)

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

sorted_actions(env,s)

Return a vector of actions sorted lowest cost to highest cost.

state_space_trait(env)

Defaults to DiscreteSpace

time_to_deadline(solver)

time to deadline(solver) or runtime_limit(solver)–whichever is shorter.

trim_path!(env,path,T)

Modify path to terminate at time step T. If length(path) < T, the path will be extended to time step T.

trim_solution!

Modify solution so that all paths terminate at time step T.

update_conflict_table!(table,nodes)

Updates a conflict table with a set of nodes.

wait(s)

returns an action that corresponds to waiting at state s

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.

GraphUtils.get_graph(env::GraphEnv)

Must be implemented for all concrete subtypes of GraphEnv

MovingAIBenchmarkFile

Points to a TOML-formatted file that contains the following elements: scenario = "/path/to/scenario/file.scen" mapfile = "/path/to/map/file.map" bucketidx = 1 # an integer n_agents = 2 # an integer

Extension is .bm

ProblemLoader

Can be queried via get_problem(iterator,problem_filename) to return MAPF instances.

is_same_scenario_and_bucket(config1,config2)

Checks that two problem_configs are on the same scenario and bucket.

parse_map_file

Parses a .map file (see citation below) into an indicator grid. Each cell of the map is encoded by one of the following characters: . - passable terrain G - passable terrain @ - out of bounds O - out of bounds T - trees (unpassable) S - swamp (passable from regular terrain) W - water (traversable, but not passable from terrain)

Returns an array of integers encoded as IMPASSABLE=>1, FREE=>0 (we treat only 'G', 'S', and '.' as free).

@article{sturtevant2012benchmarks, title={Benchmarks for Grid-Based Pathfinding}, author={Sturtevant, N.}, journal={Transactions on Computational Intelligence and AI in Games}, volume={4}, number={2}, pages={144 – 148}, year={2012}, url = {http://web.cs.du.edu/~sturtevant/papers/benchmarks.pdf}, }

parse_mapf_scenario(filename,map_path="")

Parses a .scen file into a set of 'buckets', where each bucket contains a list of (start location,goal location) pairs. Each bucket can be used to instantiate MAPF instances some (or all) of these pairs. The benchmarking approach proposed on the benchmark website (https://www.movingai.com/benchmarks/index.html) is to start with a 2-agent MAPF for each bucket, and increase the number of agents until solver time out.

profile_with_skipping!(config,loader)

Follow the Moving AI benchmarking paradigm, where problems are skipped if the solver has already failed on the same problem instance with fewer agents.