Automatisierte Planung und Planung

Automatisierte Planung und Planung, manchmal als einfach bezeichnet KI -Planung,[1] ist ein Zweig von künstliche Intelligenz Das betrifft die Verwirklichung von Strategien oder Aktionssequenzen, typischerweise zur Ausführung durch intelligente Agenten, Autonome Roboter und unbemannte Fahrzeuge. Im Gegensatz zu klassisch Kontrolle und Einstufung Probleme, die Lösungen sind komplex und müssen im mehrdimensionalen Raum entdeckt und optimiert werden. Die Planung hängt auch mit Entscheidungstheorie.

In bekannten Umgebungen mit verfügbaren Modellen kann die Planung offline durchgeführt werden. Lösungen können vor der Ausführung gefunden und bewertet werden. In dynamisch unbekannten Umgebungen die Strategie Oft muss online überarbeitet werden. Modelle und Richtlinien müssen angepasst werden. Lösungen greifen normalerweise auf iterativ zurück Versuch und Irrtum Prozesse, die üblicherweise in gesehen werden künstliche Intelligenz. Diese beinhalten Dynamische Programmierung, Verstärkungslernen und Kombinatorische Optimierung. Sprachen, die zur Beschreibung von Planung und Planung verwendet werden Aktionssprachen.

Überblick

Weitere Informationen: Zustandsspace -Suche

Bei einer Beschreibung der möglichen Anfangszustände der Welt, einer Beschreibung der gewünschten Ziele und einer Beschreibung einer Reihe möglicher Aktionen besteht das Planungsproblem darin, einen garantierten Plan zu synthetisieren (wenn sie auf einen der Anfangszustände angewendet werden) einen Staat zu generieren, der die gewünschten Ziele enthält (ein solcher Staat wird als Zielstaat bezeichnet).

Die Schwierigkeit der Planung hängt von den vereinfachenden Annahmen ab. Abhängig von den Eigenschaften, die die Probleme in mehreren Dimensionen haben, können mehrere Klassen von Planungsproblemen identifiziert werden.

  • Sind die Handlungen deterministisch Oder nicht deterministisch? Sind die damit verbundenen Wahrscheinlichkeiten für nichtdeterministische Maßnahmen verfügbar?
  • Sind die Zustandsvariablen diskret oder kontinuierlich? Wenn sie diskret sind, haben sie dann nur eine begrenzte Anzahl möglicher Werte?
  • Kann der aktuelle Zustand eindeutig beobachtet werden? Es kann volle Beobachtbarkeit und teilweise Beobachtbarkeit geben.
  • Wie viele Anfangszustände gibt es endliche oder willkürlich viele?
  • Haben Aktionen eine Dauer?
  • Können mehrere Maßnahmen gleichzeitig ergriffen werden oder sind jeweils nur eine Aktion möglich?
  • Ist das Ziel eines Plans, einen bestimmten Zielzustand zu erreichen oder a zu maximieren Belohnungsfunktion?
  • Gibt es nur einen Agenten oder gibt es mehrere Agenten? Sind die Agenten kooperativ oder egoistisch? Konstruieren alle Agenten ihre eigenen Pläne separat oder sind die Pläne zentral für alle Agenten?

Das einfachste mögliche Planungsproblem, das als klassische Planungsproblem bezeichnet wird, wird bestimmt:

  • ein einzigartiger bekannter Anfangszustand,
  • dauerlose Aktionen,
  • deterministische Handlungen,
  • die nur eine gleichzeitig eingenommen werden können,
  • und ein einzelner Agent.

Da der Anfangszustand eindeutig bekannt ist und alle Handlungen deterministisch sind, kann der Zustand der Welt nach einer Abfolge von Aktionen genau vorhergesagt werden, und die Frage der Beobachtbarkeit ist für die klassische Planung irrelevant.

Darüber hinaus können Pläne als Sequenzen von Aktionen definiert werden, da es immer im Voraus bekannt ist, welche Aktionen benötigt werden.

Bei nicht deterministischen Aktionen oder anderen Ereignissen außerhalb der Kontrolle des Agenten bilden die möglichen Ausführungen einen Baum, und Pläne müssen die entsprechenden Aktionen für jeden Knoten des Baumes bestimmen.

Diskrete Zeit Markov -Entscheidungsprozesse (MDP) planen Probleme mit:

  • dauerlose Aktionen,
  • Nichtdeterministische Handlungen mit Wahrscheinlichkeiten,
  • volle Beobachtbarkeit,
  • Maximierung einer Belohnungsfunktion,
  • und ein einzelner Agent.

