CS Paper Radar

Energy- and Time-Efficient Multi-Vehicle Trajectory Planning Using Augmented DAG Search in Configuration Space

Amirreza Akbari, Galina Sidorenko, Johan Thunberg

eess.SY ·submitted 2026-11-10 16:34 UTC · v1

Abstract

Multi-vehicle trajectory planning for CAV requires balancing energy consumption and travel time while ensuring safety and scalability. While travel-time-optimal methods based on Integer Programming exhibit poor scalability in large-scale multi-vehicle scenarios, existing energy-oriented approaches fail to balance energy consumption and travel time. We extend a configuration-space framework for multi-vehicle trajectory planning to jointly locally optimize travel time and energy consumption. A weighted energy-travel time objective is combined with an efficient augmented DAG search on two-dimensional decompositions of a high-dimensional configuration space, enabling scalable and collision-free coordination of large numbers of vehicles. Although the proposed framework is applicable to other traffic scenarios, such as roundabouts and vehicle-following, we focus on intersections as a representative and challenging planning problem. To further improve performance for our methodology, we also extend the method with an insertion-ordering heuristic that exploits reduced-space geometric information. Combined with nonlinear model predictive control, the proposed framework is shown to scale to 40 vehicles, outperform MILP-based and convex optimization baselines in dense intersections, and reduce energy consumption at equalized travel times relative to time-optimal planning.

Comment
This manuscript is currently under review at IEEE Transactions on Intelligent Transportation Systems

Closest papers

Nearest neighbours by meaning across the whole index.

A heuristic for optimal coordination of autonomous vehicles: static problems

eess.SY ·2026-10-27 ·Saugat Shahi, Filippo Fabiani, Mario Zanon
similarity 0.71
Abstract

We consider the coordination of autonomous vehicles at unsignalized intersections, where trajectory planning and crossing-order decisions are intrinsically coupled, thereby making their simultaneous optimization intractable in practice. To this end, we propose a heuristic based on a hierarchical structure consisting of a series of nonlinear programs (NLP) in the lower level, which optimizes trajectories of each vehicle for a given crossing order, and a high-level heuristic to design new crossing schedules that exploits sensitivity information from the lower-level NLPs. Extensive numerical simulations across a broad range of traffic scenarios demonstrate that our strategy achieves substantially improved scheduling with respect to first-in-first-out ordering while preserving computational tractability.

0.57

A heuristic for optimal coordination of autonomous vehicles: dynamic problems

eess.SY ·2026-10-27 ·Saugat Shahi, Filippo Fabiani, Mario Zanon
similarity 0.70
Abstract

The coordination of autonomous vehicles at unsignalized intersections requires deciding both the trajectories of the vehicles and their crossing order, with the additional difficulty that the set of vehicles to be coordinated changes as traffic flows through the intersection. Since the resulting mixed-integer optimal control problem is hard to solve online, we propose an arrival-triggered receding-horizon scheme built around a schedule-refinement heuristic: for a fixed crossing order, a single nonlinear program (NLP) optimizes all trajectories and crossing times, and the first-order sensitivities of the cost with respect to the vehicle schedule are used to select adjacent swaps that are likely to reduce the overall cost. Replanning is triggered only when a new vehicle arrives, the new vehicle is appended at the tail of the current crossing order, and a memory of evaluated swaps that persists across replanning steps avoids redundant computations. Simulations of traffic scenarios involving streams of a few hundred heterogeneous vehicles show that the proposed scheme recovers most of the optimality gap incurred by first-in-first-out scheduling.

0.52

Learning Waypoints and Passage Events for Decentralized Multi-Quadrotor Trajectory Planning

cs.RO eess.SY ·2026-10-18 ·Yunhan Shi, Jia Deng, Zehao Jia, Lin Cheng, Shengping Gong
similarity 0.68
Abstract · 9 pages, 7 figures, 3 tables

