PDF de programación - Planificación con STRIPS

Bibliografía

(cid:122) Nilsson, Artificial Intelligence: A New

Synthesis. Cap. 22.

(cid:122) Russell & Norvig, Artificial Intelligence:

A Modern Approach. Cap. 11.

Planificación con STRIPS

1

2

1

Introducción

Sintaxis

(cid:122) Objetivo: Desarrollar un proceso de

planificación
» La planificación es un proceso de búsqueda y

ejecución de una serie de acciones que permitan
alcanzar un objetivo

(cid:122) El lenguaje empleado en los problemas de

planificación es STRIPS
» STRIPS: STanford Research Institute Problem

Solver. [Fikes y Nilsson 1971]

» Los algoritmos que usan STRIPS aprovechan la
estructura de problema gracias a su capacidad
expresiva

(cid:122) Ejemplos de agentes planificadores ya vistos

» Agentes basados en búsquedas
» Agentes basados en lógica

(cid:122) La Planificación clásica se restringe a

entornos
» Observables
» Deterministas
» Finitos
» Estáticos

» Discretos

– los cambios sólo se producen al actuar los agentes

– En tiempo, acciones, objetos y efectos

(cid:122) Un método de planificación es un método de búsqueda
sobre una estructura de datos (estados del proceso de
planificación) que evoluciona con las acciones de un
agente de planificación.

(cid:122) ESTADOS

» Los estados en un proceso de planificación se denominan

DESCRIPCIONES DE ESTADO (DE)

– Compuestos de condiciones lógicas
– Sólo admiten literales simples, sin dependencias funcionales
(cid:122) En(x, y), En(padre(Pedro), Madrid) -> NO ADMITIDOS
(cid:122) En(Avión, Barcelona), En(Tren, Ávila) -> ADMITIDOS

» Las DE se restringen a conjuntos de literales aunque

pueden contener un número arbitrario de fórmulas
verdaderas como por ejemplo, en el mundo de bloques

On x y
( ,

)

⇒ =

y Fl

(

)

∨ ¬

Clear y
( )

(cid:122) OBJETIVOS

» Un objetivo es un estado parcialmente especificado
» Los objetivos se restringen a conjuntos de literales

cuantificados existencialmente

– Una DE s satisface un objetivo w si s contiene todos sus

elementos en w

– Ejemplo: La DE rico ^ famoso ^ miserable satisface el

objetivo rico ^ famoso

3

4

2

Sintaxis, II

(cid:122) OPERADORES

» Un operador o regla STRIPS es un patrón de

operador que posee variables libres

» se especifica en términos de

– Las precondiciones, PC, que deben cumplirse antes

de ser ejecutado

(cid:122) El conjunto PC está formado por literales.

» La acción correspondiente a un operador

sólo se puede ejecutar en un estado si todos
los literales en PC pertenecen también a la
DE previa a la acción

– Las consecuencias (efectos) que se derivan cuando

se ejecuta

(cid:122) Lista de borrado: Un conjunto, D, de literales
(cid:122) Lista de adición: Un conjunto, A, de literales
– Una forma alternativa de representación de los

efectos de una regla es mediante una conjunción de
literales positivos y negativos

» PC, D y A o, alternativamente, PC y EFECTOS

constituyen un esquema de acción.

» Obs.: en lo que sigue los efectos los

consideraremos como listas de borrado y adición

5

Semántica

(cid:122) Trata sobre la descripción de cómo los

operadores afectan a los estados

(cid:122) Vamos a emplear diferentes métodos de

búsqueda en los procesos de planificación.
» Hacia delante: progression planning
» Hacia atrás: regression planning
» Ambas se fundamentan en los operadores STRIPS

(cid:122) Dada una FBF objetivo w, los métodos de

búsqueda tratan de encontrar una secuencia
de acciones que proporcionen un estado del
mundo descrito mediante alguna DE ∆ tal que
∆╞ w. Si esto sucede se dice que la DE
satisface el objetivo.

