I AM WORKING ON THE CONTENT OF THIS PAGE...

To explore our ideas about the dynamic selection of coordination mechanisms CMs, we developed a scenario, a simple prototype where agents could reason about the selection of a specific CM.

Our scenario takes the form of a grid-world in which some number of autonomous agents (Ai) perform tasks for which they receive units of reward (Ri). Each agent has a specific task (STi) which only it can perform; there are other tasks which require several agents to perform them, called cooperative tasks (CTs). Each task has a reward associated with it. Generally, the rewards for the CTs are higher than those for STs since they must be divided between the coordinating agents.

The agents move about the grid one step at a time, up, down, left or right, or stay still. At any one time, each agent has a single goal, either its ST or a CT over which it is coordinating. On arrival at a square containing its goal, the agent receives the associated reward. In the case of STs, a new one appears, randomly, somewhere in the grid, visible only to the appropriate agent. In the case of CTs, a new one appears, randomly, somewhere in the grid, but this is only visible to an agent who subsequently arrives at that square.

If an agent encounters a CT, en route to its current goal (i.e. its ST), it takes charge of the CT. If several agents arrive at a CT square at the same time, one of them is arbitrarily deemed to be in charge and must decide on both whether to initiate coordination with other agents over this task, and if so which coordination mechanism (CM) it should use. In this context, each agent has a predefined range of CMs at its disposal. Each CM is parameterised by two key attributes: set-up cost (in terms of time-steps) and its chances of success. For example, a CM may take t time-steps to set-up (modelled by the agent waiting that number of time-steps before requesting bids from other agents) and have a probability, p of success (thus when the other agent(s) arrive at the CT square, the reward will be allocated with probability p, with zero reward otherwise). An agent may well decide that attempting to coordinate is not a viable option, in which case it adopts the null CM (meaning the agent rejects adopting the CT as its goal).

The agent-in-charge (AiC) of the coordination selects a CM and, after waiting for the set-up period, broadcasts a request for other agents to engage in coordination. The other agents respond with bids composed of the amount of reward they would require in order to participate in the CT and how many time-steps away from the CT square they are situated.  The next paragraph gives the protocol the agents follow at each time-step; it highlights the specific decisions which have to be made.

1. Each agent arrives at a square. If its goal is attained it receives reward and updates its goal.
2. If the agent finds a CT at the square it becomes AiC and decides to use CM = (t,p), say. If t > 0 it must wait t time-steps then broadcasts a request for coordination.
3. If a request for coordination is received, each agent decides on and submits its bid; if successful it adopts CT as new goal as does the AiC. If no suitable bids arrive, AiC returns to step [2].
4. Each agent decides on its next move according to its current goal and all agents make their move simultaneously.