¿Cómo se comparan los algoritmos comunes de Pathfinding con el proceso humano?

11

Esto podría estar al borde de la ciencia cognitiva computacional, pero tengo curiosidad sobre cómo el proceso seguido por los algoritmos de búsqueda de caminos comunes (como A * ) se compara con el proceso que los humanos usan en diferentes situaciones de búsqueda de caminos (dada la misma información). ¿Son similares estos procesos?

DorkRawk
fuente
3
Los humanos pueden usar el algoritmo de búsqueda de ruta A * ... quiero decir, un algoritmo es solo una técnica, ¿verdad? No creo que haya ningún algoritmo que un ser humano no pueda realizar. Supongo que a lo que estoy tratando de llegar es a que probablemente deberías ser mucho más claro en términos de lo que constituye "el proceso que los humanos usan en diferentes situaciones de búsqueda de caminos". No creo que nadie pueda darte una respuesta significativa hasta que digas cómo lo hacen los humanos ... lo que probablemente sea problemático en el caso general, y parece ser difícil aquí también.
Patrick87
Además, explique brevemente qué hace A * y / o enlace a una referencia. ¡Y bienvenido!
Raphael
@ Patrick87 Ciertamente, los humanos PUEDEN hacer cualquier algoritmo, pero esa no es una pregunta muy interesante. A lo que intentaba llegar era a cómo los algoritmos de búsqueda de caminos se comparan con las técnicas utilizadas por los humanos cuando se les deja resolver un problema por sí mismos (sin conocimiento previo de algoritmos de búsqueda de caminos).
DorkRawk
3
Existen estudios sobre el comportamiento humano en tales situaciones: una respuesta razonable podría apuntar a estudios reales sobre cómo los humanos realizan la búsqueda de caminos.
Suresh
2
A

Respuestas:

6

Los humanos tienden a elegir soluciones no estrictamente óptimas, sino cercanas a las más cortas. Por lo tanto, deberá buscar algoritmos difusos (aproximados), no A *.

El algoritmo más cercano al pensamiento humano que conozco es una jerarquía de contacto a la par con un algoritmo de poda Reach . Cuando necesito encontrar una ruta entre A y B en el mapa, hago una descripción general rápida, teniendo en cuenta si hay cruce de río u otra cosa y buscando algunas formas generales y luego agrego detalles que podrían acortar la ruta.

Om nom nom
fuente
¿Puede decir que el último enfoque es el camino más corto solo que comienza con una aproximación aproximada del gráfico y refina el gráfico a medida que avanza?
Raphael
@Raphael Sí, en realidad es una descripción de lo que hacen las Jerarquías de Contacción (también hay un paso de preprocesamiento, que toma el gráfico y lo colapsa en una jerarquía con diferentes niveles de detalle) y simultáneamente de lo que haré como ser humano
om-nom -nom
4

Aquí tienes una serie de consideraciones. Los dos primeros fueron tomados del maravilloso doctorado por Andreas Junghanns (ahora de vuelta a la industria en Berlín, Alemania y feliz de contarlo entre mis amigos :)):

Búsqueda de Breadth-First : si está de pie frente a un mueble y algo valioso (por ejemplo, una moneda o un anillo) cae y se coloca debajo del mueble, para que no pueda verlo, entonces agita la mano ligeramente desde el punto donde vio desaparecer el objeto. Si no lo encuentra, vaya un poco más allá y continúe de esta manera hasta que lo encuentre o pierda la paciencia. Esa es exactamente la búsqueda de amplitud en acción: primero, considera todas las ubicaciones desconocidas en la profundidad 1, luego en la profundidad 2 y así sucesivamente.

Búsqueda en profundidad : cuando busca algo que se encuentra de forma remota en su entorno, nunca elige el algoritmo mencionado anteriormente y, en cambio, se compromete con una dirección. Un ejemplo es Cristóbal Colón comprometiéndose con el oeste cuando busca una ruta hacia los indios. Bueno, estaba equivocado, pero eso lo sabemos hoy en día. Imagínese a Colón intentando una búsqueda de primer orden y moviéndose a lo largo de una espiral desde Burgos, donde se firmó el contrato entre los Reyes Católicos y Colón. En cambio, señaló una dirección determinada sin retroceder nunca.

Otro ejemplo de uno de mis profesores en la Universidad (José Cuena, quien ya falleció) se refiere a la búsqueda bidireccional : ingenieros, cuando la construcción de túneles en las montañas comienza desde ambos extremos simultáneamente y termina cuando se encuentran en algún punto intermedio. La razón es simple: si comienzan solo desde un extremo, es muy probable que haya una gran desviación en el otro extremo. Comenzar desde ambos extremos minimiza simultáneamente la desviación en el punto de encuentro.

  • La lista abierta es solo la lista de posibilidades abiertas que esperan ser consideradas. Todos los humanos hacemos esto aunque no somos tan buenos como las computadoras recordando cosas.
  • La lista cerrada solo sirve para evitar el razonamiento circular o el razonamiento continuo desde un punto que ya consideramos antes. Esto sucede si está razonando en voz alta y repite algo. Entonces, alguien se dará cuenta e inmediatamente te dirá "hey hombre, ya lo dijiste antes"

Una pregunta muy interesante de alguna manera abordada por otros es si los humanos pueden ejecutar algún algoritmo y (aún más interesante desde mi punto de vista) si estos algoritmos (o, en general, la forma en que construimos la Inteligencia Artificial) imitan nuestros procedimientos inteligentes naturales.

Carlos Linares López
fuente
El documento mencionado por Carlos se puede leer aquí: svn.sable.mcgill.ca/sable/courses/COMP763/oldpapers/…
TFerrell
-2

¿Has visto a un niño aprender a navegar por una habitación? Tienes que decirles: "Ve alrededor de la mesa. ALREDEDOR ".

La planificación del camino humano es una bolsa de heurística, algunas innatas y otras aprendidas. Lookahead probablemente está fijado a un número pequeño, ciertamente no es una recursividad general como A *.

Trevor Blackwell
fuente
1
Esta respuesta contiene solo especulaciones.
Raphael