Previously I’ve talked about predicate calculus and inference rules to find solutions to problems in artificial intelligence. These rules define the space that is searched when trying to solve a problem through AI. This space can quickly become very large in complex problems and we need efficient ways to search that space. We may find that no solutions exists, or the problem solver can end up in an infinite loop. Even if we find a solution, are we sure it’s the optimal one? How long will it take for the solver to find a problem? *State-space search* theory is what we use to tackle this problem. We will use a *state-space graph* and *graph theory* to analyze the complexity of the problem and design the best way to solve it.

Daniel C. Dennett, “Consciousness Explaned”

In order to cope, an organism must either armor itself (like a tree or a clam) and “hope for the best”, or else develop methods for getting out of harm’s way and into the better neighborhoods of the vicinity. If you follow this later course, your are confronted with the primordial problem that every agent must continually solve: now what do I do?

## Graph Theory

Firstly, we need to define what a *graph *is. Simply put a graph is a set of *nodes*. Between these nodes we have a set of *edges *or *links*. We can define this in mathematical notation the following way[efn_note](Luger, George F.; Stubblefield, William A, *Artificial intelligence: structures and strategies for complex problem solving* 1998)[/efn_note].

Set of nodes : `N`

_{1} … N_{n}

Set of arcs : `(N`

_{2},N_{3}), (N_{3}, N_{4}), … (N_{m}, N_{n})

In our use of graph theory, each node in our graph represents a *state *of the world in our problem, and the edges represent the transition between these states.

A graph can also be *directed*. In these example the edges have directions assigned to them. For example an `edge(A,B)`

will describe a state transition from *A* to *B*. However, unless `edge(B,A)`

exists, the problem solver cannot go from state *B* to *A*.

A *path *is a sequence of nodes through successive edges. In Figure 1, we could represent a path from A to C as [A,B,C].

A *rooted graph* has one node which all other nodes are connected to. The root node has no parent, and all other nodes are its children.

A *tree *is a graph with unique paths between every pair of nodes. That is to say, there is at most one path between two nodes. Figure 1 cannot be a tree because two paths occur between B and C. However, Figure 2 is a tree, and most trees also contain a root. The requirement of at most one path between nodes also leads to trees having no loops.

## Using Graph Theory to Build Finite State Machines

Our discussion on graphs allows us to build abstract models for computational devices. These models represent automation for traversing paths in a graph. This abstraction we call a *finite state machine (FSM)*. These are special graphs that are directed, finite, and connected.

A FSM can be described as a finite set of states (S), a finite set of input values (I), and a function (F) that defines the transition between states.

0 | 1 | |

S_{0} | S_{0} | S_{1} |

S_{1} | S_{1} | S_{0} |

The example above shows a very simple FSM. The transition function works as a flip. If the input is 0, then no change in state is made. But if the input is 1, the state flips between the states.

## Finite State Acceptor Machines (Moore Machines)

A special type of FSM is presented below. In this example, we have a starting state, S_{0}, and an accepting state S_{n}. This machine will recognize a specific input stream. Here are a few examples.

## State Space Representation

Ultimately these graphs help use map out the state space of a problem. Each node can represent a partial solution state to the problem. Edges in the graph represent the actions used to solve this problem. Let’s look at this using The Traveling Salesman problem.

In this problem, a salesmen must travel between 4 cities and return home.

In this problem we would like to find a path from A, then visiting each node, and back to A. An example solution would be `[A, B, D, C, A] = 14 + 29 + 28 + 20 = 91`

. But is this the shortest path? State space search is all about trying to find the best (in this case the minimum length path). We can represent the state search as a tree.

As we can see from Figure 6, the state space for this problem can grow very quickly with a large number of nodes. Graph theory helps us visualize this and even more importantly, come up with with more efficient ways to search state spaces for potential solutions. Those will be addressed in my next blog. Until then, stay tuned!

## Recent Comments