STRIPS

STRIPS

Im Bereich Künstliche Intelligenz beschreibt STRIPS (Stanford Research Institute Problem Solver) einen automatischen Planer, entwickelt von Richard Fikes und Nils Nilsson im Jahre 1971. Der Name STRIPS wurde später verwendet, um sich auf die Formale Sprache zu beziehen, die als Eingabe für den Planer diente. Diese Sprache bietet heutzutage die Grundlage zum Beschreiben der meisten Problemdomänen. Dieser Artikel bezieht sich nur auf die Sprache, nicht auf den Planer.

Definition

Ein STRIPS-Modell besteht aus:

  • einem Anfangszustand;
  • einem Zielzustande, also die Situation, die der Planer erreichen will;
  • eine Menge von Aktionen. Für jede Aktion muss Folgendes gegeben sein:
    • Vorbedingungen (was muss gegeben sein, bevor die Aktion ausgeführt werden kann);
    • Nachbedingungen (was ist erreicht, nachdem die Aktion ausgeführt wurde).

Mathematisch gesehen, ist ein STRIPS-Modell ein 4-Tupel \langle P,O,I,G \rangle, in dem jede Komponente folgende Bedeutung hat:

  1. P ist eine Menge von Bedingungen;
  2. O ist eine Menge von Operationen; jeder Operator ist dabei selbst ein 4-Tupel \langle \alpha, \beta, \gamma, \delta \rangle, wobei jedes Element eine Menge von Bedingungen ist. Die vier Mengen beschreiben in gegebener Reihenfolge, welche Bedingungen müssen wahr sein, damit die Aktion ausgeführt werden kann, welche Bedingungen müssen falsch sein, welche Bedingungen werden durch das Ausführen der Aktion wahr, welche werden falsch;
  3. I der Startzustand, beschrieben durch eine Menge von Bedingungen, die zu Beginn wahr sind (alle anderen sind demnach falsch);
  4. G der Zielzustand; gegeben als Paar \langle N,M \rangle, das Beschreibt, welche Bedingungen wahr und welche falsch sein müssen.

Ein Plan in einem solchen Planungsmodell ist eine Sequenz von Aktionen, die vom Startzustand aus erfolgen und zu dem Zielzustand führen.

Formal gesehen, ist ein Zustand eine Menge von Bedingungen – ein Zustand wird dabei von den Bedingungen beschrieben, die wahr sind.

Übergänge zwischen den Zuständen werden durch eine Übergangsfunktion beschrieben, die einen Zustand und eine Aktion auf einen anderen Zustand abbildet:

\operatorname{t}: 2^P \times O \rightarrow 2^P,, indem 2P Menge aller Teilmengen von P ist, und somit alle möglichen Zustände bei einer gegebenen Menge P von Bedingungen.

Die Übergangsfunktion kann wie folgt definiert werden, wobei davon ausgegangen wird, dass Aktionen immer ausgeführt werden können, jedoch keinen Effekt haben, wenn ihre Vorbedingungen nicht erfüllt sind:

\operatorname{t}(C,\langle \alpha,\beta,\gamma,\delta \rangle) = C \backslash \delta \cup \gamma         falls \alpha \subseteq C und \beta \cap C = \varnothing
  = P sonst

Die Übergangsfunktion \operatorname{t} kann auf Folgen von Aktionen mittels Rekursion angewandt werden:

\operatorname{t}(C,[\ ]) = C
\operatorname{t}(C,[a_1,a_2,\ldots,a_n])=\operatorname{t}(\operatorname{t}(C,a_1),[a_2,\ldots,a_n])

Ein Plan für ein STRIPS-Modell ist eine Folge von Aktionen, sodass der Zustand, der aus der Folge von Aktionen resultiert, angefangen beim Startzustand, letztendlich zum Zielzustand führt. Formal [a_1,a_2,\ldots,a_n] ist ein Plan für G = \langle N,M \rangle, falls F=\operatorname{t}(I,[a_1,a_2,\ldots,a_n]) die folgenden beiden Bedingungen erfüllt:

N \subseteq F
M \cap F = \varnothing

Beispiel für ein STRIPS-Problem

Ein Affe ist an der Position A in einem Labor. Eine Box steht an der Position C. Der Affe möchte die Bananen haben, die von der Decke an der Position B hängen. Er muss jedoch die Box bewegen und auf sie klettern, um sie zu erreichen.

