It is theorized that the process of coordination is a distributed search through a hierarchical space of agent behaviors. By specifying agent activities along multiple dimensions and at different levels of abstraction, the hierarchical behavior space provides a single, rich representation that agents can use to organize, plan, and schedule their collective actions. Agents couple a distributed search protocol with local search algorithms in order to hypothesize new combinations of behaviors that satisfy performance metrics. Agents can employ control heuristics to guide their search. A computational instance of the authors' evolving theory, which implements a particular choice of distributed protocol, local algorithm, metrics, and heuristics, as applied to resolving resource conflicts in an unstructured delivery domain, is described. In this domain, agents that initially do not know with whom they might interact exploit the hierarchical behavior representation to selectively exchange more details about themselves until they can resolve conflicting behaviors. It is experimentally demonstrated how the authors' hierarchical protocol and multidimensional representation provide powerful and practical mechanisms for coordinating these agents, and important research issues to be addressed in the authors' ongoing work are highlighted.
