《基于商空间的问题求解：粒度计算的理论基础》针对人类问题求解的特点建立一个基于商空间的数学模型，这个模型也是分层多粒度计算的理论基础。该理论能有效地解析目前已有的多粒度分析方法，如小波分析、分形几何和模糊集理论等；不仅适用于以问题求解为代表的人类深思熟虑的行为，同时也适用于人类的感知，如视觉信息处理等。
《基于商空间的问题求解：粒度计算的理论基础》共分7章和2个附录。第1章讲述问题的描述方法，关键是不同粒度世界的描述。第2章讲述分层与多粒度计算，重点是其数学模型，多粒度计算与计算复杂性、模糊分析的关系，以及它的应用。第3章多粒度计算中信息合成的数学模型，并由此导出合成的原则和方法。第4章多粒度世界中的推理，包括推理模型，不确定性与粒度的关系，推理网络、定性推理与模糊推理等。第5章自动空间规划，包括装配序列的自动产生，运动规划中的几何与拓扑方法，降维法及其应用。第6章介绍统计启发式搜索方法，分析它的理论、计算复杂性、算法的实现，这种算法的特点及其与多粒度计算的关系。第7章商空间问题求解理论的推广，包括将理论推广到非等价关系，该理论与小波分析与分形几何的关系，以及在系统分析中的应用。最后，在附录中介绍若干与本书内容关系密切的数学内容，主要是统计推断与点集拓扑的某些概念和结论，供不熟悉这部分数学内容的读者阅读时参考。
《基于商空间的问题求解：粒度计算的理论基础》是从事计算机、人工智能、模式识别以及粒计算等领域的科学工作者的有益参考书。
Preface
The term problem solving is used in many disciplines, sometimes with different perspectives. As one of the important topics in arti.cial 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 .nd 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 suf.ciently. 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 in.ltrate into AI when it becomes mature gradually. 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 ef.ciency and performance of AI algorithms have been improved signi.cantly. There are two main trends in AI research recently. One is attaching importance to the usage of modern scienti.c 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. .elds. 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. Brie.y, 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 .elds 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 new theory can cover and solve problems in more domains of AI such as learning 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 .elds 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 .elds 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 de.ned 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.
Contents
Preface .................................................... vii
Chapter1 ProblemRepresentations....................................1
1.1. ProblemSolving .............................................1
1.1.1. ExpertConsultingSystems ...................................2
1.1.2. TheoremProving ..........................................2
1.1.3. AutomaticProgramming.....................................2
1.1.4. GraphicalRepresentation.....................................3
1.1.5. AND/ORGraphicalRepresentation.............................3
1.2. World Representations at Different Granularities . .....................5
1.2.1. TheModelofDifferentGrain-SizeWorlds........................5
1.2.2. TheDe.nitionofQuotientSpace...............................7
1.3. TheAcquisitionofDifferentGrain-SizeWorlds ......................8
1.3.1. TheGranulationofDomain...................................8
1.3.2. TheGranulationbyAttributes.................................9
1.3.3. GranulationbyStructures ...................................11
1.4. TheRelationAmongDifferentGrainSizeWorlds....................13
1.4.1. TheStructureofMulti-GranularWorlds.........................13
1.4.2. The Structural Completeness of Multi-Granular Worlds . . .... .... ...15
1.5. Property-PreservingAbility ....................................21
1.5.1. Falsity-PreservingPrinciple..................................21
1.5.2. QuotientStructure.........................................32
1.6. SelectionandAdjustmentofGrain-Sizes ..........................32
1.6.1. MergenceMethods........................................33
Example1.15 .................................................34
1.6.2. DecompositionMethods ....................................34
1.6.3. The Existence and Uniqueness of Quotient Semi-Order.... .... .... .... .. .... ...41
1.6.4. The Geometrical Interpretation of Mergence andDecompositionMethods ...................42
1.7. Conclusions................................................43
Chapter2 HierarchyandMulti-GranularComputing.......................45
2.1. TheHierarchicalModel.......................................45
2.2. TheEstimationofComputationalComplexity.......................48
2.2.1. TheAssumptions .........................................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 [f]UnderUnstructuredDomains ....................65
2.3.3. Constructing [f]UnderStructuredDomains ......................67
2.3.4. Conclusions .............................................77
2.4. FuzzyEquivalenceRelationandHierarchy.........................77
2.4.1. The Properties of Fuzzy Equivalence Relations. .... .... .... ... ....77
2.4.2. TheStructureofFuzzyQuotientSpaces.........................84
2.4.3. ClusterandHierarchicalStructure.............................86
2.4.4. Conclusions .............................................88
2.5. TheApplicationsofQuotientSpaceTheory ........................88
2.5.1. Introduction .............................................88
2.5.2. TheStructuralDe.nitionofFuzzySets.........................90
2.5.3. The Robustness of the Structural De.nition 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. TheSynthesisofDomains....................................108
3.4. TheSynthesisofTopologicStructures ...........................109
3.5. TheSynthesisofSemi-OrderStructures..........................110
3.5.1. The Graphical Constructing Method of Quotient Semi-Order . . . . . . . . 110
3.5.2. TheSynthesisofSemi-OrderStructures........................112
3.6. TheSynthesisofAttributeFunctions ............................117
3.6.1. The Synthetic Principle of Attribute Functions . .... .... .... ... ... 117
3.6.2. Examples..............................................120
3.6.3. Conclusions ............................................126
Chapter4 ReasoninginMulti-GranularWorlds..........................129
4.1. ReasoningModels..........................................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. ExperimentalResults......................................146
4.4. ReasoningNetworks(2)......................................147
4.4.1. Modeling ..............................................151
4.4.2. TheProjectionofAND/ORRelations .........................152
4.4.3. TheSynthesisofAND/ORRelations..........................155
4.4.4. Conclusion.............................................160
4.5. OperationsandQuotientStructures..............................160
4.5.1. TheExistenceofQuotientOperations .........................162
4.5.2. TheConstructionofQuotientOperations.......................164
4.5.3. TheApproximationofQuotientOperations .....................172
4.5.4. ConstraintsandQuotientConstraints..........................176
4.6. QualitativeReasoning .......................................181
4.6.1. QualitativeReasoningModels...............................182
4.6.2. Examples..............................................182
4.6.3. TheProcedureofQualitativeReasoning........................186
4.7. Fuzzy Reasoning Based on Quotient Space Structures . . .............. 187
4.7.1. FuzzySetBasedonQuotientSpaceModel......................187
4.7.2. Fuzzi.edQuotientSpaceTheory.............................189
4.7.3. The Transformation of Three Different Granular ComputingMethods ...................190
4.7.4. The Transformation of Probabilistic Reasoning Models. . . .... .... .. 191
4.7.5. Conclusions ............................................191
Chapter5 AutomaticSpatialPlanning................................193
5.1. AutomaticGenerationofAssemblySequences.....................194
5.1.1. Introduction ............................................194
5.1.2. Algorithms.............................................195
5.1.3. Examples..............................................199
5.1.4. ComputationalComplexity .................................202
5.1.5. Conclusions ............................................204
5.2. TheGeometricalMethodsofMotionPlanning .....................205
5.2.1. Con.gurationSpaceRepresentation...........................205
5.2.2. FindingCollision-FreePaths................................206
5.3. TheTopologicalModelofMotionPlanning .......................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. DimensionReductionMethod .................................216
5.4.1. BasicPrinciple..........................................216
5.4.2. CharacteristicNetwork ....................................221
5.5. Applications ..............................................230
5.5.1. The Collision-Free Paths Planning for a Planar Rod . .... .... ... ... 231
5.5.2. MotionPlanningforaMulti-JointArm ........................237
5.5.3. The Applications of Multi-Granular Computing .... .... .... ... ... 242
5.5.4. The Estimation of the Computational Complexity. . . .... .... ... ...246
Chapter6 StatisticalHeuristicSearch................................249
6.1. StatisticalHeuristicSearch....................................251
6.1.1. HeuristicSearchMethods ..................................251
6.1.2. StatisticalInference.......................................254
6.1.3. StatisticalHeuristicSearch .................................256
6.2. TheComputationalComplexity ................................259
6.2.1. SPA Algorithms .........................................259
6.2.2. SAA Algorithms .........................................262
6.2.3. Different Kinds of SA ... .... .... .... .... .... .... .... ... ...264
6.2.4. TheSuccessiveAlgorithms.................................266
6.3. The Discussion of Statistical Heuristic Search. . ....................267
6.3.1. Statistical Heuristic Search and Quotient Space Theory. . . .... ... ... 267
6.3.2. HypothesisI............................................268
6.3.3. TheExtractionofGlobalStatistics............................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. ComparisontoOtherWeightedTechniques .....................283
6.4.3. ComparisontoOtherMethods...............................292
6.5. SA inGraphSearch.......................... ...............294
6.5.1. GraphSearch ...........................................294
6.5.2. AND/ORGraphSearch....................................295
6.6. Statistical Inference and Hierarchical Structure . .................... 296
Chapter7 TheExpansionofQuotientSpaceTheory.......................299
7.1. QuotientSpaceTheoryinSystemAnalysis........................299
7.1.1. Problems ..............................................300
7.1.2. QuotientSpaceApproximationModels ........................300
7.2. Quotient Space Approximation and Second-Generation Wavelets........303
7.2.1. Second-GenerationWaveletsAnalysis.........................303
7.2.2. QuotientSpaceApproximation ..............................305
7.2.3. The Relation between Quotient Space Approximation andWaveletAnalysis ...............309
7.3. Fractal Geometry and Quotient Space Analysis. . ...................311
7.3.1. Introduction ............................................311
7.3.2. IteratedFunctionSystems..................................311
7.3.3. QuotientFractals.........................................312
7.3.4. Conclusions ............................................315
7.4. TheExpansionofQuotientSpaceTheory.........................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 e 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
新书资讯