Personal tools
You are here: Home CG seminar 2020 Space-Aware Reconfiguration
« September 2020 »
Log in

Forgot your password?

Space-Aware Reconfiguration

Wednesday, May 27th, 2020, 16:10

Checkpoint 480

Zoom: Request the link from Dan Halperin or Golan Levy


Space-Aware Reconfiguration

Golan Miglioli-Levy, TAU


We consider the widely studied problem of reconfiguring a set of physical objects into a desired target configuration, a typical (sub)task in robotics and automation, arising in product assembly, packaging, stocking store shelves, and more.
In this paper we address a variant, which we call space-aware reconfiguration, where the goal is to minimize the physical space needed for the reconfiguration, while obeying constraints on the allowable collision-free motions of the objects.
Since for given start and target configurations, reconfiguration may be impossible, we translate the entire target configuration rigidly into a location that admits a valid sequence of moves, so that the physical space required by the start and the translated target configurations is minimized.
We investigate two variants of space-aware reconfiguration for the often examined setting of $n$ unit discs in the plane, depending on whether the discs are distinguishable (labeled) or indistinguishable (unlabeled). For the labeled case, we propose a representation of size $O(n^4)$ of the space of all  feasible translations, and use it to find, in $O(n^6)$ time, a shortest valid translation, or one that minimizes the enclosing circle or axis-aligned box of both the start and target configurations.
For the significantly harder unlabeled case, we show that for almost every direction, there exists a translation that makes the problem feasible.
We use this to devise heuristic solutions, where we optimize the translation under stricter notions of feasibility.
We present an implementation of such a heuristic, which solves unlabeled instances with hundreds of discs in seconds.
Joint work with Dan Halperin, Marc v.Kreveld and Micha Sharir.


Document Actions