Main menu >> Computer Science >> Artificial Intelligence

Computer Science

Artificial Intelligence
^ Agent Generation and Control
G. Agha,* N. Jamali, P. Thati
U.S. Air Force Office of Scientific Research, F49620-97-1-0382

Agents provide a natural abstraction for using geographically distributed computational and memory resources. Agents are autonomous mobile actors that may be invoked to satisfy specific goals that may require traveling across physical and economic boundaries. Agents and agent ensembles can exhibit resource consumptive or otherwise unsafe behavior, raising security and resource management concerns. Agents must, therefore, be limited by the resources they consume in pursuing a goal. The project is developing concepts necessary to provide linguistic and system support for defining multiagent architectures. A related goal is to extend the mathematical theory of actors to allow reasoning about multiagent systems.

^ An Integrated Approach to Concept Learning in Humans and Machines
G. DeJong,* B. Ross, G. Murphy, L. Pitt, K. Rosengren
National Science Foundation, SBR-97-20304

An integrated multiparadigm model of concept acquisition requires a single mechanism to exhibit SBL-like or EBL-like behavior as appropriate and be sensitive both to the learning problem and context. Furthermore, the model must be sufficiently rigorous to support the mathematical analysis of computational learning theory. This research integrates knowledge into learning and examines compound concept acquisition (the facilitation of later concept acquisition resulting from the acquisition of earlier ones). The project involves psychological experiments, model building, computer implementation, and analysis of the emergent formal properties.

^ Complex Skill Acquisition Using Combined Symbolic and Numeric Reasoning
G. DeJong,* M. Brodie
U.S. Office of Naval Research, N00014-94-1-0684

Researchers are developing and evaluating methods to combine prior symbolic knowledge with numerical observations. Simultaneously exploiting analytic and empirical sources results in greatly improved sample complexity and enhanced concept robustness. The approach employs the prior knowledge to "explain" observations. Explanations annotate the observations, adding many features not observed together with a hypothesized causal analysis. The approach also dismisses as irrelevant other observed features that do not participate in the causal analysis. The resulting structure can be seen as a hypothesis of great specificity requiring concomitantly far fewer examples to confirm or refute empirically.

^ Machine Learning to Improve User/Software Attitudes
G. DeJong,* M. Brodie
Yamaha Motor Co.

Researchers are examining machine learning as an alternative to the current one-size-fits-all approach to software applications. There is a large potential value-added component to such learning. After a few weeks or months of interactions with a particular software product, the user will naturally and unavoidably have expressed a great deal of his or her own goals, preferences, and personality. Explanation-based learning is being explored as a mechanism to recover this ignored information. In adapting to the user, the application will increase the effectiveness of the user/software system and improve the user's attitude toward the software package.

^ Next Generation Displays: Adapting Software Preferences to the User
G. DeJong,* M. Cibulskis
U.S. Army Research Laboratory, DAAL01-96-2-0003F

As displays become more flexible and sophisticated, the number of options available to a user increases combinatorially. It becomes increasingly difficult for the user to select display preferences that best fit the user's strengths and weaknesses. This research investigates an intelligent display which analyzes, explains, and generalizes user interactions. User interactions are seen as expressions of the user's implicit preferences. Intelligent interpretation of interactions can support a conceptually coherent display tailored to this user. The research holds the promise of insulating the user from the growing complexities of computer software through artificial intelligence. This research is part of a larger multidisciplinary effort.

^ Visual Tracking as a Feedback System
G. Hager* (Yale Univ.), D. Kriegman
U.S. Army Research Office, DAAG55-98-1-0168

Researchers are developing models for image dynamics arising from moving cameras, dynamic scenes, or changing lighting; the incorporation of image dynamics models into visual tracking algorithms; and the application of these algorithms to tracking articulated objects such as humans walking. Approaching vision from a dynamic perspective emphasizes the temporal continuity of the incoming image stream with the goal of simplifying the computational problem. This perspective leads naturally to techniques for embedding vision in a feedback loop. By taking this approach, researchers have been able to demonstrate a variety of high-performance visual tracking capabilities using only desktop hardware or PCs.

