# Benjamin Kuipers

Benjamin Jack Kuipers (born April 7, 1949) is an American computer scientist and artificial intelligence researcher. He is best known for his work on computational models of cognitive maps, robot exploration and mapping methods, the qualitative simulation algorithm QSIM, and foundational learning methods.

## Family origins, education, and academic career

Benjamin Kuipers was born in Grand Rapids, Michigan, the oldest of five children of Jack and Lois Kuipers. The family lived in Ann Arbor, Michigan for several years and he graduated from Ann Arbor High School in 1966.

Kuipers graduated from Swarthmore College in 1970 with a B.A. with High Honors in Mathematics. He then did two years of alternate service as a conscientious objector to military service, working in the Psychology Department at Harvard University. He began his doctoral studies in pure mathematics at the Massachusetts Institute of Technology. He soon discovered the field of Artificial Intelligence, and spent most of his time at the MIT Artificial Intelligence Lab, where his advisor was Marvin Minsky. He received his PhD in Mathematics from MIT in 1977. He spent a post-doctoral year as a Research Associate at the MIT Division for Study and Research in Education, funded by a DARPA grant to support collaborative research with BBN psychologist Albert Stevens.

Kuipers was Assistant Professor of Mathematics at Tufts University from 1978 to 1984, spent the 1984-85 year at the MIT Laboratory for Computer Science, and joined the Computer Science Department at the University of Texas at Austin as Associate Professor (1985-92) and Professor (1992-2008). At Texas, he served as Computer Science Department Chair from 1997 to 2001. In January 2009, he moved to the University of Michigan, where he is a Professor of Computer Science and Engineering.

## Modeling the cognitive map in humans and robots

Kuipers' 1977 PhD thesis from MIT presented the TOUR Model --- the first comprehensive computational model of the human cognitive map [1,2]. The TOUR model was strongly inspired by Kevin Lynch's seminal book, The Image of the City [3], and by studies of the development of spatial knowledge in children [4,5]. All evidence suggests that the human cognitive map represents space quite differently from a printed map, which has a single global frame of reference. Unlike previous attempts to model spatial knowledge, the TOUR model included several distinct representations for large-scale space, such as procedures for following a route from one place to another, a topological map containing places connected by paths, and localized metrical maps with separate frames of reference.

This work helped inspire a community of researchers working on cognitive and applied aspects of representing large-scale space, particularly geographic space, including the series of Conferences on Spatial Information Theory (COSIT) that have been held since 1992. In recognition of this, Kuipers has been an Advisory Editor to the interdisciplinary journal, Spatial Cognition and Computation, since its creation.

In the late 1980s, Kuipers and his student Yung-Tai Byun tackled the problem of extending the ideas of the TOUR Model to apply to robots. Specifically, for a robot implementation, it was no longer possible to abstract away the issues of continuous sensory input, continuous motor output, and motion in a continuous world. Kuipers and Byun [6,7] developed the critical concept of "distinctive place" (or "distinctive state" when heading is included). A distinctive state is the stable fixed-point of a hill-climbing control law, to which the robot converges from any point in a local basin of attraction. The local basins of attraction are connected by distinctive edges, which are stable attractors of trajectory-following control laws. These attractors define the elements of the topological map, and ground them as discrete abstractions of continuous behaviors of control laws in the continuous environment.

The Spatial Semantic Hierarchy [8] describes this collection of representations for large-scale space, grounded in the properties of continuous control laws. It has been extended to the Hybrid Spatial Semantic Hierarchy [9,10] by using well-developed SLAM methods [11] to build local metrical maps, extracting the topological properties of local place neighborhoods to build the topological map [9], and then using the topological map as a skeleton for building a global metrical map [10]. The original paper [6] was honored in 2007 as one of the two most influential papers from the 1988 National Conference on Artificial Intelligence.

## Qualitative reasoning about physical systems

Starting in the late 1970s, Kuipers began to study another aspect of human commonsense knowledge: how people reason about the behavior of dynamic physical systems. Collaborating with Dr. Jerome P. Kassirer, a distinguished expert on kidney disease and medical decision-making, he used protocol analysis to study in detail verbatim transcripts of expert physicians reasoning about disorders of the kidney. Analysis of these transcripts [12] provided evidence that these experts reasoned using qualitative values (e.g. high, low, increasing, decreasing) of continuous variables (e.g. electrolyte concentration, blood pressure, fluid flow, etc.), linked by qualitative constraints (e.g. monotonic relationships, pressure differences, confluence of flows, etc.).

Building on these empirical constraints, and on concepts developed by Johan de Kleer for reasoning qualitatively about physical systems, Kuipers developed first the ENV system [13] and then the QSIM algorithm [14] for qualitative simulation.

The QSIM algorithm [14] established that qualitative simulation could be rigorously defined as an abstraction of the solution of ordinary differential equations. Specifically, QSIM takes as input a qualitative differential equation (QDE), which describes a family of ordinary differential equations (ODEs), along with the qualitative description of an initial state. QSIM produces as output a tree of qualitative states whose paths describe the possible behaviors of the system. Many extensions and applications of the QSIM algorithm are described in [15].

