Verteilte Künstliche Intelligenz - Uni Ulm WS95/96
8 Planen in Multiagentensystemen
* Grundlagen Planen: Hierarchisch....
* Planen : reaktiv, bereichsabhängig und unabhängig
* Spezielle Anforderungen an Planen in Multiagentensysteme
* Robin Hood trifft Little John
* Verhandlungen in der Plangenerierung (Beispiel)
Literatur: Grundlagen der KI (Vorlesung), S.Russell, P. Norvig: Artificial Intelligence a Modern Approach, Prentice Hall, 335ff., 1995. J. Müller, Verteilte Künstliche Intelligence, Methoden und Anwendungen, Wissenschaftsverlag, Mannheim, 1993, 92-132.
8.1 Planung / Hierarchisch, partiell
Erinnerung: Grundlagen der KI: Planen als die Auswahl von Aktionen, die zu einem gewünschten Ziel führen....
Repräsentation von Zuständen und Zielen:
* Konjunktion von Prädikaten über Konstanten (ev. negiert)
Repräsentation von Aktionen
* STRIPS-Operatoren bestehen aus 3 Komponenten, action-description, precondition und effect
Situationsraum und Planungsraum
* viele Verfahren suchen durch den Raum der Situationen (als progression oder regression Planer),
* andere hingegen durch den Raum der Pläne, gegeben einen unvollständigen Plan (einen partiellen Plan), Ziel die Vervollständigung des Planes
Repräsentation eines Planes
* eine Menge von Planschritten, jeder davon stellt einen Operatoren dar.
* eine zeitliche Ordnung (die auch nur partiell sein kann)
* Variablenbindungen
* kausale Beziehungen, die den Zweck der einzelnen Planschritte festhalten.
Planer für die reale Welt
* hierarchischer Aufbau - ermöglicht häufig erst die Erstellung von Plänen (Berechnungsaufwand), auch besser verständlich
* komplexe Bedingungen erfordern ausdrucksstärkere Sprache
* Zeit: explizite Berücksichtigung von Zeit ist notwendig
* Ressourcen bilden weitere Constraints
8.2 Planen - Reaktiv /Deliberativ.....
* Planen traditionell (oder auch bereichsunabhängig, Planen als Programm) ist modellbasiert, d.h. es findet statt auf einem internen (statischen) Modell der Wirklichkeit
Phasen: Plangenerierung und Plan"ausführung" zus. Planüberwachung...
* Bei reaktiven Systemen entstehen sinnvolle Dinge über die Interaktion mit der Umgebung (die selbst dynamisch und komplex ist), d.h. Probleme werden durch das Befolgen einfacher Verhaltensmuster in Einheit mit der Umgebung gelöst, der Fokus der Kontrolle, welche Aktivitäten stattfinden und welche nicht, sind nicht mehr durch den Planer alleine definiert, sondern in die Exekutive umgeleitet. Dieses Planen wird als bereichsabhängig, reaktiv oder kommunikatives Planen bezeichnet.
Frage: welche Rolle spielen die beiden Formen von Planung im menschlichen Alltag?
Planen in der Blockworlds:
Initialer Zustand (I): {ON (C,A), ONTABLE(B), ONTABLE(A), CLEAR(C), CLEAR(B)}
Aktionen: MOVE(x,y,z) für bewege Block x von Block y auf Block z (y und z können sich auch auf den Tisch beziehen)
Zielzustand (G): {ON(B,A), ONTABLE(A), ON(C,B), CLEAR(C)}
MOVE(B,TABLE,A) in STRIPS:
Precondition: {Ontable(B), CLEAR(B), CLEAR(A)}
Add List: {ON(B,A)}
Delete List: {ONTABLE(B), CLEAR(A)}
Given a blocksworld planning problem (I,G) finding a minimal length sequence of moves that leads form I to G is NP hard.
Gupta und Nau, Artificial Intelligence (1991)
Lösung als bereichsabhängiges oder reaktives Planen:
* Falls der Block nicht in seiner Zielposition ist, nicht auf dem Tisch und frei, dann bewege ihn auf den Tisch.
* Falls der Block auf dem Tisch ist, nicht in der Zielposition und die Zielposition ist frei, dann bewege ihn zu der Zielposition.
Die Zielposition bezieht sich darauf, daß die Blöcke "darunter" auch schon in Zielposition sind.
Merke:
Verhaltensregeln des bereichsabhängigen oder reaktiven Planens beziehen sich implizit auf den zu erreichenden Zielzustand, der bei diesen Verfahren als vordefiniert gilt. Ziele sind nicht explizit, sondern implizit in den Verhaltensregeln kodiert: Auswirkung auf Flexibilität eines Systems.
8.3 Planung in MAS
* Überschneidung von Kompetenzräumen:
Mischung aus reaktiven und deliberativen Planen in einer dynamischen Umwelt
Da unterschiedliche Agenten in einer Welt planen und agieren, sind bestimmte Vorraussetzungen, die single-agent Planung betreffen, nicht mehr stichhaltig, d.h. die Welt ändert sich ohne, daß der einzelne Agent etwas tut, d.h. Pläne müssen an dynamische Umgebungen angepaßt werden.
* Generierung von Plänen durch mehrere Agenten
Pläne sind ev. kontraproduktiv in ihrer Gesamtheit, d.h. es treten Ressourcenkonflikte in der Durchführung auf, die erkannt und behoben sein wollen.
* Ausführen von Aufgaben durch mehrere Agenten
Auch die Ausführung der Aufgaben bedeutet je nach Vollständigkeit der Planung auf Unvorhergesehenes gefaßt zu sein.
* Kommunikation bzw. Verhandlung als Integraler Bestandteil
Aufgrund obiger Aspekte und da globales Wissen im allgemeinen nicht vorhanden ist.
Unterscheidung in:
* Zentrales Planen
(Georgeff 83, Lansky 87)
Hier wird der endgültige Plan von einem Agenten konzeptioniert, oder die Sicht der Agenten ist zu sog. Weltsichten erweitert, d.h. die Constraints, die den Plänen zugrundeliegen, sind offen zugänglich.
Georgeff hat ein System entwickelt, in dem Agenten individuell planen und die fertigen Pläne an eine zentrale Einheit schicken, die nach Inkonsistenzen sucht.
* Verteiltes Planen
(Rosenschein et al. 85, Corkill 86, Durfee/Lesser 89)
Das verteilte Planen beruht meistens auf einer vorläufigen Planung der Agenten und der Adaption dieser Pläne entsprechend den Plänen anderer Agenten. So wird in einem Ansatz von Durffee/Lesser jedem Agenten ein lokaler Plan zugeordnet, dieser lokale Plan ist in abstrakter Form in einem Knoten dargestellt, der bei Bedarf an andere Agenten weitergeleitet wird.
Aspekte der MAP
* Zentrales Planes oder Verteiltes Planen
* Aufgabenzentriert oder Agentenzentriert
* Mit/Ohne Zeitliche Constraints (bezgl. des Planes)
* Mit/Ohne Ressourcenkonflikten
* [Altruistisch ... egozentrisch]
Beziehungen zwischen Plänen (nach Martial)
8.4 Robin Hood trifft Little John
Literatur: D.R. Traum, J.F. Allen, Causative Forces in Multi-Agent Planning, MAAMAW 1990, 89-105.
Beispiel für eine Multiagentenplanung mit zwei Agenten und unter Berücksichtigung von Initiatoren und kausalen Kräften, ein Grenzgänge zwischen traditionellen single-agent Planer und einem multi-agenten Planer, deliberativen und reaktiven Planer
Szenario: Zwei Züge (mit Namen Robin Hood und Little John), Gleise, wobei die einzelnen Teilgleise auch Weichen und Puffer enthalten (Puffer: hier bezeichnen das Ende eines Gleises, Weichen sind mit zwei unterschiedlichen Gleisen verbunden)
Effektoren:
(add-power engine power)
Der Zug bewegt sich mit einer Geschwindigkeit proportional zur Power und umgekehrt proportional zu der Anzahl der Wagons
(set-switch switch state)
Setzt die Weiche
(rerail-train car)
Bei Entgleisung wird der Wagon wieder auf das Gleis gesetzt
Perzeption
(get-time)
(get-power engine)
(get-state-of-switch switch)
(get-location car)
(test-derailed car)
(get-object-on-track track)
Robin Hood ist zur Zeit in Nottingham und möchte nach Sherwood, Little John befindet sich in Sherwood auf dem Weg in Richtung Nottingham und ist Robin Hood einfach im Weg (Wir erinnern uns an die leidige Brück). Um einen Zusammenstoß zwischen beiden zu vermeiden, soll geplant werden.
1. Szenario (Level 0 Plan)
Züge und Weichen werden von einem zentralen Planer kontrolliert. Einziger Initiator in diesem Szenario ist der Planer, eine Zustandsbasierte Repräsentation der Welt ist ausreichend, kein Grund Zeit, Geschwindigkeit und andere Aspekte explizit zu berücksichtigen, z.B. in STRIPS.
move-one-space(x:train from-loc:track to-loc:track)
Pre: (at x from-loc)
(adjoined to-loc from-loc)
(clear to-loc)
(not (derailed x))
Delete: (at x from-loc)
Add: (at x to-loc)
Decomposition:
(move-1 x (direction x from-loc to-loc))
gemeinsam mit dem Plan Operator allign-switches (der die Weichen setzt, um aufeinanderfolgende Gleiskörper miteinander zu verbinden) kann ein Plan-Operator höherer Ordnung implementiert werden: move-along-clear-path
Lösung:
(move-along-clear-path john '(sherwood 3 4 5 6 17 18))
(move-along-clear-path robin
'(nottingham 14 13 12 11 10 9 8 7 6 5 4 3 sherwood))
2. Szenario (Level 1 Plan)
Die Züge sind unter der Kontrolle des Planers, jedoch die Weichen werden nach einem festen Schedule gesetzt (d.h. externe Ereignisse sind zu berücksichtigen)
move-one-space(x:train from-loc:track to-loc:track)
Pre: (at x from-loc begin)
(adjoined to-loc from-loc [begin end])
(clear to-loc begin)
(not (derailed x begin))
Effects: (at x to-loc end)
Duration: move-one-time
Decomposition:
(move-1 x (direction x from-loc to-loc begin) begin)
Merke: Die Delete Aktion ist nicht mehr notwendig, da Wahrheitswerte zu bestimmten Zeitpunkten zugeordnet werden.
z.B. in einem Planungssystem wie DEVISER
Zeit Ereignis
8 (set-switch 6 open)
9:30 (set-switch 10 open)
11 (set-switch 6 closed)
12:30 (set-switch 10 closed)
14 (set-switch 6 open)
15:30 (set-switch 10 open)
17 (set-switch 6 closed)
18:30 (set-switch 10 closed)
Lösung als Level 1 Plan:
Zeit Aktion
8:45 (move-along-clear-simple-path john
'(sherwood 3 4 5 6))
10:45 (move-one-space john :from 6 :to 17)
12:15 (move-along-clear-simple-path robin
'(notingham 14 13 12 11 10))
14:45 (move-one-space robin :from 10 :to 9)
15:45 (move-along-clear-simple-path robin
'(9 8 7))
17:15 (move-one-space robin :from 7 :to 6)
17:45 (move-along-clear-simple-path robin
'(6 5 4 3 sherwood))
3. Szenario (Level 2 Plan)
In diesem Szenario wird Robin kontrolliert durch einen Planer, John bewegt sich nach einem fixen Schedule, beide können sich simultan bewegen wobei sie sich gegenseitig beeinflußen, d.h. Aktionen und deren Beziehung zu Ereignissen werden wichtig.
Nun wird die vorher implizite Vorbedingung explizit notwendig:
"
x,y:train,loc:track,t:time (at x loc t) Ÿ x ð y fi(at y loc t)Andere Vorbedingungen:z.B. (clear to-loc begin) sind weder hinreichend noch notwendig...
Aktionen : start und stop
start(x:train d:direction)
Pre: (not (derailed x begin))
(stopped x begin)
Effects: (moving x d end)
Duration: start-time
Decomposition:
(set-power x (dir-fn d))
stop(x:train d:direction)
Pre: (moving x ?dir begin)
Effects: (stopped x end)
Duration: start-time
Decomposition:
(set-power x -(get-power x))
Ereignis: move
move(x:train from-loc:track to-loc:track)
Pre: (moving x ?d:direction begin)
(at x from-loc)
(element (to-loc (next-track from-loc ?d)))
(adjoined to-loc from-loc [begin,end])
(not (derailed x begin))
(not (perform ?x (stop x) [begin, end]))
(clear to-loc begin)
(
Lösung:
John's Planer startet die Aktion
(start john (towards sherwood 3) at time 1000)
condition action
(> (get-time) 1000) (follow-path robin
'(nottingham 14 12 12 11
10 9 8 7 6 5 4 3 sherwood))
(at john 6) (set-switch 6 open)
(at john 22) (set-switch 10 open)
follow path besteht aus move-one und follow-path für den Rest der Strecke, move-one besteht aus start und stop.
Set switch bewirkt, daß Little John auf jedem Fall aus dem Weg ist.
Little John wird gestartet und bewegt sich fortan ohne weitere Aufsicht, Robin folgt einem zusammengesetzten Plan, und die Switches werden reaktiv gesetzt.
Weitere Szenarios beinhalten, daß John und Robin über die Beweggründe und Präferenzen des jeweilig anderen schlußfolgern und danach ihre Bewegungen ausrichten.
Je dynamischer das System ist, und desto mehr Kontrolleure involviert werden, desto wichtiger werden bereichsabhängige Aspekte in der Formulierung der Pläne.
8.5 Verhandlungen und Kommunikation als Integraler Bestandteil Verteilten Planens
Literatur: S.E. Conry, R.A. Mayer, V.R. Lesser, Multistage Negotiation in Distributed Planning, In: Readings in Distributed Artificial Intelligence, 1989, 367-384.
Beispiel Szenario:
Problem das Monitoring und die Kontrolle eines Kommunikationsnetzes, das System besteht aus einer Menge von Einrichtungen, verbunden durch Leitungen, es existieren geographische Subregionen, pro Subregion existiert eine Kontrolleinheit, bei Störungen müssen die Kontrolleinheiten dafür sorgen, daß end-to-end user connectivity (circuits) weiterhin möglich sind, die Kontrolleinheiten sind durch ein separates Netz verbunden, jede Verbindung kann nur zwei circuits verkraften.
Charakteristisch für Multiagentenplanung (MAP):
* das Wissen der einzelnen Agenten ist unvollständig
* generelles Ziel ist die Funktionsfähigkeit des gesamten Netzes aufrechtzuerhalten
|
ckt1 |
(A-1 :L-1 A-2 :L-12 B-1 :L-11 B-2) |
|
ckt2 |
(B-1 :L-11 B-2 :L-10 C-3 :L-5 D-2) |
|
ckt3 |
(E-1 :L-6 C-2 :L-4 C-3 :L-5 D-2 :L-7 D-3) |
|
ckt4 |
(B-1 :L-12 A-2 :l_2 C-1 :L-3 C-2) |
Problem: L-11 ist nicht mehr funktionsfähig, ckt1 und ckt2 sind betroffen
|
g1/p1 |
(A-1 :L-1 A-2 :L-2 C-1 :L-3 C-2 :L-4 C-3 :L-5 D-2 :L-7 D-3 :L-8 D-1 :L-9 B-2) |
|
g1/p2 |
(A-1 :L-1 A-2 :L-2 C-1 :L-3 C-2 :L-4 C-3 :L-10 B-2) |
|
g2/p1 |
(B-1 :L-12 A-2 :L-2 C-1 :L-3 C-2 :L-4 C-3 :L-10 B-2 :L9 D-1 :L-8 D-3 :L-7 D-2) |
|
g2/p2 |
(B-1 :L-12 A-2 :L-2 C-1 :L-3 C-2 :L-4 C-3 :L-5 D-2) |
Jeder der einzelnen Agenten sieht nur Bruchstücke des Planes
|
Ziel |
Planfragment |
Ressourcen |
Kosten |
|
g1 |
1A |
L-1, L-2 |
9 |
|
g2 |
7A |
L-2, L-12 |
9 |
|
g1 |
2B |
L-9 |
9 |
|
g1 |
5B |
L-10 |
6 |
|
g2 |
8B |
L-9, L-10, L-12 |
9 |
|
g2 |
11B |
L-12 |
6 |
|
g1 |
3C |
L-2, L-3, L-4, L-5 |
9 |
|
g1 |
6C |
L-2, L-3, L-4, L-10 |
6 |
|
g2 |
9C |
L-2, L-3, L-4, L-10 |
9 |
|
g2 |
12C |
L-2, L-3, L-4, L-5 |
6 |
|
g1 |
4D |
K-4, L-7, L-8, L-9 |
9 |
|
g2 |
10D |
L-7, L-8, L-9 |
9 |
|
g2 |
13D |
L-5 |
6 |
Planauswahl wird bestimmt durch die Verfügbarkeit lokaler Ressourcen, z.B. Agent B kann gleichzeitig Ziel 1 und Ziel 2 verfolgen, Agent A, C und D können jeweils nur ein Planfragment auswählen. Die Planfragmente und ihre Machbarkeit werden in einem Machbarkeitsbaum gespeichert.
Unterscheidung in p und s Ziele
* p-goals (primary goals): Terminierung des Circuit im Hoheitsgebiet des Kontrolleurs
* s-goals: Verpflichtungen zu anderen Kontrolleuren
Vorgehensweise:
1) jeder Agent analysiert seine p-goals und verpflichtet sich seine am meisten präferierten Planfragmente durchzuführen
2) die Agenten versuchen andere zu überzeugen, Planfragmente abzuschließen, die mit ihren konsistent sind
3) jeder Agent nimmt die von aussen kommende Information auf, Anforderungen für tentative Verpflichtungen werden als aktive s-goals hinzugenommen, Antworten zu eigenen Anforderungen werden in den Machbarkeitsbaum eingetragen
4) Aktive Ziele sind p-goals und s-goals, der Agent bewertet die Handlungsalternativen (hinsichtlich Kosten, Ziele, Konsistenzen usw.) und aktualisiert seine Verpflichtungen, und informiert die Umgebung
5) dieser Prozess (ab 3) setzt sich solange fort bis der Agent über alle möglichen globalen Inkonsistenzen, die aus seinen lokalen Planfragmenten resultieren, informiert ist.
Verwendung eines Contractähnlichen Protokolls.
Fragen:
* Termination: Verhandlungen finden solange statt, solange irgendwelche Aktivitäten anstehen, die der Agent zu lösen hat, oder einkommende Anforderungen und Informationen, Verhandlungsaktivitäten erfordern
* Optimalität: nur im Falle, daß das Problem überspezifiziert ist ("overconstrained" ), müssen p-goals aufgegeben werden, das System versucht in diesem Falle über Verhandlungen soviele p-goals wie möglich zu realisieren.
|
A |
B |
C |
D |
|
1A, OK? -> C |
11B; OK? -> A |
13D; OK? -> C |
|
|
B -> OK? 11B conflict; (11B and not p-goal g1) ->B |
A->OK? 1A match 6C mit 1A und 5B 1A is OK -> A
conflict; (13 D and not g1 via C -> D) |
||
|
C-> 1A is ok |
A -> (11B and not p-goal g1) C-> 5B is OK 8B; OK? -> A |
C -> (13 D and not g1 via C -> D)
10D; OK? -> B |
|
|
B -> OK?8B
conflict; (8B and not p-goal g1) -> B |
D -> Ok? 10D
8B OK? -> C |
||
|
A -> (8B and not p-goal g1)
B weiß, daß g1 and g2 nicht möglich sind
(not both g1 and g2) -> D
|
B -> OK? 8B
conflict; (8B and not g1 via C) -> B |
||
|
C -> (8B and not g1 via C) |
B -> (not both g1 and g2) |
8.6 Zusammenfassung
* Anforderungen (partiell, hierarchisch, Berücksichtigung von Unsicherheiten, usw.) an einen Single-agent Planer in einer dynamischen Welt mit nur unvollständigem Wissen über diese sind Teil der Anforderungen, die typischerweise an einen multi-agenten Planer gestellt werden.
* Kommunikation und Koordination von Plänen sind darüber hinaus integraler Bestandteil der Plangenierung, der Planausführung und der Planüberwachung (auch bei Ansätzen mit einer zentralen Planerinstanz)
* reaktives oder bereichsabhängiges Planen wird um so wichtiger, je dynamischer die Welt um den Planer herum ist (um schnelle Reaktionen zu erlauben) und je realistischer das Gesamtszenario ist.
* reaktives Planen alleine ist jedoch im allgemeinen zu inflexibel, um umfangreichere mentale Fähigkeiten zu modellieren.
