How General is the State-Space Search Paradigm?

The state-space concept is fundamental to the theory of computation -- e.g., in finite-state automata.

Distinctions arise in terms of transitions from one state to another.

AI has traditionally concerned itself with discrete state spaces. EE (Control theory) has concerned itself with continuous state spaces (vector spaces with real or complex bases).

Neural networks work mainly in continuous spaces.

Viewing All Computation as Search

State: Contents of all memory of a machine.

Move: The execution of an instruction.

But most programs do not keep "choosing" what instruction to execute next. The program fixes most of the sequence.

Two-Person, Zero-Sum Games

Playing many games can be treated performing searches in state spaces.

Geometric Search Problems

Many problems involve geometry in one way or another. Examples....

-- Spatial puzzles such as pentominoes.
-- Optimal packing of 2D or 3D objects into fixed spaces.
-- Robot path planning, navigation, solving mazes.

Various heuristics may apply to such problems...
-- avoid slack or small isolated spaces.
-- try to reduce Euclidean distance from current state to the goal.
-- project the problem to a lower-dimensional space and compute a distance in that space.
-- try to form pieces of the solution, and then work with those pieces in a state space of lower dimension (and at a higher level of abstraction).

Agenda Mechanisms

When a complicated set of tasks is being carried out, the remaining work might best be described using a list called an agenda.

An agenda is analogous to the OPEN list.

Each item on the agenda describes a task to be performed along with justifications for that task. A priority for the task is determined from its justifications.

The highest priority task is selected for execution at each cycle.

The AM and Pythagoras programs, described in Chapter 10, use agendas.

Case-Based Reasoning as an Approach to Search

A large complicated state space may have important "landmarks" in it that correspond to the solutions of previously solved problems.

If a new problem shares common features with one of these previously solved problems, then the new search may benefit by starting from the landmark rather than from a default start state.

In addition, special moves can be determined that take advantage of the difference between the solved problem and the new problem to move the search in the right direction.

Last modified: November 2, 1998

Steve Tanimoto

tanimoto@cs.washington.edu