Dual Search in Permutation State Spaces

Uzi Zahavi, Ariel Felner, Robert Holte, Jonathan SchaefferAAAI 2006

Abstract

Traditional search algorithms for permutation puzzles, such as IDA, often rely on geometric symmetries to improve heuristic estimates. This paper introduces a deeper logical symmetry called duality, where the roles of objects and their locations are interchangeable. By exploiting this symmetry, we present DIDA (Dual IDA), an algorithm that dynamically "jumps" between a state and its dual during search. DIDA achieves the benefits of bidirectional search—effectively searching from both ends of the problem—without the prohibitive memory costs of maintaining a search frontier. Experimental results on the Pancake puzzle and the 24-puzzle demonstrate speedups of up to 10x over standard IDA*.

Introduction

Solving combinatorial puzzles like Rubik’s Cube or the 15-puzzle efficiently is a cornerstone of AI search research. Most state-of-the-art solvers utilize Iterative Deepening A (IDA), which uses a heuristic function ($h$) to prune the search space. While researchers often use geometric symmetries (e.g., rotations) to enhance heuristics, this work identifies duality as a fundamental logical symmetry in permutation state spaces.

A significant challenge in search is the trade-off between time and memory. Bidirectional search can be faster but typically requires storing a massive "frontier" of visited states to detect when forward and backward searches meet. DIDA addresses this by using duality to "jump" between representations, gaining bidirectional-like efficiency with the low memory footprint of IDA.

Methods: Duality and DIDA*

Simple and General Duality

In any permutation puzzle, we can describe the state by mapping objects to locations (e.g., "Tile 5 is in Slot 3"). Duality simply flips this mapping ("Slot 3 is occupied by Tile 5"). In many spaces, the distance from a state $S$ to the goal $G$ is identical to the distance from its dual state $S^d$ to $G$.

The relationship between a state S, the goal state G, and the dual state Sd.
  • Simple Duality: Applies to domains where any operator can be applied to any state (e.g., Rubik’s Cube).
  • General Duality: Extends to puzzles with preconditions, such as the sliding tile puzzle, where move legality depends on the position of a specific "blank" tile.

DIDA (Dual IDA)

DIDA enhances IDA by evaluating the heuristic for both the current state $S$ and its dual $S^d$ at each node. If $h(S^d) > h(S)$, the dual state appears "further" from the goal in a way that might allow for earlier pruning. The algorithm can then jump to the dual state and continue the search from there.

Search paths in DIDA* with zero, one, and two jumps between regular and dual states.

When a jump occurs, the search effectively moves to a different region of the state space that is logically equivalent but may be more efficiently pruned. However, jumping incurs a "branching factor penalty": the algorithm loses its history of previous moves, which is normally used to prevent immediate backtracking (operator pruning).

Experimental Evaluation

The authors tested DIDA* on three major benchmarks:

  1. 17-Pancake Puzzle: In this domain ($17!$ states), DIDA showed its most dramatic improvement, solving instances 9.88 times faster than IDA, reducing average search time from 53 minutes to under 6 minutes.
  2. 24-Puzzle: Using a specialized jumping policy (J24) to handle the blank tile, DIDA outperformed standard IDA by a factor of 4.79.
  3. Rubik’s Cube: Improvements were more modest due to the high penalty of losing operator pruning in this domain, though "Jump Only at Root" (JOR) policies still yielded gains.

Discussion and Key Insights

The "Aha!" moment of this research is that objects and locations are merely labels; swapping them preserves the underlying graph structure. DIDA* acts as a "frontier-less" bidirectional search because searching from $S^d$ toward $G$ is mathematically equivalent to searching backward from $G$ toward $S$.

The primary trade-off in DIDA is the Jumping Policy*. Deciding when the benefit of a higher heuristic outweighs the cost of losing move history is critical. While "Jump If Larger" (JIL) is a robust default, domain-specific policies like J24 show that accounting for state-specific constraints can further optimize performance.

Summary updated

BibTeX
@inproceedings{zahavi2006dual,
  author = {Uzi Zahavi and Ariel Felner and Robert Holte and Jonathan Schaeffer},
  title = {{Dual Search in Permutation State Spaces}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure