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. In order to run this applet, you will need the Java Plug-in for running Java 1.1.x applets. If you have problems, you can look at an older web page that has links to applets that do not need the plug-in.

This applet makes use of a NEO simulator we are developing to experiment with coordination algorithms on evacuation problems.

The evacuation problem is the same as the one described for the picture on this page's parent.

The top-down search algorithm almost immediately finds simple ways to coordinate the plans at a high level in the plan hierarchies. (Press the "High Level" button.) By agreeing to let the orange transport visit the nodes before the red transport, they avoid the potential conflicts of a collision at the center cluster of locations and of trapping the orange transport in the lower part of the graph.

The red transport can traverse the clusters of nodes clockwise or counterclockwise. The orange transport can move also visit clusters clockwise or counterclockwise but has an additional plan to go clockwise out to the middle and then retrace back counterclockwise. This latter choice avoids all conflicts with the red transport's plan. At a mid level in the hierarchies where these subplan choices exist, the top-down search algorithm finds that the solution with the shortest completion time is the global plan where red moves clockwise and orange chooses the "retrace" subplan. No synchronization is needed since conflicts were resolved by subplan choices. This is shown by pressing the "Mid Level" button.

While the retrace subplan for the orange transport obtains great concurrency with no need for synchronization, going back through the lower right cluster takes longer than going clockwise up to the upper right cluster. At the primitive level in the hierarchies, the top-down search algorithm finds the solution with the shortest completion time (for all levels). This is where the red transport goes counterclockwise; the orange transport goes clockwise; and the red transport follows the orange transport through the middle cluster. (Press the "Low Level" button.) Although synchronization is needed to avoid conflicts, as long as the orange transport is not delayed at any point in executing its plan, the red transport will not have to wait on the orange transport. Thus, both transports can execute their individually most efficient plans and potentially avoid waiting.

The table below shows the computation and execution times for the solutions found at the three levels searched. The following graph shows how the total cost changes when the importance (cost) of computation time versus execution time is varied. We find that when the cost of execution is very high (the ratio is near zero), coordinating at the primitive level is least costly. When the computation cost is much greater, the lowest cost strategy is to coordinate at a high level. However, there is also a range of cost scenarios where coordinating at a mid level is the best strategy.

Level	Computation time	Execution time
High	128	290
Mid	248	184
Low	2153	166