PaperlayerView exact revision on arXiv

Source-linked AI summary

Trajectory Generation for Multiagent Point-To-Point Transitions via Distributed Model Predictive Control

Carlos E. Luis, Angela P. Schoellig

arXiv:1809.04230v2cs.ROcs.MA

TL;DR

Generating collision-free multiagent trajectories for point-to-point transitions is a safety-critical planning problem. The paper uses distributed MPC with on-demand collision avoidance, and reports reduced computational complexity versus SCP-based methods with a small impact on plan optimality.

  • Problem

    Generating collision-free trajectories for multiple agents moving from initial to final locations within a specified time is a safety-critical planning problem.

    Source: §I · p. 1, §II · p. 2

  • Method

    The distributed MPC approach shares predicted states among agents and adds soft collision constraints on demand to resolve predicted collisions.

    Source: §III · p. 2, §I · p. 2, A. The Synchronous Algorithm · p. 3

  • Results

    The method reduces computational complexity compared with SCP-based methods, with only a small impact on plan optimality.

    Source: §VII · p. 8

  • Takeaways & Limitations

    The approach was validated in experiments and supports quickly calculating and executing transition trajectories for large quadrotor teams.

    Source: §I · p. 2, §VII · p. 8

    Soft collision constraints do not guarantee collision-free trajectories, and discrete-time planning can miss collisions between time steps.

    Source: B. Limitations and Associated… · p. 6

Abstract

from arXiv · show

This paper introduces a novel algorithm for multiagent offline trajectory generation based on distributed model predictive control. Central to the algorithm's scalability and success is the development of an on-demand collision avoidance strategy. By predicting future states and sharing this information with their neighbors, the agents are able to detect and avoid collisions while moving toward their goals. The proposed algorithm can be implemented in a distributed fashion and reduces the computation time by more than 85% compared to previous optimization approaches based on sequential convex programming, while only having a small impact on the optimality of the plans. The approach was validated both through extensive simulations and experimentally with teams of up to 25 quadrotors flying in confined indoor spaces.

I. INTRODUCTION

The paper addresses safe multiagent point-to-point transitions and introduces distributed model predictive control with on-demand collision avoidance. It positions this approach against methods whose conservatism, computational demands, or declining success rates limit transition tasks.

I. INTRODUCTION

  • MILP is computationally expensive for large teams, while decoupled SCP uses a sequential greedy strategy whose success rate decreases as agent numbers grow.Other cited approaches include distributed optimization, ORCA, and potential fields, with ORCA potentially conservative and potential fields susceptible to deadlocks.Source: §I · p. 1
  • On-demand collision avoidance resolves only the first predicted collision in the finite horizon, reducing computation time and increasing success rate for transition tasks.The approach uses soft collision constraints within DMPC.Source: §I · p. 2
  • Earlier DMPC collision strategies either restrict agents’ mobility through compatibility constraints or impose separating hyperplanes at every prediction step, limiting transition-task suitability and scalability.Synchronous DMPC had been used for coordination, but not explicitly for point-to-point transitions.Source: §I · pp. 1–2
  • The paper presents a fast DMPC algorithm for multiagent transitions and evaluates it through simulations, quadrotor experiments, and comparisons with existing approaches.The authors report that it is fast enough for on-request midflight trajectory generation with 25 drones.Source: §I · p. 2

II. PROBLEM STATEMENT

The problem is to generate collision-free trajectories from initial to final locations within a specified time while respecting state and actuation constraints. The formulation models agents, constrains their motion and separation, and applies iterative MPC planning to generate trajectories offline.

II. PROBLEM STATEMENT

  • The goal is to generate collision-free trajectories that move N agents from initial to final locations within a given time, subject to state and actuation constraints.The trajectories are generated offline for execution with the Crazyflie 2.0 quadrotor platform.Source: §II · p. 2

A. The Agents

  • Agents are modeled as unit masses in R3 with double-integrator dynamics, using position, velocity, and acceleration states.The simplified quadrotor model uses acceleration as its input; higher-order models can be accommodated with minimum modifications.Source: A. The Agents · p. 2

B. Constraints

  • Motion constraints bound acceleration and keep agents within a specified volume.The volume represents a boundary such as an indoor flying arena.Source: B. Constraints · p. 2

C. Collision Avoidance

  • The collision boundary is an ellipsoid elongated vertically to capture quadrotor downwash, with vertical separation set to c times the minimum xy-plane distance.The formulation uses Θ = diag(a, b, c), with a = b = 1 and c > 1.Source: C. Collision Avoidance · p. 2

