The term problem solving is used in many disciplines, sometimes with different perspectives. As one of the important topics in artificial intelligence (AI) research, it is a computerized process of human problem-solving behaviors. So the aim of problem solving is to develop techniques that program computers to find solutions to problems that can properly be described.
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 symbolic representation and reasoning and do not advocate the use of strict mathematical models. The most general approach to tackle problem-solving processes 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 such as planning, scheduling,diagnosis, etc. and to solve a certain kind of real problems. Therefore, the heuristic and scratch method is misunderstood as a unique one in AI for many people. We believe that more and more modern sciences such as mathematics, economics, operational research, game theory and cybernetics would infiltrate into AI when it becomes maturegradually. Over the years, we devoted ourselves to introducing mathematics to AI. Since 1979 we have introduced statistical inference methods to heuristic search, topological dimension reduction approach to motion planning, and relational matrix to temporal planning. Due to the introduction of these mathematical tools, the efficiency and performance of AI algorithms have been improved significantly. There are two main trends in AI research recently. One is attaching importance to the usage of modern scientific methods, especially mathematics; the other is paying attention to real-world problem solving. Fortunately, our efforts above are consistent with these new trends.
Based on these works, we explored further the theoretical framework of problem solving. Inspired by the following basic characteristics in human problem solving, that is, the ability to conceptualize the world at different granularities, translate from one abstraction level to the others easily and deal with them hierarchically, we establish an algebraically quotient space model to represent the multi-granular structures of the world so that it’s easy for computers to deal with them hierarchically. Certainly, this model can simulate the above characteristics of human problem-solving behaviors in a certain extent. We expect more human characteristics to merge into the model further. The system is used to describe the hierarchical and multi-granular structure of objects being observed and to solve the problems that are faced in inference, planning, search, etc. fields. Regarding the relation between computers and human problem solvers, our standpoint is that the computer problem solver should learn some things from human beings but due to the difference between their physical structures they are distinguishing.
Already 20 years has passed since the English version of the book published in 1992. Meanwhile, we found that the three important applied mathematical methods, i.e., fuzzy mathematics, fractal geometry and wavelet analysis, have a close connection with quotient space based analysis. Briefly, the representational method of fuzziness by membership functions in fuzzy mathematics is equivalent to that based on hierarchical coordinates in the quotient space model; fractal geometry rooted in the quotient approximation of spatial images; and wavelet analysis is the outcome of quotient analysis of attribute functions. The quotient space theory of problem solving has made new progress and been applied to several fields such as remote sensing images analysis, cluster analysis, etc. In addition, fuzzy set and rough set theories have been applied to real problems for managing uncertainty successively. The computational model of uncertainty has attracted wide interest. Therefore, we expanded the quotient space theory to non-equivalent partition and fuzzy equivalence relation. We explored the relation between quotient space theory and fuzzy set (rough set) theory. The quotient space theory is also extended to handling uncertain problems. Based on these works, we further proposed a new granular computing theory based on the quotient space based problem solving. The newtheory cancover and solve problemsin more domainsof AI such aslearning problems so as to become a more general and universal theoretical framework. The above new progress has been included in the second version of the book.
The quotient space based problem solving that we have discussed mainly deals with human deliberative behaviors. Recently, in perception, e.g., visual information processing, the multi-level analysis method is also adopted. So the quotient space model can be applied to these fields as well. But they will not be involved in the book.
There are seven chapters and two addenda in the book. In Chapter 1, we present a quotient space model to describe the world with different grain-sizes. This is the theoretical foundation throughout the book and is the key to problem solving and granular computing. The principle of "hierarchy" as an important concept has been used in many fields such as control, communication theory. In Chapter 2, we discuss the principle starting with the features of the human problem-solving process and pay attention to its mathematical modeling and relation to computational complexity. In Chapter 3, we discuss synthetic methods that involve the inverse of top-down hierarchical analysis, that is, how to combine the information from different viewpoints and different sources. Since synthetic method is one of main measures for human problem solving we present a mathematical model and induce the corresponding synthetic rules and methods from the model. Although there have been several inference models in AI, the model presented in Chapter 4 is a new network-based one. The new model can carry out inference at different abstraction levels and integrates deterministic, non-deterministic and qualitative inferences into one framework. And the synthetic and propagation rules of network inference are also introduced. In Chapter 5, the application of quotient space theory to spatial planning is presented. It includes robot assembly sequences and motion planning.For example, in motion planning instead of widely adopted geometry-based planning we pay attention to a topology-based one that we propose, including its principles and applications. The statistically heuristic search algorithms are presented in Chapter 6, including theory, computational complexity, the features and realization of the algorithms, and their relation to hierarchical problem-solving principles and multi-granular computing. In Chapter 7, the original equivalence relation based theory is expanded to including tolerant relations and relations defined by closure operations. Also, a more general quotient space approximation principle is presented. Finally, the basic concepts and theorems of mathematics related to the book are introduced in addenda, including point set topology and statistical inference.
The authors gratefully acknowledge support by National Key Basic Research Program (973 Program) of China under Grant Nos. 2012CB316301, 2013CB329403, National Natural Science Foundation under Grant No. 60475017. Many of the original results in the book were found by the authors while working on these projects.

