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.