# On the Intersection of Computational Geometry Algorithms with Mobile Robot Path Planning
## 2 Path Planning
### Multi-Robot Path Planning
**Centralized Planner (unlabeled):** Unlabeled multi-robot motion planning refers to the specific situation of the \(k\)-color issue with \(k=1\). When a sampling-based algorithm was originally proposed, it was first examined in [32]. This suggests that all robots in set \(R\) have the same potential target positions, represented by set \(P\). Each target position should be occupied by one and only one robot at the end of the movement:  
\[|R|=|P| \tag{5}\]  
\[\forall p\in P,\exists tr\in R,\text{ such that }r\to p \tag{6}\]  
The first exploration of this problem using a sampling-based algorithm was documented in [32]. Over the years, more efficient solutions were introduced, as highlighted in [36]. However, the inherent complexity of this problem was proven to be PSPACE-hard, according to [37]. Many solution algorithms operate on simplified assumptions, with common ones related to constraints between the start and target positions of the robots. Recent years have introduced effective and comprehensive algorithms for the unlabeled problem [36]. For the problem to be proven to be PSPACE-hard [37], these methods simplify assumptions regarding the distance between the start and goal positions. **Decentralized Planner:** A decentralized strategy that contends robot disputes should be settled locally and without centralized coordination. In the reciprocal technique [33], the individual robots compute their future trajectories while considering other robots' current position and velocity to prevent collisions. The research in [34] adopts a game-theoretical methodology. It produces a reward function that minimizes the time and resources required for coordination and increases the time between disputes. Based on the sociology of pedestrian interaction, several publications [38] create collision-avoidance \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**Algorithm** & **Category** & **Best Case** & **Worst Case** & **Average Case** & **Optimality** & **Update Cost** & **Abbreviations** \\ \hline \hline Labeled [30] & Centralized & \(O(n\times m)\) & \(O(2n\times m)\) & \(O(b\times n\times m)\) & complete & low & \begin{tabular}{c} b—no. of obstacles, \\ m—no. of robots, \\ n—no. of cells \\ \end{tabular} \\ \hline Unlabeled [32] & Centralized & \(O(logn)\) & \(O(n^{3})\) & \(O(n^{2/3})\) & complete & low & \begin{tabular}{c} n—number of cells \\ \end{tabular} \\ \hline Reciprocal [33] & Decentralized & \(O(\mu\times n\times m)\) & \(O(\mu\times n\times m)\) & - & sub & high & \(\mu\)—makespan factor \\ \hline Game-theoretic [34] & Decentralized & \(O(e\times n)\) & \(O(e\times n)\) & - & sub & high & \(\epsilon\)—depth factor \\ \hline Shadok [35] & Distributed & \(O(w^{2})\) & \(O(w^{2})\) & - & sub & high & \begin{tabular}{c} \(w\)—number of \\ labeled units \\ \end{tabular} \\ \hline UNIST [28] & Distributed & \(O(w^{3})\) & \(O(w^{3})\) & - & sub & high & \
\begin{tabular}{c} \(w\)—maximum space \\ dimension \\ \end{tabular} \\ \hline \hline Gitsatrophe \(k\)-opt [29] & Distributed & \(O(k\times w)\) & \(O(k\times w)\) & - & complete & moderate &
\begin{tabular}{c} k—number of \\ robots and \\ w—number of \\ squares \\ \end{tabular} \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparative performance analysis of multi-robot path planners. strategies. Most recent approaches use CG for multi-robot path planning while considering kino-dynamic constraints. For instance, [PERSON] et al. [39] introduced a novel approach to multi-robot motion planning for unit discs utilizing revolving areas. Leveraging computational geometry, their strategy effectively handles robots as moving discs, focusing on the dynamic rearrangement of space while avoiding collisions. Although the approach excels in handling dynamic obstacles, its complexity tends to grow rapidly with the number of robots, posing scalability challenges. On the other hand, [PERSON] and [PERSON] [40] proposed an asynchronous real-time decentralized planner that emphasizes the real-time nature of multi-robot systems.