Core Types

OBJECT_AT <: AbstractPlanningPredicate

Encodes the location and shape of the object with id o

BOT_AT <: AbstractPlanningPredicate

Encodes the location of robot with id r

BOT_COLLECT <: AbstractRobotAction

Encodes the event "robot r collects object o from x

BOT_DEPOSIT <: AbstractRobotAction

Encodes the event "robot r collects object o from x

TEAM_ACTION{R<:AbstractRobotType,A<:AbstractRobotAction{R}}

For collaborative tasks.

[GO, ...] -> TEAMCOLLECT -> TEAMCARRY -> TEAM_DEPOSIT -> [GO, ...]

ProjectSpec <: AbstractCustomNDiGraph{Union{OBJECT_AT,Operation},AbstractID}

Encodes a set of operations and the prescribed initial and final locations of the objects that form the inputs and outputs of those operations.

Elements:

• all standard fields of a concrete GraphUtils.CustomNDiGraph type
• initialconditions::Dict{ObjectID,OBJECTAT}
• finalconditions::Dict{ObjectID,OBJECTAT}

ProblemSpec{G}

Encodes the the relaxed PC-TAPF problem that ignores collision-avoidance constraints.

Elements:

• D::T - a distance matrix (or environment) that implements get_distance(D,x1,x2,args...)
• cost_function::F - the optimization objective (default is SumOfMakeSpans)
• Δt_collect::Dict{ObjectID,Int} # duration of COLLECT operations
• Δt_deposit::Dict{ObjectID,Int} # duration of DEPOSIT operations

ScheduleNode{I<:AbstractID,V<:AbstractPlanningPredicate}

The node type of the OperatingSchedule graph.

OperatingSchedule

Encodes discrete events/activities that need to take place, and the precedence constraints between them. Each ScheduleNode has a corresponding vertex index and an AbstractID. An edge from node1 to node2 indicates a precedence constraint between them.

SearchEnv{C,H,S} <: GraphEnv{State,Action,C}

Contains all of the information needed to fully define PC_TAPF and related problems.

EnvState

Reflects the state of the SearchEnv environment at a given time step.

AbstractPC_MAPF

An abstract type of which all Precedence-Constrained Multi-Agent Path-Finding problems are concrete subtypes.

AbstractPC_TAPF <: AbstractPC_MAPF

An abstract type of which all Precedence-Constrained Multi-Agent Task Assignment and Path-Finding problems are concrete subtypes.

PC_TAPF

Precedence-Constrained Multi-Agent Task Assignment and Path-Finding problem.

PC_TA

Precedence-Constrained Multi-Agent Task Assignment problem (no route planning).

PC_MAPF

A precedence-constrained multi-agent path-finding problem (no task assignment).

C_PC_MAPF

A collaborative precedence-constrained multi-agent path-finding problem. All agents have assigned tasks, there are precedence constraints between tasks, and some tasks must be done in teams.

C_PC_TAPF

Defines an instance of a Collaborative Precedence-Constrained Multi-Agent Task Assignment and Path-Finding problem, where agents must sometimes transport objects in teams.

RepeatedPC_TAPF{S<:SearchEnv} <: RepeatedAbstractPC_TAPF

Encodes a Repeated PCTAPF problem. Usage: `prob = RepeatedPCTAPF(env::SearchEnv,requests::Vector{ProjectRequest})`

ProjectRequest

Encodes a "request" that arrives in the factory command center. t_request encodes the time at which the request reaches the command center t_arrival is the time at which the project materials will be available

TODO more flexibility with t_arrival by allowing different materials to arrive at different times

ReplannerModel

Abstract type. Concrete subtypes currently include DeferUntilCompletion, ReassignFreeRobots, MergeAndBalance, Oracle, NullReplanner

ReplannerConfig

Stores parameters for configuring an instance of ReplannerModel. Fields:

• real_time::Bool - if true, adjust solver runtime limits to meet real time operation constraints.
• timeout_buffer::Float64 - defines the minimum amount of time that must be for replanning the route
• routeplanningbuffer::Float64 - defines the minimum amount of time that must be allocated for replanning the route
• commit_threshold::Float64 - defines where the ``freeze time'', or the time step from which the solver may change the existing plan.

DeferUntilCompletion <: ReplannerModel

Allow work to begin on the new project only after all other work is completed.

ReassignFreeRobots   <: ReplannerModel

Allow robots to begin working on the new project as soon as they have finished their current assignments.

MergeAndBalance      <: ReplannerModel

Allow replanning from scratch for all assignments and routes except for those that will take place

ConstrainedMergeAndBalance <: ReplannerModel

Identical to MergeAndBalance, except that the replanning commit time may be pushed farther into the future to limit the total problem size at each replanning stage.

ReplanningProfilerCache

Stores information during replanning

• schedule - maintains (non-pruned) overall project schedule
• stage_ids - maps id of each node in schedule to stage index
• stage_results - vector of result dicts
• features - vector of ::FeatureExtractors to extract after each stage
• final_features - vector of ::FeatureExtractors to extract after final stage

FullReplanner{R,S}

Wrapper for a ReplannerModel and a PC_TAPF solver, as well as a ReplanningProfilerCache.

ReplannerWithBackup{A,B}

Consists of a primary and a backup solver. The backup solver is supposed to be fast–it computes a "fallback" plan in case the primary solver fails to find a good enough solution before time out.

TaskGraphsMILP

Concrete subtypes of TaskGraphsMILP define different ways to formulate the sequential assignment portion of a PC-TAPF problem.

TaskGraphsMILPSolver

Wrapper for MILP solver for assignment problem.

AssignmentMILP <: TaskGraphsMILP

Used to formulate a MILP where the decision variable is a matrix X, where X[i,j] = 1 means that robot i is assigned to delivery task j. The dimensionality of X is (N+M) × M, where N is the number of robots and M is the number of delivery tasks. the last M rows of X correspond to "dummy robots", i.e. the N+jth row corresponds to "the robot that already completed task j". The use of these dummy robot variables allows the sequential assignment problem to be posed as a one-off assignment problem with inter-task constraints.

SparseAdjacencyMILP <: TaskGraphsMILP

Formulates a MILP where the decision variable is a sparse adjacency matrix X for the operating schedule graph. If X[i,j] = 1, there is an edge from node i to node j. Experiments have shown that the sparse matrix approach leads to much faster solve times than the dense matrix approach.

GreedyAssignment{C,M} <: TaskGraphsMILP

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.

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

Express the TaskGraphs assignment problem as an AssignmentMILP 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

AStarSC

Low-level path planner that employs Slack-and-Collision-Aware A*. Fields:

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

ISPS

Path planner that employs Incremental Slack-Prioritized Search.

NBSSolver{A,P}

A hierarchical PC-TAPF solver with an assignment level and a path-planning level. The solver works by alternating between assignment and path-planning until the optimality gap between the lower bound (from task assignment) and the lower bound (from path planning) disappears. The input to the assignment problem is the full PC-TAPF problem specification. The output of the assignment problem is a valid OperatingSchedule–that is, an operating schedule wherein all assignments have been made in a legal way. The input to the route planner is the PC-TAPF problem spec along with the OperatingSchedule that comes from the assignment solution.

TaskGraphsProblemLoader{T}

Helper cache for loading problems of type T

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

Write a problem that can later be loaded and solved.

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

Currently only impemented for PCTAPF and PCTA

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

Run profiling with a TaskGraphsProblemLoader.

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.