^ Analogical Approaches to Reuse of Software Artifacts
M. T. Harandi,* S. Yao
U.S. Army Construction Engineering Research Laboratory, DACA88-94-K-0014

While software reuse promises improved programmer productivity, greater code quality, and reduced developmental costs, it has been difficult to achieve under past paradigms. This research investigates the hypothesis that software reuse benefits are better realized at higher levels of abstraction than is typically attempted and that automated analogical reasoning, applied to knowledge-based domain-specific models, can greatly facilitate the reuse process. This work is being conducted within the context of the development of intelligent design assistance for the ISLE programming environment and in conjunction with the Advanced Collaborative Systems Laboratory (ACSL).

^ Distributed Knowledge Acquisition System
M. T. Harandi,* B. Park
University of Illinois

This project aims to build a distributed knowledge acquisition system by which domain experts can independently contribute to the gradual construction of a communal knowledge base. The knowledge base contains entities, such as subdomains, concepts, and variables, as well as relations between these entities. The system allows experts to enter information concerning a domain-related topic and to determine how this information affects the existing knowledge structures. Researchers are studying the use of such theories in proving, completing, or modifying user-specified knowledge segments. Researchers are also developing a new knowledge representation language and domain modeling tools and techniques.

^ Hybrid Reasoning in Multiagent Cooperative Systems
M. T. Harandi,* C. Tinelli
U.S. Army Construction Engineering Research Laboratory, DACA88-94-K-0014

Distributed problem solving has been widely used to provide intelligent support for cooperative activities. While a distinguished feature of hybrid reasoning systems is the use of multiple specialized subreasoners, they generally assume a centralized model of computation and rely on single-agent logics. Researchers on this project believe that the basic ideas of hybrid reasoning can be successfully extended to both distributed problem solving and multiagent logics. Researchers will be developing a hybrid reasoning framework for problem solving in multiagent cooperative systems. This work is being pursued in conjunction with the Advanced Collaborative Systems Laboratory (ACSL).

^ Intelligent Support for Distributed Problem Solving
M. T. Harandi,* G. Rendon
U.S. Army Construction Engineering Research Laboratory, DACA88-94-K-0014

This research deals with issues of distributed problem solving. In particular, researchers are looking for mechanisms that provide intelligent support for problem solving. This support could be in the form of reasoning mechanisms for handling interdependencies among tasks and interactions among agents. It could also be in the form of providing scenario analysis for decision making. A goal of this project is to develop a framework for representation of all relevant aspects of a problem-solving process. The framework provides a language composed of three primitives: agents, actions, and artifacts. This work is being pursued in conjunction with the Advanced Collaborative Systems Laboratory (ACSL).

^ Knowledge-based Programming Assistant
M. T. Harandi*
U.S. Army Construction Engineering Research Laboratory, DACA88-94-K-0014

The knowledge-based programming assistant (KBPA) project has been researching, designing, and constructing the elements of an intelligent programming support system capable of aiding programmers in various facets of program production, such as specification, design, coding, debugging, and testing. In this system, techniques of computer inference, general problem solving, planning, and data management are applied to a rich database of knowledge about different phases of program production. This study focuses on issues of program synthesis and analogical programming. This work is part of the research being conducted in the Advanced Collaborative Research Laboratory (ACSL).

^ Domain-independent Vision-based Navigation
D. Kriegman,* G. Hager (Yale Univ.)
National Science Foundation, IRI-9711967

Researchers are solving a set of problems associated with constructing a robust, domain-independent vision-based navigation system suitable for both structured and unstructured environment. Visual tracking is used to monitor a set of automatically selected image features, and vision-based control guides the robot's motion while avoiding obstacles. An environment is represented as a graph which may be constructed under human control (giving the system a tour) or autonomously as the system explores. The representation is constructed bottom-up from information derived directly from sensor measurements. A recognition system is used to annotate the representation with symbolic labels.

^ Face Recognition under Variable Illumination
D. Kriegman,* P. Belhumeur (Yale Univ.)
National Science Foundation Young Investigator Award, IRI-9257990

