Now we experimentally evaluate the use of summary information in planning and coordination for three different domains: an evacuation domain, the manufacturing domain described in Section 1.1, and a multi-rover domain. In these domains, we define performance in different ways to show a range of benefits that abstract reasoning offers.
We evaluate the algorithm described in Section 5.1. Our implementation orders search states in the queue such that those generated by synchronization operators precede those generated by expansion and selection operators. Thus, before going deeper into a part of the hierarchy, the implementation of the algorithm explores all orderings of the agents' plans before digging deeper into the hierarchy. Investigating heuristics for choosing between synchronization and decomposition operators is a topic for future research.
In the next section we report experiments for an evacuation domain that show how abstract reasoning using summary information can find optimal coordination solutions more quickly than conventional search strategies. Optimal solutions in the evacuation domain have minimal global execution times because evacuees must be transported to safety as quickly as possible. In Section 7.2, we show that summary information improves local search performance significantly when tasks within the same hierarchy have constraints over the same resource, and when solutions are found at some level of abstraction. We also evaluate the benefits of using the CFTF and EMTF heuristics for iterative repair and show where summary information can slow search.
In some domains, computation time may be insignificant to communication costs. These costs could be in terms of privacy for self-interested agents, security for sensitive information that could obtained by malicious agents, or simply communication delay. In Section 7.3, we show how multi-level coordination fails to reduce communication delay for the manufacturing domain example but, for other domains, can be expected to reduce communication overhead exponentially.