PDF de programación - Tema 6: Planificación

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Tema 6: Planificación

José Luis Ruiz Reina

Francisco J. Martín Mateos
Miguel A. Gutiérrez Naranjo

Departamento de Ciencias de la Computación e Inteligencia Artificial

Universidad de Sevilla

Inteligencia Artificial

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Índice

Representación de problemas como espacios de estados

Técnicas básicas de búsqueda en espacios de estados

Búsqueda informada mediante técnicas heurísticas

Introducción a la planificación

El formalismo PDDL

Búsqueda hacia adelante

Búsqueda hacia atrás

Heurísticas para planificación

Planificación de orden parcial: POP

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Método de solución de problemas

Problema

ABSTRACCION

Expresion

como espacio
de estados

Solucion

INTERPRETACION

Aplicacion de al−
goritmos de bus−
queda de solucion

Implementacion
en un lenguaje
de programacion

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Definición de un problema como espacio de estados

• Paso previo a la búsqueda de soluciones de un problema:

• Especificación del problema

• Elementos del problema:

• ¿Cuál la situación inicial desde la que se parte?
• ¿Cuál es el objetivo final?
• ¿Cómo describir las diferentes situaciones o estados por

los que podríamos pasar?

• ¿Qué pasos elementales o acciones para cambiar de

estado y cómo actúan?

• Especificar un problema como espacio de estados

consiste en describir de manera clara cada de uno de
estos componentes

• Ventaja: procedimientos generales de búsqueda de

soluciones

• Independientes del problema

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Planteamiento del problema del 8-puzle

• Un tablero cuadrado (3x3) en el que hay situados 8

bloques cuadrados numerados (con lo cual se deja un
hueco del tamaño de un bloque). Un bloque adyacente al
hueco puede deslizarse hacia él. El juego consiste en
transformar una posición inicial en la posición final
mediante el deslizamiento de los bloques. En particular,
consideramos el estado inicial y final siguientes:

8
6

2
1
7

3
4
5

Estado inicial

1
8
7

2

6

3
4
5

Estado final

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Representación de estados

• Estado: descripción de una posible situación en el

problema

• Abstracción de propiedades

• Importancia de una buena representación de los estados

• Sólo considerar información relevante para el problema
• La representación escogida influye en el número de

estados y éste en los procedimientos de búsqueda de
soluciones

• Ejemplo: 8-puzle: Elementos de la representación:
• relevante: localización de cada bloque y del hueco;
• irrelevante: tipo de material de los bloques, colores de los

bloques,. . .

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Acciones

• Acciones:

• Representan un conjunto finito de operadores básicos que

transforman unos estados en otros
• Elementos que describen una acción

• Aplicabilidad: precondición y postcondición
• Estado resultante de la aplicación de una acción (aplicable)

a un estado

• Criterio para elegir acciones.

• Depende de la representación de los estados
• Preferencia por representaciones con menor número de

acciones

• Ejemplo: Acciones del 8-puzle:

• Según los movimientos de los bloques: 32 = (8 bl. × 4

mov.)

• Según los movimientos del hueco: 4.

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Acciones

• Acciones en el 8 puzle

• Mover el hueco hacia arriba
• Mover el hueco hacia abajo
• Mover el hueco hacia la derecha
• Mover el hueco hacia la izquierda

• Descripción de la acción “Mover el hueco hacia arriba”
• Aplicabilidad: es aplicable a estados que no tengan el

hueco en la primera fila

• Resultado de aplicarlo: intercambiar las posiciones del

hueco y del bloque que está encima de éste

6
7
1

8
2
4

3

5

6
7
1

8
2
4

3

5

• Los tres restantes, análogamente

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Estado inicial

• Estado inicial

• Un estado que describe la situación de partida

• Estado inicial en el ejemplo del 8-puzle

8
6

2
1
7

3
4
5

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Estados finales

• Descripción del objetivo

• Usualmente, un conjunto de estados, que llamaremos

finales

• A veces, aunque no necesariamente, un único estado final

• Ejemplo del 8-puzle (un único estado final)

1
8
7

2

6

3
4
5