Because of illumination variability, the same object can appear dramatically different even when viewed in fixed pose. Researchers have proven that the set of images of an object under all lighting conditions is a convex polyhedral cone in the image space. The cone representation can be constructed from a small number of images and accounts for shadowing and multiple light sources. Recognition is performed through nearest neighbor classification by measuring the minimal distance of an image to each cone. In this project, researchers have demonstrated the utility of this approach for solving the problem of face recognition, and the results exceed those of popular existing methods.

^ Environment-independent Perception and Navigation for Tactical Mobile Robots: A Diktiometric Approach
D. Kriegman;* G. Hager, D. McDermott (Yale Univ.); M. Hyman
Defense Advanced Research Projects Agency, DAAE07-98-C-L031

While algorithms for autonomous mobile robot exploration and navigation in unknown environments have been proposed, few of these have been implemented on real robots because of a mismatch between the theoretical models of sensors and the actual sensors. Instead, this bottom-up approach starts with well developed and understood sensing methods (visual tracking coupled with low resolution range sensing) and from these methods derives a representation which can be used to guide navigation and exploration. The Diktiometric Boundary Representation is a topological representation augmented with metric information constructed from sensor information as the robot navigates.

^ Capture Regions for Grasping, Manipulating, and Reorienting Parts
J. Ponce*
National Science Foundation, IRI 990709; Beckman Institute for Advanced Science and Technology

This project addresses the problem of manipulating objects by characterizing the regions of their configuration space where they are confined by physical constraints (obstacles, friction, and gravity). The current focus is on planning planar manipulation tasks using three mobile robots, constructing collision-free motion plans for these robots, constructing a new prototype of a reconfigurable gripper and developing its control algorithms, and taking the role of friction into account.

^ Reconfigurable Part Feeding
J. Ponce,* S. Akella (Beckman)
National Science Foundation, IRI 990709; Beckman Institute for Advanced Science and Technology

This project addresses the problem of manipulating mechanical parts with simple reconfigurable mechanisms. Researchers have developed and constructed a novel part feeder and its control software, capable of constructing reorientation plans from known part geometry. The applicability of this approach to other problems, such as part recognition and mating, is being investigated.

^ Three-dimensional Vision Systems
J. Ponce*
University of Illinois

The aim of this project is to develop practical vision systems capable of 3-D interpretation of various types of image data. The focus is on interactive image synthesis from video clips using parameterized image varieties and upgrading projective reconstructions to metric ones using a minimal set of assumptions on the cameras.

^ An Intelligent Microscope for Transmission Electron Microscopy
C. Potter, B. Carragher, D. Kriegman,* R. Milligan (Scripps Research Inst.)
National Science Foundation, DBI-9904547

In this project, researchers are developing, implementing, and testing an intelligent software system for the acquisition of images from a transmission electron microscope. Molecular microscopy can provide unique information about biological structure from the molecular to cellular level, yet a bottleneck to this technique is that an enormous number of images must be acquired for structural analysis. This project integrates instrument control, feature recognition, machine learning techniques, and reconstruction to improve the quality and quantity of data collected. This approach is being applied to determine structural models of motor proteins, particularly muscle filaments and microtubes.

^ Model of Superior Colliculus with a Spatiotemporal Neuron Model
S. R. Ray,* C. Seguin, T. Anastasio
Defense Advanced Research Projects Agency

The superior colliculus is a region of the central nervous system which fuses input data from several modes (visual, auditory, somatosensory, and so forth) and computer orienting output for directing attention, such as head rotation. This project uses a neuron model with trainable temporal response. Spatiotemporal maps are learned by self-organizing algorithms which simulate known functions of the superior colliculus. The result is expected to have engineering applications.

^ Neural Network Methods for Temporal Sequence Processing
S. R. Ray,* H. Shah
University of Illinois

The storage of long temporal vector sequences and their recognition and recall is a subject of considerable interest both in engineering application and in neuroscience. A new method for storing long temporal sequences which can be content-addressed and retrieved from the starting point is under study. The method applies multilayer "chunking" of invertible vectors in feature map architectures. This multilayer method has the potential to store a quantity of distinct sequences in the same elements and to demonstrate the property of replay of long experiential memories discovered by Wilder Penfield in human subjects some decades ago.