Multi-quadrotor passage planning requires coordinated spatial routes and passage times under vehicle dynamics and actuation constraints. Optimizing these decisions jointly couples temporal allocation, nonlinear motion, and inter-vehicle interactions, creating a computational challenge for local trajectory generation. We propose a learning-optimization framework that predicts spatial waypoints and ordered passage events for independently solved quadrotor planners. A common physical time grid aligns the vehicles, with intermediate events fixed by the networks and terminal progress optimized locally to permit different completion metrics. Differentiable sequential convex programming incorporates rigid-body dynamics and rotor-thrust bounds, allowing collision and completion gradients to train both networks through the generated trajectories. In a two-quadrotor evaluation across 24 layouts, the adapted policy passes physical feasibility and sampled separation checks in all five held-out layouts. Their mean completion metric decreases by 1.52% relative to the inherited policy. The median forward time is 21.01 ms on the held-out exchange layout with matching numerical trajectory references. These results demonstrate that learned spatial and event parameters can coordinate independent rigid-body planners while preserving local vehicle constraints in the evaluated scenarios.

0.13

Vehicle Platooning

cs.CC math.OC ·2026-08-10 ·Zhi-Long Chen, Nicholas G. Hall
similarity 0.65
Abstract · 41 pages, 0 figures, 3 tables

Vehicle platooning offers significant benefits, including reduced energy consumption, lower emissions, improved road utilization, enhanced safety, and reduced driver fatigue. As intelligent driving technologies continue to advance, platoon sizes are expected to increase substantially, making the efficient sequencing and resequencing of vehicles increasingly important. We study the vehicle platoon sequencing and resequencing problem on road networks with varying segment lengths under two fundamental objectives: minimizing total energy consumption and minimizing the maximum energy consumption of any vehicle. For the typically encountered combinations of vehicle and road characteristics, we provide a complete computational complexity classification, either developing polynomial-time algorithms or proving computational intractability. For several intractable cases, we design fully polynomial-time approximation schemes and polynomial-time heuristics with provable performance guarantees. A computational study demonstrates that the proposed heuristics achieve average solutions within 1\% of optimal. We also consider settings in which only limited information about position-dependent energy savings is available and develop a heuristic with bounded worst-case performance. In addition, we present an efficient algorithm for on-road vehicle resequencing when only limited position changes are permitted. Together, these results provide a comprehensive algorithmic framework for energy-efficient vehicle platoon sequencing and resequencing.

0.38

Dynamics-Aware Adaptive Corridors with Feasibility-Perturbed Trust-Region SQP for Certified Nonholonomic Motion Planning

cs.RO eess.SY ·2026-10-05 ·Yang Shi
benchmark similarity 0.65
Abstract

Optimisation-based parking planners usually impose collision constraints only at the time samples, so a vehicle corner can cut an obstacle between samples, and no executable trajectory exists until the solver converges. We present a planner for car-like vehicles with reverse gear in which every iterate of the optimisation phase satisfies the discretised dynamics exactly and keeps the whole vehicle rectangle clear of obstacles between the samples. Each time interval receives one convex corridor that holds all vehicle corners at both ends and is shrunk by a sweep margin bounding how far the corner paths leave their chords. Separating half-planes give the corridors a direction out of obstacles when the initial guess is in collision; later, heading-aligned boxes are grown from the speed, curvature and step of the current iterate and rebuilt after accepted steps. A feasibility-perturbed trust-region sequential quadratic programming method projects each step onto the dynamics by feedback and verifies it exactly; the cost decreases monotonically, and once the corridors stop changing, limit points are Karush-Kuhn-Tucker points of the corridor-constrained problem or violate a constraint qualification. On 820 benchmark cases the planner succeeds in 818 without penetration (797 from the first initial guess), none of the 7103 evaluated optimisation-phase iterates is unusable, and it succeeds in 96.5% of the cases when 99% of the initial guesses intersect an obstacle. Its maneuvers take 0.7% longer in the median than those of a similarly certified exact-collision baseline. The guarantees hold for the planning model, not for a physical vehicle.

0.32

