PDF de programación - Planificación con STRIPS

Planificación con STRIPS

1

Bibliografía

 Nilsson, Artificial Intelligence: A New

Synthesis. Cap. 22.

 Russell & Norvig, Artificial Intelligence:

A Modern Approach. Cap. 11.

2

Introducción

 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

» Ejemplos de agentes planificadores ya vistos

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

 Cambiar una rueda, embarques de vuelos, etc.
 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

 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

3

Sintaxis

 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

 ESTADOS

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

DESCRIPCIONES DE ESTADO (DE)

– Compuestos de condiciones lógicas (predicados)

 [En(RP,E), En(RR,M)]

– Sólo admiten literales simples, sin dependencias funcionales

y sin variables no ligadas.

 En(x, y), En(padre(Pedro), Madrid) -> NO ADMITIDOS
 En(Avión, Barcelona), En(Tren, Ávila) -> ADMITIDOS

 OBJETIVOS

afirmados

» Un objetivo es una conjunción de literales básicos

» Los objetivos se restringen a conjuntos de literales

cuantificados existencialmente

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

elementos en w

 DE s: rico ^ famoso ^ miserable
 Goal w: rico ^ famoso (se satisface)

4

Sintaxis, II
 OPERADORES o ACCIONES

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

posee variables libres

» se especifica en términos de

– Las precondiciones, PC, que deben cumplirse antes

de ser ejecutado

 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

» On(x,y) ^ Clear(x) ^ Clear(z)

– Las consecuencias (efectos) que se derivan cuando

se ejecuta

 Lista de borrado: Un conjunto, D, de literales
 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

 Descripción de cómo los operadores afectan a

los estados

 Existen diferentes métodos de búsqueda
fundamentados en el uso de operadores
STRIPS aplicables a los procesos de
planificación
» Hacia delante: progression planning
» Hacia atrás: regression planning

 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.

 ∆╞ w si existe una sustitución σ tal que wσ es

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

6

Semántica, II

 Un operador es aplicable si lo es en

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

 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 el proceso:
» Comprobado que los literales de PC están,

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

» Borrados de la DE s los literales de D
» Añadidos 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

Semántica, III (ejemplo)

 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)

 On ( C, Fl)

– Move(bloque, pos_x, pos_y)

A
B
C
D

 Requiere PC. Para mover un bloque requiere que

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

 Move(B, Fl, C)
 Move (B, C, C) acción espuria o degenerada (se
8

puede solventar añadiendo PC de igualdad)

Ejemplo (cont.)

 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)

 Predicado que toma valor T si ningún bloque

está sobre posición

 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

 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

 Ej.: moverSobreTablero(x, y)

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

9

Ejemplo (cont.)

 Dificultad 2:

» O bien se permite mover Fl  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) (se evita poder
mover Fl)

10

Forward Search Methods

(FSM)

 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

 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

DE2

...

DEn

11

FSM, II

 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*)

 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

FSM, III

 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án 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 operador STRIPS

(Nilsson, pp. 376)

[1]

[2]

[3]

DE before-action

DE after-action

( )

DE

b a
−

∧
,
,

PC On x y Clear x Clear z
( )
(

( ,
∧
On B A Clear B Clear Fl
(
),

= 
On A C On C Fl
(
,
)

{
}
On x y On B A D
( ,
) ,
=
1
{
}
On B y On B A
,
(
)
=

)
(
(
),
,

}
x B
,

),
),
(

,
(

),

)




,
=
σ
1

=

A
=
1
A
σ
1 1

σ

=

{

{

}
x B
:
=

{

x B y
:
,
=

:
=

A z
,

:
=

Fl

}

14

FSM, V (aplicación cont.)

,

,

 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 Fl Clear A Clear Fl
),
,
y

(
=
{
{

)
)
),
),

(
(
(

=
=

(
(

}
)

∧

∧

(

(

)

(

(

(

a a
−

DE

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




 En la búsqueda puede usarse, por ejemplo,

),
),

),
),

,
(

,
(

,
(

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)

 Sin una heurística sobre qué acciones aplicar,

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

15

Backward Search Methods

(BSM)

 También denominados Regression Planning Methods
 Poco eficientes en problemas grandes
 Consideran sólo operadores relevantes, aquellos que
alcanzan alguno de los objetivos que se desea explorar

 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 BSM
con STRIPS
(Nilsson, pp. 382)

16

BSM, II

 Es importante que los operadores sean

consistentes, es decir, que no
deshagan literales (aquellos que
aparecen en su conjunto D)
» No hay forma de que un operador alcance

un literal λ si dicho literal lo borra el
operador

» En tal caso, una regresión sobre cualquier

conjunción de literales que contenga λ
mediante un operador que elimine λ es F
(dicho estado es imposible de alcanzar)

 El proceso de construcción de

predeces