Conceptos básicos de IA: A * Algoritmo de búsqueda

C

 

Introducción

La inteligencia artificial en su núcleo se esfuerza por resolver problemas de enorme complejidad combinatoria. A lo largo de los años, estos problemas se redujeron a problemas de búsqueda.

Un problema de búsqueda de ruta es un problema computacional en el que tiene que encontrar una ruta desde el punto A al punto B. En nuestro caso, asignaremos problemas de búsqueda a gráficos apropiados, donde los nodes representan todos los estados podemos terminar y el bordes representando todos los caminos posibles que tenemos a nuestra disposición.

Entonces, la siguiente pregunta lógica sería:

¿Cómo convertimos un problema en un problema de búsqueda?

¿Qué es A *?

Digamos que tienes que atravesar un laberinto enorme. Este laberinto es tan grande que se necesitarían horas para encontrar el objetivo manualmente. Además, una vez que termines el laberinto “a pie”, se supone que debes terminar otro.

Para hacer las cosas significativamente más fáciles y que consuman menos tiempo, reduciremos el laberinto a un problema de búsqueda y encontraremos una solución que se pueda aplicar a cualquier laberinto adicional que podamos encontrar, siempre que siga las mismas reglas / estructura.

Siempre que queramos convertir cualquier tipo de problema en un problema de búsqueda, tenemos que definir seis cosas:

  • Un conjunto de todos los estados en los que podríamos terminar
  • El estado de inicio y finalización
  • Una comprobación de finalización (una forma de comprobar si estamos en el estado final)
  • Un conjunto de posibles acciones (en este caso, diferentes direcciones de movimiento)
  • Una función transversal (una función que nos dirá dónde terminaremos si vamos en cierta dirección)
  • Un conjunto de costos de movimiento de un estado a otro (que corresponden a los bordes en el gráfico)

El problema del laberinto se puede resolver mapeando las intersecciones con los nodes apropiados (puntos rojos) y las posibles direcciones en las que podemos ir a los bordes apropiados del gráfico (líneas azules).

Naturalmente, definimos los estados de inicio y finalización como las intersecciones donde ingresamos al laberinto (node A), y donde queremos salir del laberinto (node B).

Ahora que tenemos un gráfico terminado, podemos discutir algoritmos para encontrar una ruta desde el estado A al estado B. En casos simples (como este), donde el gráfico generado consta de una pequeña cantidad de nodes y aristas, BFS, DFS y Dijkstra bastaría.

Sin embargo, en un escenario de la vida real, debido a que estamos lidiando con problemas de enorme complejidad combinatoria, sabemos que tendremos que lidiar con una enorme cantidad de nodes y aristas. Por ejemplo, hay muchos estados en los que puede estar un cubo de Rubik, razón por la cual resolverlo es tan difícil. Por tanto, tenemos que utilizar un algoritmo que, en cierto sentido, sea guiado. Ahí es donde surge un algoritmo de búsqueda informado, A *.

La búsqueda informada significa que el algoritmo tiene información adicional, para empezar. Por ejemplo, un algoritmo de problema de búsqueda desinformado sería encontrar un camino desde casa al trabajo completamente a ciegas.

Por otro lado, un algoritmo de problema de búsqueda informado sería encontrar un camino desde su casa al trabajo con la ayuda de su vista (ver qué camino lo acerca a su destino) o un mapa (saber exactamente a qué distancia está cada punto). desde su destino).

A * solo realiza un paso si parece prometedor y razonable, de acuerdo con sus funciones, a diferencia de otros algoritmos de recorrido de gráficos. Corre hacia la meta y no considera ningún paso no óptimo si no tiene que considerarlos.

Esto hace que A * sea muy útil para sistemas artificialmente inteligentes, especialmente en Machine Learning y desarrollo de juegos, ya que estos sistemas replican escenarios del mundo real.

Si desea leer más sobre los algoritmos de recorrido de gráficos, sus aplicaciones y diferencias, ¡los tenemos cubiertos!

