SLPA*: Shape-Aware Lifelong Planning A* for Differential Wheeled Vehicles

Abstract

This paper presents modified A* and Lifelong Planning A* algorithms to facilitate more accurate path finding than existing methods, including the Minkowski sum for differential wheeled vehicles with shape constraints. We use a graphical method to check for obstructions without adding the outline of vehicles to obstacles. The method applies a procedure that enables vehicles to have forward movement with the smallest rotation possible, including their turning directions. Furthermore, we show that vehicles can pass through narrow passages because we accurately check for interference against obstacles using the graphical method. Consequently, we demonstrate via a series of simulations that our method can quickly replan a collision-free path while accurately taking into account the shape of vehicles.