# On the Intersection of Computational Geometry Algorithms with Mobile Robot Path Planning
## 2 Path Planning
### CG-Based Single-Robot Path Planning  
Due to the difficulty in path planning for robots with multiple degrees of freedom (more than 4 or 5), sampling-based algorithms have been created that compromise completeness and practical application. Using such methods avoids the explicit geometric depiction of the open space. Instead, in their most basic form, they generate a sizable number of configuration sample sets and exclude samples that reflect the robot in an unallowable configuration. Then, an effort is made to connect close configurations using a metric set across the configuration space. Finally, a roadmap-like graph structure is created as a result of this construction. It has the property that every path connecting any two of its vertices corresponds to an accessible path connecting the corresponding configurations in the configuration space. Although these methods are intrinsically imperfect, it is frequently possible to demonstrate that they are probabilistically complete--guaranteed, given enough samples, to identify a solution with a high probability if one exists. **Problem Statement:** In single-robot path planning, our primary objective is to find a feasible and optimal path for a robot navigating a given environment. This entails determining a path within a configuration space \(C\), a subset of the \(n\)-dimensional Euclidean space, denoted as \(C\subset\mathbb{R}^{n}\). Within this space, there exists an obstacle space \(C_{\text{obs}}\), such that \(C_{\text{obs}}\subset C\). For a given starting configuration \(q_{\text{start}}\), which belongs to \(C\) but not to \(C_{\text{obs}}\), and a goal configuration \(q_{\text{goal}}\), which also belongs to \(C\) but outside \(C_{\text{obs}}\), the challenge is to determine a continuous path \(\pi:[0,1]\to C\). This path must start at the given starting configuration, \(\pi(0)=q_{\text{start}}\), and end at the goal configuration, \(\pi(1)=q_{\text{goal}}\), ensuring that, for every \(t\in[0,1]\), \(\pi(t)\
otin C_{\text{obs}}\). An optimal path is typically characterized by minimizing  
Figure 3: Taxonomy of robotic algorithms using computational geometry for path planning. the integral \(\int_{0}^{1}||\pi^{\prime}(t)||dt\), where \(||\pi^{\prime}(t)||\) signifies the velocity or rate of change of the robot's configuration. **Optimal Planners:** The shortest path evaluation for the known static environment is a two-level problem that entails the selection of feasible node pairs. The most straightforward path evaluation is based on the obtained possible node pairs [14]. Therefore, A* and re-planner are used for shortest path evaluation based on the information regarding the obstacles present in the environment. However, the approach is ineffective and unworkable in dynamic contexts since neither of the above conditions exists. The algorithm uses a heuristic to estimate the cost from the current node to the goal. Let \(G=(V,E)\) be a graph where \(V\) is the set of vertices and \(E\) is the edges. For a given node \(n\), let \(g(n)\) denote the cost of the shortest path from the start node to \(n\) and \(h(n)\) be the heuristic estimate of the cost from node \(n\) to the goal. The A* algorithm evaluates nodes by combining \(g(n)\) and \(h(n)\) to form \(f(n)\), defined as  
\[f(n)=g(n)+h(n). \tag{1}\]  
The objective of the A* algorithm is to minimize \(f(n)\), ensuring that the algorithm is both complete (it will find a solution if one exists) and optimal (it will find the shortest possible path), provided that the heuristic \(h(n)\) is admissible (never overestimates the actual cost to reach the goal) and consistent (satisfies the triangle inequality). D* [15] and its variants are suggested practical tools for speedy re-planning in congested contexts to facilitate path planning in dynamic environments. **Randomized Planners:** Rapidly exploring random trees (RRTs) [16], and a hybrid strategy that combines Relaxed A* (RA*) [17] with one meta-heuristic algorithm as D*, and its variations do not guarantee solution quality in significant dynamic contexts.