Conceptos básicos de A *

A * se basa en el uso heurístico métodos para lograr la optimización y la completitud, y es una variante del algoritmo del mejor primero.

Cuando un algoritmo de búsqueda tiene la propiedad de la optimización, significa que está garantizado que encontrará la mejor solución posible, en nuestro caso el camino más corto hasta el estado final. Cuando un algoritmo de búsqueda tiene la propiedad de estar completo, significa que si existe una solución a un problema dado, se garantiza que el algoritmo la encontrará.

Cada vez que A * entra en un estado, calcula el costo, f(n) (siendo n el node vecino), para viajar a todos los nodes vecinos, y luego entra en el node con el valor más bajo de f(n).

Estos valores se calculan con la siguiente fórmula:

$$
mathcal f (n) = mathcal g (n) + mathcal h (n)
$$

g(n) siendo el valor de la ruta más corta desde el node inicial al node n, y h(n) siendo una aproximación heurística del valor del node.

Para que podamos reconstruir cualquier ruta, necesitamos marcar cada node con el relativo que tiene el óptimo f(n) valor. Esto también significa que si volvemos a visitar ciertos nodes, también tendremos que actualizar sus parientes más óptimos. Más sobre eso más tarde.

La eficiencia de A * depende en gran medida del valor heurístico h(n), y dependiendo del tipo de problema, es posible que necesitemos usar una función heurística diferente para encontrar la solución óptima.

La construcción de tales funciones no es una tarea fácil y es uno de los problemas fundamentales de la IA. Las dos propiedades fundamentales que puede tener una función heurística son la admisibilidad y la coherencia.

Admisibilidad y coherencia

Una función heurística dada h(n) es admisible si nunca sobreestima la distancia real entre n y el node objetivo.

Por lo tanto, para cada node n se aplica la siguiente fórmula:

$$
h (n) leq h ^ * (n)
$$

h*(n) siendo la distancia real entre ny el node objetivo. Sin embargo, si la función sobreestima la distancia real, pero nunca en más de d, podemos decir con seguridad que la solución que produce la función es de precisión d (es decir, no sobreestima el camino más corto de principio a fin en más de re).

Una función heurística dada h(n) es consistente si la estimación es siempre menor o igual que la distancia estimada entre la meta n y cualquier vecino dado, más el costo estimado de llegar a ese vecino:

$$
c (norte, metro) + h (metro) geq h (norte)
$$

c(n,m) siendo la distancia entre nodes n y m. Además, si h(n) es consistente, entonces conocemos la ruta óptima a cualquier node que ya haya sido inspeccionado. Esto significa que esta función es óptima.

Teorema: Si una función heurística es consistente, también es admisible.

Prueba por inducción completa

El parámetro de inducción N será el número de nodes entre el node n y el node final s en el camino más corto entre los dos.

Base: N = 0

Si no hay nodes entre n y s, y porque sabemos que h(n) es consistente, la siguiente ecuación es válida:

$$
c (norte, s) + h (s) geq h (n)
$$

Conocimiento h*(n)=c(n,s) y h(s)=0 podemos deducir con seguridad que:

$$
h ^ * (n) geq h (n)
$$

Hipótesis de inducción: N <k

Suponemos que la regla dada es verdadera para cada N < k.

Paso de inducción:

En el caso de N = k nodes en el camino más corto desde n a s, inspeccionamos el primer sucesor (node m) del node final n. Porque sabemos que hay un camino desde m a n, y sabemos que esta ruta contiene k-1 nodes, la siguiente ecuación es válida:

$$
ℎ ^ * (𝑛) = 𝑐 (𝑛, 𝑚) + ℎ ^ * (𝑚) ≥ 𝑐 (𝑛, 𝑚) + ℎ (𝑚) ≥ ℎ (𝑛)
$$

QED

Implementación

Esta es una implementación directa de A * en una estructura gráfica. La función heurística se define como 1 para todos los nodes por motivos de simplicidad y brevedad.

