Path Deflection Algorithms

Owned by Andrew Shum
Last updated: 2024-07-05
2 min read

Bendy Ruler Algorithm

The Bendy Ruler algorithm is an intuitive obstacle avoidance technique that uses the concept of a virtual ruler extending from the robot's current position towards its goal. As the robot moves, it detects obstacles intersecting the ruler using sensors. When an obstacle is detected, the ruler bends around it to create a feasible path the robot can follow. This bending process continues dynamically, allowing the robot to navigate smoothly around obstacles while maintaining a trajectory toward the goal. The simplicity and effectiveness of the Bendy Ruler algorithm make it suitable for environments with moderate complexity, ensuring the robot can avoid collisions while progressing toward its target.

Vector Field Histogram

A Vector Field Histogram consists of multiple vectors spanning out from the drone. The algorithm then evaluates the histogram to identify wide gaps that represent feasible paths for navigation. A cost function is applied to each candidate direction, considering factors like the robot’s desired direction, obstacles' proximity, and the path's smoothness. The algorithm will choose the direction with the lowest cost for the robot to move toward, balancing the need to avoid obstacles to progress toward the target.

 

image-20240704-145855.png

 

Artificial Potential Field

The robot is treated as a particle in a field where the goal exerts an attractive force pulling the robot towards it, and obstacles exert repulsive forces pushing the robot away. The resultant force from combining these two influences determines the direction of the robot's movement. This way, the robot is guided smoothly towards the goal while avoiding collisions with obstacles. APF is simple to implement and effective for real-time applications, although it can sometimes struggle with local minima, where the attractive and repulsive forces cancel out, trapping the robot.

 

TODO: sources