Personal tools
You are here: Home CG seminar 2023 Rubik Tables, Stack Rearrangement, and Multi-Robot Routing
« January 2023 »
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)


Jingjin Yu, Rutgers University


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