PaperlayerView exact revision on arXiv

Source-linked AI summary

Trust-Aware Sequential Decision Making and Rollout Planning for Resilient Multi-Robot Systems

Roee M. Francos, Daniel Garces, Orhan Eren Akgün, Nathaniel D. Bastian, Stephanie Gil

arXiv:2608.25690v1cs.MAcs.RO

TL;DR

The paper addresses online multi-robot routing when unreliable localization and non-cooperative behavior make planning models diverge from physical execution. It introduces monitor-aware spoofing and trust-aware state filtering that combines localization and behavioral evidence. Experiments show that removing detected adversaries restores stable routing and rollout’s empirical advantage when sufficient planning horizon and cooperative capacity are available.

  • Problem

    Online routing assumes reliable planning information and cooperative execution, but compromised agents can create planner-execution mismatch that undermines sequential planning.

  • Method

    The paper combines distance-constrained monitor-aware spoofing with a trust-aware planning architecture using localization-integrity and task-level behavioral evidence to filter agents from subsequent planning.

  • Results

    Experiments show that trust-aware adversarial removal restores stable routing and rollout’s empirical advantage over the IA-RA base policy after detected adversaries are excluded.

  • Takeaways & Limitations

    Trust is most useful for resilient sequential planning when reliability estimates change the planning representation and the agents considered during future decisions.

  • Takeaways & Limitations

    The stability and rollout findings are empirical and do not provide general analytical guarantees for detection time, closed-loop stability, or rollout improvement under mismatch.

Abstract

from arXiv · show

Sequential decision-making in multi-robot systems typically assumes that planning information is reliable and that agents execute the actions anticipated by the planner. Compromised agents can violate both assumptions, creating a mismatch between the planning model and physical execution. We study this problem in online multi-robot routing under localization spoofing. We introduce a distance-constrained spoofing model for monitor-aware adversaries, together with a tiered bipartite matching strategy that maximizes assignment influence while limiting spoofing magnitude. To mitigate such attacks, we develop a trust-aware monitor that combines probabilistic localization trust, calibrated using real GPS spoofing data, with behavioral evidence from task execution to classify agents and remove detected adversaries from subsequent planning. We further show that undetected adversaries can cause rollout to lose its expected cost-improvement behavior by violating planner-execution consistency. Trust-aware removal restores this consistency after detection, enabling stable routing and recovery of rollout's empirical advantage over the base policy. Experiments using real GPS spoofing datasets and San Francisco taxicab demand demonstrate effective detection and resilient routing across varying spoofing capabilities, adversarial fleet sizes, adaptive attacks, monitoring configurations, and rollout horizons.

I. INTRODUCTION

The paper studies online multi-robot routing when localization reports and agent behavior may be compromised, creating a mismatch between planning assumptions and physical execution. It proposes monitor-aware spoofing and trust-aware planning methods, then evaluates resilient routing and rollout recovery.

  • I. INTRODUCTION: Compromised agents can corrupt reported states or ignore prescribed actions, causing assignment failures, reassignment, wasted capacity, delays, and cancellations.These effects can accumulate and destabilize repeatedly recomputed online routing.
  • I. INTRODUCTION: Monitor-aware adversaries trade routing influence against detectability by coordinating bounded localization spoofing.The paper introduces a distance-constrained spoofing model and tiered bipartite matching strategy for this setting.
  • I. INTRODUCTION: The trust-aware framework combines probabilistic localization trust with behavioral task-execution evidence to classify agents and construct a trusted active fleet.Detected adversaries are removed from subsequent planning, while execution outcomes update trust in a closed loop.
  • I. INTRODUCTION: Undetected adversaries can violate planner-execution consistency and cause rollout to lose its expected cost-improvement behavior.Trust-aware removal excludes detected adversaries from planning, restoring consistency and rollout’s empirical advantage over the IA-RA base policy.
  • I. INTRODUCTION: Experiments use real GPS spoofing data and San Francisco taxicab demand across spoofing, fleet, monitoring, adaptive-attack, and rollout-horizon configurations.The results report effective detection and resilient routing across these conditions.

B. Request Arrival and Service Model

