Car-like Robots Motion Planning by the Fast Marching Method (FMM)

The Robot Motion Planning (RMP) problem deals with finding a collision-free start-to-goal path for a robot navigating among workspace obstacles. Such a problem is also encountered in path planning of intelligent vehicles and Automatic Guided Vehicles (AGVs). In terms of kinematic constraints, the RMP problem can be categorized into two groups of Holonomic and Nonholonomic problems. In the first group the robot can move freely from a point to any other point in the free space, while in the second one the robot’s movement is restricted to a subset of moves, as the constraints of a car for moving sideways. This paper proposes a solution to the RMP problem for car-like robots by the Fast Marching Method (FMM), which is a numerical technique for solving the Eikonal nonlinear partial differential equation. At first a smooth collision-free path is generated without considering the nonholonomic constraints, and then it is adjusted to accommodate the kinematic constraints using the Virtual Obstacles concept, which is a novel contribution. The presented method is fast and exact and finds the optimal path. Comparisons against another nonholonomic graph-search-based method showed the advantage of the new method over it in terms of path length and runtime.