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

arXiv:2611.14299 · eess.SY, cs.SY · Submitted 2026-11-10 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: I'm Rosa.

Dev: And I'm Dev, here with Taro.

Rosa: We're looking at the paper: "Energy- and Time-Efficient Multi-Vehicle Trajectory Planning Using Augmented DAG Search in Configuration Space".

Dev: Here's the gist of the paper. Multi-vehicle trajectory planning for Connected and Autonomous Vehicles (CAVs) requires balancing energy consumption and travel time while ensuring safety and scalability.

Rosa: The proposed framework extends a configurationspace framework to jointly optimize travel time and energy consumption using an efficient augmented DAG search on two-dimensional decompositions of a high-dimensional configuration space.

Dev: This method 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.

Rosa: Problem Formulation The coordination problem is formulated in configuration space where the joint configuration of all vehicles is represented by a vector s.

Title and authors: Rosa: So we're looking at this paper now, "Energy- and Time-Efficient Multi-Vehicle Trajectory Planning Using Augmented DAG Search in Configuration Space." It seems like the authors are tackling that classic trade off between getting there fast and not burning too much energy.

Dev: Yeah, exactly. The core idea is extending the configurationspace framework to do a joint optimization of both travel time and energy consumption simultaneously. They're looking at how to make this work for a lot of vehicles without it just becoming computationally impossible for big traffic scenarios, which is where most existing methods fail.

Taro: I'm curious about what they mean by "augmenting" the DAG search states with incoming segment velocities. That sounds like they are trying to get richer information into the search process to make better decisions.

Rosa: Right, that augmentation is key because it lets them build a more complete picture of what's happening in the configuration space as they plan out their movements for all these vehicles at once. It’s about making sure the search isn't just looking at static positions but also how fast things are moving into those positions.

Dev: And they’re using this augmented graph search on two-dimensional decompositions of a high-dimensional space to manage that complexity, which they claim scales up to forty vehicles. That’s a big jump from what you see in prior work when you have many interacting agents.

Taro: So it's about transforming the massive configuration space problem into a sequence of smaller graph searches, which reduces the combinatorial search needed for collision checking significantly. That sounds like they’re trying to keep the complexity manageable while still getting good results.

Rosa: And they introduce this objective function that mixes travel time and an energy term based on kinetic energy variations and aerodynamic drag, instead of just relying on a specific fuel consumption map for the car's powertrain. This makes it more physically motivated in terms of how we actually use the vehicle.

Dev: That physical term is important because it captures things like unnecessary acceleration and stop-and-go driving that really drive up fuel use, which aligns with eco-driving studies they reference. It’s not just a guess about fuel consumption; it's based on real physics of motion twenty, twenty-one <ref:2611.14299#pg2>.

Title and authors: Taro: But what about the actual execution? If the planner spits out these optimal trajectories, how does the vehicle actually follow them when there are unexpected things happening on the road? That’s where I always look.

Rosa: They pair this high-level planning with a Nonlinear Model Predictive Control framework for each individual vehicle, which lets those low-level controllers track the reference paths generated by the planner while respecting physical constraints. It’s about making sure what's planned actually happens safely and smoothly.

Dev: And on the implementation side, they introduce something called Planner Guided Greedy Ordering or PGGO. This is supposed to be a deterministic rule that decides which vehicle goes where in the sequence of planning, based on some score psi that looks at conflict geometry and mass.

Taro: A deterministic ordering heuristic sounds good for real-time systems because you don't want the planner spending too much time searching through all possible permutations of vehicle orders. It should give us a predictable path to follow.

Rosa: The paper suggests this PGGO method is stronger than just looking at static pairwise conflicts on its own when deciding that insertion order, claiming it captures a lot of the ordering benefit deterministically in under a second for well-defined scenarios.

Dev: That speed is what matters for real-time operation. But they also talk about incremental planning, where they solve these reduced two-dimensional problems one vehicle at a time to build the overall plan sequentially. That sounds like a way to manage the computational load step by step rather than trying to solve everything at once.

Taro: Incremental coordination means that when you add a new car, you only have to re-solve the problem involving that new vehicle and what's already planned for everyone else, which is much more efficient than restarting from scratch every time.

Rosa: Exactly. They claim this incremental approach retains a worst-case complexity of O(N r cubed), where N is the number of vehicles and r is the number of conflict regions, which they say covers every scenario size they tested. That’s a strong scaling claim for large numbers of agents.

Title and authors: Dev: So to wrap up on the methodology, we've talked about augmenting search states, using PGGO for ordering, and employing an incremental approach with that specific complexity bound. The results show that when you tune the weighting parameter lambda between zero point six and zero point eight, you get a good balance between getting through an intersection quickly and saving energy compared to just being time-optimal.