The routing model represents pickup-and-delivery requests arriving over time on a strongly connected directed graph, while adversaries may falsify locations and disregard assigned service actions. The physical system evolves from executed actions and request arrivals rather than commanded actions alone.

  • B. Request Arrival and Service Model: Transportation requests specify pickup and drop-off locations, arrival time, and pickup status.A request remains outstanding until pickup or cancellation.
  • B. Request Arrival and Service Model: Request arrivals, pickup locations, and drop-off locations are sampled from distributions estimated from historical demand data.The model assumes finitely many arrivals per time step and independent location sampling across arrivals.
  • B. Request Arrival and Service Model: Requests expire and count as canceled when they are not picked up within the prescribed waiting-time limit.Outstanding demand therefore changes through arrivals, successful pickups, and expirations.
  • B. Request Arrival and Service Model: Adversarial agents may manipulate reported locations, disregard assigned service actions, and coordinate their localization information.They have unique immutable identities and knowledge of the routing policy and assignment mechanism.
  • B. Request Arrival and Service Model: The true system evolves from the executed joint action and exogenous request information, not necessarily from the commanded routing action.Cooperative agents follow commands, whereas adversarial agents may execute different behavior or provide no assigned service.

E. Performance and Stability Criterion

The paper evaluates routing using outstanding demand and cumulative cancellations, with stability requiring that these quantities do not persistently accumulate. Trust-aware planning filters unreliable agents before applying the sequential policy, but suspect agents may remain until evidence is sufficient.

  • E. Performance and Stability Criterion: Routing performance is measured through outstanding requests and cumulative request cancellations.Canceled requests remain in the cumulative term, so persistent expiration increases long-term cost.
  • E. Performance and Stability Criterion: A policy is average-cost stable when the routing system prevents persistent accumulation of outstanding and canceled requests.Unbounded growth indicates that service demand is accumulating faster than fleet capacity can process it.
  • E. Performance and Stability Criterion: Planner-execution mismatch arises because decisions use a perceived state while realized performance depends on the true state and executed action.Localization spoofing can corrupt assignments, while non-cooperative execution can invalidate assumed service behavior.
  • E. Performance and Stability Criterion: The trust-aware framework assesses information and behavior, classifies agents, filters the planning state, applies the underlying policy, and updates trust from execution.It separates information assessment, trusted state construction and planning, and execution in a feedback loop.
  • E. Performance and Stability Criterion: Agents with ambiguous evidence remain suspect rather than being immediately removed, preserving capacity while delaying exclusion.Aggressive removal can reduce useful capacity, whereas delayed removal allows unreliable agents to influence decisions.
  • E. Performance and Stability Criterion: The trusted planning state excludes agents with sufficient evidence of adversarial behavior before the policy computes actions.The filter reduces mismatch while retaining as much reliable planning capacity as possible, though undetected agents may remain represented.

C. Closed-Loop Decision Epoch

Each decision epoch updates trust from integrity observations and prior execution evidence, filters the active fleet, and plans over the resulting trusted state. Monitor-aware spoofing bounds reported positions while adversaries coordinate reports before monitoring and routing.

  • Closed-Loop Decision Epoch: Trust updates combine current localization-integrity observations with behavioral outcomes from previous execution before routing decisions are computed.The resulting trust state classifies active agents and informs subsequent planning.
  • Closed-Loop Decision Epoch: Execution generates new physical-state, information, and behavioral outcomes that become evidence for later trust updates.This ordering separates information available before planning from evidence produced after execution.
  • Closed-Loop Decision Epoch: The framework filters unreliable agents from the planning representation, producing a trusted active fleet and routing-specific trusted state.Adversarial agents are removed before the next routing decision.
  • Closed-Loop Decision Epoch: Monitor-aware adversaries restrict reported locations to a graph neighborhood of the true position, with dmax controlling the influence-detectability trade-off.When dmax reaches the graph diameter, the restriction becomes inactive and spoofing is unconstrained.
  • Closed-Loop Decision Epoch: Adversarial reports are selected before trust updates, so they affect the current routing decision only if the agents remain in the filtered planning fleet.The attack is coordinated using favorable information about requests, fleet membership, and routing conditions.

C. Tiered Target Prioritization

