Planning Long Dynamically Feasible Maneuvers for Autonomous Vehicles

Likhachev, Maxim; Ferguson, Dave · 2009 · OpenAlex-citations

DOI: 10.1177/0278364909340445

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper presents an algorithm for generating complex, dynamically feasible maneuvers for autonomous vehicles navigating large, unstructured environments at high speeds (approximately 15 mph). The research addresses the limitations of existing planning approaches, which often suffer from a mismatch between sophisticated local planning and approximate global planning, leading to susceptibility to local minima or excessive computational costs. The authors aim to provide a global planning solution that ensures real-time performance, guarantees bounds on solution suboptimality, and can efficiently repair paths in dynamic environments. The proposed method utilizes a multi-resolution, dynamically feasible lattice state space combined with an anytime, incremental search algorithm. The state space is discretized into four dimensions (x, y, orientation, velocity) and employs a multi-resolution strategy: a high-resolution action space is used near the vehicle and goal to ensure precision, while a low-resolution action space is used elsewhere to reduce computational complexity. The low-resolution actions are a strict subset of the high-resolution ones, ensuring all generated paths remain dynamically feasible. To navigate this space, the authors employ Anytime Dynamic A* (AD*), which generates bounded suboptimal solutions quickly and improves them as deliberation time allows. The search is guided by a combined heuristic that integrates a mechanism-constrained heuristic (pre-computed for empty environments) and an environment-constrained 2D heuristic (computed online based on obstacles). Additional optimizations include pre-computed collision checks using inner and outer radius maps to minimize real-time convolution costs. Experimental results from simulations and an autonomous passenger vehicle that competed in the DARPA Urban Challenge demonstrate the effectiveness of the approach. The vehicle successfully drove over 3,000 kilometers in urban environments, handling parking maneuvers, off-road navigation, and error recovery scenarios. The multi-resolution lattice reduced planning time by more than three times compared to a uniformly high-resolution lattice. The combined heuristic proved an order of magnitude more effective than individual heuristics, significantly reducing the number of states expanded. The anytime nature of the planner allowed for rapid initial path generation (under 100 milliseconds) with subsequent improvement to optimal solutions within seconds. The system also demonstrated robust replanning capabilities, efficiently repairing paths when new static or dynamic obstacles were detected. The significance of this work lies in its ability to bridge the gap between local and global planning for autonomous vehicles. By guaranteeing dynamic feasibility and providing real-time performance with suboptimality bounds, the approach enables safe and efficient navigation in complex, dynamic environments. The multi-resolution lattice and combined heuristic strategies offer a scalable solution for long-distance planning, addressing the computational challenges that have previously restricted global planning to small distances or simple environments. This contributes to the field by providing a robust framework for autonomous driving systems that must reason over large distances and execute complex maneuvers quickly.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• situational awareness