Katia Sycara - US grants

IRI-9508191 Sycara, Katia Carnegie Mellon University $50,000 - 12 mos Task-Based Coordination of Intelligent Agents Due to advances in technology, diverse and voluminous information is becoming available. This presents the potential for improved decision support, but poses challenges in terms of building tools to support users in accessing, filtering, evaluating and fusing information from heterogeneous information sources to support user tasks. Current explorations of Intelligent Agent technology have considered a single agent for each task that acts as a user's assistant. This project explores coordination among different agents that will collectively interact with other agents on a user's behalf to find, fuse and utilize information in problem solving in support of user task. A key component of the proposed research will be collaboration with Dr. Lemaitre of the LANIA Research Institute in Mexico. Because of its bi- national nature, the research effort is expected to have additional benefits, such as promotion of international scientific collaboration, and additional opportunities for experimental testing of our theories and research results.

This is a three year standard award. The research aims to develop a domain-independent computational model of negotiation capable of addressing several complex issues, such as multi-issue negotiation and decision-making under incomplete information. The research is based on a sequential decision-making view of negotiation that provides a natural representation of the multi-stage nature of negotiation. Issues such as learning associated with updating beliefs about a partially-known world will be addressed. The original sequential-decision-making-based negotiation model will be extended to explicitly model strategic parts of negotiation. The resulting formalism can be made computationally tractable by applying dynamic programming strategies. Under this model, many key issues, such as asymmetric information among agents, dynamic processes of negotiation, changing environments, etc. can be analyzed and explored experimentally. In addition, the research will contribute to the emerging field of multi-agent learning. Computationally efficient multi-agent learning algorithms will be developed and the impact of introducing learning in the model will be explored. To evaluate this research, a multi-agent simulation testbed will be developed and utilized to conduct empirical studies. These studies will be directed toward significant theoretical and practical questions, such as the effectiveness of different negotiation strategies and learning algorithms in realistic problem scenarios from domains such as supply contracting.

This research aims to develop a domain-independent computational model to support, in a uniform manner, many complex issues that arise in multi-agent contracting, such as modeling commitment flexibility in a contract, valuing a contract under assumptions of uncertainty, risk reduction, making decisions in situations of asymmetric information, or situations of sequential subcontracting where each agent must decide to subcontract part of its current contract to others. The approach is based on financial option pricing theory. This research will extend this theory to model contracts that have no analogs in financial options, such as contract quality guarantees and multiple sequential subcontracting. To evaluate the research, a multi-agent simulation testbed will be developed and utilized to conduct empirical studies that can answer significant theoretical questions. Questions to be studied for evaluation include the effects on the overall multi-agent society of different model assumptions such as stationary vs. non-stationary stochastic processes for modeling environmental uncertainty, different contracting strategies, and examinations of the value of information especially for asymmetrical information scenarios. Real world domains of theoretical and practical significance such as supply contracting and electronic commerce will be used to provide realistic problem scenarios. It is expected that the proposed research will contribute to the development of general computational models of multi-agent contracting that can answer fundamental research questions and can serve as a basis for designing efficient automated contracting systems.

Large-scale coordination tasks are becoming increasingly important in hazardous, uncertain, and time-stressed environments such as rescue operations and disaster response. In such environments, human rescuers must rapidly make decisions while under stress and with incomplete and dynamic information, that may save or put lives at risk. The proposed multidisciplinary research is founded on three key advances/technical ideas. 1) Teams of Autonomous Agents: Cyber Agents, Robots and People (CARPs) are hybrid teams that consist of large number of these entities, distributed in space and time and varying in capability and role. (2) A cooperative control paradigm facilitates the sharing of a) common goals, b) initiatives for communication and action, c) responsibilities for coherent group activity, d) information on the environment, mission, and situation, and e) assistance to overcoming barriers for various members of CARP groups whether human, robot or cyber-agent. (3) The key challenges for team formation and coordination in large-scale, uncertain coordination domains include ad hoc interoperability across different agents, teams and organizations that are brought together "as is", and co-adaptation to each other and to changing priorities and roles within the team. The impact of having CARP technology successfully deployed will allow robots to advance beyond niche roles in a handful of industries; instead they will be integrated into the larger society of humans and information systems in the workplace. Emergency response teams are an early high-payoff test domain as robots can go places normally dangerous to humans, thus saving rescuers' and victims' lives.

This proposal aims to develop algorithms for decentralized task allocation among multiple intelligent agents in uncertain environments with a focus on provable performance bounds. Four task settings and their combinations are to be considered: (1) constraints among tasks (e.g., disjoint task groups, precedence relations among tasks); (2) constraints among agents (e.g., maintenance of a communication network); (3) constraints among groups of agents (e.g., requiring a group to include agents with specialized skills); (4) on-line arrival of additional tasks. Existing algorithms for task allocation that have provable performance bounds usually do not consider the realistic constraints stated above. On the other hand, approaches that consider some of the constraints above do not have performance bounds. Furthermore, current algorithms often assume the existence of a centralized coordinator (e.g., an auctioneer in market-based approaches) and may not be scalable. Thus, there is a gap between the existing literature and the practical requirements in multi-robot applications. Hence, there is a need to design distributed task allocation methods that take into consideration practical constraints and have formal performance guarantees. The evaluation plan will use simulated and real robots in search and rescue contexts. The project will use the USARSim environment with approximately 50 simulated robots.

