The term problem solving was used in many disciplines, sometimes with different perspectives (
Newell and Simon, 1972;
Bhaskar and Simon, 1977). As one of the main topics in artificial intelligence (AI), it is a computerized process of human problem-solving behaviors. It has been investigated by many researchers. Some important results have been provided (
Kowalski, 1979;
Shapiro, 1979;
Nilson, 1980). From an AI point of view, the aim of the problem solving is to develop theory and technique which enable the computers
to find, in an efficient way, solutions to the problem provided that the problem has been described to computers in a suitable form (
Zhang and Zhang, 1992; 2004).
Problem-solving methods and techniques have been applied in several different areas. To motivate our subsequent discussions, we next describe some of these applications.
1.1.1. Expert Consulting Systems
Expert consulting systems have been used in many different areas to provide human users with expert advice. These systems can diagnose diseases, analyze complex experimental data and arrange production schedule, etc.
In many expert consulting systems, expert knowledge is represented by a set of rules. The conclusion can be deduced from initial data by successively using these rules.
1.1.3. Automatic Programming
Automatic programming, automatic scheduling, decision making, robotic action planning and the like can be regarded as the following general task. Given a goal and a set of constraints, find a sequence of operators (or actions) to achieve the goal satisfying all given constraints.
All the problems above can be regarded as intelligent problem-solving tasks. In order to enable computers to have the ability of finding the solution of these problems automatically, AI researchers made every effort to find a suitable formal description of problem-solving process. It is one of the central topics in the study of problem solving.
In the early stage of AI, symbolists play a dominant role. They believe that all human cognitive behaviors, including problem solving, can be modeled by symbols and symbolic reasoning. The most general approach to tackle problem solving is generation and test. Applying an action to an initial state, a new state is generated. Whether the state is the goal state is tested; if it is not, repeat the procedure, otherwise stop and the goal is reached. This principle imitates human trial-and-error behaviors in problem solving sufficiently. The principle has widely been used to build AI systems. The problem-solving process is generally represented by a graphical (tree) search or an AND/OR graphical (tree) search.
1.1.4. Graphical Representation
A graphically causal model (
Pearl, 2000) is an abstract model that describes the causal mechanisms of a system. So some problem-solving processes can be regarded as inference over the graphically causal model. For example, automatic reasoning, theorem proving and the like can be considered as searching a goal node in the model. And robotic action planning, automatic programming, etc., can be formalized as searching a path in the model; and the path being found is the solution of the problem and called a solution path.
Let us take the robot's indoor path-planning problem as an example. Assuming that the initial position of the robot is in room
X and the goal position is in room
Y, the aim is to find a path from room
X to room
Y.
Fig. 1.1
shows the graphical representation of the problem-solving process. The nodes shown in
Fig. 1.1 represent subsets of potential solutions. For example, the node denoted by
A represents all potential paths from room
X to room
Y by going through room
A; while the node
C all potential paths by going through rooms
A and
C; and so on. The arcs linking two nodes are planning rules for finding a path from one room to another. The path that links
X and
Y is the solution path.
1.1.5. AND/OR Graphical Representation
Some problem-solving processes may be represented more conveniently by the so-called AND/OR graph. In this representation, a complex original problem is divided into a conjunction of several subproblems. These subproblems are simpler than the original one and can generally be solved in isolation. The subproblems can be further decomposed into still more simple sub-subproblems until they can be easily solved.
In fact, the problem-solving processes above are regarded as an AND/OR graph search. The graph is similar to the general graph except that there are two kinds of links. One, called OR link, is the same as that in the general graphs. The other, called AND link, is special to the AND/OR graphical representation.
All nodes in an AND/OR graph represent subproblems to be solved or subgoals to be reached. The situation is the same as in the general graph. But in AND links, although the individual subproblems are represented by separate nodes, they all must be solved before
their parent problem is considered solved. The curved arcs between links are drawn to show this fact (see
Fig. 1.2
).
Figure 1.1
The Graphical Representation of a Problem
Figure 1.2
AND/OR Graphical Representation of a Problem
A solution to the problem represented by a general graph is a terminal node of the graph. However, the complete solution in an AND/OR graphical representation is represented by an AND/OR subgraph, called a solution graph (see
Chapter 6 for more details).
As an example shown in
Fig. 1.2, the initial problem is to design an electronic instrument. The task can be divided into several subtasks called component designs, such as power supply, amplifier and display component design. Furthermore, each subtask can be divided into several sub-subtasks called part designs. For example, power supply design consists of transformer, rectifier and filter designs, etc.
Although a wide range of problems can be described by the above representations, there is still a big gap between the formal description and human behavior in problem solving so that generally the computer solver cannot find the solution in an efficient way as a human does.
One of the basic characteristics in human problem solving is the ability to conceptualize the world at different granularities and translate from one abstraction level to the others easily, i.e. deal with them hierarchically (
Hobbs, 1985). It is the hierarchy that underlies the human power in problem solving. Suppose that a manager sitting in his office drafted a production plan for his factory. In his early mental planning stage, only a coarse-grained model of the factory is needed. The factory in his mind may be encoded as a ‘block diagram’ consisting of several workshops while ignoring all details within the workshops. When a plan has briefly been sketched out, he must enter a more fine-grained model to consider the details within the workshops, i.e., he needs a fine coding of the factory. In some planning stage, if global information is needed, he will immediately switch to the coarse-grained representation again. This ability is one of the human intelligence.
For a computer, things are quite different. Despite all data about a factory, such as machines, workers, tools, buildings, etc., having been stored in its memory, it is
still unknown how to generate different representations from these data, how to choose a properly representational form based on different computational requirements, how to transform a coarse-grained model into a fine one or vice versa. Neither general graphical nor AND/OR graphical representation can tackle such problems as they lack a mechanism for representing the world at different granularities. Therefore, we have to provide a precise formalization of the notion of problem representations at different granularities in order for computers to imitate the above human abilities.
