Reformulacion polinomial de problemas de
plani
cacion con objetivos temporales
Jorge Torres Villarrubia
Profesor Supervisor: Jorge Baier
Universidad Catolica de Chile...
Contenidos
1 Motivacion y Marco Teorico
2 Pregunta de Investigacion
3 Solucion Propuesta
4 Limitaciones de la solucion...
Contenidos
1 Motivacion y Marco Teorico
2 Pregunta de Investigacion
3 Solucion Propuesta
4 Limitaciones de la solucion...
Motivacion
Estado inicial
Jorge Torres Villarrubia Motivacion y Marco Teorico 4 / 38
Motivacion
Estado inicial Estado
nal
Jorge Torres Villarrubia Motivacion y Marco Teorico 4 / 38
Motivacion
Estado inicial Estado
nal
Como se puede terminar el cubo Rubik?
Jorge Torres Villarrubia Motivacion y Marco Teorico 4 / 38
Motivacion
Usar Plani
cacion Clasica:
Objetos: Interactuan con el mundo
Fluentes: Predicados que indican el estado de los objetos y del
mundo...
can el valor de verdad de los
uentes
Jorge Torres Villarrubia Motivacion y Marco Teorico 5 / 38
Motivacion
Usar Plani
cacion Clasica:
Objetos: Interactuan con el mundo
Fluentes: Predicados que indican el estado de los objetos y del
mundo...
can el valor de verdad de los
uentes
Planners son programas que resuelven problemas de plani
cacion
clasica.
Existen muy buenas implementaciones de Planners
Jorge Torres Villarrubia Motivacion y Marco Teorico 5 /...
Motivacion
Espacio de busqueda: Mundo de bloques1
1
Fuente: http://homepage.cs.uiowa.edu/shzhang/c145/notes/10-Planning...
Motivacion
Ejemplo: Mundo de bloques (Formalizacion)
Objetos: A, B, C, Mesa
Fluentes: on(x; y); x esta sobre y
Accione...
Motivacion
Hay un detalle con problemas de Plani
cacion Clasica:
Podemos garantizar que el plan eventualmente arme la pila
A C B antes de armar la pila A B C?
Jorge Tor...
Motivacion
Hay un detalle con problemas de Plani
cacion Clasica:
Podemos garantizar que el plan eventualmente arme la pila
A C B antes de armar la pila A B C?
Si tuvies...
Motivacion
Hay un detalle con problemas de Plani
cacion Clasica:
Podemos garantizar que el plan eventualmente arme la pila
A C B antes de armar la pila A B C?
Si tuvies...
Motivacion
Hay un detalle con problemas de Plani
cacion Clasica:
Podemos garantizar que el plan eventualmente arme la pila
A C B antes de armar la pila A B C?
Si tuvies...
cacion?
Jorge Torres Villarrubia Motivacion y Marco Teorico 8 / 38
Motivacion
Usamos Logicas temporales2 para expresar los objetivos
2Logicas temporales lineales sobre secuencias
nitas (f-LTL)
Jorge Torres Villarrubia Motivacion y Marco Teorico 9 / 38
Motivacion
Usamos Logicas temporales2 para expresar los objetivos
Logicas temporales = Logica proposicional (Variables; ...
nitas (f-LTL)
Jorge Torres Villarrubia Motivacion y Marco Teorico 9 / 38
Motivacion
Ejemplo: Secuencia que satisface (on(A; C) ^ on(C;B) ^ on(B; Mesa))
Jorge Torres Villarrubia Motivacion y Mar...
Motivacion
Ejemplo: Secuencia que satisface (on(B; Mesa) _ on(B; C))
Jorge Torres Villarrubia Motivacion y Marco Teorico...
Motivacion
Un teorema importante:
Jorge Torres Villarrubia Motivacion y Marco Teorico 12 / 38
Motivacion
Un teorema importante:
Teorema (Baier,McIlraith,2006)
Es posible reformular un problema de plani
cacion con objetivos
temporales a otro problema de plani
cacion clasica.
Jorge Torres Villarrubia Motivacion y Marco Teorico 12 / 38
Motivacion
Un teorema importante:
Teorema (Baier,McIlraith,2006)
Es posible reformular un problema de plani
cacion con objetivos
temporales a otro problema de plani
cacion clasica.
No es necesario implementar planners!
Podemos usar uno ya existente
Cual es la clave de la reformulacio...
Motivacion
Un teorema importante:
Teorema (Baier,McIlraith,2006)
Es posible reformular un problema de plani
cacion con objetivos
temporales a otro problema de plani
cacion clasica.
No es necesario implementar planners!
Podemos usar uno ya existente
Cual es la clave de la reformulacio...
ca si una formula temporal es
satisfacible usando automatas no deterministas
Jorge Torres Villarrubia Motivacion y Marco...
Motivacion
Un ejemplo
Ejemplo
Automata para p
; ;; fpg
fpg
start q0 q1
Transiciones del automata son simuladas con ...
Motivacion
Otro Ejemplo
Automata para p1 ^ p2
fp1g
start q0
;; fp1g
q1
fp1; p2g
q2
q3
;
fp2g
fp2g; fp1; p2g
;...
Motivacion
Que pasara si la formula es de la forma p1 ^ p2 ^ : : : ^ pn?
Jorge Torres Villarrubia Motivacion y Marco Teo...
Motivacion
Que pasara si la formula es de la forma p1 ^ p2 ^ : : : ^ pn?
El automata alcanza a tener 2n estados!
Para e...
cacion
con objetivos temporales
Jorge Torres Villarrubia Motivacion y Marco Teorico 15 / 38
Contenidos
1 Motivacion y Marco Teorico
2 Pregunta de Investigacion
3 Solucion Propuesta
4 Limitaciones de la solucion...
Pregunta de Investigacion
Como es posible reformular problemas de
plani
cacion con objetivos temporales a
problemas de plani
cacion clasica en forma
efectiva y e
of 53

Reformulacion polinomial de problemas de planificacion con objetivos temporales

Presentación Seminario
Published on: Mar 4, 2016
Published in: Science      
Source: www.slideshare.net


Transcripts - Reformulacion polinomial de problemas de planificacion con objetivos temporales

  • 1. Reformulacion polinomial de problemas de plani
  • 2. cacion con objetivos temporales Jorge Torres Villarrubia Profesor Supervisor: Jorge Baier Universidad Catolica de Chile 12 de septiembre de 2014 Jorge Torres Villarrubia 1 / 38
  • 3. Contenidos 1 Motivacion y Marco Teorico 2 Pregunta de Investigacion 3 Solucion Propuesta 4 Limitaciones de la solucion 5 Estado de la investigacion Jorge Torres Villarrubia 2 / 38
  • 4. Contenidos 1 Motivacion y Marco Teorico 2 Pregunta de Investigacion 3 Solucion Propuesta 4 Limitaciones de la solucion 5 Estado de la investigacion Jorge Torres Villarrubia Motivacion y Marco Teorico 3 / 38
  • 5. Motivacion Estado inicial Jorge Torres Villarrubia Motivacion y Marco Teorico 4 / 38
  • 6. Motivacion Estado inicial Estado
  • 7. nal Jorge Torres Villarrubia Motivacion y Marco Teorico 4 / 38
  • 8. Motivacion Estado inicial Estado
  • 9. nal Como se puede terminar el cubo Rubik? Jorge Torres Villarrubia Motivacion y Marco Teorico 4 / 38
  • 10. Motivacion Usar Plani
  • 11. cacion Clasica: Objetos: Interactuan con el mundo Fluentes: Predicados que indican el estado de los objetos y del mundo Acciones: Afectan el mundo Precondiciones: Condicion para que la accion se pueda ejecutar Efectos: Modi
  • 12. can el valor de verdad de los uentes Jorge Torres Villarrubia Motivacion y Marco Teorico 5 / 38
  • 13. Motivacion Usar Plani
  • 14. cacion Clasica: Objetos: Interactuan con el mundo Fluentes: Predicados que indican el estado de los objetos y del mundo Acciones: Afectan el mundo Precondiciones: Condicion para que la accion se pueda ejecutar Efectos: Modi
  • 15. can el valor de verdad de los uentes Planners son programas que resuelven problemas de plani
  • 16. cacion clasica. Existen muy buenas implementaciones de Planners Jorge Torres Villarrubia Motivacion y Marco Teorico 5 / 38
  • 17. Motivacion Espacio de busqueda: Mundo de bloques1 1 Fuente: http://homepage.cs.uiowa.edu/shzhang/c145/notes/10-Planning-6p.pdf Jorge Torres Villarrubia Motivacion y Marco Teorico 6 / 38
  • 18. Motivacion Ejemplo: Mundo de bloques (Formalizacion) Objetos: A, B, C, Mesa Fluentes: on(x; y); x esta sobre y Acciones: move(x; y; z); (mover x desde y hasta z) Precondicion: on(x; y) ^ 8w(:on(w; x)) ^ (z6= Mesa ! (8u(:on(u; z)))) Efecto: ! (:on(x; y) ^ on(x; z)) Estado inicial: on(C; A) ^ on(A; Mesa) ^ on(B; Mesa) Estado objetivo: on(A; B) ^ on(B; C) ^ on(C; Mesa) Jorge Torres Villarrubia Motivacion y Marco Teorico 7 / 38
  • 19. Motivacion Hay un detalle con problemas de Plani
  • 20. cacion Clasica: Podemos garantizar que el plan eventualmente arme la pila A C B antes de armar la pila A B C? Jorge Torres Villarrubia Motivacion y Marco Teorico 8 / 38
  • 21. Motivacion Hay un detalle con problemas de Plani
  • 22. cacion Clasica: Podemos garantizar que el plan eventualmente arme la pila A C B antes de armar la pila A B C? Si tuviesemos que generar un plan para que un auto viaje de Santiago a Valparaso: Podemos garantizar que el auto eventualmente llegue a una estacion de bencina y que siempre tenga al menos 1/4 del estanque lleno? Jorge Torres Villarrubia Motivacion y Marco Teorico 8 / 38
  • 23. Motivacion Hay un detalle con problemas de Plani
  • 24. cacion Clasica: Podemos garantizar que el plan eventualmente arme la pila A C B antes de armar la pila A B C? Si tuviesemos que generar un plan para que un auto viaje de Santiago a Valparaso: Podemos garantizar que el auto eventualmente llegue a una estacion de bencina y que siempre tenga al menos 1/4 del estanque lleno? No es posible garantizar que el plan cumpla las restricciones que deseamos Jorge Torres Villarrubia Motivacion y Marco Teorico 8 / 38
  • 25. Motivacion Hay un detalle con problemas de Plani
  • 26. cacion Clasica: Podemos garantizar que el plan eventualmente arme la pila A C B antes de armar la pila A B C? Si tuviesemos que generar un plan para que un auto viaje de Santiago a Valparaso: Podemos garantizar que el auto eventualmente llegue a una estacion de bencina y que siempre tenga al menos 1/4 del estanque lleno? No es posible garantizar que el plan cumpla las restricciones que deseamos Que debemos hacer con los problemas de plani
  • 27. cacion? Jorge Torres Villarrubia Motivacion y Marco Teorico 8 / 38
  • 28. Motivacion Usamos Logicas temporales2 para expresar los objetivos 2Logicas temporales lineales sobre secuencias
  • 29. nitas (f-LTL) Jorge Torres Villarrubia Motivacion y Marco Teorico 9 / 38
  • 30. Motivacion Usamos Logicas temporales2 para expresar los objetivos Logicas temporales = Logica proposicional (Variables; _; ^;:) + Operadores temporales ( ;;; U) ': Next ' ': Always ' ': Eventually ' 'U : ' until Evaluar con Secuencias de subconjuntos de variables 2Logicas temporales lineales sobre secuencias
  • 31. nitas (f-LTL) Jorge Torres Villarrubia Motivacion y Marco Teorico 9 / 38
  • 32. Motivacion Ejemplo: Secuencia que satisface (on(A; C) ^ on(C;B) ^ on(B; Mesa)) Jorge Torres Villarrubia Motivacion y Marco Teorico 10 / 38
  • 33. Motivacion Ejemplo: Secuencia que satisface (on(B; Mesa) _ on(B; C)) Jorge Torres Villarrubia Motivacion y Marco Teorico 11 / 38
  • 34. Motivacion Un teorema importante: Jorge Torres Villarrubia Motivacion y Marco Teorico 12 / 38
  • 35. Motivacion Un teorema importante: Teorema (Baier,McIlraith,2006) Es posible reformular un problema de plani
  • 36. cacion con objetivos temporales a otro problema de plani
  • 37. cacion clasica. Jorge Torres Villarrubia Motivacion y Marco Teorico 12 / 38
  • 38. Motivacion Un teorema importante: Teorema (Baier,McIlraith,2006) Es posible reformular un problema de plani
  • 39. cacion con objetivos temporales a otro problema de plani
  • 40. cacion clasica. No es necesario implementar planners! Podemos usar uno ya existente Cual es la clave de la reformulacion? Jorge Torres Villarrubia Motivacion y Marco Teorico 12 / 38
  • 41. Motivacion Un teorema importante: Teorema (Baier,McIlraith,2006) Es posible reformular un problema de plani
  • 42. cacion con objetivos temporales a otro problema de plani
  • 43. cacion clasica. No es necesario implementar planners! Podemos usar uno ya existente Cual es la clave de la reformulacion? Teorema (Baier, 2010) Existe un algoritmo que veri
  • 44. ca si una formula temporal es satisfacible usando automatas no deterministas Jorge Torres Villarrubia Motivacion y Marco Teorico 12 / 38
  • 45. Motivacion Un ejemplo Ejemplo Automata para p ; ;; fpg fpg start q0 q1 Transiciones del automata son simuladas con acciones del problema Estados pueden ser simulados como uentes Jorge Torres Villarrubia Motivacion y Marco Teorico 13 / 38
  • 46. Motivacion Otro Ejemplo Automata para p1 ^ p2 fp1g start q0 ;; fp1g q1 fp1; p2g q2 q3 ; fp2g fp2g; fp1; p2g ;; fp2g ;; fp1g; fp2g; fp1g; fp1; p2g fp1; p2g Jorge Torres Villarrubia Motivacion y Marco Teorico 14 / 38
  • 47. Motivacion Que pasara si la formula es de la forma p1 ^ p2 ^ : : : ^ pn? Jorge Torres Villarrubia Motivacion y Marco Teorico 15 / 38
  • 48. Motivacion Que pasara si la formula es de la forma p1 ^ p2 ^ : : : ^ pn? El automata alcanza a tener 2n estados! Para este caso, esta cantidad no se puede disminuir Necesitamos otra manera de resolver problemas de plani
  • 49. cacion con objetivos temporales Jorge Torres Villarrubia Motivacion y Marco Teorico 15 / 38
  • 50. Contenidos 1 Motivacion y Marco Teorico 2 Pregunta de Investigacion 3 Solucion Propuesta 4 Limitaciones de la solucion 5 Estado de la investigacion Jorge Torres Villarrubia Pregunta de Investigacion 16 / 38
  • 51. Pregunta de Investigacion Como es posible reformular problemas de plani
  • 52. cacion con objetivos temporales a problemas de plani
  • 53. cacion clasica en forma efectiva y e
  • 54. ciente? Jorge Torres Villarrubia Pregunta de Investigacion 17 / 38
  • 55. Contenidos 1 Motivacion y Marco Teorico 2 Pregunta de Investigacion 3 Solucion Propuesta 4 Limitaciones de la solucion 5 Estado de la investigacion Jorge Torres Villarrubia Solucion Propuesta 18 / 38
  • 56. Solucion Propuesta Utilizar otro tipo de automatas: Automatas alternantes (AA) Introducir uentes y acciones nuevas para simular las transiciones de dicho automata Jorge Torres Villarrubia Solucion Propuesta 19 / 38
  • 57. Solucion Propuesta Considere el siguiente automata no determinista: Ejemplo 1 0; 1 0 start q0 q1 q2 Jorge Torres Villarrubia Solucion Propuesta 20 / 38
  • 58. Solucion Propuesta Considere el siguiente automata no determinista: Ejemplo 1 0; 1 0 start q0 q1 q2 (q1; 0) = q1 _ q2 Jorge Torres Villarrubia Solucion Propuesta 20 / 38
  • 59. Solucion Propuesta Considere el siguiente automata no determinista: Ejemplo 1 0; 1 0 start q0 q1 q2 (q1; 0) = q1 _ q2 NFA: Disyunciones AA: Disyunciones + Conjunciones Jorge Torres Villarrubia Solucion Propuesta 20 / 38
  • 60. Solucion Propuesta Ejemplo Queremos procesar la palabra w = 101 en el automata alternante: start q0 q1 q2 q3 q4 1 1 0; 1 0 0; 1 0; 1 1 Jorge Torres Villarrubia Solucion Propuesta 21 / 38
  • 61. Solucion Propuesta Ejemplo w = 101 start q0 q1 q2 q3 q4 1 1 0; 1 0 0; 1 0; 1 1 Jorge Torres Villarrubia Solucion Propuesta 22 / 38
  • 62. Solucion Propuesta Ejemplo w = 101 start q0 q1 q2 q3 q4 1 1 0; 1 0 0; 1 0; 1 1 Jorge Torres Villarrubia Solucion Propuesta 23 / 38
  • 63. Solucion Propuesta Ejemplo w = 101 start q0 q1 q2 q3 q4 1 1 0; 1 0 0;1 0; 1 1 Jorge Torres Villarrubia Solucion Propuesta 24 / 38
  • 64. Solucion Propuesta Ejemplo w = 101 start q0 q1 q2 q3 q4 1 1 0; 1 0 0; 1 0; 1 1 Jorge Torres Villarrubia Solucion Propuesta 25 / 38
  • 65. Solucion Propuesta Podemos usar automatas alternantes para veri
  • 66. car si una formula temporal es satisfacible! Como construir los estados? Jorge Torres Villarrubia Solucion Propuesta 26 / 38
  • 67. Solucion Propuesta Podemos usar automatas alternantes para veri
  • 68. car si una formula temporal es satisfacible! Como construir los estados? Calcular las subformulas de ' Ejemplo sub((p ^ q)) = f(p ^ q); p ^ q; p; qg Jorge Torres Villarrubia Solucion Propuesta 26 / 38
  • 69. Solucion Propuesta Podemos usar automatas alternantes para veri
  • 70. car si una formula temporal es satisfacible! Como construir los estados? Calcular las subformulas de ' Ejemplo sub((p ^ q)) = f(p ^ q); p ^ q; p; qg Teorema Toda formula temporal tiene una cantidad lineal de subformulas Jorge Torres Villarrubia Solucion Propuesta 26 / 38
  • 71. Solucion Propuesta Como reformular el problema con objetivos temporales? Jorge Torres Villarrubia Solucion Propuesta 27 / 38
  • 72. Solucion Propuesta Que acciones usar? Jorge Torres Villarrubia Solucion Propuesta 28 / 38
  • 73. Solucion Propuesta Como implementamos la reformulacion? Problemas de plani
  • 74. cacion especi
  • 75. cados en un formato estandar: PDDL Convertir un archivo en PDDL a otro en PDDL usando Prolog Que hacemos con el problema reformulado? Usamos un planner: Fast Forward3 3Creado por Jorg Homann en el a~no 2000 Jorge Torres Villarrubia Solucion Propuesta 29 / 38
  • 76. Resultados Preliminares Usamos diferentes reformulaciones considerando lo siguiente: Usar literales positivos o negativos en el objetivo auxiliar (LP o LN) Forzar o no forzar orden de los estados a sincronizar (F o NF) 4 tipos de reformulaciones diferentes LN LP NF Tipo 1 Tipo 3 F Tipo 2 Tipo 4 Jorge Torres Villarrubia Solucion Propuesta 30 / 38
  • 77. Resultados Preliminares Usamos diferentes reformulaciones considerando lo siguiente: Usar literales positivos o negativos en el objetivo auxiliar (LP o LN) Forzar o no forzar orden de los estados a sincronizar (F o NF) 4 tipos de reformulaciones diferentes LN LP NF Tipo 1 Tipo 3 F Tipo 2 Tipo 4 Tipos 3 y 4 tienen mejor desempe~no. Jorge Torres Villarrubia Solucion Propuesta 31 / 38
  • 78. Resultados Preliminares Objetivos de la forma: ^n i=1 (pi ^ qi ) n Tipo 1 Tipo 2 Tipo 3 Tipo 4 LN+NF LN+F LP+NF LP+F 1 139 144 49 78 2 719 758 353 370 3 3351 3211 750 841 4 15575 11051 2461 1987 Cuadro: Numero de estados explorados por objetivo y reformulacion (Mundo de bloques) Jorge Torres Villarrubia Solucion Propuesta 32 / 38
  • 79. Contenidos 1 Motivacion y Marco Teorico 2 Pregunta de Investigacion 3 Solucion Propuesta 4 Limitaciones de la solucion 5 Estado de la investigacion Jorge Torres Villarrubia Limitaciones de la solucion 33 / 38
  • 80. Limitaciones de la solucion Hay ciertas limitaciones: Ciertas reformulaciones son mejores para ciertos planners y pueden generar pobre desempe~no para otros Requiere conocer muy bien las propiedades del planner Planes encontrados en el problema auxiliar son mas largos Jorge Torres Villarrubia Limitaciones de la solucion 34 / 38
  • 81. Contenidos 1 Motivacion y Marco Teorico 2 Pregunta de Investigacion 3 Solucion Propuesta 4 Limitaciones de la solucion 5 Estado de la investigacion Jorge Torres Villarrubia Estado de la investigacion 35 / 38
  • 82. Estado de la investigacion Finalizando demostracion de teorema de correctitud y completitud Haciendo mas pruebas con distintos dominios, objetivos y condiciones iniciales Buscando y probando otras reformulaciones Jorge Torres Villarrubia Estado de la investigacion 36 / 38
  • 83. Trabajo a futuro Utilizar otros planners Hacer comparaciones experimentales con antiguo traductor Trabajar en paper Redactar tesis Posibilidad de trabajar en un planner especializado Jorge Torres Villarrubia Estado de la investigacion 37 / 38
  • 84. Gracias! Jorge Torres Villarrubia Estado de la investigacion 38 / 38

Related Documents