AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, SWS, RG1, MMCI   Info

AG Audience

English

30 Minutes

Reconfiguring arrangements of objects is a fundamental task in many theoretical and practical fields. A typical task involves moving a large group of agents from an initial configuration to a desired goal efficiently, while avoiding collisions and respecting constraints, such as maintaining the overall connectivity of the arrangement. In the sliding squares model, a given start configuration of n square-shaped modules, must be moved from a starting arrangement to a target configuration through a sequence of atomic, sequential moves, keeping the underlying grid graph connected. Since all modules are identical, only the shape of the arrangement matters. Recent work from Computational Geometry has focused on minimizing the total number of moves, resulting in schedules with O(n^2) moves in three dimensions, and O(nP) for a 2-dimensional arrangement of n modules with bounding box perimeter P. However, these approaches are fully sequential, unlike practical settings, in which modules can move in parallel, which allows faster reconfiguration but introduces additional challenges. Coordinating parallel motions requires careful planning to maintain connectivity and prevent collisions. In this work, we present the first results for parallel reconfiguration in the sliding squares model without restrictions on the input. Our main algorithmic result is a weakly in-place algorithm that achieves makespan of O(P), where P is the perimeter of the union of the bounding boxes of start and target configurations.

Ina Geisler

+49 681 9325 1802

--email hidden

Zoom

passcode not visible

logged in users only