Taro: I wonder what happens if the world misbehaves, like a vehicle suddenly brakes hard or cuts across a lane unexpectedly? Does this planner handle those dynamic changes gracefully when it’s already running?

Rosa: The NMPC controllers are designed to track the planned trajectories generated by the planner, and they solve a finite-horizon optimal control problem to minimize the deviation from that reference trajectory while staying within physical limits. This is how they ensure that even with those dynamic disturbances, you get executable reference motions.

Dev: So, it seems this paper provides a framework where you can jointly optimize energy and time for multi-vehicle planning using an augmented DAG search and a planner-guided greedy ordering heuristic, all while keeping the computational complexity manageable at O(N r cubed).

Taro: It gives us a way to plan for more vehicles in dense intersections that respects both performance metrics without resorting to overly complex optimization methods.

Rosa: Yeah, and it shows that even with a decent trade-off, modest concessions on travel time can still lead to substantial energy savings when you look at the physical models they used.

Dev: It’s a solid piece of work for showing how geometric formulations can help tame the high dimensionality of these configuration spaces in motion planning problems.

Taro: It sets a good benchmark for how to handle coordination when you’ve got a growing number of autonomous vehicles interacting in complex environments like intersections.

Rosa: Right, so that's the gist of "Energy- and Time-Efficient Multi-Vehicle Trajectory Planning Using Augmented DAG Search in Configuration Space." We'll be looking at some other papers on scalability next time.

The paper's summary: Rosa: So, we just talked about how this paper uses augmented graph search to plan for multiple vehicles at once, balancing travel time and energy use. Now let's look at what they actually found in terms of results and how it changes things for us on the ground.

Dev: Okay, so the core thing is that they took a whole bunch of vehicles—say forty of them—and instead of trying to find one perfect path for everyone at once, which would be impossible, they broke it down into smaller problems. They use this two-dimensional decomposition of the configuration space.

Taro: Breaking it down sounds like a strategy for managing complexity. So how does that translate when you're actually moving cars around an intersection? Does it just make the search faster, or does it change *what* kind of paths they find?

Rosa: It changes what kind of paths they find because they’re looking at collisions in a way that considers where things are coming from. They define conflict regions based on those two-dimensional slices, and then they use this augmented search to plan the sequence and the geometry simultaneously.

Dev: And the objective function is weighted. It combines travel time—how fast you get there—with an energy term based on things like kinetic energy variations and drag, instead of just a simple fuel map for each car. That means it’s trying to be physically realistic about how much energy you actually use while moving.

Taro: So they aren't just optimizing for the shortest time; they are optimizing for the most efficient movement given the physics of motion. What did their simulations show when they tuned that weighting factor, lambda?

Rosa: They found a sweet spot in that parameter lambda, between zero point six and zero point eight. This range gives a good compromise between getting through an intersection quickly and demanding less energy overall compared to just picking the absolute fastest route.

Dev: And this is important because they showed that when you use their ordering heuristic—the planner guided greedy ordering—it captures most of the benefit for those vehicle orders deterministically in under one second, which is pretty fast for real-time planning.

Taro: That speed on the ordering part is a big deal. I mean, if you need to re-plan every few milliseconds when things change, you need that kind of quick decision making. But what about the world misbehaving? If a vehicle suddenly brakes hard or swerves unexpectedly while this plan is running?

Rosa: That's where the NMPC comes in. Each individual vehicle has its own controller that tracks the reference trajectory generated by this high-level planner. The NMPC solves a control problem every little bit of time to keep the car on track, even if there are disturbances, as long as those disturbances stay within physical limits.

Dev: So it’s a two-layer approach: this complex planner sets the overall goal and sequence, and then these local controllers handle the immediate physics and safety constraints. That's how they ensure executable motions.

Taro: What's the limitation here? The paper doesn't exactly say it handles *any* kind of unpredictable chaos perfectly. It’s built around optimizing traffic flow in a dense intersection scenario, which is a very specific environment.

Rosa: Right, so it works really well for dense intersections where you have many vehicles interacting, and it scales to forty cars. But the authors are clear that extending this to mixed traffic with human-driven vehicles or explicitly modeling communication would be the next big step in their research.

The paper's improvements: Taro: So we've looked at how they planned the vehicles and what their results showed in terms of trade-offs between speed and energy use. Now let's talk about what they suggest to make this framework even better, specifically the improvements they propose for this whole system.

Rosa: They are proposing a few key upgrades to the core planning method that you can hear about in this paper. First, they want to augment the graph search states with incoming segment velocities. This means when the planner is looking at a potential path, it doesn't just see where things are; it also sees how fast other vehicles are moving into those spots.

