Distributed Hedonic Coalition Formation for Multi-Robot Task Allocation

In this paper, we study the problem of allocating multiple heterogeneous robots to tasks. Due to the limited capabilities of the robots, a task might need more than one robot to complete it. The fundamental problem of optimally partitioning the set of n robots into m disjoint coalitions for allocati...

Full description

Saved in:
Bibliographic Details
Main Authors: Dutta, Ayan, Ufimtsev, Vladimir, Said, Tuffa, Jang, Inmo, Eggen, Roger
Format: Conference Proceeding
Language:English
Subjects:
Automation
Computer aided software engineering
Conferences
Games
Resource management
Robot kinematics
Task analysis
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we study the problem of allocating multiple heterogeneous robots to tasks. Due to the limited capabilities of the robots, a task might need more than one robot to complete it. The fundamental problem of optimally partitioning the set of n robots into m disjoint coalitions for allocating to m tasks is proven to be NP-hard. To solve this computationally intractable problem, we propose a distributed hedonic game formulation, where each robot decides to join or not join a team based on the other robots allocated to that particular task. It uses a bipartite matching technique to establish an initial set of coalitions before letting the robots coordinate asynchronously and change teams if desired. Our proposed solution is proved to converge to a Nash-stable solution. Results show that our proposed approach is fast and handles asynchronous robot-to-robot communication while earning more utility (up to 23%) than an existing technique in the majority of the test cases.
ISSN:2161-8089
DOI:10.1109/CASE49439.2021.9551582