Obstacle Avoidance

CS 480: Robotics & 3D Printing Lecture, Dr. Lawlor

Often in robotics we need to plan a path while avoiding portions of the configuration space due to the potential for a collision with some object, or a collision of parts of the robot with other parts of the robot.  Computing optimal paths through this modified configuration space is known to be NP-hard, and many simple problems such as path planning around closed obstacles are known to be mathematically problematic.

Luckily, we rarely require an optimal solution, and due to errors in sensing and actuation, we normally prefer to leave a buffer zone around obstacles rather than computing an exact path.  Path planning for a high precision CNC machining operation has typical tolerances of 1/10,000 of an inch, factory robot Sawyer is quoted at 0.1mm position tolerance, while the FAA defines a "Near Mid-Air Collision (NMAC)" as two aircraft passing less than 500 feet apart.

Some obstacle avoidance problems have known simple algorithmic solutions, such as a convex polygon robot avoiding a convex polygon obstacle.  More generally, the forbidden part of the configuration space under translation due to an obstacle is just the Minkowski sum of the robot and obstacle shapes.  This space can be approximated in OpenSCAD with the minkowski operator, although it tends to perform poorly.  If we're approximating anyway, I've always liked the idea of representing both robot and environment as images, and using the fast correlation theorem (FFT) to compute every possible interaction of the two.