DYNAMITE (DYnamic Negotiation-based Adaptive Multi-agent TEams), will enable simple agents to negotiate, so as to self-organize into large-scale teams, in a bottom-up fashion. Team members will negotiate to aggregate and share tasks, to reorganize or merge or split teams, to resolve conflicts, and do so in real-time.

Our DYNAMITE project is focused on collaborative negotiations for distributed re-source allocations in real-time, dynamic environments. We use distributed constraint optimization (DCOP) as a basis for distributed decision-making for resource allocation. In this approach, global state is described by a set of variables and each variable is assigned to an agent who has control of its value. Interactions between the local choices of each agent are modelled as constraints between variables belonging to different agents. If not all constraints can be satisfied rather than simply returning failure, agents must find the solution that is closest to a satisfactory solution.

We have developed a novel, complete, asynchronous algorithms for distributed constraint optimization called Adopt. Given a constraint graph and priority ordering, agents form a search tree where each agent has at most one parent and there are no neighbors in different subtrees. The algorithm begins by each agent instantiating its variable concurrently and sending this value to all its connected lower priority agents via a VALUE message. After this, agents asynchronously wait for and respond to incoming messages. Lower priority agents choose values that have the least deficiency given the current values of higher priority agents. In order to escape local minima, lower priority agents report feedback to higher priority agents.

When DCOP algorithms are used in real-world environments, real-world problems need to be dealt with. In particular, the set of tasks may not be exactly known and the set of tasks may change over time. Previous resource allocation algorithms have not been able to handle such issues. We have developed extensions to Adopt for distributed constraint optimization which allows it to be applied in such real-world domains. The approach relies on maintaining a probability distribution over tasks that are potentially present. The distribution is updated with both information from local sensors and information inferred from communication between agents.

Our current focus is on developing extensions to Adopt which allow it to deal with the real-time nature of the environment. Currently, Adopt reasons reactively about proposed resource allocations and provides solutions in an anytime manner. However, in highly dynamic environment this is not sufficient and a more principled, explicit consideration of time is being explored.

Funding: Autonomous Negotiating Targets (ANT) program of DARPA ITO.