Chapter 1

Problem Representations

Abstract

This is the overview of the quotient space theory of problem solving that we proposed. Based on the theory, a problem is represented by a triplet, i.e. domain, attribute and structure. Compared to general graph representations, it offers a tool for depicting different grain-size worlds. We discuss the acquisition of different grain-size worlds, i.e., the construction of quotient spaces from the original one, including the granulation of domains, attributes and structures, especially, the construction of quotient topology and quotient semi-order structures from the original ones. Some key issues such as the relations and the property preserving, truth/falsity preserving, ability among different quotient spaces, and the choice of a proper grain-size world by selection and adjustment of grain-sizes are discussed. Just the property preserving ability among multi-granular worlds ensures the reduction of computational complexity in multi-granular computing.

The family of quotient spaces composes a complete semi-order lattice. We show that three different kinds of complete semi-order lattices we can have and they correspond to three different multi-granular worlds. The completeness of the lattices provides a theoretical foundation for the translation, decomposition, combination operations over the multi-granular worlds.

Keywords

attribute domain falsity preserving granularity problem solving quotient space semi-order lattice structure truth preserving

Chapter Outline

1.1 Problem Solving

1.1.1 Expert Consulting Systems

1.1.2 Theorem Proving

1.1.3 Automatic Programming

1.1.4 Graphical Representation

1.1.5 AND/OR Graphical Representation

1.2 World Representations at Different Granularities

1.2.1 The Model of Different Grain-Size Worlds

1.2.2 The Definition of Quotient Space

1.3 The Acquisition of Different Grain-Size Worlds

1.3.1 The Granulation of Domain

1.3.2 The Granulation by Attributes

1.3.3 Granulation by Structures

1.4 The Relation Among Different Grain Size Worlds

1.4.1 The Structure of Multi-Granular Worlds

1.4.2 The Structural Completeness of Multi-Granular Worlds

1.5 Property-Preserving Ability

1.5.1 Falsity-Preserving Principle

1.5.2 Quotient Structure

1.6 Selection and Adjustment of Grain-Sizes

1.6.1 Mergence Methods

Example 1.15

1.6.2 Decomposition Methods

1.6.3 The Existence and Uniqueness of Quotient Semi-Order

1.6.4 The Geometrical Interpretation of Mergence and Decomposition Methods

1.7 Conclusions

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...