Our multiple robot/agent coalition formation research goal is to develop theoretical foundations and a system of coalition formation algorithms to support the allocation of task coalitions composed of humans and heterogeneous robots that are robust in a range of real-time environmental circumstances. Coalition formation partitions a set of agents into different partitions/teams. The HMT Laboratory demonstrated the limitations of applying software agent coalition formation algorithms to actual robot hardware systems and was the first to demonstrate coalition formation on real robot systems.

Coalition formation assigns robots/agents to task teams based on specified criteria; however, choosing the optimal coalition from the set of all possible coalitions is an intractable problem. Heuristic algorithms provide good solutions, but cannot be generalized to all real-time, dynamic environments. It has been proven that even approximating the coalition formation problem for task allocation is NP-Hard. The HMT Laboratory is developing a collection of algorithms that support coalition formation for a large range of real-time, dynamic situations. Task allocation is very difficult and cognitively demanding for humans, thus the coalition formation research is being integrated into the HRI research in order to support human decision making.

Recently, the lab presented a number of approximation algorithms for the coalition structure generation problem. These algorithms improve upon the existing state-of-the-art in coalition structure generation domain by guaranteeing solutions with constant factor lower bounds on the solution quality in less than the time required to solve the problem exactly. The lab is also the first to present approximation algorithms tailored to monotonic domains.

Currently, the research focuses on developing swarm-based, heuristic coalition formation algorithms that can be deployed for very large teams of robots, up to 200 agents/robots. These swarm-based algorithms do not leverage detrimental heuristics that are often used by conventional heuristic approaches, and can compute coalitions of any sizes in real-time.

Current Projects

Coalition Formation Algorithms
Multiple Robot Coalition Formation

Prior Projects

Coalition Balance
Robot Allocation through Coalitions using Heterogeneous Negotiating Agents (RACHNA)