Abstract
Knoblock and Korf have determined that abstraction can reduce search at a single agent from exponential to linear complexity (Knoblock 1991; Korf 1987). We extend their results by showing how concurrent problem solving among multiple agents using abstraction can further reduce search to logarithmic complexity. We empirically validate our formal analysis by showing that it correctly predicts performance for the Towers of Hanoi problem (which meets all of the assumptions of the analysis). Furthermore, a powerful form of abstraction for large multiagent systems is to group agents into teams, and teams of agents into larger teams, to form an organizational pyramid. We apply our analysis to such an organization of agents and demonstrate the results in a delivery task domain. Our predictions about abstraction's benefits can also be met in this more realistic domain, even though assumptions made in our analysis are violated. Our analytical results thus hold the promise for explaining in general terms many experimental observations made in specific distributed AI systems, and we demonstrate this ability with examples from prior research.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Amdahl, Gene M. (1967). “Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities.” InAFIPS Conference Proceedings. Reston, VA: AFIPS Press, pp. 483–485.
Bacchus, Fahiem, and Qiang Yang. (1991). “The Downward Refinement Property.” InProceedings of the Twelfth International Joint Conference on Artificial Intelligence, Sydney, Australia, Los Altos, CA: Morgan Kaufmann, pp. 286–292.
Bacchus, Fahiem, and Qiang Yang. (1992). “The Expected Value of Hierarchical Problem-Solving.” InProceedings of the National Conference on Artificial Intelligence, San Jose, CA, Boston: AAAI Press, pp. 369–374.
Corkill, Daniel D., and Victor R. Lesser. (1983). “The Use of Meta-level Control for Coordination in a Distributed Problem Solving Network.” InProceedings of the Eighth International Joint Conference on Artificial Intelligence, Karlsruhe, Federal Public of Germany, Los Altos, CA: Morgan Kaufmann, pp. 748–756. Also appeared inComputer Architectures for Artificial Intelligence, Benjamin W. Wah and G.J. Li (eds.), IEEE Computer Society Press, 1986, pp. 507–515.
Davis, Randall, and Reid G. Smith. (1983). “Negotiation as a Metaphor for Distributed Problem Solving.”Artificial Intelligence 20(1), 63–109. Also appeared in Alan H. Bond and Les Gasser (eds.),Readings in Distributed Artificial Intelligence. San Mateo, CA: Morgan Kaufmann, 1988, pp. 333–356.
Durfee, Edmund H., and Thomas A. Montgomery. (1990). “A Hierarchical Protocol for Coordinating Multiagent Behaviors.” InProceedings of the National Conference on Artificial Intelligence, Boston: AAAI Press, pp. 86–93.
Durfee, Edmund H., and Thomas A. Montgomery. (1991). “Coordination as Distributed Search in a Hierarchical Behavior Space,”IEEE Transactions on Systems, Man, and Cybernetics 21(6) (Special Issue on Distributed AI).
Durfee, Edmund H., Victor R. Lesser, and Daniel D. Corkill. (1987). “Coherent Cooperation among Communicating Problem Solvers.”IEEE Transactions on Computers C-36(11), 1275–1291. Also appeared in Alan H. Bond and Les Gasser (eds.),Readings in Distributed Artificial Intelligence. San Mateo, CA: Morgan Kaufmann, 1988, pp. 268–284.
Gustafson, John L. (1988). “Reevaluating Amdahl's Law.”Communications of the ACM 31(5), 532–533.
Knoblock, Craig A., Josh D. Tenenberg, and Qiang Yang. (1991). “Characterizing Abstraction Hierarchies for Planning.” InProceedings of the National Conference on Artificial Intelligence, Anaheim, CA, July, Boston: AAAI Press.
Knoblock, Craig A. (1991). “Search Reduction in Hierarchical Problem Solving.” InProceedings of the National Conference on Artificial Intelligence, Anaheim, CA, July. Boston: AAAI Press.
Korf, Richard E. (1987). “Planning as Search: A Qualitative Approach.”Artificial Intelligence 33(1), 65–88.
Montgomery, Thomas A., and Edmund H. Durfee. (1990). “Using MICE To Study Intelligent Dynamic Coordination.” InProceedings of the Tools for Artificial Intelligence Conference, Washington, DC, November.
Montgomery, Thomas A., and Edmund H. Durfee. (1992). “Search Reduction in Hierarchical Distributed Problem Solving.” InProceedings of the 1992 Distributed AI Workshop, Glen Arbor, MI, February.
Newell, A., and H.A. Simon. (1972).Human Problem Solving. Prentice Hall.
Parunak, H. Van Dyke. (1992). “How To Describe Behavior Space.” InProceedings of the 1992 Distributed AI Workshop, Glen Arbor, MI, pp. 303–316.
Sacerdoti, Earl D. (1973). “Planning in a Hierarchy of Abstraction Spaces.” InProceedings of the Third International Joint Conference on Artificial Intelligence, Los Altos, CA: Morgan Kaufmann, pp. 412–422.
Stefik, Mark. (1981). “Planning and Meta-Planning (MOLGEN: part 2).”Artificial Intelligence 16, 141–170.
Author information
Authors and Affiliations
Additional information
This research has been sponsored, in part, by the National Science Foundation under grants IRI-9015423 and IRI-9010645, by the University of Michigan Rackham Graduate School, and by a Bell Northern Research Postgraduate Award.
Rights and permissions
About this article
Cite this article
Montgomery, T.A., Durfee, E.H. Search reduction in hierarchical distributed problem solving. Group Decis Negot 2, 301–317 (1993). https://doi.org/10.1007/BF01384251
Issue Date:
DOI: https://doi.org/10.1007/BF01384251