On rearrangement of items stored in stacks

DOI10.1007/978-3-030-66723-8_31zbMATH Open1469.68137arXiv2002.04979OpenAlexW3196856498MaRDI QIDQ3382003FDOQ3382003

Mario Szegedy, Jingjin Yu

Publication date: 20 September 2021

Published in: Algorithmic Foundations of Robotics XIV (Search for Journal in Brave)

Abstract: A great number of robotics applications demand the rearrangement of many mobile objects, e.g., organizing products on shelves, shuffling containers at shipping ports, reconfiguring fleets of mobile robots, and so on. To boost the throughput in systems designed for solving these rearrangement problems, it is essential to minimize the number of atomic operations, e.g., the pick-n-places of individual objects. However, this optimization task poses a rather difficult challenge due to complex inter-dependency between objects, especially in high-density settings. In tackling the aforementioned challenges, we develop a novel algorithmic tool, Rubik Tables, that provides a clean abstraction of object rearrangement problems as the proxy problem of shuffling items stored in a table or lattice. In its basic form, a Rubik Table is an $nimesn$ table containing $n^2$ items. We show that the reconfiguration of items in such a Rubik Table can be achieved using at most $2n$ column/row shuffles in the partially labeled setting, where each column (resp., row) shuffle may arbitrarily permute the items stored in a column (resp., row) of the table. When items are fully distinguishable, additional $n$ shuffles are needed. Rubik Tables allow many generalizations, e.g., to higher dimensions. Using Rubik Table, we have designed a first constant-factor optimal algorithm for stack rearrangement problems. We show that, for $nd$ items stored in $n$ stacks of depth $d$ each, using one empty stack as the swap space, $O(nd)$ stack pop-push operations are sufficient for an arbitrary reconfiguration of the stacks where $dle{n}^{fracm2}$ for arbitrary fixed $m>0$. Rubik Table results also allow the development of constant-factor optimal solutions for solving multi-robot motion planning problems under extreme robot density. These algorithms based on Rubik Table results run in low-polynomial time.

Full work available at URL: https://arxiv.org/abs/2002.04979

Recommendations

• The stack loading and unloading problem
• Sorting with Complete Networks of Stacks
• The Complexity of Sorting with Networks of Stacks and Queues
• Competitive analysis of on-line stack-up algorithms
• Stack-up algorithms for palletizing at delivery industry

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27) Artificial intelligence for robotics (68T40)

Cites Work

• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• Sorting in \(c \log n\) parallel steps
• Online rules for container stacking
• Approaches for solving the container stacking problem with route distance minimization and stack rearrangement considerations
• Sorting twice through a stack
• Asymptotic aspects of Schreier graphs and Hanoi Towers groups.
• On multiple moving objects
• Path Planning among Movable Obstacles: A Probabilistically Complete Approach
• Motion planning in the presence of movable obstacles
• Perfect matchings in \(O(n\log n)\) time in regular bipartite graphs
• Planning Among Movable Obstacles with Artificial Constraints
• Title not available (Why is that?)

Cited In (2)

• Sorting twice through a stack
• Stack sorting with increasing and decreasing stacks

This page was built for publication: On rearrangement of items stored in stacks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3382003)