The adversarial strategy prioritizes requests by proximity to cooperative service and coordinates feasible assignments through lexicographic bipartite matching. It recomputes reports online under the spoofing-distance constraint.

  • Tiered Target Prioritization: Requests closer to cooperative service receive higher adversarial priority through ordered distance tiers.Smaller εr(t) values identify requests nearer to cooperative agents, while lower αr(t) values indicate higher priority.
  • Tiered Target Prioritization: The attack matches active adversaries to cooperative-feasible requests, with at most one request per adversary and at most one adversary per request.Only adversary-request pairs satisfying the spoofing feasibility constraint enter the matching graph.
  • Tiered Target Prioritization: The lexicographic objective first maximizes targeted requests, then favors lower distance tiers, and finally minimizes total localization displacement.This ordering explicitly balances assignment influence, cooperative-service proximity, and spoofing magnitude.
  • Tiered Target Prioritization: A weighted assignment formulation preserves the lexicographic ordering using sufficiently separated weights.The weights bound lower-priority displacement and tier terms so higher-priority objectives dominate.
  • Tiered Target Prioritization: At each epoch, matched adversaries report targeted pickup locations, while unmatched adversaries report their true locations.The attack is recomputed as fleet configuration, demand, request lifetimes, and spoofing constraints change.

VI. TRUST EVIDENCE AND ONLINE MONITORING

Online monitoring combines probabilistic localization evidence with behavioral execution evidence to classify agents and remove adversaries from subsequent planning. Localization trust is calibrated from GPS spoofing data and made dependent on observed discrepancy.

  • Trust Evidence and Online Monitoring: The monitor independently evaluates localization integrity and task-execution behavior, fusing their classifications into χi(t).Behavioral evidence includes pickups, assignment churn, and request expirations.
  • Localization-Trust Evidence: Localization trust models reported-position reliability with bounded Beta distributions, where larger values indicate greater confidence.The model represents both confidence and uncertainty over localization information.
  • Localization-Trust Evidence: GPS-derived localization features are modeled with class-conditional Gaussians, converted by QDA into posterior confidence scores, and represented by class-specific Beta distributions.The classes include cooperative operation and spoofing strategies with different stealth levels.
  • Discrepancy-Dependent Localization Trust: The monitor can use a trusted or independently validated localization reference rather than direct access to the true physical position.Possible sources include independent integrity mechanisms, redundant sensing, or another trusted source.
  • Discrepancy-Dependent Localization Trust: Localization trust shifts from the cooperative distribution toward a calibrated adversarial distribution as reported-position discrepancy increases.Zero discrepancy matches the cooperative model, while larger deviations provide stronger localization-based manipulation evidence.

3) Temporal Aggregation and Localization Classification:

Localization evidence is aggregated over a sliding window before classification, reducing sensitivity to individual observations. Conservative thresholds distinguish accumulated adversarial evidence from typical nominal localization behavior.

  • Temporal Aggregation and Localization Classification: The monitor aggregates localization trust over a sliding window of length Wloc to reduce sensitivity to individual observations.The window includes recent localization-trust observations for agents active during those epochs.
  • Temporal Aggregation and Localization Classification: Agents remain suspect until a complete localization window has been accumulated.This delays definitive classification during the initial observation period.
  • Temporal Aggregation and Localization Classification: The adversarial threshold is selected conservatively from nominal cooperative data, while the cooperative threshold represents typical nominal localization behavior.Localization evidence is most informative when spoofing creates sufficiently large observable discrepancies.

B. Behavioral Trust and Request Responsibility

Behavioral trust evaluates task-level service outcomes rather than reported positions, using complete request histories to attribute positive evidence and penalties to responsible agents. The monitor delays updates until terminal events and requires sufficient evidence and confidence before classification.

  • Behavioral evidence: Behavioral trust uses request-level outcomes to identify agents whose task execution deviates from cooperative service.It complements localization trust by accumulating evidence from successful pickups, expirations, and reassignment churn.
  • Request responsibility: Complete assignment histories attribute responsibility for successful service, expiration, and harmful reassignment churn to involved agents.This captures repeated disruption even when the disruptive agent is not the final assignee at expiration.
  • Behavioral update: Behavioral evidence is updated only after terminal events, allowing the monitor to reconstruct each request’s complete assignment history.Each agent maintains a behavioral trust distribution that accumulates evidence over time.
  • Request responsibility: Harmful reassignment churn penalizes agents whose anticipated pickup should have occurred before a request terminated without completed service.The rule uses the complete request history because repeated disruption can occur before the final assignment.
  • Behavioral update: Behavioral classification requires sufficient accumulated evidence and posterior confidence; ambiguous agents remain suspect.The update procedure combines evidence accumulation with confidence-based classification rather than forcing an immediate binary decision.

