Accession Number : ADA482872


Title :   A United Framework for Solving Multiagent Task Assignment Problems


Descriptive Note : Doctoral thesis


Corporate Author : AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH SCHOOL OF ENGINEERING AND MANAGEMENT


Personal Author(s) : Cousin, Kevin


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a482872.pdf


Report Date : Dec 2007


Pagination or Media Count : 230


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.


Descriptors :   *ALGORITHMS , *DISTRIBUTED DATA PROCESSING , *SCHEDULING , *MULTIAGENT SYSTEMS , ARTIFICIAL INTELLIGENCE , ALLOCATIONS , LEARNING MACHINES , THESES


Subject Categories : Computer Systems
      Cybernetics


Distribution Statement : APPROVED FOR PUBLIC RELEASE