BARC Talk by Tzvika Geft

Abstract

On Two-Handed Planar Assembly Partitioning with Connectivity Constraints

 Assembly planning is a fundamental problem in robotics and automation, in which we design a sequence of motions to bring the separate constituent parts of a product into their final placement in the product. Assembly planning is naturally cast as a disassembly problem, where assembly partitioning is a key problem that arises: Given a set A of parts, and a direction d, find a subset S of A, referred to as a subassembly, such that S can be rigidly translated to infinity along d without colliding with A\S. While assembly partitioning is efficiently solvable, practical consideration further dictates that it should be easy to hold the parts in a subassembly together.

This motivates the problem we study, called connected-assembly-partitioning, which additionally requires each of the two subassemblies, S and A\S, to be connected. We show that this problem is NP-complete, settling an open question posed by Wilson et al. (1995) a quarter of a century ago, even when A consists of unit-grid squares (i.e., grid cells of a unit grid).

Towards this result, we prove the NP-hardness of a new Planar SAT variant, in which variables appearing in a clause have some locality. On the positive side, we give an O(2^k n^2)-time fixed-parameter tractable algorithm (requiring efficient pre-processing) for an assembly A consisting of polygons in the plane, where n=|A|, k=|S|. We also describe a special case of unit-grid square assemblies, where a connected partition can always be found in O(n)-time. Each of the positive results sheds further light on the special geometric structure of the problem.

This is a joint work with Pankaj K. Agarwal, Boris Aronov, and Dan Halperin.

Bio
Tzvika Geft is a Ph.D. candidate at the Computational Geometry Lab, led by Dan Halperin, at Tel Aviv University, where he also completed his M.Sc. degree. Prior to that he obtained a B.Sc. degree in computer science at Tel Aviv University. Tzvika is interested in confronting NP-hard motion planning and transportation problems by improving the understanding of what makes such problems hard.