STRIPS

STRIPS

STRIPS

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 este generador de planes.


Definición

Una instancia de STRIPS se compone de:

  • Un estado inicial.
  • La especificación de estados de meta.
  • Un conjunto de acciones, para cada una de las cuales se incluyen:
    • Precondiciones.
    • Poscondiciones.

Matemáticamente, una instancia de STRIPS es una tupla \langle P,O,I,G \rangle, donde:

  • P es un conjunto de condiciones (es decir, variables proposicionales).
  • O es un conjunto de operadores (es decir, acciones); cada operador es también una tupla \langle \alpha, \beta, \gamma, \delta \rangle, donde cada elemento es un conjunto de condiciones:
    • α representa a las condiciones que deben ser verdaderas para que la acción pueda ejecutarse.
    • β representa a las condiciones que deben ser falsas para que la acción pueda ejecutarse.
    • γ representa a las condiciones se hacen verdaderas si se ejecuta la acción.
    • δ representa a las condiciones se hacen falsas si se ejecuta la acción.
  • I es el estado inicial, dado por un conjunto de condiciones que son inicialmente verdaderas (todas las demás se asumen falsas).
  • G es la especificación del estado de meta, que está dada por una dupla \langle N,M \rangle, que especifica qué condiciones deben ser verdaderas y cuales falsas para considerar a un estado como meta.

Un plan para una instancia es una secuencia de operadores que puede ser ejecutada desde el estado inicial, y que lleva hasta un estado meta.

Formalmente, un estado es un conjunto de condiciones, y se representa por el conjunto de condiciones que son verdaderas en él. Las transiciones entre estados se modelan mediante una función de transición, que es una función que mapea estados en otros estados que resultan de aplicarles acciones a los primeros. Ya que los estados se representan por conjuntos de acciones, la función de transición emparentada con la instancia STRIPS \langle P,O,I,G \rangle es una función:

\operatorname{sucesor}: 2^P \times A \rightarrow 2^P,

donde 2P es el conjunto de todos los subconjuntos de P, y por lo tanto es el conjunto de todos los posibles estados.

La función de transición puede definirse, asumiendo que las acciones siempre pueden ser ejecutadas pero no tienen efecto si sus precondiciones no se cumplen, como:

\operatorname{sucesor}(C,\langle \alpha,\beta,\gamma,\delta \rangle) = (C \backslash \delta) \cup \gamma         Si (\alpha \subseteq C /and \beta \cap C = \varnothing)
  = P De otra forma

La función \operatorname{sucesor} puede extenderse para secuencias de acciones mediante ecuaciones recursivas:

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

Un plan para una instancia de STRIPS es una secuencia de acciones cuya ejecución ordenada produce un estado que satisface las condiciones de meta, a partir del estado inicial. Formalmente, [a_1,a_2,\ldots,a_n] es un plan para G = \langle N,M \rangle si F=\operatorname{sucesor}(I,[a_1,a_2,\ldots,a_n]) satisface:

  • N \subseteq F
  • M \cap F = \varnothing


Un problema STRIPS de ejemplo

Hay un mono en el laboratorio, y quiere bananas. Hay tres ubicaciones en el laboratorio: A, B y C. El mono está en la ubicación A. Hay una caja en la ubicación C. Hay bananas en la ubicación B, pero cuelgan del techo. El mono necesita la caja para alcanzar las bananas.


Estado inicial
MonoEn(A)
NivelMono(abajo)
CajaEn(C)
BananasEn(B)
Estado meta MonoTiene(Bananas)
Acciones
Acción Descripción Precondición Poscondición
Ir(X, Y) Ir de X a Y MonoEn(X), NivelMono(abajo) \negMonoEn(X), MonoEn(Y)
Trepar(X) Subirse a la caja en la ubicación X MonoEn(X), CajaEn(X), NivelMono(Abajo) \negNivelMono(Abajo), NivelMono(Arriba)
Bajarse(X) Bajarse de la caja en la ubicación X MonoEn(X), CajaEn(X), NivelMono(Arriba) \negNivelMono(Arriba), NivelMono(Abajo)
LlevarCaja(X, Y) Llevar la caja de X a Y MonoEn(X), CajaEn(X), NivelMono(Abajo) \negCajaEn(X), CajaEn(Y), \negMonoEn(X), MonoEn(Y)
TomarBananas(X) Tomar las bananas en la ubicación X MonoEn(X), BananasEn(X), NivelMono(Arriba) MonoTiene(Bananas)
Obtenido de "STRIPS"

Wikimedia foundation. 2010.

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

Mira otros diccionarios:

  • 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 — 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… …   Deutsch Wikipedia

  • 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

Compartir el artículo y extractos

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