Grid Search based path planning for mobile robots with kinematic and shape constraints

Abstract

This thesis presents algorithms that can be inserted into the conventional A* or Lifelong Planning A* (LPA*) algorithms to facilitate accurate path finding for quasiholonomic (or holonomic) and nonholonomic mobile robots. For a mobile robot to safely avoid obstacles in complex environments that have many obstacles, its shape should be taken into account by path planners. However, prior works have problems that a mobile robot cannot pass through a narrow passage if it is rectangular in shape and its computed radius is larger than the width of the passage. For quasiholonomic mobile robots, this thesis proposes an A* (and LPA*) based path planning method in which the forward movement of the mobile robot is favored over the reverse because cameras are generally installed on the mobile robot with forward motion in mind, and the shape of the mobile robot is more accurately taken into account. Further, this method is extended to LPA* such that it can cover both static and dynamic obstacle environments. Finally, this thesis shows via a series of simulations that the proposed algorithm provides feasible paths by accurately taking into account the unsymmetrical shape of mobile robots in static and dynamic obstacle environments. Consequently, this thesis demonstrates via a series of simulations that the proposed method can quickly replan a collision-free path while accurately taking into account the unsymmetrical shapes of the mobile robots with quasiholonomic constraint. For nonholonomic mobile robots, this thesis presents a novel path planning method, Kinematicsaware A* (K*), for efficiently generating paths considering the kinematics, shape and turning space of the mobile robots. The proposed method is based on a kinematics-aware node expansion method that also checks for collisions based on the shape of the mobile robots. This thesis presents two different heuristics considering the kinematics of the mobile robot simultaneously with and without obstacles. Especially ...