API Reference

AbstractPCTAPFSolver

Abstract type of which all PC-TAPF solvers must be concrete subtypes. All concrete solvers must implement the following interface for solving PC-TAPF problems:

• solution, cost = solve!(solver,problem_def)
• check_runtime(solver) should trigger an interrupt + early return if the allowable runtime has been exceeded

Also, we need a good Logger type for keeping track of thing like runtime, iterations, optimality gap (including upper and lower bound), etc.

BOT_CARRY <: AbstractRobotAction

Encodes the event "robot r carries object o from x1 to x2"

BOT_GO <: AbstractRobotAction

Encodes the event "robot r goes from x1 to x2"

CLEAN_UP <: AbstractRobotAction

Encodes the event "robot r cleans up locations vtxs`

CleanUpBot <: AbstractRobotType

A robot type for picking up dropped objects, cleaning up spills, and taking care of dead robots

DeadRobot

Robot id is frozen.

Effect:

• Freeze robot
• Add "no-go" constraint to CBS/PIBT (how to do consistently? Perhaps place in SearchEnv and add directly to PCCBSEnv) OR temporarily remove vertex from graph
• Set robot state to NULL state? How to avoid having CBS complain about conflicts? Maybe set State to NULL State and place DeadRobotObject at the collection site?
• Dispatch CleanUpBot to collect frozen robot
• When CleanUpBot returns to "garage", regenerate frozen Robot's ROBOT_AT node and valid state.

DelayedRobot

Robot id is delayed by dt timesteps.

DroppedObject

Object id dropped.

ExtendedAssignmentMILP <: TaskGraphsMILP

Extended to the replanning setting. Replaces robotics with the "tips" of each robot's existing itinerary, and replaces objectics with each COLLECT node that with an invalid robot id.

FlowGraph

Represents a time-extended graph useful for MILP formulations. Each vertex of the FlowGraph corresponds to a "flow edge"

Intruder

An intruder that begins at location start_vtx and follows policy policy

MultiGoalPCMAPFSolver

OilSpill

An obstruction that affects vertices vtxs and edges edges.

Operation <: AbstractPlanningPredicate

A manufacturing operation.

PathSpec

Encodes information about the path that must be planned for a particular schedule node.

Fields:

• node_type::Symbol = :EMPTY
• start_vtx::Int = -1
• final_vtx::Int = -1
• min_duration::Int = 0
• agent_id::Int = -1
• object_id::Int = -1
• plan_path::Bool = true - flag indicating whether a path must be planned. For example, Operation nodes do not require any path planning.
• tight::Bool = false - if true, the path may not terminate prior to the beginning of successors. If tight == true, local slack == 0. For example, GO must not end before COLLECT can begin, because this would produce empty time between planning phases.
• static::Bool = false - if true, the robot must remain in place for this planning phase (e.g., COLLECT, DEPOSIT).
• free::Bool = false - if true, and if the node is a terminal node, the planning must go on until all non-free nodes are completed.
• fixed::Bool = false - if true, do not plan path because it is already fixed. Instead, retrieve the portion of the path directly from the pre-existing solution.

SimplePCMAPFDef

Simple definition of a PCMAPF problem (PCTAPF) with assignments already made.

SimpleRepeatedProblemDef

Intermediate representation of a RepeatedPC_TAPF (useful for I/O)

SimpleReplanningRequest

Intermediate representation of a ProjectRequest (useful for I/O)

StochasticProblem{P<:AbstractPC_TAPF}

Defines a stochastic version of PC_TAPF, wherein different disturbances can cause unexpected problems in the factory.

TeamAssignmentMILP

***Not yet implemented.***

Eextend the assignment matrix formulation of AssignmentMILP to the "team-forming" case where robots must collaboratively transport some objects.

UNDERTAKE <: AbstractRobotAction{CleanUpBot}

Encodes the task of collecting, carrying, and depositing a dead robot

For COLLABORATIVE transport problems

CRCBS.load_problem(loader::TaskGraphsProblemLoader,solver_config,prob_path)

Currently only impemented for PCTAPF and PCTA

CRCBS.pibt_update_solution!(solver,pc_mapf::PC_MAPF,solution::SearchEnv,cache)

Overridden to update the SearchEnv

CRCBS.run_profiling(loader::TaskGraphsProblemLoader,solver_config,problem_dir)

Run profiling with a TaskGraphsProblemLoader.

