Personal tools
You are here: Home CG seminar 2023 Rubik Tables, Stack Rearrangement, and Multi-Robot Routing
« January 2023 »
January
SuMoTuWeThFrSa
1234567
891011121314
15161718192021
22232425262728
293031
Log in


Forgot your password?
 

Rubik Tables, Stack Rearrangement, and Multi-Robot Routing

Wednesday, November 30th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)

underline

Jingjin Yu, Rutgers University

Abstract:

In a basic Rubik table problem, there are $n$ item types, each with a multiplicity of $n$. These $n^2$ items are randomly placed in an $n x n$ table, one in each cell. In a shuffle, a row (resp., column) of the table may be permuted to achieve an arbitrary configuration of the items in that row (resp., column). We ask how many shuffles are needed to sort the table so that type $i$ items occupy column $i$ of the table. Somewhat surprisingly, $2n$ shuffles suffice. Rubik tables and its many generalizations enable the successful tackling of difficult "sequential combinatorial optimization" problems in robotics, including stack rearrangement and multi-robot path planning, resulting in polynomial time algorithms for computing asymptotically optimal solutions that were previously not possible, to our knowledge. In particular, using the Rubik table abstraction as a building block, we are able to achieve $1.x$ asymptotic makespan optimality for multi-robot path planning on grids in polynomial time, with high probability.
Document Actions