Dynamic team formation addresses the problem of forming teams of robots and humans in a pickup manner. That is, we assume that both human and robot team members may have only minimal knowledge of each other's behavior but are able to team effectively. We focus specifically on the problem of dynamically forming teams of heterogeneous robots with a range of capabilities together with human team members. The human members of the team are responsible for the highest-level planning and the robots have comparatively limited capabilities; they can sense information about their environment, and they can be tasked to execute abstract tasks. Furthermore, the robots are capable of accepting spoken orders that specify high-level objectives, receive important cue information about the terrain, and provide status reports as needed. These research objectives are demonstrated and evaluated in a treasure hunt scenario.

Allocation

TraderBots, developed by Dias and Stentz (Dias 2004) is a coordination mechanism, inspired by the contract net protocol by Smith (Smith 1980), is designed to inherit the efficacy and flexibility of a market economy, and to exploit these benefits to enable robust and efficient multirobot coordination in dynamic environments. A brief overview of the TraderBots approach is presented here to provide context for this work.

Consider a team of robots assembled to perform a particular set of tasks. Consider further, that each robot in the team is modeled as a self-interested agent, and the team of robots as an economy. The goal of the team is to complete the tasks successfully while minimizing overall costs. Each robot aims to maximize its individual profit; however, since all revenue is derived from satisfying team objectives, the robots self-interest equates to doing global good. Moreover, all robots can increase their profit by eliminating excess cost. Thus, to solve the task-allocation problem, the robots run task auctions, and bid on tasks in other robots task auctions. If the global cost is determined by the summation of individual robot costs, each deal made by a robot will result in global cost reduction. Note that robots will only make profitable deals. Furthermore, the individual aim to maximize profit (rather than to minimize cost) allows added flexibility in the approach to prioritize tasks that are of high cost and high priority over tasks that incur low cost but provide lower value to the overall mission. The competitive element of the robots bidding for different tasks enables the system to decipher the competing local information of each robot, while the currency exchange provides grounding for the competing local costs in terms of the global value of the tasks being performed.

Coordination

Veloso and colleagues (Bowling, Browning, & Veloso 2004)introduce a skills, tactics, and plays architecture (STP) for controlling autonomous robot teams in adversarial environments. In STP, teamwork, individual behavior, and low-level control are decomposed into three separate modules. Relevant to our implementation are Plays which provide the mechanism for adaptive team coordination. Plays are the central mechanism for coordinating team actions. Each play consists of the following components: (a) a set of roles for each team member executing the play, (b) a sequence of actions for each role to perform, (c) an applicability evaluation function, (d) a termination evaluation function, (e) a weight to determine the likelihood of selecting the play. Each play is a fixed team plan that describes a sequence of actions for each role in the team towards achieving the team goal(s). Each of the roles is assigned to a unique team member during execution. The role assignment is based on the believed state of the world and is dynamic (e.g. role A may start with player 1, but may switch to player 3 as execution progresses). Note that the role assignment mechanism is independent of the play framework.

The concept of plays was created for domains where tight synchronization of actions between team members is required. Therefore, the sequence of tactics to be performed by each role is executed in lock step with each other role in the play. Hence, the play forms a fixed team plan whereby the sequence of activities is synchronized between team members.

As not all plans are appropriate under all circumstances, each play has a Boolean evaluation function that determines the applicability of the play. This function is defined on the team's belief state, and determines if the play can be executed or not. Thus, it is possible to define special purpose plays that are applicable only under specific conditions as well as general-purpose plays that can be executed under much broader conditions. Once executed, there are two conditions under which the play can terminate. The first is that the team finishes executing the team plan. Each play includes an evaluation function that determines whether the play should be terminated. As with applicability, this evaluation function operates over the team's belief state. Hence, the second means of ending a play is if the termination evaluation function determines that the play should end, either because it has failed or is successful.

Team strategy consists of a set of plays, called a playbook, of which the team can execute only one play at any instant of time. A play can only be selected for execution if it is applicable. From the set of applicable plays, one is selected at random with a likelihood that is tied to the play's weight. The plays are selected with a likelihood determined by a Gibbs distribution from the weights over the set of applicable plays. This means the team strategy is in effect stochastic. This is desirable in adversarial domains to prevent the team strategy being predictable, and therefore exploitable by the opponent.

Language

The human interface, Teamtalk (Harris et al. 2004), is a multi-modal multi-agent dialog system, which accommodates multiple dialogue agents in a single experimental framework. Teamtalk uses the Galaxy-II framework (Seneff et al. 1998) for message routing. It uses Sphinx-II (Huang et al. 1993) for automatic speech recognition, Phoenix (Ward 1994) for context-free grammar parsing, Helios (Bohus & Rudnicky 2002) for confidence annotation, Ravenclaw (Bohus & Rudnicky 2003) for dialogue management, ROSETTA (Oh & Rudnicky 2000) for natural language generation, and Swift for text-to-speech rendering. The dialog management system, Ravenclaw, is a generalized tree-based dialogue management framework that provides the designer of a dialogue management system with mechanisms through which to specify dialogue tasks.

The Teamtalk system addresses several challenges in multi-modal and multi-agent spoken dialog. Some of these challenges are currently addressed at a superficial level, as we believe that all of the elements must be in place to some degree in order to develop valid tests of the system-wide consequences of the other design decisions.