Posts Tagged ‘state space search’

How to Design an Effective State Space Search

After determining the state space for a problem, we need to design a state space search algorithm for solutions. The importance of decisions regarding searching state space for AI problem solvers can’t be understated. Most problems where AI tools are useful in solving, are very complex and therefore the state spaces are exponentially large. Two approaches could be used. We could use our data and work towards our goal, or we could define our goal and find out what states lead to that goal. We also need to decide in what order to search the graph. This leads us to our discussion on data-driven search, goal-driven search, breadth-first search, and depth-first search[efn_note](Luger, George F.; Stubblefield, William A, Artificial intelligence: structures and strategies for complex problem solving 1998[/efn_note].

Two roads diverged in a yellow wood,
And sorry I could not travel both
And be one traveler, long I stood
And looked down one as far as I could
To where it bent in the undergrowth;
Then took the other…,,

Robert Frost, “The Road Not Taken”

Data-driven search

Data-driven search, also called forward chaining, we start with the data and a set of logical rules for changing states. We apply these rules to create new facts, and iteratively continue until we find a solution or fail.

Data-driven search is most appropriate when:

  1. Most of the data is given in the statement of the problem. This is usual when the problem involves high level interpretations.
  2. If there are many potential goals, but only a few ways to use the data.
  3. If it is difficult to define the goal. It may not be possible to start at a goal if you aren’t able to clearly define it.
Graph showing a data-driven state space search.
Figure 1: Data-Driven Search.

An example could be if a person claims to be a distance relative with a common ancestor with an unknown name that is at most eight generations back. A program that reads sonar readings and interprets them as either small submarines or marine wildlife is another example. A final example is an expert system that classifies plants by family, genus, species, etc.

Goal-driven search

Conversely, we could start with our goal and determine which rules we need to be true in order to arrive at the goal. We create subgoals this way working backwards until we arrive at the data we have defined for our problem.

  1. If the goal is given or easily defined. Theory provers tend have a structure like this. The problem solver gives a solution, and then tries to prove it.
  2. If there is a large number of rules that match the problem. This leads to a large number of potential goals. If we decide to choose a goal first, the state space trimmed off is much larger and therefore a more efficient strategy.
  3. If the problem data isn’t given, we have no choice but to use a goal-driven approach. This approach is great for providing a guide to effective data gathering.
Graph showing a goal-driven state space search.
Figure 2: Goal-Driven Search.

Some goal-driven examples if the same person from the data-driven example instead gives you the name of the common ancestor, then finding the verification is goal-driven. Diagnosing automobile problems, and theorem provers for plane geometry are two more examples.

Depth-first search

Search direction is only one way we can design the state space search algorithm. Another way to enhance the performance is through the order in which child nodes are examined.

Depth-first searches go deep into the search space whenever possible. It ignores siblings of child nodes and “pushes forward”. This can be very good when the solution path is long. However, it can get lost deep in the graph, and it can also find very long paths when shorter paths may exist. It works well when there are many branches.

graph showing depth-first state space search
Figure 3: Depth-first search.

Using our above examples, both the ancestor searches, the theorem prover, and the expert system for identifying plants are good examples where depth-first searches will be appropriate.

Breadth-first

A breadth-first search travels level by level in a graph. Because it examines all children of a parent as it visits them, it is gauranteed to find the shortest path.

These searches are best with the solution is simple or known. However, it starts to perform poorly with a high number of branching, and long solution paths.

graph showing breadth-first state space search.
Figure 4: Breadth-first search.

Our automobile problem checker, and our sonar reader from the above are good examples where breath-first search is best.

State Space Search of the Farmer, Wolf, Cabbage, Goat Problem

Finally I’ll present a real solution to a common problem used in graph search. A farmer is traveling with his wolf, cabbage, and goat. He gets to a river that he needs to cross, but has come to a problem. The boat only carries two things (one being the farmer). If the wolf is left alone with the goat then the wolf will eat the goat. If the goat is left alone with the cabbage, then the goat will eat the cabbage.

The solution involves bringing back “something” on a return trip, however I intend just to show the solution(s), in our state graph.

graph representation of Farmer, Wolf, Goat, Cabbage problem.
Figure 5: Graph representation of Farmer, Wolf, Goat, Cabbage problem.

In this problem, with a breadth-first search we would go level by level and both paths from A to J would be discovered. If one of these paths was shorter than the other, we would find that path and, therefore find an optimal solution.  Because this path has a known solution, few branches, and a short solution path, a breadth-first is a reasonable approach to this problem. If each state has an average of B children, Bn states will be on each level n.

However, a depth-first search would end up being a more efficient solution in this case. As both solutions require 7 edges, finding only one solution is necessary in this case. The longer the solution path becomes, the more a depth-first solution is appropriate. However this approach can result in getting lost in deep paths, and won’t ensure the shortest path. It would be useful if the graph has many branches, with the space used being linear with the length of the path. If there are B children, then B x n states are seen to go n deep.

This concludes my discussion on graph theory and state space search. Next on the docket is heuristics and how to make our search algorithms even more efficient! If you’re curious about how I made the graphs, check out this link!

Tags: , , , ,
Posted in artificial intelligence | No Comments »

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!

Tags: , ,
Posted in artificial intelligence | No Comments »