Inteligencia artificial

Planificaci´n (planning) o
Definici´n: Proceso de encontrar una secuencia de acciones que permiten o alcanzar un objetivo.

Inteligencia Artificial (2009)

Ya vimos un agente elemental de planning: el agente de resoluci´n de o u problemas basado en b´squeda Es posible hacer planning con los 3 enfoques vistos para representar acciones y cambio:

´ Planning (Planificacion) 1. Representaci´nStrips o 2. Situation Calculus 3. Event Calculus Nos centraremos en planificadores basados en la representaci´n STRIPS o

Planning (Planificaci´n) o

1

Planning (Planificaci´n) o

3

Aspectos a abordar
♦ Introducci´n a planning o ♦ B´squeda vs. planning u ♦ Planning de orden parcial ♦ Combinando planning y ejecuci´n o Bibliograf´ Cap´ ıa: ıtulo 11 - Russell (Versi´n anterior) oPlanificaci´n en Situation Calculus o

La siguiente consulta da un plan para que Rob sostenga la llave k1 ? llevando(rob,k1,S). S = realizar(alzar(rob,k1), realizar(mover(rob,o103,mail), realizar(mover(rob,o109,o103), inicio)))
Planning (Planificaci´n) o 2 Planning (Planificaci´n) o 4

Planificaci´n con Representaci´n STRIPS o o
Difiere con resoluci´n de problemas basada en b´squeda en la forma o u derepresentar: 1. Estados 2. Objetivos 3. Acciones 4. Planes

Representaci´n de estados: planning o
Cada estado es representado por sentencias de un lenguaje formal (usual/ subconjunto de FOL).
A C B A B C
Estado Objetivo

Estado Inicial

En STRIPS, un estado es una conjunci´n de literales ground sin s´ o ımbolos de funci´n. O sea, predicados aplicados a s´ o ımbolos constantes posible/negados. Ejemplo: Situaci´n Inicial: enlamesa(b), enlamesa(a), encima(c,a), o libre(b), libre(c), vacio. Objetivo: enlamesa(c), encima(b,c), encima(a,b), libre(a), vacio.
Planning (Planificaci´n) o 5 Planning (Planificaci´n) o 7

Representaci´n de estados: resoluci´n de problemas o o
Cada estado es una descripci´n de estado completa (arbitraria). Ejemplo: o
A C B A B C
Estado Objetivo

ObjetivosResoluci´n de problemas: o ♦ los objetivos son cajas negras. ♦ la unica informaci´n sobre el objetivo es provista mediante: ´ o 1) el test de objetivo: objetivo([b,c,m]) 2) la funci´n heur´ o ıstica: h(Est,N). Planning STRIPS: ♦ los objetivos se describen mediante conjunciones de literales (que pueden tener variables). Ejemplo: enlamesa(c), encima(b,c), encima(a,b), libre(a), vacio. ♦ Permite usarenfoques divide y triunfar´s y abordar sub-objetivos. a

Estado Inicial

Estado: una lista [A,B,C] con la ubicaci´n del bloque respectivo: o m: sobre la mesa. r: sostenido por el brazo rob´tico. o a,b,c: cubo sobre el cual est´ apoyado. a Estado inicial: [m,m,a] Estado objetivo: [b,c,m]
Planning (Planificaci´n) o 6

Planning (Planificaci´n) o

8

Acciones
Resoluci´n de problemas: o ♦Las acciones son programas que en base a descripciones completas de estados generan descripciones completas de estados. sucesor(dejarenmesa(a), [r,B,C], Planning STRIPS: ♦ las acciones son descripciones l´gicas de precondiciones y efectos. o ´ Accion: dejarenmesa(X) Precondiciones: sosteniendo(X) Lista delete: sosteniendo(X) Lista add: vacio, enlamesa(X), libre(X) [m,B,C]).

Representaci´n gr´ficade acciones STRIPS o a
´ Accion: Buy(x) ´ Precondicion: At(p), Sells(p, x) Efecto: Have(x) Representaci´n gr´fica o a

At(p) Sells(p,x)
Buy(x)

Have(x)

Planning (Planificaci´n) o

9

Planning (Planificaci´n) o

11

Notaci´n de acciones STRIPS o
♦ La acci´n se identifica por el nombre y su lista de par´metros. o a ♦ La precondici´n es una lista de literales positivos (si aparecenvariables o deben tambi´n figurar en la lista de argumentos de la acci´n) e o ♦ En algunos casos en lugar de las listas delete y add, se especifica s´lo o el efecto mediante literales positivos y negativos. En lugar de (notaci´n usada en Poole): o ´ Accion: dejarenmesa(X) Precondiciones: sosteniendo(X) Lista delete: sosteniendo(X) Lista add: vacio, enlamesa(X), libre(X) Se puede usar (notaci´n usada...