Recent Comments

    Categories

    State Space Search and a Simple Introduction to Graph Theory

    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 directed graph showing nodes A, B, and C with edges (A,B),(B,C), and (C,B).
    Figure 1: Directed graph.

    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 rooted graph with A as the root, and B to F as children.
    Figure 2: Rooted graph.

    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.

    Finite State Machine for flipping a states.
    Figure 3: Finite State Machine (FSM)
    01
    S0S0S1
    S1S1S0
    Table 1: Transition table for the FSM in Figure 3. Input is on the top row, and states are the first column. The transition states are at the intersection.

    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.

    Moore machines for binary digits.
    Figure 4: The first finite state acceptor identifies a stream of binary digits “111”. S3 is only reached with that input stream. The second finite state acceptor accepts only three consecutive “1”‘s.

    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.

    Graph of the TSP problem.
    Figure 5: TSP problem.

    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.

    Tree graph of the TSP problem
    Figure 6: TSP Tree, partially filled, searching all solutions to the TSP problem

    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!

    Leave a Reply

    You can use these HTML tags

    <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>