# Sampling-Based Path Planning Algorithm for a Plug & Produce Environment
## 1 Introduction
### Short Literature Review
#### 1.1.2 Optimal Algorithms  
Passive Algorithms  
PRM is another sampling-based planning algorithm, and it works on incremental sampling-based node search algorithms, which could not bring a path on their own, but could generate a practical graph for the entire configuration space. Once the road map is constructed, any type of graph search algorithm can be implemented to find the optimal path between the start and goal points. This process repeats the entire workspace and creates a dense graph among all configurations in the free space [32]. PRM samples the random configuration and checks that the configuration is in the free space. If it is in the free space, PRM uses the local planner to make the edges between the configurations. There are many ways to make the connection between the nodes. One among them is Delaunay Triangulation, which makes the connection based on the node connection [33], but this is not used due to the intractable complexity of computing and also local path planning using artificial potential field supported by augmented reality, which bypasses the local minima issue [34]. In this article, the K-nearest neighborhood connection is used in PRM to make the connections between the randomly generated configurations due to its high accuracy [35]. There are improved PRM algorithms implemented by reducing the sampling space generated by random nodes, yet maintaining the same number of nodes generated, thereby improving the space utilization. The results are compared with traditional PRM and improved genetic algorithms, and were found to have significant advantages in terms of energy consumption and adaptability [36]. A* is considered one of the best heuristic graph search algorithms, it can calculate the solution quickly, but it is not adapted for complex scenarios and the optimal value depends on the heuristic value [37]. The algorithm named Bellman-Ford can handle negative weights, but it does not scale well, meaning changes in the network topology are not reflected quickly because the updates are spread node by node only, indicating it is slower compared to other graph search algorithms [38]. [PERSON]'s algorithm can recalculate if any problem arises from the starting node to the ending node, and due to its simplicity and flexibility, it can be implemented in complex situations and the optimal value is not dependent on the heuristic value. [PERSON] always fetches close to linear paths, with less computational time even in high-dimensional spaces [39]. Active Algorithms  
RRT* is another variation of RRT algorithms, but it has an inbuilt optimization function to improve the path quality. It differs from RRT in several ways: the high-density tree is generated randomly toward the nodes with a lower distance; the path is optimized by rewiring; and it brings asymptotic optimal paths, meaning it can fetch a path in large spaces. Another improved RRT path planning algorithm is outlined in [26]; it can fetch the efficient path in shorter time, but it cannot guarantee the results when there are more constraints in the environment, so it is obvious that it takes more computational time. To generate the path planning with less computational time, the improved RRT algorithm, i.e., RRT expansion, is one example with target gravity and the result is tested in humanoid robots [28]. During map generation, the node will be expanded under joint and gravity action based on random probability. When the path generation is complete, the breadth-first search is used to smoothen the generated path [23]. The RRT-biased with regression [40] algorithms are tested in complex environments. This algorithm adds the regression mechanism to avoid the over-searching of nodes in the configuration space, and it continuously improves the reachable spatial information, as well as refines the boundary nodes in joint space. This algorithm avoids the time taken in collision detection function and increases the success rate and efficiency. Even though the results are comparable, it is tested only within the simulation environment.