7 - Problem Decomposition

Summary

So far our approach to solving problems has been characterized by state space search. We are in a given state, and we have a desired or goal state. We have a set of moves available to us which allow us to navigate from one state to another. We search through the possible moves, and we employ a heuristic function to explore the space in an informed manner. In this chapter we study two different approaches to problem solving.

One, with emphasis on knowledge that we can acquire from domain experts. We look at mechanisms to harness and exploit such knowledge. In the last century in the 1980s, an approach to express knowledge in the form of if–then rules gained momentum, and many systems were developed under the umbrella of expert systems. Although only a few lived up to expert level expectations, the technology matured into an approach to allow human users to impart their knowledge into systems. The key to this approach was the Rete algorithm that allowed an inference engine to efficiently match rules with data.

The other looks at problem solving from a teleological perspective. That is, we look at a goal based approach which investigates what needs to be done to achieve a goal. In that sense, it is reasoning backwards from the goal. We look at how problems can be formulated as goal trees, and an algorithm AO* to solve them.

The search algorithms we have studied so far take a holistic view of a state representing the given situation. In practice, states are represented in some language in which the different constituents are described. The state description is essentially a set of statements. As the importance of knowledge for problem solving became evident, using rules to spot patterns in the description and proposing actions emerged as a problem solving strategy.

Pattern Directed Inference Systems

An approach to problem solving that was developed in the mid-1970s was called pattern directed inference systems (Waterman and Hayes-Roth, 1978). The basic idea is that patterns in a given state are associated with actions.