solve!(solver, base_env::SearchEnv;kwargs...) where {A,P}

Use the planner defined by solver to solve the PC-TAPF problem encoded by base_env. For solvers of type NBSSolver, the algorithm involves repeatedly solving an assignment problem followed by a route-planning problem. Within the generic solve! method it is possible to initialize an assignment problem (the type is not constrained) and then modify it via update_assignment_problem! prior to each new call to solve_assignment_problem!. This is the approach taken for various MILP-based assignment solvers. It is also possible to reconstruct the assignment problem from scratch within each call to solve_assignment_problem!.

Arguments:

• solver <: AbstractPCTAPFSolver
• base_env::SearchEnv : a PC-TAPF problem

Outputs:

• best_env : a SearchEnv data structure that encodes a solution to the problem
• cost : the cost of the solution encoded by best_env

add_capacity_constraint!(model,edge_idx)

add_gadget_layer!(G::FlowGraph,edge_list,t,vtx_map=Dict{Int,Int}())

vtxmap points to `START` vertices

[START (already added)]––––––––-<STAY>–––––––––[MID] | | |–<EDGE>–| |–<EDGE>–| [GADGET]–<EDGE>–[GADGET] |–<EDGE>–| |–<EDGE>–| | | [START (already added)]––––––––-<_STAY>–––––––––[MID]

add_job_shop_constraints!(milp_model::AbstractAssignmentMILP,sched::OperatingSchedule,spec::ProblemSpec) #,model::JuMP.Model)

After an AbstractAssignmentMILP has been optimized, add in any edges that result from an active ``job shop'' constraint (where two robots require the same resource).

add_sink_constraint!(model,source_map,flow,v,t=0)

Constrain flow to be equal to 1 leaving vertex v, time t

add_source_constraint!(model,source_map,flow,v,t=0)

Constrain flow to be equal to 1 leaving vertex v, time t

add_vertex_layer!(G::FlowGraph,incoming::Dict{Int,Vector{Int}},t)

incoming points to _MID vertices. [MID (already added)]–<_BRIDGE>–[START]

adj_mat_from_assignment_mat(sched,assignment_matrix)

Compute an adjacency matrix from an assignment matrix

align_route_plan_tips!(env::MPCCBSEnv)

Extend all paths to match the length of the longest path.

align_schedule_node_times!(env::MPCCBSEnv,sched=get_schedule(env))

Align all node completion times align with the associated robots' paths.

align_stage_results!(primary_results,backup_results)

Align results dicts when they stages aren't aligned (i.e., if the backup planner only runs some of the time.)

align_with_predecessor(node,succ)

Modifies a node to match the information encoded by its predecessor. This is how e.g., robot ids are propagated through an existing operating schedule after assignments (or re-assignments) have been made.

align_with_successor(node,succ)

Modifies a node to match the information encoded by its successor. This is how e.g., robot ids are propagated through an existing operating schedule after assignments (or re-assignments) have been made.

apply_assignment_dict!(sched::OperatingSchedule,assignment_dict)

Make the assignments encoded in assignment_dict.

`backtrack_node(sched::OperatingSchedule,v::Int)`

Find the closest ancestor of v with overlapping RobotIDs.

backtrack_to_previous_node(path,node,tf)

Work backward from tf until finding the beginning of the previous node's path segment. Returns:

• t::Int : the time step at which the previous node's path segment begins
• previous::ScheduleNode : the previous node

break_assignments!(sched::OperatingSchedule,problem_spec::ProblemSpec)

Break all assignments that are eligible for replanning

Check if a node is associated with objectid

Tool for randomly selecting how many robots (and in what configuration)
    should deliver each task.

clear_default_optimizer_attributes!()

Clear the default optimizer attributes.

compute_lower_bound(env,[starts,assigned,dist_mtx,pairs])

Computes a lower bound on makespan for sched::OperatingSchedule by assuming that any robot can be simultaneously assigned to multiple tasks.

Args:

• env SearchEnv
• starts the set of vertices whose outgoing edges are available
• assigned the set of vertices whose incoming edges are already assigned
• dist_mtx encodes the cost of each edge v -> vp as dist_mtx[v,vp]
• pairs specifies eligible edges

compute_route_plan!

Computes all paths specified by the project schedule and updates the solution in the ConstraintTreeNode::node accordingly.

construct_cost_model(solver::AStarSC, args...;kwargs...)

