# Improved Analytic Expansions in Hybrid A-Star Path Planning for Non-Holonomic Robots
## 1 Introduction  
Since the emergence of artificial intelligence, path planning has become an attractive topic investigated in many studies. Popular path planning methods such as probabilistic road map (PRM), rapidly-exploring random tree (RRT), and space skeletonization have their advantages because of the countless number of scenarios in occupancy grid maps [1]. Moreover, diverse path planning algorithms [2, 3] have emerged to tackle constraints of motions of robots or autonomous vehicles. Path planning algorithms include Dijkstra algorithm [4, 5], A-star algorithm [6, 7], Genetic algorithm [8, 9], Artificial Neural Network (ANN) [10] and a combination of several algorithms [11, 12] to name a few. Resulted waypoints of a path planner are connected to form a trajectory from a start configuration to a goal configuration. The trajectory mainly contains many sharp or angular turns that make a mobile robot move awkwardly. Many experts and scholars have studied path smoothing techniques that produce a smooth path and guarantee a kinematically feasible obstacle-free path to deal with this problem [13]. Velocity, acceleration, and jerk have also been optimized to acquire smoothing trajectories for autonomous vehicles [14, 15, 16]. While the robot moves on a smooth trajectory, obstacle avoidance has also been considered [17, 18]. However, path smoothing methods can not make informed decisions regarding other paths during the search algorithm. Stanford University researchers have developed a variant of the A-star algorithm, named hybrid A-star, for application to a real car robot in an outdoor racing competition [19]. The hybrid A-star algorithm is a hybrid of discrete state and continuous state. This algorithm consists of two phases: the forward search phase, which takes into account the kinematics of the robot model in order to plan continuous motions of the robot in discrete grid maps, and the analytic expansion phase, which uses the RS curve to augment the accuracy and the speed of the algorithm. Planning a continuous state in the discrete domain of the hybrid A-star search algorithm has been an inspiration for numerous researchers to investigate and strive to apply it to real applications. Authors in [20] extended the search algorithm to accomplish several challenges, such as planning to a waypoint lying outside the vehicle's local map in outdoor applications. In [21], the authors proposed a method that is a combination of a visibility diagram and the hybrid A-star algorithm for valet parking applications. Firstly, the visibility diagram algorithm was used to find the shortest visible waypoints from a start position to a goal position. Then, the hybrid A-star was implemented to follow these waypoints with non-holonomic constraints of vehicles. The method proved faster than the standard hybrid A-star. However, RS curves' drawbacks when the robot approaches the destination were ignored in these two works. In another work [22], the authors strive to optimize paths generated by the hybrid A-star search. A concept of the artificial potential field was applied to reduce unnecessary steering actions and smooth the paths. However, the proposed method was applied in the hybrid A-star path as a post-smoothing technique. Since the RS curves were re-used from the open motion planning library, the problem in implementing the RS curves has remained. In this study, we investigate the hybrid A-star algorithm for non-holonomic robots in indoor environments. Through this investigation, issues that occurred in each phase of the algorithm are discovered. First, RS curves in the analytic expansion are often generated closely to obstacles, especially at corners. To overcome this issue, we generate multiple RS curves with different curvature values and propose a cost function to evaluate each curve to select the best one on which the robot moves safely in the presence of obstacles. Second, routes developed by the forward search consist of multiple unnecessary turns.