Edmund H. Durfee - US grants

This research is funded under the Special Initiative on Coordination Theory and Collaboration Technology. This is one of eleven winners under that competition. This research is directed towards integrating concepts from artificial intelligence, organization theory, and operations research into a single framework. The research argument is that the plans, organizations, and schedules studies in these separate fields can share a common representation, and are simply different abstractions of a behavioral specification. The PI develops a hierarchical, multi-dimensional specification for behavior that subsumes traditional goal, plan, functional and product hierarchies. the research outlines a protocol for coordination based on the behavioral specification, where intelligent agents incrementally exchange behavioral information and search through alternative behaviors to resolve conflicts and promote cooperation. The research also implements and evaluates this framework both in the context of cooperative robotics domain, and in the context of an intelligent systems for scheduling meetings between people. The objective is to generate scientific and technological advances using a novel, interdisciplinary approach to coordination.

This work focuses on the study of coordination between AI systems. One objective is to take techniques developed for different aspects of coordination and unify them in a single computational theory. Initially, the work will develop a formalism and computational theory that can lead to novel coordination techniques by drawing together the separate approaches of planning, organizational design, and scheduling. This theory provides a powerful framework for improving performance, reducing overhead, increasing reliability, and flexibly managing distributed resources among AI systems. The work will lead toward a generic coordination framework for developing AI systems, because we believe that reasoning about interactions with others is fundamental to intelligence. A second objective of DIAL is to build an experimental infrastructure for validating coordination theories and discovering new theories. To facilitate comparisons between alternative theories both within DIAL and elsewhere, a versatile, portable simulation testbed will be developed. Techniques will also be integrated into actual mobile robots to investigate the interplay between sensing, acting, reasoning, and communicating in real-time physical systems. The research will help pave the way for introducing intelligent, cooperating robots into real- world environments.

This award is for the purchase of equipment for the high speed acquisition of images and for manipulator end-effector hardware. The image equipment is needed for real-time performance and the end-effector hardware is needed for experimentation with manipulation tasks. The equipment is also used in integrating vision and manipulation tasks incorporating perception, cognition, and action. Applied robotics involves the integration of many areas including vision research, control research, sensor integration, and planning algorithms. This proposal requests funds for the purchase of equipment to support vision research and manipulator research. The vision equipment will allow real time processing of visual data while the manipulators (grippers, etc.) will allow the testing of manipulator algorithms with the robot arm connected to actual manipulators.

This is the first year base amount funding of a five-year PYI continuing award. This PYI will continue his research on distributed artificial intelligence (AI) with an emphasis on building intelligent computing systems for dynamic, multiagent applications. The research uses blackboard systems and other integrating architectures that allow an agent's perception, reasoning, communication, and motor components to collectively control an agent's behavior. The PI is also pursuing work in real-time artificial intelligence. He is working on developing preliminary theories of real-time reasoning that account for both meeting deadlines and for negotiating to change deadlines. This work on techniques for negotiating ties into his additional research interest in uncovering the general principles underlying coordination between intelligent agents. The goal is to build interdisciplinary theories of coordination, drawing on concepts from management science and operations research as well as AI, and to embody these theories in practical mechanisms for coordinating multiple intelligent computing systems. The near term plan is to develop a core of interdisciplinary concepts using a hierarchy of behavioral specifications as a common representation, with the long-term objective of developing fundamental theories of a science of coordination. The researcher is also interested in applying techniques for coordinating AI systems to problems in human-human and human- computer interactions.

This research explores a cooperative intelligent real time control architecture (CIRCA) developed by the PIs as an alternative to traditional approaches that have limited the power of the AI methods or embedded "reactivity" into an AI system to achieve real time performance. The CIRCA architecture uses separate AI and real-time subsystems to address the problems for which each is designed. A structured interface allows the subsystems to communicate without compromising their respective performance goals. By reasoning about its own bounded reactivity, CIRCA can guarantee that it will meet hard deadlines while using AI methods whose time performance need not be accurately predictable. With its abilities to guarantee or trade off the timeliness, precision, confidence, and completeness of its output, CIRCA should provide more flexible performance than traditional systems. This project will develop the cooperative theory which supports CIRCA's performance guarantees as well as its experimental implementation and evaluation. The main emphasis is on CIRCA's ability to combine AI and real-time subsystems.

In agent-based systems, agents can team in different combinations to cooperatively solve problems. Teaming, however, requires that agents understand each other and commit to concerted actions. In open, evolving networked systems, universal understanding and commitment are unlikely; instead, agents should congregate with those agents that they can understand and with whom they have successfully teamed in the past. Agent congregations are defined by commitments to common semantics and ontologies (conceptualizations of the world). Congregating improves the efficiency of communication and the likelihood of successful teaming. It can, however, impede the formation of effective teams whose members cross congregations, because agents need to learn new ontologies and incur overhead in searching for new congregations that meet their preferences. This project investigates how agent congregations are formed and how and when they should be reformed. The research includes simulations of large communities of agents, formal models of agency, and prototype systems. Its results will help guide the development of a national computing and communication infrastructure that supports the evolving identities and interests of scientific, educational, and commercial communities, and encourages communication between different communities. http://ai.eecs.umich.edu/people/wpb/conagents/

