《基于商空間的問題求解：粒度計算的理論基礎》針對人類問題求解的特點建立一個基于商空間的數學模型，這個模型也是分層多粒度計算的理論基礎。該理論能有效地解析目前已有的多粒度分析方法，如小波分析、分形幾何和模糊集理論等；不僅適用于以問題求解為代表的人類深思熟慮的行為，同時也適用于人類的感知，如視覺信息處理等。
《基于商空間的問題求解：粒度計算的理論基礎》共分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
新書資訊