D-Plan: Efficient Collision-Free
Path Computation For Part Removal and Disassembly
Zhang, Xin Huang, Young J. Kim and Dinesh Manocha
University of North Carolina
at Chapel Hill
We present a novel
approach to compute a collision-free path for part disassembly simulation and
virtual prototyping of part removal. Our algorithm is based on sample-based
motion planning that connects collision-free samples in the configuration
space using local planning. In order to effectively handle the tight-fitting
scenarios, we describe techniques to generate samples in narrow passages and
efficient local planning algorithms to connect them with collision-free
paths. Our approach is general, makes no assumption about model connectivity
or object topology, and can handle polygon soup models that frequently arise
in CAD applications. We highlight the performance on many challenging
benchmarks including the Alpha puzzle, maintainability of the windscreen
wiper motion, and disassembly of a seat from the interior of a car body.
International CAD Conference (CAD'08),
2008; Best Paper Award
Computer-Aided Design and Applications;
Paper: PDF , BIB
Benchmark: the goal is to separate the two intertwined models. This is a
very difficult benchmark for motion planning due to the underlying
"narrow passage". Our planner can efficiently solve this
benchmark (less than 20 minutes).
our planner finds two different solutions. This matches the underlying symmetry
in the models and the benchmark.
seat benchmark: The problem is to remove a seat outside of a car body. It
is a difficult benchmark for motion planning approaches due to the
cluttered environment and complex geometric representation of the models.
Car Seat (Video)
Generalized Penetration Depth
Complete Motion Planning