# On the Intersection of Computational Geometry Algorithms with Mobile Robot Path Planning
## 2 Path Planning
### Distributed Approaches from CG-SHOP 2021  
The 2021 CG-SHOP Challenge [44] was centered on the issue of calculating polygons with minimum areas whose vertices were a predetermined set of points in the plane. Numerous research teams from the computational geometry and combinatorial optimization communities responded enthusiastically to this challenge, which led to an active discussion of potential solutions. The challenge has two objective functions: minimize the makespan and minimize the total distance traveled by all nodes. There were three apparent front-runners: Team Giastrophe finished first in the total distance traveled objective and third in the makespan objective and, followed by Team UNIST in the second place in both the makespan and total distance objectives. Team Shadoks achieved first place in the makespan and third place in total distance traveled. **Shadoks Approach to Low-Makespan:** The Shadoks approach [35] utilized a few algorithms considering a coordinated motion planning issue in the two-dimensional grid \(Z^{2}\). The objective is to transport a collection of robots, a set of \(n\) labeled unit squares, between the specified start and target grid cells without causing any collisions. The goal of the problem is to reduce the _makespan_ as much as possible. The longest \(L_{1}\) distance a robot can travel between its starting point and objective while avoiding obstacles is a trivial lower bound to the makespan. The objective function we maximize is the sum of all the variables with weight defined as  
\[weight(r,P)=\left(\delta_{r}(p(0))-\delta_{r}(p(k))\right)\times\left(\delta_{r }(p(0))^{2}+1\right), \tag{7}\]  
Therein, \(p(0)\) and \(p(k)\) are the first and last positions of the path \(P\), and \(\delta_{r}(p)\) is the obstacle-avoiding distance from a point p to the target of the robot r. We can always swap start-target positions and reverse the pathways, preserving the best solution identified, because the problem is symmetric over time. Their strategy begins with transforming path planning into SAT problems to make it tractable, then applying A* for trivial optimization along with the cross, Cotty catcher, dichotomy, and escape strategies. Later, they improved their solution by using feasible and conflict optimizers. All the strategies work in parallel; overall computation complexity is polynomial. **UNIST Simulated Annealing Approach:** The UNIST method [28] consists of three components. A feasible solution is first calculated to move each robot from its beginning to its goal point through a middle point. This is performed by setting intermediate points outside the minimum bounding box created by the input positions of the robots and obstacles. The second uses a straightforward local search strategy that involves regularly deleting and inserting a random robot along an ideal path. As a result of the robots no longer having to pass through the midway locations, the quality of the solution is improved. Finally, simulated annealing is used to enhance this workable solution further. To improve the feasible solution, UNIST has picked a robot \(i\), deleted it from \(G\), and inserted it again using the feasible solution. It may greatly improve this robot, as it no longer has to go through its middle-point \(m_{i}\). UNIST calls this operation a tightening move (see Figure 4). UNIST used two alternative types of moves: either tightening the robot's whole trajectory or stretching it between two places by having the robot pass through a third intermediate point that was randomly created. They have run the deletion and insertion procedures \(2w\) times and obtained a feasible solution in \(O(w^{3})\) time, where \(w\) is the maximum-sized dimension of world space. **Gitastrophe Randomized \(k\)-Opt:** An excellent initial solution is found during the initialization phase of the Gitastrophe technique [29], and this solution is then optimized during the k-opt local search phase. [PERSON]'s main contribution was to approximate the joint optimization using \(k\) unique single-path optimizations.