Probabilistic Roadmap Algorithms serve a crucial role in robotics by facilitating the discovery of collision-free routes between an initial point and a final destination within obstacle-laden maps. Once a path devoid of collisions is established, the integration of a post-processing algorithm, such as the Path Shortcutting algorithm, becomes instrumental. This subsequent step aims to extract the most concise route between the starting point and the target by optimizing the path through sampled points.
I used two algorithms to find the nearest neighbours of points:-
- Euclidean distance (cdist) - Requires less number of sample points
- K-Nearest Neighbors Algorithm - Requires more number of sample points
I found that when utilizing Euclidean distance (cdist) to create the network of nearest neighbours, I only had to use a few samples of points (600) to pass all test cases.
This is the network created using 600 points (Number of Neighbours per point = 60).
The network covers almost the entire area as seen in the picture below. It is able to pass all test cases.
Observations: Overall the speed for running cdist over 600 points is faster than running KNN for 5000 points. Even though the sample points are less (600), the network is vast as the number of neighbours considered is high (60). I found this algorithm more efficient than KNN.
This is the images for the shortest path for the test case (size_x = 10, size_y = 6, number of obstacles = 5):
| Path before post-processing (Euclidean distance) | Shortest path after path shortcutting (Euclidean distance) |
|---|---|
 |
 |
While utilizing the KNN algorithm (Number of Neighbours = 20, radius = 0.4), I found that I had to use more sample points (5000) than cdist to pass all test cases.
The network area of KNN can be seen below :
This is the shortest path for the test case (size_x = 10, size_y = 6, number of obstacles = 5):
| Path before post-processing (KNN) | Shortest path after path shortcutting (KNN) |
|---|---|
 |
 |
Dijkstra's algorithm is used for finding the shortest path from a starting point to a destination. It works by exploring neighboring points, picking the one that's closest to the starting point, and gradually moving towards the destination. It keeps track of distances as it goes along, ensuring it always takes the shortest route available. Once it reaches the goal, it traces back its steps to reveal the optimal path that leads from the source to the destination. The PRM path for the given problem is obtained using the Dijkstra's Algorithm
The paths found by the planning methods of Section Path planning are collision-free but might not be optimal in terms of path length. The following two approaches can be utilized to optimize the PRM path obtained:
- Shortcut Method
- Two pointer Method
- Utilize the path from the Dijkstra's algorithm. Pick 2 random nodes and check if the line created by joining them is valid (:- does not intersect an obstacle)
- If the line created is valid, delete all elements between the two points in the path, and update the path
- Repeat the process max_rep (250) times
Constraints: Although this is very unlikely, the number of repetitions may not be enough to get the most optimal path. Since the shortcut points are randomly chosen, we may have a case where a certain shortcut point is missed out.
- Utilize the path from the Dijkstra's algorithm. Create a loop that checks if the line joining the left pointer and right pointer of the path is valid (:- does not intersect an obstacle)
- The right pointer is decremented until the line is valid. The valid point is now appended to the shortest path list, and the left pointer of the loop is the valid point. The right pointer is changed back to len(path) - 1
- This process is repeated until the left pointer is equal to len(path) - 1, and the shortest path is returned
Constraints: Although this method is very accurate as it always gives the most optimal path, it is less efficient than the shortcut method.