A unified framework for solving multiagent task assignment problems

Multiagent task assignment problem descriptors do not fully represent the complex interactions in a multiagent domain, and algorithmic solutions vary widely depending on how the domain is represented. This issue is compounded as related research fields contain descriptors that similarly describe multiagent task assignment problems, including complex domain interactions, but generally do not provide the mechanisms needed to solve the multiagent aspect of task assignment.; This research presents a unified approach to representing and solving the multiagent task assignment problem for complex problem domains. Ideas central to multiagent task allocation, project scheduling, constraint satisfaction, and coalition formation are combined to form the basis of the constrained multiagent task scheduling (CMTS) problem. Basic analysis reveals the exponential size of the solution space for a CMTS problem, approximated by O(2 n(m+n)) based on the number of agents and tasks involved in a problem. The shape of the solution space is shown to contain numerous discontinuous regions due to the complexities involved in relational constraints defined between agents and tasks. 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, with varying degrees of suitability. Solution generating methods range from simple random scheduling to state-of-the-art biologically inspired approaches. Techniques from classical task assignment solvers are extended to handle multiagent task problems where agents can also multitask. Additional ideas are incorporated from constraint satisfaction, project scheduling, evolutionary algorithms, dynamic coalition formation, auctioning, and behavior-based robotics to highlight how different solution generation strategies apply to the complex problem space.; Furthermore, a new approach to solving the CMTS problem using a distributed system shows how to scale the adapted algorithms to solve increasingly larger domain problems. The distributed approach introduces several methods for decomposing a problem and recomposing subsolutions into a complete solution without significantly compromising solution quality. On the other hand, decomposition techniques show methods to reduce the search space by several orders of magnitude allowing for improved search efficiency.; Finally, experimentation in the search and recovery problem domain instance for the CMTS problem class demonstrates the ability to use the CMTS descriptor as a unified descriptor for a variety of algorithms. The results of various algorithms in turn empirically demonstrate key characteristics of the solving the search and rescue problem with and without enhanced heuristics, such as those from dynamic coalition formation and behavior-based robotics. Ultimately, the efficiency and effectiveness of solving the problem in a distributed process empirically demonstrates methods to dramatically reduce search space complexity while maintaining acceptable quality solutions in this domain. Experiments in alarm handling and search and rescue problem domains show search space reductions of 1039 and 10106 solution points respectively while producing competitive solutions.