Carnegie Mellon University Robotics Institute Research Guide

Multi-Agent Systems

Research in the area of multi-agent and multi-robot systems is concerned with the effective coordination of autonomous agents to perform tasks so as to achieve high quality overall system performance. Multi-agent coordination challenges include the lack of single point of control, local views of each agent that provide only incomplete information, private goals and solution procedures of the agents, communication asynchrony, dynamic environments and uncertainty. Coordination regimes include teamwork, where the agents are cooperative and coordinate to achieve a global team goal, or regimes where the agents are self-interested and try to achieve individual goals. An extreme case is where agents are adversaries and try to fulfill their individual goals even while inflicting costs/harm on one another. Over the past 10 years, research at RI has encompassed all these types of coordination.

In teamwork settings, UAVs and UGVs collaborate to collect and fuse information for increased situational awareness (Sycara, Scerri), use market-based algorithms for task allocation for space application (Dias, Stentz), such as Mars rover exploration.

Other applications include using UAVs with different types of sensors to find ground vehicles that emit RF signals (Scerri, Sycara) in the least amount of time, and research in coordinated path planning so as to find safe paths with minimal cost that respect environmental constraints (Likhachev), or optimize the detection of victims in urban search and rescue (Sycara, Scerri). Additionally, applications such as robotic assembly (Singh, Simmons), and Oil and Gas extraction/refinement/transportation (Browning, Dias, Schempf) provide additional challenges for teamwork coordination:

• In the case of robotic space assembly, multiple trade-off challenges for stand-alone vs. collaborative operation need to be negotiated. The research focuses on robot software architectures for multi-robot coordination, task planning for assembly teams, detecting when multi-agent plans are likely to fail, and re-planning to dynamically reformulate teams to optimize resource utilization; efforts also investigate the use of "sliding autonomy" to enable humans and robots to seamlessly switch control from one to another (see http://www.frc.ri.cmu.edu/projects/trestle/index.html).
• In the case of UGV-based motion-planning, some research has focused on addressing the challenges of effectively coordinating heterogeneous teams operating in uncertain and dynamic environments. Faculty (Dias, Stentz) have developed a coordination and execution mechanism that combines market-based, play-based, and operations research-based techniques that allows customization for different operations, fluidity of team members, and options for using different planning mechanisms as appropriate for given tasks. Such a coordination mechanism is capable of handling a variety of tasks at different levels of abstraction and with different capability requirements, dynamic task and resource re-allocation, dynamic grouping of team members, and constraints on resources, teams, and tasks.
• In the case of combined UAV/UGV motion planning, Graph-based searches, such A* search and Dijkstra's search, are highly popular means of planning due to their generality, solid theoretical ground and simplicity in the implementation. The type of planning problems they can usually solve in real-time however, is limited to low-dimensional problems, whereas the joint state-space that represents planning for teams of robots performing tasks requiring collaborations, regular communications and other kinds of interaction is very high-dimensional. Likhachev has shown how and when a one-shot joint state-space planning can be decomposed into planning with a series of lower-dimensional searches converging to a solution with rigorous guarantees on completeness and the solution quality (see http://www.cs.cmu.edu/~maxim/multiagent.html).
• In the case of search-and-rescue applications RI's focus (Scerri, Sycara) is on how to create very large cooperative teams that can achieve complex objectives in complex environments. Algorithms for key aspects of large-scale coordination including task assignment, plan management, maintaining ad hoc networks and failure handling have been developed to collect information about an environment; hence a large focus of effort has been on planning for information collection, fusion of information and sharing of information under network constraints. Moreover, the collected information is not useful until a human can understand the situation, providing another focus on operator interfaces for large robot teams.

When the agents are self interested and economically rational, trying to maximize their individual goals/utilities, automated negotiation techniques have been developed (Sycara) for resource allocation, and also for formation of optimal teams (coalitions) that consider the agents' task-related abilities and utilities (Sycara). In adversarial environments, effective algorithms and applications have been developed in domains such as robotic soccer (Veloso), pursuit evasion (Singh, Sycara), or in agent societies where different groups in the society may be in conflict with one another and where we are interested in understanding the spatio-temporal characteristics of such conflicts (Sycara).

Besides the work on applications, extensive research is being done on theoretical work on multi-agent coordination and control (Likhachev, Rubinstein, Scerri, Simmons, Smith, Sycara, Veloso) as well as multi-agent learning (Gordon, Simmons, Sycara, Veloso). Additional theoretical contributions have been made in multi-agent coordination in open environments where heterogeneous agents with different task performance capabilities can enter and exit dynamically. In such environments, algorithms have been developed for agent discovery, selection and coordination (Scerri, Sycara). Additionally, research has been concerned with coordination architectures, e.g. hierarchical vs. peer-to-peer interactions, as well as the level of individual agent sophistication and intelligence ranging from large numbers of simple agents that interact through evolutionary algorithms to sophisticated intelligent agents (Simmons, Smith, Sycara, Veloso).

Another dimension of challenges in multi-agent coordination is scaling up the number of coordinating agents and the associated algorithms for information sharing, task allocation and planning. To this end, research in RI has developed innovative algorithms for understanding the emergent dynamics of information sharing in very large agent networks with different topologies comprised of thousands of agents (Scerri, Sycara), efficient algorithms for scaling path planning (Likhachev, Scerri, Sycara) and algorithms for adversarial games in graphs (Sycara).

The research on multi-agent systems provides foundations for research in human and robot teams and Human Robot Interaction and Human Computer Interaction (Dolan, Scerri, Simmons, Steinfeld, Sycara). A significant share of multi-agent systems research within the RI is conducted in collaboration with other units of SCS and the rest of the university. For example, faculty members supervise students and collaborate with faculty in CSD (Sandholm, Harhold-Bachler) and others (Smith, Sycara) supervise students and collaborate with faculty in the Tepper School of Business.

Continue Reading: Planning & Scheduling