TL;DR
This paper tackles the challenge of real-time path planning for autonomous vehicles navigating dynamic environments. They introduce a novel approach combining software-based memoization using Morton codes with a hardware acceleration for this memoization, significantly speeding up the path planning process.
What Problem Does This Paper Address?
Autonomous driving systems need to plan paths that are not only safe and efficient but also computed within strict real-time constraints (typically under 100ms). This becomes particularly challenging when dealing with dynamic obstacles, such as other vehicles and pedestrians, whose positions change over time. Traditional path planning algorithms, especially those that consider the time dimension (making them effectively 3D or higher-dimensional problems), can become computationally prohibitive, taking hundreds of milliseconds even on powerful hardware. Existing hardware accelerators often focus on specific algorithms and lack flexibility, while software optimizations can still be bottlenecked by time-consuming nearest neighbor searches and collision detection.
Methods
The core of the proposed solution lies in memoization, a technique to store and reuse results of expensive computations. The authors introduce two key components:
- Software-based Memoization with Morton Codes:
- Morton Codes: They map 3D points (x, y, time) into a 1D space using Morton codes (also known as Z-order curves). This mapping preserves spatial locality, meaning nearby points in 3D tend to have nearby Morton codes.
- "Morton Store": This is a data structure that stores information about recently processed tree nodes and obstacles, indexed by their Morton codes.
- Pruning: Before performing expensive baseline nearest neighbor (NN) searches and collision detection, the system first checks the Morton store. If a relevant entry is found (a "hit"), the pre-computed result can be reused, skipping the baseline computation. If not (a "miss"), the baseline computation is performed, and its results are then stored in the Morton store for future use.
- Masking: To adjust the granularity of the Morton code indexing, they mask the least significant bits of the Morton code.
- Hardware-Assisted Memoization:
- To further accelerate the Morton store operations (lookup and update), they propose a hardware implementation using a fully-associative content-addressable memory (CAM).
- This hardware Morton store directly handles Morton code calculations and lookups, drastically reducing the dynamic instruction count compared to software implementations.
- They define new Instruction Set Architecture (ISA) extensions (
morton_update,morton_col,morton_nn) to allow the CPU to interact with this hardware Morton store.
Datasets
The paper evaluates their approach using:
- Synthetic Test Cases: These are generated scenarios characterized by map edge length, number of time steps, and number of dynamic obstacles. The authors provide an example visualization of such a test case.
- Commonroad Benchmark: They use a realistic scenario ("USA_US101-20_1_T_1") from the Commonroad dataset, which includes real-world traffic data with dynamic obstacles.
Key Insights and Ideas
- Morton Codes for 3D Indexing: The insight that Morton codes can effectively map the spatio-temporal domain of autonomous driving path planning into a lower-dimensional space for efficient indexing is crucial. This allows for faster lookups and comparisons.
- Hardware Acceleration for Memoization: Recognizing that even software-based memoization can be a bottleneck, the move to hardware (CAM) for the Morton store operations is a significant step. This directly addresses the instruction-level overhead of software implementations.
- Algorithm-Hardware Co-optimization: The paper emphasizes the synergy between optimizing the path planning algorithm (using Morton codes for indexing) and co-designing hardware (CAM-based Morton store) to accelerate these specific algorithmic optimizations.
- Flexibility through ISA Extensions: By defining ISA extensions, the approach aims to be more flexible than fixed-function hardware accelerators, allowing adaptation to different path planning algorithms that can leverage Morton code indexing.
Key Results
The proposed approach demonstrates significant performance improvements:
- Software-based Morton Store: Achieved an average of 1.96x performance improvement over the baseline RRT algorithm in software simulations.
- Hardware-Assisted Morton Store: Showed an average of 8x performance improvement over the baseline RRT in gem5 simulations. In the best case, this improvement reached 56.3x.
- Commonroad Benchmark: The hardware-based approach achieved a 35x reduction in execution time compared to the baseline.
- Solution Path Length: The memoization-based approaches (both software and hardware) sometimes resulted in slightly longer solution paths (1.42x and 1.65x respectively) compared to the baseline. The authors attribute this to the "approximate nearest neighbor" nature of the Morton code lookup, which might not always find the exact nearest neighbor, leading to more circuitous paths. They suggest path refinement as a potential solution.
Limitations and Future Work
- Solution Path Length: As noted above, the approximate nature of the Morton-based NN search can lead to longer solution paths. Future work could involve path refinement techniques to optimize path length after the initial planning.
- Flexibility: While the ISA extensions aim for flexibility, the current implementation and evaluation focus on RRT. Extending this to other sampling-based algorithms like PRM is mentioned as a possibility.
- Hardware Implementation Details: The paper describes the hardware concept and simulation but doesn't detail the physical implementation of the CAM or the full system integration.
The authors suggest that their hardware-assisted memoization approach can be applied to other sampling-based planning algorithms beyond RRT.
Summary updated