Planeacion

Inteligencia Artificial I

Curso 2006–2007

Tema 8: Planificaci´n o
Jos´ L. Ruiz Reina e

Dpto. de Ciencias de la Computaci´n e Inteligencia Artificial o

Universidad de Sevilla

IA-I 2006–2007

Cc Ia

Planificaci´n o

8.1

Planificaci´n en IA o
x

Planificar: encontrar una secuencia de acciones que alcanzan un determinado objetivo si se ejecutan desde un determinado estadoinicial. Plan: secuencia de acciones que consiguen el objetivo Aplicaciones del mundo real:
u u u

x

x

Rob´tica o Fabricaci´n mediante ensamblado de componentes o Misiones espaciales

x

Planning vs Scheduling

IA-I 2006–2007

Cc Ia

Planificaci´n o

8.2

El problema de la planificaci´n en IA o
x

Cuestiones a abordar:
u

Representaci´n del mundo y de las acciones que lotransforman o Representaci´n de planes o Algoritmos de b´ squeda de planes u Minimizar los recursos consumidos por el plan Tiempo en el que se realiza cada acci´n o Monitorizar la ejecuci´n del plan, revis´ndolo en caso de errores o contingencias o a

u

u u u u

x

Por simplificar, en este cap´ ıtulo supondremos:
u u

Acciones deterministas, totalmente definidas por su especificaci´n oHip´tesis del mundo cerrado o

IA-I 2006–2007

Cc Ia

Planificaci´n o

8.3

Planificaci´n y b´squeda en espacio de estados o u
x

Solucionar un problema de planificaci´n usando los algoritmos ya vistos o de b´ squeda en espacio de estados no funciona en un problema de u escala real, por los siguientes motivos:
u u

Descripci´n de los estados en el mundo real extremadamente compleja o Grancantidad de posibles acciones, muchas de ellas irrelevantes para la consecuci´n o del objetivo final Las acciones s´lo cambian una peque˜ a porci´n del mundo (el problema del marco) o n o Necesitamos heur´ ısticas independientes del dominio La necesidad de una acci´n puede detectarse sin necesidad de que se haya decidido o las acciones previas (compromiso m´ ınimo) A veces es aconsejabledescomponer en subproblemas m´s simples a

u u u

u

x

Idea: usar la l´gica para representar estados, acciones y objetivos o
u

Y algoritmos espec´ ıficos que operan sobre esta representaci´n o

IA-I 2006–2007

Cc Ia

Planificaci´n o

8.4

Un formalismo l´gico: STRIPS o
x

Un lenguaje para representar problemas de planificaci´n: o
u u u u

Constantes: objetos del mundo (en may´sculas) u Variables para representar cualquier objeto (en min´ sculas) u S´ ımbolos de predicados (para expresar propiedades de los objetos) S´ ımbolos de acciones (para representar operadores)

x

Terminolog´ ıa:
u

Atomos: f´rmulas de la forma P (o1, . . . , on), donde P es un s´ o ımbolo de predicado y cada oi es una constante o una variable Literales: ´tomos o negaci´n de ´tomos a o aLiterales cerrados: sin variables

u u x

Estados: conjunci´n de literales cerrados o
u

Hip´tesis del mundo cerrado: las condiciones que no se mencionan se suponen falsas o
Cc Ia

IA-I 2006–2007

Planificaci´n o

8.5

Ejemplo: el mundo de los bloques
x

Ejemplo cl´sico en planificaci´n. a o Elementos que intervienen:
u u u u

x

Una superficie plana. Una serie de bloques c´bicos. u Un brazo robotizado, que puede coger un bloque cada vez. Un bloque puede estar sobre la mesa o apilado sobre otro bloque.

B C
IA-I 2006–2007

A
Cc Ia

D
Planificaci´n o 8.6

Representaci´n de estados en el mundo de los bloques o
x

Descripci´n de un estado: o

B C A D

DESPEJADO(B), DESPEJADO(C), DESPEJADO(D), BRAZOLIBRE, SOBRE(B,A) SOBRELAMESA(C), SOBRELAMESA(D),SOBRELAMESA(A)
x

Predicados en el mundo de los bloques:
DESPEJADO(x), el bloque x est´ despejado. a BRAZOLIBRE, el brazo no agarra ning´n bloque. u SOBRELAMESA(x), el bloque x est´ sobre la mesa. a SOBRE(x,y), el bloque x est´ sobre el y. a AGARRADO(x), el bloque X est´ sujeto por el brazo. a

IA-I 2006–2007

Cc Ia

Planificaci´n o

8.7

Representaci´n de objetivos en STRIPS o
x...