J. Basch, L. J. Guibas, D. Hsu, A. Nguyen, Disconnection Proofs for
Motion Planning, IEEE International Conferrence on Robotics Animation 2001,
Probabilistic road-map (PRM) planners have shown great promise in
attacking motion planning problems with many degrees of freedom that
were previously infeasible. Yet when such a planner fails to find a path,
it is not clear that no path exists, or that the planner simply did not
sample adequately or intelligently the free part of the configuration
space. We propose to attack the motion planning problem from the other
end, focussing on disconnection proofs, or proofs showing that there
exists no solution to the posed motion planning problem. Just as PRM
planners avoid generating a complete description of the configuration
space, our disconnection provers search for certain special classes
of proofs that are compact and easy to find when the motion planning
problem is `obviously impossible,' again avoiding complex geometric and
combinatorial calculations. We demonstrate such a prover in action for
a simple, yet still realistic, motion planning problem. Failure of the
prover suggests key milestones, or configurations of the robot that can
then be passed on and used by a PRM planner. Thus by hitting the motion
planning problem from both ends, we hope to resolve the existence of
a path, except in truly delicate border-line situations.
, author = "J. Basch, L. J. Guibas, D. Hsu, and A. Nguyen"
, title = "Disconnection Proofs for Motion Planning"
, booktitle = "International Conference on Robotics and Automation"
, year = 2001
, pages = "1765--1772"