# Sampling-Based Path Planning Algorithm for a Plug & Produce Environment
## 2 Implementation of Path Planning Algorithms
### Adaptive RRT
Sampling is performed based on uniform random distribution in \(C_{free}\) space. The sample configurations that lie in the configuration obstacles space are discarded using a simple collision check algorithm. The next step is connecting the pair of randomly generated sample configurations. Depending on the PRM parameter \((k)\), the value and the number of connections established between each sample created, four distance functions can be used to find the nearest neighbor. For example, 2-norm in C--space, \(\infty\)--norm in C--space, 2--norm in workspace, and \(\infty\)--norm in workspace. Here, 2--norm in C--space is used due to its simplicity. One pair of neighboring configurations is identified, and using a simple local planner, the connections are established between these two configurations. To establish the connection, an incremental collision detection function is enabled and it checks for the collision between the configurations. If there is no collision found, the edge will be created between the configurations. Each configuration can have a maximum number of possible connections, and it can be fixed with the value \(k\), which is called \(k\)-nearest neighbor value. During the construction phase, the user can fix the number of samples \(\left(n_{samples}\right)\) to be created, which can increase or decrease the complexity of the created map. Algorithm 3 shows captures of the PRM algorithm. When the connections are established between all the random configurations, the formation of the road map in the entire \(C-space\) is finished, i.e., the learning phase of PRM is finished. The purpose of the learning phase is to construct a roadmap in the form of an undirected graph. The time it takes to create the graph mainly depends on two values: \(k\) and \(n_{samples}\). If these two values are increased, the density of the graph increases. Thus, the learning phase is always slow. In the query phase, the start \((q_{start})\) and goal \((q_{goal})\) points are assigned within the \(C_{free}\)_space_ in the created dense graph. ```
Algorithm to build roadmap with PRM: function \(PRM\) \(\left(n_{samples},\ k\ \right):\ G\) \(V\leftarrow\varnothing\) and \(\dot{E}\leftarrow\varnothing\) while\(|V|<n\)do repeat \(q_{rand}\leftarrow\) a random configuration in \(C_{free}\) until\(q_{rand}\) is collision free \(V\gets V\ \cup\ \left\{q\right\}\) endwhile forall\(q\in V\)do \(N_{q}\gets k\) nearest neighbors of \(q\) chosen from \(V\) forall\(q_{near}\in N_{q}\)do if\((q_{rand},q_{near})\
eq E\)and\(\Delta(q_{rand},q_{near})\
eq NIL\)then \(E\gets E\cup\ \left\{(q_{rand},q_{near})\right\}\) endif endfor \(G=(V,E)\) returnG endfunction
```
**Algorithm 3** Captures of the PRM algorithm

### PRM with the Dijkstra Algorithm

PRM works in two phases, i.e., the construction phase and a query phase. During the construction phase, it constructs the roadmap in the form of an undirected graph \(G=(V,E)\) in the configuration-free space \((C_{free})\). It randomly generates uniform sample configurations \((q_{start},\ q_{rand},\ q_{near}\ and\ q_{goal})\) in \(C_{free}\). The _edge in \(E\)_ corresponds to the collision-free, connecting the random samples \(q_{start}\) and \(q_{goal}\). \(E\) is a straight line which is referred to as a local path, computed by a local planner. Sampling is performed based on uniform random distribution in \(C_{free}\) space. The sample configurations that lie in the configuration obstacles space are discarded using a simple collision check algorithm. The next step is connecting the pair of randomly generated sample configurations. Depending on the PRM parameter \((k)\), the value and the number of connections established between each sample created, four distance functions can be used to find the nearest neighbor. For example, 2-norm in C--space, \(\infty\)--norm in C--space, 2--norm in workspace, and \(\infty\)--norm in workspace. Here, 2--norm in C--space is used due to its simplicity.