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):

Report Date:

2007-12-01

Pagination or Media Count:

230.0

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.

Subject Categories:

  • Computer Systems
  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE