Autonomous Team Coordination

A second principal research area I am interested in is that of autonomous team coordination. Specifically, I am interested in coordinating limited resources under dynamic and unstructured conditions. My doctoral work produced the “TraderBots” software module that allows market-based coordination of a team under dynamic conditions. This software module, enhanced by the contributions of several other faculty, students and staff members, is now licensed to a few industry users. Market-based coordination solves the task-allocation problem (that is, who should do what) in multirobot coordination by creating a virtual economy where the robots are traders, tasks and resources are traded commodities, and allocations are determined via auctions. My work in team coordination continues primarily through the rCommerce Laboratory (www.cs.cmu.edu/~rCommerce) which I co-direct with Professor Anthony Stentz. My work in this are is progressing in several dimensions as described next.



Dealing with dynamic and Uncertain Conditions
Operations in dynamic and uncertain environments pose a variety of challenges to team coordination: ensuring graceful degradation of solution quality with failures, enabling team functionality despite imperfect and uncertain information, maintaining effective response speed to dynamic events, and accommodating evolving conditions and constraints. Benchmarking the robustness of a coordination approach requires evaluating the diversity of failures the team can accommodate, the required quantity and certainty in information available to the team, the team’s response speed to dynamic events, the fluidity of the team, and the overall solution quality produced by the team in the face of dynamic events. I am working on improving TraderBots to support these requirements of robustness in dynamic and uncertain conditions, and am also helping to define and understand these requirements from a scientific point of view. While much can be done to improve the operation of market-based approaches in dynamic environments, a few key challenges are paramount. Effective information sharing among team members in market-based approaches is one necessary area of research. If a robot discovers a task is expensive because of new environmental information it has gathered, it can potentially allocate the task to another robot that does not have that information. This robot will then try to execute the task until it, too, perceives the new information; then it tries to allocate the task to another robot. This can continue until all robots have attempted to perform the task, causing tremendous inefficiency. Enabling both the individual robots and the team to respond quickly to dynamic conditions, and characterizing this performance is another important challenge. Other challenges for improving robustness are cooperative handling of partial malfunctions and repairs, evaluating robustness to a variety of failures (and combinations of failures), incorporating contract breaches with appropriate penalties, and incorporating sliding autonomy to allow robots to request assistance when appropriate.

Complex Tasks, Teams, and Interactions
To realize the vision of robots seamlessly integrated into society, robots must be capable of executing complex tasks as a part of complex heterogeneous teams. A team is heterogeneous if not all of its members are equally capable of performing all the tasks (e.g. because of hardware or software differences) or if its members play different roles (e.g., in team games where robots play different positions). Heterogeneity is highly advantageous for several reasons. First, complex missions often have many different functional requirements and can often be achieved more effectively by a team of specialists. Second, it is often more practical to design robots that specialize in only a small set of skills; indeed, in many domains, it may be infeasible to construct robots that can do everything. Third, by being able to coordinate heterogeneous teams, we can reuse robots across multiple applications. Ultimately coordination approaches must accommodate teams of humans, robots, and other agents engaged in complex tasks (tightly coordinated tasks and tasks with different levels of urgency and priority) and complex interactions (humans and robots interacting through speech and graphical interfaces). This is an active area of my current research sponsored by the Boeing Company. Relevant future research challenges include modeling human preferences using appropriate reward functions, developing techniques for consistently computing different robots’ costs, enabling pickup teams (dynamically formed heterogeneous teams where little may be known a priori about the task, the team members, or the environments), and addressing the challenges of human–robot teams where tasks are understandable to humans and robots and both participate in task allocation and coordinated task execution.

Learning and Adaptation
Several application domains that require teamwork, such as disaster response and grid computing scheduling, present scenarios where agents cannot complete all tasks even if they act optimally. These domains are categorized as oversubscribed, where the team resources are insufficient to complete all tasks within the required deadlines. Oversubscribed domains present several challenges to task-allocation. The primary challenge is to determine which tasks should be completed, based on estimates of future constraints, and thus minimize penalties. Within this problem space, we focus on domains where the selection of tasks for execution significantly impacts the quality of the allocation solution. Specifically, we are interested in domains where the set of tasks are not known prior to execution, new tasks are issued throughout the mission, tasks differ in importance and urgency, and failed or broken commitments incur a cost in proportion to the importance and urgency of the tasks. Existing market-based approaches to task allocation do not often reason about future tasks and thus perform poorly in domains that demonstrate the above characteristics. Although precisely anticipating the future is impossible, learning techniques can be used to identify and exploit patterns in the characteristics and rate of emergence of tasks. Thus, designing, implementing, and evaluating learning-enhanced market-based allocation approaches for oversubscribed domains are an important are of research that we have been exploring. I am also interested in enabling robots to learn better cost models during execution, and to adapt allocation strategies based on team composition, reputation of teammates and aggregate performance evaluations of teammates.

Benchmarking and Comparisons
An important need in this area of research is a clear conceptual understanding of market-based coordination approaches. Much discussion is needed to further our understanding of how components such as cost and reward functions, bidding strategies, and auction clearing mechanisms can be designed, implemented, and used effectively in different multirobot application domains. Understanding the tradeoff between solution quality and scalability when designing and implementing coordination mechanisms is also important. Additionally, much work still remains in defining a relevant set of benchmarks for effective comparison of different coordination approaches. Although market-based approaches have performed well in preliminary comparative studies, these studies are fairly limited and broader studies are in high demand.

All of my work in this area of research is done in collaboration with members of the rCommerce Lab; primarily with Professor Anthony Stentz, Robotics Ph.D. student E. Gil Jones, past students Robert Zlot and Nidhi Kalra, and staff members Marc Zinck, Balajee Kannan, and Freddie Dias. Beyond my individual research interests in this area, I have also worked on several initiatives to build a relevant research community and advance this are of research. Some of these endeavors are the creation of a market-based coordination wiki to encourage researchers in this area to discuss relevant challenges, relevant tutorials and workshops at prominent Robotics and Artificial Intelligence conferences, and the publication of the first survey paper in this area.