A Collision-Aware Predictive Rerouting Framework for Connected and Automated Vehicles

eess.SY ·2026-10-13 ·Tony Kinchen, Ting Bai, Andreas A. Malikopoulos
benchmark similarity 0.64
Abstract · 15 pages

In this paper, we investigate the problem of mitigating non-recurrent congestion in urban transportation networks through predictive and adaptive routing for connected and automated vehicles (CAVs). We propose a collision-aware predictive rerouting framework that integrates microscopic SUMO simulation, DCRNN-based spatiotemporal traffic-state forecasting, collision-window lookahead, and multi-objective route scoring. The routing controller uses predicted congestion, live emission information, route-length penalties, and incident-window constraints to decide when CAVs deviate from their current routes. The completed simulation campaign across three urban network scenarios, five CAV penetration levels, three random seeds, and multiple benchmark rerouting strategies shows that the proposed full framework does not dominate all baselines in aggregate travel time, distance, or emissions. Instead, its principal advantage is operational stability: it maintains comparable network-level efficiency while substantially reducing rerouting frequency relative to active rerouting baselines. These results demonstrate both the promise and the tradeoffs of embedding graph-based prediction and collision awareness into real-time CAV rerouting, and they motivate further work on forecast calibration, uncertainty-aware prediction, and system-level fairness between CAV and non-CAV traffic.

0.11

Driving Context-guided Model Predictive Planning and Control for Autonomous Car Racing at the Limit and Beyond

cs.RO eess.SY ·2026-09-11 ·Ayoub Raji, Federico Sacco, Nicola Musiu, Marko Bertogna
published similarity 0.64
Abstract · Accepted to IEEE/RSJ International Conference on Intelligent Robots & Systems - IROS 2026

This paper presents a Model Predictive Control-based motion planning and control pipeline for autonomous car racing capable of adapting to different driving contexts, such as overtaking, nominal driving, and countersteering. A Cost Blending state machine manages the identification of different driving contexts and the selection of their predefined weights to be applied to the Model Predictive Planning (MPP) and Control (MPC) modules. The two optimization-based solutions share the same problem formulation and model, differing only in horizon length, rate, tuning, and in their open-loop versus closed-loop approach to maximize the effectiveness of their interaction. The work is validated on the fully autonomous open-wheel racecar Superformula EAV-25, with a lap time achieved that is within 2% of the best human driver reference. The results demonstrate the capability of the solution in driving at the limit of handling, smoothly executing overtaking maneuvers, and quickly reacting to high oversteering conditions to recover the vehicle stability.

0.31

Learned Terminal Costs for Short-Horizon Model Predictive Control of Autonomous Trucks in Interactive Highway Traffic

cs.LG cs.AIcs.ROeess.SY ·2026-10-29 ·Hooman Hamze, Benjamin Houshmand, Deepthi Pathare, Erik Börve, Morteza Haghir Chehreghani +1 more
similarity 0.63
Abstract · 13 pages, 2 figures, 8 tables

Autonomous highway driving for heavy-duty trucks is a challenging control problem. The greater mass, dimensions and intricate dynamics increase the requirements for cooperation from surrounding traffic in critical maneuvers, requiring a careful balance between safety constraints and efficient long-horizon decision making. Model Predictive Control (MPC) provides rigorous constraint satisfaction but relies on terminal cost which can limit its effectiveness at short, computationally affordable horizons. Reinforcement Learning (RL) captures long-term driving behavior but offers no constraint guarantees and tends toward overly conservative policies when trained under sparse collision penalties. In this paper, we propose a hybrid MPC and RL framework for highway driving in autonomous trucks, where a finite-horizon MPC, solved via dynamic programming, uses a pre-trained RL model for terminal cost estimation. We evaluate the framework in a simulation environment with reactive surrounding traffic and compare it against pure MPC with zero terminal cost, rollout with terminal cost estimation using a base policy, and pure RL. Results show that the hybrid approach achieves zero collisions with the lowest cost of any configuration.

0.12