Token Swapping and Robot Pivoting

Erik Demaine, MIT

..... .OOO. .O... .OOO. .O.O. .OOO. .....

Hardness of Token Swapping on Trees

Oswin Aichholzer•Erik Demaine•Matias Korman•Jayson Lynch•Anna Lubiw•Zuzana Masárová•Mikhail Rudoy•Virginia Vassilevska Williams•Nicole Wein

Token Swapping Problem

  • Given a graph
    • with one token per vertex
    • and a destination for each token
  • How many swaps along edges do we need?

Cayley Graph View

• Positions of tokens• Permutation in $S_n$
• Graph edge• Transposition (swap)
• Configuration space• Cayley graph
• Reconfiguration• Path in Cayley graph
https://commons.wikimedia.org/wiki/File:Symmetric_group_4;_Cayley_graph_1,2,6_(1-based).png

Connection to Bubble Sort

Path graphSorting by swapping adjacent elements
Min number of swapsNumber of inversions / cost of bubble sort

History

  • Studied in discrete mathematics, theoretical computer science, network engineering, robot motion planning, game theory
  • Cayley [1849] solved clique version
  • Knuth [1968] solved path version
  • Also solved for cycles, stars, brooms, bicliques
  • NP-complete [Amir & Porat 2015]
  • APX-complete with 4-approximation
    [Miltzow et al. 2016]
  • W[1]-hard with respect to number of swaps [Bonnet et al. 2018]

Token Swapping in Trees

History: Trees

  • Akers & Krishnamurthy [1989] first studied tree version as routing in proposed network topology
  • Three 2-approximation algorithms
    [Akers & Krishnamurthy 1989; Vaughan 1991; Yamanaka et al. 2015]
  • Family of algorithms (including past algorithms) cannot beat $4 \over 3$-approximation [Biniaz et al. 2019]

  • OPEN: NP-hard?
  • OPEN: Better approximation?

Happy Leaf Conjecture

  • Conjecture: [Vaughan 1991] Never need to swap a token that’s already at destination leaf
  • Counterexample: [Biniaz et al. 2019]
    (smallest possible)
  • Any algorithm satisfying conjecture cannot beat $4 \over 3$-approximation [Biniaz et al. 2019]

Our Results

  • Token swapping is NP-hard on trees
    • Also for parallel token swapping, where we can swap a matching in each round
  • Algorithms that stay within 1 of shortest path cannot beat 2-approximation

Reduction from Star Subseq.

  • Rephrasing/simplification of Garey & Johnson's “MS6: Permutation Generation”:
    • Given tokens’ start/destination on $\bm n$-star
    • Given sequence of edges (incident to center)
    • Can you get from start to destination
      via swaps that form a subsequence?

0/1-Weighted Token Swapping

  • Each token $t$ has a weight $w(t) \in \{0,1\}$
  • Cost of swapping $t \leftrightarrow t'$ is $w(t) + w(t')$
$w(~~~~~~) = 1$
$w(~~~~~~) = 0$

Unweighted Token Swapping

  • Idea: Simulate each weight-1 token
    with long path of tokens
    • Increase cost gap between
      “good” and “bad” solutions
    • $\leq n$ swaps from weight-0 tokens negligible

  • Challenge: Slack $\Rightarrow$ options no longer forced

Characterizing Universal Reconfigurability of Modular Pivoting Robots

Hugo Akitaya•Erik Demaine•Andrei Gonczi•Dylan Hendrickson•Adam Hesterberg•Matias Korman•Oliver Korten•Jayson Lynch•Irene Parada•Vera Sacristán

Reconfiguration by Pivots

  • Given two configurations of $n$ robots/modules
  • Reconfigure via a sequence of pivots
  • Maintain connectivity via edges throughout
    (including during pivot, except for the pivoted robot)
..... .OOO. .O... .OOO. .O.O. .OOO. .....
..... .OOO. .O... .OOO. .O.O. .OOO. .....
..... .OOO. .O.O. .OOO. ...O. .OOO. .....

