Decentralized Coalition Structure Formation for Interdependent Tasks Allocation

This paper addresses the problem of task allocation among multiple autonomous agents that must accomplish a complex global task. Solutions to the problem have real-world applications in defense, space, disaster management, etc. We solve this problem via agent coalition formation. Multiple coalition...

Full description

Saved in:
Bibliographic Details
Main Authors: Ahmadoun, Douae, Bonzon, Elise, Buron, Cedric, Moraitis, Pavlos, Saveant, Pierre, Shehory, Onn
Format: Conference Proceeding
Language:English
Subjects:
Autonomous agents
Autonomous underwater vehicles
coalition formation
Complexity theory
Conferences
constraint programming
Disaster management
multi-agent systems
Programming
Radar
task allocation
task interdependence
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper addresses the problem of task allocation among multiple autonomous agents that must accomplish a complex global task. Solutions to the problem have real-world applications in defense, space, disaster management, etc. We solve this problem via agent coalition formation. Multiple coalition formation mechanisms were introduced in prior art, seldom accounting for interdependent tasks. We address this challenge. We introduce an anytime decentralized coalition formation mechanism that enables agents with complementary capabilities to form, autonomously and dynamically, feasible coalition structures that accomplish a global, composite task. The formed structures are incrementally improved via agent replacements to optimize a global utility. We analyze the complexity and show that, although the general problem is NP-hard, our mechanism provides a solution within acceptable time. We present extensive experimental results that illustrate the added value of our approach.
ISSN:2375-0197
DOI:10.1109/ICTAI52525.2021.00018