Wenn die vollständige Beobachtbarkeit durch teilweise Beobachtbarkeit ersetzt wird, entspricht die Planung teilweise beobachtbarer Markov -Entscheidungsprozess (Pomdp).

Wenn es mehr als einen Agenten gibt, haben wir Multi-Agent-Planung, was eng mit dem verwandt ist mit Spieltheorie.

Domain -unabhängige Planung

In der KI -Planung geben die Planer in der Regel ein Domänenmodell (eine Beschreibung einer Reihe möglicher Aktionen ein, die die Domäne modellieren) sowie das spezifische Problem, das durch den Ausgangszustand und das Ziel festgelegt werden soll, im Gegensatz zu denen, in denen es keine gibt Eingabedomäne angegeben. Solche Planer werden als "Domain Independent" bezeichnet, um die Tatsache zu betonen, dass sie Planungsprobleme aus einer Vielzahl von Domänen lösen können. Typische Beispiele für Domänen sind Blockstapel-, Logistik-, Workflow-Management- und Roboter-Aufgabenplanung. Daher kann ein einzelner domänenunabhängiger Planer verwendet werden, um Planungsprobleme in all diesen verschiedenen Bereichen zu lösen. Andererseits ist ein Routenplaner typisch für einen domänenspezifischen Planer.

Planungsdomänen -Modellierungssprachen


Die am häufigsten verwendeten Sprachen für die Darstellung von Planungsdomänen und spezifischen Planungsproblemen, wie z. Streifen und PDDL Für die klassische Planung basieren auf staatlichen Variablen. Jeder mögliche Zustand der Welt ist eine Zuordnung von Werten zu den Zustandsvariablen, und Aktionen bestimmen, wie sich die Werte der Zustandsvariablen ändern, wenn diese Aktion ergriffen wird. Da eine Reihe von Zustandsvariablen einen Zustandsraum induzieren, der eine Größe im Set hat, hat die Planung, ähnlich wie viele andere Rechenprobleme, an der Fluch der Dimensionalität und die Kombinatorische Explosion.

Eine alternative Sprache zur Beschreibung von Planungsproblemen ist die von Hierarchische Tasknetzwerke, in denen eine Reihe von Aufgaben erteilt wird und jede Aufgabe entweder durch eine primitive Aktion verwirklicht oder in eine Reihe anderer Aufgaben zerlegt werden kann. Dies beinhaltet nicht unbedingt Zustandsvariablen, obwohl in realistischeren Anwendungsstaat Variablen die Beschreibung von Tasknetzwerken vereinfachen.

Algorithmen für die Planung

Klassische Planung

Siehe auch: Sussman -Anomalie

Reduzierung anderer Probleme

  • Reduzierung des Aussagenerfriedigung Problem (Satplan).
  • Reduktion auf Modellprüfung - Beide sind im Wesentlichen Probleme beim Durchqueren von Staatsräumen, und das klassische Planungsproblem entspricht einer Unterklasse von Modellprüfproblemen.

Zeitplanung

Die zeitliche Planung kann mit Methoden gelöst werden, die der klassischen Planung ähneln. Der Hauptunterschied besteht darin, dass die Möglichkeit mehrerer zeitlich überlappender Aktionen mit einer gleichzeitigen Dauer ergriffen wird, dass die Definition eines Staates Informationen über die aktuelle absolute Zeit und die Ausführung jeder aktiven Aktion enthalten muss. In der Planung mit rationaler oder echter Zeit kann der Staatsraum im Gegensatz zur klassischen Planung oder Planung mit ganzzahliger Zeit unendlich sein. Die zeitliche Planung ist eng mit dem verwandt mit Planung Probleme, wenn Unsicherheit beteiligt ist und auch in Bezug zeitgesteuerte Automaten. Das einfache zeitliche Netzwerk mit Unsicherheit (STNU) ist ein Planungsproblem, das kontrollierbare Maßnahmen, unsichere Ereignisse und zeitliche Einschränkungen beinhaltet. Die dynamische Steuerbarkeit für solche Probleme ist eine Art der Planung, die eine zeitliche Planungsstrategie erfordert, um kontrollierbare Maßnahmen reaktiv zu aktivieren, wenn unsichere Ereignisse beobachtet werden, sodass alle Einschränkungen garantiert erfüllt werden. [2]

Probabilistische Planung

Hauptartikel: Markov -Entscheidungsprozess und Teilweise beobachtbarer Markov -Entscheidungsprozess

