A Distributed Approach To Solving Constrained Multiagent Task Scheduling Problems

Kevin Cousin, Gilbert L. Peterson

The constrained multiagent task scheduling problem is a problem class that describes complex scheduling problems that integrate stochastic task allocation with constraint satisfaction for agents that concurrently execute multiple tasks. The combination of elements from constraint satisfaction, task allocation and resource scheduling produces a challenging class of problems. Unfortunately, existing work in multiagent scheduling limits the solution space and therefore task allocations do not completely encompass the complexity and interaction of the full multiagent task scheduling problem. We propose a problem description and distributed approach designed to directly solve such problems allowing optimal and approximated solution comparison. Experimentation using a simulated alarm handling domain provides empirical evidence of the successful adaptation of our approach to solving constrained multiagent task scheduling problems with scalability towards large problem sizes.

Subjects: 7.1 Multi-Agent Systems; 7. Distributed AI

Submitted: Sep 14, 2007