A Case Study in Distributed Planning for Autonomous Cooperating Agents

Abstract

A distributed solution is appropriate for many planning and search problems where large search spaces occur. These search spaces often cannot be bounded with adequate global heuristics, so “traditional” strategies may become very expensive. We show that a distributed setting, where problem knowledge and information about the domain is decomposed among individual entities, can cope with such snags in a natural way. Simple local heuristics suffice to achieve good global solution. This thesis gives an overview about the basic methodology of Distributed Artificial Intelligence. In order to clarify the intentions a larger sample scenario will be discussed in detail, a distributed realization of the “Towers of Hanoi” puzzle. The results support the feasibility of this approach.

Viele Planungs- und Suchprobleme mit riesigen Suchräumen können verteilt angemessener gelöst werden. Oftmals ist es nicht möglich, diese Suchräume mit globalen Heuristiken zu beschränken, weshalb „traditionelle“ Strategien sehr kostenintensiv werden können. Wir zeigen, daß ein verteilter Zugang in natürlicher Weise Abhilfe schaffen kann. Hierzu wird das Problemlösungswissen und die Informationen über die Problemwelt verteilt auf einzelne Bestandteile des Szenarios. Einfache lokale Heuristiken genügen, um eine gute globale Lösung zu erreichen. Diese Arbeit gibt zunächst einen Überblick über die grundlegenden Begriffe und Methoden der „verteilten Künstlichen Intelligenz“. An der Realisation eines verteilten „Türme von Hanoi“-Spiels sollen die ldeen dann klargemacht werden. Die Ergebnisse untermauern die Eignung dieses Ansatzes.