(Nota: Tarea 3 de la asignatura Introducción a la Inteligencia Artificial)
Introducción
La Inteligencia Artificial puede resolver multitud de problemas cuya característica común es la elevada complejidad que presenta su resolución. Tanto es así, que un problema para el que no existe un método matemático que lo resuelva, es precisamente un problema específico para la IA, o también, problemas cuyos métodos de resolución resulten demasiado costosos de implementar.
Representando los problemas como un espacio o conjunto de estados que formen un grafo donde los nodos son diferentes estados, la solución computacional corresponde a
encontrar un camino desde el estado inicial a un estado objetivo.
Normalmente, para resolver estos problemas se utiliza una gran cantidad de información que en ocasiones es poco precisa, lo que dificulta la resolución de los problemas con fórmulas matemáticas, por lo que para ello se aplican lo que se llaman técnicas de búsqueda. Es decir, dado el problema como un espacio de estados, se planteará resolverlos como un problema de búsqueda en ese espacio de estados.
Algunos problemas de la vida real que se pueden plantear y resolver como espacios de estados serían, por ejemplo:(Tema 2: Representación de problemas como espacios de Estados, 2019):
- Búsquedas de rutas en redes informáticas
- Rutas aéreas para viajar
- Problema del viajante
- Diseño de microchips
- Ensamblaje de componentes
- Desplazamiento de robots
Ejemplo. Problema del viajante: Dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad de origen?
 |
Representación del problema del viajante con un grafo. Fuente: Wikipedia
|
El problema del viajante puede ser representado como un grafo donde las ciudades son los vértices, las artistas son los caminos y las distancias entre los caminos son los valores de las aristas.
Si como en el ejemplo, el problema no presenta muchos estados, la técnica de búsqueda específica que se suele utilizar es la búsqueda exhaustiva, pero si contamos con muchos operadores o muchos estados, esto sería eterno.
Como ejemplo típico tenemos al juego del ajedrez, para el que sería imposible representarlo por medio de un grafo. Además, en la realidad los jugadores emplean su conocimiento, pero también su experiencia y su intuición para decidir qué jugada realizar. Esto, la experiencia, la intuición y en general, al conjunto de ese tipo de información se le denomina información heurística y permite elegir el camino correcto hacia la solución del problema.
Pondré el ejemplo del temario porque me parece muy acertado: En la vida cotidiana es muy frecuente que apliquemos heurísticos, como cuando alguien se encuentra de vacaciones por distintas ciudades. Lo lógico, es que busque la oficina de turismo y, generalmente, esas oficinas se encuentran cerca de las estaciones de tren o de autobús o en el centro de la ciudad, por lo que la atención del turista se centrará en dichos lugares. Esto es un heurístico válido, pero no seguro.
Definir un buen heurístico es complicado, de forma que el uso de un mal
heurístico puede resultar en la elección de caminos cuyo coste no sea el
mínimo y habrá que seguir buscando, de forma que a medida que se
ha obtenido un estado válido, el siguiente a considerar sea el que mejor
heurística nos dé.
La información heurística se implementa al proceso de búsqueda mediante una función de evaluación, a través de probabilidades, distancias o diferencias métricas entre un nodo y el objetivo. Existen muchas opciones, una de las más usadas en resolver puzzles es la Distancia Manhattan que sería la suma de las distancias de unas fichas de puzzle desordenadas desde la posición actual hasta la posición correcta.
Algoritmo A* y condición para su éxito
Junto con la heurística hay un factor que es de gran importancia, el coste de un operador. Encontrar la solución o el camino correcto del menor coste es lo que proporciona este algoritmo.
Es muy utilizado
en Inteligencia Artificial y en juegos como el ajedrez, de hecho, fue
el utilizado en el ordenador Deep Blue que venció por
primera vez en la historia al Campeón del Mundo de Ajedrez Gary Kasparov
en 1997.
Desarrollado en 1968 por los informáticos Peter Hart,
Nils Nilsson y Bertram Raphael, es un método de búsqueda para encontrar la ruta más
corta, pero también con menor coste, entre dos puntos. Para ello, utiliza dos listas, una abierta en la que están los
estados o nodos sin explorar y una lista cerrada en la que están los que
ya han sido explorados y escoge como el siguiente estado a explorar el que minimiza la heurística y el coste. Comenzando con el nodo o estado inicial,
calcula la estimación del coste restante para llegar al objetivo desde
él, de forma que el nodo con un coste menor es el que se explora a
continuación, así sucesivamente hasta llegar a la solución (al
objetivo).
Además, si la heurística no es óptima, la complejidad computacional del algoritmo será exponencial y por lo tanto, se requerirá de la cantidad de memoria adecuada al tamaño del problema.
