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,
Robert Frost, “The Road Not Taken”
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…,,
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:
- Most of the data is given in the statement of the problem. This is usual when the problem involves high level interpretations.
- If there are many potential goals, but only a few ways to use the data.
- 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.
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.
- 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.
- 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.
- 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.
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.
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.
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.
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!
