Personal tools
You are here: Home Projects In-house Projects Space-Aware Reconfiguration Space-Aware Reconfiguration
« December 2020 »
December
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
2728293031
Log in


Forgot your password?
 

Space-Aware Reconfiguration

Abstract

SAR

The workspace of 3 discs at their start configuration (empty discs) 
and at their target configuration (shaded discs). The vippodromes 
are colored by their type, blue for (i) and red for (ii), partitioning
the translation plane into valid and invalid cells. Every translation v
in a valid cell of the partition admits a collision-free one-by-one 
itinerary of translations of the discs, such that each disc is translated 
 once from its start position to some target position, after the target
position was initially translated by v.

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.

Links

  • Dan Halperin, Marc van Kreveld, Golan Miglioli-Levy, and Micha Sharir
    Space-Aware Reconfiguration

    In Workshop on the Algorithmic Foundations of Robotics (WAFR), 2020 [pdf]

  • Full version in arXiv [pdf]

  • Interactive example in GeoGebra.
    In order to add new vippodromes, choose the type of the vippodrome from the tool menu
    and choose the centers of the relevant discs.

Contacts 

Golan Levy null null
Dan Halperin http://acg.cs.tau.ac.il/danhalperin danha@post.tau.ac.il
Document Actions