III. DISTRIBUTED MODEL PREDICTIVE CONTROL

  • In offline MPC, each agent repeatedly optimizes an input sequence, applies its first input to the model, and may share information with neighboring agents.The model advances to generate the next trajectory state without measuring a physical agent after each input.Source: §III · p. 2

A. The Synchronous Algorithm

The synchronous algorithm shares predicted state sequences before agents simultaneously update their plans. Its prediction model expresses position trajectories over a fixed horizon as functions of the initial state and input sequence.

A. The Synchronous Algorithm

  • At each time step, agents use neighbors’ latest predictions to check for future collisions, add collision constraints only when needed, then apply the first element of each new input sequence to advance the model.The synchronous update repeats until all agents reach their goals.Source: A. The Synchronous Algorithm · pp. 2–3
  • The on-demand strategy includes constraints for the first predicted collisions rather than imposing collision constraints throughout the prediction horizon.The agents share their previously predicted state sequences before simultaneously solving their next optimization problems.Source: A. The Synchronous Algorithm · pp. 2–3

B. The Agent Prediction Model

  • The agent prediction model uses a fixed horizon of length K and denotes predicted values using the information available at the current time step.The prediction index k ranges from 0 to K − 1.Source: B. The Agent Prediction Model · p. 3
  • The position sequence is expressed as an affine function of the input sequence and initial state, using matrices that propagate both contributions across the horizon.The position components are selected from the matrix products used in the prediction representation.Source: B. The Agent Prediction Model · p. 3

C. Objective Function

The objective combines trajectory error, control effort, and input variation penalties. The trajectory error term steers agents toward their assigned goals by reducing position error over the horizon’s last κ time steps.

C. Objective Function

  • The objective combines trajectory error, control effort, and input variation penalties.The formulation describes these as its three main components.Source: C. Objective Function · p. 3

1) Trajectory error penalty:

  • The trajectory error penalty minimizes position error over the horizon’s last κ time steps relative to the desired final position.A larger κ produces more aggressive movement toward goals but may cause overshooting.Source: 1) Trajectory error penalty · p. 3

2) Control effort penalty:

  • The control effort penalty minimizes control effort using a quadratic cost function.A positive definite, block-diagonal matrix weights the control effort penalty.Source: 2) Control effort penalty · p. 3

3) Input variation penalty:

The input variation penalty smooths input trajectories by minimizing acceleration variation. Physical limits are also formulated as constraints on the input sequence.

3) Input variation penalty:

  • Minimizing acceleration variation produces smoother input trajectories.The section expresses this penalty in quadratic form and weights control variation with a positive definite, block-diagonal matrix.Source: 3) Input variation penalty · p. 3

D. Physical Limits

  • Physical limits on the input sequence are formulated as inequality constraints and stacked into AinUi ≤ bin.The constraints combine into a single expression.Source: D. Physical Limits · pp. 3–4

E. Convex Optimization Problem, No Collision Case

When no future collision is detected, each agent solves a quadratic program whose decision-variable and constraint counts are independent of the number of agents. For collisions, the method imposes a relaxed constraint on the first predicted collision, using nearby agents and penalized slack variables.

E. Convex Optimization Problem, No Collision Case

  • With no detected future collisions, the agent solves a quadratic program with 3K decision variables and 12K inequality constraints, independent of N.The problem is subject to the physical-limit constraints AinUi ≤ bin.Source: E. Convex Optimization Problem, No… · p. 4

F. On-demand Collision Avoidance with Soft Constraints

  • On-demand avoidance constrains the first predicted collision rather than incrementally resolving every predicted collision.The method applies collision constraints to a subset of nearby agents treated as obstacles.Source: F. On-demand Collision Avoidance with… · p. 4
  • Collision constraints use bounded relaxation variables whose penalties are added to the objective to account for possible infeasibility.The relaxation variables are bounded by −εmax ≤ εij ≤ 0, and positive tuning parameters set their penalty strength.Source: F. On-demand Collision Avoidance with… · p. 4
  • Imposing the collision constraint one time step after the predicted collision produced more preemptive avoidance and faster transitions on average.This timing choice was based on empirical assessment across a wide range of transition scenarios.Source: F. On-demand Collision Avoidance with… · p. 4

IV. THE ALGORITHM

The algorithm repeatedly solves optimization problems for the agents, updating predicted trajectories until they reach their goals or a maximum time is exceeded. The inner problems can be solved sequentially or in parallel, and the resulting interpolated trajectories undergo a collision safety check.