Preface xi

Chapter 1 Problem Representations 1

1.1. Problem Solving 1

      1.1.1. Expert Consulting Systems 2

      1.1.2. Theorem Proving 2

      1.1.3. Automatic Programming 2

      1.1.4. Graphical Representation 3

      1.1.5. AND/OR Graphical Representation 3

1.2. World Representations at Different Granularities 5

      1.2.1. The Model of Different Grain-Size Worlds 5

      1.2.2. The Definition of Quotient Space 7

1.3. The Acquisition of Different Grain-Size Worlds 8

      1.3.1. The Granulation of Domain 8

      1.3.2. The Granulation by Attributes 9

      1.3.3. Granulation by Structures 11

1.4. The Relation Among Different Grain Size Worlds 13

      1.4.1. The Structure of Multi-Granular Worlds 13

      1.4.2. The Structural Completeness of Multi-Granular Worlds 15

1.5. Property-Preserving Ability 21

      1.5.1. Falsity-Preserving Principle 21

      1.5.2. Quotient Structure 32

1.6. Selection and Adjustment of Grain-Sizes 32

      1.6.1. Mergence Methods 33

      Example 1.15 34

      1.6.2. Decomposition Methods 34

      1.6.3. The Existence and Uniqueness of Quotient Semi-Order 41

      1.6.4. The Geometrical Interpretation of Merge nce and Decomposition Methods 42

1.7. Conclusions 43

Chapter 2 Hierarchy and Multi-Granular Computing 45

2.1. The Hierarchical Model 45

2.2. The Estimation of Computational Complexity 48

      2.2.1. The Assumptions 48

      2.2.2. The Estimation of the Complexity Under Deterministic Models 49

      2.2.3. The Estimation of the Complexity Under Probabilistic Models 54

2.3. The Extraction of Information on Coarsely Granular Levels 62

      2.3.1. Examples 64

      2.3.2. Constructing [ƒ] Under Unstructured Domains 65

      2.3.3. Constructing [ƒ] Under Structured Domains 67

      2.3.4. Conclusions 77

2.4. Fuzzy Equivalence Relation and Hierarchy 77

      2.4.1. The Properties of Fuzzy Equivalence Relations 77

      2.4.2. The Structure of Fuzzy Quotient Spaces 84

      2.4.3. Cluster and Hierarchical Structure 86

      2.4.4. Conclusions 88

2.5. The Applications of Quotient Space Theory 88

      2.5.1. Introduction 88

      2.5.2. The Structural Definition of Fuzzy Sets 90

      2.5.3. The Robustness of the Structural Definition of Fuzzy Sets 95

      2.5.4. Conclusions 102

2.6. Conclusions 102

Chapter 3 Information Synthesis in Multi-Granular Computing 105

3.1. Introduction 105

3.2. The Mathematical Model of Information Synthesis 106

3.3. The Synthesis of Domains 108

3.4. The Synthesis of Topo logic Structures 109

3.5. The Synthesis of Semi-Order Structures 110

      3.5.1. The Graphical Constructing Method of Quotient Semi-Order 110

      3.5.2. The Synthesis of Semi-Order Structures 112

3.6. The Synthesis of Attribute Functions 117

      3.6.1. The Synthetic Principle of Attribute Functions 117

      3.6.2. Examples 120

      3.6.3. Conclusions 126

Chapter 4 Reasoning in Multi-Granular Worlds 129

4.1. Reasoning Models 129

4.2. The Relation Between Uncertainty and Granularity 133

4.3. Reasoning (Inference) Networks (1) 135

      4.3.1. Projection 138

      4.3.2. Synthesis 140

      4.3.3. Experimental Results 146

4.4. Reasoning Networks (2) 147

      4.4.1. Modeling 151

      4.4.2. The Projection of AND/OR Relations 152

      4.4.3. The Synthesis of AND/OR Relations 155

      4.4.4. Conclusion 160

