Upload
jacinta-barabas
View
12
Download
1
Embed Size (px)
Citation preview
Mg. Samuel Oporto Díaz Lima, 19 Septiembre 2005
Planeación
INTELIGENCIA ARTIFICIAL
22/29/29
Mapa Conceptual del Curso
Inteligencia Artificial y Sistemas Expertos
Lenguaje Simbólico
LISP
Búsqueda
Búsqueda Ciega
Búsqueda Heurística
Planeación
Lógica y Razonamiento
Lógica Proposicional
Lógica de Predicados
Inferencia y Razonamiento
Inteligencia Artificial
Conceptos Generales
Conocimiento
Agentes
33/29/29
Tabla de Contenido1. Planeación.
2. Representación
3. El Mundo de los Bloques
44/29/29
Objetivos• Exponer los conceptos de planeación.• Planificación en IA• Ejemplo de planeación
55/29/29
PLANEACION
66/29/29
¿Qué es planificación?
• Empresarios: planes de la empresa• Abogados: planes de defensa del cliente• Industriales: planes de movimiento de robots• Arquitectos: planes de diseño de edificios• Informáticos: planes de desarrollo del sistema• Telecomunicaciones: planes de conexión• Ejército: planes de ataque/defensa• Logística de transportes: planes para llevar• objetos/sujetos de un sitio a otro
77/29/29
¿Qué tienen en común?
Búsqueda en un espacio de problemas
1. Estado o situación: descripción instantánea
2. Acción u Operador: transformación de un estado en otro
3. Estado inicial: situación de partida
4. Objetivo o meta: descripción de condiciones que se tienen que dar para considerar por terminado el proceso
5. Plan: secuencia de operaciones que permiten pasar del estado inicial a un estado en el que se cumplan los objetivos
6. Heurísticas: conocimiento que permite obtener eficientemente el plan
88/29/29
Ejemplo en Turismo
• Estado:– situación de una persona, restricciones de precio, tiempo,. .– precios, horarios y disponibilidad de los billetes de avión, tren,
autobús, hoteles, etc. . . de diferentes compañías,
• Operadores:– volar en un determinado vuelo, viajar en un determinado tren, coger
un taxi, ir en coche, alojarse en un hotel, alojarse en una casa rural, solicitar los servicios de una agencias de viajes. . .
• Estado inicial:– estamos en Lima
• Meta:– quiero pasar una semana en el Cuzco
99/29/29
Ejemplo de un Plan
• Tomar_Taxi(Casa,AeropuertoJorgeChavez)• Tomar_Vuelo(JChavez,AArequipa,. . . )• Tomar_Vuelo (Aarequipa, Acuzco,. . . )• Tomar_Taxi (ACuzco,Hotel)• Estar_en_Hotel(Hotel,. . . )• …• …
• Heurísticas: – Para tomar taxi en Lima, pregunte 4 veces y pague en soles.– Para seleccionar hotel en Cuzco, preguente si tiene convenios con
agencias de viajes.
1010/29/29
¿Cómo planificamos?
• En función de los fines (metas) y los medios (operadores)• Descomponiendo problemas en subproblemas• Jerárquicamente• Basado en la experiencia• Reactivamente• Entre varios agentes• Estableciendo prioridades
• ¿de qué otras formas?
1111/29/29
Algunas cuestiones difíciles
• Nuestra visión del mundo es incompleta: racionalidad limitada
• El mundo cambia constantemente: dinamismo
• Las acciones tardan en ejecutarse: razonamiento temporal
• Nuestras metas son contradictorias: dependencia entre metas
• Nuestro modelo del mundo falla muchas veces: incertidumbre
• Los planes no siempre son válidos: ejecución y replanificación
• No todos los planes son buenos: calidad
• Nos adaptamos al mundo: aprendizaje
• Tardamos mucho en aprender: aprendizaje
• La planificación y la filosofía: creencias, intenciones y deseos
1212/29/29
Ejercicio 1• Planifique las acciones necesarias para limpiar tu cuarto.• Asume lo siguiente:
– Si limpias la mesa se ensucias el piso.– Si ordenas el estande de libros ensucias el piso, la mesa y la cama– Si limpias las paredes ensucias la cama, la mesa y la
computadora.– La computadora está encima de la mesa– Si recoges la basura del piso y luego limpias algo, ensucias de
nuevo el piso.
• Identifica:
1. Estado o situación 4. Acción u Operador
2. Estado inicial 5. Objetivo o meta
3. Plan 6. Heurísticas:
1313/29/29
REPRESENTACION
1414/29/29
Representación en planificación• Para que el ordenador pueda resolver problemas, es
necesario decirle qué tiene que resolver en algún lenguaje.
• Existen muchas formas de suministrar esa información.
• Se usa la lógica de predicados (LP1)
1515/29/29
Representación mediante LP1• Se representan los estados y los operadores• LP1 permite representar estados V o F mediante: términos,
predicados, conectivas, y cuantificadores:
x,y alumno(x) Λ asignatura(y) Λ [¬aprobado(x, y) V
primera-vez(x,y)] se-matricula(x, y)
• No hay una representación única y válida; cada persona representa los dominios de forma diferente
1616/29/29
Representación en planificación• Por cada estado se definen predicados:
tiene-dinero(x,y), vuelo-reservado(x,vuelo,día),
datos-vuelo(vuelo,origen,destino,hora-salida,hora-llegada), .
• Cada estado se representa por una conjunción de predicados instanciados:
tiene-dinero(Pepe,100.000), vuelo-reservado(Pepe,IB304,3-Nov-99),
datos-vuelo(IB304, Lima, Arequipa, 12:05,12:30),
datos-vuelo(TWA2001, Arequipa, Cuzco, 13:55,17:20), . . .
1717/29/29
Supuesto del mundo cerrado• Lo que no aparece explícitamente representado en un
estado es falso: suposición del mundo cerrado
dinero(Pepe, y), cuando y = 100.000
• No es necesario decir nada respecto a Julio que no tiene dinero.
¬dinero(Julio, y), cuando y = 0 no es necesario
1818/29/29
Representación de los operadores• Se deben representar los cambios que ocurren en el mundo
mediante operadores: STRIPS
• Se definen por tres listas:• precondiciones: condiciones que se tienen que cumplir en
un estado para poder ejecutar el operador• añadidos: cosas que pasan a ser ciertas por la ejecución
del operador (hay que añadirlas al estado)• borrados: cosas que dejan de ser ciertas por la ejecución
del operador (hay que borrarlas del estado)
1919/29/29
Representación de los operadoresPagar-billete-avión(x,vuelo,día,dinero,coste-billete)
• precondiciones:
vuelo-reservado(x,vuelo,día), tiene-dinero(x,dinero), cuesta(vuelo,día,precio), dinero ≥ precio
• añadidos:
tiene-dinero(x,dinero - precio), tiene-billete(x,vuelo,día)
• borrados:
tiene-dinero(x,dinero)
2020/29/29
EL MUNDO DE LOS BLOQUES
2121/29/29
El mundo de los bloques• Un conjunto de bloques, una mesa, y un brazo de un robot
• Los bloques son iguales de tamaño, forma y color, diferenciándose en el nombre
• La mesa tiene extensión ilimitada
• Cada bloque puede estar encima de la mesa, encima de un sólo bloque, o sujeto por el brazo del robot
• El brazo de robot sólo puede sujetar un bloque cada vez
2222/29/29
El mundo de los bloques
Estado Inicial Estado Final
• Resolver problemas supone pasar de una configuración (estado) inicial a un estado en el que sean ciertas unas metas
A
D C
B
D
B A
C
2323/29/29
Estados• Se podrían utilizar los siguientes predicados:
– encima(x,y) : el bloque x está encima del y– en-mesa(x) : el bloque x está encima de la mesa– libre(x) : el bloque x no tiene ningún bloque encima– sujeto(x) : el brazo del robot tiene cogido al bloque x– brazo-libre : el brazo del robot no tiene cogido a ningún bloque
• Estado inicial: encima(A,B),encima(B,D),en-mesa(D),en-mesa(C), libre(A),libre(C),brazo-libre
• Metas: en-mesa(A), en-mesa(B), encima(C,B) , encima(D,C)
Estado Inicial Estado Final
A
D C
B
D
B A
C
A
D C
B
D
B A
C
2424/29/29
OperadoresQUITAR(x, y)
– precondiciones: encima(x, y),libre(x),brazo-libre– añadidos: sujeto(x),libre(y)– borrados: encima(x, y),brazo-libre,libre(x)
LEVANTAR(x)– precondiciones: en-mesa(x),libre(x),brazo-libre– añadidos: sujeto(x)– borrados: en-mesa(x),brazo-libre,libre(x)
PONER(x, y)– precondiciones: sujeto(x),libre(y)– añadidos: encima(x, y),libre(x),brazo-libre– borrados: sujeto(x),libre(y)
DEJAR(x)– precondiciones: sujeto(x)– añadidos: en-mesa(x),libre(x),brazo-libre– borrados: sujeto(x)
2525/29/29
Lenguaje PDDL - Operadores(define (domain mundobloques) (:requirements :strips :equality) (:predicates (encima ?bl1 ?bl2) (enmesa ?bl) (libre ?bl) (sujeto ?bl) (brazolibre) ) (:action quitar :parameters (?bl1 ?bl2 ) :precondition (and (encima ?bl1 ?bl2) (libre ?bl1) (brazolibre) ) :effect (and (sujeto ?bl1) (libre ?bl2) (not (encima ?bl1 ?bl2)) (not (brazolibre)) (not (libre ?bl1)) ) )
2626/29/29
Lenguaje PDDL - Operadores (:action levantar :parameters (?bl1 ) :precondition (and (enmesa ?bl1) (libre ?bl1) (brazolibre) ) :effect (and (sujeto ?bl1) (not (enmesa ?bl1)) (not (brazolibre)) (not (libre ?bl1)) ) )
2727/29/29
Lenguaje PDDL - Operadores (:action poner :parameters (?bl1 ?bl2 ) :precondition (and (sujeto ?bl1) (libre ?bl2) ) :effect (and (encima ?bl1 ?bl2) (libre ?bl1) (brazolibre) (not (sujeto ?bl1)) (not (libre ?bl2)) ) )
2828/29/29
Lenguaje PDDL - Operadores (:action dejar :parameters (?bl1 ) :precondition (and (sujeto ?bl1) ) :effect (and (enmesa ?bl1) (libre ?bl1) (brazolibre) (not (sujeto ?bl1)) ) ))
2929/29/29
Definición del Problema(define (problem ejemplo) (:domain mundobloques) (:objects a b c d )
(:init (enmesa d) (enmesa c) (libre a) (libre c) (encima a b) (encima b d) (brazolibre) ) (:goal (and (enmesa a) (enmesa b) (encima c b) (encima d c) (libre a) (libre d) ) ))
PREGUNTAS