# On the Intersection of Computational Geometry Algorithms with Mobile Robot Path Planning
## 2 Path Planning
### CG-Based Single-Robot Path Planning
In RRT, given a configuration space \(C\), the algorithm iteratively builds a tree \(T\) rooted at the starting configuration \(q_{\text{start}}\). For each iteration, a random sample \(q_{\text{rand}}\) is drawn from \(C\), and the nearest node \(q_{\text{near}}\) from the tree \(T\) to \(q_{\text{rand}}\) is determined. A new node \(q_{\text{new}}\) is then added to the tree \(T\) by moving from \(q_{\text{near}}\) towards \(q_{\text{rand}}\) by a specified distance. The process is repeated until a termination condition is met, e.g., reaching \(q_{\text{goal}}\) or after a certain number of iterations. The hybrid technique consists of two phases: an initialization phase where the algorithm is initialized using RA* and a post-optimization degree where the quality of the solution identified in the earlier stage is improved using one heuristic method. Like A*, RA* maintains a heuristic function \(h(n)\) for estimating the cost from node \(n\) to the goal. The function \(f(n)\) in RA* is defined similarly as in A*:  
\[f(n)=g(n)+h(n) \tag{2}\]  
However, RA* can operate in two phases: the search phase and the repair phase. In the search phase, RA* behaves like A*, finding an initial path. During the repair phase, if the costs of edges change, RA* updates the costs in its open list and re-plans, repairing the path without re-exploring the entire space. The Genetic, Ant colony, and Firefly algorithms--three meta-heuristic algorithms--are also counted as randomized planners. These seek to offer valuable features in support of a hybrid approach to path planning. **Sampling-based Planners:** A sampling-based method of path planning [18] eliminates non-free configurations from a set of randomly chosen configurations. The edges are utilized to represent edges and are placed on the roadmap as collision-free paths. The sampling density can be increased in certain areas to hasten the roadmap connection. For instance, the oft-employed RRT generates a random configuration at each step and identifies the configuration most similar to the sample in the current tree. Other sampling techniques, such as expansive-space trees (EST) [19] and rapidly exploring random trees (RRTs) [16], presuppose that the initial and target configurations are known. EST evenly distributes samples in the undiscovered regions of the configuration space and then attempts to connect them to the tree, in contrast to RRTs' quick exploration of the space by extending from a tree towards random samples. The EST algorithm aims to grow a tree in the configuration space \(C\) by placing more samples in less-explored regions. Let \(T\) be a tree rooted at the starting configuration \(q_{\text{start}}\). The algorithm proceeds with the following general steps:  
1. Select a random sample \(q_{\text{rand}}\) from \(C\);
2. Determine a region \(R\) in \(C\) such that the probability of selecting a sample from \(R\) is inversely proportional to the volume of \(C\) already explored by \(T\) in \(R\);
3. If \(q_{\text{rand}}\) lies in \(R\), attempt to connect \(q_{\text{rand}}\) to the nearest node \(q_{\text{near}}\) in the tree \(T\);
4. Add \(q_{\text{rand}}\) to \(T\) if a valid connection is established. Mathematically, the probability \(P(R)\) of selecting a sample in region \(R\) can be represented as  
\[P(R)=\frac{V_{\text{unexplored}}(R)}{V_{\text{total}}(R)} \tag{3}\]  
where \(V_{\text{unexplored}}(R)\) denotes the volume of the region \(R\) that remains unexplored by \(T\) and \(V_{\text{total}}(R)\) is the total volume of \(R\). Conventional sampling-based planners cannot determine the absence of a solution to a given problem. Disconnection proofs, which can establish that two given configurations dwell in two different free-space components in specific circumstances, are the subject of several works [20]. **Optimal Sampling-based Planners:** Probabilistic Roadmap (PRM) and RRT*, variations of PRM, are discussed, demonstrating their asymptotical optimality, in [21].