• Formas de describir los estados finales:

• Enumerativa.
• Declarativa.

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Soluciones de un problema

• Definición de solución de un problema.

• Secuencia de acciones a realizar para conseguir el objetivo
• Secuencia de acciones cuya aplicación desde el estado

inicial obtiene un estado final

• Ejemplo: Una solución del 8-puzle:

2
1
7

8
6


3
4
5

2
1
7

8

6

3
4
5

2
1
7


8
6

3
4
5


1
7

2
8
6

3
4
5

1

7

2
8
6

3
4
5

1
8
7

2

6

3
4
5

(arriba arriba izquierda abajo derecha)

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Soluciones de un problema

• Tipos de problemas:

• Buscar una solución.
• Determinar si existe solución y encontrar un estado final.
• Buscar cualquier solución lo más rápidamente posible.
• Buscar todas las soluciones.
• Buscar la solución más corta.
• Buscar la solución menos costosa.

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Espacio de estados como un grafo

• Un espacio de estados se puede ver como un grafo

dirigido

• Los vértices de dicho grafo son los estados
• Sucesores de un estado: aquellos obtenidos a partir del

estado aplicando una acción aplicable

• Ejemplo en el 8-puzle

2
1
7

2
1
7

8
6

8

6

3
4
5

3
4
5

3
4

2
1
7

8
6
5

2
1

8
6
7

3
4
5

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Planteamiento del problema del granjero

• Enunciado:

• Un granjero está con un lobo, una cabra y una col en una

orilla de un río.

• Desea pasarlos a la otra orilla.
• Dispone de una barca en la que sólo puede llevar una cosa

cada vez.

• El lobo se come a la cabra si no está el granjero.
• La cabra se come la col si no está el granjero.

• Información de los estados: orilla en la que está cada

elemento

• La orilla de la barca es redundante (está en la orilla donde

esté el granjero)

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Formulación del problema del granjero

• Representación de estados: (x y z u) en {i,d}4.

• Número de estados: 16.

• Estado inicial: (i i i i).
• Estado final (único): (d d d d).
• Acciones:

• Pasa el granjero solo.
• Pasa el granjero con el lobo.
• Pasa el granjero con la cabra.
• Pasa el granjero con la col.

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Formulación del problema del granjero

• Aplicabilidad de las acciones

• Precondición (en los tres últimos): los dos elementos que

pasan han de estar en la misma orilla

• Poscondición: en el estado resultante no deben estar el
lobo y la cabra, o la cabra y la col, en la misma orilla sin
que el granjero esté en esa misma orilla

• Estado resultante de aplicar la acción

• Cambiar la orilla de los elementos que pasan por la orilla

opuesta

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Planteamiento del problema de las jarras

• Enunciado:

• Se tienen dos jarras, de 4 y 3 litros respectivamente.
• Ninguna de ellas tiene marcas de medición.
• Se tiene una bomba que permite llenar las jarras de agua.
• Averiguar cómo se puede lograr tener exactamente 2 litros

de agua en la jarra de 4 litros de capacidad.

• Representación de estados: (x y) con x en {0,1,2,3,4} e y

en {0,1,2,3}.

• Número de estados: 20.

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Formulación del problema de las jarras

• Estado inicial: (0 0).
• Estados finales: todos los estados de la forma (2 _).
• Acciones:

• Llenar la jarra de 4 litros con la bomba.
• Llenar la jarra de 3 litros con la bomba.
• Vaciar la jarra de 4 litros en el suelo.
• Vaciar la jarra de 3 litros en el suelo.
• Llenar la jarra de 4 litros con la jarra de 3 litros.
• Llenar la jarra de 3 litros con la jarra de 4 litros.
• Vaciar la jarra de 3 litros en la jarra de 4 litros.
• Vaciar la jarra de 4 litros en la jarra de 3 litros.

Espacios de estados Técnicas básicas de búsqueda en espacios de estados Búsqueda informada mediante técnicas heurísticas Introducción

Planteamiento del problema de las jarras

• Aplicación de acciones a un estado (x y)
• Acción “Llenar jarra de 3”

• Aplicabilidad: y<3 (p