Defines the cost model used by Slack- and Collision-aware A*. This particular setting of cost model is crucial for good performance of A_star, because it encourages depth first search. If we were to replace terms 3-5 with SumOfTravelTime(), we would get worst-case exponentially slow breadth-first search!

construct_heuristic_model(solver,env_graph;kwargs...)

Construct the heuristic model to be used by solver.

construct_operation(spec::ProjectSpec, station_id, input_ids, output_ids, Δt, id=get_unique_operation_id())

construct_partial_project_schedule

Constructs a partial project graph

construct_random_project_spec(M::Int;max_children=1)

Inputs:
    `M` - number of objects involved in the operation
    `max_parents` - determines the max number of inputs to any operation
    `depth_bias` ∈ [0,1] - hyperparameter for tuning depth.
        If `depth_bias` == 1.0, the project_spec graph will always be depth
        balanced (all paths through the tree will be of the same length).
        For `depth_bias` == 0.0, the graph will be as "strung out" as
        possible.

`construct_randomd_task_graphs_problem`

construct_search_env(solver,schedule,env,...)

Constructs a new search env by combining the new schedule with the pre- existing get_route_plan(env). This involves constructing a new cost function that reflects the new schedule structure. TODO: Carry over information about get_cache(search_env)

function construct_search_env(solver, env::SearchEnv, ... )

Construct a new SearchEnv, with costmodel and heuristicmodel defined by the solver type.

`construct_task_graphs_problem`

convert_env_graph_to_undirected(G)

It is necessary to convert the env graph to an undirected graph because the gadget is based on undirected edges. Self-edges also need to be removed, as these are already accounted for in the gadget.

default_milp_optimizer()

Returns the black box optimizer to be use when formulating JuMP models.

default_optimizer_attributes()

Return a dictionary of default optimizer attributes.

evaluate_path_gap(search_env::SearchEnv,path,v)

Returns the gap between a path's length and it's expected length (based on times stored in get_cache(env).t0)

exclude_solutions!(model::JuMP.Model,forbidden_solutions::Vector{Matrix{Int}})

Adds constraints to model such that the solution may not match any solution contained in forbiddensolutions. Assumes that the model contains a variable container called X whose entries are binary and whose dimensions are identical to the dimensions of each solution in forbiddensolutions.

extract_robot_itinerary(sched::OperatingSchedule,id::BotID)

Return the sequence of tasks assigned to id