(cid:122) ∆╞ w si existe una sustitución σ tal que wσ es

una conjunción de literales todos los cuales
están en ∆

6

3

Semántica, II

Semántica, III (ejemplo)

(cid:122) Un operador es aplicable si lo es en

cualquier DE que satisfaga sus PC. En
caso contrario es no aplicable (sin
efecto)

(cid:122) Partiendo de una DE s (before-action),

el resultado de ejecutar un operador
aplicable a s nos lleva a otra DE s’
(after-action) en la que
» Comprobando que los literales de PC

están, a su vez, en la DE s (condición de
aplicación del operador STRIPS)

» Borrando de la DE s los literales de D
» Añadiendo a la DE s los literales en A
» Todos los literales no mencionados en D se

acarrean a la DE s’. Este acarreo se
denomina HIPÓTESIS STRIPS
– Hipótesis STRIPS: Cada literal no mencionado
7

en los efectos permanece sin modificar

(cid:122) Mundo de Bloques

» Dominio:

– conjunto de bloques sobre un tablero
– Sólo es posible situar un bloque sobre otro
– Los bloques los mueve un brazo mecánico, uno cada

vez

» Objetivo:

– Construir uno o más montones de bloques

A
B

C
D

» Operadores:

– On(bloque, posición)

(cid:122) On ( C, Fl)

– Move(bloque, pos_x, pos_y)

A
B
C
D

(cid:122) Requieres PC. Para mover un bloque requiere

que no haya otro sobre él. Con el predicado
CLEAR garantizaremos esta restricción

(cid:122) Move(B, Fl, C)
(cid:122) Move (B, C, C) acción espuria o degenerada (se
8

puede solventar añadiendo PC de igualdad)

4

Ejemplo (cont.)

(cid:122) Ej.: move(x,y,z)

» PC: On(x,y) ^ Clear(x) ^ Clear(z)
» D: Clear(z), On(x,y)
» A: On(x,z), Clear(y), Clear(Fl)

– Clear(posición)

(cid:122) Predicado que toma valor T si ningún bloque

está sobre posición

(cid:122) Se debe interpretar este operador como

» “existe un espacio vacío sobre posición

para trasladar un bloque”

» En tal caso Clear(Fl) = T siempre

(cid:122) Dificultad 1: si en el operador move y o z
corresponden al tablero (Fl), este no se
puede despejar. Para evitarlo se podría
incluir un operador adicional
moverSobreTablero

(cid:122) Ej.: moverSobreTablero(x, y)

» PC: On(x,y) ^ Clear(x)
» D: Clear (x)
» A: On(x, Fl), Clear(y)

9

Ejemplo (cont.)

(cid:122) Dificultad 2:

» O bien se permite -> espacio de

búsqueda mayor

» Si no se permite hay que incluir un

nuevo predicado, bloque(x), e incluir,
como precondiciones de move,
bloque(x) ^ bloque(z)

10

5

Forward Search Methods

(FSM)

FSM, II

(cid:122) Búsqueda en el espacio de estados desde el estado

inicial
» El estado inicial del problema de planificación está

descrito en términos de un conjunto de literales simples
positivos (los literales que no aparecen se consideran F)

» Los operadores STRIPS aplicables deben cumplir las

precondiciones. La DE resultante, a-a, se obtiene
aplicando los conjuntos D y A sobre la DE b-a

DE before-action

DE after-action

STRIPS
action-operator

» Se debe incluir un test objetivo
» El coste de aplicación de los operadores habitualmente es

unitario

(cid:122) Los FSM parten de una DE before-action y mediante un

operador STRIPS generan una DE after-action. Este
proceso lo realizan de forma iterativa (hacia delante),
generando una secuencia de DEs, la última de las
cuales se desea que sea el objetivo

DE1

DE1

...

DEn

11

