Zhang Quotient Space Based Problem Solving

A Theoretical Foundation of Granular Computing
1. Auflage 2014
ISBN: 978-0-12-410443-3
Verlag: Elsevier Science & Techn.
Format: EPUB
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 396 Seiten

Quotient Space Based Problem Solving provides an in-depth treatment of hierarchical problem solving, computational complexity, and the principles and applications of multi-granular computing, including inference, information fusing, planning, and heuristic search. - Explains the theory of hierarchical problem solving, its computational complexity, and discusses the principle and applications of multi-granular computing - Describes a human-like, theoretical framework using quotient space theory, that will be of interest to researchers in artificial intelligence - Provides many applications and examples in the engineering and computer science area - Includes complete coverage of planning, heuristic search and coverage of strictly mathematical models

Professor Ling Zhang is currently with the Department of Computer Science at Anhui University in Hefei, China. His main interests are artificial intelligence, machine learning, neural networks, genetic algorithms and computational intelligence.

Autoren/Hrsg.

Zhang, Ling

Zhang, Bo

Inhaltsverzeichnis

1;Front Cover;1
2;Quotient Space Based Problem Solving: A Theoretical Foundation of Granular Computing;4
3;Copyright;5
4;Contents;6
5;Preface;12
6;Chapter 1 - Problem Representations;16
6.1;1.1 Problem Solving;16
6.2;1.2 World Representations at Different Granularities;20
6.3;1.3 The Acquisition of Different Grain-Size Worlds;23
6.4;1.4 The Relation Among Different Grain Size Worlds;28
6.5;1.5 Property-Preserving Ability;36
6.6;1.6 Selection and Adjustment of Grain-Sizes;47
6.7;Example 1.15;49
6.8;1.7 Conclusions;58
7;Chapter 2 - Hierarchy and Multi-Granular Computing;60
7.1;2.1 The Hierarchical Model;60
7.2;2.2 The Estimation of Computational Complexity;63
7.3;2.3 The Extraction of Information on Coarsely Granular Levels;77
7.4;2.4 Fuzzy Equivalence Relation and Hierarchy;92
7.5;2.5 The Applications of Quotient Space Theory;103
7.6;2.6 Conclusions;117
8;Chapter 3 - Information Synthesis in Multi-Granular Computing;120
8.1;3.1 Introduction;120
8.2;3.2 The Mathematical Model of Information Synthesis;121
8.3;3.3 The Synthesis of Domains;123
8.4;3.4 The Synthesis of Topologic Structures;124
8.5;3.5 The Synthesis of Semi-Order Structures;125
8.6;3.6 The Synthesis of Attribute Functions;132
9;Chapter 4 - Reasoning in Multi-Granular Worlds;144
9.1;4.1 Reasoning Models;144
9.2;4.2 The Relation Between Uncertainty and Granularity;148
9.3;4.3 Reasoning (Inference) Networks (1);150
9.4;4.4 Reasoning Networks (2);162
9.5;4.5 Operations and Quotient Structures;175
9.6;4.6 Qualitative Reasoning;196
9.7;4.7 Fuzzy Reasoning Based on Quotient Space Structures;202
10;Chapter 5 - Automatic Spatial Planning;208
10.1;5.1 Automatic Generation of Assembly Sequences;209
10.2;5.2 The Geometrical Methods of Motion Planning;220
10.3;5.3 The Topological Model of Motion Planning;222
10.4;5.4 Dimension Reduction Method;231
10.5;5.5 Applications;245
11;Chapter 6 - Statistical Heuristic Search;264
11.1;6.1 Statistical Heuristic Search;266
11.2;6.2 The Computational Complexity;274
11.3;6.3 The Discussion of Statistical Heuristic Search;282
11.4;6.4 The Comparison between Statistical Heuristic Search and A* Algorithm;295
11.5;6.5 SA in Graph Search;309
11.6;6.6 Statistical Inference and Hierarchical Structure;311
12;Chapter 7 - The Expansion of Quotient Space Theory;314
12.1;7.1 Quotient Space Theory in System Analysis;314
12.2;7.2 Quotient Space Approximation and Second-Generation Wavelets;318
12.3;7.3 Fractal Geometry and Quotient Space Analysis;326
12.4;7.4 The Expansion of Quotient Space Theory;330
12.5;7.5 Conclusions;346
13;Addenda A - Some Concepts and Properties of Point Set Topology;348
13.1;A.1 Relation and Mapping;348
13.2;A.2 Topology Space;350
13.3;A.3 Separability Axiom;357
13.4;A.4 Countability Axiom;359
13.5;A.5 Compactness;361
13.6;A.6 Connectedness;364
13.7;A.7 Order-Relation, Galois Connected and Closure Space;368
14;Addenda B - Some Concepts and Properties of Integral and Statistical Inference;378
14.1;B.1 Some Properties of Integral;378
14.2;B.2 Central Limit Theorem;382
14.3;B.3 Statistical Inference;384
15;References;390
16;Index;396

Leseproben

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