A United Framework for Solving Multiagent Task Assignment Problems
Abstract
This research presents a unified approach to representing and solving the multiagent task assignment problem for complex problem domains using ideas central to multiagent task allocation, project scheduling, constraint satisfaction, and coalition formation, forming the basis of the constrained multiagent task scheduling (CMTS) problem. The CMTS descriptor represents a wide range of classical and modern problems, such as job shop scheduling, the traveling salesman problem, vehicle routing, and cooperative multi-object tracking. Problems using the CMTS representation are solvable by a suite of algorithms ranging from simple random scheduling to state-of-the-art biologically inspired approaches incorporating evolutionary algorithms, dynamic coalition formation, auctioning, and behavior-based robotics to highlight different solution generation strategies. The framework includes a distributed process to show how to scale adapted algorithms to solve increasingly larger domain problems. This approach introduces several methods for problem decomposition and recomposition without significantly compromising solution quality. Decomposition techniques show methods to reduce the search space by several orders of magnitude allowing for improved search efficiency.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 2007
- Accession Number
- ADA482872
Entities
People
- Kevin Cousin
Organizations
- Air Force Institute of Technology