^ Probabilistic Learning of Causal Relationships through Time
S. R. Ray,* W. H. Hsu
University of Illinois

Predicting, forecasting, or monitoring of time series require the capability to build complex models from data. To take proper account of the spatial and temporal referencing of data sets, a quantitative analysis of their causal and temporal characteristics is required. This analysis yields two benefits: a criterion for hierarchical decomposition or automatic relevance determination and a metric for choosing and applying the "right tool for the right job." The first criterion is an unsupervised learning mechanism; the second is a high-level variety of metric-based model selection. The resulting problem components can be more effectively learned, then recombined, using sensor and data fusion algorithms. Such an approach finds application in agricultural monitoring.

^ Large-Scale Temporal Associative Memory
S. Ray,* S. Swarup
University of Illinois

The basic problem addressed is to research methods for learning to store and recognize a large body of temporal sequential percepts (presented in any order) utilizing neuroscience compatible techniques. Further, the system must be capable of stable learning and forgetting of randomly presented samples. In spite of a decade or more of research in artificial neural networks, temporal sequence associative memory is still very poorly understood. Researchers are studying, analyzing, and simulating a number of different models.

^ Self-Aiming Camera
S. Ray,* T. Anastasio, P. Patton
University of Illinois

The superior colliculus in vertebrates appears to be a primary agent in deciding the direction of saccades and head-turning actions. Multisensory information, especially visual, audible, and somatosensory, feeds the two-layer neural network which comprises the superior colliculus. This research team has developed and continues to develop models of the SC that learn to adapt to variations in the head dimensions and visual/auditory properties. To demonstrate the overall system, including learning, researchers are constructing a camera and microphone system which will supply input to the model SC and respond to its directives. The camera/microphone system is fully operative on a physically fixed frame.

^ Inference with Classifiers
D. Roth,* V. Punyakanok
National Science Foundation, Information Technology Research, IIS-00-85836

In many situations it is necessary to make decisions that depend on the outcomes of several classifiers in a way that provides a coherent inference that satisfies some constraint. These constraints might arise from the sequential nature of the data or other domain specific constraints. Researchers are studying two general approaches for this problem and are evaluating those in the context of an important inference problem in natural language—identifying phrase structure. The first approach studied is a Markovian approach that extends standard HMMs to allow the use of a rich observation structure and of general classifiers to model state-observation dependencies. The second is an extension of constraint satisfaction formalisms.

^ Intermediate Knowledge Representations that Facilitate Learning
D. Roth,* S. Agarwal, C. Cumby, W. T. Yih, D. Zimak
National Science Foundation, Information Technology Research, IIS 00-85836; NSF IIS 00-85980; (Office of Naval Research) Multidisciplinary Research Program of the University Research Initiative Award

Learning becomes easy once the correct input representation has been chosen. A representation that produces linearly separable point sets is an example. Several projects are aimed at automatically generating intermediate representations to aid supervised learning algorithms, developing methods that allow the use of relational representations and of learning relational definitions, and developing a flexible knowledge representation language that can be used along with feature-efficient learning algorithms. Applications of this general knowledge representation paradigm are studied in the context of learning in the natural language domain and visual recognition.

^ Learning Coherent Concepts
D. Roth,* A. Garg, V. Punyakanok
National Science Foundation, CAREER Award, IIS-9984168

This research seeks to develop an integrated view (theoretical understanding, algorithms development, and experimental evaluation) for learning coherent concepts. These are learning scenarios that are common in cognitive learning, where multiple learners co-exist and may learn different functions on the same input, but there are mutual compatibility constraints on outcomes. This effort will consist of developing a learning theory for these situations and of studying algorithmic ways to exploit them in natural language inferences. The theoretical study concentrates on developing a semantics for the coherency conditions and study of it from a learning theory point of view. The goal is to understand ways that learning can become easier and more robust in these situations. The algorithmic study concentrates on developing ways to exploit coherency and makes use of several important problems in natural language processing as a testbed for investigating chaining of coherent classifiers and inferences that rely on the outcomes of several classifiers.

