2.1 Artificial Intelligence

Artificial Intelligence is the study of computational models of the mind. At Yale, we study a wide variety of topics, including robotics, vision, computational neuroscience, learning, and knowledge representation.

The term ``artificial intelligence'' is somewhat misleading, because the focus of research in the field is often on more mundane activities, such as simple visual perception, than the word ``intelligence'' would suggest. The field has learned over the years that the effortlessness of a skill such as vision is deceptive, that in fact the brain does a great deal of hard labor behind the scenes to allow us to see without conscious effort. It will take us years to duplicate the skills that nature evolved over eons.

AI uses many of the same techniques as other areas of Computer Science application, from numerical optimization to symbolic indexing. The key to solving any problem is always the algorithm and its analysis. The goal is always to characterize precisely a set of problems and demonstrate an algorithm that solves them with reasonable efficiency. But, at least at its current state of development, AI is of necessity more exploratory than other areas. We are often forced to define a problem at the same time that we try to solve it. It often happens that we don't know how to analyze the performance of an algorithm with existing tools, but we believe that its average-case performance is much better than its worst-case performance, and this belief must be backed up with experiments.

In general we think it is a mistake for AI research to focus on central mental function and ignore input and output. In the long run, machines will not be treated as intelligent unless they can perceive and manipulate the objects around them. Real perception and action impose stubborn constraints on thinking. Sophisticated robot planning is wasted if the robot crashes into the wall while trying to generate a predicate-calculus description of the world in front of it. So our planning research focuses on models of execution and replanning in realistic, changing worlds, and not so much on provably correct plans.

Here is a partial list of the projects we are now working on:

• Illumination cones: The appearance of a particular object depends on both the viewpoint from which it is observed and the light sources by which it is illuminated. If the appearance of two objects is never identical for any pose or lighting conditions, then -- in theory -- the objects can always be distinguished or recognized. The question arises: What is the set of images of an object under all lighting conditions and pose? We have proved that the set of n-pixel images of a convex object with a Lambertian reflectance function, illuminated by an arbitrary number of point light sources at infinity, forms a convex polyhedral cone in Rⁿ and that the dimension of this illumination cone equals the number of distinct surface normals. Furthermore, we can show that the cone for a particular object can be constructed from three properly chosen images; and that the set of n-pixel images of an object of any shape and with an arbitrary reflectance function, seen under all possible illumination conditions, still forms a convex cone in Rⁿ. These results immediately suggest certain approaches to object recognition. We've produced empirical results demonstrating the validity of the illumination-cone representation.

• Map learning for mobile robots: The fundamental problem for robot navigation is for a robot to be able to get back to places it has been before. To solve this question, you need to define what a place is. We are pursuing a model in which a place is a visually distinctive point, reachable from other places by fairly robust but not perfect operations. As the robot wanders around its world, it builds up a graph of places and the metrical relationships among them. It is able to correct errors in this graph by merging two places that are really the same, and splitting a place that really corresponds to two similar places.

• Agent communication: Agents are programs with a higher degree of autonomy and semantic transparency than traditional programs. A key goal of agent theory is to enable agents to form teams at run time. Teamwork may require Agent B to be able to make use of the outputs of Agent A. So we must have a syntactic and semantic description of the data A produces and the data B requires. Using these descriptions, we can generate a ``glue'' program that translates between the two representations. Finding this program can be expressed as the problem of solving an equation for an unknown function, which in turn can be expressed in terms of transformations on functional expressions. Which transformation to use can only be determined by searching, but there is reason to believe the search space is not too large.

• Mathematical neuroscience: Computational vision is at the heart of robotics and biomedicine, but is still quite primitive when compared with our own visual sense. We effortlessly demonstrate enormous flexibility and generality, which hides its staggering complexity: More than one-third of the primate brain processes visual information. Characterization the function of billions of neurons in algorithmic terms requires a combination of mathematical, algorithmic, and neuroscientific methods. The resulting theoretical framework lends itself to solution of problems in curve detection, shading and texture analyses, and generic shape description.

Faculty members working in Artificial Intelligence are Peter Belhumeur, Drew McDermott, and Steven Zucker. Michael Hines is a research associate. Dana Angluin is a senior research scientist with interests in formal learning theory.

Drew McDermott
2000-01-18