When is an obstacle a perfect obstacle?

Traditional robot motion planning makes the “perfect obstacle assumption” and divides workspace into perfect obstacles and perfect freespace. A region of the workspace is a perfect obstacle if the cost of traversing it is such that there always exists a more efficient path external to the region. Identifying perfect obstacles helps avoid situations where it may be possible to push aside an obstacle, or climb a hillock, for example. We present a linear-time algorithm for determining perfect obstacles in the convex case, and a genetic algorithms approach in the nonconvex case. When the obstacle is not perfect, we identify a measure of the degree to which it approximates a perfect obstacle. This can be a pre-condition to applying standard motion planning techniques