Strips

Seminario Planificación y STRIPS
Inteligencia Artificial
5o Informática
IA curso 2012-2013
CCIA

Octubre 2012

IA–1213 (CCIA)

Seminario planificación

Octubre-2012

1 / 11

Planificación en IA
Plan: secuencia de acciones individuales que permiten alcanzar
una meta a partir de una situación inicial
Planificación en IA: procedimiento automático para encontrar un
plan para un problema concreto
Sepueden aplicar directamente los métodos conocidos de
búsqueda en espacio de estados pero en ocasiones presentan
problemas de eficiencia
Acciones no relevantes ⇒ alto factor de ramificación

Existen formalismos específicos para representar problemas de
planificación
Representación de estados: descripción de la situación del
”mundo”
en todo momento se conoce el estado del ”mundo”
sólo hay un”agente” que pueda cambiar el estado del ”mundo”

Representación de acciones: modifican el estado del ”mundo”
se suponen instantáneas
se supone que sus efectos son deterministas

Nota: las restriciones anteriores definen la ”planificación clásica”
IA–1213 (CCIA)

Seminario planificación

Octubre-2012

2 / 11

Introducción a STRIPS
STRIPS: STanford Research Institute Problem Solver [Fikes y
Nilsson 1971]Planificador automático usado en aplicaciones de robótica
Utiliza un formalismo basado en lógica para representar estados y
operadores
Estado = conjunto de predicados lógicos
Operador añade y/o elimina predicados al estado actual
Sirvió como modelo a la mayor parte de planificadores posteriores

Ejemplo de planificador lineal
Realiza una búsqueda regresiva en el espacio de estados
Parte de ladescripción del estado objetivo y selecciona operadores
y estados hacia atrás
Descompone el estado meta inicial en sucesivas submetas hasta
alcanzar una situación que corresponda con la descripción del
estado inicial

IA–1213 (CCIA)

Seminario planificación

Octubre-2012

3 / 11

Operadores STRIPS
Operador STRIPS: representa una acción mediante 3
componentes
precondiciones (PC): lista de átomos quetienen que ser ciertos
en el estado para que la acción pueda sera aplicada
lista borrar (B): lista de átomos que dejan de ser ciertos una vez
aplicada la acción
lista añadir (A): lista de átomos que pasan a ser ciertos una vez
aplicada la acción
Nota: listas A y B pueden unirse (lista Efectos) indicando los
atomos de B negados
Solo especifica lo que cambia en el ”mundo” con la ejecución de
la acciónOperadores parametrizables: átomos en listas PC, A y B pueden
contener variables que se instanciarán al aplicar el operador
IA–1213 (CCIA)

Seminario planificación

Octubre-2012

4 / 11

Ejemplos STRIPS
Apilar el bloque en el brazo sobre otro

Quitar un bloque que estaba sobre otro
DESAPILAR(x,y)
P: SOBRE(x,y), LIBRE(x), BRAZO_LIBRE
B: SOBRE(x,y), LIBRE(x), BRAZO_LIBRE
A: COGIDO(x), LIBRE(y)APILAR(x,y)
P: LIBRE(y), COGIDO(x)
B: LIBRE(y), COGIDO(x)
A: BRAZO_LIBRE, SOBRE(x,y), LIBRE(x)

Coger un bloque de la mesa con el brazo

Soltar un bloque en la mesa
SOLTAR(x)
P: COGIDO(x)
B: COGIDO(x)
A: EN_MESA(x), BRAZO_LIBRE, LIBRE(x)

COGER(x)
P: LIBRE(x), EN_MESA(x), BRAZO_LIBRE
B: LIBRE(x), EN_MESA(x), BRAZO_LIBRE
A: COGIDO(x)

Estado inicial

A

C
B

Estado final

D

A
B

C
D

Solución (plan)DESAPILAR(C,B)
APILAR(C,D)
COGER(A)
APILAR(A,B)

Demo: http://aispace.org/planning

IA–1213 (CCIA)

Seminario planificación

Octubre-2012

5 / 11

Búsqueda en planificación (espacio de estados)
Idea: aplicar los métodos de búsqueda en espacio de estados
Operadores = acciones posibles
Solución = secuencia de acciones desde estado inicial al final

Búsqueda progresiva (hacia adelante)
Ineficiente enaplicaciones prácticas
Gran núm. de acciones irrelevantes (no hacen avanzar el plan) a
evaluar en cada estado ⇒ alto factor de ramificación
Dificultad para definir heurísticas generales útiles

Búsqueda regresiva (hacia atrás)
Comienza en un objetivo y para cada uno de los estado se generan
los posibles predecesores
Predecesor de Ei : cualquier estado Ej para el que existe una
sustitución...