El gráfico se representa con una lista de adyacencia, donde las claves representan los nodes del gráfico y los valores contienen una lista de bordes con los nodes vecinos correspondientes.

Aquí encontrará el algoritmo A * implementado en Python:

from collections import deque

class Graph:
    # example of adjacency list (or rather map)
    # adjacency_list = {
    # 'A': [('B', 1), ('C', 3), ('D', 7)],
    # 'B': [('D', 5)],
    # 'C': [('D', 12)]
    # }

    def __init__(self, adjacency_list):
        self.adjacency_list = adjacency_list

    def get_neighbors(self, v):
        return self.adjacency_list[v]

    # heuristic function with equal values for all nodes
    def h(self, n):
        H = {
            'A': 1,
            'B': 1,
            'C': 1,
            'D': 1
        }

        return H[n]

    def a_star_algorithm(self, start_node, stop_node):
        # open_list is a list of nodes which have been visited, but who's neighbors
        # haven't all been inspected, starts off with the start node
        # closed_list is a list of nodes which have been visited
        # and who's neighbors have been inspected
        open_list = set([start_node])
        closed_list = set([])

        # g contains current distances from start_node to all other nodes
        # the default value (if it's not found in the map) is +infinity
        g = {}

        g[start_node] = 0

        # parents contains an adjacency map of all nodes
        parents = {}
        parents[start_node] = start_node

        while len(open_list) > 0:
            n = None

            # find a node with the lowest value of f() - evaluation function
            for v in open_list:
                if n == None or g[v] + self.h(v) < g[n] + self.h(n):
                    n = v;

            if n == None:
                print('Path does not exist!')
                return None

            # if the current node is the stop_node
            # then we begin reconstructin the path from it to the start_node
            if n == stop_node:
                reconst_path = []

                while parents[n] != n:
                    reconst_path.append(n)
                    n = parents[n]

                reconst_path.append(start_node)

                reconst_path.reverse()

                print('Path found: {}'.format(reconst_path))
                return reconst_path

            # for all neighbors of the current node do
            for (m, weight) in self.get_neighbors(n):
                # if the current node isn't in both open_list and closed_list
                # add it to open_list and note n as it's parent
                if m not in open_list and m not in closed_list:
                    open_list.add(m)
                    parents[m] = n
                    g[m] = g[n] + weight

                # otherwise, check if it's quicker to first visit n, then m
                # and if it is, update parent data and g data
                # and if the node was in the closed_list, move it to open_list
                else:
                    if g[m] > g[n] + weight:
                        g[m] = g[n] + weight
                        parents[m] = n

                        if m in closed_list:
                            closed_list.remove(m)
                            open_list.add(m)

            # remove n from the open_list, and add it to closed_list
            # because all of his neighbors were inspected
            open_list.remove(n)
            closed_list.add(n)

        print('Path does not exist!')
        return None

Veamos un ejemplo con el siguiente gráfico ponderado:

Ejecutamos el código así:

adjacency_list = {
    'A': [('B', 1), ('C', 3), ('D', 7)],
    'B': [('D', 5)],
    'C': [('D', 12)]
}
graph1 = Graph(adjacency_list)
graph1.a_star_algorithm('A', 'D')

Y la salida se vería así:

Path found: ['A', 'B', 'D']
['A', 'B', 'D']

Por lo tanto, el camino óptimo desde A a D, encontrado usando A *, es A->B->D.

Conclusión

A * es un algoritmo muy poderoso con un potencial casi ilimitado. Sin embargo, solo es tan bueno como su función heurística, que puede ser muy variable considerando la naturaleza de un problema.

Ha encontrado aplicaciones en muchos sistemas de software, desde Machine Learning y Search Optimization hasta el desarrollo de juegos donde los personajes NPC navegan a través de terrenos complejos y obstáculos para llegar al jugador.

 

About the author

Ramiro de la Vega

Bienvenido a Pharos.sh

Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

Add comment

Sobre mi

Últimos Post

Etiquetas

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad