From videogames to autonomous trucks: A new algorithm for lattice-based motion planning

Abstract

Autonomous navigation in real-world environments is still a challenging task in many respects. One of the key open challenges is fast planning of physically executable complex maneuvers under non-holonomic constraints. In recent years, lattice-based motion planners have been successfully used to generate kinematically and kinodynamically feasible motions for non-holonomic vehicles. However, it is not clear yet what algorithms are best to efficiently explore the lattice state space, while at the same time ensuring real-time performance. Here, we show how motion planning can greatly benefit from tapping into the latest results in path planning on grids, and we present a new version of Time-Bounded A*. Our version is designed to work for high-dimensional motion planning problems in real-world robotic applications. We demonstrate our algorithm in simulation and on a full-size autonomous truck.