4.5. Operations and Quotient Structures 160

      4.5.1. The Existence of Quotient Operations 162

      4.5.2. The Construction of Quotient Operations 164

      4.5.3. The Approximation of Quotient Operations 172

      4.5.4. Constraints and Quotient Constraints 176

4.6. Qualitative Reasoning 181

      4.6.1. Qualitative Reasoning Models 182

      4.6.2. Examples 182

      4.6.3. The Procedure of Qualitative Reasoning 186

4.7. Fuzzy Reasoning Based on Quotient Space Structures 187

      4.7.1. Fuzzy Set Based on Quotient Space Model 187

      4.7.2. Fuzzified Quotient Space Theory 189

      4.7.3. The Transformation of Three Different Granular Computing Methods 190

      4.7.4. The Transformation of Probabilistic Reasoning Models 191

      4.7.5. Conclusions 191

Chapter 5 Automatic Spatial Planning 193

5.1. Automatic Generation of Assembly Sequences 194

      5.1.1. Introduction 194

      5.1.2. Algorithms 195

      5.1.3. Examples 199

      5.1.4. Computational Complexity 202

      5.1.5. Conclusions 204

5.2. The Geometrical Methods of Motion Planning 205

      5.2.1. Configuration Space Representation 205

      5.2.2. Finding Collision-Free Paths 206

5.3. The Topological Model of Motion Planning 207

      5.3.1. The Mathematical Model of Topology-Based Problem Solving 208

      5.3.2. The Topologic Model of Collision-Free Paths Planning 210

5.4. Dimension Reduction Method

      5.4.1. Basic Principle

      5.4.2. Characteristic Network

5.5. Applications

      5.5.1. The Collision-Free Paths Planning for a Planar Rod

      5.5.2. Motion Planning for a Multi-Joint Arm

      5.5.3. The Applications of Multi-Granular Computing

      5.5.4. The Estimation of the Computational Complexity

Chapter 6 Statistical Heuristic Search

6.1. Statistical Heuristic Search

      6.1.1. Heuristic Search Methods

      6.1.2. Statistical Inference

      6.1.3. Statistical Heuristic Search

6.2. The Computational Complexity

      6.2.1. SPA Algorithms

      6.2.2. SAA Algorithms

      6.2.3. Different Kinds of SA

      6.2.4. The Successive Algorithms 266

6.3. The Discussion of Statistical Heuristic Search 267

      6.3.1. Statistical Heuristic Search and Quotient Space Theory 267

      6.3.2. Hypothesis I 268

      6.3.3. The Extraction of Global Statistics 271

      6.3.4. SA Algorithms 279

6.4. The Comparison between Statistical Heuristic Search and A* Algorithm 280

      6.4.1. Comparison to A* 280

      6.4.2. Comparison to Other Weighted Techniques 283

      6.4.3. Comparison to Other Methods 292

6.5. SA in Graph Search 294

      6.5.1. Graph Search 294

      6.5.2. AND/ORGraphSearch 295

6.6. Statistical Inference and Hierarchical Structure 296

Chapter 7 The Expansion of Quotient Space Theory 299

7.1. Quotient Space Theory in System Analysis 299

      7.1.1. Problems 300

      7.1.2. Quotient Space Approximation Models 300

7.2. Quotient Space Approximation and Second-Generation Wavelets 303

      7.2.1. Second-Generation Wavelets Analysis 303

      7.2.2. Quotient Space Approximation 305

      7.2.3. The Relation between Quotient Space Approximation and Wavelet Analysis 309

7.3. Fractal Geometry and Quotient Space Analysis 311

      7.3.1. Introduction 311

      7.3.2. Iterated Function Systems 311

      7.3.3. Quotient Fractals 312

      7.3.4. Conclusions 315

7.4. The Expansion of Quotient Space Theory 315

      7.4.1. Introduction 315

      7.4.2. Closure Operation-Based Quotient Space Theory 315

      7.4.3. Non-Partition Model-Based Quotient Space Theory 320

      7.4.4. Granular Computing and Quotient Space Theory 324

      7.4.5. Protein Structure Prediction-An Application of Tolerance Relations 326

      7.4.6. Conclusions 331

7.5. Conclusions 331

Addenda A: Some Concepts and Properties of Point Set Topology 333

Addenda B: Some Concepts and Properties of Integral and Statistical Inference 363

References 375

Index 381

Professor Bo Zhang is currently with the Computer Science and Technology Department at Tsinghua University in Beijing, China, He is a Fellow of Chinese Academy of Sciences. His main research interests include artificial intelligence, robotics, intelligent control and pattern recognition. He has published over 150 papers and 3 monographs in these fields.

中科院文献情报中心