(cid:122) Al no existir funciones, el espacio de
estados es finito. Cualquier algoritmo
completo para búsqueda en grafos lo
es también para planificación. Por
ejemplo A*.

(cid:122) En la práctica suelen ser ineficaces en

problemas de tamaño medio. Por
ejemplo, para un problema de
planificación de carga aérea con
» 9 aeropuertos
» 50 aviones
» 200 piezas a transportar
» Objetivo: llevar la carga de aeropuerto A a

aeropuerto B

» El factor de ramificación es de

aproximadamente 1000 y el árbol de
búsqueda tiene aproximadamente 100041
nodos

12

6

FSM, III

(cid:122) Ejemplo de aplicación del patrón de

regla visto anteriormente en búsqueda
hacia adelante:
» move(x,y,z)

– PC: On(x,y) ^ Clear(x) ^ Clear(z)
– D: Clear(z), On(x,y)
– A: On(x,z), Clear(y), Clear(Fl)

[1]
[2]
[3]

» [1]: PC en una regla STRIPS está en forma

de objetivo: conjunción de literales. Se
asumen cuantificadas existencialmente las
variables de PC.
– Una instancia de regla STRIPS (instancia de

patrón) se puede aplicar a la DE ∆ si una
instancia de PC se satisface mediante la DE. Tal
instancia se obtiene mediante la unificación, por
etapas, de los literales en PC con un literal en la
DE.

– La instancia del operador aplicable se obtiene

aplicando la sustitución a todos los elementos de
la regla.

13

FSM, IV (ejemplo)

Ejemplo de operador STRIPS (Nilsson, pp. 376)

[2]

[3]

DE after-action

=

)

∧
,

DE before-action
PC On x y Clear x Clear z
( )
( ,
( )
∧
}
{
DE
On B A Clear B Clear Fl
),
(
(
)
=
b a
−
}
{
}
On x y On B A D
x B
A
,
,
) ,
( ,
=
=
σ
1
1
1
{
}
A
On B y On B A
,
(
)
=
σ
1
1

(
),
,

),
(

,
(

{

),

L
=
σ

{

x B y
:
,
=

:
=

A z
,

:
=

Fl

}

=

{

}
x B
:
=

14

7

FSM, V (aplicación cont.)

Backward Search Methods

(BSM)

,

,

(cid:122) La instancia de la regla y la DE after-action
quedan, una vez aplicado el unificador σ:
move B A Fl
PC On B A Clear B Clear Fl
)
(
,
}
D On B A Clear Fl
)
,
A On B A Clear A Clear Fl
),
,
y

(
=
{
{

)
)
),
),

(
(
(

=
=

(
(

}
)

∧

∧

)

(

(

(cid:122) También denominados Regression Planning Methods
(cid:122) Poco eficiente en problemas grandes
(cid:122) Permiten considerar sólo operadores relevantes,

aquellos que alcanzan alguno de los objetivos que se
desea explorar

(cid:122) La regresión de una fórmula w mediante una regla

STRIPS a es una fórmula más débil w’ tal que, si w’ se
satisface por una DEb-a antes de aplicar una instancia
de a (w’ verifica PC de la instancia de a) entonces w
será satisfecha por la DEa-a después de aplicar la
instancia de a

Ejemplo de FSM
con STRIPS
(Nilsson, pp. 382)

(

(

(

DE

On A C On B Fl On C Fl
),

= 
Clear A Clear B Clear Fl
)





(cid:122) En la búsqueda puede usarse, por ejemplo,

),
),

),
),

,
(

,
(

,
(

a a
−

A*, donde
» h es una heurística que estime el coste al objetivo
» g función que refleje el coste de las acciones

(usualmente unitario)

(cid:122) Sin una heurística sobre qué acciones aplicar,

FSM no es apta en aplicaciones con gran
número de reglas y DE

15

16

8

BSM, II

BSM, III

(cid:122) Es importante que los operadores sean

consis