Satoru Fujita, NEC Corp., Japan, and Victor R. Lesser, University of Massachusetts, USA
This paper focuses on a deadline-based multiagent task decomposition/scheduling of hierarchical task structures in an environment in which one agent is responsible for assigning subtasks and their execution order to a set of agents. The overall task to be decomposed is specified in an extended version of TAEMS task modeling framework in which task quality and execution time are uncertain before execution and are represented in the form of a probability distribution.
The master agent generates and assigns an initial subtask schedule to agents, and if necessary will revise agent schedules whenever agents make rescheduling requests. These requests are based on the degree of deviation that has occurred in expected quality and duration as a result of actual method execution. Evaluations of scheduler performance indicate a phase transition of rescheduling efficiency with respect to problem difficulty. Specifically, while frequent rescheduling was ineffective for both very easy and very difficult problems, it was extremely effective in the transition region (mid-range) of difficulty.