Hoy os voy a hablar del algoritmo A* y a darle un poco al cerebro intentando descubrir cuáles pueden ser sus limitaciones. Para empezar os contaré que lo que hace el algoritmo A* es algo que nosotros hacemos de forma natural a la hora de realizar algunas de nuestras tareas cotidianas.
Antes de entrar en el algoritmo en sí mismo os voy a contar algo que yo hago de forma reiterada y que se corresponde con la versión humana del algoritmo A*.
Habitualmente hago las compras los sábados por la mañana y siempre compro en los comercios de mi entorno. Así que, normalmente antes de salir de casa me hago un esquema mental de la distancia que tengo que recorrer, el peso que tengo que cargar y las tiendas que voy a visitar. Para cuando voy a las compras ya he pensado cuál es mi primer destino y cuál es el último, para optimizar el tiempo que tardo en comprar y para no cargar con mucho peso durante mucho recorrido. En definitiva, que traduzco el mapa de mi entorno a nodos, e intento calcular cuál va a ser el recorrido que hace óptimo el coste en tiempo y esfuerzo. Lógicamente el recorrido y la selección de nodos la hago mentalmente descartando de entrada aquellos que no me resultan válidos para mi objetivo.
Bueno, pues esto que yo hago de cabeza, que ya sé que soy como una máquina😅, es lo que hace el algoritmo A*.
El algoritmo A* es un algoritmo de búsqueda informada en grafos de tipo heurístico, es decir que utiliza el conocimiento específico del problema más allá de su definición. Se trata de buscar recorridos de bajo coste usando un heurístico que utilice la información de forma eficiente. Normalmente encuentra el camino de menor coste desde un nodo origen a un nodo objetivo. El algoritmo no podrá resolver aquellos problemas que no estén bien definidos.
Se trata de grafos informados, es decir, que de cada nodo se conoce la relación con los otros y se guían exclusivamente por la función heurística. En los casos en los que no se conozca bien qué es un nodo y la relación con otros, el algoritmo no será de utilidad.
Pero ¿qué es un heurístico? Existen varios puntos de vista desde el que se puede definir, pero por analogía con nuestro procesamiento mental, la definición más comprensible es la siguiente:
“Una forma sencilla y eficiente de orientar la toma de decisiones, para explicar en un plano práctico cómo las personas llegan a un juicio o solucionan un problema”
Por extensión al ámbito que nos ocupa, una heuristica es una regla o conjunto de reglas que permite escoger ramas del espacio de estados que llevan a una solución aceptable. Aunque puede fallar ya que depende de la intuición y de la información del estado. En la metodología científica resulta útil cuando no contamos con un procedimiento algorítmico de solución. En el caso de que las ramas entre nodos no estén bien definidas, el heurístico no funcionará bien para el algoritmo.
Este algoritmo, trata de calcular el camino de menor coste teniendo en cuenta dos factores: el coste del camino para llegar a un nodo y el valor del heurístico de un nodo a evaluar. El conjunto de ambos factores nos dará el mérito del nodo. Por lo tanto el siguiente paso será ir al nodo con mayor mérito.
Sin embargo, también tiene algunas limitaciones. La primera de ellas es la que se refiere a los estados, el algoritmo tendrá dificultades en cuanto sean estados difícilmente evaluables y las distancias no sean medibles. Debe ser completo, si lo es encontrará la solución, en caso contrario, no alcanzará la solución. Del mismo modo que tampoco será útil en situaciones con alto grado de incertidumbre. En este caso no se pueden determinar con seguridad los estados y por tanto su evaluación no será posible.
Por otra parte, el heurístico debe ser bien elegido. Debe ser consistente, es decir, que para todo nodo y sus sucesores el coste de alcanzar el objetivo desde un nodo no sea mayor que el de alcanzar el nodo sucesor y de ese al objetivo. Se debe elegir aquel que aprovecha mejor la información del estado. Y que nunca sobreestime el coste de alcanzar la meta.
La complejidad será exponencial si la función heurística es mala. Sin embargo, si es buena, el algoritmo funcionará en tiempo lineal. Así que la utilización del algoritmo también está limitada por la posibilidad de elegir un heurístico que valore los nodos y los caminos de forma correcta.
A modo de resumen lo más relevante para elegir un buen algoritmo A* depende de que elijamos un buen heurístico que nos lleve a una buena solución. Eso significa que si el heurístico no esta bien elegido el cálculo del coste no necesariamente será el mejor. A lo que hay que añadir que si no se cumplen todas las limitaciones el espacio para ser ejecutado crecerá de forma exponencial, ya que debe almacenar la información de todos los siguientes nodos desde uno dado.
Si lo analizamos desde mi algoritmo para hacer las compras, las limitaciones serían:
- No saber qué compras tengo que hacer y dónde (Formulación del problema)
- No saber dónde están las tiendas. (Nodos)
- No conocer la distancia entre ellas. (Distancia ente nodos)
- No conocer mi capacidad para cargar peso. (Coste del recorrido entre nodos)
Así que si yo no valoro bien estos aspectos, tardaré mucho, me cansaré y seguro que me dejo algo sin comprar.
Estamos hablando de inteligencia, aunque se trate de artificial, y en algunos casos queremos equipararla a la nuestra como he hecho con mi ejemplo. Sin entrar en los detalles técnicos, que es lo que explicado hasta ahora, me gustaría contaros desde el punto de vista humano los problemas que creo que no podría solucionar este algoritmo.
¿Cuáles son sus límites? Es difícil contestar a esta pregunta, pero por intentarlo que no sea. En primer lugar creo que uno de los límites será, debido a su definición, aquellos en los que los estados no puedan ser definidos o representados de forma clara y unívoca. De entrada, creo que no podrá con los asuntos que supongan cuestiones éticas o morales que procedan del bagaje cultural humano y del propio aprendizaje a través de las relaciones sociales. Es posible que en sus soluciones o respuestas se pueda comportar como un niño que solo se rige por ciertas normas aprendidas pero que no ha tenido interacción social suficiente para imitar el comportamiento de los adultos frente a ciertas situaciones.
Tampoco creo que pudiera responder bien a las situaciones en las que los humanos nos encontramos en situación de disonancia cognitiva aspecto muy propio del comportamiento humano. Sus respuestas estarán basadas en su propio aprendizaje . Lo que obviamente hará sera procesar más información sobre una cosa en concreto y evaluar todos los posibles caminos que llevan a la solución. Y todo desde un punto de vista estadisticamente a priorista. Mientras que nosotros, en la evaluación de riesgos o en el establecimiento de soluciones unívocas, normalmente recurrimos al ensayo error y en muchas ocasiones nos dejamos llevar por caminos sin recorrer o sin explorar. No tenemos ni la capacidad ni el tiempo para poder procesar todo lo que necesitamos para elegir un camino que lleve a la solución directamente. De hecho, creo que de aquí procede el ansia humana por la comunicación con otros y la creación de inteligencia artificial que pueda explorar aquello a lo que nosotros no llegamos. Es una forma de ahorrarnos caminos que nos conducen a estados que, gracias a la experiencia de otros, sabemos que no son viables o que el resultado no es el óptimo.
Me planteo la siguiente pregunta: si no somos capaces de conocer nuestro propio comportamiento más alla de algunas pautas generales, ¿cómo vamos a conseguir que un algoritmo simule ese comportamiento? ¿actuando de forma aleatoria? Los heurísticos nos abren vías a encontrar soluciones rápidas. Pero, ¿sabemos lo que aprende la máquina una vez que ha empezado a funcionar de forma independiente?
Una de las cosas que más caracteriza al ser humano es la capacidad de mentir. ¿Eso lo puede hacer una máquina?. El objetivo de la mentira es precisamente alcanzar una meta que de otra forma resulta inviable. ¿Puede hacerlo un algoritmo? Creo que, con certeza puedo decir, que el algoritmo A* no puede.
Referencias:
http://idelab.uva.es/algoritmo
https://es.wikipedia.org/wiki/Algoritmo_de_b%C3%BAsqueda_A*
This work © 2022 by darthscience666 is licensed under
Comentarios
Publicar un comentario