Operator Decomposability: A New Type of Problem Structure

Richard E. KorfAAAI 1983

Introduction

In classical AI, solving a problem typically involves searching through a state space using algorithms like A. While effective, this approach is computationally expensive when solving many instances of the same problem from scratch. In his 1983 paper, Richard Korf introduces operator decomposability*, a structural property that allows problems to be solved using a "Macro Problem Solver" without any search at solve-time. By identifying how state variables interact, we can build a strategy once and apply it to any instance with minimal effort.

The Macro Problem Solver

The core of Korf's approach is the use of macros: sequences of primitive moves designed to achieve a specific subgoal—such as placing a single tile in its home position—without permanently disturbing subgoals already achieved. This method relies on two types of decomposability:

  1. Total Decomposability: An operator's effect on one part of the state depends only on that part's current state, independent of everything else.
  2. Serial Decomposability: A more common condition where an operator's effect on a state variable depends only on that variable and those that precede it in a specific solution order.

These properties allow for the construction of a Macro Table, a matrix where columns represent subgoals and rows represent possible positions.

Macro Table for the Eight Puzzle showing sequences of moves for different tile positions.

Case Studies: From Sliding Tiles to Rubik's Cube

Korf demonstrates the power of decomposability using several classic puzzles:

  • The Eight Puzzle: All 181,440 possible instances can be solved using a table of just 35 macros.
  • Rubik’s Cube: Despite having over 43 quintillion states, the puzzle can be solved from any starting position using only 238 macros.
  • Think-a-Dot: A toy involving marbles falling through gated channels, used to illustrate complex serial dependencies where the state of a gate depends on the paths of previous marbles.
The physical structure of the Think-a-Dot puzzle, illustrating the gated channels that create serial dependencies.

Key Insights

  • Search vs. Structure: If a problem is serially decomposable, search is unnecessary at solve-time. One trades a one-time "learning" cost (finding the macros) for a near-zero "application" cost.
  • Representation is Everything: Decomposability is often a property of the state-vector representation chosen. A "dual representation" of the Eight Puzzle might not be decomposable, making it much harder to solve without search.
  • Macro Restoration: A macro can "break" previous subgoals during execution, provided it restores them by the time the sequence finishes. This allows for complex problem-solving beyond simple greedy algorithms.

Conclusion and Results

The efficiency gains from identifying this structure are staggering. Once a macro table is constructed, the time complexity of solving a puzzle becomes linear relative to the number of subgoals, rather than exponential relative to the depth of a search tree. While the resulting solutions may be suboptimal in length, the ability to solve billions of configurations with a handful of pre-learned moves marks a significant advancement in problem-solving theory. Future work involves automating the discovery of the representations and macros that unlock this decomposability.

Summary updated

BibTeX
@inproceedings{korf1983operator,
  author = {Richard E. Korf},
  title = {{Operator Decomposability: A New Type of Problem Structure}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
}
Figure