^ Learning from Data and Additional Knowledge Sources
D. Roth*
National Science Foundation, IIS-9801638

The majority of the work in learning assumes that the learner interacts with the world via examples. This research focuses on situations in which the learner can interact with many information sources. Some of these may supply the learner with examples, while others may supply other types of information. In text-understanding related tasks, for example, in addition to examples (text) the learner may make use of dictionaries, thesaurus, experts of various sorts, various general and domain-specific taxonomies, and other sources. In other cases, the additional information can be viewed as cross-modality information. This research is a study of how learning algorithms can make use of this additional information in various learning models and for various applications.

^ Learning to Perform Knowledge-intensive Inferences
D. Roth*
National Science Foundation, IIS-9801638

The goals of this research are to study an integrated theory of learning, knowledge representation, and reasoning, and evaluate it on large-scale, knowledge-intensive inferences in the natural language domain. Recent studies within the learning-to-reason framework have shown that there is much to gain from studying these issues within a unified framework. This research investigates some of the fundamental issues within this framework, concentrating on a probabilistic setting.

^ Machine Learning in Natural Language Processing
D. Roth,* Y. Even-Zohar, A. Garg, V. Punyakanok
National Science Foundation, IIS-9801638; NSF, KDI SBR 98-73450

Two main lines of research are being pursued. One focus is on developing a coherent learning theory account of the major statistical approaches to learning in natural language. This is an attempt to develop better learning methods and an understanding of the role of learning in natural language inferences. A second focus is on the study of knowledge representations and learning techniques for various language-understanding related tasks. The emphasis is on learning techniques that tolerate data of high dimensionality and on incorporating additional knowledge. Projects include context-sensitive spelling correction, prepositional phrase attachment, part of speech tagging, shallow parsing, and applications to information extraction.

^ Robust Methods for Natural Language-based Human and Machine Interaction
D. Roth,* X. Li, V. Punyakanok, W. T. Yih
(Office of Naval Research) Multidisciplinary Research Program of the University Research Initiative Award

This research is direct toward development of robust, freestyle, and adaptive natural language-based human and machine interaction. These include developing robust methods for identifying phrases in sentences. This is a fundamental technology that underlies the ability to extract key phrases and perform shallow parsing of sentences. The research also targets methods for information extraction, a robust identification of functional phrases in sentences. This is part of an effort to construct a more abstract representation of sentences that will be used to respond to queries and/or access a knowledge base. Another focus is on question–answering. This approach integrates the two other methods with relevant learning, knowledge representation, and inference methods in the natural language domain to a preliminary open domain question–answering system.

^ The Role of Experience in Natural Language
D. Roth,* K. Bock, J. Cole, G. Dell, C. Fisher, S. Garnsey, A. Goldberg, S. Levinson
National Science Foundation, KDI SBR 98-73450

An integrated multiparadigm approach to the study of learning mechanism in language production and comprehension is studied. The language processing system is constantly changing. It adapts quickly to recent experience while continuing to reflect the accumulated experience of a lifetime of speaking, listening, reading, and writing. This project integrates research efforts in psycholinguistics, linguistics theory, and computational models of learning in an attempt to address the mechanisms that enable the language processor to adapt to experience. In addition, the research will suggest learning mechanisms for language processing technology, particularly for rapid adaptation to changing linguistic environments.

^ The SNoW Learning Architecture
D. Roth,* A. Carlson
National Science Foundation, IIS-9801638; NSF KDI SBR 98-73450

A learning architecture and algorithms that are tailored for learning on large-scale, knowledge-intensive problems are being developed. The SNoW learning architecture is a sparse network of linear units over a common predefined or incrementally learned feature space. It is tailored for learning in domains in which the potential number of features taking part in decisions is very large, but may be unknown .:italic{a priori):.. Preliminary versions of SNoW have already been used successfully on a variety of large-scale learning tasks in NLP and in the visual processing domain, including face detection and object recognition.


Summary of Engineering Research