Problem Solving
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.
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.
Theorem Proving
The aim of theorem proving is to draw a potential mathematical theorem from a set of given axioms and previously proven theorems by computers. It employs the same rule-based deduction principle as in most expert systems.
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.
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.
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...