Paying for Space: Incentive-Aware Motion Planning for Multi-Agent Collision Avoidance

Debajyoti Chakrabarti, Anushri Dixit · IEEE Conference on Decision and Control (CDC), 2026

IEEE CDC 2026 · Accepted
Multi-Agent Systems Motion Planning Optimal Control Mechanism Design
Paper Code · Coming soon ← Back to Home

Abstract

Advanced Air Mobility (AAM) systems require scalable coordination mechanisms to manage large fleets of aerial vehicles operating in shared, capacity-limited airspace. In such environments, different operators may have private preferences over trajectory characteristics, such as travel time, fuel consumption, or deviation from nominal routes. If centralized traffic management relies on self-reported preferences, operators may strategically misreport their costs to obtain more favorable trajectories.

This paper proposes a multistage motion planning framework augmented with mechanism design to enable collision avoidance for AAM systems with privately known costs. The proposed approach integrates convex safe corridor construction with a VCG-inspired mechanism to ensure conflict-free passage through constrained airspace while incentivizing truthful revelation of private preferences. Simulation results demonstrate safe and decentralized coordination among agents with heterogeneous preferences.

Why Collision Avoidance Is Not Enough

Advanced Air Mobility systems may involve multiple autonomous aerial vehicles sharing constrained airspace or landing corridors.

The challenge is not only avoiding collisions. Different operators can have private preferences over travel time, control effort, fuel usage, or route deviation.

If the central planner relies on self-reported costs, agents may strategically misreport those preferences to obtain more favorable trajectories.

Motivation flow: shared airspace is a scarce resource, agents have private preferences over trajectories, and if reports affect allocation, agents may strategically misreport. We need both an allocation rule for safe space and a transfer/payment accounting for externality on others.
Allocating scarce airspace under private information requires both a safe-space allocation rule and a payment that accounts for externalities.

Incentive-Aware Airspace Allocation

The framework treats shared airspace as a scarce resource. A central planner:

  1. allocates collision-free corridors,
  2. accounts for each agent's reported preferences,
  3. computes VCG-inspired transfers based on the externality imposed on other agents.

Each agent then performs its own trajectory optimization inside its assigned safe corridor.

Overview of the incentive-aware airspace allocation framework: objective, central allocation, and decentralized execution, applied to a three-agent shared-corridor scenario.
Overview of the incentive-aware airspace allocation framework, applied to a three-agent shared-corridor landing scenario.
Payment defined as the externality imposed on other agents; utility is the net payoff after the transfer.
Payment as the externality imposed on other agents; utility is the net payoff after the transfer.

Central Allocation with Decentralized Execution

The ideal formulation is bilevel.

Outer level: allocates non-overlapping safe airspace, chooses how shared corridor space is divided, and minimizes total reported cost.

Inner level: represents each agent solving its own trajectory optimization, ensuring the assigned corridor is compatible with decentralized behavior.

Bilevel structure: outer level allocates non-overlapping safe space across agents; inner level replicates each agent's own trajectory-cost optimization.
Outer allocation problem coupled with each agent's inner trajectory optimization.
Exact bilevel formulation: outer-level allocation and collision constraints, with each agent's inner-level trajectory optimization circled.
Exact bilevel formulation, with each agent's inner-level problem circled.

From Bilevel Optimization to a Tractable Three-Stage Pipeline

Solving the exact bilevel problem directly is hard, since the collision-avoidance constraints are nonconvex. A three-stage decomposition gives a tractable approximation:

Three-stage decomposition: nominal planning, convex corridor allocation, then final decentralized planning and payment computation.
Three-stage decomposition of the bilevel allocation problem into a tractable pipeline.

Time-Varying Convex Safe Corridors

Pairwise separating hyperplanes define convex regions for each agent. Continuous mixing variables control where the separating boundary lies between pairs of agents.

After reconciliation, each agent receives a non-overlapping time-varying polytopic corridor and can plan independently inside it.

Allocated time-varying polytopic corridor for one agent.
Allocated time-varying polytopic corridor for one agent.
Halfspace mixing variables controlling pairwise corridor allocation over time.
Halfspace mixing variables controlling pairwise corridor allocation over time.

Decentralized Coordination in the Shared Corridor

Animated landing-coordination sequence: three agents enter the shared corridor and reach their assigned goals at prescribed landing times.
Animated replay of the landing-coordination scenario. Agents enter the shared corridor and reach their assigned goals at prescribed landing times.

Results

A. Social Valuation

Across 70 Monte Carlo trials with randomized initial conditions, goals, preferences, and misreporting agents, the proposed method achieved the highest average social valuation among the compared methods in both truthful and misreporting settings.

Average social valuation ×108; higher is better.
Reporting P2 P3 P4 (Ours)
Truthful -3.30854 -3.30907 -3.30782
Misreport -3.3431 -3.34105 -3.33867

B. Incentive Behavior

The effect of the VCG-inspired transfer was evaluated using the difference between truthful and misreported utility (Δu).

The positive mean indicates that the transfer mechanism helps incentivize truthful reporting on average. This does not establish exact strategyproofness — see Limitations below.

C. Scalability

Agents Central time (s) Agent time (s)
3 147.08 2.26
4 347.4 2.30
5 924 2.34

Centralized computation is the main bottleneck, while decentralized agent-level computation remains approximately constant across the tested cases.

Takeaways and Limitations

Key Takeaways

  • Collision avoidance can be combined with incentive-aware allocation.
  • Convex corridor allocation enables decentralized execution.
  • The VCG-inspired transfer improves truthful-reporting behavior on average.
  • The method achieved higher social valuation than the tested baselines.

Limitations

  • The multistage decomposition is only an approximation of the exact VCG allocation.
  • The method is therefore incentive-aware, not strictly strategyproof.
  • Centralized leave-one-out computations remain the scalability bottleneck.
  • The current study uses deterministic planar double-integrator dynamics.

Future Directions

Read the full paper ← Back to Home