C. Trust Fusion and Agent Classification

Localization and behavioral trust assess different parts of the planner-execution relationship, and their classifications are fused conservatively. Detected adversaries are removed from the trusted planning state, while suspect agents remain temporarily eligible for additional evidence.

  • Trust fusion: Localization trust evaluates reported-position integrity, whereas behavioral trust evaluates whether task execution matches expected cooperative service.Their complementarity matters when monitor-aware attacks reduce localization discrepancies but still produce repeated service failures.
  • Trust fusion: Strong evidence from either trust branch is sufficient for adversarial classification, while cooperative classification requires agreement between both branches.Conflicting or incomplete evidence leaves an agent in the suspect state.
  • Agent classification: Suspect agents remain in planning while additional evidence is collected, so planner-execution mismatch may persist during the detection interval.This avoids forcing a binary decision from insufficient evidence but creates a temporary operational trade-off.
  • Trusted planning state: Agents classified as adversarial are excluded from subsequent planning, and outstanding assignments involving them are revoked.Their request histories are retained so later behavioral attribution remains consistent.
  • Rollout planning: Rollout operates on the monitored fleet and trusted perceived state, using IA-RA as its base policy for subsequent simulated decisions.Monitoring changes which agents are represented in the rollout model rather than modifying the rollout objective.

C. Planner-Execution Mismatch Under Undetected Adversaries

Rollout assumes that retained agents execute commanded actions, but undetected adversaries violate this planner model and can eliminate rollout’s expected improvement over IA-RA. The implementation therefore uses trust-aware, one-at-a-time rollout over the monitored fleet, while evaluating improvement empirically.

  • Mismatch mechanism: Undetected adversaries are modeled during lookahead as cooperative service resources even when their physical execution deviates from commanded actions.This creates divergent simulated and physical transitions.
  • Mismatch consequences: Planner-execution mismatch can make estimated cost-to-go misrepresent physical cost, so rollout need not improve upon IA-RA in adversarial operation.The nominal cost-improvement behavior depends on consistency between simulated and executing systems.
  • Evaluation scope: Classical rollout improvement guarantees do not directly apply when candidate actions are evaluated under a model different from the executing system.Finite-horizon Monte Carlo approximation further motivates empirical rather than general guaranteed evaluation.
  • Rollout construction: One-at-a-time rollout improves agent actions sequentially while holding other components of the current joint action fixed.This avoids the full joint optimization’s combinatorial action-space cost.

E. Closed-Loop Trust-Aware Rollout Procedure

The closed-loop procedure processes monitoring evidence, constructs a trusted planning state, computes trust-aware rollout, and uses physical outcomes to update monitoring. Experiments combine real GPS spoofing data with San Francisco demand to test detection, routing resilience, and rollout alignment across attack and monitoring conditions.

  • Closed-loop procedure: At each decision epoch, the system processes evidence, updates classifications, removes detected agents, constructs the trusted state, and then computes rollout.Physical execution generates request outcomes and assignment histories for later monitoring updates.
  • Operating regimes: While adversaries remain undetected, rollout remains vulnerable because its lookahead model treats them as cooperative service resources.The filtered fleet can still contain adversarial agents during this regime.
  • Operating regimes: After all remaining adversaries are removed, the specific mismatch from adversarial non-execution is removed and simulations better align with physical execution.This conclusion is qualified by possible cooperative-agent false positives.
  • Scope and evaluation: Monitoring does not eliminate finite-horizon, demand-sampling, model-approximation, or cooperative-false-positive errors, nor guarantee rollout superiority at every epoch.Adversarial removal addresses the specific inconsistency caused by retaining non-cooperative service resources.
  • Experimental setting: The case study uses a directed San Francisco road network with 1026 intersections and 2300 road segments over a 1500 m radius region.Simulations use real taxicab demand, typically run for 2880 one-minute steps, and average results over 100 demand realizations.
  • Experimental design: Experiments vary spoofing bounds, adversarial fleet proportions, adaptive attacks, monitoring configurations, and rollout horizons while comparing four routing configurations.Monitoring and routing metrics include detection, false positives, detection time, outstanding requests, cancellations, and stage cost.
  • Localization validation: Real GPS spoofing datasets produce distinct cooperative and spoofed localization-trust distributions, but stealthier attacks move closer to cooperative observations.This supports localization evidence while motivating complementary behavioral evidence.

