2.1. Solución
de problemas en Inteligencia Artificial.
En general,
podemos afirmar que un problema consiste en:
• Una descripción de la situación de la que se
parte;
• Una descripción de la situación a la que se
quiere llegar;
• Una
descripción de los medios de que disponemos para alcanzar nuestro objetivo.
En el contexto
de la Informática, a partir de un problema, se intenta construir un sistema que
lo resuelva. Las acciones para construir un sistema que resuelva un problema
serían:
Definir el
problema con precisión (especificación del problema):
• De qué se parte;
• Cuál es el objetivo.
• Analizar el problema: información para elegir
las técnicas.
• Aislar y representar el conocimiento
necesario para resolver el problema.
• Elegir la
mejor técnica que resuelva el problema y aplicarla al problema particular.
Trasladar estas
acciones al contexto de la Inteligencia Artificial consiste en elegir las
técnicas de resolución entre aquellas que son utilizadas en esta disciplina.
Utilizaremos
como ejemplos para ilustrar las nociones teóricas algunos problemas que no son
aplicaciones reales de la Inteligencia Artificial. Se trata más bien de
ejemplos que han sido elegidos porque son suficientemente manejables, tanto en
cuanto a la facilidad de su enunciado como en cuanto al volumen de datos que es
necesario explorar para obtener una solución.
He aquí algunos
de ellos:
1) El 8-puzzle.
• Entrada:
Un tablero 3x3 donde aparecen distribuidos los dígitos 1, 2, 3, 4, 5, 6, 7 y 8,
quedando por tanto una de las casillas del tablero en blanco. Por ejemplo, un
tablero tal y como aparece en la Figura 1.
Figura 1
•Salida:
Alcanzar una disposición distinta de los dígitos en el tablero.
Habitualmente se toma como configuración de llegada el
tablero que tiene el dígito 1 en la primera casilla de la primera línea
(esquina superior izquierda) y los dígitos 2, 3, … , 8 se distribuyen uno a
continuación de otro en el sentido de las agujas del reloj, quedando la
posición central del tablero sin ocupar (ver Figura 2).
Figura 2
•Medios:
si una casilla del tablero está al lado de la casilla vacía se puede desplazar
sobre ella. (En particular, está prohibido usar un destornillador para sacar
las piezas y resituarlas como a uno le parezca … )
Revisa el siguiente enlace:
2) El problema de las garrafas de vino.
•Entrada:
dos garrafas vacías, una de cuatro litros y otra de tres.
•Salida: la garrafa de cuatro litros
contiene exactamente dos litros de vino.
•Medios:
se dispone de un depósito con mucho vino (más de 100 litros … ) y las únicas
operaciones permitidas son llenar cada garrafa en el depósito, vaciarlas en el
depósito y pasar contenido de una garrafa a la otra, hasta que la primera se
vacíe o la segunda se llene. (En particular, no es lícito suponer que se
dispone de otra garrafa que puede contener exactamente dos litros … )
3) El problema del granjero, el lobo, el carnero y la
lechuga.
•Entrada:
un granjero, un lobo, un carnero y una lechuga se encuentran en la orilla
derecha de un río.
•Salida:
todos ellos han pasado a la orilla izquierda del río.
•Medios
y restricciones: se dispone de una barca que debe ser conducida por el
granjero y que sólo tiene capacidad para uno de los otros elementos; el lobo se
comerá al carnero si los deja juntos sin compañía en uno de los lados; el
carnero se comerá la lechuga si los deja solos.
Ejercicios.
A partir de los
siguientes problemas, detallar con mayor
precisión la entrada, la salida y los medios de resolución.
1) El
problema del viajante. Un representante de comercio tiene que visitar una serie
de ciudades viajando entre ellas por carretera. Dispone de un plano de la región
con la información de las distancias entre las ciudades. Desea partir de la ciudad
en la que está para volver a ella tras haber visitado el resto de ciudades, pero
habiendo hecho el mínimo número de kilómetros posible.
2) Las n
reinas. Se trata de situar n reinas del ajedrez en un tablero n x n (siendo n un número entero positivo mayor
que 3 y el tablero normal tiene 8 x 8 casillas) de modo
que las reinas no se "coman" entre sí.
______________________________________________________________________________________________________
Para entender lo referente a Espacios de Estado Determinísticos y Espacios de Estado No Deterministicos:
El espacio de estados es una noción clave en los
sistemas de producción, puesto que es el lugar en el que se va a desarrollar la
búsqueda. Un
fragmento del espacio de estados para el 8-puzzle,
donde se ha elegido como representación para los operadores, los 4 operadores
citados antes. Ver figura 4.
______________________________________________________________________________________________________
2.2 ESPACIOS DE
ESTADOS.
Estado: Situación de algo o alguien junto con las características que lo
describen en un momento determinado. Puede cambiar.
Espacios de Estados
Es la
representación de un problema que abarca todas las posibles situaciones que se
pueden presentar en la solución de un problema. Utiliza una estructura definida
implícitamente (Se genera conforme a la situación) por los operadores o reglas. (Ver Figura 3)
Figura 3
Para entender lo referente a Espacios de Estado Determinísticos y Espacios de Estado No Deterministicos:
REPRESENTACIÓN DE PROBLEMAS
Una vez decidido que
el problema planteado va a ser resuelto
por medio de un sistema de producción/búsqueda en el espacio de estados,
debemos elegir una representación adecuada para el problema. Esto debe ser
resuelto en tres niveles:
•Conceptual.
•Lógico.
•Físico.
y en cada uno de ellos
deberemos elegir representaciones para dos cosas:
•Estados.
•Operadores.
El nivel conceptual hace referencia a qué
consideramos como estado del problema y qué
como regla u operador válido, pero independientemente de cualquier
estructura de datos o descripción de algoritmos que vayamos a usar.
En el nivel lógico se elige una estructura de datos
para los estados y se determina el formato de codificación de los operadores
(puede ser también una estructura de datos o se puede hacer proceduralmente).
Por último en el nivel físico se concreta para el
lenguaje de programación elegido la implementación de estados y operadores
determinada en el nivel lógico. Los niveles lógico y físico están confundidos
en ocasiones y, además, la fase clave para un procesamiento eficiente está en
el nivel conceptual.
Por ejemplo, para el problema del 8-puzzle:
En cuanto a los estados.
Nivel conceptual.
• localización de cada
casilla (numeradas del 1 al 8) y el hueco;
• nada más.
Opciones en el nivel lógico:
•matriz 3 x 3;
que puede tomar los valores de (x,y)
•vector de longitud 9;
•conjunto de hechos: {(superior-izda = 2),
(superior-centro = 1), … }.
Nivel físico.
Dependiendo
de las estructuras permitidas en un lenguaje de programación concreto, para
cada una de ellas son posibles diferentes elecciones.
En cualquier caso, la
elección de la representación para los estados está muy ligada a la que se haga
para los operadores, puesto que ambos elementos deben "cooperar" para
la resolución del problema.
En cuanto a los operadores, deben ser tan generales como sea posible para así reducir el número
de reglas distintas. En el caso del 8-puzzle:
Nivel conceptual.
•4 x 9! operadores para pasar de un estado cualquiera
a sus, como máximo 4, estados sucesores;
•4 x 8 operadores que mueven cualquier ficha arriba,
abajo, derecha o izquierda;
•4 operadores que mueven el hueco arriba, abajo,
derecha o izquierda.
Nota: Evidentemente, la última representación es la
más adecuada.
Nivel Lógico.
• El procedimiento inferencial para mover una pieza
según su situación actual.
Nivel Físico.
La definición
conceptual, lógica y física de los estados y los operadores están relacionados
entre sí, por lo que la elección del lenguaje de programación para implementar
las reglas operacionales depende del elegido para los estados.
La elección de una
representación para los estados y los operadores define implícitamente una
relación de adyacencia en el conjunto de estados factibles para el problema. A
este conjunto con la estructura de adyacencia definida se le denomina espacio
de estados.
Figura 4
En conclusión, el espacio de estados es el conjunto de
estados factibles para un problema junto a la estructura de adyacencia definida
implícitamente por los operadores o reglas.
Como estructuras, las posibilidades relevantes son:
a)
Árbol
b)
Grafo
dirigido o acíclico
c)
Grafo
dirigido no acíclico
d)
Grafo
no dirigido
Tarea: Por equipo traer un ejemplo de cada uno de los
anteriores para el día 25 de Febrero (Actividad individual).
¿Qué significa encontrar una solución?
La solución consiste
en una secuencia de operadores que transforman el estado inicial en el estado
objetivo.
Tenemos dos problemas
distintos:
• El problema de decisión: consiste simplemente en decir si sí o no se puede alcanzar el objetivo desde el estado inicial.
• El problema de explicación: en este caso se debe indicar cómo se ha llegado desde
el estado inicial hasta el objetivo.
En este último caso,
el sistema de producción debe disponer de un modo de almacenamiento de los
caminos que van siendo explorados.
Opciones de solución en un espacio de estados:
- Encontrar la secuencia más corta.
- Encontrar la secuencia menos costosa (en este caso se supondrá que los disparos de las reglas tienen asociado un coste o, equivalentemente, que el espacio de estados tiene pesos en las aristas).
- Encontrar cualquier secuencia lo más rápido posible.
- Una última variante para todos los problemas de búsqueda requiere no sólo que se encuentre un camino de solución, sino todos los que existan.
BÚSQUEDAS EN ESTRUCTURAS DE ÁRBOLES
Primero revisa el siguiente material:
O bien, copia el siguiente enlace en un
navegador:
O bien, copia los enlaces en un navegador
Actividad: Una vez revisado el
material indicado, analiza los siguientes grafos y explica los dos posibles
recorridos realizados para el puzzle 8. Escribe tu análisis y entrégalo a la
profesora en la misma clase.
Búsqueda en anchura.
Figura 5
Búsqueda en profundidad.
Figura 6
Actividad por equipo:
a) Investiga sobre los diferentes métodos de búsqueda y elige uno. Representa un ejemplo claro aplicable a algún tema de la vida cotidiana.
b) El método elegido será expuesto en clase dejando muy claro el proceso de búsqueda.
MATERIAL PARA PROYECTO:
a) Revisa en qué consisten las Torres de Hanoi aquí.
b) Revisa este material a detalle para que realices el proyecto de la Unidad
c) Representa el problema para los estados y los operadores a nivel conceptual, lógico y físico.
d) El valor de entrada es: el número de piezas para trabajar con las Torres y el valor de salida será: La torre 3 con todas las piezas en orden. Por lo tanto, de acuerdo a los enlaces indicados previamente, define las posibles reglas a aplicar.
e) Realiza el proyecto en un lenguaje de programación elegido, muestra gráficamente la solución sin que el usuario tenga que mover las piezas.
Nota: debe aceptar de 3 a 15 piezas, sin restricciones.