find_inconsistencies(env::MPCCBSEnv;

Return a dictionary mapping from node id to the amount of time by which the node completion time exceeds the time step at which the transition occurs in the itinerary of the associated robot.

fix_precutoff_nodes!(sched::OperatingSchedule,
    problem_spec::ProblemSpec,t)

Identify all nodes that end before the cutoff time, and change their path spec so that the route planner will not actually plan a path for them.

formulate_assignment_problem(solver,prob;

Returns an assignment problem instance that can be updated (as opposed to being reconstructed from scratch) on each call to update_assignment_problem! prior to being resolved.

formulate_big_milp

Formulate a PCTAPF problem as a giant network flow MILP.

formulate_milp(milp_model::AbstractAssignmentMILP,sched,problem_spec;kwargs...)

Express the TaskGraphs assignment problem as an AbstractAssignmentMILP using the JuMP optimization framework.

Inputs: milpmodel::T <: TaskGraphsMILP : a milp model that determines how the sequential task assignment problem is modeled. Current options are AssignmentMILP, SparseAdjacencyMILP and GreedyAssignment. sched::OperatingSchedule : a partial operating schedule, where some or all assignment edges may be missing. problemspec::ProblemSpec : encodes the distance matrix and other information about the problem.

Keyword Args: optimizer - a JuMP optimizer (e.g., Gurobi.optimizer) cost_model=MakeSpan - optimization objective, currently either MakeSpan or SumOfMakeSpans. Defaults to the costmodel associated with `problemspecOutputs:model::AssignmentMILP` - an instantiated optimization problem

generate_path_spec(spec,node)

Generates a PathSpec struct that encodes information about the path to be planned for node.

Arguments:

• spec::ProblemSpec
• node::T <: AbstractPlanningPredicate

get_active_and_fixed_vtxs(sched::OperatingSchedule,t)

"active" vertices "straddle" the query time t "fixed" vertices finish before the query time t

get_assignment_dict(assignment_matrix,N,M)

Returns dictionary that maps each robot id to a sequence of tasks.

get_assignment_dict(sched::OperatingSchedule)

Return a dictionary mapping robot id to a sequence of object_ids.

get_best_pair(Ao,Ai,cost_func,filt=(a,b)->true)

Return argmin v ∈ Ao, v2 ∈ Ai, cost_func(v,v2) s.t. filt(v,v2) == true

get_delivery_task_vtxs(sched::OperatingSchedule,o::ObjectID)

Return all vertices that correspond to the delivery task (COLLECT → CARRY → DEPOSIT) of object o.

get_duration_vector(spec::ProjectSpec)

Return a vector Δt such that Δt[i] is the amount of time that must elapse before object i can be picked up after its parent operation is performed.

get_env_snapshot(route_plan::S,t)

get_next_node_matching_agent_id(schedule,cache,agent_id)

Return the node_id of the active node assigned to an agent.

get_next_vtx_matching_agent_id(schedule,cache,agent_id)

Return the node_id of the active node assigned to an agent.

get_start_and_end_maps(sched,cache,default=0)

Return dictionaries mapping each node id in schedule to its start and end time

get_objective_expr

Helper for setting the objective function for a milp model

`get_random_problem_instantiation`

Args:
- `N`: number of robots
- `M`: number of delivery tasks
- `robot_zones`: list of possible start locations for robots
- `pickup_zones`: list of possible start locations for objects
- `dropoff_zones`: list of possible destinations for objects

get_sF(milp_model::AbstractAssignmentMILP)

Return an a vector of final object locations.

get_source_map(G::FlowGraph,env_graph,TMAX)

Return a source map such that source_map[v][t] points to the corresponding _START vertex in the gadget graph.

get_valid_robot_ids(sched::OperatingSchedule,n_id::AbstractID)

Returns vector of all robot ids associated with the schedule node referenced by n_id.

GreedyAssignment maintains three sets: The "satisfied set" C, the "required incoming" set Ai, and the "available outgoing" set Ao.

At each step, the algorithm identifies the nodes v1 ∈ Ai and v2 ∈ Ao with shortest "distance" (in the context of OperatingSchedules, this distance refers to the duration of v1 if an edge v1 → v2 is added) and adds an edge between them. The distance corresponding to an ineligible edge is set to Inf.

After adding the edge, the algorithm sweeps through a topological ordering of the vertices and updates C, Ai, and Ao. In order for v to be placed in C, v must have enough incoming edges and all of v's predecessors must already be in C. In order to be added to Ai, v must have less than the required number of incoming edges and all of v's predecessors must already be in C. In order for v to be added to Ao, v must have less than the allowable number of outgoing edges, and must be in C.

handle_disturbance!(solver,prob,env,d::DroppedObject,t,env_state=get_env_state(env,t))

Returns a new SearchEnv with a modified OperatingSchedule. The new schedule replaces the previous delivery task (OBJECT_AT(o,old_x) → COLLECT → CARRY → DEPOSIT) with a new CleanUpBot delivery task (OBJECT_AT(o,new_x) → CUB_COLLECT → CUB_CARRY → CUB_DEPOSIT). It is assumed that the time t corresponds to a moment when the object referred to by d.id is being CARRIED.

initialize_multi_goal_route_plan(sched::OperatingSchedule,cost_model)

Init route plan with MState as the state type.

isolate_delivery_task_vtxs(sched,o,vtxs=get_delivery_task_vtxs(sched,o))

Returns:

• incoming: a set of all incoming Action ScheduleNodes
• outgoing: a set of all outgoing Action ScheduleNodes
• op: the target Operation

isps_queue_cost(solver::ISPS,sched::OperatingSchedule,v::Int)

Allow prioritization of nodes flagged for backtracking.

compute_lower_bound(_sched,dist_func,

Compute a (potentially very loose) lower bound on the makespan of a schedule

matches_node_type(::A,::Type{B}) where {A<:AbstractPlanningPredicate,B}

Returns true if {A <: B}

multi_goal_queue_priority(solver,env::MPCCBSEnv,id::BotID)

Compute the priority (determines the order in which paths will be computed) for the itinerary of robot id.

pctapf_problem_1

Optimal MakeSpan = 5 Optimal SumOfMakeSpans = 5

pctapf_problem_10(;cost_function=MakeSpan(),verbose=false,Δt_op=0,Δt_collect=[0,0,0,0,0,0],Δt_deposit=[0,0,0,0,0,0])

Motivation for backtracking in ISPS The makespan optimal solution is T = 6. However, the optimistic schedule will always prioritize robot 2 over robot 1, causing robot 1 to get stuck waiting for 3, 4, and 5 to pass all in a row. This creates an unavoidable delay in the schedule, leading to a +1 delay that will not be caught without backtracking in ISPS. Hence, the solver will return a solution with T = 7.

pctapf_problem_11

Requires collaborative transport: Robots 1 and 2 transport object 1 while robot 3 transports object 2. Robot 3 will need to move over to let the other robots pass.

pctapf_problem_12(;

Robot 1 will plan a path first, but then that path will need to be extended by one time step because robot 2 will get delayed by robot 3, which is on the critical path.

pctapf_problem_13

Same as pctapf_problem_12, except that there is a 4th robot who must collect object 1 with robot 1.

pctapf_problem_15(;cost_function=SumOfMakeSpans(),verbose=false)

Trying to stress the multi goal algorithm

pctapf_problem_2(;cost_function=SumOfMakeSpans(),verbose=false)

In this problem robot 1 will first do [1-9-17], then [17-21-35] robot 2 will do [4-12-32]. The key thing is that robot 1 will need to wait until robot 2 is finished before robot 1 can do its second task.

Optimal paths: Optimal MakeSpan = 8 Optimal SumOfMakeSpans = 8

pctapf_problem_3(;cost_function=SumOfMakeSpans(),verbose=false,Δt_op=0,Δt_collect=[0,0,0,0],Δt_deposit=[0,0,0,0])

In this problem robot 2 will need to yield to let robot 1 through. First operation: robot 1 does [2-2-30] Second operation: robot 1 does [30-30-32] robot 2 does [5-7-8] Third operation: robot 2 does [8-12-16]

pctapf_problem_4(;cost_function=SumOfMakeSpans(),verbose=false)

In this problem the cost of the task assignment problem is lower than the true cost (which requires that one of the robots is delayed by a single time step) First operation: robot 1 does [2-2-8] robot 2 does [4-4-6]

pctapf_problem_5(;cost_function=SumOfMakeSpans(),verbose=false)

In this problem the robots try to pass through each other in such a way that an edge conflict is generated.

First operation: robot 1 does [3-11] robot 2 does [15-7]

pctapf_problem_6(;cost_function=SumOfMakeSpans(),verbose=false,Δt_op=1,Δt_collect=[0,0,0],Δt_deposit=[0,0,0])

Identical to pctapf_problem_2, but process time is non-zero. In this problem robot 1 will first do [1-5-9], then [9-13-17] robot 2 will do [4-8-32]. The key thing is that robot 1 will need to wait until robot 2 is finished before robot 1 can do its second task

pctapf_problem_7(;cost_function=SumOfMakeSpans(),verbose=false,Δt_op=0,Δt_collect=[0,4,0],Δt_deposit=[0,0,0])

Robot 2 will have to sit and wait at the pickup station, meaning that robot 1 will have to go around if robot 2 is on the critical path

pctapf_problem_8(;cost_function=SumOfMakeSpans(),verbose=false,Δt_op=0,Δt_collect=[0,0,0,0],Δt_deposit=[0,0,0,0])

Two-headed project. Robot 1 does the first half of the first head, and robot 2 handles the first half of the second head, and then they swap. Optimal MakeSpan = 8 Optimal SumOfMakeSpans = 16

pctapf_problem_9(;cost_function=SumOfMakeSpans(),verbose=false,Δt_op=0,Δt_collect=[0,0],Δt_deposit=[0,0])

Project with station-sharing. Station 5 needs to accessed by both robots for picking up their objects.

pctapf_problem_multi_backtrack(;cost_function=MakeSpan(),verbose=false,Δt_op=0,Δt_collect=[0,0,0,0,0,0],Δt_deposit=[0,0,0,0,0,0])

Motivation for backtracking in ISPS The makespan optimal solution is T = 8, and requires that robots 2,3, and 4 allow robot 1 to pass before them. However, the slack-based priority schedme of ISPS will always prioritize robot 2, 3, and 4 over robot 1, causing robot 1 to get stuck waiting for 5, 6, and 7 to pass all in a row. Without backtracking, CBS+ISPS will eventually return a plan with makespan T = 9. With recursive backtracking (not just a single pass)

`plan_next_path`

plan_path!

Computes next path specified by the project schedule and updates the
solution in the ConstraintTreeNode::node accordingly.

plan_route!

Compute a route plan that corresponds to the OperatingSchedule. Arguments:

• solver
• schedule
• search_env

Outputs:

• A SearchEnv the contains a valid solution

post_process_problem_type(solver,prob)

An overridable helper function for potentially modifying prob based on solver. Default behavior is to return prob with no changes.

add start_time, completion_time, and makespan for each stage

preprocess_project_schedule(sched)

Returns information about the eligible and required successors and predecessors of nodes in sched

Arguments:

• sched::OperatingSchedule

Outputs:

• missing_successors
• missing_predecessors
• neligiblesuccessors
• neligiblepredecessors
• nrequiredsuccessors
• nrequiredpredecessors
• upstream_vertices
• nonupstreamvertices

TODO: OBJECTAT nodes should always have the properties that `indegree(G,v) == nrequiredpredecessors(v) == neligiblepredecessors(v)outdegree(G,v) == nrequiredsuccessors(v) == neligible_successors(v)` Not sure if this is currently the case. UPDATE: I believe this has already been addressed by making each object come from an initial operation.

process_schedule(schedule::P) where {P<:OperatingSchedule}

Compute the optimistic start and end times, along with the slack associated with each vertex in the schedule. Slack for each vertex is represented as a vector in order to handle multi-headed projects.

Args:

• schedule::OperatingSchedule
• [OPTIONAL] t0::Vector{Int}: default = zeros(Int,nv(schedule))
• [OPTIONAL] tF::Vector{Int}: default = zeros(Int,nv(schedule))

prune_schedule(sched::OperatingSchedule,
    problem_spec::ProblemSpec,t)

remove nodes that don't need to be kept around any longer

random_pcmapf_def(env,config;objective=MakeSpan(),solver,kwargs...)

Return a random SimplePCMAPFDef. Same arguments for config as in random_multihead_pctapf_def.

instantiate_random_pctapf_def(env,config)

Instantiate a random PC_TAPF problem based on the parameters of config.

instantiate_random_repeated_pctapf_problem(env,config)

Instantiate a random RepeatedPC_TAPF problem based on the parameters of config.

regenerate_path_specs!(solver,env)

Recompute all paths specs (to account for changes in the env_graphs that will be propagated to the ProblemSpec's distance function as well.)

replace_in_schedule!(schedule::OperatingSchedule,path_spec::T,pred,id::ID) where {T<:PathSpec,ID<:AbstractID}

Replace the ScheduleNode associated with id with the new node pred, and the accompanying PathSpec path_spec.

replanning_config_1

Returns a vector of config dictionaries, which can be used to generate random problem instances for profiling.

replanning_problem

Constructs a replanning problem, consisting of robot initial conditions, an environment, and a sequence of project requests scheduled to arrive in the factory at regular intervals. Args:

• r0: list of integers specifying the start locations of the robots

• defs: a list of tuples, where each tuple is of the form

  ([start_1=>goal_1, ...], [([inputs],[outputs]),...])

  where the start=>goal pairs define the start and end points for each object to be delivered, and the ([inputs],[outputs]) pairs define the objects that go in and out of each operation.

• env_graph: the environment (presumably a GridFactoryEnvironment)

Outputs:

• requests: a sequence of ProjectRequests
• problem_spec: a ProblemSpec
• robotICs: Robot initial conditions `ROBOTAT`
• env_graph: the environment

The robot should do better if it handles the single task in the second
project prior to working on the third task of the first project.

Just intended to take longer so that the tests pass even if Julia hasn't
finished warming up yet.

`reset_cache!(cache,sched)`

Resets the cache so that a solution can be repaired (otherwise calling
low_level_search!() will return immediately because the cache says it's
complete)

Helper to reset the solution in a constraint node between re-runs of ISPS

resources_reserved(node)

Identifies the resources reserved by a particular node for its duration. For example, resources_reserved(node::COLLECT) = AbstractID[get_location_id(node)]

robot_ids_match(node,node2)

Checks if robot_ids match between the nodes

robot_tip_map(sched::OperatingSchedule)

Returns a Dict{RobotID,AbstractID} mapping RobotID to the terminal node of the sched corresponding to the robot's last assigned task.

Identifies the nodes v ∈ Ai and v2 ∈ Ao with the shortest distance D[v,v2].

select_trim_points(env,inconsistencies)

Choose locations at which to prune agent paths. Each path will be trimmed at the completion time of the latest consistent node in the agent's itinerary.

set_default_milp_optimizer!(optimizer)

Set the black box optimizer to be use when formulating JuMP models.

set_default_optimizer_attributes!(vals)

Set default optimizer attributes. e.g. set_default_optimizer_attributes!(Dict("PreSolve"=>-1))

solve_assignment_problem!(solver,model,prob)

Solve the "assignment problem"–i.e., the relaxation of the full PC-TAPF problem wherein we ignore collisions–using the algorithm encoded by solver.

solve_with_multi_goal_solver!(solver,pc_mapf,

Compute a consistent solution to the PC_MAPF problem using the "multi-goal" appoach.

splice_schedules!(sched::P,next_sched::P) where {P<:OperatingSchedule}

Merge next_sched into sched

split_active_vtxs!(sched::OperatingSchedule,
    problem_spec::ProblemSpec,t;

Split all GO nodes that "straddle" the cutoff time.

split_node(node::N,x::LocationID)

Creates two new nodes of type N, where the destination of the first node and the starting location of the second node are both set to x.

stitch_disjoint_node_sets!(sched,incoming,outgoing)

Finds and adds the appropriate edges between two sets of nodes. It is assumed that size(incoming) == size(outgoing), that each node in incoming has exactly one feasible successor in outgoing, and that each node in outgoing has exactly one feasible predecessor in incoming.

tighten_gaps!(solver, pc_mapf, env::SearchEnv, constraint_node::ConstraintTreeNode)

If any path ends before it should (based on times stored in get_cache(env)), recomputes the path segment for the final node in that line.

trim_route_plan(search_env, route_plan, T)

Construct a trimmed route_plan that stops at a certain time step

update_assignment_problem!(solver, assignment_problem)

A helper method for updating an instance of an assignment problem. In the case of MILP-based models, this method simply excludes all previous solutions by adding new constraints on the assignment/adjacency matrix.

update_backtrack_list!(solver::ISPS,sched,id,val=false)

Add to backtrack_list.

`update_env!`

`v` is the vertex id

update_planning_cache!(solver,env)

Update cache continually. After a call to this function, the start and end times of all schedule nodes will be updated to reflect the progress of active schedule nodes (i.e., if a robot had not yet completed a GO task, the predicted final time for that task will be updated based on the robot's current state and distance to the goal). All active nodes that don't require planning will be automatically marked as complete.

update_planning_cache!(solver,env,v,path)

update_project_schedule!(solver,milp_model::M,sched,problem_spec,
    adj_matrix) where {M<:TaskGraphsMILP}

Args:

• milp_model <: TaskGraphsMILP
• sched::OperatingSchedule
• problem_spec::ProblemSpec
• adjmatrix : an adjacencymatrix or (in the case where milp_model::AssignmentMILP), an assignment matrix

Adds all required edges to the schedule graph and modifies all nodes to reflect the appropriate valid IDs (e.g., Action nodes are populated with the correct RobotIDs) Returns false if the new edges cause cycles in the project graph.

update_project_schedule!

Args:

• solver
• sched
• adjmatrix - adjacencymatrix encoding the edges that need to be added to the project schedule

Adds all required edges to the project graph and modifies all nodes to reflect the appropriate valid IDs (e.g., Action nodes are populated with the correct RobotIDs) Returns false if the new edges cause cycles in the project graph.

update_route_plan!()

update_schedule_times!(sched::OperatingSchedule,frontier::Set{Int},local_only=true)

Compute start and end times for all nodes in frontier and their descendants. If local_only == true, descendants of nodes with unchanged final time will not be updated.

update_schedule_times!(sched::OperatingSchedule)

Compute start and end times for all nodes based on the end times of their inneighbors and their own durations.

warmup(loader::TaskGraphsProblemLoader,solver_config,problem_dir,dummy_path = "dummy_path")

Do a small dry run of run_profiling(loader,solver_config,problem_dir) to ensure that all code is fully compiled before collecting results.

write_pcmapf_from_pctapf!(loader,solver_config,pcmapf_dir)

Copy assignments from PCTAPF or PCTA results into problems in pcmapf_dir.

write_problem(loader::TaskGraphsProblemLoader,problem_def,prob_path,env_id="")

Write a problem that can later be loaded and solved.