![Page 1: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/1.jpg)
PLANIFICACION AUTOMATICA
Daniel Borrajo
Universidad Carlos III de Madrid
Planificacion Automatica. Tekniker, 2012
![Page 2: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/2.jpg)
Indice
1 IntroduccionConcepto de PlanificacionRepresentacionBusqueda
2 Planificacion clasica
3 Planificacion neoclasica
4 Heurıstica
5 Otras cuestiones
![Page 3: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/3.jpg)
Indice
1 IntroduccionConcepto de PlanificacionRepresentacionBusqueda
2 Planificacion clasica
3 Planificacion neoclasica
4 Heurıstica
5 Otras cuestiones
![Page 4: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/4.jpg)
Planificacion
![Page 5: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/5.jpg)
¿Que es planificacion?
• Empresarios: planes de la empresa• Abogados: planes de defensa del cliente• Industriales: planes de movimiento de robots• Arquitectos: planes de diseno de edificios• Informaticos: planes de desarrollo del sistema• Telecomunicaciones: planes de conexion• Ejercito: planes de ataque/defensa• Logıstica: planes para transportar objetos
![Page 6: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/6.jpg)
¿Que tienen en comun?
Busqueda en un espacio de problemas• Estado o situacion: descripcion instantanea• Accion u Operador: transformacion de un estado en otro• Estado inicial: situacion de partida• Objetivo o meta: descripcion de condiciones que se tienen
que dar para considerar por terminado el proceso• Plan: secuencia de operadores que permiten pasar del
estado inicial a un estado en el que se cumplan losobjetivos
• Heurısticas: conocimiento que permite obtenereficientemente el plan
![Page 7: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/7.jpg)
¿Que es la planificacion?
Planificacion• Dados:
• un modelo del dominio (lenguaje PDDL): conjunto deacciones
• un problema: un estado inicial, un conjunto de metas, unametrica
• Obtener: un conjunto ordenado de acciones que consiguelas metas desde el estado inicial(intentando optimizar la metrica)
![Page 8: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/8.jpg)
Acciones en el dominio de los Rovers
(:action navigate:parameters (?x - rover ?y - waypoint ?z - waypoint):precondition (and (can_traverse ?x ?y ?z)
(available ?x)(at ?x ?y)(visible ?y ?z)(>= (energy ?x) 8))
:effect (and (decrease (energy ?x) 8)(not (at ?x ?y))(at ?x ?z)))
![Page 9: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/9.jpg)
Ejemplo de solucion
Solution:1: (navigate rover1 waypoint2 waypoint1) [1]2: (sample_soil rover0 rover0store waypoint3) [1]3: (sample_rock rover1 rover1store waypoint1) [1]4: (calibrate rover1 camera0 objective0 waypoint1) [1]5: (take_image rover1 waypoint1 objective0 camera0 high_res) [1]6: (communicate_soil_data rover0 general waypoint3
waypoint3 waypoint2) [1]7: (communicate_rock_data rover1 general waypoint1
waypoint1 waypoint2) [1]8: (communicate_image_data rover1 general objective0 high_res
waypoint1 waypoint2) [1]
![Page 10: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/10.jpg)
¿Que es planificacion?
Scheduling• Dados:
• un conjunto de actividades (acciones)• algunas restricciones sobre la precedencia, aspectos
temporales o de utilizacion de recursos
• Obtener: una asignacion temporal y de recursos a lasactividades
![Page 11: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/11.jpg)
Ejemplo de salida
[0,5] (navigate rover1 waypoint2 waypoint1) [10,40][10,45] (sample_soil rover0 rover0store waypoint3) [5,10][10,45] (sample_rock rover1 rover1store waypoint1) [10,20][20,65] (calibrate rover1 camera0 objective0 waypoint1) [2,5][22,70] (take_image rover1 waypoint1 objective0
camera0 high_res) [2,5][24,75] (communicate_soil_data rover0 general waypoint3
waypoint3 waypoint2) [5,20][24,75] (communicate_rock_data rover1 general waypoint1
waypoint1 waypoint2) [5,20][29,95] (communicate_image_data rover1 general objective0 high_res
waypoint1 waypoint2) [10,30]
![Page 12: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/12.jpg)
Una historia de la planificacion
1950 1960 198019801970 1990 2000
Planners
Learning
Applications
![Page 13: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/13.jpg)
¿Como planificamos?
De multiples formas• En funcion de los fines (metas) y los medios (operadores)• Descomponiendo problemas en subproblemas• Basado en la experiencia• Reactivamente• Entre varios agentes• Estableciendo prioridades
![Page 14: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/14.jpg)
Aproximaciones a la planificacion
![Page 15: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/15.jpg)
Aproximaciones a la planificacion
![Page 16: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/16.jpg)
Aproximaciones a la planificacion
![Page 17: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/17.jpg)
Aproximaciones a la planificacion
![Page 18: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/18.jpg)
Arquitectura generica
Entorno
actuadoressensores
Controlador
Reacción
Planificación
Sentimientos
Comportamiento social
Aprendizaje
Localización yplanificación de
Comunicación
trayectorias
![Page 19: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/19.jpg)
Arquitectura generica
Entorno
actuadoressensores
Controlador
Reacción
Planificación
Sentimientos
Comportamiento social
Aprendizaje
Localización yplanificación de
Comunicación
trayectorias
![Page 20: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/20.jpg)
Arquitectura generica
Entorno
actuadoressensores
Controlador
Reacción
Planificación
Sentimientos
Comportamiento social
Aprendizaje
Localización yplanificación de
Comunicación
trayectorias
![Page 21: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/21.jpg)
Arquitectura generica
Entorno
actuadoressensores
Controlador
Reacción
Planificación
Sentimientos
Comportamiento social
Aprendizaje
Localización yplanificación de
Comunicación
trayectorias
![Page 22: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/22.jpg)
Arquitectura generica
Entorno
actuadoressensores
Controlador
Reacción
Planificación
Sentimientos
Comportamiento social
Aprendizaje
Localización yplanificación de
Comunicación
trayectorias
![Page 23: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/23.jpg)
Suposiciones iniciales
• Conjunto de estados finito• Completamente observable• Determinista• Estatico• Metas restringidas• Planes secuenciales• Tiempo implıcito• Planificacion off-line
![Page 24: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/24.jpg)
Clasificacion de tecnicas de planificacion
• Planificacion determinista:• entorno completamente conocido• no hay realimentacion sobre ejecucion de acciones• enfoques: planificacion clasica, con costes, optima
• Planificacion probabilıstica:• entorno completamente observable, donde las acciones
pueden producir diferentes estados determinados por unadistribucion de probabilidad
• enfoques: combinacion de planificacion determinista yreplanificacion, extender planificacion clasica y resolverMarkov Decision Processes (MDPs)
• Planificacion contingente: se pueden observar algunosaspectos del estado actual durante la ejecucion de lasacciones
• Planificacion conformante: no determinista y entorno noobservable
![Page 25: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/25.jpg)
El mundo de los bloques
• Un conjunto de bloques, una mesa, y un brazo de un robot
• Todos los bloques son iguales de tamano, forma y color, diferenciandoseen el nombre
• La mesa tiene extension ilimitada
• Cada bloque puede estar encima de la mesa, encima de un solo bloque,o sujeto por el brazo del robot
• El brazo de robot solo puede sujetar un bloque cada vez
• Resolver problemas supone pasar de una configuracion (estado) inicial aun estado en el que sean ciertas unas metas
C
BC
B
A
D A
Estado inicial Metas
![Page 26: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/26.jpg)
La logıstica de transportes
• Ciudades, con aeropuertos y oficinas de correos
• Aviones que pueden volar entre los aeropuertos
• Camiones que solo pueden llevar paquetes dentro de las ciudades
• Paquetes que deben ir de un sitio a otro, posiblemente situados endiferentes ciudades
![Page 27: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/27.jpg)
Otros dominios
• Competiciones de planificacion: desde 1998:http://icaps-conference.org
• Aplicaciones reales:• DeepSpace One• Spirit+Opportunity• Gestion de incendios• Gestion de ascensores• UAV de vigilancia (WITAS)• Bridge
![Page 28: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/28.jpg)
Maintenance of satellites. Hispasat
![Page 29: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/29.jpg)
What else?
• Representation: functions (real ones) in thepreconditions+control knowledge
• Time: Allen primitives• Uncertainty: not considered• Sensors and actuators: parsing (GUI), Excel• Search:
• cost-based planning: easy (Prodigy). . .• once the right control knowledge was defined
• Reality check: it was developed with the users, never used
[AI Magazine, 2004]
![Page 30: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/30.jpg)
Representation
(OPERATOR SOUTH-MANEUVER(params <s> <d> <t> <dend> <db>)(preconds ((<s> SATELLITE)
(<t> TIMES)(<d> (and DATE
(gen-from-pred (south-maneuver <s> <t> <d>))))(<dend> (and DATE (end-operation <d> 3 hours)))(<db> (and DATE (required-hour <d> Monday 0))))
(and (free)(south-maneuver <s> <t> <d>)))
(effects ()((add (south-m <s> <t>))(add (south-man <s> <t> <d>))(add (no-maneuver <s> <t> <db>)))))
![Page 31: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/31.jpg)
Personalized city tourism. SAMAP
![Page 32: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/32.jpg)
What else?
• Representation: real functions on preconditions• Time: linear, constrained• Uncertainty: replanning• Sensors and actuators:
• parsing (Web, maps, GUI, smartphone, ...)• oversubscription, user-based goals generation
• Search: two planning models• temporal HTN• cost-based planning
• Reality check:• started as a research project• now a product, Onmyplan
(http://www.iactiveit.com/soluciones/turismo/)
[ESWA, 2008]
![Page 33: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/33.jpg)
Representation
(OPERATOR MOVE(params <u> <pu> <p> <day> <time> <new-time> <duration> <price> <utility>)(preconds ((<u> USER) (<day> DAY) (<p> PLACE)
(<pu> (and PLACE (is-user-there-p <u> <pu>)))(<time> (and TIME (gen-from-pred (current-time <u> <day> <time>))))(<duration> (and DURATION
(compute-move-time <pu> <p> <time> <day> nil <duration>)))(<money> (and MONEY (gen-from-pred (money-available <u> <money>))))(<price> (and MONEY (get-transport-cost <price>) (<= <price> <money>)))(<utility> (and UTILITY (get-transport-utility <utility>)))(<new-time> (and TIME (increase <time> <duration> <new-time>))))
(and (at <u> <pu>)))(effects ((<new-money> (and MONEY (decrease <money> <price> <new-money>))))
((del (money-available <u> <money>))(add (money-available <u> <new-money>))(del (at <u> <pu>))(add (at <u> <p>))(del (current-time <u> <day> <time>))(add (current-time <u> <day> <new-time>))))
(costs ()((PRICE <price> )(UTILITY <utility>)(MAKESPAN <duration>)(OTHER-METRIC (compute-metric <utility> <price>)))))
![Page 34: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/34.jpg)
Social games. Planning and emotions
![Page 35: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/35.jpg)
What else?
• Representation:• functions• numerical preconditions• state-dependent costs
• Time: linear, explicit• Uncertainty: replanning• Sensors and actuators: 3D simulator• Search: cost-based planning• Reality check: research project
[ICAART, 2011]
![Page 36: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/36.jpg)
Representation
(:action PLAY:parameters (?leisure-object - leisure-object ?room - room):precondition (and (in ?room) (at ?leisure-object ?room) (not (time))):effect (and (time)
(decrease (boredom) 1)(assign (needs)
(+ (+ (+ (+ (boredom) (hunger)) (thirst)) (dirtiness))(tiredness)))
(increase (valence)(* (neuroticism)
(- (/ (+ (preference ?leisure-object) (play-preference)) 2)(/ (max-preference) 2))))
(increase (arousal)(* (neuroticism)
(- (/ (+ (activation ?leisure-object) (play-activation)) 2)(/ (max-activation) 2))))
(increase (v-valence)(* (neuroticism)
(- 1 (/ (/ (+ (preference ?leisure-object) (play-preference)) 2)(max-preference)))))
(increase (v-arousal)(* (neuroticism)
(- 1 (/ (/ (+ (activation ?leisure-object) (play-activation)) 2)(max-activation)))))))
![Page 37: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/37.jpg)
e-Learning. Adaptaplan
![Page 38: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/38.jpg)
What else?
• Representation: functions, numerical preconditions• Time: linear• Uncertainty:
• how to plan for failures?• can we change on-line a new plan?
• Sensors and actuators:• parsing (e-Learning standards)• oversubscription: clustered oversubscription
• Search: three different planning models (temporal, HTN andcost-based planning)
• Reality check: it was applied in its HTN version by acompany
[J. of Scheduling, 2010; ESWA, 2011; KERJ, In Press]
![Page 39: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/39.jpg)
Representation
(:action designs-problem-space:parameters (?s - student):precondition (and (not (task_designs-problem-space_done ?s))
(task_reads-introduction_done ?s)(novice_level ?s)(user_role ?s learner))
:effect (and (is-part-of introduction)(task_designs-problem-space_done ?s)(increase (total_time_student ?s) 60)(when (active ?s strong)
(increase (reward_student ?s) 40))(when (reflective ?s strong)
(increase (reward_student ?s) 20))(when (intuitive ?s strong)
(increase (reward_student ?s) 20))(when (sensitive ?s strong)
(increase (reward_student ?s) 40))(when (visual ?s strong)
(increase (reward_student ?s) 20))(when (verbal ?s strong)
(increase (reward_student ?s) 40))))
![Page 40: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/40.jpg)
Clustered oversubscription
![Page 41: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/41.jpg)
Planning for data mining. Ericsson Research
![Page 42: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/42.jpg)
Planning for data mining
![Page 43: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/43.jpg)
What else?
• Representation: functions, numerical preconditions,state-dependent costs, new objects
• Time: not considered• Uncertainty:
• how to estimate the actions cost• how to estimate the results of executing actions
• Sensors and actuators:• PMML, databases and Weka• use of learning
• Search: cost-based planning• Reality check: developed with users (Ericsson), patent
application, unknown usage
[KERJ, In Press]
![Page 44: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/44.jpg)
Representation
(:action train-classification:parameters (?mi - ModelInstance ?m - Model ?d - DataSet
?fi - FieldName ?dt - DataType ?t - TestMode):precondition (and (learnable ?mi)
(is-model ?mi ?m)(implements ?m classification)(is-field ?fi ?d)(dataField ?fi categorical ?dt)(eval-on ?d ?t))
:effect (and (is-classification-model ?mi ?d ?fi)(not (preprocess-on ?d))(not (learnable ?mi))(increase (reward) (reward-model ?m))(increase (understandability)
(understandability-model ?m))(increase (exec-time)
(* (model-time ?m)(numberOfFields)))))
![Page 45: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/45.jpg)
Planning for data mining. Sensors
![Page 46: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/46.jpg)
Logistics planning. Acciona
![Page 47: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/47.jpg)
What else?
• Representation: MIP model, functions, numericalpreconditions, state-dependent costs
• Time: linear, explicit• Uncertainty: monitoring and replanning• Sensors and actuators: company databases (errors)• Search: problem size→ MIP+cost-based planning• Reality check: developed with users (Acciona), unknown
usage
[ICAPS’11]
![Page 48: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/48.jpg)
Representation
(:action delivery-after-time:parameters (?p - load ?c - truck ?o - container ?l - place
?m - time ?s - time):precondition (and (loaded ?c ?o)
(inside ?p ?o)(at ?p ?l)(time ?p ?m)(after ?p ?m ?s)(> (time-truck ?c) (delivery-time ?p ?l))(> (container-load ?o) 0))
:effect (and (not (time ?p ?m))(time ?p ?s)(delivered ?p ?l ?m)(decrease (container-load ?o)
(unload-amount ?p ?l))(increase (plan-cost)
(* (- (time-truck ?c)(delivery-time ?p ?l))
(late-delivery-cost ?p ?l)))))
![Page 49: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/49.jpg)
Robotic tasks. CMU
![Page 50: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/50.jpg)
What else?
• Representation: two levels, functions, numericalpreconditions, state-dependent costs
• Time: defined as a cost, learned• Uncertainty: monitoring and replanning at the two levels• Sensors and actuators: noisy• Search: cost-based planning• Reality check: robots are moving
![Page 51: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/51.jpg)
Representation
(:action move-stay-connected:parameters (?robot - robot ?cell1 - cell ?cell2 - cell):precondition (and (at-robot ?robot ?cell1)
(free ?cell2)(adjacent ?cell1 ?cell2)(connected-cell ?cell2)(< (uncertainty-obstacle ?cell2)
(uncertainty-threshold))):effect (and (not (at-robot ?robot ?cell1))
(not (free ?cell2))(free ?cell1)(at-robot ?robot ?cell2)(visited ?robot ?cell2)(increase (exec-time) 1)(increase (total-uncertainty)
(uncertainty-obstacle ?cell2))(increase (number-visited) 1)))
![Page 52: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/52.jpg)
Robotic tasks
![Page 53: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/53.jpg)
Robotic tasks
![Page 54: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/54.jpg)
Multiple-sensors observation
![Page 55: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/55.jpg)
User-centered tourist guides
![Page 56: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/56.jpg)
User-centered tourist guides
![Page 57: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/57.jpg)
Indice
1 IntroduccionConcepto de PlanificacionRepresentacionBusqueda
2 Planificacion clasica
3 Planificacion neoclasica
4 Heurıstica
5 Otras cuestiones
![Page 58: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/58.jpg)
Representacion en planificacion
• Para que el ordenador pueda resolver problemas, hace faltadecirle que tiene que resolver en algun lenguaje (al igualque a nosotros)
• Existen muchas formas de suministrar esa informacion• La mas empleada en planificacion automatica es la logica
de predicados• Ası se representan los estados y los operadores• La logica de predicados permite representar las cuestiones
ciertas o falsas del mundo mediante: terminos, predicados,conectivas, y cuantificadores
• No hay una representacion unica y valida; cada personarepresenta los dominios de forma diferente
![Page 59: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/59.jpg)
Representacion de los estados
• Los estados se representan definiendo un conjunto depredicados
en(objeto/vehıculo,lugar), dentro(objeto,vehıculo),
en-ciudad(lugar,ciudad)
• y tipos
objeto(x), vehıculo(x)={avion(x),camion(x)},lugar(x)={aeropuerto(x),oficina-correos(x)}, ciudad(x)
![Page 60: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/60.jpg)
Representacion de los estados
• Cada estado se representa por una conjuncion depredicados instanciados
en(objeto1,aeropuerto1),en(avion1,aeropuerto1),
en(camion1,aeropuerto1),en(camion2,oficina-correos2),...
• Normalmente, se supone que lo que no apareceexplıcitamente representado en un estado es falso:suposicion del mundo cerrado
en(objeto1,x) ∀x 6=aeropuerto1
![Page 61: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/61.jpg)
Estados en el mundo de los bloques
• Se podrıan utilizar los siguientes predicados:• encima(x,y): el bloque x esta encima del y• en-mesa(x): el bloque x esta encima de la mesa• libre(x): el bloque x no tiene ningun bloque encima• sujeto(x): el brazo del robot tiene cogido al bloque x• brazo-libre: el brazo del robot no tiene cogido a ningun
bloque
Estado inicial:encima(A,B),encima(B,D),en-mesa(D),en-mesa(C),libre(A),libre(C),brazo-libreMetas: en-mesa(A),encima(C,B)
C
BC
B
A
D A
Estado inicial Metas
![Page 62: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/62.jpg)
Representacion de los operadores
• Se deben representar los cambios que ocurren en el mundopor la aplicacion del operador: suposicion STRIPS
• Se definen por tres listas:• precondiciones: condiciones que se tienen que cumplir en
un estado para poder ejecutar el operador• anadidos: cosas que pasan a ser ciertas por la ejecucion del
operador (hay que anadirlas al estado)• borrados: cosas que dejan de ser ciertas por la ejecucion
del operador (hay que borrarlas del estado)
cargar-avion(objeto,avion,aeropuerto)precondiciones: en(objeto,aeropuerto),en(avion,aeropuerto)anadidos: dentro(objeto,avion)borrados: en(objeto,aeropuerto)
![Page 63: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/63.jpg)
Ejemplo: Mundo de los bloques
Operators
• pickup(?x): (ontable ?x) (clear ?x) (arm-empty)(holding ?x)¬(ontable ?x) ¬(clear ?x) ¬(arm-empty)
• putdown(?x): (holding ?x)(ontable ?x) (clear ?x) (arm-empty)¬(holding ?x)
• stack(?x ?y): (holding ?x) (clear ?y)(on ?x ?y) (clear ?x) (arm-empty) ¬(. . . ) ¬(. . . )
• unstack(?x ?y):(on ?x ?y) (clear ?x) (arm-empty)(holding ?x) (clear ?y) ¬(. . . ) ¬(. . . ) ¬(. . . )
C
BC
B
A
D A
Estado inicial Metas
![Page 64: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/64.jpg)
Ejemplos de operadores en logıstica
cargar-avion(objeto,avion,aeropuerto)precondiciones: en(objeto,aeropuerto),en(avion,aeropuerto)anadidos: dentro(objeto,avion)borrados: en(objeto,aeropuerto)
descargar-avion(objeto,avion,aeropuerto)precondiciones: dentro(objeto,aeropuerto),en(avion,aeropuerto)anadidos: en(objeto,aeropuerto)borrados: dentro(objeto,avion)
cargar-camion(objeto,camion,lugar)precondiciones: en(objeto,lugar),en(camion,lugar)anadidos: dentro(objeto,camion)borrados: en(objeto,lugar)
descargar-camion(objeto,camion,lugar)
volar-avion(avion,aeropuerto1,aeropuerto2)precondiciones: en(avion,aeropuerto1)anadidos: en(avion,aeropuerto2)borrados: en(avion,aeropuerto1)
conducir-camion(camion,lugar1,lugar2,ciudad)precondiciones: en(camion,lugar1),en-ciudad(lugar1,ciudad),en-ciudad(lugar2,ciudad)anadidos: en(camion,lugar2)borrados: en(camion,lugar1)
![Page 65: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/65.jpg)
Desde STRIPS hasta PDDL
• El lenguaje de STRIPS es muy simple• Se amplio el lenguaje, generando ADL, que incorpora, entre
otros:• cuantificacion universal y existencial• efectos condicionales
• Desde 1998 se ha venido organizando una competicion deplanificadores, IPC (“International Planning Competition”)
• Se necesitaba un lenguaje comun: PDDL
• Ha tenido varias versiones, que permiten, entre otros:• especificacion de costes de ejecucion de operadores• tipos para variables de operadores• modelos no conservativos de acciones
![Page 66: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/66.jpg)
Lenguaje estandar PDDL. Dominio de la logıstica
(define (domain logistics)(:requirements :strips :typing)(:types truck airplane - vehicle
package vehicle - physobjairport location - placecity place physobj - object)
(:predicates (in-city ?loc - place ?city - city)(at ?obj - physobj ?loc - place)(in ?pkg - package ?veh - vehicle))
...)
![Page 67: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/67.jpg)
Operadores
(:action load-truck ...)(:action load-airplane ...)(:action unload-truck ...)(:action unload-airplane ...)(:action drive-truck ...)(:action fly-airplane
:parameters (?p - airplane ?s - airport ?d - airport):precondition (and (at ?p ?s)
(not (= ?s ?d))):effect (and (at ?p ?d)
(not (at ?p ?s))))
![Page 68: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/68.jpg)
Definicion del problema
(define (problem log1) (:domain logistics)(:objects (ob0 ob1 ob2 - package)
(c2 c1 c0 - city)(po2 po1 po0 - location)(a2 a1 a0 - airport)(tr2 tr1 tr0 - truck)(pl1 pl2 - airplane))
(:init (in-city a2 c2) (in-city po2 c2) (at tr2 po2)(in-city a1 c1) (in-city po1 c1) (at tr1 po1)(in-city a0 c0) (in-city po0 c0) (at tr0 po0)(at ob1 a1) (in ob0 pl0) (in ob2 tr1)(at pl2 a1) (at pl1 a2))
(:goal (at ob1 a2)))
![Page 69: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/69.jpg)
Operadores mas complejos
(:action zoom:parameters (?a - aircraft ?c1 ?c2 - city):precondition (and (at ?a ?c1)
(>= (fuel ?a)(* (distance ?c1 ?c2) (fast-burn ?a)))
(<= (onboard ?a) (zoom-limit ?a))):effect (and (not (at ?a ?c1))
(at ?a ?c2)(increase (total-fuel-used)
(* (distance ?c1 ?c2) (fast-burn ?a)))(decrease (fuel ?a)
(* (distance ?c1 ?c2) (fast-burn ?a)))))
![Page 70: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/70.jpg)
Problemas mas complejos
(define (problem strips-sat-x-1) (:domain satellite)(:objects satellite0 - satellite
instrument0 - instrumentimage1 spectrograph2 thermograph0 - modeStar0 Star5 GroundStation1 GroundStation2 Phenomenon3Phenomenon4 Phenomenon6 - direction)
(:init (supports instrument0 thermograph0)(= (calibration-target instrument0) GroundStation2)(= (calibration-time instrument0 GroundStation2) 5.9)(on-board instrument0 satellite0)(power-avail satellite0)(= (pointing satellite0) Phenomenon6)(= (slew-time GroundStation1 Star0) 18.17)(= (slew-time Star0 GroundStation1) 18.17)...)
(:goal (and (have-image Phenomenon4 thermograph0)(have-image Star5 thermograph0)(have-image Phenomenon6 thermograph0)))
(:metric minimize (total-time)))
![Page 71: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/71.jpg)
PPDDL: dominios probabilısticos
(:action calibrate:parameters (?s - satellite ?i - instrument ?d - direction):precondition (and (on-board ?i ?s)
(pointing ?s ?d)(power-on ?i))
:effect (and (when (calibration-target ?i ?d) (calibrated ?i))(when (not (calibration-target ?i ?d))
(probabilistic 0.2 (and (calibrated ?i))))))
![Page 72: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/72.jpg)
Preferencias (problema)
(:constraints (and (preference a0 (always (at rover0 waypoint0)))(preference e0 (sometime (at rover0 waypoint3)))(preference o0 (at-most-once (empty rover0store)))(preference o1 (at-most-once (full rover0store)))...))
(:metric minimize (+ (* (is-violated a0) 6.22222)(* (is-violated e0) 5.44444)(* (is-violated o0) 7)(* (is-violated o1) 5.44444)(* (is-violated sb1) 5.44444)
...))
![Page 73: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/73.jpg)
Otras representaciones (dominio). SAS+
(:functions (city-of ?l - location) - city(location-of ?t - thing) - (either location vehicle))
(:action drive:parameters (?t - truck ?to - location):precondition (= (city-of (location-of ?t)) (city-of ?to)):effect (assign (location-of ?t) ?to))
(:action unload:parameters (?p - package ?v - vehicle):precondition (= (location-of ?p) ?v):effect (assign (location-of ?p) (location-of ?v)))
![Page 74: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/74.jpg)
Indice
1 IntroduccionConcepto de PlanificacionRepresentacionBusqueda
2 Planificacion clasica
3 Planificacion neoclasica
4 Heurıstica
5 Otras cuestiones
![Page 75: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/75.jpg)
Busqueda
• Busqueda hacia adelante (progresion): se ejecutanoperadores hasta que se encuentre la solucion
• Ejemplos: SOAR [Laird et al., 1986], FF [Hoffmann andNebel, 2001], TLPLAN [Bacchus and Kabanza, 2000]
• Busqueda hacia atras (regresion): se comienza desde lasmetas, se seleccionan operadores que las anadan y seanaden las precondiciones de los mismos al conjunto demetas
• Ejemplos: STRIPS [Fikes and Nilsson, 1971],UCPOP [Penberthy and Weld, 1992], PRODIGY [Veloso et al.,1995]
![Page 76: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/76.jpg)
Busqueda
• Busqueda hacia adelante (progresion): se ejecutanoperadores hasta que se encuentre la solucion
• Ejemplos: SOAR [Laird et al., 1986], FF [Hoffmann andNebel, 2001], TLPLAN [Bacchus and Kabanza, 2000]
• Busqueda hacia atras (regresion): se comienza desde lasmetas, se seleccionan operadores que las anadan y seanaden las precondiciones de los mismos al conjunto demetas
• Ejemplos: STRIPS [Fikes and Nilsson, 1971],UCPOP [Penberthy and Weld, 1992], PRODIGY [Veloso et al.,1995]
![Page 77: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/77.jpg)
Busqueda hacia adelante
![Page 78: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/78.jpg)
Busqueda hacia adelante
![Page 79: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/79.jpg)
Busqueda hacia adelante
![Page 80: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/80.jpg)
Busqueda hacia adelante
![Page 81: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/81.jpg)
Busqueda hacia adelante
![Page 82: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/82.jpg)
Busqueda hacia adelante
![Page 83: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/83.jpg)
Busqueda hacia adelante
![Page 84: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/84.jpg)
Busqueda hacia adelante
![Page 85: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/85.jpg)
Busqueda hacia adelante
![Page 86: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/86.jpg)
Busqueda hacia adelante
![Page 87: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/87.jpg)
Busqueda hacia atras
![Page 88: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/88.jpg)
Busqueda hacia atras
![Page 89: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/89.jpg)
Busqueda hacia atras
![Page 90: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/90.jpg)
Busqueda hacia atras
![Page 91: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/91.jpg)
Busqueda sin conocimiento
(:action a-1:parameters (?p - type-x ?s - type-y ?d - type-z):precondition (and (p-1 ?p ?s) (not (= ?s ?d))):effect (and (p-1 ?p ?d)
(not (p-1 ?p ?s))))(:action a-2
:parameters (?p - type-x ?s - type-y ?d - type-z):precondition (and (p-1 ?p ?d) (p-1 ?s ?d)):effect (and (p-2 ?p ?s)
(not (p-1 ?p ?d))))(:action a-3
:parameters (?p - type-x ?s - type-y ?d - type-z):precondition (and (p-2 ?p ?s) (p-1 ?s ?d)):effect (and (p-1 ?p ?d)
(not (p-2 ?p ?s))))
![Page 92: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/92.jpg)
Busqueda
Sin conocimiento• Amplitud vs. Profundidad• Hacia adelante vs. hacia atras vs. bidireccional• Con costes vs. sin costes• Uno vs. multiples agentes
Busqueda con conocimiento• Busqueda local y avara (greedy) vs. busqueda global• Escalada, en Haz• A∗, IDA∗, . . .• Alfa-beta
![Page 93: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/93.jpg)
Caracterısticas
• Complejidad en tiempo y espacio• Validez• Completud• Optimalidad• Incertidumbre
![Page 94: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/94.jpg)
Mas informacion en
• Libro: [Ghallab et al., 2004]
• Otras referencias: [Nilsson, 1987,Borrajo et al., 1993,Rich and Knight, 1994,Russell and Norvig, 1995,Allen et al., 1990,Weld, 1994]
![Page 95: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/95.jpg)
Indice
1 Introduccion
2 Planificacion clasicaEspacio de estadosPlanes de orden parcial
3 Planificacion neoclasica
4 Heurıstica
5 Otras cuestiones
![Page 96: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/96.jpg)
Indice
1 Introduccion
2 Planificacion clasicaEspacio de estadosPlanes de orden parcial
3 Planificacion neoclasica
4 Heurıstica
5 Otras cuestiones
![Page 97: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/97.jpg)
STRIPS
Objetivo: construccion de un sistema de control para el robot Shakey
![Page 98: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/98.jpg)
Representacion de operadores
• Problema del marco: ¿que ocurre con el contexto delmundo cuando se ejecuta una accion?
• Solucion (hipotesis STRIPS): solo cambian las cosas queaparecen en las post-condiciones de cada operador [Fikesand Nilsson, 1971]
• Busqueda:• Nodos: estado actual y pila de metas-operadores• Nodo raız: estado inicial y conjuncion de metas• Heurıstica: seleccionar siempre alguno de los sucesores de
cada nodo• Idea:
• Meter en la pila las metas por conseguir y los operadoresque consiguen dichas metas
• Sacar de la pila las metas que sean ciertas en el estadoactual y los operadores que se ejecuten
![Page 99: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/99.jpg)
Algoritmo de STRIPS
Repetir hasta que pila=φ OR no se puedan expandir mas nodos• Si la cima de la pila del nodo es una conjuncion de metas
Si la conjuncion es cierta en el estado Entonces se elimina de la pilaSi no, generar como sucesores todas las posibles combinaciones de las metas
seleccionar una de ellas• Si la cima de la pila del nodo es una meta
Si la meta es cierta en el estado Entonces se elimina de la pilaSi no, Si hay bucle de meta Entonces retroceder
Si no, generar un sucesor por cada instanciacion de operadorque anade dicha meta
Si hay sucesores Entonces elegir unoSi no, retroceder
• Si la cima de la pila del nodo es un operador instanciadoSi el operador instanciado se puede ejecutarEntonces ejecutar operador, quitarlo de la pila y anadirlo al planSi no, se introducen sus precondiciones en la pila
![Page 100: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/100.jpg)
Representacion de operadores
QUITAR(x , y )precondiciones: encima(x , y ),libre(x),brazo-libreanadidos: sujeto(x),libre(y )borrados: encima(x , y ),brazo-libre,libre(x)
LEVANTAR(x)precondiciones: en-mesa(x),libre(x),brazo-libreanadidos: sujeto(x)borrados: en-mesa(x),brazo-libre,libre(x)
PONER(x , y )precondiciones: sujeto(x),libre(y )anadidos: encima(x , y ),libre(x),brazo-libreborrados: sujeto(x),libre(y )
DEJAR(x)precondiciones: sujeto(x)anadidos: en-mesa(x),libre(x),brazo-libreborrados: sujeto(x)
![Page 101: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/101.jpg)
Ejemplo de STRIPS
A
AB
Estado inicial (E )0 Metas
en-mesa(A) E0
en-mesa(A)DEJAR(A) E0
sujeto(A)DEJAR(A)en-mesa(A)
E0
E0
en-mesa(A)
sujeto(A)DEJAR(A)
QUITAR(A,A)
QUITAR(A,B)
en-mesa(A)
sujeto(A)DEJAR(A)
E0E
sujeto(A)DEJAR(A)en-mesa(A)
0
LEVANTAR(A)
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A) E0
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A)
E0
metabucle de
X
brazo-libreen-mesa(A) libre(A)
en-mesa(A) libre(A)brazo-librebrazo-libre
X
X X
X X
en-mesa(A)libre(A)
...
libre(A) brazo-libre encima(A,B)QUITAR(A,B)sujeto(A)DEJAR(A)en-mesa(A)
E0
E1sujeto(A)DEJAR(A)en-mesa(A) B
A
E1E2en-mesa(A)
B A
E2
![Page 102: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/102.jpg)
Ejemplo de STRIPS
A
AB
Estado inicial (E )0 Metas
en-mesa(A) E0
en-mesa(A)DEJAR(A) E0
sujeto(A)DEJAR(A)en-mesa(A)
E0
E0
en-mesa(A)
sujeto(A)DEJAR(A)
QUITAR(A,A)
QUITAR(A,B)
en-mesa(A)
sujeto(A)DEJAR(A)
E0E
sujeto(A)DEJAR(A)en-mesa(A)
0
LEVANTAR(A)
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A) E0
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A)
E0
metabucle de
X
brazo-libreen-mesa(A) libre(A)
en-mesa(A) libre(A)brazo-librebrazo-libre
X
X X
X X
en-mesa(A)libre(A)
...
libre(A) brazo-libre encima(A,B)QUITAR(A,B)sujeto(A)DEJAR(A)en-mesa(A)
E0
E1sujeto(A)DEJAR(A)en-mesa(A) B
A
E1E2en-mesa(A)
B A
E2
![Page 103: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/103.jpg)
Ejemplo de STRIPS
A
AB
Estado inicial (E )0 Metas
en-mesa(A) E0
en-mesa(A)DEJAR(A) E0
sujeto(A)DEJAR(A)en-mesa(A)
E0
E0
en-mesa(A)
sujeto(A)DEJAR(A)
QUITAR(A,A)
QUITAR(A,B)
en-mesa(A)
sujeto(A)DEJAR(A)
E0E
sujeto(A)DEJAR(A)en-mesa(A)
0
LEVANTAR(A)
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A) E0
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A)
E0
metabucle de
X
brazo-libreen-mesa(A) libre(A)
en-mesa(A) libre(A)brazo-librebrazo-libre
X
X X
X X
en-mesa(A)libre(A)
...
libre(A) brazo-libre encima(A,B)QUITAR(A,B)sujeto(A)DEJAR(A)en-mesa(A)
E0
E1sujeto(A)DEJAR(A)en-mesa(A) B
A
E1E2en-mesa(A)
B A
E2
![Page 104: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/104.jpg)
Ejemplo de STRIPS
A
AB
Estado inicial (E )0 Metas
en-mesa(A) E0
en-mesa(A)DEJAR(A) E0
sujeto(A)DEJAR(A)en-mesa(A)
E0
E0
en-mesa(A)
sujeto(A)DEJAR(A)
QUITAR(A,A)
QUITAR(A,B)
en-mesa(A)
sujeto(A)DEJAR(A)
E0E
sujeto(A)DEJAR(A)en-mesa(A)
0
LEVANTAR(A)
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A) E0
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A)
E0
metabucle de
X
brazo-libreen-mesa(A) libre(A)
en-mesa(A) libre(A)brazo-librebrazo-libre
X
X X
X X
en-mesa(A)libre(A)
...
libre(A) brazo-libre encima(A,B)QUITAR(A,B)sujeto(A)DEJAR(A)en-mesa(A)
E0
E1sujeto(A)DEJAR(A)en-mesa(A) B
A
E1E2en-mesa(A)
B A
E2
![Page 105: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/105.jpg)
Ejemplo de STRIPS
A
AB
Estado inicial (E )0 Metas
en-mesa(A) E0
en-mesa(A)DEJAR(A) E0
sujeto(A)DEJAR(A)en-mesa(A)
E0
E0
en-mesa(A)
sujeto(A)DEJAR(A)
QUITAR(A,A)
QUITAR(A,B)
en-mesa(A)
sujeto(A)DEJAR(A)
E0E
sujeto(A)DEJAR(A)en-mesa(A)
0
LEVANTAR(A)
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A) E0
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A)
E0
metabucle de
X
brazo-libreen-mesa(A) libre(A)
en-mesa(A) libre(A)brazo-librebrazo-libre
X
X X
X X
en-mesa(A)libre(A)
...
libre(A) brazo-libre encima(A,B)QUITAR(A,B)sujeto(A)DEJAR(A)en-mesa(A)
E0
E1sujeto(A)DEJAR(A)en-mesa(A) B
A
E1E2en-mesa(A)
B A
E2
![Page 106: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/106.jpg)
Ejemplo de STRIPS
A
AB
Estado inicial (E )0 Metas
en-mesa(A) E0
en-mesa(A)DEJAR(A) E0
sujeto(A)DEJAR(A)en-mesa(A)
E0
E0
en-mesa(A)
sujeto(A)DEJAR(A)
QUITAR(A,A)
QUITAR(A,B)
en-mesa(A)
sujeto(A)DEJAR(A)
E0E
sujeto(A)DEJAR(A)en-mesa(A)
0
LEVANTAR(A)
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A) E0
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A)
E0
metabucle de
X
brazo-libreen-mesa(A) libre(A)
en-mesa(A) libre(A)brazo-librebrazo-libre
X
X X
X X
en-mesa(A)libre(A)
...
libre(A) brazo-libre encima(A,B)QUITAR(A,B)sujeto(A)DEJAR(A)en-mesa(A)
E0
E1sujeto(A)DEJAR(A)en-mesa(A) B
A
E1E2en-mesa(A)
B A
E2
![Page 107: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/107.jpg)
Ejemplo de STRIPS
A
AB
Estado inicial (E )0 Metas
en-mesa(A) E0
en-mesa(A)DEJAR(A) E0
sujeto(A)DEJAR(A)en-mesa(A)
E0
E0
en-mesa(A)
sujeto(A)DEJAR(A)
QUITAR(A,A)
QUITAR(A,B)
en-mesa(A)
sujeto(A)DEJAR(A)
E0E
sujeto(A)DEJAR(A)en-mesa(A)
0
LEVANTAR(A)
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A) E0
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A)
E0
metabucle de
X
brazo-libreen-mesa(A) libre(A)
en-mesa(A) libre(A)brazo-librebrazo-libre
X
X X
X X
en-mesa(A)libre(A)
...
libre(A) brazo-libre encima(A,B)QUITAR(A,B)sujeto(A)DEJAR(A)en-mesa(A)
E0
E1sujeto(A)DEJAR(A)en-mesa(A) B
A
E1
E2en-mesa(A)
B A
E2
![Page 108: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/108.jpg)
Ejemplo de STRIPS
A
AB
Estado inicial (E )0 Metas
en-mesa(A) E0
en-mesa(A)DEJAR(A) E0
sujeto(A)DEJAR(A)en-mesa(A)
E0
E0
en-mesa(A)
sujeto(A)DEJAR(A)
QUITAR(A,A)
QUITAR(A,B)
en-mesa(A)
sujeto(A)DEJAR(A)
E0E
sujeto(A)DEJAR(A)en-mesa(A)
0
LEVANTAR(A)
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A) E0
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A)
E0
metabucle de
X
brazo-libreen-mesa(A) libre(A)
en-mesa(A) libre(A)brazo-librebrazo-libre
X
X X
X X
en-mesa(A)libre(A)
...
libre(A) brazo-libre encima(A,B)QUITAR(A,B)sujeto(A)DEJAR(A)en-mesa(A)
E0
E1sujeto(A)DEJAR(A)en-mesa(A) B
A
E1E2en-mesa(A)
B A
E2
![Page 109: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/109.jpg)
Problema: linealidad
• STRIPS asume independencia entre las metas, por lo quelas trata linealmente: hasta que no encuentra un plan paraobtener una meta, no pasa a las siguientes metas
• No funciona cuando hay recursos limitados, por lo que es:• incompleta: existe solucion, pero no la encuentra
Problema del cohete chinoBA A B
C
MarteTierra
Estado inicial
Marte
Metas
• no optima: no encuentra la solucion optima
Anomalıa de SussmanEstado inicial Metas
A
C
B
A
B
C
![Page 110: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/110.jpg)
Planificacion no lineal
• Consideracion de varias metas al mismo tiempo• Pensar con un conjunto de metas: no es necesario generar
completamente un plan de una meta para estudiar al mismotiempo el resto
...
en−aeropuerto(Pepe,Barajas)
coger−taxi(Pepe,Casa−Pepe,Barajas)
en−aeropuerto(Maletas−Pepe,Barajas)
descargar−maletas(Maletas−Pepe,x,Barajas)
• Expandir un grafo en el que las metas (y los operadores) sonnodos y se pueden seleccionar las metas en cualquier orden
en(Maletas−Pepe,Casa−Pepe)
en(Pepe,Casa−Pepe)
coger−taxi(Pepe,Casa−Pepe,Barajas)
descargar−maletas(Maletas−Pepe,x,Barajas)
en−aeropuerto(Maletas−Pepe,Barajas)
en−aeropuerto(Pepe,Barajas)Estado inicial Metas
![Page 111: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/111.jpg)
PRODIGY
• Analisis medios-fines con busqueda hacia atras(bidireccional) [Veloso et al., 1995]
• Las metas se tratan como un conjunto• Decisiones:
• Meta: que meta escoger• Operador: que operador utilizar para obtener una meta• Instanciacion de operador: que valores asignar a las
variables del operador• Ejecutar un operador o trabajar en alguna submeta
• Se puede definir conocimiento de control explıcito paratomar las decisiones
![Page 112: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/112.jpg)
Arbol de busqueda generico de PRODIGY
operador o trabajar enuna submeta
1 g
1
1 b
1 g
4 3
2
1
o
meta meta
meta meta
metaElige una
Elige unoperador
Elige unainstanciación
Decide si ejecutar un
ejecutar operador submeta
submetaejecutar operador
operador
instanciacióninstanciación
operador
![Page 113: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/113.jpg)
Algunas definiciones
• Una meta esta pendiente si es una precondicion de unoperador seleccionado (incluyendo las metas iniciales) queno es cierta en el estado actual
• Un operador es aplicable cuando todas sus precondicionesson ciertas en el estado actual
• Operadores relevantes a una meta son aquellos que, si seejecutara una de sus instanciaciones, conseguirıa que lameta fuera cierta en el estado
• Camino sin salida• Bucle de meta• Todas las opciones han sido caminos sin salida• No hay ninguna opcion• Se ha sobrepasado el lımite de profundidad o tiempo
![Page 114: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/114.jpg)
Algoritmo de planificacion de PRODIGY4.0
Prodigy (E ,M,O, C)
Mientras que las metasM no sean ciertas en el estado E Yno se hayan sobrepasado los recursos lımite (tiempo o nodos) Yno se hayan explorado todos los posibles nodos
Si hay un camino sin salida, entonces retrocederSi no, Calcular el conjunto de operadores aplicables, A
Elegir una meta M ∈M o un operador A ∈ A de acuerdo a CSi se ha seleccionado M, entonces:
Generar el conjunto O′ ∈ O de los operadores relevantesElegir un operador O ∈ O′, de acuerdo a CGenerar el conjunto de instanciaciones del operador O, Oi
Elegir un operador instanciado Oi ∈ Oi , de acuerdo a CSi no, (se ha seleccionado un A):
Asignar E al estado despues de Ejecutar ACalcular el conjunto de metas pendientesM
![Page 115: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/115.jpg)
Ejemplo de PRODIGY
A
B
B
A
MetasEstado inicial
done
*finish*
en−mesa(A) encima(B,A)
dejar
dejar(A)
sujeto(A)
levantar
encima(B,A)
quitar
QUITAR(A,B)
encima(B,A)DEJAR(A)
encima(B,A)
poner
sujeto(B)
poner(B,A)libre(A)
quitarlevantar
LEVANTAR(B)
PONER(B,A)
*finish*()
*FINISH*()
encima(B,A)
levantar(A)
en−mesa(A)
brazo−librelibre(A),
encima(B,A)
quitar(A,B) brazo−libre
libre(B) levantar(B)
encima(A,B),libre(A),
en−mesa(B),brazo−libre,
![Page 116: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/116.jpg)
Arquitectura de PRODIGY
Aprendizaje de conocimientode dominio
Aprendizaje de conocimientode control para mejorar la
calidad
Aprendizaje de conocimientode control para mejorar la eficiencia
Planificador
ApprenticeExperiment
Observe Hamlet
Quality
Prodigy/EBL Static Dynamic Alpine Prodigy/Analogy
![Page 117: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/117.jpg)
Indice
1 Introduccion
2 Planificacion clasicaEspacio de estadosPlanes de orden parcial
3 Planificacion neoclasica
4 Heurıstica
5 Otras cuestiones
![Page 118: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/118.jpg)
Definiciones
B A
B
D
Estado inicial
C
A
D
Metas: en−mesa(A), encima(B,D)
• Conjunto de operadores (acciones), Λ
quitar(x , y),poner(x , y),levantar(x),dejar(x)
• Conjunto no ordenado de operadores instanciados queintervienen en el plan, A
A ={A0,A∞,A1=levantar(B),A2=dejar(A),A3=quitar(A,C),A4=poner(B,D)}
• Operador inicial, A0, es aquel que tiene comopost-condiciones el estado inicial
• Operador final, A∞, es aquel que tiene como precondicioneslas metas del problema
![Page 119: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/119.jpg)
Definiciones II
• Conjunto de restricciones de orden entre los operadores deun plan, O
O ={(A1 < A4), (A3 < A2)}
• Conjunto de enlaces causales entre operadores, L: li ∈ Les de la forma Ap
p−→ Ac , donde Ap es la accion productora,p es el predicado que anade, y Ac es la accion consumidora
L = {l1 = A1sujeto(x)−→ A4, l2 = A3
sujeto(y)−→ A2,
l3 = A2brazo-libre−→ A1, l4 = A4
brazo-libre−→ A3}
• Conjunto de asignaciones validas, B: bi = (u, v) y u es unavariable
B = {(x ,B), (y ,A), (z,C), (r ,D)}
![Page 120: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/120.jpg)
Definiciones III
• Plan, < A,O,L,B >: orden parcial de operadoresinstanciados
• Agenda, AG: conjunto de pares < m,Ac >, donde m es unameta, y Ac es la accion que la necesita
![Page 121: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/121.jpg)
UCPOP. Plan parcial
CBA
D
AB
B
C
A
CBA
PICK−UP(C)
UNSTACK(A,B)
STACK(C,B)
PUT−DOWN(A)
C
![Page 122: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/122.jpg)
Amenazas (threats)
• Si existe un enlace causal li = App−→ Ac ∈ L, incluir un operador
instanciado Aa en el plan causa una amenaza a li cuando un literal raparece en la lista de borrados de Aa, r equipara con p de acuerdo conB y ok = (Ap < Aa < Ac) es consistente.
A5=levantar(t) amenaza a l3 y a l4 por borrar brazo-libre
• Formas de resolver la amenaza:
• Retrasar (demotion): O ← O∪ {(Aa < Ap)}Anadir (A5 < A2) y (A5 < A4) a O
• Adelantar (promotion): O ← O∪ {(Ac < Aa)}Anadir (A1 < A5) y (A3 < A5) a O
• Separar (separation): B ← B∪ {(u, v)} (no aplicable enUCPOP)
![Page 123: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/123.jpg)
Inicializacion
• A ={A0,A∞}
A0precondiciones:anadidos: encima(A,C),libre(A),en-mesa(C),en-mesa(B),
libre(B),en-mesa(D),libre(D),brazo-libreborrados:A∞precondiciones: en-mesa(A),encima(B,D)anadidos:borrados:
![Page 124: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/124.jpg)
Inicializacion
• O={(A0 < A∞)}• L,B = φ
• AG = {< mi ,A∞ >| mi ∈M}
AG = {< en −mesa(A),A∞ >,< encima(B,D),A∞ >}
![Page 125: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/125.jpg)
Algoritmo UCPOP (< A,O,L,B >,AG,Λ)
1. Si AG = φ, devolver < A,O,L,B >2. Seleccionar un g =< m,Ac > de AG;
Si existe un enlace causal Ap∼m−→ Ac , devolver fallo
3. Si existe un operador Ap ∈ A o uno instanciado de Λ,que anada m′, y Ap < Ac sea consistente con O ym′ unifique con m mediante σ, teniendo en cuenta a B
Entonces L ← L∪{Apm−→ Ac}; B ← B ∪ σ; O ← O∪{(Ap < Ac)};
Si Ap 6∈ A Entonces A ← A∪{Ap};Para cada p precondicion de Ap
AG← AG∪{< pσ,Ap >};O ← O∪{(A0 < Ap), (Ap < A∞)}
Si no, devolver fallo4. Para cada lk = (Ai
p−→ Aj ) ∈ L y para cada Aa que amenace a lk , elegira) Adelantar: si es consistente, O ← O∪{(Aj < Aa)} ob) Retrasar: si es consistente, O ← O∪{(Aa < Ai )}
5. Si B es consistente, devolver UCPOP(< A,O,L,B >,AG,Λ)Si no, devolver fallo
![Page 126: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/126.jpg)
Ejemplo
B A
B
D
Estado inicial
C
A
D
Metas: en−mesa(A), encima(B,D)
![Page 127: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/127.jpg)
Ejemplo
encima(A,C)libre(A)en−mesa(C)en−mesa(B)libre(B)en−mesa(D)libre(D)brazo−libre
A0 A 8
en−mesa(A)
encima(B,D)
Arbol de búsqueda
![Page 128: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/128.jpg)
Ejemplo
• A ={A0,A∞}• O ={(A0 < A∞)}• L = φ
• B = φ
![Page 129: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/129.jpg)
Ejemplo
encima(A,C)libre(A)en−mesa(C)en−mesa(B)libre(B)en−mesa(D)libre(D)brazo−libre
A0 A 8
en−mesa(A)
encima(B,D)
dejar(A)sujeto(A)
Arbol de búsqueda
dejar(A)
![Page 130: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/130.jpg)
Ejemplo
• A ={A0,A∞,dejar(A)}• O ={(A0 < A∞), (dejar(A)< A∞), (A0 <dejar(A))}
• L ={(dejar(A)en-mesa(A)−→ A∞)}
• B = φ
![Page 131: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/131.jpg)
Ejemplo
encima(A,C)libre(A)en−mesa(C)en−mesa(B)libre(B)en−mesa(D)libre(D)brazo−libre
A0
A 8
en−mesa(A)
encima(B,D)
Arbol de búsqueda
dejar(A)
dejar(A)sujeto(A)
poner(B,D)sujeto(B)
libre(D)
poner(B,D)
![Page 132: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/132.jpg)
Ejemplo
• A ={A0,A∞,dejar(A),poner(B,D)}• O ={(A0 < A∞), (dejar(A)< A∞), (A0 <dejar(A)),
(poner(B,D)< A∞), (A0 <poner(B,D))}
• L ={(dejar(A)en-mesa(A)−→ A∞),(poner(B,D)
encima(B,D)−→ A∞)}
• B = φ
![Page 133: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/133.jpg)
Ejemplo
A0 A 8
Arbol de búsqueda
dejar(A)
poner(B,D)
levantar(A) quitar(A,<y>)
dejar(A)sujeto(A)
poner(B,D)sujeto(B)
libre(D)
levantar(A)
en−mesa(A)
encima(B,D)
encima(A,C)libre(A)en−mesa(C)en−mesa(B)libre(B)en−mesa(D)libre(D)brazo−libre
libre(A)
brazo−libre
en−mesa(A)
![Page 134: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/134.jpg)
Ejemplo
• A ={A0,A∞,dejar(A),poner(B,D),levantar(A)}• O ={(A0 < A∞), (dejar(A)< A∞), (A0 <dejar(A)),
(poner(B,D)< A∞), (A0 <poner(B,D)),(levantar(A)< A∞), (A0 <levantar(A)),(levantar(A)<dejar(A))}
• L ={(dejar(A)en-mesa(A)−→ A∞),(poner(B,D)
encima(B,D)−→ A∞),
(levantar(A)sujeto(A)−→ dejar(A))}
• B = φ
![Page 135: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/135.jpg)
Ejemplo
A0 A 8
Arbol de búsqueda
dejar(A)
poner(B,D)
levantar(A) quitar(A,<y>)
dejar(A)sujeto(A)
poner(B,D)sujeto(B)
libre(D)
levantar(A)
en−mesa(A)
encima(B,D)
encima(A,C)libre(A)en−mesa(C)en−mesa(B)libre(B)en−mesa(D)libre(D)brazo−libre
libre(A)
brazo−libre
en−mesa(A)
La unica opcion para anadir en-mesa(A) para levantar(A) serıadejar(A) pero generarıa inconsistencia en O
![Page 136: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/136.jpg)
Ejemplo
encima(A,C)libre(A)en−mesa(C)en−mesa(B)libre(B)en−mesa(D)libre(D)brazo−libre
A0
A 8
en−mesa(A)
encima(B,D)
dejar(A)sujeto(A)
poner(B,D)sujeto(B)
libre(D)
quitar(A,<y>)
encima(A,<y>)
libre(A)
brazo−libre
(<y>,C)A
0
A0
A0
poner(A,<z>)
Arbol de búsqueda
dejar(A)
poner(B,D)
levantar(A) quitar(A,<y>)
![Page 137: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/137.jpg)
Ejemplo
• A ={A0,A∞,dejar(A),poner(B,D),quitar(A,< y >)}• O ={(A0 < A∞), (dejar(A)< A∞), (A0 <dejar(A)),
(poner(B,D)< A∞), (A0 <poner(B,D)),(quitar(A,< y >)< A∞), (A0 <quitar(A,< y >)),(quitar(A,< y >)<dejar(A))}
• L ={(dejar(A)en-mesa(A)−→ A∞),(poner(B,D)
encima(B,D)−→ A∞),
(quitar(A,< y >)sujeto(A)−→ dejar(A)),
(A0encima(A,<y>)
−→ quitar(A,< y >)),(A0libre(A)−→ quitar(A,< y >)),
(A0brazo-libre−→ quitar(A,< y >))}
• B ={(< y >,C)}
![Page 138: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/138.jpg)
Ejemplo
A0
A0
A0
A0
A 8
poner(A,<z>)
dejar(A)
poner(B,D)
levantar(A) quitar(A,<y>)
quitar(B,<t>)levantar(B)
Arbol de búsqueda
quitar(A,<y>)
encima(A,<y>)
libre(A)
brazo−libre
(<y>,C)
levantar(B)
encima(A,C)libre(A)en−mesa(C)en−mesa(B)libre(B)en−mesa(D)libre(D)brazo−libre
libre(B)
brazo−libre
en−mesa(B)
dejar(A)sujeto(A)
poner(B,D)sujeto(B)
libre(D)
en−mesa(A)
encima(B,D)
![Page 139: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/139.jpg)
Ejemplo
• A ={A0,A∞,dejar(A),poner(B,D),quitar(A,< y >),levantar(B)}• O ={(A0 < A∞), (dejar(A)< A∞), (A0 <dejar(A)),(poner(B,D)< A∞),
(A0 <poner(B,D)),(quitar(A,< y >)< A∞), (A0 <quitar(A,< y >)),(quitar(A,< y >)<dejar(A)),(levantar(B)< A∞), (A0 <levantar(B)),(levantar(B)<poner(B,D)),(quitar(A,< y >)<levantar(B))}
• L ={(dejar(A)en-mesa(A)−→ A∞),(poner(B,D)
encima(B,D)−→ A∞),
(quitar(A,< y >)sujeto(A)−→ dejar(A)),(A0
encima(A,<y>)−→ quitar(A,< y >)),
(A0libre(A)−→ quitar(A,< y >)),(A0
brazo-libre−→ quitar(A,< y >)),
(levantar(B)sujeto(B)−→ poner(B,D))}
• B ={(< y >,C)}
Amenazas: levantar(B) podrıa situarse entre A0 yquitar(A,< y >), borrando brazo-libreSolucion de amenaza: ordenar quitar(A,< y >) antes que levantar(B)
![Page 140: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/140.jpg)
Ejemplo
A0
A0
A0
A0
A0
A0 A
0A 8
en−mesa(A)
encima(B,D)A0
poner(A,<z>)
dejar(A)
poner(B,D)
levantar(A) quitar(A,<y>)
quitar(B,<t>)levantar(B)
quitar(A,<y>)
encima(A,<y>)
libre(A)
brazo−libre
(<y>,C)
levantar(B)
encima(A,C)libre(A)en−mesa(C)en−mesa(B)libre(B)en−mesa(D)libre(D)brazo−libre
libre(B)
brazo−libre
en−mesa(B)
dejar(A)sujeto(A)
poner(B,D)sujeto(B)
libre(D)
Arbol de búsqueda
Amenazas: quitar(A,< y >) podrıa situarse entre A0 ylevantar(B), borrando brazo-libreSolucion de amenaza: no hay
![Page 141: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/141.jpg)
Ejemplo
• A ={A0,A∞,dejar(A),poner(B,D),quitar(A,< y >),levantar(B)}• O ={(A0 < A∞), (dejar(A)< A∞), (A0 <dejar(A)), (poner(B,D)< A∞),
(A0 <poner(B,D)),(quitar(A,< y >)< A∞), (A0 <quitar(A,< y >)),(quitar(A,< y >)<dejar(A)),(levantar(B)< A∞), (A0 <levantar(B)),(levantar(B)<poner(B,D)),(quitar(A,< y >)<levantar(B))}
• L ={(dejar(A)en-mesa(A)−→ A∞),(poner(B,D)
encima(B,D)−→ A∞),
(quitar(A,< y >)sujeto(A)−→ dejar(A)),
(A0encima(A,<y>)
−→ quitar(A,< y >)),(A0libre(A)−→ quitar(A,< y >)),
(A0brazo-libre−→ quitar(A,< y >)),(levantar(B)
sujeto(B)−→ poner(B,D)),
(A0libre(D)−→ poner(B,D)),(A0
libre(B)−→ levantar(B)),
(A0en-mesa(B)−→ levantar(B)),(A0
brazo-libre−→ levantar(B))}• B ={(< y >,C)}
![Page 142: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/142.jpg)
Ejemplo
A0
A0
A0
A0
A0
A0 A
0A 8
en−mesa(A)
encima(B,D)A0
poner(A,<z>)
dejar(A)
poner(B,D)
levantar(A) quitar(A,<y>)
quitar(B,<t>)levantar(B)
quitar(A,<y>)
encima(A,<y>)
libre(A)
brazo−libre
(<y>,C)
levantar(B)
encima(A,C)libre(A)en−mesa(C)en−mesa(B)libre(B)en−mesa(D)libre(D)brazo−libre
libre(B)
brazo−libre
en−mesa(B)
dejar(A)sujeto(A)
poner(B,D)sujeto(B)
libre(D)
Arbol de búsqueda
dejar(A)
![Page 143: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/143.jpg)
Solucion del ejemplo
• A ={A0,A∞,dejar(A),poner(B,D),quitar(A,< y >),levantar(B)}• O ={(A0 < A∞), (dejar(A)< A∞), (A0 <dejar(A)),
(poner(B,D)< A∞), (A0 <poner(B,D)),(quitar(A,< y >)< A∞),(A0 <quitar(A,< y >)),(quitar(A,< y >)<dejar(A)),(levantar(B)< A∞), (A0 <levantar(B)),(levantar(B)<poner(B,D)),(quitar(A,< y >)<levantar(B)),(dejar(A)<levantar(B))}
• L ={(dejar(A)en-mesa(A)−→ A∞),(poner(B,D)
encima(B,D)−→ A∞),
(quitar(A,< y >)sujeto(A)−→ dejar(A)),(A0
encima(A,<y>)−→ quitar(A,< y >)),
(A0libre(A)−→ quitar(A,< y >)),(A0
brazo-libre−→ quitar(A,< y >)),
(levantar(B)sujeto(B)−→ poner(B,D)),(A0
libre(D)−→ poner(B,D)),
(A0libre(B)−→ levantar(B)),(A0
en-mesa(B)−→ levantar(B)),
(dejar(A)brazo-libre−→ levantar(B))}• B ={(< y >,C)}
![Page 144: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/144.jpg)
Mas informacion en
• Libros: [Allen et al., 1990,Ghallab et al., 2004]
• Otras referencias: [Fikes and Nilsson, 1971,Newell et al., 1972,Veloso et al., 1995,Weld, 1994]
![Page 145: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/145.jpg)
Indice
1 Introduccion
2 Planificacion clasica
3 Planificacion neoclasicaGrafos de planesPlanificacion SAT
4 Heurıstica
5 Otras cuestiones
![Page 146: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/146.jpg)
Indice
1 Introduccion
2 Planificacion clasica
3 Planificacion neoclasicaGrafos de planesPlanificacion SAT
4 Heurıstica
5 Otras cuestiones
![Page 147: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/147.jpg)
Grafos de planes. GRAPHPLAN
• A mediados de los 90, se produce una revolucion enplanificacion: GRAPHPLAN [Blum and Furst, 1995]
• Se basa en grafos de planificacion, que son estructuras querepresentan de forma completamente instanciada laresolucion del problema
• Dos fases:• Generacion de alcanzabilidad: niveles alternados de
proposicion y accion• Busqueda de plan valido: busqueda hacia atras de un
posible plan paralelo
![Page 148: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/148.jpg)
Fases del algoritmo
Dos fases• Expansion del grafo: extiende un grafo del plan hasta que
las condiciones necesarias para existencia de plan secumplen• alterna niveles de proposicion y accion• se calculan restricciones binarias de “mutex”• termina cuando todas las metas aparecen como no mutex
en el mismo nivel de proposicion• Extraccion de la solucion: busqueda hacia atras
• Se comienza la busqueda de que acciones concretasasignar a cada meta / submeta
• Si no se logra una asignacion valida, se generan masniveles de proposiciones / acciones y se repite el proceso
![Page 149: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/149.jpg)
Grafo de planificacion
0
at-truck-Aat-truck-Bat-package-Aat-package-Bin-package
load-truck-Aunload-truck-Aload-truck-Bunload-truck-Bdrive-truck-A-Bdrive-truck-B-A
P
0A
1P
1A PP
2 2 3PA
![Page 150: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/150.jpg)
Grafo de planificacion
0
at-truck-Aat-truck-Bat-package-Aat-package-Bin-package
load-truck-Aunload-truck-Aload-truck-Bunload-truck-Bdrive-truck-A-Bdrive-truck-B-A
P0
A
1P
1A PP
2 2 3PA
![Page 151: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/151.jpg)
Grafo de planificacion
0
at-truck-Aat-truck-Bat-package-Aat-package-Bin-package
load-truck-Aunload-truck-Aload-truck-Bunload-truck-Bdrive-truck-A-Bdrive-truck-B-A
P0
A1
P
1A PP
2 2 3PA
![Page 152: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/152.jpg)
Grafo de planificacion
0
at-truck-Aat-truck-Bat-package-Aat-package-Bin-package
load-truck-Aunload-truck-Aload-truck-Bunload-truck-Bdrive-truck-A-Bdrive-truck-B-A
P0
A1
P1
A
PP2 2 3
PA
![Page 153: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/153.jpg)
Grafo de planificacion
0
at-truck-Aat-truck-Bat-package-Aat-package-Bin-package
load-truck-Aunload-truck-Aload-truck-Bunload-truck-Bdrive-truck-A-Bdrive-truck-B-A
P0
A1
P1
A PP2
2 3PA
![Page 154: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/154.jpg)
Grafo de planificacion
0
at-truck-Aat-truck-Bat-package-Aat-package-Bin-package
load-truck-Aunload-truck-Aload-truck-Bunload-truck-Bdrive-truck-A-Bdrive-truck-B-A
P0
A1
P1
A PP2 2 3
PA
![Page 155: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/155.jpg)
Grafo de planificacion
0
at-truck-Aat-truck-Bat-package-Aat-package-Bin-package
load-truck-Aunload-truck-Aload-truck-Bunload-truck-Bdrive-truck-A-Bdrive-truck-B-A
P0
A1
P1
A PP2 2 3
PA
![Page 156: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/156.jpg)
Mutex
• Dos acciones son mutex si:• una borra una precondicion o efecto positivo de la otra
levantar(A) y quitar(C,B)
• una precondicion de una accion es mutex con otraprecondicion de la otra accion
• Dos proposiciones son mutex si:• cada accion que consiga la primera proposicion es mutex
con alguna accion que consiga la segunda
![Page 157: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/157.jpg)
Ejemplo de repeticion de expansion de grafo
9A
8A
7A
6A
A5
11A
10A
Accionesnivel k-1
P3
P6
P5
P4
P1
P2
Proposicionesnivel k-1
4A
3A
2A
1A
Accionesnivel k
G1
G2
G3
G4
Proposicionesnivel k
![Page 158: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/158.jpg)
Ejemplo de repeticion de expansion de grafo
9A
8A
7A
6A
A5
11A
10A
Accionesnivel k-1
P3
P6
P5
P4
P1
P2
Proposicionesnivel k-1
4A
3A
2A
1A
Accionesnivel k
G1
G2
G3
G4
Proposicionesnivel k
![Page 159: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/159.jpg)
Ejemplo de repeticion de expansion de grafo
9A
8A
7A
6A
A5
11A
10A
Accionesnivel k-1
P3
P6
P5
P4
P1
P2
Proposicionesnivel k-1
4A
3A
2A
1A
Accionesnivel k
G1
G2
G3
G4
Proposicionesnivel k
![Page 160: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/160.jpg)
Ejemplo de repeticion de expansion de grafo
9A
8A
7A
6A
A5
11A
10A
Accionesnivel k-1
P3
P6
P5
P4
P1
P2
Proposicionesnivel k-1
4A
3A
2A
1A
Accionesnivel k
G1
G2
G3
G4
Proposicionesnivel k
![Page 161: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/161.jpg)
Ejemplo de repeticion de expansion de grafo
9A
8A
7A
6A
A5
11A
10A
Accionesnivel k-1
P3
P6
P5
P4
P1
P2
Proposicionesnivel k-1
4A
3A
2A
1A
Accionesnivel k
G1
G2
G3
G4
Proposicionesnivel k
![Page 162: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/162.jpg)
Ejemplo de repeticion de expansion de grafo
9A
8A
7A
6A
A5
11A
10A
Accionesnivel k-1
P3
P6
P5
P4
P1
P2
Proposicionesnivel k-1
4A
3A
2A
1A
Accionesnivel k
G1
G2
G3
G4
Proposicionesnivel k
![Page 163: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/163.jpg)
Ejemplo de repeticion de expansion de grafo
9A
8A
7A
6A
A5
11A
10A
Accionesnivel k-1
P3
P6
P5
P4
P1
P2
Proposicionesnivel k-1
4A
3A
2A
1A
Accionesnivel k
G1
G2
G3
G4
Proposicionesnivel k
![Page 164: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/164.jpg)
Ejemplo de repeticion de expansion de grafo
9A
8A
7A
6A
A5
11A
10A
Accionesnivel k-1
P3
P6
P5
P4
P1
P2
Proposicionesnivel k-1
4A
3A
2A
1A
Accionesnivel k
G1
G2
G3
G4
Proposicionesnivel k
![Page 165: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/165.jpg)
Ejemplo de repeticion de expansion de grafo
9A
8A
7A
6A
A5
11A
10A
Accionesnivel k-1
P3
P6
P5
P4
P1
P2
Proposicionesnivel k-1
4A
3A
2A
1A
Accionesnivel k
G1
G2
G3
G4
Proposicionesnivel k
![Page 166: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/166.jpg)
Otras cuestiones
• Es completo y sound (el plan generado es valido)• Obtiene el plan paralelo optimo en terminos de numero de
pasos de ejecucion paralelo• No asegura encontrar el optimo en terminos de numero de
operadores• Memos: se guarda la informacion de que ha fallado en ese
nivel para cuando vuelva• Tiempo: se puede mejorar el algoritmo para tener en cuenta
la duracion de las acciones
![Page 167: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/167.jpg)
Eficiencia
• Se pueden implementar mecanismos que mejoran laeficiencia:• un vector de bits para cada estado• cuatro vectores de bits para cada accion instanciada (dos
para precondiciones y dos para efectos)• se puede guardar para cada proposicion y accion la primera
vez que aparecio en el grafo• se puede guardar para cada mutex el primer nivel donde
desaparecio• se pueden eliminar las proposiciones que no cambian su
valor
![Page 168: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/168.jpg)
Otros planificadores
• IPP: [Koehler et al., 1997]
• STAN: [Long and Fox, 1999]
• LPG: [Gerevini et al., 2003]
• TGP [Smith and Weld, 1999]
• Como un CSP: [Kambhampati, 2000]
![Page 169: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/169.jpg)
Mas informacion en
• Libro: [Ghallab et al., 2004]
• Otros sistemas: STAN [Long and Fox, 1999], IPP [Koehler etal., 1997], LPG [Gerevini et al., 2003]
• Visto como CSP dinamico: [Kambhampati, 2000]
• Mejorandolo con aprendizaje: [Kambhampati, 1999]
![Page 170: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/170.jpg)
Indice
1 Introduccion
2 Planificacion clasica
3 Planificacion neoclasicaGrafos de planesPlanificacion SAT
4 Heurıstica
5 Otras cuestiones
![Page 171: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/171.jpg)
SATPLAN
• El que la planificacion sea PSpace-Complete es ciertocuando la longitud de los planes puede serexponencialmente larga
• Sin embargo, si se trata de encontrar un plan que tengamenos de k pasos en la solucion, la dificultad se queda enNP-completo
• El problema se convierte en conocer “a priori” la longitud• Una solucion: busqueda binaria• Se convierte la planificacion a un problema de
satisfacibilidad de una formula logica (CNF) con unhorizonte n (longitud del plan)
• Se resuelve con una maquina SAT (WALKSAT, CHAFF, ...)• Si se encuentra la solucion, se para. Si no, se aumenta n y
se repite el proceso
![Page 172: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/172.jpg)
Estados como formulas proposicionales
• Los estados se pueden representar como formulasproposicionales:
on-table(A)∧clear(B)
• Las formulas proposicionales tambien pueden representarconjuntos de estados:
(on-table(A)∧clear (B))∨(on-table (A)∧clear(C))
• La codificacion de los estados es directa. Sin embargo,algunos modelos no deseados pueden satisfacer lasformulas
• Ademas, las formulas no codifican la dinamica del sistema
![Page 173: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/173.jpg)
Una posible codificacion
• A cada predicado instanciado se le anade el nivel en el que esta
en(obj1,aeropuerto1,1),en(obj1,aeropuerto1,2),...
• El estado inicial se representa como la conjuncion de todas lasproposiciones que son ciertas y todas las que son falsas en nivel 0
en(obj1,aeropuerto1,0),en(avion1,aeropuerto1,0),...
• Las metas se representan como la conjuncion de todas las proposicionesque deben ser ciertas y todas las que deben ser falsas en el instante n
en(obj1,oficina2,3),en(obj2,oficina1,3), ...
![Page 174: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/174.jpg)
Estado inicial y metas
• El estado inicial se codifica como una conjuncion depredicados instanciados ciertos/falsos en en el momentoinicial ∧
f0 ∧∧∼ f0
• La meta se codifica como una conjuncion de predicadosinstanciados que deben ser ciertos en nivel n∧
f∈G
fn
![Page 175: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/175.jpg)
Codificacion de acciones
• A cada accion instanciada se le anade el nivel en el que esta
cargar(obj1,avion1,aeropuerto1,1),cargar(obj1,avion1,aeropuerto1,2)
• Cada accion en el instante i necesita las precondiciones en el instante iy consigue los efectos en el instante i + 1
cargar(obj1,avion1,aeropuerto1,1) →en(obj1,aeropuerto1,1),en(avion1,aeropuerto1,1),dentro(obj1,avion1,2),∼en(obj1,aeropuerto1,2)
![Page 176: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/176.jpg)
Transiciones de estado como formulas
• Por tanto, un modelo valido debe satisfacer esas formulasen todos los momentos de tiempo t :
µ={on-table(A,t)← true,clear(A,t)← true,arm-empty(t)← true,holding(A,t + 1)← true,on-table(A,t + 1)← false,clear(A,t + 1)← false,arm-empty(t + 1)← false}
• En general, por cada accion ai =< p+i ,p
−i ,e
+i ,e
−i >∈ A:∧
ai∈A
∧t∈[0,n−1]
ai,t → p+i,t ∧ p−i,t ∧ e+
i,t+1 ∧ e−i,t+1
![Page 177: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/177.jpg)
Codificacion de acciones
• Se debe considerar tambien el problema de ejecutar dosacciones mutex al mismo tiempo• Solo se permite la ejecucion de una accion en cada
momento de tiempo (planes secuenciales)∧t=[0,n−1]
∧ai∈A
ai,t →∧
aj∈A,aj 6=ai
∼ aj,t
• Se calculan todos los mutexes entre acciones, M(ai ,aj ) y:∧t=[0,n−1]
∧ai∈A
ai,t →∧
aj∈A,M(aj ,ai )
∼ aj,t
![Page 178: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/178.jpg)
Planificacion como satisfacibilidad
• Dos tipos de algoritmos:• basados en Davis-Putnam: completos y validos• estocasticos (como WALKSAT): validos, pero no completos
![Page 179: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/179.jpg)
Problemas SAT
• SAT: problemas de satisfacibilidad logica• Dada: una formula arbitraria en logica proposicional (en
FNC)• Determinar: una asignacion de valor a las proposiciones
que haga cierta la formula• Algoritmo:
1 Estado-inicial es conjunto de asignaciones nula2 Seleccionar una proposicion y generar dos sucesores del
nodo actual: asignar verdadero a la proposicion y asignarfalso
3 Seleccionar por cual de los dos nodos seguir4 Sustituir el valor elegido por la proposicion en la formula
logica y simplificar5 Si la formula queda como verdadera, se termina6 Si la formula se hace falsa, se hace retroceso7 Si no, se vuelve a 2
![Page 180: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/180.jpg)
Problemas SAT
v2-x( v ) 1-x x2 3-x( v ) 1-x x3 4-x( v v ) 1x 4x( v )v v v
1-x
1x4xx2 x3
3v )( x3 4-x( v )v v
FV
2-x x2 -x
2
X
V F
x x3 4x
F
4-x
X
V F
V
4x
4
v-x3 )v( -x43x
V
X
xx3
![Page 181: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/181.jpg)
Problemas SAT
v2-x( v ) 1-x x2 3-x( v ) 1-x x3 4-x( v v ) 1x 4x( v )v v v
1-x
1x4xx2 x3
3v )( x3 4-x( v )v v
FV
2-x x2 -x
2
X
V F
x x3 4x
F
4-x
X
V F
V
4x
4
v-x3 )v( -x43x
V
X
xx3
![Page 182: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/182.jpg)
Problemas SAT
v2-x( v ) 1-x x2 3-x( v ) 1-x x3 4-x( v v ) 1x 4x( v )v v v
1-x
1x4xx2 x3
3v )( x3 4-x( v )v v
FV
2-x x2 -x
2
X
V F
x x3 4x
F
4-x
X
V F
V
4x
4
v-x3 )v( -x43x
V
X
xx3
![Page 183: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/183.jpg)
Problemas SAT
v2-x( v ) 1-x x2 3-x( v ) 1-x x3 4-x( v v ) 1x 4x( v )v v v
1-x
1x4xx2 x3
3v )( x3 4-x( v )v v
FV
2-x x2 -x
2
X
V F
x x3 4x
F
4-x
X
V F
V
4x
4
v-x3 )v( -x43x
V
X
xx3
![Page 184: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/184.jpg)
Problemas SAT
v2-x( v ) 1-x x2 3-x( v ) 1-x x3 4-x( v v ) 1x 4x( v )v v v
1-x
1x4xx2 x3
3v )( x3 4-x( v )v v
FV
2-x x2 -x
2
X
V F
x x3 4x
F
4-x
X
V F
V
4x
4
v-x3 )v( -x43x
V
X
xx3
![Page 185: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/185.jpg)
Mas informacion en
• Idea inicial: [Kautz and Selman, 1992]
• Tecnicas: SATPLAN [Kautz and Selman, 1996],BLACKBOX [Kautz and Selman, 1999]
![Page 186: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/186.jpg)
Indice
1 Introduccion
2 Planificacion clasica
3 Planificacion neoclasica
4 HeurısticaPlanificacion heurısticaRedes de tareas jerarquicasConocimiento de controlAprendizaje automatico
5 Otras cuestiones
![Page 187: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/187.jpg)
Indice
1 Introduccion
2 Planificacion clasica
3 Planificacion neoclasica
4 HeurısticaPlanificacion heurısticaRedes de tareas jerarquicasConocimiento de controlAprendizaje automatico
5 Otras cuestiones
![Page 188: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/188.jpg)
Heurısticas
• Tipos de heurısticas• Independientes de dominio: validas para cada dominio• Independientes de dominio: disenadas especialmente para
un determinado dominio
• Las aplicaciones reales tienen una mezcla de ambas• Ideal general: definir heurısticas independientes del dominio
en lugar de funciones dependientes de dominio ad-hoc(como en N-puzzle o Sokoban)
![Page 189: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/189.jpg)
Heurısticas como problemas relajados
• Origen de las heurısticas: soluciones optimas a problemasrelajados [Pearl, 1983]
• La relajacion se obtiene eliminando las listas deborrados [Bonet and Geffner, 2001]:
P = (O, I,G)→ P ′ = (O′, I,G)
O′ = {(pre(o),add(o), ∅)|(pre(o),add(o),del(o)) ∈ O}
• Una secuencia de acciones es un plan relajado si es unasolucion del problema relajado P ′ del problema original P:• Cuanto mas parecido sea P ′ a P, mas informada sera la
funcion heurıstica, h(· )• Cuanto mas simplificado sea P ′, mas facil sera computar
h(· )
![Page 190: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/190.jpg)
Relajacion sobre la alcanzabilidad
• Distancia mınima del estado s al literal p: numero mınimode acciones requeridas para transitar de s a un estado quecontenga p
gs(p) =
{0 si p ∈ smın
o∈O(p)[1 + gs(pre(o))] en otro caso
• El coste gs(C) de un conjunto de literales puede definirsecomo:• Costes aditivos: g+
s (C) =∑r∈C
gs(r)
• Costes max: gmaxs (C) = max
r∈Cgs(r)
![Page 191: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/191.jpg)
Ejemplo
encima(B,C)libre(B)brazo−libre
libre(B)brazo−libre
en−mesa(B)
libre(B)sujeto(C)
libre(C)en−mesa(C)brazo−libre
brazo−librelibre(B)encima(B,C)
sujeto(C)libre(B)
C
B
B
C
g(en−mesa(B)) = 2g(encima(C,B)) = 3
g+ = 2+3 = 5gmax = max {2,3} = 3
B
C
DEJAR(B)
LEVANTAR(B)QUITAR(B,C)
en−mesa(B) encima(C,B)
PONER(C,B)
sujeto(B)
QUITAR(C,x) LEVANTAR(C)
libre(C)
brazo−libreencima(C,x)
DEJAR(C) QUITAR(B,C)DEJAR(C,B)
sujeto(C)Estado inicial
Estado final
Estado inicial
![Page 192: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/192.jpg)
Heuristic Search Planning (HSP) [Bonet and Geffner, 2001]
• HSP: emplea la funcion heurıstica hadd = g+s con un
algoritmo de escalada hacia adelante• HSP2: emplea la funcion heurıstica hadd con un algoritmo
BFS hacia adelante• Inconvenientes:
• El algoritmo consume el 80 % del tiempo en computar h(· )• No considera la interaccion entre operadores, es decir,
busca ordenaciones secuenciales suboptimas encontraposicion con las ordenaciones paralelas optimas
• Alternativas:• HSPr (empleando regresion), GRT (busqueda bidireccional),
HSP∗ (optimo)• Utilizar GRAPHPLAN para capturar la interaccion entre
operadores
![Page 193: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/193.jpg)
GRAPHPLAN como heurıstica
• Sea P ′ = (O′, I,G) un problema relajado. GRAPHPLAN nomarcara ningun par de hechos o acciones comoexcluyentes, puesto que no existen eliminados
• GRAPHPLAN encuentra una solucion a P ′ en un tiempopolinomial en l (la mayor lista de anadidos), |I| y |O′|:〈O0,O1, . . . ,Om−1〉 donde Oi es el conjunto de operadoreselegidos en paralelo en el nivel i y m el primer nivel quecontiene todas las soluciones
• FF emplea la funcion heurıstica:
h(S) =∑
i=0,...,m−1
|Oi |
• Tıpicamente h(S) ≤ hadd
![Page 194: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/194.jpg)
Fast-Forward (FF) [Hoffmann and Nebel, 2001]
• Tecnica de busqueda: EHC, un tipo de tecnica en escalada• Usa una funcion heurıstica h(S): GRAPHPLAN relajado• Prefiere las acciones que ayudan (helpful actions)• El computo de la heurıstica se mejora prefiriendo los
NO-OPs y las acciones con menor dificultad• En plateaux, elige una variante de busqueda en amplitud• Si falla y tiene mas tiempo, llama a un A∗
![Page 195: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/195.jpg)
Ejemplo
Nivel 3
QUITAR (B,C)
LEVANTAR (C)
DEJAR (B)
B
C
encima(B,C)en−mesa(C)
libre(B)brazo−libre sujeto(B)
libre(C)
encima(B,C)en−mesa(C)
libre(B)brazo−libre sujeto(B)
libre(C)
encima(B,C)en−mesa(C)
libre(B)brazo−libre
encima(B,C)en−mesa(C)
libre(B)brazo−libre
libre(C)
sujeto(C)
sujeto(B)
libre(C)
en−mesa(B)libre(B)encima(C,B)
C
B
PONER (C,B)
Solucion = {QUITAR(B,C), <LEVANTAR(C),DEJAR(B)>, PONER(C,B)}
h(S) = 1 + 2 + 1 = 4
Nivel 0 Nivel 1
sujeto(C)
Nivel 2
en−mesa(B)
libre(B)
![Page 196: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/196.jpg)
LPG [Gerevini et al., 2003]
• Construye un grafo de acciones• Niveles de proposicion y accion• Las metas y el estado inicial estan• Si una accion aparece, esta ligada a sus efectos y a sus
precondiciones• Tipos
• lineal: luego se puede transformar a un plan paralelo• paralelo
• Trata progresivamente los fallos• acciones mutex (si planes paralelos)• una accion con precondiciones no conseguidas• metas pendientes
![Page 197: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/197.jpg)
Busqueda en LPG
• Heurıstica con parametros
h(n) = αhc(n) + βht (n) + γhs(n)
donde• hc(n): coste estimado hasta meta (coste solucion)• ht (n): tiempo estimado hasta meta (tiempo de ejecucion)• hs(n): busqueda estimada hasta meta (nodos)
• Busqueda estocastica en el espacio de planes con restart• Vecindad:
• anadir una accion• borrar una accion• (cambiar de orden dos acciones)
• Permite replanificacion: LPG-ADAPT [Fox et al., 2006]
![Page 198: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/198.jpg)
Ejemplo de grafo de acciones temporal
![Page 199: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/199.jpg)
Otros planificadores estocasticos
• Basados en RRT [LaValle and Kuffner, 2001]:RRTPLAN [Burfoot et al., 2006], BRT [Alcazar et al., 2011]
• Basados en busqueda local estocastica: Arvand [Nakhostand Muller, 2009]
![Page 200: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/200.jpg)
Nueva generacion. Fast-Downward (FD)
• FAST-DOWNWARD [Helmert, 2006]
• Representacion: SAS+ (traducido desde PDDL)• Heurısticas: grafo causal+FF+. . .• Busqueda
• busqueda heurıstica con multiples colas (cada estado seevalua una vez por cada heurıstica y se inserta en la colacorrespondiente)
• evaluacion heurıstica diferida (se crean con el valor de supadre, se evaluan cuando se expanden)
• operadores preferidos (por cada heurıstica)
![Page 201: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/201.jpg)
Landmarks
![Page 202: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/202.jpg)
Landmarks
![Page 203: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/203.jpg)
Landmarks
![Page 204: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/204.jpg)
Landmarks
![Page 205: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/205.jpg)
Landmarks
![Page 206: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/206.jpg)
Landmarks
![Page 207: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/207.jpg)
Landmarks
![Page 208: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/208.jpg)
Portfolios
• No hay un planificador mejor que todos en todos losdominios
• Aprender un conjunto de pesos para parametrizar:• un conjunto de planificadores: portfolio• un planificador: auto-tuning
• Tipos• Dependiente de dominio: PbP• Independiente de dominio: Fast-Downward Stone Soup
(FDSS)• Ejemplos:
• aprender que planificador es el mejor• aprender un conjunto de pesos para los parametros• aprender un conjunto de valores para los parametros• aprender el tiempo a dedicar a cada planificador
![Page 209: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/209.jpg)
Bases de datos de patrones (PDBs)
• Calcular solucion (optima) para un conjunto deabstracciones
• Valor heurıstico para cada estado es:• simple: el correspondiente de su abstraccion• max: maximo del conjunto de abstracciones• aditivas: suma del conjunto de abstracciones
• Alternativa: alternar un proceso de mezcla y reduccionPDBs (merge&shrink)
![Page 210: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/210.jpg)
Ejemplo de una PDB1
• Un paquete: L, R, A, B• Camion A: L, R• Camion B: L, R1Malte Helmert y Gabrielle Rogers
![Page 211: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/211.jpg)
Ejemplo de una PDB. Abstrayendo un paquete2
2Malte Helmert y Gabrielle Rogers
![Page 212: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/212.jpg)
Ejemplo de una PDB. Abstrayendo un paquete y el camion A3
3Malte Helmert y Gabrielle Rogers
![Page 213: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/213.jpg)
Estado del arte (2011)
• Optimal: Fast-Downward Stone Soup• No-optima: Lama2011• Multi-core: Arvand Herd• Temporal: DAEYAHSP• Aprendizaje: PbP
![Page 214: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/214.jpg)
Indice
1 Introduccion
2 Planificacion clasica
3 Planificacion neoclasica
4 HeurısticaPlanificacion heurısticaRedes de tareas jerarquicasConocimiento de controlAprendizaje automatico
5 Otras cuestiones
![Page 215: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/215.jpg)
Planificacion jerarquica
• Se distingue de la planificacion clasica en:• Que planifica: en vez de un conjunto de metas G, el conjunto
de acciones que llevan a cabo una actividad o tarea• Como planifica: descomponiendo tareas en subtareas de
acuerdo con la definicion de varios metodos
• Se diferencian:• Simple Task Networks (STNs): la descomposicion se aplica
en cumplimiento de unas precondiciones segun unajerarquıa
• Hierarchical Task Networks (HTNs): la descomposicion serealiza en un conjunto de tareas que cumplen ciertasrestricciones
• Muy eficiente si se define bien el conocimiento• Los dominios son mas complicados de definir
![Page 216: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/216.jpg)
Tipos de planificacion jerarquica
• Los planes se van generando gradualmente de operadoresmas generales a mas concretos:• Estableciendo niveles de abstraccion en las precondiciones
de los operadores: ABSTRIPS [Sacerdoti, 1974],ALPINE [Knoblock, 1994]
• Refinando los operadores sucesivamente: NOAH [Sacerdoti,1977], MOLGEN [Stefik, 1981b,Stefik, 1981a]
• Preprogramando en que se divide cada operador:O-PLAN [Currie and Tate, 1991], SHOP2 [Nau et al., 2003]
![Page 217: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/217.jpg)
Metodos STN
• Un metodo STN es una tupla m = (name(m), task(m),precond(m), network(m)) donde:• name(m) es el nombre del metodo• task(m) es una tarea no primitiva• precond(m) son las precondiciones del metodo• network(m) son las subtareas del metodo
• Un problema de planificacion STN es una tuplaP = (s0,w ,O,M) donde:• s0 es el estado inicial• w es una jerarquıa de tareas• D = (O,M) es el dominio de planificacion —operadores y
metodos
![Page 218: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/218.jpg)
Ejemplo STN
metodo: iniciar-inversion (b1, b2)tarea: invertir-pila (b1)preconds: libre (b1), encima (b1, b2)subtareas: quitar (b1, b2), dejar (b1),
invertir-sobre-pila (b2, b1)
metodo: invertir (b1, b2, b3)tarea: invertir-sobre-pila (b1, b2)preconds: libre (b1), libre (b2), encima (b1, b3)subtareas: quitar (b1, b3), poner (b1, b2),
invertir-sobre-pila (b3, b1)
metodo: finalizar-inversion (b1, b2)tarea: invertir-sobre-pila (b1, b2)preconds: libre (b1), libre (b2), en-mesa (b1)subtareas: levantar (b1), poner (b1, b2)
![Page 219: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/219.jpg)
Simple Task Networks. STNs
C
B
B
C
invertir−pila (B)
dejar (B)quitar (B,C) invertir−sobre−pila (C,B)
poner (C,B) levantar(C)
![Page 220: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/220.jpg)
Ejemplo STN (cont.)
quitar (A,B) dejar (A) invertir−sobre−pila (B,A)
poner (B,A)quitar (B,C) invertir−sobre−pila (C,B)
B
C
A
B
C A
poner (C,B)levantar (C)
C A
B
A
B
C
iniciar−inversion (A,B)
invertir−pila (A)
invertir (B,A,C)
finalizar−inversion (C,B)
![Page 221: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/221.jpg)
Hierarchical Task Networks (HTN)
• Tipos de tareas: compuestas o primitivas• Entradas: estado inicial, tareas compuestas, orden en el
que se deben conseguir y teorıa del dominio (metodos yacciones)
• Metodos: estan formados por• tarea compuestas• precondiciones para poder realizar la descomposicion• conjunto de subtareas en las que se puede descomponer• restricciones que se deben cumplir en esas subtareas
• Acciones:• consiguen las tareas primitivas• son semejantes a los operadores de planificacion STRIPS• formadas por: tarea primitiva, precondiciones y efectos
![Page 222: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/222.jpg)
Ejemplo de teorıa del dominio (acciones)
(defdomain logistics((:operator (!load-truck ?obj ?truck ?loc)
((obj-at ?obj ?loc)(:protection (truck-at ?truck ?loc)))
((in-truck ?obj ?truck)))
(:operator (!unload-truck ?obj ?truck ?loc)((in-truck ?obj ?truck)(:protection (truck-at ?truck ?loc)))
((obj-at ?obj ?loc))). . .))
![Page 223: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/223.jpg)
Metodos (same-city-deliver)
(:method (obj-at ?obj ?loc-goal) same-city-deliver((in-city ?loc-goal ?city-goal) (obj-at ?obj ?loc-now)(in-city ?loc-now ?city-goal) (truck ?truck ?city-goal))
((:task in-city-delivery ?truck ?obj ?loc-now ?loc-goal))different-city-deliver
((in-city ?loc-goal ?city-goal) (obj-at ?obj ?loc-now)(in-city ?loc-now ?city-now) (different ?city-goal ?city-now)(truck ?truck-now ?city-now) (truck ?truck-goal ?city-goal)(airport ?airport-now) (in-city ?airport-now ?city-now)(airport ?airport-goal) (in-city ?airport-goal ?city-goal))
(:ordered (:task in-city-delivery ?truck-now ?obj ?loc-now ?airport-now)(:task air-deliver-obj ?obj ?airport-now ?airport-goal)(:task in-city-delivery ?truck-goal ?obj ?airport-goal ?loc-goal)))
![Page 224: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/224.jpg)
Resolucion de problemas con HTN
• Proceso: descomposicion de tareas compuestas en tareasmas sencillas hasta que todas sean tareas primitivas
• Plan: composicion de todas las acciones relativas a lastareas primitivas, conservando restricciones de orden
![Page 225: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/225.jpg)
Variantes
• SIPE, O-PLAN, UMCP• permiten ordenes parciales entre subtareas• difieren en el tipo de restricciones que pueden definir
• SHOP• orden total en las subtareas• mas eficiente, menos rico en representacion
![Page 226: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/226.jpg)
SHOP2
• SHOP2 es un planificador HTN independiente del dominiocuyos metodos deben ser especializados en cada dominio
• Como otros planificadores HTN, SHOP2 planifica las tareasen el orden en que seran ejecutadas
• Ademas de tareas, metodos y operadores, SHOP2 aceptaaxiomas como clausulas de Horn e invocaciones afunciones externas
![Page 227: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/227.jpg)
Algoritmo SHOP2 (s,T ,D)
1 Escoger una tarea t ∈ T que no tenga predecesoras deacuerdo con las restricciones
2 Si t es una tarea primitiva:• Elegir una accion a que unifique con t mediante θ y cuyas
precondiciones se cumplan en s• Actualizar s borrando del(a) y anadiendo add(a)• Eliminar t de T y aplicar θ
3 Si t es una tarea no primitiva (o compuesta):• Elegir un metodo m que descomponga t en subtareas segunθ
• Eliminar t de T y anadir las subtareas de m propagando lasrestricciones
4 Volver al principio
![Page 228: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/228.jpg)
Aplicaciones
• SIPE: fabrica de cerveza• O-PLAN: operaciones militares• BRIDGE-BARON: campeon del mundo de bridge
computacional 1997• SIADEX: gestion de incendios
![Page 229: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/229.jpg)
Indice
1 Introduccion
2 Planificacion clasica
3 Planificacion neoclasica
4 HeurısticaPlanificacion heurısticaRedes de tareas jerarquicasConocimiento de controlAprendizaje automatico
5 Otras cuestiones
![Page 230: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/230.jpg)
Conocimiento de control
• Planificacion necesita heurısticas• Tipos
• Independientes del dominio: HSP, FF, LPG, . . .• Dependientes del dominio
• Formas de codificar conocimiento de control• reglas de control o de reescritura• jerarquıa de tareas• precondiciones de operadores (funciones, nuevos
predicados, . . . )• macro-operadores, casos, polıticas, . . .
![Page 231: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/231.jpg)
Indice
1 Introduccion
2 Planificacion clasica
3 Planificacion neoclasica
4 HeurısticaPlanificacion heurısticaRedes de tareas jerarquicasConocimiento de controlAprendizaje automatico
5 Otras cuestiones
![Page 232: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/232.jpg)
Motivacion
• Los algoritmos de planificacion actuales permiten resolvermuchos problemas eficientemente, utilizando:• heurısticas independientes del dominio con busquedas
eficientes• heurısticas dependientes del dominio creadas a mano
• Todavıa hay sitio para mejorar• Solucion:
• aprendizaje automatico integrado con planificacion paraextraer conocimiento automaticamente de uno o variosproblemas y ası mejorar el rendimiento en futuros problemas
![Page 233: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/233.jpg)
Aplicacion de aprendizaje a planificacion
Planificador
Aprendizajemodelo
DominioPDDL
Ingeniero
Aprendizajeheurísticas
![Page 234: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/234.jpg)
Tipos de tecnicas de aprendizaje
• Metodos inductivos (neuronas, geneticos, ID3, ILP, . . . )• intensivos en datos: extraen descripciones generales de un
concepto a partir de muchos ejemplos• Metodos deductivos (macro-operadores, EBL, . . . )
• intensivos en conocimiento: explican y analizan un soloejemplo de un concepto
• Enfoques hıbridos (EBL+ILP, analogy, Q-RRL, EVOCK, . . . )• metodo deductivo para extraer informacion de un episodio
de planificacion• metodo inductivo para generalizar/especializar el
conocimiento adquirido
![Page 235: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/235.jpg)
¿Que podemos hacer?
Aprendizaje de heurısticas• ¿Como?
• Observando las decisiones realizadas por el planificadordurante la busqueda
• Observando las secuencias de decisiones realizadas• Guardando y reutilizando planes previos• Generando conocimiento pseudo-aleatoriamente• Por demostracion
• ¿Que?• Reglas de control [De la Rosa et al., 2011]• Macro-operadores• Polıticas• Casos [De la Rosa et al., 2007]
![Page 236: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/236.jpg)
Macro-Operadores
• Una de las primeras ideas de aplicar aprendizaje a planificacion
• Se utilizo para mejorar la eficiencia del planificador STRIPS [Fikeset al., 1972]
• Concebido con un doble objetivo:• Aprendizaje de secuencias de acciones• Monitorizacion de ejecucion de planes
• Idea clave: crear nuevos operadores juntando las descripcionesde los operadores individuales que formaban un plan
• Se crean construyendo tablas triangulares y parametrizando
• Ejemplos: cubo de Rubik [Korf, 1985], ACT∗ [Anderson, 1983],MORRIS [Minton, 1985], MACRO-FF [Botea et al., 2005] . . .
• Tambien hay macro-operadores iterativos y condicionales [Chengand Carbonell, 1986,Shell and Carbonell, 1989]
![Page 237: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/237.jpg)
Ejemplo de STRIPS
A
AB
Estado inicial (E )0 Metas
en-mesa(A) E0
en-mesa(A)DEJAR(A) E0
sujeto(A)DEJAR(A)en-mesa(A)
E0
QUITAR(A,B)
en-mesa(A)
sujeto(A)DEJAR(A)
EE
LEVANTAR(A)sujeto(A)DEJAR(A)en-mesa(A)
00
metabucle de
X
X
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A)
en-mesa(A) brazo-libre
E0
libre(A) brazo-libre encima(A,B)QUITAR(A,B)sujeto(A)DEJAR(A)en-mesa(A)
E0
E1sujeto(A)DEJAR(A)en-mesa(A)
B
A
E1
E2en-mesa(A) B A
E2
![Page 238: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/238.jpg)
Ejemplo de STRIPS
A
AB
Estado inicial (E )0 Metas
en-mesa(A) E0
en-mesa(A)DEJAR(A) E0
sujeto(A)DEJAR(A)en-mesa(A)
E0
QUITAR(A,B)
en-mesa(A)
sujeto(A)DEJAR(A)
EE
LEVANTAR(A)sujeto(A)DEJAR(A)en-mesa(A)
00
metabucle de
X
X
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A)
en-mesa(A) brazo-libre
E0
libre(A) brazo-libre encima(A,B)QUITAR(A,B)sujeto(A)DEJAR(A)en-mesa(A)
E0
E1sujeto(A)DEJAR(A)en-mesa(A)
B
A
E1
E2en-mesa(A) B A
E2
![Page 239: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/239.jpg)
Ejemplo de STRIPS
A
AB
Estado inicial (E )0 Metas
en-mesa(A) E0
en-mesa(A)DEJAR(A) E0
sujeto(A)DEJAR(A)en-mesa(A)
E0
QUITAR(A,B)
en-mesa(A)
sujeto(A)DEJAR(A)
EE
LEVANTAR(A)sujeto(A)DEJAR(A)en-mesa(A)
00
metabucle de
X
X
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A)
en-mesa(A) brazo-libre
E0
libre(A) brazo-libre encima(A,B)QUITAR(A,B)sujeto(A)DEJAR(A)en-mesa(A)
E0
E1sujeto(A)DEJAR(A)en-mesa(A)
B
A
E1
E2en-mesa(A) B A
E2
![Page 240: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/240.jpg)
Ejemplo de STRIPS
A
AB
Estado inicial (E )0 Metas
en-mesa(A) E0
en-mesa(A)DEJAR(A) E0
sujeto(A)DEJAR(A)en-mesa(A)
E0
QUITAR(A,B)
en-mesa(A)
sujeto(A)DEJAR(A)
EE
LEVANTAR(A)sujeto(A)DEJAR(A)en-mesa(A)
00
metabucle de
X
X
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A)
en-mesa(A) brazo-libre
E0
libre(A) brazo-libre encima(A,B)QUITAR(A,B)sujeto(A)DEJAR(A)en-mesa(A)
E0
E1sujeto(A)DEJAR(A)en-mesa(A)
B
A
E1
E2en-mesa(A) B A
E2
![Page 241: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/241.jpg)
Ejemplo de STRIPS
A
AB
Estado inicial (E )0 Metas
en-mesa(A) E0
en-mesa(A)DEJAR(A) E0
sujeto(A)DEJAR(A)en-mesa(A)
E0
QUITAR(A,B)
en-mesa(A)
sujeto(A)DEJAR(A)
EE
LEVANTAR(A)sujeto(A)DEJAR(A)en-mesa(A)
00
metabucle de
X
X
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A)
en-mesa(A) brazo-libre
E0
libre(A) brazo-libre encima(A,B)QUITAR(A,B)sujeto(A)DEJAR(A)en-mesa(A)
E0
E1sujeto(A)DEJAR(A)en-mesa(A)
B
A
E1
E2en-mesa(A) B A
E2
![Page 242: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/242.jpg)
Ejemplo de STRIPS
A
AB
Estado inicial (E )0 Metas
en-mesa(A) E0
en-mesa(A)DEJAR(A) E0
sujeto(A)DEJAR(A)en-mesa(A)
E0
QUITAR(A,B)
en-mesa(A)
sujeto(A)DEJAR(A)
EE
LEVANTAR(A)sujeto(A)DEJAR(A)en-mesa(A)
00
metabucle de
X
X
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A)
en-mesa(A) brazo-libre
E0
libre(A) brazo-libre encima(A,B)QUITAR(A,B)sujeto(A)DEJAR(A)en-mesa(A)
E0
E1sujeto(A)DEJAR(A)en-mesa(A)
B
A
E1
E2en-mesa(A) B A
E2
![Page 243: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/243.jpg)
Ejemplo de STRIPS
A
AB
Estado inicial (E )0 Metas
en-mesa(A) E0
en-mesa(A)DEJAR(A) E0
sujeto(A)DEJAR(A)en-mesa(A)
E0
QUITAR(A,B)
en-mesa(A)
sujeto(A)DEJAR(A)
EE
LEVANTAR(A)sujeto(A)DEJAR(A)en-mesa(A)
00
metabucle de
X
X
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A)
en-mesa(A) brazo-libre
E0
libre(A) brazo-libre encima(A,B)QUITAR(A,B)sujeto(A)DEJAR(A)en-mesa(A)
E0
E1sujeto(A)DEJAR(A)en-mesa(A)
B
A
E1
E2en-mesa(A) B A
E2
![Page 244: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/244.jpg)
Ejemplo de STRIPS
A
AB
Estado inicial (E )0 Metas
en-mesa(A) E0
en-mesa(A)DEJAR(A) E0
sujeto(A)DEJAR(A)en-mesa(A)
E0
QUITAR(A,B)
en-mesa(A)
sujeto(A)DEJAR(A)
EE
LEVANTAR(A)sujeto(A)DEJAR(A)en-mesa(A)
00
metabucle de
X
X
LEVANTAR(A)
en-mesa(A)DEJAR(A)sujeto(A)
en-mesa(A) brazo-libre
E0
libre(A) brazo-libre encima(A,B)QUITAR(A,B)sujeto(A)DEJAR(A)en-mesa(A)
E0
E1sujeto(A)DEJAR(A)en-mesa(A)
B
A
E1
E2en-mesa(A) B A
E2
![Page 245: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/245.jpg)
Macro-operador
∗ encima(A,B)∗ libre(A)∗ brazo-libre QUITAR(A,B)
sujeto(A)libre(B)
![Page 246: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/246.jpg)
Macro-operador
∗ encima(A,B)∗ libre(A)∗ brazo-libre QUITAR(A,B)
∗ sujeto(A)libre(B) DEJAR(A)libre(B) brazo-libre
en-mesa(A)libre(A)
![Page 247: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/247.jpg)
Parametrizacion de macro-operador
∗ encima(x ,y )∗ libre(x)∗ brazo-libre QUITAR(x ,y )
∗ sujeto(x)libre(y ) DEJAR(x)libre(y ) brazo-libre
en-mesa(x)libre(x)
![Page 248: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/248.jpg)
Otro ejemplo de parametrizacion
∗ en-mesa(x)∗ libre(x)∗ brazo-libre levantar(x)∗ libre(y) ∗ sujeto(x)
poner(x,y)∗ libre(z) libre(x)∗ encima(z,w) encima(x,y)
∗ brazo-libre quitar(z,w)libre(x) sujeto(z)encima(x,y) libre(w)
![Page 249: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/249.jpg)
Ejemplo de STRIPS
A
B
ABE0
E0on-table(B)on-table(A)
E0C
GoalsInitial state
on-table(A)on-table(B)on-table(B)on-table(A)
on-table(B)on-table(A)on-table(B)on-table(A)
E0E0
E0
UNSTACK-AND-PUT-DOWN(A,B)on-table(A)on-table(B)on-table(B)on-table(A)
on-table(A) on-table(B)on-table(B)on-table(A)
PUT-DOWN(A)
UNSTACK-AND-PUT-DOWN(A,C)on-table(A)on-table(B)on-table(B)on-table(A)
E0
clear(A) arm-empty on(A,B)UNSTACK-AND-PUT-DOWN(A,B)
on-table(A)on-table(B)on-table(B)on-table(A)
E 1
A
B
C
E1E1
E1
UNSTACK-AND-PUT-DOWN(B,A)on-table(B)on-table(B)on-table(A)
UNSTACK-AND-PUT-DOWN(B,C)
on-table(A) on-table(B)on-table(B)
on-table(B)on-table(B)
on-table(A)
PUT-DOWN(B)
loopgoal
X
X
E1AB
E 2
C
clear(B) arm-empty on(B,C)UNSTACK-AND-PUT-DOWN(B,C)
on-table(B)on-table(A) on-table(B)
![Page 250: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/250.jpg)
Ejemplo de STRIPS
A
B
ABE0
E0on-table(B)on-table(A)
E0C
GoalsInitial state
on-table(A)on-table(B)on-table(B)on-table(A)
on-table(B)on-table(A)on-table(B)on-table(A)
E0E0
E0
UNSTACK-AND-PUT-DOWN(A,B)on-table(A)on-table(B)on-table(B)on-table(A)
on-table(A) on-table(B)on-table(B)on-table(A)
PUT-DOWN(A)
UNSTACK-AND-PUT-DOWN(A,C)on-table(A)on-table(B)on-table(B)on-table(A)
E0
clear(A) arm-empty on(A,B)UNSTACK-AND-PUT-DOWN(A,B)
on-table(A)on-table(B)on-table(B)on-table(A)
E 1
A
B
C
E1E1
E1
UNSTACK-AND-PUT-DOWN(B,A)on-table(B)on-table(B)on-table(A)
UNSTACK-AND-PUT-DOWN(B,C)
on-table(A) on-table(B)on-table(B)
on-table(B)on-table(B)
on-table(A)
PUT-DOWN(B)
loopgoal
X
X
E1AB
E 2
C
clear(B) arm-empty on(B,C)UNSTACK-AND-PUT-DOWN(B,C)
on-table(B)on-table(A) on-table(B)
![Page 251: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/251.jpg)
Ejemplo de STRIPS
A
B
ABE0
E0on-table(B)on-table(A)
E0C
GoalsInitial state
on-table(A)on-table(B)on-table(B)on-table(A)
on-table(B)on-table(A)on-table(B)on-table(A)
E0E0
E0
UNSTACK-AND-PUT-DOWN(A,B)on-table(A)on-table(B)on-table(B)on-table(A)
on-table(A) on-table(B)on-table(B)on-table(A)
PUT-DOWN(A)
UNSTACK-AND-PUT-DOWN(A,C)on-table(A)on-table(B)on-table(B)on-table(A)
E0
clear(A) arm-empty on(A,B)UNSTACK-AND-PUT-DOWN(A,B)
on-table(A)on-table(B)on-table(B)on-table(A)
E 1
A
B
C
E1E1
E1
UNSTACK-AND-PUT-DOWN(B,A)on-table(B)on-table(B)on-table(A)
UNSTACK-AND-PUT-DOWN(B,C)
on-table(A) on-table(B)on-table(B)
on-table(B)on-table(B)
on-table(A)
PUT-DOWN(B)
loopgoal
X
X
E1AB
E 2
C
clear(B) arm-empty on(B,C)UNSTACK-AND-PUT-DOWN(B,C)
on-table(B)on-table(A) on-table(B)
![Page 252: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/252.jpg)
Ejemplo de STRIPS
A
B
ABE0
E0on-table(B)on-table(A)
E0C
GoalsInitial state
on-table(A)on-table(B)on-table(B)on-table(A)
on-table(B)on-table(A)on-table(B)on-table(A)
E0E0
E0
UNSTACK-AND-PUT-DOWN(A,B)on-table(A)on-table(B)on-table(B)on-table(A)
on-table(A) on-table(B)on-table(B)on-table(A)
PUT-DOWN(A)
UNSTACK-AND-PUT-DOWN(A,C)on-table(A)on-table(B)on-table(B)on-table(A)
E0
clear(A) arm-empty on(A,B)UNSTACK-AND-PUT-DOWN(A,B)
on-table(A)on-table(B)on-table(B)on-table(A)
E 1
A
B
C
E1E1
E1
UNSTACK-AND-PUT-DOWN(B,A)on-table(B)on-table(B)on-table(A)
UNSTACK-AND-PUT-DOWN(B,C)
on-table(A) on-table(B)on-table(B)
on-table(B)on-table(B)
on-table(A)
PUT-DOWN(B)
loopgoal
X
X
E1AB
E 2
C
clear(B) arm-empty on(B,C)UNSTACK-AND-PUT-DOWN(B,C)
on-table(B)on-table(A) on-table(B)
![Page 253: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/253.jpg)
Ejemplo de STRIPS
A
B
ABE0
E0on-table(B)on-table(A)
E0C
GoalsInitial state
on-table(A)on-table(B)on-table(B)on-table(A)
on-table(B)on-table(A)on-table(B)on-table(A)
E0E0
E0
UNSTACK-AND-PUT-DOWN(A,B)on-table(A)on-table(B)on-table(B)on-table(A)
on-table(A) on-table(B)on-table(B)on-table(A)
PUT-DOWN(A)
UNSTACK-AND-PUT-DOWN(A,C)on-table(A)on-table(B)on-table(B)on-table(A)
E0
clear(A) arm-empty on(A,B)UNSTACK-AND-PUT-DOWN(A,B)
on-table(A)on-table(B)on-table(B)on-table(A)
E 1
A
B
C
E1E1
E1
UNSTACK-AND-PUT-DOWN(B,A)on-table(B)on-table(B)on-table(A)
UNSTACK-AND-PUT-DOWN(B,C)
on-table(A) on-table(B)on-table(B)
on-table(B)on-table(B)
on-table(A)
PUT-DOWN(B)
loopgoal
X
X
E1AB
E 2
C
clear(B) arm-empty on(B,C)UNSTACK-AND-PUT-DOWN(B,C)
on-table(B)on-table(A) on-table(B)
![Page 254: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/254.jpg)
Ejemplo de STRIPS
A
B
ABE0
E0on-table(B)on-table(A)
E0C
GoalsInitial state
on-table(A)on-table(B)on-table(B)on-table(A)
on-table(B)on-table(A)on-table(B)on-table(A)
E0E0
E0
UNSTACK-AND-PUT-DOWN(A,B)on-table(A)on-table(B)on-table(B)on-table(A)
on-table(A) on-table(B)on-table(B)on-table(A)
PUT-DOWN(A)
UNSTACK-AND-PUT-DOWN(A,C)on-table(A)on-table(B)on-table(B)on-table(A)
E0
clear(A) arm-empty on(A,B)UNSTACK-AND-PUT-DOWN(A,B)
on-table(A)on-table(B)on-table(B)on-table(A)
E 1
A
B
C
E1E1
E1
UNSTACK-AND-PUT-DOWN(B,A)on-table(B)on-table(B)on-table(A)
UNSTACK-AND-PUT-DOWN(B,C)
on-table(A) on-table(B)on-table(B)
on-table(B)on-table(B)
on-table(A)
PUT-DOWN(B)
loopgoal
X
X
E1AB
E 2
C
clear(B) arm-empty on(B,C)UNSTACK-AND-PUT-DOWN(B,C)
on-table(B)on-table(A) on-table(B)
![Page 255: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/255.jpg)
Generacion de macro-operadores
• Se recogen las soluciones a N problemas de entrenamiento
• s1 : a11,a21, . . . ,an1• s1 : a12,a22, . . . ,an2• . . .• sm : a1m,a2m, . . . ,anm
• Se calculan todas las subsecuencias de 2 acciones, 3acciones, . . . , K acciones
• Se realiza algun analisis de utilidad• se filtran aquellas que no superan un umbral de frecuencia• se utilizan para resolver otros P problemas
![Page 256: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/256.jpg)
Discusion: Macro-Operadores
• Ventajas:• Reutilizacion de experiencias pasadas• Replanificacion despues de fallos• Menor profundidad de busqueda• Menor tiempo de equiparacion• Efecto secundario: aprendizaje de subsecuencias de
operadores• Desventajas:
• Incremento del factor de ramificacion
• Necesidad de considerar la utilidad
![Page 257: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/257.jpg)
Busqueda
![Page 258: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/258.jpg)
Busqueda
![Page 259: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/259.jpg)
Busqueda
![Page 260: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/260.jpg)
Busqueda
![Page 261: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/261.jpg)
Busqueda
![Page 262: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/262.jpg)
Busqueda
![Page 263: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/263.jpg)
Busqueda
![Page 264: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/264.jpg)
Busqueda
![Page 265: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/265.jpg)
Busqueda
![Page 266: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/266.jpg)
Aprendizaje clasico
EBL [Minton, 1988], EBL+ILP [Veloso et al., 1995]
Reglas de control
If meta(en-mesa(A)),meta(encima(C,B)),estado(encima(A,B)),estado(encima(B,D)),. . .
Then selecciona(quitar(A,B))
![Page 267: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/267.jpg)
Aprendizaje con contextos utiles
Roller [De la Rosa et al., 2011]
Reglas de control
If meta(en-mesa(A)),meta(encima(C,B)),candidato(levantar(C)),candidato(quitar(A,B))
Then selecciona(quitar(A,B))
![Page 268: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/268.jpg)
Resultados
DEPTH-FIRST BEST-FIRST HELPFUL BEST-FIRSTDomains roller gr-ha df-ha roller-bfs lh-bfs bfs roller-bfs-ha lh-bfs-ha bfs-ha
Blocksworld (30) 30 1 0 8 0 0 8 0 0Depots (22) 21 18 18 20 19 13 20 20 20
Gold-miner (30) 30 0 0 17 17 16 30 0 0Matching-BW (30) 21 0 0 14 7 14 19 10 17
Parking (30) 30 25 1 30 11 7 30 11 9Rovers (30) 28 30 30 26 28 11 30 30 30
Satellite (30) 30 23 22 25 22 15 30 23 23Storage (30) 15 9 10 19 18 20 19 10 10
Thoughtful(30) 12 15 0 20 14 11 23 16 12TPP (30) 30 30 30 16 24 9 19 26 14
Total 247 151 111 195 160 116 228 146 135
![Page 269: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/269.jpg)
Razonamiento basado en casos
[De la Rosa et al., 2007]
SAYPHI-CBR
Planificador
Algoritmo debúsqueda
Heurística
Razonamiento basadoen casos
Reutilización
Base decasos
![Page 270: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/270.jpg)
Razonamiento basado en casos
(at crate0 depot0) (on crate0 pallet0) (clear crate0)
LIFT HOIST0 CRATE0 PALLET0 DEPOT0
(lifting crate0 hoist0)
at1on1 clear1
lifting1
1: LIFT (HOIST0 CRATE1 CRATE0 DEPOT0)2: LOAD (HOIST0 CRATE1 TRUCK0 DEPOT0)3: LIFT (HOIST0 CRATE0 PALLET0 DEPOT0)4: LOAD (HOIST0 CRATE0 TRUCK0 DEPOT0)5: DRIVE (TRUCK0 DEPOT0 DIST0)6: UNLOAD (HOIST1 CRATE0 TRUCK0 DIST0)7: DROP (HOIST1 CRATE0 PALLET1 DIST0)
[(at1 on1 on2),][(at1 on1 clear1) , LIFT][(at1 on1 clear1), (NO-OP 1)][(lifting1) , LIFT][(in1), LOAD][(in1), (NO-OP 1)][(lifting1), UNLOAD][(at1 on1 clear1), DROP]
Secuencia de tiposPlan
Planificador
Dominio Problema
Casos
![Page 271: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/271.jpg)
Construccion de los casos
estado inicial
meta
Sub-estado de Objeto(at object0 depot0) (at hoist0 depot0)(on object0 pallet0) (at hoist1 depot1)(clear object0) (at pallet0 depot0)(at pallet1 depot1) (clear pallet1)(available hoist0) (available hoist1)
Propiedades del Objeto(at1) propiedad de object0 en (at object0 depot0)(at2) propiedad de depot0 en (at object0 depot0)
Sub-estado de tipoobjecto0: (at1 on1 clear1)
hoist0: (at1 available1)
![Page 272: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/272.jpg)
Casos: Secuencias de tipo
object0 sub-estado
(at obectj0 depot0) (on object0 pallet0) (clear object0)
LIFT OBJECT0 HOIST0 PALLET0 DEPOT0
(lifting object0 hoist0)
at1on1 clear1
lifting1
Transición de sub-estados de tipo
Secuencias de Tipo
1: LIFT (HOIST0 CRATE1 CRATE0 DEPOT0)2: LOAD (HOIST0 CRATE1 TRUCK0 DEPOT0)3: LIFT (HOIST0 CRATE0 PALLET0 DEPOT0)4: LOAD (HOIST0 CRATE0 TRUCK0 DEPOT0)5: DRIVE (TRUCK0 DEPOT0 DIST0)6: UNLOAD (HOIST1 CRATE0 TRUCK0 DIST0)7: DROP (HOIST1 CRATE0 PALLET1 DIST0)
[(at1 on1 on2),][(at1 on1 clear1) , LIFT][(at1 on1 clear1), (NO-OP 1)][(lifting1) , LIFT][(in1), LOAD][(in1), (NO-OP 1)][(lifting1), UNLOAD][(at1 on1 clear1), DROP]
Plan
![Page 273: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/273.jpg)
Reutilizacion
[(at1 on1 on2),][(at1 on1 clear1) , LIFT][(at1 on1 clear1), (NO-OP 1)][(lifting1) , LIFT][(in1), LOAD][(in1), (NO-OP 1)][(lifting1), UNLOAD][(at1 on1 clear1), DROP]
Casos
Contenedores
[(at1)][(at1), NO-OP 4][(at1), (DRIVE)][(at1), NO-OP 2]
Camiones
Grúas Pallets
Árbol de búsqueda
![Page 274: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/274.jpg)
Resultados en el dominio de Satelite
![Page 275: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/275.jpg)
Y algo mas...
• Aprendizaje de reglas de control [Borrajo and Veloso, 1997]
• Programacion genetica [Aler et al., 2002]
• Transferencia de aprendizaje [Fernandez et al., 2007]
• Aprendizaje de modelos reactivos [Ledezma et al., 2005,Garcıa-Martınez and Borrajo, 2000]
• Aprendizaje por refuerzo [Fernandez and Borrajo, 2008]
• Aprendizaje activo [Fuentetaja and Borrajo, 2006]
• Mezcla de tecnicas [Garcıa et al., 2006]
![Page 276: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/276.jpg)
Aplicacion de aprendizaje a planificacion
Planner
Model learning
PDDLdomain
Engineer
Heuristics learning
![Page 277: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/277.jpg)
¿Que podemos hacer?
Aprendizaje de modelos de acciones• ¿Como?
• Observando otro agente realizar las tareas• Ejecutando acciones y analizando los resultados• Ayudando al sistema cuando se equivoca• Interactuando con el experto
• ¿Que?• Modelos deliberativos: PDDL, PPDDL• Modelos reactivos: habilidades, MDPs• Precondiciones y efectos• Conocimiento probabilıstico• Informacion sobre la calidad
![Page 278: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/278.jpg)
Acciones probabilısticas en los Rovers
(:action navigate:parameters (?x - rover ?y - waypoint ?z - waypoint):precondition (and (can_traverse ?x ?y ?z)
(available ?x)(at ?x ?y)(visible ?y ?z)(>= (energy ?x) 8))
:effect (and (decrease (energy ?x) 8)(when (rocky-terrain ?y ?z)
(probabilistic 0.8(not (at ?x ?y))(at ?x ?z)))
(when (sandy-terrain ?y ?z)(probabilistic 0.6
(not (at ?x ?y))(at ?x ?z)))))
![Page 279: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/279.jpg)
Aprendizaje de modelos. PELA
[Jimenez et al., In Press], [Jimenez et al., 2008], [Lanchas et al., 2007]
Planificación
Ejecución
Aprendizaje
Ingenierio
Plan
Observaciones
Modelos deacción
Dominiodeterminista
MundorealAcción
Nuevoestado
![Page 280: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/280.jpg)
Dominio Tireworld
![Page 281: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/281.jpg)
Dominio Tireworld
Plan:mover(n1,n5)mover(n5,n6)
![Page 282: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/282.jpg)
Dominio Tireworld
![Page 283: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/283.jpg)
Dominio Tireworld
Plan:mover(n1,n5)mover(n5,n6)
Ejecucion: mover(n1,n5)Nuevo plan: ningunoDead-endEstado: coche-en(n5),pinchado
![Page 284: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/284.jpg)
Dominio Tireworld
![Page 285: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/285.jpg)
Dominio Tireworld
Plan: mover(n1,n2), mover(n2,n3),mover(n3,n4), mover(n4,n6)
Ejecucion: mover(n1,n2)Nuevo plan: arreglar(n2), mover(n2,n3),
mover(n3,n4), mover(n4,n6)FalloEstado: coche-en(n2), pinchado,
llanta-en(n2)
![Page 286: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/286.jpg)
Dominio Tireworld
![Page 287: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/287.jpg)
Dominio Tireworld
Plan: mover(n1,n2), mover(n2,n3),mover(n3,n4), mover(n4,n6)
Ejecucion: mover(n1,n2)ExitoEstado: coche-en(n2)
![Page 288: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/288.jpg)
Ejemplos de entrenamiento
% Example1move(e0,n1,n5,dead-end).tire-at(e0,n2). tire-at(e0,n3). tire-at(e0,n4). flat-tire(e0,n5).at(e0,n5). road(e0,n1,n2). road(e0,n2,n3).road(e0,n3,n4). road(e0,n4,n6). road(e0,n1,n5).road(e0,n5,n6).
% Example2move(e0,n1,n2,failure).tire-at(e0,n2). tire-at(e0,n3). tire-at(e0,n4). flat-tire(e0,n2).at(e0,n2). road(e0,n1,n2). road(e0,n2,n3).road(e0,n3,n4). road(e0,n4,n6). road(e0,n1,n5).road(e0,n5,n6).
% Example3move(e0,n1,n2,success).tire-at(e0,n2). tire-at(e0,n3). tire-at(e0,n4).at(e0,n2). road(e0,n1,n2). road(e0,n2,n3).road(e0,n3,n4). road(e0,n4,n6). road(e0,n1,n5).road(e0,n5,n6).
![Page 289: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/289.jpg)
Arbol de decision relacional
![Page 290: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/290.jpg)
Arbol de decision relacional
![Page 291: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/291.jpg)
Compilacion en costes
(:action mover:parameters (?v1 - lugar ?v2 - lugar):precondition (and (coche-en ?v1)
(camino ?v1 ?v2)(not (pinchado))
:effect (and (when (and (llanta ?v2))(and (coche-en ?v2)
(not (coche-en ?v1))(increase (fragility) 0.22)))
(when (and (not (llanta ?v2)))(and (coche-en ?v2)
(not (coche-en ?v1))(increase (fragility) 999999999)))))
![Page 292: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/292.jpg)
Compilacion en PPDDL
(:action mover:parameters (?v1 - lugar ?v2 - lugar):precondition (and (coche-en ?v1)
(camino ?v1 ?v2)(not (pinchado))
:effect (and (when (and (llanta ?v2))(probabilistic 0.8
(and (coche-en ?v2)(not (coche-en ?v1)))))
(when (and (not (llanta ?v2)))(probabilistic 0.001
(and (coche-en ?v2)(not (coche-en ?v1)))))))
![Page 293: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/293.jpg)
Modelado de costes
(:action sample-rock:parameters (?x -rover ?s -store ?p -waypoint):precondition (and (at ?x ?p)
(at ?r ?p)(>= (energy ?x) 5)(empty ?x ?s))
:effect (and (increase (total-time) ?)(decrease (energy ?x) ?)(not (empty ?s))(full ?s)(have-rock-analysis ?x ?p)(not (at-rock-sample ?p))))
![Page 294: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/294.jpg)
Aprendizaje de duraciones
(:action sample-rock:parameters (?x -rover ?s -store ?p -waypoint ?r - rock):precondition (and (at ?x ?p)
(at ?r ?p)(>= (energy ?x) 5)(empty ?x ?s))
:effect (and (not (empty ?s))(full ?s)(have-rock-analysis ?x ?p)(not (at-rock-sample ?p))(when (and (is-heavy ?r))
(probabilistic0.75 (increase (spent-time) 30)0.25 (increase (spent-time) 20)))
(when (and (not (is-heavy ?r)))(probabilistic
0.6 (increase (spent-time) 2)0.4 (increase (spent-time) 1)))...
![Page 295: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/295.jpg)
Resultados
![Page 296: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/296.jpg)
Trabajo actual. Robots
[Quintero et al., 2011b]
![Page 297: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/297.jpg)
Indice
1 Introduccion
2 Planificacion clasica
3 Planificacion neoclasica
4 Heurıstica
5 Otras cuestionesPlanificacion con tiempo y recursosIncertidumbreOversubscriptionReplanificacionRobotica
![Page 298: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/298.jpg)
Indice
1 Introduccion
2 Planificacion clasica
3 Planificacion neoclasica
4 Heurıstica
5 Otras cuestionesPlanificacion con tiempo y recursosIncertidumbreOversubscriptionReplanificacionRobotica
![Page 299: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/299.jpg)
Planificacion temporal
• Las acciones tienen duracion• Las precondiciones y efectos pueden (des)aparecer:
• al principio de la ejecucion• durante toda la ejecucion• al final de la ejecucion
• Los literales pueden ser ciertos/falsos a partir de undeterminado momento
• Se puede compilar a planificacion con funciones en muchoscasos
• Complejidad: EXPSPACE-complete [Rintanen, 2007]
• Planificadores: LPG-td, OPTIC, CPT4, . . .
![Page 300: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/300.jpg)
Accion durativa y literales temporales
(:durative-action load-truck:parameters (?t - truck ?l - location ?o - cargo ?c - crane):duration (= ?duration 5):condition (and (at start (at ?t ?l))
(at start (at ?o ?l))(at start (empty ?c))(over all (at ?t ?l))(at end (holding ?c ?o)))
:effect (and (at end (in ?o ?t))(at start (holding ?c ?o))(at start (not (at ?o ?l)))(at end (not (holding ?c ?o)))))
(:init (at 10 (see sensor1 object1))(at 20 (not (see sensor1 object1)))...)
![Page 301: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/301.jpg)
Planificacion con tiempo y recursos (scheduling)
• Las acciones llevan su tiempo y utilizan recursos• Se parte de un conjunto de actividades ordenadas (salida
de un planificador o manual), y un conjunto de recursos consus capacidades
• Se desea obtener una asignacion temporal a cada actividadsin violar las restricciones temporales (entre actividades) yde recursos
• Aproximacion estandar: busqueda heurıstica• Tecnicas: A∗, escalada, CSP, algoritmos geneticos, . . .• Muchas aplicaciones reales con este tipo de tecnicas:
logıstica, horarios, manufactura, espacio, . . .
![Page 302: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/302.jpg)
Indice
1 Introduccion
2 Planificacion clasica
3 Planificacion neoclasica
4 Heurıstica
5 Otras cuestionesPlanificacion con tiempo y recursosIncertidumbreOversubscriptionReplanificacionRobotica
![Page 303: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/303.jpg)
Incertidumbre
• Fuentes de incertidumbre• Estado inicial• Metas• Acciones
• Formas de tratarla• planificacion probabilıstica• planificacion condicional• planificacion conformante• MDP• model checking
![Page 304: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/304.jpg)
Modelos de incertidumbre
Modelo de accionesObservabilidad Determinista Estocastico
Completa Clasica ProbabilısticaParcial Contingente Contingente Probabilıstica
Ninguna Conformante Conformante Probabilıstica
![Page 305: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/305.jpg)
Indice
1 Introduccion
2 Planificacion clasica
3 Planificacion neoclasica
4 Heurıstica
5 Otras cuestionesPlanificacion con tiempo y recursosIncertidumbreOversubscriptionReplanificacionRobotica
![Page 306: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/306.jpg)
Goal and state preferences
• Both goals and constraints must be accomplished for theplan being valid
• But, what if we have goals we would like to be accomplishedbut do not want the plan to be invalid if not?
• PDDL3.0 introduces preferences• Applicable to goals or constraints• Can appear:• Can appear:
• domain: actions preconditions• problem: :goals or :constraints
![Page 307: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/307.jpg)
Preferencias
• Syntax: preference [name] <GD>• Name is optional• Different preferences can share same name• Examples at problem file:
(:constraints(and (preference a0 (always (at rover0 waypoint0)))
(preference e0 (sometime (at rover0 waypoint3)))(preference e1 (sometime (at rover0 waypoint2)))(preference e2 (sometime (calibrated camera0 rover0)))))
(:constraints(and (forall (?g - goods)
(preference p5A(at end (forall (?m - market ?t - truck)
(and (= (ready-to-load ?g ?m) 0)(= (loaded ?g ?t) 0))))))))
![Page 308: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/308.jpg)
Preferencias
Examples: precondition
(:durative-action drive:parameters (?t - truck ?from ?to - place):duration (= ?duration (drive-time ?from ?to)):condition (and (preference p-drive
(at start (forall (?g - goods)(< (ready-to-load ?g ?from) 1))))
(at start (at ?t ?from))(over all (connected ?from ?to)))
:effect (and (at start (not (at ?t ?from)))(at end (at ?t ?to))(at end (increase (total-cost) (drive-cost ?from ?to)))))
![Page 309: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/309.jpg)
More examples
• We would like that the energy of every rover should alwaysbe above the threshold of 5 units
(:constraints(and (preference (always (forall (?r - rover)
(> (energy ?r) 5))))))
• Whenever the energy of a rover is below 5, it should be atthe recharging location within 10 time units
(:constraints(and (forall (?r - rover)
(always-within 10 (< (energy ?r) 5)(at ?r recharging-point)))))
![Page 310: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/310.jpg)
Plan quality and preferences
• Preferences can be given a weight to establish which ismore important• Only applicable to named preferences• If no name is given, weight is set to 1• Done in metric part of the problem:
(:metric minimize(+ (* (is-violated sb10) 6.22222)
(* (is-violated sb9) 5.44444)(* (is-violated sb8) 7)))
![Page 311: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/311.jpg)
Strategies for dealing with oversubscription
• Assessing if we are facing an OSP is generally as difficultas trying to solve it
• Expressing the OSP as a Markov decision problem (MDP)yields always to an optimal solution
• . . . but, except for very simple ones, these problems areintractable
• Two different strategies for solving OSP• Searching in goals space: goal preselection
Planner only plans for a predefined subset of goals• Combined search in goals and plans spaces: on-the-fly goal
selectionPlanner plans taking into account all goals
• Another alternative: compiling soft goals away
![Page 312: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/312.jpg)
Indice
1 Introduccion
2 Planificacion clasica
3 Planificacion neoclasica
4 Heurıstica
5 Otras cuestionesPlanificacion con tiempo y recursosIncertidumbreOversubscriptionReplanificacionRobotica
![Page 313: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/313.jpg)
Planning paradigms
Planningfrom
scratch-P-D
?
DomainIndependent
Heuristics
![Page 314: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/314.jpg)
Planning paradigms
Planningfrom
scratch-P-D
?
DomainIndependent
Heuristics
Planningwith
learning-P-D
?
DomainIndependent
Heuristics
6LearnedHeuristics
Experience
![Page 315: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/315.jpg)
Planning paradigms
Planningfrom
scratch-P-D
?
DomainIndependent
Heuristics
Planningwith
learning-P-D
?
DomainIndependent
Heuristics
6LearnedHeuristics
Experience
Planningwith
reuse-P-D
?
DomainIndependent
Heuristics
6PastPlan(s)
Experience
![Page 316: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/316.jpg)
Motivation
• State of the art:• planners: eager commitment to a (set of) heuristic(s)• replanners+learning systems eager commitment to a plan
(learned knowledge)
• Alternative: stochastic use of knowledge
![Page 317: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/317.jpg)
Motivation
• State of the art:• planners: eager commitment to a (set of) heuristic(s)• replanners+learning systems eager commitment to a plan
(learned knowledge)
• Alternative: stochastic use of knowledge
![Page 318: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/318.jpg)
New grid domain
![Page 319: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/319.jpg)
Dead-end
![Page 320: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/320.jpg)
Solution
![Page 321: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/321.jpg)
New problem
![Page 322: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/322.jpg)
“Balancing” heuristics and previous plan
![Page 323: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/323.jpg)
Plan not necessarily always right
![Page 324: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/324.jpg)
RRT [LaValle and Kuffner, 2001]
p: probability of choosing G1-p: probability of choosing some other random goal
![Page 325: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/325.jpg)
RRT
![Page 326: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/326.jpg)
RRT
![Page 327: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/327.jpg)
RRT
![Page 328: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/328.jpg)
New problem
![Page 329: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/329.jpg)
ERRT [Bruce and Veloso, 2002]
![Page 330: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/330.jpg)
ERRT
p: probability of choosing Gr : probability of choosing a previous node as goal1-p-r : probability of choosing some other random goal
![Page 331: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/331.jpg)
ERRT
![Page 332: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/332.jpg)
ERRT
![Page 333: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/333.jpg)
ERRT-PLAN(I,G,A,p, ra,W ): plan
I: initial state, G: goals, A: actionsp: probability of selecting EHC
ra: probability of action-reuserg = 1− (p + ra): probability of goal-reuseW = [(a0,wp0), (a1,wp1), . . . , (ak ,wpk )]: plan
tree = {I}while not(solution(tree,G)) do
i: UniformRandom in [0.0 .. 1.0]if 0 < i < pthen tree = expand-tree(EHC ,I,G,A, φ,tree)else if p < i < p + ra
then tree = expand-tree(action-reuse,I,G,A,W ,tree)else tree = expand-tree(goal-reuse,I,G,A,W ,tree)
return extract-plan(tree)
![Page 334: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/334.jpg)
Expand-tree
EHC
• ChooseTarget: select G• Nearest: closest open node• Extend: EHC expansion
Action reuse• ChooseTarget: select G• Nearest: open node with greatest action pointer• Extend: apply as many actions as possible. Otherwise, EHC
Goal reuse• ChooseTarget: randomly select a past wpi
• Nearest: closest open node• Extend: expand it with EHC
![Page 335: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/335.jpg)
Expand-tree
EHC
• ChooseTarget: select G• Nearest: closest open node• Extend: EHC expansion
Action reuse• ChooseTarget: select G• Nearest: open node with greatest action pointer• Extend: apply as many actions as possible. Otherwise, EHC
Goal reuse• ChooseTarget: randomly select a past wpi
• Nearest: closest open node• Extend: expand it with EHC
![Page 336: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/336.jpg)
Expand-tree
EHC
• ChooseTarget: select G• Nearest: closest open node• Extend: EHC expansion
Action reuse• ChooseTarget: select G• Nearest: open node with greatest action pointer• Extend: apply as many actions as possible. Otherwise, EHC
Goal reuse• ChooseTarget: randomly select a past wpi
• Nearest: closest open node• Extend: expand it with EHC
![Page 337: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/337.jpg)
Discussion
• Deterministic commitment to reuse• e.g., Prodigy/Analogy• adapts past greedily - no optimality guarantees
• Heuristic-based choice to reuse• e.g., LPG-Adapt• uses and adapts past, if heuristic decides so
• Probabilistic reuse• e.g., ERRT-Plan• balance between reuse or not - probabilistic optimal
![Page 338: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/338.jpg)
Blocksworld. Time to solve (600s time-bound)
#blocks FF ERRT-PLAN
p = 0,3ra = 0,3
6 0.32 0.027 8.58 0.128 505.36 0.379 - 0.68
10 - 3.5511 - 24.5612 - 424.06(*)
![Page 339: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/339.jpg)
Experiments. Rovers
![Page 340: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/340.jpg)
Indice
1 Introduccion
2 Planificacion clasica
3 Planificacion neoclasica
4 Heurıstica
5 Otras cuestionesPlanificacion con tiempo y recursosIncertidumbreOversubscriptionReplanificacionRobotica
![Page 341: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/341.jpg)
T-Rex. Arquitectura
• Constraint-based temporal planner• Hierarchy of reactors• Each reactor takes as input a set of goals and a state and
returns a timeline• Reactors are usually state machines• States have: name, parameters, duration, start, end• Time information in the form of intervals• Goals:At (work) [8:30-9:30] [8-9] [16:30-18:30]
• Execution is synchronous
![Page 342: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/342.jpg)
T-Rex. Definitions
• Timeline: temporal representation of the evolution of a statemachine
• Token: each of the states in a timeline• Token (states) are represented using predicates• Constraints: (temporal) relations among tokens• Flaws: constraints not met (yet) by the plan• Planning process: find a sequence of tokens going from the
initial state to the goals
![Page 343: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/343.jpg)
Arquitectura de PELEA
![Page 344: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/344.jpg)
Items de conocimiento
• domainH• domainL• problemH: stateH, goals, metric• problemL: stateL, planH• infoMonitoring
![Page 345: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/345.jpg)
XML
<?xml version=”1.0” encoding=”UTF-8”?> <define xmlns=”http://www.example.org/xPddl”...> <domain name=” driverlog-temporal “> <requirements> <require-key name=”:typing :durative-actions”/> </requirements> <types> <term name=”location” type=“object”/> <term name=”truck” type=“locatable”/> <term name=”obj” type=“locatable”/> ... </types> <predicates> <atom predicate=”at”> <term type=”locatable” name=”?obj”/> <term type=”location” name=”?loc”/> </atom> ... </predicates> ... </domain> </define>
![Page 346: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/346.jpg)
Arquitectura. Ejecucion
![Page 347: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/347.jpg)
Interfaces implementados
• Simuladores:• MDPSim [Younes and Littman, 2004]• Simulador probabilıstico temporal• Virtual Robot Simulator
• Plataformas roboticas• ROS• Stage/Player• Microsoft Robotics Studio
• Robots (a traves de las plataformas):• Pioneer• NAO• iRobot Create
• Juegos:• AI-LIVE [Fernandez et al., 2008]• ORTS [Alcazar et al., 2008]• Starcraft
![Page 348: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/348.jpg)
Arquitectura. Monitorizacion, LowToHigh
![Page 349: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/349.jpg)
Arquitectura. Metas & Metricas
![Page 350: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/350.jpg)
Metas & Metricas
• Permite a PELEA cambiar metas y metricas dinamicamente:• Oversubscription [Garcıa-Olaya et al., 2011,
Fernandez and Borrajo, 2012]• Tareas complejas a traves de automatas• Multi-agente
![Page 351: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/351.jpg)
Automata
![Page 352: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/352.jpg)
Arquitectura. Soporte a las decisiones
![Page 353: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/353.jpg)
Arquitectura. (Re)planificacion
![Page 354: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/354.jpg)
Planificadores y replanificadores
• Temporal: LPG-TD [Gerevini et al., 2003], SGPLAN [Hsu etal., 2007], CRIKEY [Coles et al., 2009] and TFD [Eyerich etal., 2009]
• Strips: CBP [Fuentetaja et al., 2010], Sayphi [De la Rosa etal., 2007]
• HTN: Siadex [Fdez-Olivares et al., 2006]
• Replanificadores: LPG-Adapt [Fox et al., 2006],ERRTPlan [Borrajo and Veloso, 2012]
![Page 355: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/355.jpg)
Arquitectura. Planificacion bajo nivel
![Page 356: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/356.jpg)
Planificacion bajo nivel
• Tareas difıciles de resolver con planificacion deliberativa:path planning, razonamiento numerico, . . .
• Hemos utilizado• Traduccion directa• Decomposicion jerarquica a tareas de bajo nivel• Reinforcement learning• Instance-based policies
![Page 357: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/357.jpg)
Arquitectura. Aprendizaje automatico
![Page 358: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/358.jpg)
Aprendizaje automatico
• Modelo de dominio (domainH): [Jimenez et al.,2008], [Quintero et al., 2011a]
• Modelo de dominio (domainL):• reinforcement learning [Kaebling et al., 1996]• instance-based policies [Garcıa-Duran et al., 2012]
• Heurısticas: [De la Rosa et al., 2011], [de la Rosa et al.,2009]
![Page 359: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/359.jpg)
Independencia de dominio y entorno
![Page 360: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/360.jpg)
Independencia de dominio y dependencia de entorno
![Page 361: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/361.jpg)
Demo
![Page 362: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/362.jpg)
Trabajo relacionado
• Arquitecturas previas: APSI [Cesta et al., 2009],PRS [Georgeff and Lansky, 1987], IxTeT [Ghallab andLaruelle, 1994], IDEA [Aschwanden et al., 2006],TCA [Simmons, 1992], T-Rex [McGann et al., 2007]
• Mas componentes integrados: Goals & Metrics, Learning• Enfasis en estandares: PDDL• Multi-paradigma: Strips, temporal, HTN• Clara separacion de tareas• Comunicacion estandarizada: XML• Muchos interfaces• Pre-soporte para multi-agentes
![Page 363: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/363.jpg)
Nuestro trabajo
• iRoomba: videos• Pioneer: videos• Nao: videos
![Page 364: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/364.jpg)
Referencias
Vidal Alcazar, Daniel Borrajo, and Carlos Linares Lopez.Modelling a RTS planning domain with cost conversion and rewards.In Artificial Intelligence in Games. Workshop of the 18th European Conference onArtificial Intelligence, pages 50–54, Patras (Greece), July 2008.
Vidal Alcazar, Manuela Veloso, and Daniel Borrajo.Adapting an RRT for automated planning.In Daniel Borrajo, Carlos Linares Lopez, and Max Likhachev, editors,Proceedings of the Fourth International Symposium on Combinatorial Search(SoCS-2011), pages 2–9, Cardona (Spain), 2011. AAAI Press.
Ricardo Aler, Daniel Borrajo, and Pedro Isasi.Using genetic programming to learn and improve control knowledge.Artificial Intelligence Journal, 141(1-2):29–56, October 2002.
James F. Allen, James Hendler, and Austin Tate (eds.).Readings in Planning.Morgan Kaufmann, 1990.
John R. Anderson.The Architecture of Cognition.Harvard University Press, Cambridge, Mass, 1983.
P. Aschwanden, V. Baskaran, S. Bernardini, M. Moreno C. Fry, N. Muscettola,C. Plaunt, D. Rijsman, and P. Tompkins.Model-unified planning and execution for distributed autonomous system control.In Workshop on Spacecraft Autonomy: Using AI to Expand Human SpaceExploration. AAAI Press, 2006.
![Page 365: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/365.jpg)
Fahiem Bacchus and Froduald Kabanza.Using temporal logics to express search control knowledge for planning.Artificial Intelligence, 116:123–191, 2000.
Avrim L. Blum and Merrick L. Furst.Fast planning through planning graph analysis.In Chris S. Mellish, editor, Proceedings of the 14th International Joint Conferenceon Artificial Intelligence, IJCAI-95, volume 2, pages 1636–1642, Montreal,Canada, August 1995. Morgan Kaufmann.
Blai Bonet and Hector Geffner.Planning as heuristic search.Artificial Intelligence, 129(1-2):5–33, 2001.
Daniel Borrajo and Manuela Veloso.Lazy incremental learning of control knowledge for efficiently obtaining qualityplans.AI Review Journal. Special Issue on Lazy Learning, 11(1-5):371–405, February1997.Also in the book ”Lazy Learning”, David Aha (ed.), Kluwer Academic Publishers,May 1997, ISBN 0-7923-4584-3.
Daniel Borrajo and Manuela Veloso.Probabilistically reusing plans in deterministic planning.In Proceedings of ICAPS’12 workshop on Heuristics and Search forDomain-Independent Planning, pages 17–25, Atibaia (Brazil), 2012.
Daniel Borrajo, Natalia Juristo, Vicente Martınez, and Juan Pazos.Inteligencia Artificial. Metodos y Tecnicas.Centro de Estudios Ramon Areces, Madrid, 1993.
![Page 366: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/366.jpg)
Adi Botea, Martin Mueller, and Jonathan Schaeffer.Learning partial-order macros from solutions.In Proceedings of ICAPS’05, Monterrey (USA), June 2005.
James Bruce and Manuela Veloso.Real-time randomized path planning for robot navigation.In Proceedings of IROS-2002, Switzerland, October 2002.
Daniel Burfoot, Joelle Pineau, and Gregory Dudek.RRT-Plan: A Randomized Algorithm for STRIPS Planning.In Proceedings of ICAPS’06, pages 362–365, Ambleside (UK), June 2006. AAAIPress.
A. Cesta, G. Cortellessa, S. Fratini, and A. Oddi.Developing an End-to-End Planning Application from a Timeline RepresentationFramework.In IAAI-09. Proceedings of the 21st Innovative Applications of ArtificialIntelligence Conference, Pasadena, CA, USA, 2009.
Pat W. Cheng and Jaime G. Carbonell.The FERMI system: Inducing iterative rules from experience.In Proceedings of AAAI-86, pages 490–495, Philadelphia, PA, 1986.
Andrew Coles, Maria Fox, Keith Halsey, Derek Long, and Amanda Smith.Managing concurrency in temporal planning using planner-scheduler interaction.Artificial Intelligence Journal, 173(1):1–44, 2009.
Ken Currie and Austin Tate.O-Plan: the open planning architecture.Artificial Intelligence, 52(1):49–86, 1991.
![Page 367: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/367.jpg)
Tomas De la Rosa, Angel Garcıa-Olaya, and Daniel Borrajo.Using cases utility for heuristic planning improvement.In Rosina Weber and Michael Richter, editors, Case-Based Reasoning Researchand Development: Proceedings of the 7th International Conference onCase-Based Reasoning, volume 4626 of Lecture Notes on Artificial Intelligence,pages 137–148, Belfast, Northern Ireland, UK, August 2007. Springer Verlag.
Tomas de la Rosa, Rocıo Garcıa-Duran, Sergio Jimenez, Fernando Fernandez,Angel Garcıa-Olaya, and Daniel Borrajo.Three relational learning approaches for lookahead heuristic search.In Proceedings of the Workshop on Planning and Learning of ICAPS09,Thessaloniki (Greece), September 2009.
Tomas De la Rosa, Sergio Jimenez, Raquel Fuentetaja, and Daniel Borrajo.Scaling up heuristic planning with relational decision trees.Journal of Artificial Intelligence Research, 40:767–813, 2011.http://dx.doi.org/10.1613/jair.3231.
P. Eyerich, R. Mattmuller, and G. Roger.Using the context-enhanced additive heuristic for temporal and numeric planning.In Proceedings of the 19th International Conference on Automated Planning andScheduling (ICAPS), 2009.
J. Fdez-Olivares, L. Castillo, O. Garcıa-Perez, and F. Palao.Bringing users and planning technology together. experiences in SIADEX.In Proc. ICAPS 2006, 2006.Awarded as the Best Application Paper of this edition.
Fernando Fernandez and Daniel Borrajo.Two steps reinforcement learning.
![Page 368: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/368.jpg)
International Journal of Intelligent Systems, 23(2):213–245, February 2008.
Susana Fernandez and Daniel Borrajo.Using linear programming to solve clustered oversubscription planning problemsfor designing e-courses.Expert Systems with Applications, 39:5178–5188, 2012.doi:10.1016/j.eswa.2011.11.021.
Susana Fernandez, Ricardo Aler, and Daniel Borrajo.Transferring learned control-knowledge between planners.In Manuela Veloso, editor, Proceedings of IJCAI’07, Hyderabad (India), 2007.IJCAI Press.Poster.
Susana Fernandez, Javier Asensio, Marta Jimenez, and Daniel Borrajo.A social and emotional model for obtaining believable emergent behavior.In Paolo Traverso and Marco Pistore, editors, Artificial Intelligence: Methodology,Systems, and Applications, volume 5253/2008 of Lecture Notes in ComputerScience, pages 395–399, Varna, Bulgaria, September 2008. Springer Verlag.
Richard E. Fikes and Nils J. Nilsson.Strips: A new approach to the application of theorem proving to problem solving.Artificial Intelligence, 2:189–208, 1971.
Richard E. Fikes, P. E. Hart, and Nils J. Nilsson.Learning and executing generalized robot plans.Artificial Intelligence, 3:251–288, 1972.
Maria Fox, Alfonso Gerevini, Derek Long, and Ivan Serina.Plan stability: Replanning versus plan repair.In Proceedings of ICAPS’06, pages 212–221, 2006.
![Page 369: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/369.jpg)
Raquel Fuentetaja and Daniel Borrajo.Improving control-knowledge acquisition for planning by active learning.In Johannes Fuernkranz Tobias Scheffer and Myra Spiliopoulou, editors,Proceedings of 17th European Conference on Machine Learning (ECML’06),volume 4212 of Lecture Notes in Computer Science, pages 138–149, Berlin(Germany), 2006. Springer Verlag.
Raquel Fuentetaja, Daniel Borrajo, and Carlos Linares Lopez.A look-ahead B&B search for cost-based planning.In Pedro Meseguer, Lawrence Mandow, and Rafael Martınez-Gasca, editors,Current Topics in Artficial Intelligence, CAEPIA 2009 Selected Papers, volumeLNAI 5988 of Lecture Notes on Artificial Intelligence, pages 201–211, Sevilla(Spain), 2010. Springer Verlag.
Rocıo Garcıa, Fernando Fernandez, and Daniel Borrajo.Combining macro-operators with control knowledge.In Ramon Otero, editor, Proceedings of International Conference on InductiveLogic Programming (ILP’06), volume 4455 of Lecture Notes on ArtificialIntelligence, pages 229–243, Santiago de Compostela (Spain), 2006. SpringerVerlag.
Rocıo Garcıa-Duran, Fernando Fernandez, and Daniel Borrajo.A prototype-based method for classification with time constraints: A case studyon automated planning.Pattern Analysis and Applications Journal, 15(3):261–277, 2012.
Ramon Garcıa-Martınez and Daniel Borrajo.An integrated approach of learning, planning, and execution.Journal of Intelligent and Robotic Systems, 29(1):47–78, September 2000.
![Page 370: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/370.jpg)
Angel Garcıa-Olaya, Tomas de la Rosa, and Daniel Borrajo.Using relaxed plan heuristic to select goals in oversubscription planning problems.
In Jose A. Lozano, Jose A. Gamez, and Jose A. Moreno, editors, Advances inArtificial Intelligence, volume 7023/2011 of Lecture Notes on Computer Science,pages 183–192, La Laguna (Spain), November 2011. Springer Verlag.Best paper award. ISBN 978-3-642-25273-0.
Michael P. Georgeff and Amy L. Lansky.Reactive reasoning and planning.In Proceedings of AAAI-87 Sixth National Conference on Artificial Intelligence,pages 677–682, Seattle, WA (USA), July 1987.
Alfonso Gerevini, Alessandro Saetti, and Ivan Serina.Planning through stochastic local search and temporal action graphs.Journal of Artificial Intelligence Research, 20:239–290, 2003.
M. Ghallab and H. Laruelle.Representation and control in IxTeT, a temporal planner.In Proceedings of the 2nd International Conference on AI Planning Systems,1994.
Malik Ghallab, Dana Nau, and Paolo Traverso.Automated Planning. Theory & Practice.Morgan Kaufmann, 2004.
Malte Helmert.The Fast Downward planning system.JAIR, 26:191–246, 2006.
![Page 371: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/371.jpg)
Jorg Hoffmann and Bernhard Nebel.The FF planning system: Fast plan generation through heuristic search.Journal of Artificial Intelligence Research, 14:253–302, 2001.
Chih-Wei Hsu, Benjamin W. Wah, Ruoyun Huang, and Yixin Chen.Constraint partitioning for solving planning problems with trajectory constraintsand goal preferences.In Proceedings of IJCAI’07, Hyderabad, India, 2007.
Sergio Jimenez, Fernando Fernandez, and Daniel Borrajo.The PELA architecture: integrating planning and learning to improve execution.In Proceedings of the AAAI’08, Chicago, IL (USA), July 2008. AAAI, AAAI Press.
Sergio Jimenez, Fernando Fernandez, and Daniel Borrajo.Integrating planning, execution and learning to improve plan execution.Computational Intelligence Journal, In Press.
Leslie Pack Kaebling, Michael L. Littman, and Andrew W. Moore.Reinforcement learning: A survey.International Journal of Artificial Intelligence Research, pages 237–285, 1996.
Subbarao Kambhampati.Improving graphplan’s search with ebl & ddb techniques.In Thomas Dean, editor, Proceedings of the IJCAI’99, pages 982–987,Stockholm, Sweden, July-August 1999. Morgan Kaufmann Publishers.
Subbarao Kambhampati.Planning graph as a (dynamic) CSP: Exploiting EBL, DDB and other CSP searchtechniques in Graphplan.Journal of Artificial Intelligence Research, 12:1–34, 2000.
![Page 372: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/372.jpg)
Henry Kautz and Bart Selman.Planning as satisfiability.In Proceedings of ECAI’92, 1992.
Henry Kautz and Bart Selman.Pushing the envelope: Planning, propositional logic, and stochastic search.In Proceedings of AAAI-96, pages 1194–1201, 1996.
Henry Kautz and Bart Selman.Unifying sat-based and graph-based planning.In Proceedings of IJCAI-99, Stockholm (Sweden), 1999.
Craig A. Knoblock.Automatically generating abstractions for planning.Artificial Intelligence, 68, 1994.
Jana Koehler, Bernhard Nebel, Jorg Hoffmann, and Yannis Dimopoulos.Extending planning graphs to an ADL subset.In S. Steel and R. Alami, editors, Proceedings of the 4th European Conference onPlanning, ECP’97, volume 1348 of Lecture Notes in Computer Science, pages273–285. Springer-Verlag, 1997.
Richard E. Korf.Macro-operators: A weak method for learning.Artificial Intelligence, 26:35–77, 1985.
John E. Laird, Paul S. Rosenbloom, and Allen Newell.Chunking in SOAR: The anatomy of a general learning mechanism.Machine Learning, 1:11–46, 1986.
Jesus Lanchas, Sergio Jimenez, Fernando Fernandez, and Daniel Borrajo.
![Page 373: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/373.jpg)
Learning action durations from executions.In Proceedings of the ICAPS’07 Workshop on Planning and Learning,Providence, Rhode Island (USA), 2007.
S. M. LaValle and J. James J. Kuffner.Randomized kinodynamic planning.In Proceedings of the International Journal of Robotics Research, volume 20,pages 378–400, May 2001.
Agapito Ledezma, Ricardo Aler, Araceli Sanchis, and Daniel Borrajo.Predicting opponent actions by observation.In Daniele Nardi, Martin Riedmiller, and Claude Sammut, editors, RoboCup 2004:Robot Soccer World Cup VIII, volume 3276 of Lecture Notes in ComputerScience, pages 286–296, Lisbon (Portugal), 2005. Springer Verlag.
Derek Long and Maria Fox.Efficient implementation of the plan graph in STAN.Journal of Artificial Intelligence Research, 10:87–115, 1999.
C. McGann, F. Py, K. Rajan, H. Thomas, R. Henthorn, and R. McEwen.T-REX: A Deliberative System for AUV Control.In 3rd Workshop on Planning and Plan Execution for Real-World Systems,ICAPS, Providence, RI, 2007.
Steven Minton.Selectively generalizing plans for problem solving.In Proceedings of AAAI-85, pages 596–599, 1985.
Steven Minton.Learning Effective Search Control Knowledge: An Explanation-Based Approach.
![Page 374: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/374.jpg)
Kluwer Academic Publishers, Boston, MA, 1988.
H. Nakhost and M. Muller.Monte-carlo exploration for deterministic planning.In Proceedings of IJCAI’09, 2009.
Dana Nau, Tsz-Chiu Au, Okhtay Ilghami, Ugur Kuter, J. William Mur, and Dan Wu.
SHOP2: An HTN planning system.Journal of Artificial Intelligence Research, 20:379–404, 2003.
Allen Newell, Herbert A. Simon, and J. Shaw.Human Problem Solving.Prentice-Hall, Englewood Cliffs, NJ, 1972.
Nils Nilsson.Principios de Inteligencia Artificial.Ediciones Dıaz de Santos, Madrid, 1987.
Judea Pearl.Heuristics: Intelligent Search Strategies for Computer Problem Solving.Addison-Wesley, 1983.
J. S. Penberthy and D. S. Weld.UCPOP: A sound, complete, partial order planner for ADL.In Proceedings of KR-92, pages 103–114, 1992.
Ezequiel Quintero, Vidal Alcazar, Daniel Borrajo, Juan Fdez-Olivares, FernandoFernandez, Angel Garcıa-Olaya, Cesar Guzman, Eva Onaindıa, and David Prior.Autonomous mobile robot control and learning with pelea architecture.
![Page 375: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/375.jpg)
In Sanem Sariel-Talay, Stephen Smith, and Nilufer Onder, editors, Working Notesof the AAAI’11 Workshop on Automated Action Planning for Autonomous MobileRobots (PAMR’11), pages 51–56, San Francisco (USA), August 2011. AAAI,AAAI Press.Technical Report WS-11-04.
Ezequiel Quintero, Angel Garcıa-Olaya, Daniel Borrajo, and Fernando Fernandez.
Control of autonomous mobile robots with automated planning.Journal of Physical Agents, 5(1):3–13, 2011.
Elaine Rich and Kevin Knight.Inteligencia Artificial.McGraw-Hill, Inc., 1994.Segunda edicion.
Jussi Rintanen.Complexity of concurrent temporal planning.In Proceedings of ICAPS’07, pages 280–287, 2007.
Stuart Russell and Peter Norvig.Artificial Intelligence: A Modern Approach.Prentice Hall, 1995.
Earl D. Sacerdoti.Planning in a hierarchy of abstraction spaces.Artificial Intelligence, 5:115–135, 1974.
Earl D. Sacerdoti.A Structure for Plans and Behavior.
![Page 376: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/376.jpg)
American Elsevier, New York, 1977.
Peter Shell and Jaime G. Carbonell.Towards a general framework for composing disjunctive and iterativemacro-operators.In Proceedings of the Eleventh International Joint Conference on ArtificialIntelligence, 1989.
Reid Simmons.Concurrent planning and execution for autonomous robots.In IEEE International Conference on Robotics and Automation, pages 46–50,1992.
David E. Smith and Daniel S. Weld.Temporal planning with mutual exclusion reasoning.In Proceedings of IJCA’99, pages 326–337, 1999.
Mark Stefik.Planning and meta-planning (MOLGEN: Part 2).Artificial Intelligence, 16:141–169, 1981.
Mark Stefik.Planning with constraints (MOLGEN: Part 1).Artificial Intelligence, 16:111–140, 1981.
Manuela Veloso, Jaime Carbonell, Alicia Perez, Daniel Borrajo, Eugene Fink, andJim Blythe.Integrating planning and learning: The PRODIGY architecture.Journal of Experimental and Theoretical AI, 7:81–120, 1995.
Daniel S. Weld.
![Page 377: PLANIFICACION AUTOM ATICA Daniel Borrajo · ¿Que tienen en com´ un?´ Busqueda en un espacio de problemas´ Estado o situacion ´: descripcion instantanea Accion u Operador ´:](https://reader035.vdocumento.com/reader035/viewer/2022062510/611443404fa7c86a9621e6d7/html5/thumbnails/377.jpg)
An introduction to least commitment planning.AI Magazine, 15(4):27–61, 1994.
Hakan L. S. Younes and Michael L. Littman.PPDDL1.0: An extension to pddl for expressing planning domains withprobabilistic effects.Technical Report CMU-CS-04-167, 2004.