TIRAS

En la inteligencia artificial, las TIRAS (Solucionista del problema del Instituto de investigación de Stanford) son un planificador automatizado desarrollado por Richard Fikes y Nils Nilsson en 1971 en SRI International. El mismo nombre era usado más tarde para referirse a la lengua formal de las entradas a este planificador. Esta lengua es la base para la mayor parte de las lenguas para expresar casos del problema de planificación automatizados en el uso hoy; tales lenguas comúnmente se conocen como lenguas de acción. Este artículo sólo describe la lengua, no el planificador.

Definición

Un caso de TIRAS se forma de:

Matemáticamente, un caso de TIRAS es un cuádruple, en el cual cada componente tiene el sentido siguiente:

  1. es un juego de condiciones (es decir, variables de proposiciones);
  1. es un grupo de operadores (es decir, acciones); cada operador es un cuádruple, cada elemento que es un juego de condiciones. Estos cuatro juegos especifican, en el pedido, qué condiciones deben ser verdad para la acción para ser ejecutables, cuales deben ser falsos, cuales son hechos verdaderos por la acción y cuales se hacen falsos;
  1. es el estado inicial, dado como el juego de condiciones que son verdad al principio (todos los otros se asumen falsos);
  1. es la especificación del estado del objetivo; dan esto como un par, que especifican qué condiciones son verdad y son falsas, respectivamente, para un estado para considerarse un estado del objetivo.

Un plan para tal caso de planificación es una secuencia de operadores que se pueden ejecutar del estado inicial y esto lleva a un estado del objetivo.

Formalmente, un estado es un juego de condiciones: un estado es representado por el juego de condiciones que son verdad en ello. Las transiciones entre estados son modeladas por una función de transición, que es una función que traza un mapa de estados en nuevos estados que resultan de la ejecución de acciones. Ya que los estados son representados por juegos de condiciones, la función de transición con relación al caso de TIRAS es una función

:

donde está el juego de todos los subconjuntos de y es por lo tanto el juego de todos los estados posibles.

La función de transición para un estado, se puede definir así, usando la asunción de simplificación que las acciones siempre se pueden ejecutar, pero no tener efecto si sus condiciones previas no se encuentran:

La función puede ser ampliada a secuencias de acciones por las ecuaciones recurrentes siguientes:

:

:

Un plan para un caso de TIRAS es una secuencia de acciones tales que el estado que resulta de ejecutar las acciones en el pedido del estado inicial satisface las condiciones del objetivo. Formalmente, es un plan para si satisface las dos condiciones siguientes:

:

:

Extensiones

La susodicha lengua es realmente la versión de proposiciones de TIRAS; en la práctica, las condiciones a menudo son sobre objetos: por ejemplo, que la posición de un robot pueda ser modelada por un predicado y signifique que el robot está en Room1. En este caso, las acciones pueden tener variables libres, que implícitamente existencialmente se cuantifican. En otras palabras, una acción representa todas las acciones de proposiciones posibles que se pueden obtener sustituyendo cada variable libre con un valor.

El estado inicial se considera totalmente conocido en la lengua descrita encima: las condiciones que no están en todos se asumen falsas. Esto a menudo es una asunción restrictiva, como hay ejemplos naturales de planear problemas en los cuales el estado inicial totalmente no se conoce. Las extensiones de TIRAS se han desarrollado para tratar con estados iniciales parcialmente conocidos.

Una muestra QUITA problema

Un mono está en la posición un en un laboratorio. Hay una caja en la posición C. El mono quiere los plátanos que cuelgan del techo en la posición B, pero tiene que mover la caja y subida en ello a fin de alcanzarlos.

Estado inicial: En (A), Nivel (bajo), BoxAt (C), BananasAt (B)

Estado del objetivo: Tenga (Plátanos)

Acciones:

//muévase de X a Y

_Move (X, Y) _

Condiciones previas: en (X), nivel (bajo)

Postcondiciones: no En (X), En (Y)

//suba en la caja

_ClimbUp (Posición) _

Condiciones previas: en (posición), BoxAt (posición), nivel (bajo)

Postcondiciones: Nivel (alto), no Nivel (bajo)

//bájese de la caja

_ClimbDown (Posición) _

Condiciones previas: en (posición), BoxAt (posición), nivel (alto)

Postcondiciones: Nivel (bajo), no Nivel (alto)

//mueva el mono y la caja de X a Y

_MoveBox (X, Y) _

Condiciones previas: en (X), BoxAt (X), nivel (bajo)

Postcondiciones: BoxAt (Y), no BoxAt (X), En (Y), no En (X)

//tome los plátanos

_TakeBananas (Posición) _

Condiciones previas: en (posición), BananasAt (posición), nivel (alto)

Postcondiciones: tenga (plátanos)

Complejidad

La decisión de la existencia de un plan para un caso de TIRAS de proposiciones es PSPACE-completa. Varias restricciones se pueden hacer cumplir en los casos para hacer el problema NP-complete

Véase también

Notas



Buscar