C. Routing Impact and Detectability of Monitor-Aware Spoofing

Monitor-aware spoofing can destabilize routing while remaining harder to detect at smaller spoofing distances. Combining trust-based removal with rollout reduces planner-execution mismatch, backlog, and cancellation accumulation after detection.

  • Routing impact: A single adversarial agent can destabilize an otherwise nominally stable IA-RA fleet under unconstrained or sufficiently permissive distance-constrained spoofing.The effect persists even when the cooperative fleet satisfies the fully cooperative stability condition.
  • Routing impact: Restricting spoofing distance does not eliminate persistent routing degradation because adversaries can still influence assignments through the tiered strategy.Smaller spoofing bounds reduce localization-trust separation from cooperative behavior, making adversaries harder to distinguish.
  • Complementary monitoring evidence: Localization and behavioral evidence provide complementary detection: localization can identify large deviations early, while behavioral evidence can identify less distinguishable adversaries over time.The fused monitor achieves the lowest routing cost and fewest active adversaries while maintaining a low cooperative-agent false-positive rate; behavior-only monitoring produced no reported cooperative false positives.
  • Adversarial removal and planning-execution alignment: Unmonitored rollout can accumulate backlog because lookahead assigns service capability to adversarial agents that do not execute the modeled service.Trust-aware removal progressively restricts planning to agents more consistent with cooperative execution and reduces outstanding requests after detection.
  • Cancellations and transient mismatch: Monitoring also stabilizes cancellations by removing agents that repeatedly invalidate simulated service trajectories, although the effect depends on rollout horizon.Cancellations accumulated before removal remain in the cost, so trust-aware rollout can retain higher cost despite later backlog recovery.
  • Routing cost and recovery: Before detection, rollout is especially vulnerable to an incorrect execution model; after removal, it can again use lookahead to improve current service decisions.This establishes distinct pre-detection and post-removal routing regimes.

F. Effect of Planning Horizon and Cooperative Capacity

Longer rollout horizons reduce backlog and cancellations, while cooperative capacity determines how effectively the system recovers after trust-aware adversarial removal. Trust filtering improves planning consistency, but detection delay, finite-horizon approximation, and deployment assumptions limit recovery guarantees.

  • Planning Horizon: Longer rollout horizons reduce persistent backlog and cancellations, whereas H = 10 can remain unstable even with monitoring.Longer lookahead helps account for downstream consequences of current assignments.
  • Planning Horizon: For H = 10, cancellations may continue accumulating after monitoring because removal cannot erase transient damage incurred before detection.Longer horizons allow cancellations to stabilize in the evaluated configurations.
  • Cooperative Capacity: Higher cooperative capacity enables trust-aware rollout to achieve lower routing cost, fewer outstanding requests, and fewer cancellations than monitored IA-RA in the reported experiment.Additional capacity helps clear backlog accumulated before adversarial removal, especially near minimum stable capacity.
  • Trust-Aware Planning: Trust-aware filtering prevents agents with unreliable behavior from influencing routing and rollout simulations, restoring a more consistent planning representation.The framework uses trust to determine which agents remain under consideration during planning.
  • Recovery Constraints: Recovery depends on detection delay, available cooperative capacity, and the planner’s ability to clear backlog accumulated before adversarial removal.Trust-aware planning therefore improves consistency without immediately eliminating prior mismatch consequences.
  • Adversarial Setting: The study’s adversaries coordinate bounded localization spoofing, while the framework combines localization-integrity and behavioral evidence to classify agents for planning.Behavioral evidence remains important because reduced localization deviation can make monitor-aware spoofing harder to distinguish using localization alone.
Loading 2608.25690v1…