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