When is an obstacle a perfect obstacle

摘要

Owing to the exponential costs of path planning in a continuous or graded cost environment, robot motion planning traditionally makes the "perfect obstacle assumption" and divides workspace into perfect obstacles and perfect freespace, although in practice such a black-and-white distinction is rare. Under the above definition, however, many finite cost regions can also be shown to be perfect, substantially reducing the computational costs. We present a linear-time algorithm for deciding whether an obstacle is perfect 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. Identifying perfect obstacles helps avoid situations where it may be possible to push aside an obstacle, or climb a hillock, for example.