The mathematical techniques upon which this project will rely to develop algorithms for task allocation will depend on the problem characteristics. When there are constraints among tasks, the project will use techniques from combinatorial optimization and linear programming. For tasks where each task can be performed by multiple agents, the project will use concepts from cooperative game theory and coalition formation in conjunction with integer optimization techniques. For dynamically arising tasks, the project will explore the use of stochastic programming techniques with the key idea being use of the dual of the integer program model of the task allocation problem to design "bidding rules" for agents that ensure a performance guarantee for the overall system.

A wide range of application domains -- including emergency response, homeland security, environmental monitoring, hazardous waste cleanup and manufacturing -- stand to benefit from the task allocation techniques proposed in this project. Results from this project will enable application domains to more fully reap the benefits of emerging robotic technology by providing techniques that allow robots to autonomously and efficiently coordinate and allocate tasks among themselves. Graduate students will play a major role in conducting the proposed research. Additionally, this project will provide research opportunities to undergraduate students both within Carnegie Mellon University and from other institutions through the Robotics Institute Summer Scholar program.

Cyber-Physical Systems (CPS) encompass a large variety of systems including for example future energy systems (e.g. smart grid), homeland security and emergency response, smart medical technologies, smart cars and air transportation. One of the most important challenges in the design and deployment of Cyber-Physical Systems is how to formally guarantee that they are amenable to effective human control. This is a challenging problem not only because of the operational changes and increasing complexity of future CPS but also because of the nonlinear nature of the human-CPS system under realistic assumptions. Current state of the art has in general produced simplified models and has not fully considered realistic assumptions about system and environmental constraints or human cognitive abilities and limitations. To overcome current state of the art limitations, our overall research goal is to develop a theoretical framework for complex human-CPS that enables formal analysis and verification to ensure stability of the overall system operation as well as avoidance of unsafe operating states. To analyze a human-CPS involving a human operator(s) with bounded rationality three key questions are identified: (a) Are the inputs available to the operator sufficient to generate desirable behaviors for the CPS? (b) If so, how easy is it for the operator with her cognitive limitations to drive the system towards a desired behavior? (c) How can areas of poor system performance and determine appropriate mitigations be formally identified? The overall technical approach will be to (a) develop and appropriately leverage general cognitive models that incorporate human limitations and capabilities, (b) develop methods to abstract cognitive models to yield tractable analytical human models (c) develop innovative techniques to design the abstract interface between the human and underlying system to reflect mutual constraints, and (d) extend current state-of-the-art reachability and verification algorithms for analysis of abstract interfaces, iin which one of the systems in the feedback loop (i.e., the user) is mostly unknown, uncertain, highly variable or poorly modeled.

The research will provide contributions with broad significance in the following areas: (1) fundamental principles and algorithms that would serve as a foundation for provably safe robust hybrid control systems for mixed human-CPS (2) methods for the development of analytical human models that incorporate cognitive abilities and limitations and their consequences in human control of CPS, (3) validated techniques for interface design that enables effective human situation awareness through an interface that ensures minimum information necessary for the human to safely control the CPS, (4) new reachability analysis techniques that are scalable and allow rapid determination of different levels of system safety. The research will help to identify problems (such as automation surprises, inadequate or excessive information contained in the user interface) in safety critical, high-risk, or expensive CPS before they are built, tested and deployed. The research will provide the formal foundations for understanding and developing human-CPS and will have a broad range of applications in the domains of healthcare, energy, air traffic control, transportation systems, homeland security and large-scale emergency response. The research will contribute to the advancement of under-represented students in STEM fields through educational innovation and outreach. The code, benchmarks and data will be released via the project website.

Formal descriptions of models of human cognition are in general incompatible with formal models of the Cyber Physical System (CPS) the human operator(s) control. Therefore, it is difficult to determine in a rigorous way whether a CPS controlled by a human operator will be safe or stable and under which circumstances. The objective of this research is to develop an analytic framework of human-CPS systems that encompasses engineering compatible formal models of the human operator that preserve the basic architectural features of human cognition. In this project the team will develop methodologies for building such models as well as techniques for formal verification of the human-CPS system so that performance guarantees can be provided. They will validate models in a variety of domains ranging from air traffic control to large scale emergency response to the administration of anesthesia.

For robots to effectively collaborate with humans, they must be able to reason about the ethical consequences of their decisions and actions, incorporating societal values, rules, and conventions. Consider, for example, autonomous cars, which are envisioned to become commonplace in 5-10 years. Autonomous cars will provide many advantages for road safety, and they will offer mobility to those with physical challenges. For such cars to be successful, however, multiple ethical problems must be solved. For example, is it allowable for a car to break traffic laws as it is taking a wounded person to a hospital? What should a car do if it recognizes that an accident is unavoidable? How can a car reason in a way that is understandable and acceptable in human society (and courts of law)? Important ethical questions also arise in applications of robotics to areas such as military engagements, law enforcement, and healthcare. To address these issues, the research will provide ways for robots to reason and plan their tasks and make ethically sound decisions. These reasoning procedures will enable robots to learn and adapt over time as laws and social conventions change.


The research approach is based on normative reasoning integrated with Markov Decision Process (MDP) planning to enable the creation of an ethical intelligent Physical System (IPS) that will be evaluated via human experiments. The research is innovative in that it will provide: (a) an integrated way of reasoning about task performance and ethical behavior in the context of long-term autonomy, where ethical rules can be changing and action consequences could be task and context dependent, (b) principled ways of evaluating consequences of robot actions, by considering and resolving conflicts between domain goals and normative goals, (c) criteria to determine norm priority in a flexible and context dependent manner, (d) methods to consider the whole life-cycle of norms, namely norm activation, deactivation, contradiction, violation and obsolescence.