Square Pivoting Models

Restricted moves

Leapfrog move

Monkey moves

Hexagon Pivoting Models

Restricted move

Monkey move

Known Results: Hexagons

  • Restricted moves are universal if no forbidden pattern[Nguyen, Guibas, Kim 2001]

Restricted move

Forbidden pattern

Known Results: Squares

  • Restricted moves are universal if no forbidden pattern[Sung, Bern, Romanishin, Rus 2015]
  • Restricted moves are universal given 5 extra robots on external boundary[Akitaya, Arkin, Damian, Demaine, Dujmović, Flatland, Korman, Palop, Parada, van Renssen, Sacristán 2019]

Restricted moves

Forbidden patterns

Our Results

  • No forbidden patterns or extra robots

Model:RestrictedRestricted + LeapfrogRestricted + Leapfrog + Monkey
HexagonsPSPACE-hardUniversal:$O(n^3)$ moves
SquaresPSPACE-hardPSPACE-hardPSPACE-hard

Restricted vs. Monkey Moves

  • Some configurations are rigid under restricted moves[Nguyen, Guibas, Kim 2001]
  • Monkey moves unlock these examples
. . . . . . O . . . . . . . O O . . . . . . O . O . O . . . . . . . O O . O O O O O . . . O O O . . . O O O . . . O O . . . . . . . O . O . O . . . . . . O O . . . . . . . O . . . . . . . . . . . . . . .

Hexagon Algorithm Overview

  • Goal: Canonicalize
    into vertical strip
. . . . . . . . . . . O . . . . . . . . O . . . . . . . . O . . . . . . . . O . . . . . . . . O . . . . . . . . O . . . . . . . . O . . . . . . . . O . . . . . . . . O . . . . . .

Hexagon Algorithm Overview

  • Goal: Canonicalize
    into vertical strip

  • If a robot is
    • on the convex hull,
    • whose removal preserves connectivity,
    then can pivot robot directly to vertical strip
  • Otherwise, we need to make such a robot…
. . . . . . . . . . . O . . . . . . . . O . . . . . . . . O . . . O O . . O O O . 1 . O O . O O O . O O . O . O . . . O . . O . . . . . O . O O . O O O . . O O . . . O . . . . . .

Hexagon Algorithm: Phase 1

  • Remove degree-1 vertices
. . . . . . O O . . . O O O . . . . . . . O 1 O 1 O . . O . . . . . . O . . O . . O . O . . . . O . . O O O . . O . . . . . O . . . . . . .
Case analysis

Hexagon Algorithm: Phase 2

  • 2-connected components connected by bridges
  • Merge leaf 2-connected component into others
. . . . . . . . . . . . . . . . . . . . . . 1 . . . . . . 1 . . . . . . . . 1 . . . . . . 1 . . . . O . O . 1 . . O O O O . . . . O . O . O 2 . . . . . . O . . . O . O O O . . 2 O O O O . 1 . . . O . . . 1 1 1 . . . 2 1 . . . 1 . . . . 1 1 1 1 . . 2 1 . . . 1 . . . 2 1 1 . . . . . . 1 . . . . . . . . .
Merge procedure

Hexagon Algorithm: Phase 3

  • Now 2-connected
  • Using a modified merge procedure, can produce a robot
    • on the convex hull,
    • whose removal preserves 2-connectivity
  • Pivot robot directly to vertical strip
. . . . . . . . . . . O . . . . . . . . O . . . . . . . . O . . . O O . . O O O . 1 . O O . O O O . O O . O . O . . . O . . O . . . . . O . O O . O O O . . O O . . . O . . . . . .

