# Improved Analytic Expansions in Hybrid A-Star Path Planning for Non-Holonomic Robots
## 2 Statement of the Problem  
### Hybrid-State A-Star Algorithm  
The hybrid-state A-star (or hybrid A-star in short) is known as one of the most efficient path planners for non-holonomic autonomous vehicles. This planner was first implemented in outdoor environments by the Stanford Racing Teams robot, Junior, in the 2007 DARPA urban challenge [19].  
The hybrid A-star algorithm includes two phases (the forward search and analytic expansions) to produce an effective path [23; 24]. In the forward search, as the conventional A-star algorithm, the hybrid A-star algorithm is guided by a cost-to-go \(g(n)\) which is a cost from the start node to the current node (\(n\)), and a heuristic function \(h_{1}(n)\). The heuristic function \(h_{1}(n)\) uses the obstacle map to compute the cost of the distance from the current node to the goal in the discrete state. Moreover, like an advanced version of the normal A-star, the hybrid A-star algorithm is also guided by another heuristic function \(h_{2}(n)\) that ignores obstacles but considers the kinematics of a non-holonomic robot (e.g., autonomous vehicles). Further details can be found in [24; 25; 26]. The kinematics of the robot model is used to predict motions that depend on the speed, direction, and steering angle of the robot in the continuous state. This way helps the algorithm select the right successor in continuous coordinate, which a non-holonomic robot is able to follow, as shown in Figure 1a.  
These continuous coordinate successors have converted approximately to discrete coordinate nodes to compute the total cost of a movement. Equation (1) represents an objective function of the planner at each node \(n\). The successor with the lowest objective value will be chosen until it reaches the goal node.  
\[F(n)=g(n)+h_{1}(n)+h_{2}(n) \tag{1}\]  
However, reaching the exact continuous coordinate goal node is hard due to the dependence of the resolution of the grid map and the smallest motion that the robot can take.  
Analytic expansions are the second phase of the hybrid A-star algorithm. This phase plays a role in guaranteeing that the algorithm reaches the exact continuous coordinate of the goal state. In this phase, the RS curves have been utilized since the RS curves algorithm was a well-known algorithm that applies to non-holonomic vehicles that can move forward and backward. An RS curve is calculated to produce the shortest path from a start point to a goal point. Figure 1b depicts a combination of Left, Straight, and Right curves (or LSR curve in short) between two configurations: \([0,0,0]\), \([15,2,-\pi/2]\), where the first two values are position, the third value is an orientation of the robot. The red arrow represents the robot's direction. The curvature value (0.5 in this case) allows the robot to make the most turning angle, or minimum turning radius. The inventors of the hybrid A-star have claimed that the analytic expansion method leads to significant benefits in terms of accuracy and search speed.  
Additionally, Voronoi field was proposed to help the vehicle move in narrow opening by adding a path-cost function \(v\) as shown in Equation (2) below:  
\[v(x,y)=\frac{\alpha}{\alpha+d_{0}(x,y)}\frac{d_{v}(x,y)}{d_{0}(x,y)+d_{v}(x,y) }\left(\frac{d_{0}-d_{0}^{max}}{d_{0}^{max}}\right)^{2} \tag{2}\]  
where, \(\alpha\) is a constant falloff rate (\(\alpha>0\)), \(d_{0}^{max}\) is a constant maximum effective range of the field (\(d_{0}^{max}>0\)), \(d_{0}\) is a distance to the nearest obstacle (\(d_{0}<d_{0}^{max}\)), and \(d_{v}\) is a distance to the nearest edge of the generalized Voronoi diagram. The effectiveness of this function is  
Figure 1: Hybrid state A-star method. (**a**) Successor selection in continuous domain. (**b**) Reeds-Shepp curve.  
that the cost is higher in the area near obstacles, and decreases to zero at points that are equidistant to obstacles. As a result, the hybrid A-star path will tend to be in the center of the road.