Probabilistische Planung kann mit iterativen Methoden wie z. Wert -Iteration und Richtlinien -Iteration, wenn der Staatsraum ausreichend klein ist. Bei teilweise Beobachtbarkeit wird die probabilistische Planung in ähnlicher Weise mit iterativen Methoden gelöst, aber unter Verwendung einer Darstellung der für den Raum der Überzeugungen definierten Wertfunktionen anstelle von Zuständen.

Präferenzbasierte Planung

Hauptartikel: Präferenzbasierte Planung

In der Präferenzplanung ist das Ziel nicht nur, einen Plan zu erstellen, sondern auch die benutzerdefinierte Bekanntheit zu erfüllen Vorlieben. Ein Unterschied in der häufigeren Belohnungsplanung, beispielsweise der MDPs, haben Präferenzen nicht unbedingt einen genauen numerischen Wert.

Bedingte Planung

Die deterministische Planung wurde mit dem eingeführt Streifen Planungssystem, hierarchischer Planer. Aktionsnamen werden in einer Sequenz bestellt und dies ist ein Plan für den Roboter. Hierarchische Planung kann mit einer automatischen erzeugten verglichen werden Verhaltensbaum.[3] Der Nachteil ist, dass ein normaler Verhaltensbaum wie ein Computerprogramm nicht so ausdrucksstark ist. Das heißt, die Notation eines Verhaltensdiagramms enthält Aktionsbefehle, aber nein Schleifen oder wenn sie anwesend sind. Die bedingte Planung überwindet den Engpass und führt eine ausgearbeitete Notation ein, die einem ähnlich ist Steuerfluss, bekannt aus anderen Programmiersprachen wie Pascal. Es ist sehr ähnlich zu ProgrammsyntheseDies bedeutet, dass ein Planer Sourcecode generiert, der von einem Interpreter ausgeführt werden kann.[4]

Ein frühes Beispiel für einen bedingten Planer ist „Warplan-C“, das Mitte der 1970er Jahre eingeführt wurde.[5] Was ist der Unterschied zwischen einer normalen Sequenz und einem komplizierten Plan, der if-then-Statements enthält? Es hat mit Unsicherheit bei zu tun Laufzeit eines Plans. Die Idee ist, dass ein Plan darauf reagieren kann Sensorsignale die für den Planer unbekannt sind. Der Planer generiert im Voraus zwei Möglichkeiten. Wenn beispielsweise ein Objekt erkannt wurde, wird Aktion A ausgeführt. Wenn ein Objekt fehlt, wird Aktion B ausgeführt.[6] Ein wesentlicher Vorteil der bedingten Planung ist die Fähigkeit zu handhaben Teilpläne.[7] Ein Agent ist nicht gezwungen, alles von Anfang bis Ende zu planen, kann aber das Problem unterteilen Stücke. Dies hilft, den Zustandsraum zu reduzieren und viel komplexere Probleme zu löst.

Kontingente Planung

Wir sprechen von "Kontingentplanung", wenn die Umgebung durch Sensoren beobachtet werden kann, was fehlerhaft sein kann. Es ist somit eine Situation, in der der Planungsagent unter unvollständigen Informationen handelt. Für ein Kontingentplanungsproblem ist ein Plan nicht mehr eine Folge von Aktionen, sondern a Entscheidungsbaum Weil jeder Schritt des Plans eher durch eine Reihe von Zuständen als durch einen einzelnen perfekt beobachtbaren Zustand dargestellt wird, wie im Fall der klassischen Planung.[8] Die ausgewählten Aktionen hängen vom Status des Systems ab. Wenn es beispielsweise regnet, nimmt der Agent den Regenschirm, und wenn dies nicht der Fall ist, entscheiden er sich möglicherweise, ihn nicht zu nehmen.

Michael L. Littman zeigte 1998, dass das Planungsproblem mit Verzweigungsmaßnahmen wird Nachfolger-Komplett.[9][10] Ein spezieller Fall einer zusammenhängenden Planung wird durch schöne Probleme dargestellt-für "vollständig beobachtbar und nicht deterministisch". Wenn das Ziel in LTLF (lineare Zeitlogik für endliche Spur) angegeben ist[11] und 2Exptime-Complete, wenn das Ziel mit LDLF angegeben ist.

Konformeplanung