Anfangszustand: At(A), Level(low), BoxAt(C), BananasAt(B) Zielzustand: Have(Bananas)

Aktionen:
               // move from X to Y
               _Move(X, Y)_
               Preconditions:  At(X), Level(low)
               Postconditions: not At(X), At(Y)
               
               // climb up on the box
               _ClimbUp(Location)_
               Preconditions:  At(Location), BoxAt(Location), Level(low)
               Postconditions: Level(high), not Level(low)
               
               // climb down from the box
               _ClimbDown(Location)_
               Preconditions:  At(Location), BoxAt(Location), Level(high)
               Postconditions: Level(low), not Level(high)
               
               // move monkey and box from X to Y
               _MoveBox(X, Y)_
               Preconditions:  At(X), BoxAt(X), Level(low)
               Postconditions: BoxAt(Y), not BoxAt(X), At(Y), not At(X)
               
               // take the bananas
               _TakeBananas(Location)_
               Preconditions:  At(Location), BananasAt(Location), Level(high)
               Postconditions: Have(bananas)

Quellen

  • C. Bäckström and B. Nebel (1995). Complexity results for SAS+ planning. Computational Intelligence, 11:625-656.
  • T. Bylander (1991). Complexity results for planning. In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence (IJCAI'91), pages 274-279.
  • R. Fikes and N. Nilsson (1971). STRIPS: a new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2:189-208.
  • Stuart Russell, Peter Norvig: Künstliche Intelligenz: Ein moderner Ansatz, August 2004, Pearson Studium, ISBN 3-8273-7089-2 (deutsche Übersetzung der 2. Auflage)

Wikimedia Foundation.

Игры ⚽ Поможем сделать НИР

Schlagen Sie auch in anderen Wörterbüchern nach:

  • STRIPS — Saltar a navegación, búsqueda En Inteligencia artificial, STRIPS (Stanford Research Institute Problem Solver) es un generador de planes automatizado. El mismo nombre fue utilizado más tarde para referirse al lenguaje formal de las entradas de… …   Wikipedia Español

  • STRIPS — (ou STanford Research Institute Problem Solver) est un algorithme de planification classique conçu par Richard Fikes et Nils Nilsson en 1971. L algorithme de STRIPS est assez basique, mais il est intéressant comme exemple pédagogique. On nomme… …   Wikipédia en Français

  • Strips — die (Plur.) <aus gleichbed. engl. amerik. strips, Plur. von strip, vgl. ↑Strip>: 1. kurze Fasern, die auf einer Spinnereimaschine durch Arbeitswalzen abgestreift werden. 2. svw. ↑Comicstrips …   Das große Fremdwörterbuch

  • Strips — (engl.), 1) bei der englischen Armee u. Flotte eingeführte Strafe, besteht aus Hieben mit einer ledernen, am Ende in mehre Riemen geschnittenen Peitsche; 2) diese Peitsche selbst (Neunschwänzige Katze). Diese Hiebe mit dem S. sind, zahlreich… …   Pierer's Universal-Lexikon

  • STRIPS — In artificial intelligence, STRIPS (Stanford Research Institute Problem Solver) is an automated planner developed by Richard Fikes and Nils Nilsson in 1971. The same name was later used to refer to the formal language of the inputs to this… …   Wikipedia

  • Strips — Comic strip Pour les articles homonymes, voir Strip. Les comic strips sont des bandes dessinées de quelques cases qui constituent soit de courts gags soit des histoires à suivre, publiées dans la presse quotidienne ou hebdomadaire. Aux États Unis …   Wikipédia en Français

  • STRIPS — Эта статья о системах автоматического планирования, которое является подразделом Искусственного интеллекта STRIPS (Stanford Research Institute Problem Solver)  это автоматический планировщик, разработанный Ричардом Файксом и Нильсом Нилсоном …   Википедия

  • Strips — The term strips has various meanings:* A financial option composed of one call option and two put options with the same strike price * A treasury security acronym for Separate Trading of Registered Interest and Principal of Securities , which are …   Wikipedia

  • STRIPS — Separately Tradable Registered Interest and Principal Securities (Business » General) Separately Tradable Registered Interest and Principal Securities (Business » International Business) Separately Tradable Registered Interest and Principal… …   Abbreviations dictionary

  • strips — Principal and interest cash flows due from any interest bearing securities can be separated into different financial instruments. This is done by stripping each coupon payment from the underlying investment to create a separate security. For… …   Financial and business terms

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”