Source-linked AI summary
Model-Based Reinforcement Learning for Heterogeneous Multi-Robot Task Assignment Under Distribution Shifts
Daniel Garces, Sara Castro, Adrian Haimovich, Byron Crowe, Stephanie Gil
TL;DR
The paper studies online assignment and scheduling for heterogeneous robot teams serving scheduled and real-time requests under uncertain, shifting demand. It proposes prediction-aware adaptive rollout that uses sampled forecasts without committing to unobserved requests, while adapting forecast influence and revising unstarted assignments. In hospital-floor experiments, the method achieved near-complete service and reduced wait times, especially in the tail, against several baselines.
Problem
Online heterogeneous robot scheduling must satisfy compatibility, routing, timing, and service requirements while adapting to real-time requests and distribution shifts that can make historical forecasts inaccurate.
Method
The framework combines stochastic dynamic programming, sampled future-request rollout scenarios, adaptive prediction weighting, selective re-optimization, tractable candidate generation, wait actions, and historical-data-driven fleet selection.
Results
The hospital-floor case study achieved near-complete service and reduced request wait times relative to reactive, token-passing, prediction-positioning, and myopic greedy baselines, with the largest improvements in tail metrics.
Takeaways & Limitations
Restricting immediate commitments to observed requests while adaptively weighting predictions uses useful forecasts without allowing unreliable forecasts to dominate online decisions.
Takeaways & Limitations
Future work is needed to improve finite-scenario and heuristic future-cost estimation, prediction calibration, and disruption-aware selective re-optimization.
Abstract
from arXiv · showhide
Heterogeneous multi-robot service systems must assign requests to compatible robots, construct feasible schedules, and adapt as new tasks arrive online. Historical data can help anticipate future demand, but relying too heavily on inaccurate predictions can degrade performance under distribution shifts. We develop a prediction-aware adaptive rollout framework for heterogeneous multi-robot task assignment with scheduled and real-time requests. The problem is formulated as a finite-horizon stochastic dynamic program incorporating robot-task compatibility, ordered service requirements, routing constraints, service windows, and end-of-horizon return requirements. The proposed policy evaluates current assignments using sampled future request scenarios while restricting immediate commitments to requests already observed. To enable online use, the framework combines pruned candidate controls, wait actions, and an interaction-aware base policy for efficient future-cost estimation. Robustness to forecast error is provided by adaptively reweighting predicted requests based on recent prediction mismatch and selectively re-optimizing assigned but unstarted requests. We also introduce a historical-data-driven procedure for selecting the heterogeneous fleet composition before deployment. In a case study using real nursing-task requests from hospital inpatient floors, the proposed approach achieves near-complete service and reduces serviced-request wait times relative to reactive, token-passing, prediction-positioning, and myopic greedy baselines, with the largest improvements in tail-delay metrics.
1. Introduction
The paper addresses online assignment and scheduling for heterogeneous robot teams facing sequential requests, tight feasibility constraints, and uncertain future demand. It proposes an adaptive rollout framework that uses predictions for lookahead without committing to unobserved requests, and reports near-complete service with lower wait times in a hospital case study.
- Heterogeneous robot teams must repeatedly adapt assignments as requests arrive, robot availability changes, and operating conditions depart from historical expectations.
- Current assignments have delayed consequences because they change robots’ future locations, availability, and ability to serve later requests under distribution shifts.
- Existing methods trade off responsiveness, anticipation, and tractability: reactive methods are myopic, prediction-based methods often lack mismatch adaptation, and exact stochastic optimization is intractable here.
- The framework combines sampled future scenarios, forecast-error reweighting, selective re-optimization, pruned candidate controls, wait actions, and interaction-aware rollout simulation.
- Predicted future requests inform simulated opportunity costs but cannot receive immediate assignments, while observed requests can trigger schedule revisions.
- The hospital case study reports near-complete service and reduced average and upper-tail waiting times relative to reactive, token-passing, prediction-positioning, and myopic greedy baselines.
2. Related Work
Related work spans heterogeneous allocation, scalable online coordination, learning-based policies, uncertainty modeling, fleet composition, and temporal point-process prediction. The paper combines these threads by adapting prediction influence online and reconsidering unstarted assignments under forecast mismatch.
- Prior heterogeneous allocation methods model capabilities, temporal constraints, routing, and task-and-motion planning, but dynamic insertion and rescheduling remain challenging.
- Reactive, auction-based, decentralized, and metaheuristic methods respond quickly but can be myopic when assignments affect future service quality.
- Learning-based allocation policies can degrade under shifts in arrivals, task frequencies, robot availability, travel conditions, or operating policies.
- Uncertainty-aware allocation addresses uncertain capabilities, outcomes, or demand, whereas this work focuses on adapting the influence of predicted future requests.
- Fleet composition matters because adding robots may not increase capacity for bottleneck request types lacking compatible robots.
- Temporal point processes represent irregular event timing and task-relevant marks directly, supporting feasibility reasoning based on request type, location, and robot compatibility.
- The framework converts sampled temporal-point-process events into planner-compatible requests rather than treating predictions as fixed schedules or mandatory tasks.
- Adaptive weighting is paired with selective reconsideration of assigned but unstarted requests when observations indicate that the current schedule has become undesirable.
3. Problem Formulation
The formulation models finite-horizon scheduling for a fixed heterogeneous fleet serving scheduled and sequentially revealed requests under compatibility, routing, timing, and return constraints. It represents deployment uncertainty through a stochastic request process and motivates approximation because exact optimization is computationally intractable.
- 3. Problem Formulation: The problem concerns a fixed heterogeneous team serving scheduled and real-time requests with ordered service locations and timing requirements.
- 3.1. Operating Horizon and Environment: The operating horizon is finite, with controls selected at times t = 0, …, T−1 determining system evolution over each interval.
- 3.1. Operating Horizon and Environment: The environment is a directed traversal graph whose nodes represent traversable configurations or locations and whose edges represent collision-free local trajectories.
- 3.1. Operating Horizon and Environment: Service locations are a subset of traversal nodes; other nodes support motion planning but do not accept requests.
- 3.2. Robot Team and Task Compatibility: Robot types determine capabilities and edge traversal times, while the fleet composition specifies counts of each type and robot identities.
- 3.2. Robot Team and Task Compatibility: Robots start and must return to assigned maintenance stations by time T, and the planning problem assumes a fixed team composition.
- 3.3. Requests: Requests encode task types, ordered service-node sequences, release information, execution times, and timing requirements, and are divided into scheduled and real-time sets.
- 3.4. Standing Assumptions: The model assumes finite request arrivals, connectable request endpoints, and reliable robot execution, so stochasticity enters through future request arrivals.
4. Our Approach
The approach uses a tractable rollout policy that assigns only observed requests while using predicted requests to estimate future costs. It supports online decisions through candidate pruning and wait actions.
- The rollout policy selects feasible controls from a pruned candidate set containing schedule modifications only for requests that have entered the system.
- Predicted future requests are used for rollout-based future-cost estimation rather than immediate assignment.
4.1. Overview of the Prediction-Aware Adaptive Rollout Framework
The online policy combines prediction-aware rollout, tractable candidate generation, sequential robot processing, and adaptive schedule revision. A pre-deployment fleet-sizing procedure selects a fixed heterogeneous composition using historical request sequences.
- Framework components: The planner combines candidate generation, sampled future scenarios, an interaction-aware base policy, adaptive confidence weights, and selective re-optimization.These components support repeated online decisions while allowing assigned but unstarted requests to return to the pending set when schedules become undesirable.
- Framework components: Robots are processed sequentially, with local controls selected for earlier robots held fixed while later decisions are completed using the base policy.This one-robot-at-a-time decomposition reduces the size of the decision problem evaluated during rollout.
- Fleet sizing: Historical request sequences determine a heterogeneous fleet composition selected to achieve a target empirical feasibility level before deployment.The selected composition remains fixed during online operation.
- Framework components: The framework is organized around rollout decisions, candidate controls and waits, scenario generation, base-policy estimation, adaptive weighting, and selective re-optimization.These components are presented as successive parts of the framework.
4.2. One-Robot-at-a-Time Rollout Decision Rule
The rollout decision rule evaluates feasible robot-local controls sequentially by completing simulated decisions and estimating downstream schedule quality under sampled future requests. Predicted requests affect evaluation but are excluded from immediate executable candidate sets.
- Sequential decision rule: The planner replaces joint optimization with sequential robot-local decisions, holding earlier choices fixed and using simulation to complete later decisions.This processes robots in an order that may be fixed or state-dependent.
- Candidate evaluation: Each local candidate uses only requests known by the current decision time, while predicted future requests are excluded from the immediate candidate set.This preserves the distinction between executable assignments and predictive information used for lookahead.
- Candidate evaluation: A completed joint control fixes earlier robot choices, applies the current robot’s candidate, and uses the base policy for unprocessed robots.The completion step evaluates candidates inside rollout; the final executable control is formed after all robots are processed.
- Rollout simulation: Each completed control is simulated from the current state through a truncated horizon, producing a resulting simulated state for terminal evaluation.The rollout applies the completed control first and then follows the base policy.
- Terminal scoring: Pending requests are resolved with the base policy before terminal scoring so that wait actions cannot leave relevant requests cost-free indefinitely.Requests may be assigned, remain available for later simulated assignment, or be marked rejected or unserviceable before deadlines.
- Terminal scoring: The resolved weighted terminal score is equivalent, up to a fixed baseline, to summing weighted incremental costs over the truncated horizon.The equivalence follows from the one-step cost being defined as a change in aggregate schedule score.
- Sequential decision rule: After each selected control is fixed, the planner advances to the next robot until the one-robot-at-a-time control is complete.The decision rule constructs the executable control incrementally.
- Adaptive prediction use: The policy is prediction-aware because sampled scenarios affect candidate evaluation, but predicted requests never enter immediate candidate controls.Their influence is mediated by online confidence weights computed from recent forecast errors.
4.3. Candidate-Control Generation and Wait Actions
Candidate-control generation prunes feasible assignments for known compatible requests using urgency and heuristic delay, while always retaining a wait action. Rollout evaluation, rather than pruning rank alone, selects among the retained actions.
- Candidate generation: The generator creates a small set of feasible schedule modifications for known requests instead of enumerating the full feasible control space.Predicted requests influence selection only through later rollout simulation.
- Eligible requests: Only known, unrejected, incomplete, nonexecuting requests enter the eligible set, with unstarted assignments re-entering only after explicit re-optimization.Started services remain fixed.
- Feasibility filtering: A robot considers an assignment only when it is compatible with the request.Compatibility is enforced before robot-local assignment candidates are generated.
- Feasibility filtering: A retained assignment appends the request’s ordered service-node sequence to a compatible robot’s remaining schedule and must satisfy routing, timing, preservation, and return constraints.The robot must return to its maintenance station by the horizon.
- Pruning and ranking: Candidate assignments are ranked by urgency and estimated delay, with earlier latest feasible service-start times expanded first.The heuristic ranking is used for pruning, not as the rollout objective.
- Wait actions: The wait action is always included, leaving a robot unassigned for the current cycle and preserving future reconsideration.During simulated completion, the waiting robot is temporarily unavailable so the base policy cannot immediately undo the wait.
- Pruning and ranking: The procedure reduces rollout search to a tractable robot-local candidate set while retaining wait when downstream estimates favor preserving capacity.This keeps the candidate set nonempty even when no feasible assignment exists.
4.4. Future-Request Scenario Generation
Future-request scenarios are sampled from local temporal point-process models, converted into graph-grounded request tuples, filtered for duplicates, and supplied to rollout simulation under the same operational constraints as observed requests.
- Scenario generation: The scenario generator samples future events from an estimated distribution and converts them into request tuples for scheduling.It connects the request-prediction model with the scheduling model.
- Prediction model: Historical data train local temporal point-process models rather than one global process, with each hospital process corresponding to a patient encounter.The construction can also associate future demand with other local entities, regions, or service contexts.
- Prediction model: Past timed marks encode event times and task-family information used by the neural temporal point process to parameterize future event-time and mark distributions.The sampled events provide raw future demand for scenario construction.
- Request construction: Each sampled timed mark is deterministically mapped into a request tuple with task type, service time, entry time, earliest start, deadline, and task-specific attributes.Service locations and ordered endpoints are constructed from local process context and task type.
- Scenario generation: Sampled requests are grouped into future disturbance sequences by their simulated entry decision times through the truncated rollout horizon.The generator aggregates predicted requests separately for each rollout sample.
- Duplicate filtering: Predictions matching scheduled or already observed requests are removed to prevent double-counting.Matching uses task type, compatible service-node context, and predicted service time within tolerance Δ.
- Scenario generation: The algorithm samples future timed marks for each active local process across multiple scenarios and excludes matched requests before simulation.Its inputs include local histories, local models, a request-construction map, rollout depth, sample count, and match tolerance.
- Scenario evaluation: Generated future demand uses the same compatibility, routing, service-window, and scheduling constraints as real requests while remaining outside immediate candidate controls.This keeps predictive demand operationally consistent with observed demand during rollout.
4.5. Interaction-Aware Base Policy for Future-Cost Estimation
The interaction-aware base policy efficiently estimates future assignment costs by preserving key scheduling constraints while approximating downstream decisions inside rollout simulations. It uses reservation tables to account for competition at shared service locations when comparing compatible robot assignments.
- Base-policy role: The base policy approximates downstream assignment and routing decisions inside rollout simulations rather than solving each hypothetical scheduling problem fully.It completes simulated assignments for unprocessed robots and resolves pending requests before terminal scoring.
- Request processing: Requests are processed in priority order, with less remaining scheduling flexibility considered first.The policy handles newly sampled, pending, and reconsidered requests in the simulated state.
- Robot evaluation: For each request, the policy evaluates compatible, unblocked robots using travel times, service durations, timing constraints, and reservation-table feasibility.It estimates completion times after appending the request to each robot’s simulated schedule.
- Interaction modeling: Reservation tables shift overlapping service intervals to the earliest available time satisfying the request’s timing constraints.This captures service-location blocking and shared-node competition without constructing full collision-free paths for every hypothetical request.
- Assignment choice: The request is assigned to the compatible robot with the smallest heuristic delay, or marked rejected when no feasible robot can meet its deadline.The resulting assignments, completion times, rejection indicators, and reservations feed the rollout estimator.
- Constraint preservation: The approximation preserves compatibility, endpoint order, release times, deadlines, service durations, availability, and service-location blocking while avoiding full hypothetical schedule construction.
4.6. Adaptive Prediction Confidence and Weighted Rollout Costs
Adaptive prediction confidence changes how strongly hypothetical future requests influence rollout evaluation as recent forecast errors accumulate. The mechanism distinguishes overprediction from small timing shifts and uses hierarchical fallback when local evidence is sparse.
- Scope of weighting: Confidence weighting affects only hypothetical requests inside rollout simulation and does not alter real assignments, feasibility constraints, or observed-request commitments.Retrospective changes to already assigned unstarted requests are handled separately by selective re-optimization.
- Confidence weighting: Predicted requests receive context-dependent confidence weights, while observed and scheduled requests always receive unit weight.Weights lie between λmin and 1; smaller values reduce predicted requests’ influence on rollout evaluation.
- Forecast mismatch: The update compares recent observations with prediction snapshots using fixed confidence-update bins and distinguishes overprediction from timing error.Adjacent-bin demand is treated as a possible timing shift rather than automatically as a spurious prediction.
- Online update: Persistent overprediction or timing mismatch lowers future prediction weights, with separate smoothing and sensitivity parameters controlling responsiveness and reduction strength.The implementation typically penalizes persistent overprediction at least as strongly as timing mismatch.
- Sparse contexts: Hierarchical fallback blends local and broader-context reliability estimates so sparse or new contexts initially rely more on broader evidence.Local context weights dominate after sufficient prediction evidence accumulates.
4.7. Selective Re-optimization of Unstarted Assignments
Selective re-optimization provides retrospective correction when new observations make existing assignments undesirable. It releases eligible assigned but unstarted requests while preserving commitments for services already underway.
- Eligibility: Assigned but unstarted requests can be returned to the pending set because started requests remain protected by the no-reassignment constraint.Requests whose service has begun remain fixed until completion.
- Trigger: Re-optimization is considered when newly observed requests coexist with assigned but unstarted requests and urgency indicates a schedule conflict.Urgency is based on slack derived from lower bounds on earliest possible completion times.
- Release rule: When a new request is more urgent, lower-priority unstarted assignments with larger slack are released and their robot schedules are repaired.Released requests have their assignments reset while started or completed commitments are preserved.
- Updated planning: Newly observed and released requests are reconsidered together under current prediction-confidence weights before rollout selects updated controls.This combines retrospective correction with the current online decision process.
4.8. Supporting Pre-Deployment Fleet Sizing
The pre-deployment fleet-sizing procedure selects a fixed heterogeneous robot composition from historical request sequences. It combines day-wise capacity estimation, marginal initialization, and joint historical feasibility verification, while providing empirical rather than deployment-distribution guarantees.
- Sizing objective: The procedure chooses a fixed heterogeneous team composition that targets an empirical feasibility level on representative historical operating days.Feasibility requires compatible assignment, deadline completion, and robot return to maintenance stations by the horizon.
- Day-wise sizing: For each historical day, the method increases the count of a compatible robot type when requests are rejected or violate service windows, then repeats assignment simulation.The resulting day-wise feasible compositions estimate type-specific capacity requirements.
- Initialization: Initial counts for each robot type are selected from empirical quantiles of the day-wise feasible counts.The target level γ determines the selected quantile.
- Joint verification: Joint verification is necessary because separate type percentiles do not guarantee feasibility for the combined heterogeneous team.The joint check accounts for task interactions, service windows, routing, and robot-type substitution.
- Verification: The verification phase accepts a composition when its empirical feasibility rate reaches the target, otherwise it increments the type with the largest failure score and repeats.Failure scores count how often each type could have served rejected or deadline-violating requests.
- Scope boundary: The selected composition is fixed for the online rollout formulation, but the procedure does not prove feasibility under the deployment distribution.
5. Case Study: Task Assignment in Hospital Floors
The hospital-floor case study evaluates prediction quality, fleet sizing, service completion, wait times, and computational cost across demand regimes. The proposed adaptive rollout achieves near-complete service and the strongest wait-time improvements, especially in tail delays, while remaining operationally usable.
- Evaluation setup: Laney-adjusted control limits identify high-, medium-, and low-demand weeks for held-out evaluation under demand shifts.Weeks outside the upper or lower limits are flagged by task type and aggregated at the floor level.
- Prediction ablation: FlexTPP with enhanced marks and previous-day context obtains the lowest monitoring-request OTD, while enhanced features do not consistently improve medication-delivery prediction.FlexTPP-based models outperform other medication-delivery predictors, but richer conditioning is less consistently beneficial there.
- Team sizing: The verified heterogeneous fleet contains 6 monitoring robots and 3 delivery robots, and this composition is fixed for subsequent policy comparisons.Joint verification increases delivery capacity from 2 to 3 robots because marginal family-wise percentile estimates do not guarantee joint feasibility.
- Service completion: All evaluated policies avoid rejection except Token Passing and Token Passing with Task Swaps, which reject 28 of 36,948 high-demand requests.The proposed adaptive rollout policy has no service-level failures in the reported evaluation.
- Interpretation: The rollout policy improves wait times by evaluating sampled future costs while restricting immediate assignments to requests that have entered the system and adapting the influence of unreliable predictions.This mechanism is intended to reduce locally feasible decisions that create later bottlenecks and to outperform direct prediction-based positioning.
6. Conclusion
The paper presents an adaptive rollout framework for online heterogeneous multi-robot scheduling that uses predicted future demand without prematurely committing robots, while correcting forecast influence and eligible assignments as conditions change. In hospital-floor experiments, it reduced wait times relative to multiple baselines, especially for tail delays, while several implementation and deployment limitations remain.
- Conclusion: The framework formulates online heterogeneous multi-robot assignment as a finite-horizon stochastic dynamic program with scheduled and real-time requests.Controls update assignments and schedules for known requests, while future requests enter through a stochastic disturbance process and predicted and true distributions are distinguished.
- Conclusion: Prediction-aware rollout uses sampled future requests for lookahead while restricting immediate assignments to requests already observed.Pruned candidate controls, wait actions, one-robot-at-a-time decisions, and an interaction-aware base policy make future-cost estimation tractable.
- Conclusion: Adaptive forecast-error weights reduce unreliable predicted requests’ influence, while selective re-optimization revises assigned but unstarted requests when new observations make schedules undesirable.The two mechanisms provide prospective correction and repair of eligible commitments.
- Conclusion: In the hospital-floor case study, the adaptive rollout policy reduced request wait times relative to reactive, token-passing, prediction-positioning, and myopic greedy baselines.The largest improvements appeared in tail wait-time metrics, and the selected heterogeneous team composition avoided persistent overload on held-out floor-days.
- Conclusion: The current implementation remains limited by sampled future scenarios, a heuristic base policy, count-based forecast-error contexts, and evaluation that should extend to closed-loop physical or high-fidelity hospital operations.Future work also concerns richer calibration and more explicit modeling of schedule-disruption costs.
CRediT authorship contribution statement
The contribution statement assigns conceptualization, methodology, data, supervision, analysis, implementation, validation, visualization, writing, and funding roles across five authors.
- CRediT authorship contribution statement: Daniel Garces contributed conceptualization, formal analysis, investigation, methodology, software, validation, visualization, and writing.His listed writing roles include the original draft and review and editing.
- CRediT authorship contribution statement: Sara Castro contributed conceptualization, data curation, methodology, and writing review and editing.
- CRediT authorship contribution statement: Adrian Haimovich contributed data curation and supervision.
- CRediT authorship contribution statement: Byron Crowe contributed conceptualization, data curation, and supervision.
- CRediT authorship contribution statement: Stephanie Gil contributed funding acquisition, supervision, and writing review and editing.