# Sampling-Based Path Planning Algorithm for a Plug & Produce Environment
## 2 Implementation of Path Planning Algorithms
### Adaptive RRT*  
This is a modified version of RRT*. The main purpose of this algorithm is that it can be used in a constraint environment when RRT* cannot fetch a collision-free path after the number of iterations. This adaptive RRT* dynamically changes its sampling value in the collision check module and tries to create a collision-free path in the more constraint environment. While the collision check function happens between \(q_{new}\) and \(q_{nearest}\), if there is no collision, it follows RRT*, but if a collision exists, an adaptive RRT* finds the mid-point \(q_{mid}\) between \(q_{new}\) and \(q_{nearest}\). Then, the collision check function performs a collision check between \(q_{mid}\) and \(q_{nearest}\). If there is no collision, it connects the edge from \(q_{nearest}\) to \(q_{mid}\) and ignores the portion of \(q_{mid}\) to \(q_{new}\). If there is a collision between \(q_{nearest}\) to \(q_{mid}\), it rejects the entire portion of \(q_{nearest}\) to \(q_{new}\) and continues searching for the next \(q_{rand}\) point. This process continues until it finds another collision between \(q_{new}\) and \(q_{nearest}\). If no collision occurs, it works as RRT*, but when there is a collision occurring between \(q_{mid}\) and \(q_{nearest}\), this algorithm functions as an adaptive RRT* by having the extra collision check module. This iteration continues until it constructs the entire \(T\) of \(C_{free}\) space or until it reaches the \(q_{goal}\) point. In this adaptive RRT*, best parent search and rewiring take place to bring the asymptotically optimal probabilistic collision-free path for the environment, as it is in the RRT* algorithm. Algorithm 6 shows the captures of the adaptive RRT*. This Adaptive RRT* is mainly used where a lot of constraints are present in the process module. This algorithm creates a greater number of nodes if the obstacle is present compared to RRT* because of the extra collision check function.  
```
Algorithm to build Adaptive RRT* tree: function Adaptive RRT* \(\left(q_{start},\ q_{goal},\ n(samples),\ C\right):\Upsilon\)  create \(T\) with \(q_{start}\) for n do  generate a random node \(q_{rand}\) in \(C_{free}\)  find the nearest node in the tree \(q_{nearest}\) from \(q_{rand}\) if\(Collision\,free\ (q_{nearest},\ q_{rand})\)then  generate \(q_{new}\) between \(q_{nearest}\) and \(q_{rand}\)  add \(q_{new}\) to the tree!  find \(q_{near}\) in the vicinity of the \(q_{new}\)  calculate the cost in terms of distance \(q_{min}\gets dist_{min}=d(nearest,\ new)+d(new,\ new)\) if\(d_{new}<d(nearest,\ new)\)then  update parent of \(q_{near}\) to \(q_{new}\)  rewire \(T\) for \(q_{new}\) end if else  find \(q_{mid}\) point between \(q_{nearest}\) and \(q_{random}\) if collision free (\(q_{nearest}\), \(q_{mid}\)) then  generate \(q_{new}\) between \(q_{nearest}\) and \(q_{mid}\)  find \(q_{near}\) in the vicinity of the \(q_{new}\)  calculate the cost in terms of distance. \(q_{min}\gets dist_{min}=d(nearest,\ new)+d(new,\ new)\) if\(d_{new}<d(nearest,\ new)\)then  update parent of \(q_{near}\) to \(q_{new}\)  rewire \(T\) for \(q_{new}\) end if end if  end if
```  
**Algorithm 6** Captures from the adaptive RRT* algorithm