On rearrangement of items stored in stacks

DOI10.1007/978-3-030-66723-8_31MaRDI QIDQ3382003zbMATH OpenOpenAlexFDO

Authors Jingjin Yu, Mario Szegedy

Publication date 20 September 2021

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

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

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)

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.

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

Cites work

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

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)