Effects of Various Coordination Strategies on Coordination Computation, Communication and Reliability

A Simple Dynamic Multi-agent Domain

In this domain,there are two agents A and B who are tasked with transporting evacuees from unsafe nodes to certain safe nodes (see Figure 1). Agent A (colored red in the simulation), initially at node 1, has to transport evacuees from nodes 2, 6, and 5 (unsafe nodes) to node 1 (safe node). Agent B (colored blue in the simulation) initially at node 7, has to transport evacuees from nodes 4, 3, and 8 (unsafe nodes), to node 7 (safe node). The edges between the nodes represent links that the agents can use to move between nodes. Dashed edges represent links that must be destroyed by one of the agents after it has used that link for transporting the evacuees. Specifically, A is tasked with destroying links (2,6) and (6,5), while B is tasked with destroying link (3,6). Only one agent can traverse a link at a given time, but nodes are large enough to hold both A and B. Agents A and B are capable of two kinds of primitive actions. The first kind is called MOV and it is used to transport evacuees between two nodes. MOV(Q,X,Y) is used to denote the transport of evacuees by agent Q from node X to node Y along the link connecting them. The other action called MOVD is used to effect a MOV and then destroy the link that was traversed.

The Agents' Plans

We assume, at the outset, that the agents know enough about the topology of their environment to formulate several alternative plans (routes that allow them to collect their evacuees and destroy their assigned links). The reason why an agent would want alternative plans is that it could be the case that some of the links are unusable, but it will not know this until it arrives at a node connected to that link. For example, if A suspects that link (2,6) could be unusable, then it might formulate a conditional plan of the form: first MOV(A,1,2) then if (2,6) is usable (MOVD(A,2,6)< MOVD(A,6,5) < MOV(A,5,1)) else (MOV(A,2,1) < MOV(A,1,5) < MOV(A,5,6) < MOVD(A,6,5) < MOV(A,5,1)) where < denotes precedence. This kind of conditional plan can be captured with a Hierarchical Task Network (HTN) representation as in Figure 2(a), where A's overall plan A-EVAC is comprised of the first move A12 (the primitive actions an agent can execute directly are shaded) followed by some plan to evacuate from 6 and 5 (A-EVAC-6-5). A-EVAC-6-5 can be accomplished either the short way (A-SHORT-EVAC) along the route 2-6-5-1, or the long way (A-LONG-EVAC) with route 2-1-5-6-5-1. Similarly, if B suspects link (3,6), it could have the HTN plan in Figure 2(b).

From the HTNs for A and B, it is clear that they have to coordinate their tasks. One scenario which can arise if they do not coordinate is the following: Assume that A, having evacuated from node 2, traverses link (2,6) and destroys it on its way to node 6. B, having reached node 3, discovers that link (3,6) is unusable. It then has to fall back on its ``longer'' evacuation route B-LONG-EVAC, but it will fail in its mission because link (2,6) was already destroyed by agent A. This situation could have been averted if agent A had waited until agent B had committed itself to a specific route on its way to node 8. The tradeoff that is possible here is between an efficient simultaneous joint plan (A and B both evacuate via their shorter routes) with some probability of failure (when link (3,6) is unusable) and a less efficient but more robust joint plan (A sits idle at 2 until B chooses its route) which can tolerate the lack of link (3,6) without causing B to fail. It is the task of the distributed coordination process to discover the potential for conflict and tradeoffs in this situation and resolve it in an acceptable fashion.

Brief Overview of Approach

The Applet and User Controls

• Event Window: The event window has five buttons at the top for each of the five cases described below. Below the buttons, there is a scrollable window which displays event information at runtime. The events represent the reception of various communication messages used by the coordinator and the task agents during the incremental coordination process. Examples of such messages include requests for abstract plan refinements and plan synchronization messages. Each line in this window gives the time of the event, the agent servicing that event and a brief description of the event. Below this window, there is a panel which lists all the agents in the system and two different time measures: the time spent executing plans and the time spent waiting for the coordination agent to analyze and coordinate plans as well as the time spent by the agents waiting for synchronization messages. A check box is provided to step through the simulation one event at a time.
• Simulator Window: The simulator window graphically depicts the movement of the agents and the evacuees in the system. A slider is provided to adjust the rate of the simulation and the Continue/Pause button can be used to pause the simulation and resume it. The window also displays various simulation statistics such as the elapsed time, the number of evacuees remaining to be evacuated and the number of moves made by the various transporting agents.

The applet is slow to load up. Please allow it half a minute after it has downloaded. Two windows will appear. Nothing happens in the box below.

Five Scenarios

• Scenario 1 (Negligible Coordination): In this scenario, the agents serialize their plan executions such that agent B executes its plan completely, before agent A begins executing its plan. There is negligible coordination or communication involved in this scenario (agent B signals agent A after it is done) but this comes at the expense of execution inefficiency which is reflected in the task completion times.
• Scenario 2 (Failure Recovery): This scenario is the same as 1, except that link (3,6) is rendered unusable after B has started executing its plan but before it has reached node 3. However, since B has the option of using its alternative evacuation plan, it is able to successfully complete its evacuation. Thus it was able to recover from the failure of its preferred plan (the short evacuation plan) at the expense of some execution inefficiency (due to serialization of the agents' plans).
• Scenario 3 (Maximum Concurrency with Plan Selection) : In this scenario, B's plan execution is overlapped with A's execution. The coordinator proposes that B commit to its short evacuation route before B can reach node 3 and decide which evacuation plan to employ. This strategy maximizes concurrency (no synchronization is required) and there is no coordination or communication overhead but trades off reliability (see scenario 4).
• Scenario 4 (Failure due to Premature Plan Selection) : This scenario is the same as 3, except that link (3,6) is rendered unusable after B has started executing its plan but before it has reached node 3. Since B has committed to the shorter route, it cannot evacuate from node 8 as A has rendered its alternative route unusable by destroying (2,6). Thus the strategy for maximizing concurrency has back-fired due to the runtime failure of link (3,6).
• Scenario 5 (More Concurrency with Plan Synchronization) : In this scenario, the coordinator interleaves coordination with plan execution. The plan of agent B is overlapped with that of A by carefully synchronizing their actions without committing to the premature plan selection strategy in Scenario 4. Specifically, the coordinator waits until agent B is sure of its plan for evacuating from node 8, before it decides how the agents must be coordinated. This allows agent B to cope with the dynamic failure of link (3,6) and complete its task successfully. The increased reliability and concurrency comes at the expense of some coordination and communication overhead.

The execution times and the waiting times (for plan synchronization, coordination etc.) for the three agents A, B and C (Coordination agent) are summarized below.