- Bug Algorithm
- Artificial Potential Field
- Dynamic Window Approach
- Follow the Gap
- Dijkstra's Algorithm
- A* Algorithm
- Rapidly-Exploring Random Tree (RRT)
- Probabilistic Roadmap (RPM)
- Visiblity Planning
- Smoothing Planned Paths
- This is an algorithm where the vehicle moves in a straight line towards the goal point, but when it encounters an obstacle, it moves around the obstacle's perimeter and then resumes moving straight towards the goal.
- It starts with prior knowledge of the final destination, but without any prior information about obstacles or the map.
- There are various versions of the BUG algorithm, such as BUG0, BUG1, BUG2, and Tangent Bug.
- It is simple to implement and requires low computation, but it does not always guarantee the optimal path.
- After running the three algorithms, the BUG0 algorithm visually appeared to provide the most optimal path and took the least amount of time.
- In the case of the BUG1 algorithm, it showed an inefficient path, rotating around the obstacle more than once.
- Both the BUG0 and BUG2 algorithms appeared more efficient compared to BUG1, but there was a difference in that BUG0 moved along the optimal distance, whereas BUG2 followed the edges of the obstacle.
- The algorithm explores possible combinations of velocity (linear velocity/acceleration) in the velocity and angular velocity space.
- It derives the optimal linear velocity and angular velocity based on speed, direction, and the distance to obstacles to avoid collisions and reach the destination.
- The process of calculating the cost involves sampling the velocity space and simulating, which can result in high computational costs.
- Since it focuses on local path planning, it does not guarantee the optimal path after collision avoidance.
- Starting from the initial node, the algorithm visits the nearest node first and computes the shortest distance information for all other nodes.
- Since it calculates for all nodes, it can be computationally expensive and slow.
- The modified Dijkstra algorithm uses a heuristic function between the starting point and the goal point to calculate scores, and based on the calculated scores, it searches for the optimal path.
- This reduces the computational load, making it faster and generally providing the optimal path.
- The performance and accuracy of the path depend on the heuristic function used.
The A* algorithm has the advantage of more efficiently searching for the path to the goal by visiting only certain nodes based on priority, allowing it to find the optimal route more quickly.
It was observed that the A* algorithm, with its smaller search space compared to the Dijkstra algorithm, is significantly superior in terms of time and computational efficiency.
- This algorithm generates an attractive force toward the goal point and a repulsive force around obstacles, causing the robot to move based on a physical force field.
- When the robot approaches an obstacle, the repulsive force changes abruptly, leading to oscillation.
- A local minima problem can occur when the repulsive force from obstacles and the attractive force toward the goal point become equal, causing the robot to stop mid-path.
Integrating the Dynamic Window Approach, BUG, and Potential Field algorithms into a single code.
- An algorithm that generates a path to reach the target point by expanding a tree through a Random Sampling process.
- It efficiently searches for paths in unstructured or high-dimensional spaces.
- A drawback is that the tree may expand unnecessarily due to the random sampling process.
- It operates efficiently with a simple structure and has the advantage of being applicable to high-dimensional spaces.
Since it operates through random sampling, the time taken to reach the destination varies each time it is executed, and ultimately, different paths are generated.
I thought the RRT algorithm was not very efficient, so I considered ways to improve its performance and applied some of those methods.
A method where multiple trees are generated simultaneously from the starting point, and the path of the tree that reaches the destination first is selected.
→ Increases efficiency in terms of time.
→ I wrote a code : rrt_many_tree_generate.py.
By performing random sampling anywhere, the process can take a long time due to randomness.
To prevent this, random sampling is conducted within a small distance radius only around the node closest to the destination, avoiding inefficient random sampling.
→ Increases efficiency in terms of time and computation.
→ I wrote a code : rrt_sampling_short.py.
By generating and expanding two trees simultaneously from the starting point and the goal point, and selecting the path when the two trees meet within a certain distance.
→ Increases efficiency in terms of time.
→ I wrote a code called rrt_both_path.py.
This approach finds the path relatively faster compared to the previously improved algorithms.