Improved Analytic Expansions in Hybrid A-Star Path Planning for Non-Holonomic Robots

Abstract

In this study, we concisely investigate two phases in the hybrid A-star algorithm for non-holonomic robots: the forward search phase and analytic expansion phase. The forward search phase considers the kinematics of the robot model in order to plan continuous motion of the robot in discrete grid maps. Reeds-Shepp (RS) curve in the analytic expansion phase augments the accuracy and the speed of the algorithm. However, RS curves are often produced close to obstacles, especially at corners. Consequently, the robot may collide with obstacles through the process of movement at these corners because of the measurement errors or errors of motor controllers. Therefore, we propose an improved RS method to eventually improve the hybrid A-star algorithm’s performance in terms of safety for robots to move in indoor environments. The advantage of the proposed method is that the non-holonomic robot has multiple options of curvature or turning radius to move safer on pathways. To select a safer route among multiple routes to a goal configuration, we introduce a cost function to evaluate the cost of risk of robot collision, and the cost of movement of the robot along the route. In addition, generated paths by the forward search phase always consist of unnecessary turning points. To overcome this issue, we present a fine-tuning of motion primitive in the forward search phase to make the route smoother without using complex path smoothing techniques. In the end, the effectiveness of the improved method is verified via its performance in simulations using benchmark maps where cost of risk of collision and number of turning points are reduced by up to around 20%.

Keywords

• Reeds-Shepp curves
• hybrid A-star
• non-holonomic mobile robot
• indoor robot applications