# Efficient and Safe Strategies for Intersection Management: A Review
## 3 Efficiency
### Trajectory Planning
#### 3.3.1 Algorithms
In the sense of the Lyapunov stability theory, the stability and asymptotic convergence of the tracking error of the closed-loop system are proved. The A-star algorithm is commonly used for path planning or unstructured trajectory planning. [PERSON] et al. propose a method named two new A-star [54] that expand the node for road trajectory planning. The first scheme attempts to find a trajectory by numerical optimization, connecting the current node of the vehicle directly to the target node. The second option uses a pure tracking controller to generate the short side (which guides the car along the whole situation reference path). The basic algorithm formula [55] is shown as follows:  
\[f(n)=g(n)+h(n) \tag{4}\]  
During the operation, A* algorithm selects the node with the lowest \(f(n)\) value (highest priority) from the priority queue as the node to be traversed next time. N represents node; \(f(n)\) is the comprehensive priority of node n; \(g(n)\) is the cost of n from the starting point; and \(h(n)\) is the expected cost of node n's distance from the end point, which is also the heuristic function of A* algorithm. As for heuristic function \(h(n)\), there are three main functions. The first type is Manhattan distance [56]. We need to calculate the distance from node to goal as shown in Figure 8. The calculation is as follows. \(D\) refers to the movement cost between two adjacent nodes, which is usually a fixed constant. Figure 8: From node to goal. Function heuristic(node) =  
\[d_{x}=abs(node.x-goal.x)\] \[d_{y}=abs(node.y-goal.y).\]  
Return (4):  
\[D*(d_{x}+d_{y}) \tag{5}\]  
The second type is diagonal distance [56]. The calculation is as follows. D2 refers to the cost of movement between two obliquely adjacent nodes. Function heuristic(node) =  
\[d_{x}=abs(node.x-goal.x)\] \[d_{y}=abs(node.y-goal.y).\]  
Return (5):  
\[D*(d_{x}+d_{y})+(D2-2*D)*min(d_{x},d_{y}). \tag{6}\]  
The last type is simple and we use it commonly, which names Euclidean distance [56]. The calculation is as follows. Function heuristic(node) =  
\[f(n)=g(n)+h(n) \tag{4}\]0 \[f(n)=g(n)+h(n) \tag{4}\]1  
Return (6)  
\[f(n)=g(n)+h(n) \tag{4}\]2  
The technology based on sampling randomly samples the state space to find the connection between the current state of the car and the next target state. In autonomous vehicles, the most commonly used sampling technique based on trajectory planning techniques is a rapidly-exploring random tree (RRT) [57]. The RRT method for trajectory generation uses a random sample in the state space to incrementally construct a search tree from the current state of the car. For each random state, a control command is applied to the nearest vertex of the tree to create a new state that is as close as possible to the random state. Each vertex of the tree represents a state, and each directed edge represents a command for extending the state. Candidate trajectories are evaluated according to various criteria. The RRT method based on sampling has a lower computational cost for high-dimensional space, and as long as there is a solution and time is sufficient, the solution can always exit. However, the results are not continuous and stable. A rough trajectory is obtained by using a sampling search planner, and then it is optimized by numerical optimization. Among the mainstream sampling search planners, most sampling operations are not flexible. If the sampling density is low, the solution will inevitably fail; if the sampling density is high, the dimension curse will appear. In this paper, authors propose an improved RRT* algorithm [58] for trajectory search, which uses a sampling search planner to get a rough trajectory, and then optimizes it through numerical optimization, so as to improve the sampling flexibility of trajectory search and eliminate the randomness of search. A new smoother based on quadratic programming (QP) is proposed to refine coarse trajectories. Reinforcement learning (RL) usually include two parts: Agent and environment.