Dev: That’s right, so you get that joint optimization of travel time and energy consumption happening right inside the graph search process itself. It makes the search much smarter about predicting future states without needing separate calculations later.

Taro: And they talk about an incremental algorithm here too, where instead of solving the entire problem for all forty vehicles at once, they solve it step by step as each new vehicle is added to the plan. This is called incremental coordination.

Rosa: Exactly, which means when you add a new car, you only need to re-solve a smaller problem involving that single new vehicle and the existing planned trajectories of everyone else already coordinated. It’s much more efficient for real-time use than starting over every time.

Dev: They also introduce this Planner Guided Greedy Ordering, or PGGO heuristic, as an improvement to how they build that sequence of vehicles. It’s a deterministic rule that decides the insertion order by looking at things like conflict geometry and mass. This replaces having to check every single possible way you could order the vehicles with a huge search.

Taro: So it’s making the ordering decision faster and smarter, based on reduced space conflict geometry between each vehicle and the group of others it's joining, which sounds like a much more practical heuristic than just looking at static pairwise conflicts alone.

Rosa: And they want to ensure collision-free feasibility is maintained during this incremental process by adding a second-order graph search augmentation. They incorporate those energy and time costs directly into the edge costs of the graph search, which is what helps them maintain that worst-case complexity of O(N r cubed).

Dev: That complexity bound is important because it tells us exactly how much computational muscle this framework needs to handle as you add more vehicles or if you have more conflict regions. It gives us a solid safety case for its scalability.

Taro: So the goal here is to have a system that not only plans efficiently but can also adapt incrementally and maintain a predictable performance ceiling even when the number of interacting agents gets large.

Rosa: That’s it, so they are focusing on making the system more robust for real-world deployment by improving both the planning logic and the way it handles growth. But we still have to remember what they didn't do, which is explicitly modeling communication between vehicles or dealing with human drivers yet.

Conclusion: Rosa: So we’ve covered how they used augmented graph search and those greedy ordering rules to plan for multiple vehicles, balancing travel time and energy use in dense intersections. Now let's wrap up what this means for us on the ground.

Dev: The paper shows that you can get a high-performance plan while actually keeping an eye on energy consumption using a method that scales reasonably well, even up to forty vehicles. That’s important because it moves beyond just finding the fastest route and makes it more responsible in terms of fuel use.

Taro: I think what this really changes for autonomous systems is that you can plan for complex coordination without needing an impossibly huge search space upfront. It gives us a structured way to tackle the massive configuration space problem in motion planning.

Rosa: That’s right, the idea is that this framework allows for scalable energy-aware trajectory planning, giving us better performance when we need it most in congested areas. It moves the needle on how we design these coordinated systems.

Dev: And for anyone working on real-time loops, knowing that the worst-case complexity is O of N r cubed gives us a good number to work with when designing our safety cases and latency budgets. It helps us predict how much computation we’re actually going to need.

Taro: It sets a baseline for what scalable coordination looks like in these scenarios, but it also flags the areas where they haven't reached yet, like handling human drivers or communication delays.

Rosa: Exactly, so while this paper tackles the core planning and optimization of the multi-vehicle trajectory planning problem, future work is clearly looking at extending this framework to mixed traffic or integrating communication models.

Dev: We’ll be interested to see how they handle those additions because that’s where real-world deployment gets messy and things don't always go according to the math.

Taro: I’m curious about what happens when you start throwing in human-driven vehicles, because that introduces a whole new set of unpredictable behaviors into the system.

Rosa: Well, for now, this work on Energy- and Time-Efficient Multi-Vehicle Trajectory Planning Using Augmented DAG Search in Configuration Space gives us a strong foundation for making these plans smarter and more efficient today.

Dev: It’s solid work that proves geometric formulations can help tame the high dimensionality of these configuration spaces when you’ve got many interacting agents.

Taro: Yeah, it's a good step forward in showing how to manage complexity without just throwing brute force math at the problem.

Amirreza Akbari, Galina Sidorenko, Johan Thunberg

Department of Electrical and Information Technology, Lund, Sweden

eess.SY, cs.SY

Submitted: 2026-11-10

Updated: 2026-11-10

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

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 81/100

The gist: Multi-vehicle trajectory planning for Connected and Autonomous Vehicles (CAVs) requires balancing energy consumption and travel time while ensuring safety and scalability.

Key concepts

