Inteligencia Artificial

Inteligencia Artificial I

Curso 2006–2007

Tema 2: Representaci´n de o problemas como espacios de estados
Jos´ A. Alonso Jim´nez e e Carmen Graciani D´ ıaz Francisco J. Mart´ Mateos ın Jos´ L. Ruiz Reina e
Dpto. de Ciencias de la Computaci´n e Inteligencia Artificial o

Universidad de Sevilla

IA-I 2006–2007

CcIa

Representaci´n de problemas como espacios de estados o

2.1Definici´n de un problema como espacio de estados o
x

Paso previo a la b´ squeda de soluciones de un problema: u
u

Especificaci´n del problema o

x

Elementos del problema
u u u u

¿Cu´l es el objetivo final? a ¿Cu´l la situaci´n inicial desde la que se parte? a o ¿C´mo describir las diferentes situaciones o estados por los que podemos pasar? o ¿Qu´ acciones u operadores se pueden llevar acabo en cada momento para cambiar e las situaciones y c´mo cambian? o

x

Especificar un problema como espacio de estados consiste en describir de manera clara cada de uno de estos componentes
u u

Ventaja: procedimientos generales de b´ squeda de soluciones u Independientes del problema

IA-I 2006–2007

CcIa

Representaci´n de problemas como espacios de estados o

2.2

M´todo desoluci´n de problemas e o
ABSTRACCION

Problema

Expresion como espacio de estados

Solucion
INTERPRETACION

Aplicacion de al− goritmos de bus− queda de solucion
IA-I 2006–2007

Implementacion en un lenguaje de programacion
Representaci´n de problemas como espacios de estados o 2.3

CcIa

Planteamiento del problema del 8-puzle
x

Enunciado: Para el 8-puzle se usa un caj´ncuadrado en el que hay situados 8 o bloques cuadrados. El cuadrado restante est´ sin rellenar. Cada bloque a tiene un n´ mero. Un bloque adyacente al hueco puede deslizarse hacia u ´l. El juego consiste en transformar la posici´n inicial en la posici´n final e o o mediante el deslizamiento de los bloques. En particular, consideramos el estado inicial y final siguientes:
2 1 7 8 6 3 4 5 1 8 7 6 2 3 45

Estado inicial

Estado final

IA-I 2006–2007

CcIa

Representaci´n de problemas como espacios de estados o

2.4

Representaci´n de estados o
x

Estado: descripci´n de una posible situaci´n en el problema o o
u

Abstracci´n de propiedades o

x

Importancia de una buena representaci´n de los estados o
u u u

S´lo considerar informaci´n relevante para el problema o oRepresentaci´n suficiente y necesaria o La representaci´n escogida influye en el n´ mero de estados y ´ste en los procedio u e mientos de b´ squeda de soluciones u

x

Ejemplo: 8-puzle: Elementos de la representaci´n: o
u u u

Localizaci´n de cada bloque y del hueco; o tipo de material de los bloques; colores de los bloques, ...

IA-I 2006–2007

CcIa

Representaci´n de problemas comoespacios de estados o

2.5

Representaci´n de estados o
x

Ejemplo del 8-puzle: Representaciones del estado
u

Gr´fico: a
2 1 7 8 6 3 4 5

u

Descripci´n de la posici´n exacta de cada uno de los bloques o o

x

Representaci´n vs. implementaci´n o o
u u u

Lista: (2 8 3 1 6 4 7 H 5), (2 8 3 4 5 H 7 1 6) Matriz: ((2 8 3)(1 6 4)(7 H 5)) Hechos: ((primera-izquierda 2) (primera-centro8) ...)

x

N´ mero de estados = 9! = 362.880. u

IA-I 2006–2007

CcIa

Representaci´n de problemas como espacios de estados o

2.6

Operadores
x

Operadores:
u

Representan un conjunto finito de acciones b´sicas que transforman unos estados a en otros

x

Elementos que describen un operador
u u

Aplicabilidad: precondici´n y postcondici´n o o Estado resultante de laaplicaci´n de un operador (aplicable) a un estado o

x

Criterio para elegir operadores.
u u

Depende de la representaci´n de los estados o Preferencia por representaciones con menor n´ mero de operadores u

x

Ejemplo: Operadores del 8-puzle:
u u

Seg´ n los movimientos de los bloques: 32. u Seg´ n los movimientos del hueco: 4. u
CcIa
Representaci´n de problemas como espacios de...