IV. THE ALGORITHM

  • In the four-agent position-exchange example, the distributed plan is only slightly suboptimal to the centralized plan by the sum of travelled distances.The figure shows predicted positions over a 3-second horizon and the generated trajectories.Source: Figure 2 · p. 5
  • The algorithm repeatedly solves the agents’ optimization problems until all reach their goals or the maximum number of time steps is exceeded.The agent problems in each inner loop can be solved sequentially or in parallel because they have no data dependency.Source: §IV · p. 5
  • The algorithm interpolates a found transition solution to a higher-resolution trajectory and checks it against a user-defined safety limit before execution.If the solution fails the sanity checks, the algorithm returns an empty solution.Source: §IV · p. 5

A. Example Scenario

In a four-agent example, DMPC first detects collisions among direct paths and incorporates them into the optimization, producing a non-colliding plan. Its total travelled distance is close to that of centralized trajectories despite their visibly different paths.

  • The distributed plan’s total travelled distance is only 1.7% greater than the centralized plan’s, despite substantially different trajectories.Source: A. Example Scenario · p. 5

B. Limitations and Associated Mitigation Strategies

The algorithm’s limitations include possible optimization infeasibility, collision-constraint violations, and oscillations or deadlocks. The paper describes parameter adjustments to mitigate infeasibility and collision failures, while noting oscillations in predictions often disappear after a few MPC cycles.

  • Infeasibility occurs when constraint (27) cannot be met within acceleration and relaxation limits; locally increasing εmax until it is satisfied restores feasibility.εmax is reset to its original value once a solution is found.Source: B. Limitations and Associated… · p. 5
  • Soft on-demand collision constraints do not guarantee collision-free trajectories, and discrete-time planning can miss collisions between time steps.Higher ϱ and ζ penalize constraint violations more; oscillations can lead to deadlocks, while higher κ and Q encourage goal-directed motion.Source: B. Limitations and Associated… · p. 6
  • Oscillations often appear in agents’ predictions but vanish after a few MPC cycles and do not appear in generated trajectories.The paper says collision failures can be minimized by balancing goal aggressiveness against penalties for relaxing constraints.Source: B. Limitations and Associated… · p. 6

V. SIMULATIONS

The simulations evaluate DMPC’s collision-avoidance strategies and compare it with SCP-based approaches; the experiments also depict a 25-agent transition scenario. DMPC reports high success across tested densities and substantially lower computation time than the SCP baselines, with longer paths on average.

V. SIMULATIONS

  • The simulation models Crazyflie 2.0 agents and compares cluster counts using mean runtime and standard deviation from 30 successful transitions per swarm size.The simulations used a sequential implementation of Algorithm 1 on an 8-core Intel Xeon PC.Source: §V · p. 6, Figure 5 · p. 7

B. Comparison to SCP-Based Approaches

A. Comparison of Collision Avoidance Strategies in DMPC

  • With fixed workspace density, soft on-demand collision avoidance achieves more than 75% success through 150 agents and outperforms the other two tested strategies.At 200 agents, the reported 55% of failures due to insufficient completion time may reflect transitions infeasible regardless of algorithm; 45% are attributed to more collisions.Source: A. Comparison of Collision Avoidance… · p. 6

B. Comparison to SCP-Based Approaches

VI. EXPERIMENTS

  • The experimental figure depicts 25 agents transitioning from an initial grid to a target ‘DSL’ configuration, with a central static obstacle.Matching circles and diamonds mark initial and final locations; a dashed red box marks workspace boundaries.Source: Figure 6 · p. 7

A. Parallel DMPC

The method parallelizes DMPC optimization across clusters and was tested on quadrotors in a swarm transition. The paper concludes that on-demand collision avoidance supports fast trajectory generation, with only a small impact on plan optimality.

A. Parallel DMPC

  • More than 60% less computation time was achieved with 8 clusters than with sequential execution on an 8-core CPU.The optimization problems within each cluster are solved sequentially; clusters exchange updated predictions and repeat.Source: A. Parallel DMPC · p. 7

B. Swarm Transition

  • Across six trials, the minimum inter-agent distance remained above the collision zone, although it dipped below the warning zone used as a safety margin.The scenario required rmin = 0.25 m and was solved in 1.8 seconds; the warning-zone size is controlled by rmin, which must be chosen carefully for robust execution.Source: B. Swarm Transition · pp. 7–8, Figure 7 · p. 8
  • The experimental agents reached their goals within tolerance and then hovered; the position controller reported a maximum hover error close to 3 cm.Fig. 7 reports maximum and minimum distances over six independent trials, including pairwise and target distances.Source: B. Swarm Transition · p. 8, Figure 7 · p. 8

VII. CONCLUSIONS

  • On-demand collision avoidance with soft constraints supports fast multiagent point-to-point trajectory generation, with only a small impact on plan optimality compared with SCP-based methods.The paper also reports validation on randomly generated transition tasks and experimental results with large quadrotor teams.Source: §VII · p. 8

Related papers

Loading 1809.04230v2…