The QSIM Guaranteed Coverage Theorem [14,15] states that every solution to every ODE initial value problem consistent with the QDE and qualitative initial value description will be described by some path through the predicted tree of states. Since the tree of states can become large enough to be difficult to inspect by hand, a temporal logic model-checker can be used to query the tree of states with formulas in temporal logic [16].

The two seminal papers in this line of research [13,14] were honored for being two among the 25 most-cited papers in the first fifty volumes of the premier journal in the field, Artificial Intelligence [17].

## Learning from uninterpreted sensors and effectors

In virtually all work in artificial intelligence or robotics, the human researcher or programmer provides knowledge of the agent's sensors and effectors, and assumptions about the nature of the environment. Kuipers and his students have been investigating the problem of how a learning agent can begin with an uninterpreted sense vector and motor vector, and no knowledge of its environment, and construct a useful model of its interaction with its world [18].

In a recent essay [19], he describes the intellectual history of his work on spatial knowledge, from the cognitive map, to the Spatial Semantic Hierarchy, to foundational learning of high-level concepts of objects and actions based on low-level experience with sensor inputs and motor outputs.

## No military funding

Kuipers is also well known for his personal stance against accepting military funding for his research. As he explains in his essay, Why don't I take military funding?, during a DARPA-funded post-doctoral year (1977-78) he discovered that the primary interest in his early work on cognitive maps came from military agencies with the goal of building intelligent cruise missiles. He felt that he did not want his life's work to contribute to war.

He does not condemn individuals who accept, or agencies who provide, military funding. Rather, his position is a public testimony that it is possible for a computer scientist to have a successful research career without military funding.

## References

[1] B. J. Kuipers. 1977. Representing Knowledge of Large-Scale Space. Doctoral dissertation, Mathematics Department, Massachusetts Institute of Technology, Cambridge, Massachusetts, June 1977.

[2] B. J. Kuipers. 1978. Modeling spatial knowledge. Cognitive Science 2: 129-153, 1978.

[3] K. Lynch, The Image of the City. MIT Press, 1960. (ISBN: 0262620014)

[4] J. Piaget and B. Inhelder, The Child's Conception of Space. Norton, 1967. (ISBN: 0393004082)

[5] A. W. Siegel and S. H. White, 1975. The development of spatial representations of large-scale environments. In H. W. Reese (Ed.), Advances in Child Development and Behavior, vol. 10, Academic Press, 1975, pp. 9-55.

[6] B. J. Kuipers & Y.-T. Byun. 1988. A robust qualitative method for spatial learning in unknown environments. In Proceedings of the National Conference on Artificial Intelligence (AAAI-88). Los Altos, CA: Morgan Kaufman, 1988.

[7] B. J. Kuipers & Y.-T. Byun. 1991. A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations. Journal of Robotics and Autonomous Systems, 8: 47-63, 1991.

[8] B. Kuipers. 2000. The Spatial Semantic Hierarchy. Artificial Intelligence 119: 191-233.

[9] B. Kuipers, J. Modayil, P. Beeson, M. MacMahon, and F. Savelli. 2004. Local metrical and global topological maps in the hybrid Spatial Semantic Hierarchy. IEEE International Conference on Robotics and Automation (ICRA-04).

[10] J. Modayil, P. Beeson and B. Kuipers. 2004. Using the topological skeleton for scalable global metrical map-building. IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS-04).

[11] S. Thrun, W. Burgard, and D. Fox, Probabilistic Robotics, MIT Press, 2005. (ISBN: 0262201623)

[12] B. J. Kuipers and J. P. Kassirer. 1984. Causal reasoning in medicine: analysis of a protocol. Cognitive Science 8: 363-385, 1984.

[13] B. J. Kuipers. 1984. Commonsense reasoning about causality: deriving behavior from structure. Artificial Intelligence 24: 169-203, 1984.

[14] B. J. Kuipers. 1986. Qualitative simulation. Artificial Intelligence 29: 289-338, 1986.

[15] B. Kuipers, Qualitative Reasoning: Modeling and Simulation with Incomplete Knowledge. MIT Press, 1994. (ISBN 026211190X)

[16] B. Shults and B. Kuipers. 1997. Proving properties of continuous systems: qualitative simulation and temporal logic. Artificial Intelligence 92: 91-129, 1997.

[17] B. J. Kuipers. Reasoning with qualitative models. Artificial Intelligence 59: 125-132, 1993.
B. J. Kuipers. Qualitative simulation: then and now. Artificial Intelligence 59: 133-140, 1993.

[18] D. M. Pierce and B. Kuipers. 1997. Map learning with uninterpreted sensors and effectors. Artificial Intelligence 92: 169-229, 1997.

[19] B. Kuipers. 2008. An intellectual history of the Spatial Semantic Hierarchy. In M. Jefferies and A. (W.-K.) Yeap (Eds.), Robot and Cognitive Approaches to Spatial Mapping. To appear, Springer Verlag, 2008.