Verteiltes Problemlösen

Verteiltes Problemlösen untersucht, wie ein Problem von mehreren Agenten gelöst werden kann, wobei jeder Agent einen Teil der Informationen oder der Verantwortung besitzt und die Agenten kommunizieren und ihre Teilergebnisse zu einer globalen Lösung kombinieren.

Definition

Verteiltes Problemlösen ist die kooperative Lösung eines Problems durch eine Gruppe von Agenten, von denen jeder über lokales Wissen oder Teilprobleme verfügt und die sich durch Kommunikation koordinieren, um eine kohärente Gesamtlösung zu erzeugen.

Scope

Dieses Thema behandelt kooperatives Problemlösen über Agenten hinweg, die keine zentrale Steuerung teilen: Aufgaben- und Ergebnisverteilung, verteiltes Constraint-Satisfaction und -Optimierung (DCSP/DCOP) mit Algorithmen wie asynchronem Backtracking sowie die Koordination von Teillösungen unter Kommunikations- und Datenschutzbeschränkungen. Es befasst sich damit, wie Zerlegung, lokale Berechnung und Nachrichtenübermittlung zu global konsistenten Lösungen führen. Rein kompetitive Interaktion und Anreizgestaltung werden unter Spieltheorie und Mechanismusdesign behandelt.

Core questions

• Wie wird ein Problem zerlegt und unter Agenten mit partiellen Ansichten verteilt?
• Wie tauschen Agenten Aufgaben und Zwischenergebnisse aus, um eine globale Lösung zu erstellen?
• Wie wird ein Constraint-Problem gelöst, wenn Variablen und Constraints über Agenten verteilt sind?
• Wie werden Kommunikationskosten und lokale Autonomie gegen die Lösungsqualität abgewogen?

Key concepts

• Problemzerlegung
• Aufgabenteilung und Ergebnisverteilung
• verteiltes Constraint-Satisfaction (DCSP)
• verteilte Constraint-Optimierung (DCOP)
• asynchrones Backtracking
• Nachrichtenübermittlung
• lokale Autonomie und Datenschutz
• globale Konsistenz

Key theories

Verteiltes Constraint-Satisfaction und -Optimierung

Verteiltes Constraint-Satisfaction (DCSP) und -Optimierung (DCOP) verallgemeinern Constraint-Probleme auf Szenarien, in denen Variablen und Constraints von verschiedenen Agenten gehalten werden, gelöst durch Algorithmen, bei denen Agenten asynchron Wertzuweisungen und Konfliktinformationen austauschen.

Aufgabenteilung und Ergebnisverteilung

Kooperatives verteiltes Problemlösen erfolgt durch Zerlegung und Verteilung von Aufgaben sowie durch den Austausch von Teilergebnissen, die Agenten integrieren, wodurch eine Gruppe Probleme lösen kann, die kein einzelner Agent allein lösen könnte.

Asynchrone verteilte Suche

Algorithmen wie asynchrones Backtracking ermöglichen es Agenten, ohne zentrale Steuerung nach einer konsistenten globalen Zuweisung zu suchen, indem sie priorisierte Nachrichtenübermittlung verwenden, um Konflikte zu lösen und gleichzeitig die lokale Autonomie zu wahren.

Clinical relevance

Verteiltes Problemlösen findet Anwendung in der Multi-Sensor-Überwachung und -Verfolgung, bei der verteilten Terminplanung und Besprechungskoordination, im Stromnetz- und Verkehrsmanagement sowie in allen Situationen, in denen Daten oder Verantwortlichkeiten natürlich auf Agenten verteilt sind, die gemeinsam eine konsistente Lösung finden müssen, während die Kommunikation begrenzt wird.

History

Kooperatives verteiltes Problemlösen war ein Gründungsthema der verteilten KI, exemplarisch dargestellt durch die Arbeiten der 1980er Jahre zu verteilten Sensornetzwerken und Blackboard-Systemen. Yokoo und Kollegen formalisierten das verteilte Constraint-Satisfaction in den 1990er Jahren, und die verteilte Constraint-Optimierung entwickelte sich später zu einem wichtigen Rahmenwerk für kooperative Multi-Agenten-Entscheidungsfindung.

Key figures

• Edmund H. Durfee
• Victor R. Lesser
• Makoto Yokoo
• Daniel D. Corkill

Seminal works

• yokoo1998
• durfee1989

Frequently asked questions

Wie unterscheidet sich verteiltes Problemlösen von parallelem Rechnen?

Paralleles Rechnen teilt ein Problem typischerweise unter zentraler Steuerung auf Prozessoren auf, um schneller zu sein. Verteiltes Problemlösen geht von autonomen Agenten mit eigenem lokalem Wissen und möglicherweise Datenschutz- oder Kommunikationsbeschränkungen aus, sodass die Herausforderung in der Koordination und dem Erreichen einer kohärenten Lösung liegt, nicht nur in der Geschwindigkeit.

Was ist ein verteiltes Constraint-Optimierungsproblem?

Es ist ein Constraint-Problem, bei dem die Variablen und Constraints verschiedenen Agenten gehören und die Agenten kooperativ Werte zuweisen müssen, um ein globales Ziel (wie die Minimierung der Gesamtkosten) zu optimieren, während sie nur lokal kommunizieren. Es modelliert viele kooperative Koordinationsaufgaben zwischen Agenten.