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.
Task assignment in multiagent systems (MAS) is complex, especially in systems characterized by highly dynamic and changing operating conditions. The work presented in this paper is part of an ongoing effort of our research group to study suitable task assigning mechanisms for decentralized MAS. Our focus is on MAS with the following characteristics: ² The system is subject to highly dynamic and changing operating conditions. Examples are continuous changes in availability of resources, particular failure modes, variations in network traffic, etc. ² Agents can dynamically join and leave the system. Agents may be removed from the system at runtime, new agents may join, or agents may leave the system temporarily.
A typical example application in the domain of manufacturing control is described in [
A second typical domain that complies with the problem characteristics are automated transportation systems. In this paper we, use an industrial AGV transportation system as an example. An AGV transportation system consists of a set of automatic guided vehicles (AGVs) that transport loads in a warehouse. AGV transportation systems have to deal with dynamic operation conditions. Production machines may have variable waiting times, certain routes may be blocked, etc. AGVs can leave and re-enter the system, for example for maintenance. The stream of transport tasks that enter the system is typically irregular and unpredictable. Tasks in an AGV transportation system are characterized by delayed commencement. To execute a task, an AGV first has to drive to a load before it can pick the load and transport it to the destination. While driving towards the load all kinds of changes in the system may occur. New tasks may enter the system that are more suitable for the AGV to execute, new AGVs may become available that are more suitable to perform the task, etc.
Quality Requirements for Dynamic Task Assignment. In order to deal with the problem characteristics
mentioned above, two important quality requirements for task assignment are flexibility and openness. [
Previous Work. In a joint R & D project (EMC2 [
In previous work, we have applied two approaches for task assignment in AGV transportation systems.
First, we have applied the well-known Contract-Net protocol (CNET [
As a second approach, we have developed a field-based approach for task assignment (FiTA [
Motivations for DynCNET. Standard CNET does not provide the required flexibility and openness to cope with the system characteristics mentioned above. FiTA satisfies the required quality goals, however, the field-based approach provides an emergent solution for task assignment. It is well known that emergent approaches are difficult to engineer and reason about. Egemin engineers as well as colleague researchers and reviewers therefore raised the question whether it is not easier to adapt standard CNET to take dynamics and changes in the system into account.
This paper presents the DynCNET protocol. DynCNET is an extention of CNET, with “Dyn” referring to support for dynamic task assignment, i.e. DynCNET supports flexibility and openness for assigning tasks Overview. In the next section, we give a brief overview of the decentralized architecture of the AGV transportation system. Section 3 introduces the DynCNET protocol. In section 4, we discuss test results obtained from applying DynCNET in an AGV transportation system, and we compare DynCNET with standard CNET and FiTA. Section 5 discusses related work. Finally, in section 6 we draw conclusions. AGVs. An AGV is a unmanned, battery powered vehicle, capable of picking up loads, driving around and dropping them. AGVs can communicate by means of a wireless LAN. The AGVs are restricted to follow a predefined layout in the environment. The layout is defined in a map that consists of a network of stations and segments. AGVs are equipped with low-level control software that provides an interface to command the AGV; example commands are move(segment), pick(load), etc. The low-level control software uses sensors and actuators, and beacons in the environment to stay on track, turn, pick and drop loads, and determine the current position.
Transports. A transport represents a task to move a load from a pick location to a drop location. Transports are generated by an external system, typically a warehouse management system. Each transport has a priority that increases over time, e.g. as a result of long waiting times. The execution of a transport starts when an AGV picks the load and it terminates when that AGV drops the load at the drop location. with delayed commencement.
The AGV Transportation System this section we give a brief overview of the AGV transportation application and the basic software architecthe system without interrupting the rest of the system. We start by explaining a number of general properties of the DynCNET protocol. Then we give an overview of the default sequence of the protocol. Next we explain how the agents involved in a protocol can switch the assignment of tasks. We will use the AGV transportation scenario depicted in Fig. 3 to illustrate the steps of the protocol.
General Properties. DynCNET is an m £ n protocol. An initiator that offers a task can interact with m participants, i.e. the candidate agents that can execute the task. On the other hand, each participant can interact with n initiators that offer tasks. As an example, consider the scenario shown in Fig. 3. In the AGV transportation system, an initiator corresponds with a transport agent that represents a task in the system and the participant corresponds with an AGV agent that can execute tasks. We denote the area where an initiator (or participant) searches for participants (or initiators) the area of interest of the initiator (or participant). The dotted circles in Fig.3 show the current areas of interest of AGV A (top) and task x (bottom). For task x, there are currently two candidate AGVs to execute the task: F and G. For AGV A on the other hand, there are three possible tasks to execute: u, v, and w.
Due to the dynamics in the system, the set of candidate tasks (initiators) and agents that can execute a task (participants) can change over time. E.g., in the right part of Fig. 4, AGV E has just dropped its load and becomes a candidate to execute task x.
Default Sequence. Fig. 2 shows an AUML interaction diagram with the default message sequence of DynCNET.
The default protocol consists of four steps: (1) the initiator sends a call for proposals; (2) the participants respond with proposals; (3) the initiator notifies the provisional winner; and finally, (4) the selected participant informs the initiator that the task is started. These four steps are basically the same as in the standard CNET protocol. The flexibility of DynCNET is based on the possible revision of the provisional task assignment between the third and fourth step of the protocol.
Switching Initiators and Participants. To explain how agents can switch tasks when the conditions in the environment change, we use the UML state diagram of Fig. 5. This state diagram shows a compact repre-,./ -,./ sentation of the behavior of the initiator and participant agents in the protocol2. First we look at the protocol from the perspective of the participant, then we look from the point of view of the initiator. Switching Initiators. Consider the situation in Fig. 3 where AGV A has a provisional agreement to execute task w. While AGV A drives towards the pick location of task w, a new task p enters the system, see the left part of Fig. 4. This new task is an opportunity for AGV A.
DynCNET enables participants to switch initiators and exploit such opportunities. When a participant is ready to execute a task, it enters the Voting state where it answers cfp’s with proposals. When the participant receives a provisional–accept message (step 3 in Fig. 2), it enters the Intentional state, see Fig. 5. As soon as the participant starts the task, it sends a bound message to the initiator to inform this latter that the execution of the task is started. The participant is then committed to execute the task. However, if a new opportunity occurs before the task is started, i.e. the participant receives a better offer, the participant changes to the Switch Initiator state. In this state the participant retracts from the provisional task assignment and switches to the more suitable task.
Switching Participants. Consider the situation in Fig. 3 where the task x has a provisional agreement with AGV G. While AGV G drives towards the pick location of task x, AGV E becomes available, see the right part of Fig. 4. This new AGV is an opportunity for transport x.
2We have made abstraction of a number of synchronization issues in the description of the state diagrams. An example is the
situation where an initiator has not yet received the bound message from the provisionally assigned participant that has started a task,
while this initiator switches participants. To deal with such synchronization problems, confirmation messages are used. However, to
avoid overloaded diagrams, we have omitted these messages. For more details, see [
Discussion. Contrary to the suggestions of Egemin engineers and colleague researchers and reviewers, extending standard CNET to take dynamism and change into account is not obvious. Enabling the agents to switch the assignment of tasks increases the complexity of the protocol significantly. Since AUML diagrams do not support the specification of dynamic m £ n protocols, we used state diagrams to describe DynCNET. However, these diagrams are not simple and becomes even more complex when synchronization is taken into account. In addition, DynCNET requires the tuning of various parameters. Examples are the range of interest of both types of agents, the growth rate to extend this range when no suitable candidates are found, the pace to send call for proposals, etc. Parameter tuning is typically associated with emergent solutions such as FiTA. This paper indicates that a flexible agent-interaction protocol that deals with dynamism and change in the system also requires considerable efforts to tune parameters.
Contrary to FiTA, DynCNET explicitly defines the various communicative actions, the points of choice, and the internal state of the agents in the protocol. The protocol precisely specifies which participants are involved in the assignment of a task, when a task is provisionally assigned, when the assignment switches, and when a participant becomes committed to execute the task. The explicit specification of the protocol allows engineers to reason on the assignment of tasks and it helps them to debug the system.
DynCNET (as FiTA) supports openness during delayed commencement. Whereas FiTA inherently supports openness, the DynCNET protocol requires specific functionality for openness. In FiTA, a participant is guided by the combination of sensed fields. A field that disappears or a new field that appears will affect the combination of sensed fields. DynCNET includes specific functionality to notify agents when other agents enter and leave its current area of interest (ParticipantInScope, ParticipantOutOfScope, InitiatorInScope, and InitiatorOutOfScope).
The flexibility of DynCNET is provided by the points of choice for each agent (Switch Participant and Switch Initiator). The points of choice are abstractly defined in the protocol and need to be instantiated according to the requirements of an application at hand. In the AGV application (discussed in the next section), agents use the priorities of tasks and the distance between AGVs and loads to switch tasks. More advanced approaches can be considered, e.g., participants may (to some extent) favour tasks that are located near to other tasks increasing the change to find a closely located task when the original assignment of tasks for some reason switches.
A final remark concerns the convergence of the protocol. A potential risk of DynCNET is that the assignment of tasks oscillates between participants and no tasks are executed. In the AGV application, oscillations were avoided by: (1) limiting the areas of interest of the agents, and (2) choosing different areas of interest for initiators (task agents) and participants (AGV agents). In particular, the area of interests of AGV agents covered up to 1/10th of the total area of the map and the area of transport agents was 4 times smaller as that of AGV agents. 4
This section discusses the test results obtained from applying DynCNET in a simulated AGV transportation
system. The section starts by explaining the test setting. Subsequently, we present the results of the various
tests and we reflect on the test results. Due to space limitation only the main test results are presented. For
a detailed discussion of the remaining test results we refer to [
AGV Transportation System. All tests are performed on the map of an AGV transportation system that is implemented by Egemin at EuroBaltic. The size of the physical layout is 134 m x 134 m. The map has 56 pick and 50 drop locations. We used a standard transport profile that is used by Egemin for testing purposes. This profile generates 140 transports with a random pick location and a random drop location per hour real time. Each transport is assigned a random priority that increases over time. In the simulation, we used 14 AGVs just as in the real application. The average speed of driving AGVs is 0.7 m/s, while pick and drop actions take an average amount of time of 5 s.
Infrastructure. For the tests, we used an AGV simulator [
Metrics. Every simulation was run for 200.000 timesteps, corresponding to approximately 4 hours real time, i.e. one timestep represents 20 ms in real time. All test results displayed in the paper are average values over 20 simulation runs. Performance is measured in terms of throughput (number of finished transports as a function of simulated timesteps) and reaction time (average waiting time per transport as a function of simulated timesteps). Additionally, the amount of communication needed is measured (number of messages sent per transport).
Reference Algorithms. We compared DynCNET with standard CNET and FiTA. With CNET each transport that enters the system is assigned as soon as possible to the most suitable AGV, i.e., an idle AGV for which the cost to reach the pick location is minimal. When transports can not be assigned immediately, they enter a waiting status. All waiting transports are ordered by priority, and this priority determines the order in which transports are assigned. With FiTA, AGVs combine fields that guide them toward pick locations of transports. Transport agents emit fields that attract idle AGVs. The strength (and thus the range) of the fields of transport agents that attract AGVs depends on the priority of the task and increases over time. The strength of the repulsive fields emitted by the AGVs is fixed.
Parameter Settings. Preceding to the tests, we determined the most suitable set of values for the
parameters of the three tested protocols. Parameter tuning is a labour-intensive job. For most of the parameters, for
FiTA as well as for DynCNET, we were able to determine a range of values from which we could select one
without significantly affecting the performance of the protocol. We suspect that the constrained nature of the
problem (such as the restrictions imposed by the layout) accounts for this relaxation. A thorough discussion
of parameter tuning however, is not feasible within the limited space of this paper, for a detailed overview
we refer to [
We have measured communication load, average waiting time, and the number of finished transports. In addition, we have performed a stress test in which AGVs have to handle as quickly as possible a fixed number of transports from a limited number of locations.
Communication Load. To compare the communication load, we have measured the average number of messages sent per finished transport. The left part of Fig. 6 shows the results of the test.
50000
100000 150000 Time of simulation [timesteps] 200000 50000
100000 150000 Time of simulation [timesteps] 200000 The number of messages of DynCNET is approximately the same as for FiTA, while the communication load of CNET is about half of the load of the dynamic mechanisms. However, an important difference exists between the type of messages sent. Fig. 7 summarizes the number of unicast and broadcast messages sent by the three mechanisms.
For CNET, more than 90 % of the communication are unicast messages. For DynCNET the balance unicast–broadcast messages is about 75–25, yet, for the field-based approach this balance is about 25–75, thus the opposite. This difference is an important factor for selecting appropriate communication infrastructure for a particular task assignment mechanism and vice versa.
Average Waiting Time. The left part of Fig. 6 shows the test results for average waiting time for transports. Average waiting time is expressed as the number of timesteps a transport has to wait before an AGV picks up the load. After a transition period (around 20.000 timesteps), DynCNET outperforms CNET. The difference increases when time elapses. On the other hand, FiTA is slightly better than DynCNET over the full test
CNET DynCNET Field-based
CNET DynCNET Field-based
16000 range. A possible explanation is that idle AGVs in FiTA immediately start moving when they sense a field of a task, while in DynCNET AGVs only start moving after they are provisionally accepted as a winner. The fact that DynCNET is not able to outperform FiTA came as a surprise to us. Since every aspect in DynCNET is explicitly specified, we expected that if fine tuned well DynCNET could perform better than FiTA. Number of Finished Transports. The right part of Fig. 8 shows the number of transports finished by each of the protocols during the test run.
600 500 s t rpo 400 s n a r tde 300 h s i inF 200 100 0
CNET DynCNET Field-based
CNET DynCNET
Field-based 50 40 s tr o p rsan 30 t d e h iisnF 20
10 50000
100000 150000 Time of simulation [timesteps] 200000 The results confirm the measures of the average waiting time per finished transport. DynCNET handles more transports than CNET, but less than the field-based protocol. After four hours in real-time, CNET has handled 380 transports, DynCNET has handled 467 transports, and the field-based approach 515 transports. For the 467 executed transports of DynCNET, we measured an average of 414 switches of transport assignments performed by transport agents and AGV agents.
Stress Test. In addition to the standard transport test profile, we have performed a stress test in which 45 transports are created at a limited number of locations in the beginning of the test. These transports have to be dropped at a particular set of destinations. The test simulates for example the arrival of a truck with loads that have to be distributed in a warehouse. The task of the AGVs is to bring the loads as quickly as possible to the right destinations. The transport test profiles for the three mechanisms was identical. The left part of Fig. 8 shows the test results.
The slopes of the curves of FiTA and DynCNET are similar but much steeper than the curve of CNET. The results demonstrate that CNET requires about 2.5 times more time to complete the 45 transports than the dynamic protocols.
In the stress test, the communication load of FiTA is slightly higher as for DynCNET during the full test. In the initial phase of the test, the dynamic protocol requires much more bandwidth as CNET (about factor four), later the difference converges to the difference we have measured for the standard test profiles (about factor two).
Variance. The tests we have discussed are non-deterministic. Orders are generated randomly and priorities
are assigned randomly. To verify the statistic significance of the mean values of the test results we have
calculated the 95 % confidence interval [
DynCNET outperforms CNET on all performance measures, the cost is a doubling of required bandwidth. Contrary to our expectations, DynCNET is in general not able to outperform FiTA. At best DynCNET is able to equal the performance of FiTA. Fig. 9 compares several quality attributes and engineering aspects of the three mechanisms.
Flexibility and Openness. Both DynCNET and FiTA support flexible assigning of tasks with delayed commencement. In FiTA, the choices of the participant agents are implicitly determined by the combination of the sensed fields. DynCNET provides explicit points of choice for initiators and participants. Both DynCNET and FiTA support openness during delayed commencement, i.e. both mechanisms allow initiators to take into account new participants that become available and participants can participate in the assignment of new tasks that become available. Whereas FiTA inherently supports openness (the combination of fields adapts when fields disappear or new fields appear), the DynCNET protocol includes explicit functions that notify initiators and participants when changes occur. Neither flexibility, nor openness is supported by CNET.
Robustness. In FiTA, the freshness of the received fields is taken into account to determine the attraction
and repulsion of fields. When an agent misses an update of a field due to the loss of a message, the previous
value of the field is used. Yet, to determine the combined field that guides the agent, less importance is given
to older field values. As such, FiTA is (to some degree) robust to message loss. CNET and DynCNET on
the other hand fail when a message gets lost and the prescribed sequence of messages is disrupted. As such,
the contract-net based mechanisms require additional support for robustness to message loss.
Mechanism Engineering. No common engineering approaches are available for the design and development
of FiTA. On the other hand, DynCNET allows to specify the behavior of the agents by means of common
engineering diagrams such as interaction diagrams and state charts. We used UniMod [
Type of Communication. A significant difference exists in the ratio unicast–broadcast messages that are used in the three task assignment mechanisms. This difference is important for selecting appropriate communication infrastructure for a specific task assignment mechanism and vice versa. Further research is needed to investigate the implications of the type of communication of the different mechanisms. 5
Task assignment is an extensive domain of research. Here we focus on mechanisms that are based CNET.
CNET is a widely known and extensively used protocol that uses an auction-like mechanism to achieve
task assignment. CNET was originally proposed by Smith and Davis [
Several extensions of CNET exist that support m £ n negotiations. [
The protocol in [
FIPA proposes the Iterated CNET protocol, allowing multi-round iterative bidding [
Related to the Iterated CNET protocol are levelled-commitment contracts [
Finally, there are several researchers who use the original CNET protocol in combination with other
strategies to provide support for dynamism. Maturana et al. [
The work presented in this paper is part of an ongoing effort to study suitable task assignment mechanisms for decentralized MAS. Our focus in on the assignment of tasks with delayed commencement. In previous work, we studied two mechanisms for task assignment: standard CNET and FiTA, a field based approach for task assignment. In this paper, we presented the DynCNET protocol, an extension to standard CNET that supports dynamic task assignment.
We compared DynCNET with CNET and FiTA in a real-world test setting. DynCNET (as FiTA) outperforms CNET on all performance measures. The cost is a doubling of required bandwidth. However, contrary to suggestions made by engineers and colleague researchers, extending standard CNET to take dynamism and change into account is not obvious. Enabling the agents to switch the assignment of tasks increases the complexity of the protocol significantly.
Our experiences with DynCNET with FiTA yield the following conclusions: ² Contrary to our expectations, DynCNET was not able to outperform FiTA, both mechanisms have similar performance characteristics. ² Parameter tuning for DynCNET has similar complexity as for FiTA. ² Whereas FiTA is inherently robust to message loss, DynCNET is not and requires additional functionality to deal with message loss. ² FiTA mainly uses broadcast messages, while DynCNET mainly uses unicast message. ² DynCNET explicitly defines the task assignment process among the agents while in FiTA everything is implicitly enclosed in the fields.
Egemin, our partner in the EMC2 project, currently considers to apply an agent-based approach for task assignment in one of its AGV transportation systems. Due to the explicit specification of the protocol the engineers tend to prefer DynCNET over FiTA. The fact that DynCNET allows engineers to reason on the assignment of tasks may be of overriding importance in the selection of a mechanism for task assignment in practice. Still, extensive tests are necessary before an eventual decision can be made.
DynCNET is a promising protocol for task assignment in decentralized MAS. Yet, before any claim can be made about its general applicability, the protocol needs further tests in different application domains.