Networked information technology has led to unprecedented opportunities for exchanging information in a population of participants whose interests and needs vary over time. In particular, this project concerns populations of consumers looking for information products, and producers who possess products that others might be seeking. Substantial research has gone into studying how producers and consumers can settle the terms of a transaction for a particular good. However, there are many possible variations and combinations of information products and their prices that can be offered. A critical and poorly understood problem is how parties should position themselves in this vast information product and price space to differentiate themselves from competitors and attract those with whom they should transact. To address this problem, the investigators will use economic analysis and computer simulation to study how producers of information goods can learn to position themselves based on criteria such as price schedules and information content, and can adapt to changing consumer tastes where consumers might be making strategic buying decisions to affect producer positioning. This project will extend economic theory to account for these concerns, and create computational agents that can make adaptive, strategic decisions about product positioning.

The objective of this project is to solve technical problems that need to be overcome to build socio-cognitive orthotic systems, which will augment human cognitive capabilities to promote social interactions. Information technology can help a person with cognitive impairment in managing his or her everyday life, by modeling the activities the person wants or needs to do, monitoring the person's activities as they unfold, and guiding the person to ensure that the most important activities occur. Thus, information technology can provide a cognitive orthotic that augments reduced cognitive abilities and helps the person live independently. Unfortunately, though, replacing dependence on other people with reliance on information technology can mean fewer opportunities for social interaction, which in turn can lead to loneliness and isolation.

To solve this problem, a person's socio-cognitive orthotic system could be networked with the systems of other people. Now, as time passes and people make choices about their activities, these choices can help bring about, or make more difficult, potential planned social activities. Thus, the networked orthotic systems, as agents acting on behalf of their associated users, need to behave as a collaborative multi-agent system to cooperatively manage the users' plans. Each separate system needs to monitor and guide its user's activities while giving its user as much autonomy as possible to independently control his or her day, and yet must also attempt to maintain desirable options for social activities that obviously must be timed well with the schedules of other participants. And all this should be done in a timely, adaptive, and efficient way.

The hypothesis that this project will investigate is that incorporating hierarchical activity abstractions and richer constraint models into well-founded temporal constraint network representations, and augmenting distributed constraint reasoning techniques to adaptively handle these more flexible representations, will provide a principled and efficient foundation for collaborative plan management systems for individual and social activities. Some of the key ideas to be investigated include: using abstract activity specifications that can postpone commitments about which particular activities will be done, when, and by whom, until decisions need to be made; developing algorithms that can exploit, and even introduce, abstractions in activities, their timing, and (for social activities) their participants to increase flexibility and to reduce computation and communication; representing alternative activity plans, even if they contradict each other, to leave many options open for important social (and individual) activities; and capturing activity importance and costs of violating constraints in the models to calculate tradeoffs in the (likely) case where the multi-agent plans evolve such that contentions arise.

The project will build from the current state-of-the-art in hierarchical multi-agent planning and coordination, single-agent plan management, and distributed constraint reasoning. It will incorporate new ideas in multi-agent activity modeling, continual distributed constraint network maintenance, and adaptive refinement and constraint relaxation mechanisms, to innovate practical computational techniques that will scale to multi-agent applications involving complex interrelationships in continually-evolving worlds. The project will design, develop, analyze, and empirically test novel techniques for continual collaborative multi-agent management of loosely-coupled plans, a problem that deserves more study and for which no general intuitions or solution methods exist.

Developing socio-cognitive orthotics, where information technology can be cost-effectively used to simultaneously promote independence while combating isolation for cognitively-impaired people, can have tremendous societal benefits. A further expected impact of this project is that it will form the basis for a course in information technology for cognitive assistance, which will introduce first-year undergraduates not only to computer science concepts but also to the possible societal contributions computer scientists can make. It is expected that such a course can attract more students, and particularly women and minorities, to major in computer science.

The centerpiece of this project is the design, development, and evaluation of computational representations and algorithms for making software agents that are organizationally adept. An organizationally-adept agent is not only aware of its role(s) in an organization, but can also monitor how well it is fulfilling its organizational responsibilities and can proactively adapt its behaviors to meet organizational needs better. Organizationally adept agents evaluate their behaviors based not on their (agent-centric) self-interests but rather on their (organization-centric) responsibilities to each other, and autonomously adapt to achieve organizational objectives emergently.

Elaboration and adaptation by organizationally adept agents means that the ultimate organization design is formed by a combination of top-down design (to produce a "ballpark" organization) and emergent refinement processes. Further, this combination can be iterative and ongoing, where organizationally adept agents can detect tension between top-down and emergent influences, and inform the design processes of runtime interaction patterns and environmental tendencies that suggest useful top-down organization restructurings.

The intellectual problems being pursued are central to practical issues in scaling multi-agent systems to help solve complex, long-term, global problems. Many critical challenges facing society including climate change, health care, and sustainable energy|require a prolonged commitment to monitoring and managing distributed activities. Networked computer systems populated by software agents, which can be constantly measuring, comparing, and interpreting information to understand and respond to wide-scale phenomena, promise to address such challenges, but need the kinds of innovations proposed in this project. Second, while the project is specifically looking at organizations for computational agents, our results will inform, and be informed by, research on human organizations. To stimulate sharing insights and results, the investigators will organize a multi-disciplinary symposium on organization-centric reasoning, and will train an inter-disciplinary cohort of graduate students.