Search reduction in hierarchical distributed problem solving
dc.contributor.author | Montgomery, Thomas A. | en_US |
dc.contributor.author | Durfee, Edmund H. | en_US |
dc.date.accessioned | 2006-09-08T20:46:05Z | |
dc.date.available | 2006-09-08T20:46:05Z | |
dc.date.issued | 1993-09 | en_US |
dc.identifier.citation | Montgomery, Thomas A.; Durfee, Edmund H.; (1993). "Search reduction in hierarchical distributed problem solving." Group Decision and Negotiation 2(3): 301-317. <http://hdl.handle.net/2027.42/42828> | en_US |
dc.identifier.issn | 0926-2644 | en_US |
dc.identifier.issn | 1572-9907 | en_US |
dc.identifier.uri | https://hdl.handle.net/2027.42/42828 | |
dc.description.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. | en_US |
dc.format.extent | 1173531 bytes | |
dc.format.extent | 3115 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | text/plain | |
dc.language.iso | en_US | |
dc.publisher | Kluwer Academic Publishers; Springer Science+Business Media | en_US |
dc.subject.other | Economics / Management Science | en_US |
dc.subject.other | Operation Research/Decision Theory | en_US |
dc.subject.other | Abstraction | en_US |
dc.subject.other | Coordination | en_US |
dc.subject.other | Distributed Artificial Intelligence | en_US |
dc.subject.other | Multiagent Systems | en_US |
dc.subject.other | Planning | en_US |
dc.subject.other | Search | en_US |
dc.title | Search reduction in hierarchical distributed problem solving | en_US |
dc.type | Article | en_US |
dc.subject.hlbsecondlevel | Urban Planning | en_US |
dc.subject.hlbsecondlevel | Management | en_US |
dc.subject.hlbsecondlevel | Economics | en_US |
dc.subject.hlbsecondlevel | Business (General) | en_US |
dc.subject.hlbtoplevel | Social Sciences | en_US |
dc.subject.hlbtoplevel | Business | en_US |
dc.description.peerreviewed | Peer Reviewed | en_US |
dc.contributor.affiliationum | Department of Electrical Engineering and Computer Science, University of Michigan, 48109, Ann Arbor, Michigan | en_US |
dc.contributor.affiliationother | Scientific Research Laboratory, Ford Motor Company, P.O. Box 2053, MC #2036, 48121-2053, Dearborn, MI | en_US |
dc.contributor.affiliationumcampus | Ann Arbor | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/42828/1/10726_2005_Article_BF01384251.pdf | en_US |
dc.identifier.doi | http://dx.doi.org/10.1007/BF01384251 | en_US |
dc.identifier.source | Group Decision and Negotiation | en_US |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.