On Methods To Decide Solvability of Transformation Problems

P. Florath

Abstract

This paper presents a structural approach to determining the solvability of transformation problems by partitioning state spaces into "separated subsets." By identifying "sink," "source," and "island" regions, the proposed method allows for the early termination of search processes in unsolvable problem instances. The approach is particularly effective in binary-coded state spaces where operators are defined by Boolean conditions, enabling computational efficiency through under- and over-approximation strategies.

Introduction

In classical artificial intelligence and operations research, solving a transformation problem typically involves searching through a problem space—a graph of states and transitions—to find a path from an initial state to a goal state. However, many problems are inherently unsolvable. Standard search algorithms often exhaust significant time and memory exploring every possible path before concluding that no solution exists.

Peter Florath argues that efficiency can be drastically improved by analyzing the structure of the problem space itself. If it can be proven that a goal state is unreachable from a starting state based on the "topography" of the space, the search process can be terminated immediately. The challenge lies in formally defining these structural properties and detecting them within complex, high-dimensional spaces.

Methodology: Separated Subsets

The core of the proposed method is the classification of state space $S$ into type-k-separated subsets:

  1. Type-1 (Sink): A subset where no operators lead out of the set.
  2. Type-2 (Source): A subset where no operators lead into the set from the outside.
  3. Type-3 (Island): A subset that is both Type-1 and Type-2, representing an isolated region.

Based on these definitions, Florath develops specific Decision Rules: if the initial state is within a Type-1 subset and the goal is outside it, or if the goal state is in a Type-2 subset and the initial state is outside it, the problem is guaranteed to be unsolvable.

A directed graph illustrating the reachability between states $s_1$ through $s_9$, highlighting how certain regions can become isolated.

Binary-Coded Problem Spaces and Approximation

The paper applies these structural concepts to binary-coded problem spaces, where states are represented as bit-strings (vectors of 0s and 1s) and operators are defined by Boolean conditions. To manage the complexity of these spaces, the author introduces approximation techniques:

  • Underapproximation: Simplifying complex operator conditions into strict "conjunctive" forms (AND gates). If a problem is solvable in this restricted space, it is guaranteed to be solvable in the original.
  • Overapproximation: Using permissive "disjunctive" forms (OR gates). If a problem is unsolvable in this expanded space, it is definitely unsolvable in the original.
A transition diagram for a synthetic 4-bit state space used to demonstrate the construction of admissible systems for solvability decisions.

Key Results and Insights

The shift from pathfinding (the "how") to reachability (the "if") provides a powerful tool for computational logic. A primary result is Theorem 1, which proves that a problem space is "totally solvable" (every state can reach every other state) if and only if it contains no non-empty proper separated subsets. Furthermore, the paper provides an iterative algorithmic method to construct these separated subsets for conjunctive binary-coded spaces, making the theoretical framework computationally applicable.

Limitations and Future Work

While the method offers significant potential for saving computational effort, it requires formal knowledge of the operators (the "rules" of the space), which may not be available in "black box" scenarios. Additionally, the overhead of calculating separated subsets is only justified if the time saved by avoiding unsolvable searches exceeds the analysis time. Future research is needed to extend these definitions to more general, non-linear problem spaces and varied data structures.

Summary updated

BibTeX
@inproceedings{florath1975methods,
  author = {P. Florath},
  title = {{On Methods To Decide Solvability of Transformation Problems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1975},
}
Figure