estado inicial graphplan estado finalusers.exa.unicen.edu.ar/catedras/iaplanning/c2.pdf · planners...
TRANSCRIPT
I t d ió l Al itIntroducción a los Algoritmos de planeamientode planeamiento
2013
Ejemplo - ModeladoEjemplo Modelado
Ejemplo 2 - ModeladoEjemplo 2 Modelado
Estado inicial
Estado Final
Acciones Acciones
GraphPlanGraphPlanIntroducción a los Algoritmos de Planning2013
PlannersPlanners
State Space: el plan como una State-Space: el plan como una secuencia de acciones
Plan-Space: el plan como una secuencia Plan-Space: el plan como una secuencia parcialmente ordenada de acciones
Planning-Graph: una solución intermedia Planning Graph: una solución intermedia
Planning GraphPlanning Graph
La salida es una secuencia de conjuntos de acciones
{ { 1 2} { 3 4} { 5 6 7} } { {a1, a2}, {a3,a4}, {a5,a6,a7} }
GraphplanGraphplan
Alterna entre dos fases: Expansión del grafop g
Extracción de solución Extracción de solución
Descripción del grafo de planningDescripción del grafo de planning
0 I 1 i I + 1
… …0 I - 1 i I + 1
……
… ……
………
Estado Nodos de Nodos dePrecondiciones Efectos
Proposiciones Estado inicial
Nodos de proposición
Nodos de acción
que se mantienenen el siguiente nivel
GraphplanGraphplan
Expansión del grafo: Extiende el grafo de planning avanzando en el tiempo hasta que se alcance una condición necesaria (pero insuficiente) para la existencia del plan
Descripción del grafo de planningDescripción del grafo de planning
AccionesAcciones
I - 1 i I + 1
AccionesAcciones
A1: Pre=[f, a] Pos=[g, h]A1: Pre=[f, a] Pos=[g, h]
A2: Pre=[h] Pos=[a, b]A2: Pre=[h] Pos=[a, b]
ffggA1A1ffA3: Pre=[a, b] Pos=[d]A3: Pre=[a, b] Pos=[d]
aahhaa
ccddA3A3cc
bb bb
Relación de exclusión mutuaRelación de exclusión mutua
Dos instancias de acciones en el nivel i son mutex si: Efectos inconsistentes
Interferencia
Necesidades competitivas
Relación de exclusión mutuaRelación de exclusión mutua
Efectos inconsistentes El efecto de una acción es la negación del g
efecto de otra acción
a
-a
Relación de exclusión mutuaRelación de exclusión mutua
Interferencia Una acción elimina la precondición de otrap
-a
a
Relación de exclusión mutuaRelación de exclusión mutua
Necesidades competitivas Las acciones tienen precondiciones que p q
son mutuamente excluyentes en el nivel i-1
Relación de exclusión mutuaRelación de exclusión mutua
Dos proposiciones en el nivel i son mutex si: Contradicción Soporte inconsistente Soporte inconsistente
Relación de exclusión mutuaRelación de exclusión mutua
Contradicción Una proposición es la negación de otrap p g
a
-aa
Relación de exclusión mutuaRelación de exclusión mutua
Soporte inconsistente Todas las formas de alcanzar las
proposiciones (es decir, las acciones del nivel i-1) son mutex de a pares) p
GraphplanGraphplan
Extracción de solución: Ejecuta una búsqueda hacia atrás en el grafo, buscando un plan que resuelva el problema. Si no encuentra una solución, se repite el ciclo
Extracción de la soluciónExtracción de la solución
El grafo se encuentra en un nivel par i que contiene todas las proposiciones del objetivo
No hay relaciones mutex de pares deNo hay relaciones mutex de pares de proposiciones en el nivel i
Para cada literal del objetivo (presentes en i), elige una acción a del nivel i 1 que alcanceelige una acción a del nivel i-1, que alcance ese sub-objetivo (punto de backtracking)
Extracción de la soluciónExtracción de la solución
Si i t t ( t ) t d l Si a es consistente (no mutex) con todas las acciones elegidas hasta el momento en ese nivel pasa al siguiente nivel Caso contrarionivel, pasa al siguiente nivel. Caso contrario, retrocede a una elección anterior.
Cuando encuentra un conjunto consistente de acciones en el nivel i 1 trata recursivamenteacciones en el nivel i-1, trata recursivamente de encontrar un plan para el conjunto formado por la unión de todas las precondiciones depor la unión de todas las precondiciones de aquellas acciones en el nivel i-2.
Extracción de la soluciónExtracción de la solución
El caso base es el nivel 0 Si las proposiciones están allí presentes se
encontró una solución Caso contrario, si fallan todas las combinaciones
ibl d i t d l i lposibles de acciones en todos los niveles, se extiende el grafo con otro par de niveles de acción y proposicionesy proposiciones
EjemploEjemplo
E t d i i i l b Li i Estado inicial: basura, manosLimpias, tranquilo
Objetivo: desayuno, regalo, not(basura)
Acciones:BarrerCocinar
Precondiciones:Efectos: not(basura), not(manosLimpias)
A i
Precondiciones:manosLimpiasEfectos: desayuno
AspirarPrecondiciones:Efectos: not(basura), not(tranquilo)
EnvolverPrecondiciones: tranquiloEf t lEfectos: regalo
EjemploEjemplo
0 1 2basura basura
Barrer
0 1 2
-basuraBarrer
Aspirar
manosL manosL
-manosLCocinar
tranquilo
manosL
tranquilo
Cocinar
-tranquilodesayuno
Envolver
desayunoregalo
EjemploEjemplo
0 1 2basura
Barrer
basura0 1 2
Barrer
Aspirar-basura
manosL
Cocinar
manosL
-manosL
tranquilo
Cocinar manosL
tranquiloEnvolver -tranquilo
desayunodesayunoregalo
EjemploEjemplo
0 1 2
Objetivo: -basura ^ desayuno ^ regalo
basuraBarrer
basura0 1 2
Barrer
Aspirar-basura
manosL
Cocinar
manosL
-manosL
tranquilo
Cocinar manosL
tranquiloEnvolver -tranquilo
desayunodesayunoregalo
EjemploEjemplo
basuraBarrer
basuraBarrer
Aspirar-basura
manosL
Cocinar
manosL
-manosL
tranquilo
Cocinar manosL
tranquiloEnvolver -tranquilo
desayunodesayunoregalo
EjemploEjemplo
basuraBarrer
basuraBarrer
Aspirar-basura
manosL
Cocinar
manosL
-manosL
tranquilo
Cocinar manosL
tranquiloEnvolver -tranquilo
desayunodesayunoregalo
EjemploEjemplo
0 1 2 3 4basura
Barrer
basura0 1 2
Barrerbasura
3 4
Barrer
Aspirar-basura
Aspirar
-basura
manosL
Cocinar
manosL
-manosL
manosL
-manosL
tranquilo
Cocinar manosL
tranquiloCocinar
manosL
tranquiloEnvolver -tranquilo
desayunoEnvolver
-tranquilo
desayunodesayunoregalo
desayunoregalo
EjemploEjemplo
0 1 2 3 4basura
Barrer
basura0 1 2
Barrerbasura
3 4
Barrer
Aspirar-basura
Aspirar
-basura
manosL
Cocinar
manosL
-manosL
manosL
-manosL
tranquilo
Cocinar manosL
tranquiloCocinar
manosL
tranquiloEnvolver -tranquilo
desayunoEnvolver
-tranquilo
desayunodesayunoregalo
desayunoregalo
EjemploEjemplo
0 1 2 3 4basura
Barrer
basura0 1 2
Barrerbasura
3 4
Barrer
Aspirar-basura
Aspirar
-basura
manosL
Cocinar
manosL
-manosL
manosL
-manosL
tranquilo
Cocinar manosL
tranquiloCocinar
manosL
tranquiloEnvolver -tranquilo
desayunoEnvolver
-tranquilo
desayunodesayunoregalo
desayunoregalo
EjemploEjemplo
0 1 2 3 4basura
Barrer
basura0 1 2
Barrerbasura
3 4
Barrer
Aspirar-basura
Aspirar
-basura
manosL
Cocinar
manosL
-manosL
manosL
-manosL
tranquilo
Cocinar manosL
tranquiloCocinar
manosL
tranquiloEnvolver -tranquilo
desayunoEnvolver
-tranquilo
desayunodesayunoregalo
desayunoregalo
EjemploEjemplo
0 1 2 3 40 1 2
Barrer
3 4
-basura
manosL
Cocinar
tranquilo
Cocinar
tranquilotranquilo tranquilo
desayunoEnvolver
desayunodesayuno desayunoregalo
Problema de CapacidadProblema de Capacidad
Se desea transportar en un coche con capacidad para cuatro personas a un p p pgrupo de personas a lo largo de un recorridorecorrido.