strips

KI-Planung mit STRIPS

Dieses Projekt ist eine Demo der Verwendung der Strips der automatisierten Planungsbibliothek für künstliche Intelligenz in node.js.

Probieren Sie es online unter https://stripsfiddle.meteorapp.com aus

 npm install strips

Wenn Sie neu bei der automatisierten Planung von STRIPS sind, finden Sie hier ein großartiges Tutorial, das Ihnen den Einstieg erleichtert.

Beispiele

Die folgenden Beispiele zeigen, wie man Planungsprobleme löst, indem man die optimalen Maßnahmen zur Erreichung eines Ziels ermittelt. Beispielsweise können Stapelblöcke, Türme von Hanoi und sogar Starcraft von der KI gelöst werden (siehe unten, es ist ziemlich nett!).

In diesem Projekt sind mehrere Beispiele aus dem Bereich Blocks World enthalten, in denen die KI in der Lage ist, die Reihe von Schritten zum Bewegen und Stapeln von Blöcken auf einer Reihe von Tischen erfolgreich zu planen.

Bei der KI-Planung wird eine einfache Domäne mithilfe eines PEG.js-Grammatikblatts verarbeitet und das Ergebnis mithilfe eines einfachen STRIPS-Problems ausgeführt.

Die Domänen- und Problem-PDDL-Dateien werden über PEG.js analysiert, wodurch ein JSON-Objekt für eine bestimmte Domäne erstellt wird. Der JSON-Code wird dann verarbeitet, um anwendbare Aktionen innerhalb eines bestimmten Problemzustands zu identifizieren. Die Aktionen werden dann auf den aktuellen Zustand angewendet, wodurch eine neue Reihe von Zuständen entsteht. Dieser Prozess wird wiederholt, wenn anwendbare Maßnahmen für die neuen Zustände identifiziert, angewendet und weitere neue Zustände erzeugt werden. Der resultierende Baum möglicher Zustände und Aktionen kann dann mit dem A*-Algorithmus durchlaufen werden, um einen optimalen Satz von Schritten zum Erreichen des im Problem spezifizierten Zielzustands zu finden.

Beispielablauf eines Programms

• Beginnen Sie mit dem Ausgangszustand.
• Identifizieren Sie gültige Aktionen für den aktuellen Status.
• Wenden Sie Aktionen auf den aktuellen Status an, um untergeordnete Status zu erstellen.
• Wiederholen, bis der Zielzustand gefunden ist.

Beispiel blockiert Weltprobleme

Domäne | Problem Verschieben Sie die Blöcke a, b von Tisch x nach Tisch y. Auf einer Tabelle sind mehrere Blöcke zulässig. Die einzige verfügbare Aktion ist „Verschieben“.

Domäne | Problem Verschiebt die Blöcke a, b von Tisch x auf einen Stapel ab auf Tisch y. Auf einer Tabelle sind mehrere Blöcke zulässig. Zu den verfügbaren Aktionen gehören „Verschieben“, „Stapeln“ und „Entstapeln“.

Domäne | Problem Entstapelt Blöcke ba von Tisch x auf einen Stapel ab auf Tisch y. Auf einer Tabelle sind mehrere Blöcke zulässig. Zu den verfügbaren Aktionen gehören „Verschieben“, „Stapeln“ und „Entstapeln“.

Domäne | Problem: Das lustige! Entstapeln Sie Blöcke ba von Tisch 1 auf einen Stapel ab auf Tisch 3. Auf einem Tisch ist nur ein Block oder Stapel zulässig. Die KI muss planen, einen Block vorübergehend auf Tisch 2 zu verschieben, während sie die richtige Reihenfolge für das Stapeln auf Tisch 3 einrichtet. Zu den verfügbaren Aktionen gehören „Verschieben“, „Stapeln“ und „Entstapeln“.

Beispielausgabe von Blocks World Problem #3

Blöcke werden auf Tisch 1 abwärts gestapelt. Ziel ist es, sie auf Tisch 2 abwärts zu stapeln. Pro Tisch ist nur ein Block oder Stapel zulässig. Hier sind die Lösungen.

 *** Solution found in 6 steps!
1. unstack a b t1 t2
2. move b t1 t3
3. move a t2 t1
4. move b t3 t2
5. move a t1 t3
6. stack a t3 b t2
*** Solution found in 5 steps!
1. unstack a b t1 t2
2. move b t1 t3
3. move a t2 t1
4. move b t3 t2
5. stack a t1 b t2
*** Solution found in 5 steps!
1. unstack a b t1 t2
2. move a t2 t3
3. move b t1 t2
4. move a t3 t1
5. stack a t1 b t2
*** Solution found in 4 steps!
1. unstack a b t1 t2
2. move a t2 t3
3. move b t1 t2
4. stack a t3 b t2
*** Solution found in 4 steps!
1. unstack a b t1 t3
2. move b t1 t2
3. move a t3 t1
4. stack a t1 b t2
*** Solution found in 3 steps!
1. unstack a b t1 t3
2. move b t1 t2
3. stack a t3 b t2

Sussman-Anomalielösung

Hier ist die Lösung der KI für die Blocks World Sussman-Anomalie.

 *** Solution found in 3 steps!
1. unstack2 c a x
2. stack2 b c x
3. stack3 a b c x

Starcraft!

Nun zum Spaß. Hier ist die Starcraft-Domäne. Die Aufgabe bestand darin, eine Kaserne zu bauen. Ursprünglich wollte ich einen Schlachtkreuzer bauen, aber das hat viel zu lange gedauert (ohne heuristische Suche!).

 *** Solution found in 8 steps!
1. move scv sector-a mineral-field-b
2. collect-minerals scv mineral-field-b
3. move scv mineral-field-b sector-b
4. build-supply-depot scv sector-b
5. move scv sector-b mineral-field-a
6. collect-minerals scv mineral-field-a
7. move scv mineral-field-a sector-a
8. build-barracks scv sector-a sector-b

Einen Schritt weiter, hier ist die KI-Lösung für das Training eines Marinesoldaten.

 - Solution found in 11 steps!
1. move scv sector-a mineral-field-a
2. collect-minerals scv mineral-field-a
3. move scv mineral-field-a sector-b
4. build-supply-depot scv sector-b
5. move scv sector-b mineral-field-b
6. collect-minerals scv mineral-field-b
7. move scv mineral-field-b sector-a
8. build-barracks scv sector-a sector-b
9. move scv sector-a mineral-field-c
10. collect-minerals scv mineral-field-c
11. train-marine scv sector-a

Lizenz

MIT

Autor

Kory Becker http://www.primaryobjects.com/kory-becker