# Research on Path Planning of Mobile Robot Based on Improved Theta* Algorithm
## 2 Algorithm Design  
### Theta* Algorithm  
The Theta* algorithm is a variant of the A* algorithm, which is centered on the grid of the current node and expands outward, the node expansion direction of the A* algorithm is shown in Figure 2 and is restricted to eight directions around the current node, while the same Theta* does not restrict the expansion direction of the node. The Theta* algorithm, like the A* algorithm, is applicable to static grid maps and its cost function expression is:  
\[f(n)=g(n)+h(n) \tag{1}\]  
where \(f(n)\) is the estimated cost from the starting point to the target point; \(g(n)\) is the actual cost from the starting point to the current node \(n\); and \(h(n)\) is the heuristic function, which represents the estimated cost from the intermediate point \(n\) to the target point. In the traditional Theta* algorithm, the calculated value of \(g(n)\) is generally characterized as the number of nodes of the grid map through which the path passes, and the heuristic function \(h(n)\) is the distance from node \(n\) to the target point. The key difference between the Theta* algorithm and the A* algorithm is that the parent node of a vertex in the A* algorithm can only be the node adjacent to it, while the visibility check mechanism is added in the Theta* algorithm to break the restriction of the raster environment, so that the parent node of a node can be any node. When extending a new node, the A* algorithm considers only one path, while the Theta* algorithm considers two paths, as shown in Figure 2(a), when the Theta* algorithm wants to extend from point A2 to point C3. 1. Path 1 has 3 path nodes: A2, B2, and C3, currently the parent node of C3 is B2 and the parent node of B2 is A2. This is also the path considered by the A* algorithm. 2. Path 2 has 2 path nodes: A2 and C3. Currently, C3's parent node is A2. This is an additional path to consider with the A* algorithm. Figure 3: Theta* algorithm path planning schematic. Figure 2: A* algorithm node search direction. According to the triangle trilateral length property it is known that the distance of path 2 must be shorter than path 1. Additionally, the need to visualize the current node and the extended node to determine whether there are obstacles before the two nodes, as in Figure 2(a), there is no obstacle between node A2 and node C3, so path 2 can be selected, but in Figure 2(b), there is an obstacle between node A2 and node B4, the two nodes are not visible, so path 2 cannot be selected. The specific steps of the Theta* algorithm are as follows:  
1. Initialize the starting point and target point, create a new open table and a new close table, and add the starting point to the open table. 2. Determine whether the open table is empty, if it is empty, the path planning fails and the search stops; if it is not empty, the node with the lowest evaluation cost in the open table is taken as the current node to be expanded and set to \(n\). Go to the next step. 3. Determine whether the current node \(n\) is the target point, if yes, it means the path finding is successful, backtrack the parent node of n until the starting point is the path, and the search is terminated; otherwise, go to the next step. 4. Extend node \(n\). Iterate over all neighboring nodes of node \(n\) (set to \(s\)) and perform the following operations. * If node \(s\) is an obstacle or is already in the close table, do not process it; instead proceed to the next step. * If node \(s\) is not in the open list, initialize the actual cost \(g(s)\) from the starting point to node \(s\) to infinity, set its parent node to NULL, and insert node \(s\) into the open table. If node \(s\) is in the open list, proceed directly to the next step. * Update the information of the node. Check if the parent node (set to \(p\)) of the current node \(n\) exists. If it exists, check whether node \(s\) and node \(p\) are visible by line of sight (LOS) function [13].