Expansive Voronoi Tree: A Motion Planner for Assembly Sequence Planning

One major challenge in Assembly Sequence Planning (ASP) for complex real-world CAD-scenarios is to find an appropriate disassembly path for each assembled part. Complex real-world scenes are characterized by a large installation space. There each part has many different possible disassembly paths that differ in length and clearance. However, due to tight packing in the installation space, these paths can contain narrow passages. Therefore a motion planner is needed that is able to globally search for a reasonable path and to locally overcome narrow passages. Moreover, since motion planning requests are executed in the ASP context over and over again for many parts, both for those that can be disassembled in the next step and for those that cannot be yet, the motion planner has to be reliably fast. We present a new rigid body motion planner, called Expansive Voronoi Tree (EVT), which is optimized for complex ASP scenarios. The EVT estimates a globally reasonable path using a General Voronoi Diagram of the complete scene. With a novel EST-based sampling strategy, which is the contribution of this paper, it then locally explores the environment along the estimated path. The EVT automatically adapts to different clearance situations. It passes wide environments quickly and samples densely at narrow passages. We compare our EVT to state of the art motion planners which use different sampling strategies on a real-world data set consisting of a large subset of a car. The experiments show that the EVT is reliably many times faster and delivers shorter paths.