Source-linked AI summary
Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints
Shushman Choudhury, Jayesh K. Gupta, Mykel J. Kochenderfer, Dorsa Sadigh, Jeannette Bohg
TL;DR
The paper addresses dynamic multi-robot allocation with uncertain task completion and time-window constraints. SCoBA hierarchically combines single-agent policy-tree planning with multi-agent conflict resolution. It is optimal in expectation and complete under stated assumptions, while outperforming baselines across two simulated domains.
Problem
Dynamic multi-robot allocation must coordinate tasks that arrive online despite uncertain execution and temporal constraints.
Method
SCoBA uses dynamic programming with single-agent policy trees and upper-level conflict resolution to produce coordinated allocations.
Results
SCoBA is optimal in expectation and complete under mild assumptions, outperforms baselines, competes strongly with an oracle, and scales across agents and tasks.
Takeaways & Limitations
The hierarchical design supports online planning and execution for uncertain multi-robot allocation in conveyor-belt and multi-drone delivery simulations.
Abstract
from arXiv · showhide
We consider the problem of dynamically allocating tasks to multiple agents under time window constraints and task completion uncertainty. Our objective is to minimize the number of unsuccessful tasks at the end of the operation horizon. We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination and addresses them in a hierarchical manner. The lower layer computes policies for individual agents using dynamic programming with tree search, and the upper layer resolves conflicts in individual plans to obtain a valid multi-agent allocation. Our algorithm, Stochastic Conflict-Based Allocation (SCoBA), is optimal in expectation and complete under some reasonable assumptions. In practice, SCoBA is computationally efficient enough to interleave planning and execution online. On the metric of successful task completion, SCoBA consistently outperforms a number of baseline methods and shows strong competitive performance against an oracle with complete lookahead. It also scales well with the number of tasks and agents. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
I. INTRODUCTION
The paper addresses dynamic multi-robot allocation under uncertainty, temporal constraints, and online task arrivals. SCoBA separates individual sequential planning from multi-agent coordination through a hierarchical allocation framework.
- Motivation: Multi-robot allocation combines combinatorial optimization with uncertainty, dynamic task arrivals, and time-window constraints.Planning must account for horizons and spatio-temporal relationships among tasks.
- Motivation: Existing approaches often simplify either task planning or multi-agent coordination because the joint problem is computationally intractable.The paper identifies sequential planning under uncertainty and coordinating multi-agent decisions as the central algorithmic challenges.
- Contributions: SCoBA decouples the problem hierarchically: a lower layer plans for individual agents, while an upper layer resolves conflicts among their decisions.The lower layer uses dynamic programming on policy trees, and the upper layer applies conflict-resolution logic.
- Contributions: SCoBA is optimal in expectation and complete under mild assumptions.These guarantees are stated as formal contributions of the hierarchical algorithm.
- Evaluation: SCoBA outperforms four baseline methods on successful task execution and remains competitive with an oracle using complete lookahead.The evaluations cover conveyor-belt robot arms and city-scale multi-drone delivery, while also examining scalability with agents and tasks.
III. PROBLEM FORMULATION
The formulation models agents assigning uncertain-duration tasks within agent-specific service windows over a finite horizon. It minimizes expected penalties for tasks that remain unsuccessful at the horizon.
- Formulation: The problem contains N agents, K tasks, and a T-step planning horizon with agent-task service windows W_nk.Each task can be attempted only within its valid time window.
- Uncertainty: Task duration uncertainty is represented by τ_nk(t), the probability that agent n completes task k within t time-steps.The cumulative distribution is assumed known as part of the problem specification and is domain-dependent.
- Uncertainty: Time windows and completion distributions jointly upper-bound the probability of completing a task successfully.The formulation explicitly combines temporal feasibility with uncertain task duration.
- Objective: The objective minimizes expected cumulative penalties for tasks that remain incomplete at the end of the horizon.The paper assumes equal task importance, yielding the unweighted tardy-jobs penalty.
- Objective: The allocation policy maps agents to tasks and attempt times, with future attempts depending on earlier stochastic execution outcomes.Each agent can attempt only one task at a time.
- Scope: The discrete-time rolling-horizon formulation targets high-level allocation while avoiding continuous-time trajectory-planning complexity.Underlying time-constrained trajectory planning is treated as a separate layer with established models and methods.
IV. HIERARCHICAL MULTI-ROBOT TASK ALLOCATION
SCoBA addresses sequential planning under uncertain task completion and multi-agent coordination in two layers. Individual policy trees are optimized by dynamic programming, after which coordinated allocation decisions are obtained through conflict resolution.
- Hierarchical architecture: SCoBA uses a two-layer architecture to separate individual stochastic planning from multi-agent allocation coordination.The joint planning problem is computationally prohibitive in large settings, motivating the hierarchical design.
- Individual planning: For each agent, the lower layer constructs a policy tree over current tasks, time windows, and completion uncertainty.The tree represents alternative task-attempt decisions and stochastic outcomes over the planning horizon.
- Individual planning: The low-level approximation has each agent attempt a task as soon as possible and observe its outcome at the end of the task window.This treats tasks as discrete events rather than extended temporal activities.
- Policy-tree construction: The policy tree is updated at task-window starts, finishes, and successful-task downtime events.At a window start, the agent branches between attempting and leaving the task; outcome nodes represent success or failure.
- Dynamic programming: Dynamic programming assigns expected values to outcome branches and minimum values to decision branches.For outcome siblings, the parent value is p·V(Fail) + (1−p)·V(Succ); decision nodes choose the lower-valued child.
- Dynamic programming: Following minimum-value children from the root yields the individual policy and identifies the next task assigned to the agent.The root value represents the agent’s minimum expected penalty over the planning horizon.
B. High-Level: Multi-Agent Coordination
SCoBA hierarchically coordinates individually optimized agent policies by resolving allocation conflicts through best-first search on a constraint tree. Under stated assumptions, it is optimal in expectation and complete when a valid allocation exists.
- Motivation: Independent policy-tree searches can produce conflicting allocations, so naïve tie-breaking may yield arbitrarily poor global allocations.SCoBA addresses sequential planning under uncertainty separately from multi-agent coordination.
- Constraint-tree coordination: SCoBA builds a binary constraint tree from conflicts between individual-agent allocations and searches it using allocation cost.A constraint excludes a task from an agent’s policy-tree search; each node stores constraints, a feasible allocation, and its summed expected penalty.
- Constraint-tree coordination: Best-first search returns the first conflict-free allocation, while child generation recomputes policy search only for the agent receiving the new task constraint.In the illustrated conflict over task k1, both children are conflict-free and the lower-cost allocation, 2.6, is returned.
- Algorithm: SCoBA initializes individual policies at the constraint-tree root, expands the minimum-cost node, and returns its allocation when no conflicts remain.Conflicting nodes generate children by adding agent-task constraints and reinserting the resulting allocations into the open list.
- Guarantees: Under assumptions of no online task additions, full-horizon search, and completion determined at window end, SCoBA is optimal in expectation and complete.Completeness means that if a valid allocation exists, SCoBA returns one.
- Efficiency: Coordination graphs reduce coordination to dependent agents; for the conveyor belt, the graph is a directed chain ordered along the arms.Agents without an edge cannot have conflicting allocations, and directed graphs permit topological-order coordination.
V. EVALUATION
The evaluation measures unsuccessful-task penalty and computational scalability in simulations of conveyor-belt pick-and-place and multi-drone delivery. Experiments use Julia on a 16 GiB RAM machine with a 6-core 3.7 GHz CPU.
- Metrics: The primary evaluation metric is accumulated penalty for unsuccessful tasks, with scalability assessed by computation time as task and agent counts increase.Both metrics are evaluated in the two robotics-inspired domains.
- Domains: The experiments cover conveyor-belt pick-and-place and on-demand multi-drone delivery dispatch.The simulations are conducted in Julia on a 16 GiB RAM machine with a 6-core 3.7 GHz CPU.
A. Baselines for Unsuccessful Task Penalty
SCoBA is evaluated against scheduling, reactive assignment, reinforcement-learning, and Monte-Carlo tree-search baselines on unsuccessful-task penalty and scalability. Conveyor-belt experiments vary grasp uncertainty, belt speed, object arrivals, and task load, with results averaged over 100 trials where specified.
- Baselines: The baselines include EDD, Hungarian assignment, Q-Learning, and MCTS, spanning scheduling, reactive assignment, sequential decision-making, and Monte-Carlo tree search.EDD uses nearest deadlines, while Hungarian weights agent-task edges by successful-completion probability.
- Scenario parameters: Grasp uncertainty is modeled as a Bernoulli process with arm-specific success probability p_i, and performance is expected to improve as p_i increases.The cumulative success distribution is derived from this model.
- Scenario parameters: Increasing belt speed reduces effective time windows, while successful execution incurs Δt = 2 s of arm downtime.The experiments expect performance to degrade as belt speed increases.
- Evaluation setup: 100 trials with T = 500 time-steps per trial are used for the unsuccessful-task fraction comparison in Figure 5.The metric is the fraction of unsuccessful tasks, interpreted as objects missed.
- Results: SCoBA considerably outperforms the other baselines across all conveyor-belt settings.Its performance changes in the expected direction as problem parameters vary, including more missed objects with higher new-object probability.
- Scalability: SCoBA’s single-arm policy-tree search has roughly quadratic tree-node growth and roughly cubic computation-time growth with the number of objects.Reported wall-clock times are described as reasonable, and Table II characterizes the search as scalable for objects in an arm’s workspace.
C. Drone Delivery: Experiments and Results
The drone-delivery experiments vary depot coverage, drone-to-depot ratios, request arrivals, and uncertain travel times while measuring late deliveries. SCoBA is evaluated across these settings using repeated trials.
- Scenario setup: The city-scale domain dispatches drones from up to five depots, with 10 km maximum flight range constraining feasible deliveries.Depot placement and the drone-to-depot ratio affect dispatch coverage.
- Evaluation: The primary evaluation metric is the fraction of late package deliveries, averaged over 100 trials of 100 time-steps.SCoBA is compared with EDD, Hungarian, and MCTS baselines.
- Scenario setup: New requests arrive probabilistically, with delivery windows uniformly sampled between 15 and 30 minutes.Each scenario begins with roughly 1.5 packages per drone.
- Uncertainty model: Travel times use deterministic depot-to-package estimates with uncertainty modeled by a finite-support Epanechnikov distribution.The distribution is centered on the reference travel-time estimate, with scale tied to that estimate.
1) Unsuccessful Task Penalty:
The drone-delivery results compare SCoBA with baselines across coverage and request-rate settings using late-delivery penalties. SCoBA is generally strongest, while computation remains reasonable but can vary with conflict density.
- Unsuccessful Task Penalty: SCoBA is generally best across drone-delivery settings, except with 5 depots, 15 drones, and request probability 1.0, where MCTS is slightly better.The comparison uses the fraction of late package deliveries as the outcome.
- Unsuccessful Task Penalty: More drones per depot appears more influential than the number of depots for coverage performance.The reported scenarios contrast fewer depots with higher drone-to-depot ratios against more depots with lower ratios.
- Computation time: SCoBA computation times are reported as means and standard errors over 50 trials for each drone-delivery setting.The experiments vary drones, depots, and currently available package requests; all table times are in seconds.
- Computation time: Computation time is generally reasonable for minute- and hour-scale operations but can have disproportionately high mean and variance when high-level conflicts increase.This behavior is identified as a known property of Conflict-Based Search.
- Overall findings: Across two realistic domains, SCoBA shows strong competitive performance against an oracle, outperforms baselines, and scales with agents and tasks.The reported domains are conveyor-belt manipulation and city-scale multi-drone delivery.
APPENDIX OPTIMALITY AND COMPLETENESS PROOFS
The appendix establishes SCoBA’s expected optimality and completeness by combining optimal single-agent policy-tree search with conflict-based multi-agent coordination. These guarantees hold under stated finite-horizon and task-arrival assumptions.
- Optimality: Under no online task additions, full-horizon tree search, and end-of-window completion, SCoBA minimizes expected incomplete tasks.This is the stated optimality condition for the algorithm.
- Optimality: The low-level routine uses exhaustive dynamic programming with forward tree search to obtain an expectation-optimal policy for each finite-horizon single-agent MDP.The expectation is over uncertain action outcomes.
- Optimality: SCoBA’s multi-agent objective decomposes into the sum of individual-agent expected penalties because conflict resolution assigns each task to at most one agent.This decomposition supplies the second condition needed to inherit Conflict-Based Search optimality.
- Optimality: Therefore, SCoBA is optimal in expectation under the stated assumptions.The proof combines low-level policy optimality with the decomposed multi-agent objective.
- Completeness: Under the same assumptions, SCoBA is complete: whenever a conflict-free allocation exists, it returns one.The proof uses a finite constraint tree and systematic best-first search.
Conveyor Belt Task Generation Process
The conveyor-belt task generator mirrors a virtual assembly line to create real pick-and-place tasks, while enabling evaluation against an oracle with perfect future information.
- Task generation: The generator reflects the belt setup in space and time, using virtual arms to place objects that later appear as real objects.The virtual belt crossing causes virtual objects to appear as new real objects.
- Perfect allocation: A perfect allocation strategy exists when there is no uncertainty because the virtual setup itself specifies successful arm-to-object assignments.This strategy assigns each real object according to the corresponding virtual form’s generating arm.
- Practical access: Obtaining that perfect strategy in practice would require complete access to the virtual generator for each problem instance.
- Oracle evaluation: The oracle achieves full success on generated sequences, so competitive performance reduces to the evaluated method’s fraction of unsuccessful tasks.The oracle is an upper bound based on access to all future information.
Baseline Implementation Details
The baselines use different implementations and input interfaces, making timing comparisons informative but not fully equivalent. SCoBA’s timing reflects sequential policy-tree planning, whereas other methods often restrict or precompute their decision spaces.
- Implementation: MCTS uses EDD rollouts, while Q-Learning uses ϵ-greedy exploration with a 0.01 learning rate over 100000 training steps.MCTS and Q-Learning are implemented through POMDPs.jl.
- Timing caveat: Baseline timing comparisons are not apples-to-apples because domain-specific input interfaces impose different restrictions on problem size.
- Timing objective: SCoBA’s computation time is treated as a satisficing requirement rather than an optimization objective, with reasonableness judged by domain needs.
- Conveyor timing: In the conveyor domain, Hungarian is much faster than SCoBA because it matches locally rather than planning sequentially across all objects.Its effective object count per arm is about one third of the total for three arms.
- Conveyor timing: MCTS takes 0.1 s per action with 100 iterations and search depth 20, using a belt-slot action space independent of object count.
- Baseline scope: EDD does not plan jointly, while tabular Q-Learning precomputes its policy offline and looks it up online.Both methods use action spaces based on discretized belt slots rather than the number of objects.
- Drone timing: In drone delivery, Hungarian is orders of magnitude faster than SCoBA, while MCTS’s action space grows with the number of tasks.