Configuration Space
This is a mathematical space where the positions of all vehicles are represented by a single vector. It allows the system to model the complex interactions and potential collisions between multiple cars simultaneously, treating them as points in this combined space.
Energy-Aware Objective Function
Instead of just minimizing travel time, this function minimizes a weighted combination of travel time and an energy term. This energy term is based on physical models of vehicle speed and acceleration rather than relying on specific fuel consumption maps, providing a realistic measure of energy usage.
Energy–Travel-Time Augmented DAG Search
This is the core planning algorithm. It modifies the standard graph search by adding information about incoming segment velocities to its states. This allows the search to simultaneously optimize for both how fast vehicles can travel and how much energy they will consume along a planned path.
Planner-Guided Greedy Ordering (PGGO)
This is a rule used to decide the sequence in which vehicles should be inserted into the overall plan. It uses a calculated score that considers conflict geometry, graph structure, and vehicle mass to deterministically select the next vehicle for insertion, improving planning efficiency.

Terminology

Summary

Multi-vehicle trajectory planning for Connected and Autonomous Vehicles (CAVs) requires balancing energy consumption and travel time while ensuring safety and scalability. p. 0 The proposed framework extends a configurationspace framework to jointly optimize travel time and energy consumption using an efficient augmented DAG search on two-dimensional decompositions of a high-dimensional configuration space. p. 0 This method 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. p. 0

Problem Formulation

The coordination problem is formulated in configuration space where the joint configuration of all vehicles is represented by a vector s. Potential collisions are defined as conflict regions Okij in the two-dimensional subspace [0, s¯i] × [0, s¯j]. p. 1 The complete conflict set is then defined as O = [ikij]. p. 2

Energy-Aware Objective

The objective function minimizes a weighted energy–travel time objective combining travel time and a physically motivated energy term. This expression involves positive kinetic-energy variations and aerodynamic drag rather than modeling a powertrain-specific fuel-consumption map. p. 2 The energy term is consistent with microscopic fuel-consumption and emission models based on vehicle speed and acceleration. p. 2

Energy–Travel-Time Augmented DAG Search

The core algorithm develops an incremental planning algorithm that augments the visibility DAG states with incoming segment velocities and velocity-dependent edge costs. This enables joint optimization of travel time and energy consumption within the graph search trajectory planning. p. 1 The resulting algorithm retains a worst-case complexity of O(Nr3) where N is the number of vehicles and r is the number of conflict regions for the vehicles. p. 1

Planner-Guided Greedy Ordering

The Planner-Guided Greedy Ordering (PGGO) heuristic is a deterministic rule that builds the insertion order sequentially by selecting the next vehicle based on a score Ψ(˜i G). This score encodes information from reducedspace conflict geometry, graph-based criteria, and mass. p. 5 The PGGO method is shown to be markedly stronger than static pairwise conflict information alone in determining a competitive order. p. 8

Controller Design

A Nonlinear Model Predictive Control (NMPC) framework is employed for each vehicle to track the reference trajectories generated by the highlevel planner. The NMPC solves a finite-horizon optimal control problem to minimize the deviation from the reference trajectory while satisfying physical constraints. p. 6

Numerical Results

Simulations on a 20-vehicle scenario demonstrate that intermediate values of λ, especially λ = 0.6–0.8, provide a favorable compromise between intersection throughput and energy demand. p. 8 PGGO alone captures a large and increasing share of the ordering benefit deterministically in well under a second. p. 8 The proposed planner is the only method that scales across the entire range and solves every scenario size. p. 9

Conclusion

This paper presents a scalable framework for jointly optimizing energy consumption and travel time in multi-vehicle trajectory planning. The proposed approach enables scalable energy-aware trajectory planning. p. 4 Future work will extend the framework to mixed traffic involving human-driven vehicles and explicitly account for communication and connectivity.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Augment configuration space graph search states with incoming segment velocities to enable joint optimization of travel time and energy consumption within trajectory planning. This allows for joint optimization of travel time and energy consumption within the graph search trajectory planning.

  2. Implement a Planner Guided Greedy Ordering (PGGO) heuristic to deterministically construct the vehicle insertion order by selecting the next vehicle that minimizes a complex insertion score. This replaces intractable exhaustive search over permutations with a rule based on reducedspace conflict geometry between the candidate and the group (D, Γ, V,Ξ).

  3. Develop an incremental algorithm that solves reduced two-dimensional planning problems sequentially for each vehicle insertion step. This procedure allows for incremental coordination, where each addition requires solving only a problem involving the new vehicle and the aggregate trajectory of previously coordinated vehicles.

  4. Integrate a second-order graph search augmentation in the incremental algorithm to ensure collision-free feasibility while incorporating energy and time costs directly into edge costs, yielding a worst-case complexity of O(Nr3). This results in an algorithm that retains a worst-case complexity of O(Nr3).

  5. Utilize the NMPC framework with vehicle dynamics models to track the planned trajectories generated by the high-level planner. This ensures that the planned trajectories can be tracked by the low-level controller with bounded control effort, confirming that the proposed configuration-space planner produces executable reference motions.

Related papers