# On the Intersection of Computational Geometry Algorithms with Mobile Robot Path Planning
## 2 Path Planning
### Multi-Robot Path Planning  
Several robots work together in a common workspace during multi-robot motion planning. The objective is to transfer the robots to their designated target positions without colliding with obstacles or other robots by keeping the overall schedule optimal concerning objective functions (minimize the makespan and minimize the total distance traveled by all robots). The issue can be seen as a single-robot scenario where the robot comprises multiple independent elements (robots). Let us say, for example, that the goal is to plan the movements of \(n\) robots; let \(S_{i}\) represent the configuration space of the \(i\)th robot. This can thus be rephrased as \"_planning the motion of a single robot_\" with a configuration space of \(S=\{S_{1},S_{2},...,S_{n}\}\). This discovery enables the direct application of single-robot tools to the multi-robot case. Such a simplistic approach, however, tends to be ineffective in theory and practice since it ignores the unique aspects of the current problem. Algorithm 1 generalizes the pseudocode of multi-robot path planning in different approaches. Different methods were created, especially for this issue. Table 1 depicts the comparative performance and complexity analysis of state-of-the-art multi-robot path planners. ```
1:procedureMultiRobotPathPlanner(robots, environment)
2:for each robot \(r_{i}\) in robots do
3:\(start_{i}\leftarrow\) starting position of \(r_{i}\)
4:\(goal_{i}\leftarrow\) goal position of \(r_{i}\)
5:endfor
6:while not all robots have reached their goals do
7:for each robot \(r_{i}\) in robots do
8:if\(r_{i}\) has not reached \(goal_{i}\)then
9:\(path_{i}\leftarrow\)PathPlanner(\(start_{i},goal_{i}\), environment)
10:MoveRobotAlongPath(\(r_{i},path_{i}\))
11:endif
12:endfor
13:HandleCollisions(robots, environment)
14:endwhile
15:endprocedure
16:procedurePathPlanner(\(start,goal,environment\))
17: Centralized/Decentralized/Distributed path planners
18: Annealing for UNIST [28]
19: Path optimization for Gitsatrophe [29]\(\triangleright\) Generate a path for a single robot from start to goal
20:return path
21:endprocedure
22:procedureMoveRobotAlongPath(\(robot,path\))\(\triangleright\) Move the robot along the generated path
23:endprocedure
24:procedureHandleCollisions(\(robots,environment\))\(\triangleright\) Resolve any potential collisions among robots
25:endprocedure
```  
**Algorithm 1** Generalized Algorithmic Overview for Multi-Robot Path Planning  
**Centralized Planner (labeled/colored):** The robots are divided into \(k\) groups (colors), with each group having replaceable robots, and a centralized algorithm for \(k\)-color multi-robot motion planning is given in [30]. Each robot must go to one of the target positions designated for its group, ensuring that, after the motion, precisely one robot occupies each target position. The continuous multi-robot issue and a discrete variation of it known as pebble motion on graphs are related in this study. Consider that the robots are partitioned into \(k\) groups or colors. Robots within each group are interchangeable. The motion-planning problem for these \(k\)-colored robots ispresented in [30]. Each robot aims to move to one of the target positions designated for its group, ensuring that  
\[\forall\text{ target positions }p,\exists\text{ exactly one robot }r,\text{ such that }r\to p \tag{4}\]  
The multi-robot motion-planning problem in continuous space is closely related to its discrete counterpart: pebble motion on graphs, as discussed in [31]. In this discrete problem, the challenge is to navigate pebbles from a set of source vertices to a set of target vertices, respecting certain movement rules. The method to solve the continuous multi-robot motion planning problem is decomposing the \(k\)-color problem into multiple smaller pebble motion problems. Solutions to these sub-problems can then be merged to derive a solution to the original continuous problem.