Hexagon Algorithm Analysis

  • Phase 1 (leaf removal): $O(n^2)$ moves
  • Phase 2 (merging 2-connected components):
    • $O(n^2)$ moves per 2-connected component
    • $\Rightarrow O(n^3)$ overall
  • Phase 3 (canonicalization):
    • $O(n^2)$ moves per robot $\Rightarrow O(n^3)$ overall
    • $\Rightarrow O(n^3)$ moves overall
  • $\Rightarrow O(n^3)$ moves overall

  • OPEN: Do $O(n^2)$ moves suffice?
  • OPEN: How fast with parallel moves?

Our Results

  • No forbidden patterns or extra robots

Model:RestrictedRestricted + LeapfrogRestricted + Leapfrog + Monkey
HexagonsPSPACE-hardUniversal:$O(n^3)$ moves
SquaresPSPACE-hardPSPACE-hardPSPACE-hard

Motion-Planning-Through-Gadgets Framework

  • Which local finite-state gadgets suffice to prove single-agent motion planning PSPACE-complete?[Demaine, Grosof, Lynch, Rudoy 2018]•[Demaine, Hendrickson, Lynch 2020]•[Ani, Bosboom, Demaine, Diomidov, Hendrickson, Lynch 2020]•[Ani, Demaine, Hendrickson, Lynch 2021]

  • Example:
    Locking 2-toggle
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . O O . . . . . . . 2 . . . . O . O O O . O . . . . 2 2 . . . O O O . . O O O . . . 2 . 2 . . O . O . O . O . O . . 2 . 1 2 . O . . . O O . . . O . 2 . . 1 2 O . 2 . O . O . 2 . O 2 . . . . 2 . 2 2 O . . O 2 2 . 2 . . . . . 2 . . . . . . . . . 2 . . . . . . 2 . 2 O . . O 2 . 2 . . . . . . . 2 2 . . . . . 2 2 . . . . . . . . 2 . O . . O . 2 . . . . . . . . . . 1 O . O 1 . . . . . . . O . . . . . O O . . . . . O . . O O . . . O . . . O . . . O O . O . O . . O O O O O O . . O . O . . . . . O . . . . . O . . . . . O O O . O . . O O . . O . O O O . . . . O . O O . O O . O . . . . O O O O O . O . . O . O O O O O . O . . . O . . . . . O . . . O . . . O O . O . . . . O . O O . . . . . . . . O . . . O . . . . . . . . O O O . O . . O . O O O . . . . . . . O . O . O . O . . . . . . . O O . . . O O . . . O O . . . . . . O O . . O . . O O . . . . . . O . O . . . . . . O . O . . . . . . . . . . O . . . . . . . . . . O . . O . . . . O . . O . . . . . . O O O . O . O O O . . . . . . O O O . O . . O . O O O . . . O . . . . . . O . . . . . . O . O O O O . O O . . O O . O O O O . . . . O . O . O . O . O . . . . O O O . O . . . . . . O . O O O . . . . 1 O . . O . . O 1 . . . . O . O 1 . O . . . . O . 1 O . O . O O 1 . . O . O . O . . 1 O O . . O . . . . O . . O . . . . O . . . . . . . . O O O . . . . . . . . . . . 2 . . O O . . 2 . . . . . . . . 2 2 . . O . . 2 2 . . . . . . . 2 . 2 . . . . 2 . 2 . . . . . . 2 . . . . O . . . . 2 . . . . . 2 . 2 2 . O O . 2 2 . 2 . . . . 2 O . 2 . O . O . 2 . O 2 . . . 2 . O . . O . . O . . O . 2 . . 2 . . O . O . . . O . O . . 2 . 2 . . . O O . . . . O O . . . 2 2 . . . . O . . . . . O . . . . 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Our Results

  • No forbidden patterns or extra robots

Model:RestrictedRestricted + LeapfrogRestricted + Leapfrog + Monkey
HexagonsPSPACE-hardUniversal:$O(n^3)$ moves
SquaresPSPACE-hardPSPACE-hardPSPACE-hard

Token Swapping and Robot Pivoting

Erik Demaine, MIT

..... .OOO. .O... .OOO. .O.O. .OOO. .....