Intelligent Systems Lecture Notes

9 September 2011 • Solving by Search

---

Outline

• State and state-space problem models.
• Graph representations.
• Problem solving as search.

How Can A Program Solve This?

How Can A Program Solve This?

Problem Modeling

• A program must represent a problem it’s trying to solve.
  • This is the data structures part.
• The problem’s representation then influences program’s algorithm.

Problem Characteristics

• Consider a problem with these characteristics:
  • No uncertainty in the problem itself.
  • Well-defined goals.
  • Well-defined actions.
  • No, or few, problem hierarchy levels.
• Variations can be accommodated, up to a point.
  • Or use another problem model.

State Representation

• A state is a representation of a problem at a particular time.
  • A state is a snapshot; there is no motion.
• A state is an abstraction of a problem.
  • Unneeded details are surpressed; only relevent details are kept.
• More formally, a state is a dictionary of (name, value) pairs.
  • Name: some problem aspect.
  • Value: that aspect’s value.

Tic-Tac-Toe State Example

State: square0: empty square1: empty square2: empty square3: X square4: empty square5: empty square6: empty square7: O square8: empty next move: X

State-Space Problem Model

• A state-space problem model is
  • A set of problem states \(S\).
  • A set \(I\) of initial states \(I\subseteq S\).
  • Possible next states \(A: S \rightarrow \mathcal{P}(S)\).
  • A goal-state test \(G: S \rightarrow \) Bool.
  • A cost function \(C: S \times S \rightarrow \mathbb{R}\).

Tic-Tac-Toe Example

• The states are the board between moves.
• The initial state is the empty board.
• The goal state is three in a row by X or O.
• Possible next states are legal moves from X or O.
• There is no cost function (or the cost function is constant).

However

• Sometimes squeezing a problem into a solution technique produces interesting results.

  

Searching

• One way to solve a state-space problem model is to search it.
• A search is an organized examination of model states, looking for a goal state.
  • “Organized” because all states should be explicitly handled (accepted or rejected).

Why Search?

• Searching is a basic problem solving technique.
  • Applicable to many problems, in whole or in part.
  • Easy to set up and run (at least at first).
  • It almost always works (with important caveats).
• Searching is also known as brute force or exhaustive search.

Search Results

• A successful search has two results:
  1. A solution to the problem.
  2. A sequence of steps to reach the problem.
• The second result is known as planning.
• An unsuccessful search is, in most cases, definitive.
  • The problem, as modeled, can’t be solved.

Why Not Search?

• Searches, although simple, can be incredibly expensive.
  • Many important problems solved by search are NP complete.
    • Route finding, bin packing, quality matching, room scheduling, ...
  • “Incredibly” means exponential or worse resource use.
  • Tricks can avoid exponential behavior.

Graphs

• A graph is natural data structure for representing state-space models.
  • “Natural” means a there’s a simple, effective transformation from a state-space model to a graph.
• Graphs are intuitive as themselves and as representations.
• There’s a rich history of graph theoretic works to draw on.
  • And there’s lots of practical work to draw on too.

Graph Definition

• A graph \(G\) is a pair of sets \(G = (V, E)\).
• \(V\) is the possibly empty, possibly infinite vertex set.
• \(E\) is the possibly empty, possibly infinite edge set.
  • \(E \subseteq V \times V\)
  • \((v_1, v_2) \in E\) is an ordered pair.
  • \((v_1, v_2) \neq (v_2, v_1)\)
• Technically, \(G\) is a directed graph.

Example Graphs

Graph Paths

• A graph path (or just path) is a sequence of vertices

  \(v_0, v_1, \ldots, v_k\)

  such that

  \((v_i, v_{i+1})\in E\) for \(0 \leq i < k\).

• That is, a path is a sequence of vertices with adjacent vertices linked by an edge.
• Path \(v_0, v_1, \ldots, v_k\) has length \(k\).

Graph Path Example

Cycles

• A graph cycle (or just cycle) is a path with repeated vertices.
  • A simple cycle only repeats the first and last vertices.

  

• Cycles are going to cause problems.

Labels

• It is often convenient to assign values called labels to edges and vertices in a graph.
  • The type of the label values can vary as needed.
• Augment graphs with label functions to assign labels:

  \(G = (V, E, L_V, L_E, \ldots)\)
  \(L_V: V \rightarrow V_L\), \(V_L\) is the vertex-label set.
  \(L_E: E \rightarrow V_E\), \(V_E\) is the edge-label set.

• Label functions are often left implicit.

Costs

• The edge cost label function (or just cost function) is used frequently enough to be singled out.
  • The cost labels are often, but not always, real numbers.
• Given an edge cost function \(C_E\), the path cost function \(C_P\) is defined as the sum of the individual edge functions.

  \(C_P(v_0, \ldots, v_k) = \sum^{k-1}_{i=0}C_E(v_i, v_{i+1})\)

State-Space Model as Graph.

• What is the graph representation of a state-space model?
  • The vertex set is the same size as the state set.
  • A vertex-label function associates states with vertices.
  • The edge set is the same size as the transformation set.
  • A edge-label function associates transformations with edges (often called moves.

State-Space Model as Graph..

• A vertex label function \(L_I : V \rightarrow\) boolean marks initial states.
  • Although a vertex set is usually more convenient.
• A vertex label function \(L_G : V \rightarrow\) boolean marks goal states.
  • A vertex set is also possible, but may be expensive to compute.
• The edge cost function, if needed, is a straightforward translation.

Three-Puzzle Example

• The fifteen puzzle has around 2·10¹³ states.

Graph Searching

• Representing a state-space model as a graph turns state-space searching into graph traversal.
• Graph traversal is a well-understood problem.
• Details to follow...

Summary

• Search is a powerful, general, expensive problem-solving technique.
• State-space problem models and common and powerful.
• Graph are a natural representation for state-space problem models.
• A state-space problem model can be searched for a solution.

References

• Mapping Tic Tac Toe-dom from RadioLab, 6 September 2011.

Credits

• Tic Tac Toe by creativevictuals under a Creative Commons BY NC ND license.
• The fifteen puzzle from Cyclopedia of 5000 Puzzles by Sam Loyd, 1914, p. 235.
• Detail from Harold Hutchinson’s hated Tube Map - 1963 by Annie Mole under a Creative Commons BY license.
• IMG_0496 by Bernat Agullo under a Creative Commons BY SA license.

---

This page last modified on 2011 September 14.