DynCNET: A protocol for flexible task assignment in situated multiagent systems

Abstract

The work presented in this paper is part of an ongoing effort to study suitable task assignment mechanisms for decentralized MAS. Our focus is on systems that are characterized by tasks with delayed commencement. Such a task requires a preceding effort before the agent can start executing the task. An example is a robot that first has to move to the location of a task before it can start executing that task. Important quality requirements for assigning tasks with delayed commencement are flexibility (enable agents to adapt task assignment with changing circumstances) and openness (enable agents to take into account other agents that come and go during the process of task assignment). In previous work, we have studied Contract Net (CNET) and a field-based approach for task assignment (FiTA). CNET does not provide the required flexibility and openness. FiTA satisfies the required qualities, however, the field-based approach provides an emergent solution for task assignment. It is well known that emergent solutions are difficult to engineer and reason about. This raises the question whether it is not easier to extend CNET to take dynamics and changes into account. This paper presents the DynCNET protocol. DynCNET is an extention of CNET, with “Dyn ” referring to support for dynamic task assignment. DynCNET provides flexibility and openness for assigning tasks with delayed commencement. We compare the DynCNET protocol with CNET and FiTA in an AGV transportation system. Our experiences in this real-world setting show that: (1) the performance of DynCNET and FiTA are similar, while both outperform CNET; (2) extending CNET to deal with delayed commencement of tasks is not obvious; the complexity to engineer DynCNET is similar to FiTA but much more complex than CNET; (3) whereas task assignment with FiTA is an emergent solution, DynCNET explicitly specifies the interaction among agents allowing engineers to reason on the assignment of tasks. This latter property may be of overriding importance in the selection of an agent-based approach for task assignment in practice. 1