Probabilistic Robust Path Planning for Nonholonomic Arbitrary-Shaped Mobile Robots Using a Hybrid A* Algorithm

To guarantee safe motion planning, the underlying path planning algorithm must consider motion uncertainties and uncertain state information related to static, and dynamic obstacles. This paper proposes novel hybrid A* (HA*) algorithms that consider the uncertainty in the motion of a mobile robot, position uncertainty of static obstacles, and position and velocity uncertainty of dynamic obstacles. Variants of the HA* algorithm are proposed wherein a soft constraint is used in the cost function instead of chance constraints for probability guarantees. The proposed algorithm offers a tradeoff between the traveling distance and safety of paths without pruning additional nodes. Furthermore, this paper introduces a method for considering the shape of a mobile robot for probabilistic safe path planning. The proposed algorithms are compared with existing path planning algorithms and the performance of the algorithms is evaluated using the Monte Carlo simulation. Compared with the related probabilistic robust path planning algorithms, the proposed algorithms significantly improved safety without excessively increasing travel distance and computational time. The results also showed that dynamic obstacles were safely avoided, which is in contrast to the conventional HA* algorithm that has a high probability of collision. In addition, considering the shape of the robot in the proposed probabilistic approach led to safer paths overall.