Hardware-accelerated
path planning

Distance field and heuristic

The distance field and heuristic of the A* algorithm are calculated using an altered version of the FM² method introduced by Garrido et al., taking advantage of the wave-like expansion of a queue-based breadth-first search.

The original C++ obstacle flood spreads a proximity cost from obstacles. A second C++ flood accumulates distance and painted-line costs from the goal. Inspect either field while the vehicle search runs independently in a browser worker.

Non-holonomic expansion

Cars are not holonomic, requiring non-holonomic exploration. A car can go forwards or backwards, turning by a smaller angle than its maximum turning angle.

Each search state includes position, body heading, velocity sign and gear. Curved motion is collision-checked along its full length against the car’s actual rectangle at its current heading. A route succeeds only within the requested goal-position and heading tolerances, with matching final motion. The distance estimate includes unavoidable turning and gear changes.

Lane direction and markings

The thesis left directional bias to future work: “What is needed on the path planning side for this is an input in the form of a cost map rather than a bitmap.” This version adds that cost map.

Lane markings have a crossing cost. Lane direction adds a continuous heading penalty: adjoining road vectors blend through intersections, and the car’s body heading determines its lane preference. In reverse, the car also pays most of the wrong-way cost for the direction it is actually moving, so shunting back and forth to tighten a turn costs something. Grey lines show every expanded search edge. Orange shading shows combined lane and marking cost in the same units used by search, updated as the car turns.

Results on the ZCU102

The accelerated path planner planned 699 test paths in less than 30 ms per path, with the average path taking less than 8 ms to calculate. The speedup from hardware acceleration in comparison to the low-power ARM processor on the development board is sixfold; compared with the Ryzen 1600 on the development machine, which provides similar speeds, the efficiency improvement is fourfold.