Die konformante Planung ist, wenn der Agent den Zustand des Systems nicht sicher ist und keine Beobachtungen machen kann. Der Agent hat dann Überzeugungen über die reale Welt, kann sie jedoch nicht mit Erkennung von Handlungen überprüfen. Diese Probleme werden durch Techniken gelöst, die denen der klassischen Planung ähneln.[12][13] Aber wo der Zustandsraum in der Größe des Problems exponentiell ist, aufgrund der Unsicherheit über den aktuellen Zustand. Eine Lösung für ein konformes Planungsproblem ist eine Folge von Aktionen. Haslum und Jonsson haben gezeigt, dass das Problem der Konformantenplanung ist Expace-Komplett,[14] und 2xptimale, wenn die anfängliche Situation ungewiss ist, und die Ergebnisse der Aktionen enthält Nichtdeterminismus.[10]

Bereitstellung von Planungssystemen

Siehe auch

Listen

Verweise

  1. ^ Ghallab, Malik; Nau, Dana S.; Traverso, Paolo (2004), Automatische Planung: Theorie und Praxis, Morgan Kaufmann, ISBN 1-55860-856-7
  2. ^ Vidal, Thierry (Januar 1999). "Handhabung der Kontingenz in zeitlichen Einschränkungen Networks: Von Konsistenz zu Kontrollabilitäten". Zeitschrift für experimentelle & theoretische künstliche Intelligenz. 11 (1): 23-45. doi:10.1080/095281399146607.
  3. ^ Neufeld, Xenija und Mostaghim, Sanaz und Sancho-Pradel, Dario und Brand, Sandy (2017). "Aufbau eines Planers: Eine Übersicht über Planungssysteme, die in kommerziellen Videospielen verwendet werden". IEEE -Transaktionen auf Spielen. IEEE.{{}}: Cs1 montiert: Mehrfachnamen: Autorenliste (Link)
  4. ^ Sanelli, Valerio und Cashmore, Michael und Magazzeni, Daniele und Iocchi, Luca (2017). Kurzfristige Interaktion zwischen menschlichem Roboter durch bedingte Planung und Ausführung. Proc. der internationalen Konferenz über automatisierte Planung und Planung (ICAPS).{{}}: Cs1 montiert: Mehrfachnamen: Autorenliste (Link)
  5. ^ Peot, Mark A und Smith, David E (1992). Bedingte nichtlineare Planung (PDF). Künstliche Intelligenzplanungssysteme. Elsevier. S. 189–197.{{}}: Cs1 montiert: Mehrfachnamen: Autorenliste (Link)
  6. ^ Karlsson, Lars (2001). Bedingte progressive Planung unter Unsicherheit. Ijcai. S. 431–438.
  7. ^ Liu, Daphne Hao (2008). Eine Umfrage zur Planung in intelligenten Agenten: Von extern motiviert zu intern motivierten Systemen (Technischer Bericht). Technischer Bericht TR-2008-936, Abteilung für Informatik, Universität Rochester.
  8. ^ Alexandre Albore; Hector Palacios; Hector Geffner (2009). Ein übersetzungsbasierter Ansatz zur Kontingentplanung. Internationale gemeinsame Konferenz für künstliche Intelligenz (IJCAI). Pasadena, CA: AAAI.
  9. ^ Littman, Michael L. (1997). Probabilistische Sätze Planung: Darstellungen und Komplexität. Vierzehnte nationale Konferenz über künstliche Intelligenz. MIT Press. S. 748–754. Abgerufen 2019-02-10.
  10. ^ a b Jussi Rintanen (2004). Komplexität der Planung mit teilweise Beobachtbarkeit (PDF). Int. Conf. Automatisierte Planung und Planung. Aaai.
  11. ^ De Giacomo, Giuseppe; Rubin, Sasha (2018). Automatisch-theoretische Grundlagen der schönen Planung für LTLF- und LDLF-Ziele. Ijcai. Abgerufen 2018-07-17.
  12. ^ Palacios, Hector; Geffner, Hector (2009). "Zusammenstellung der Unsicherheit in konformanten Planungsproblemen mit begrenzter Breite". Journal of Artificial Intelligence Research. 35: 623–675. doi:10.1613/jair.2708.
  13. ^ Albore, Alexandre; Ramírez, Miquel; Geffner, Hector (2011). Wirksame Heuristik und Glaubensverfolgung für die Planung mit unvollständigen Informationen. Die einundzwanzigste internationale Konferenz für automatisierte Planung und Planung (ICAPS).
  14. ^ Haslum, Patrik; Jonsson, Peter (2000). "Einige Ergebnisse zur Komplexität der Planung mit unvollständigen Informationen". Jüngste Fortschritte bei der KI -Planung. Vorlesungsnotizen in Informatik. Springer Berlin Heidelberg. 1809: 308–318. doi:10.1007/10720246_24. ISBN 9783540446576.

Weitere Lektüre

Externe Links