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.
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?
Daniel C. Dennett, “Consciousness Explaned”
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 : N1 … Nn
Set of arcs : (N2,N3), (N3, N4), … (Nm, Nn)
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 | |
| S0 | S0 | S1 |
| S1 | S1 | S0 |
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, S0, and an accepting state Sn. 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!
Tags: finite state machine, graph theory, state space search