Como os algoritmos comuns de busca de caminhos se comparam ao processo humano

Isso pode estar relacionado à ciência cognitiva computacional, mas estou curioso para saber como o processo seguido por algoritmos comuns de busca de caminhos (como A * ) se compara ao processo que os humanos usam em diferentes situações de busca de caminhos (com as mesmas informações). Esses processos são semelhantes?

Os humanos tendem a escolher não estritamente ideal, mas aproximam-se das soluções mais curtas. Portanto, você precisará olhar para algoritmos difusos (aproximados), não para A *.

O algoritmo mais próximo do pensamento humano que eu conheço é uma hierarquia de Contação a par de um algoritmo de remoção de alcance . Quando preciso encontrar um caminho entre A e B no mapa, faço uma rápida visão geral, levando em consideração se há travessia de rio ou algo mais e procurando algumas maneiras gerais e adicionando detalhes que podem encurtar o caminho.

Aqui estão algumas considerações. Os dois primeiros foram retirados do maravilhoso doutorado de Andreas Junghanns (agora de volta à indústria em Berlim, Alemanha, e felizes em contá-lo entre meus amigos :)):

Pesquisa de largura : se você estiver em pé na frente de um móvel e algo valioso (por exemplo, uma moeda ou um anel) cair e ficar embaixo do móvel, para que você não possa vê-lo, acene levemente com a mão a partir do ponto em que você viu o objeto desaparecendo. Se você não o encontrar, vá um pouco mais longe e continue assim até encontrá-lo ou perder a paciência. Essa é exatamente a primeira pesquisa em ação: primeiro, você considera todos os locais desconhecidos na profundidade 1, depois na profundidade 2 e assim por diante.

Pesquisa em profundidade : ao procurar algo localizado remotamente ao seu redor, você nunca escolhe o algoritmo mencionado acima e, em vez disso, se compromete com uma direção. Um exemplo é Cristobal Colon comprometendo-se a oeste ao procurar uma rota para os índios. Bem, ele estava errado, mas sabemos disso hoje em dia. Imagine dois pontos tentando uma busca pela primeira vez e movendo-se ao longo de uma espiral de Burgos, onde o contrato entre Reyes Católicos e dois pontos foi assinado. Em vez disso, ele apontou para uma determinada direção sem voltar atrás.

Outro exemplo de um dos meus professores da Universidade (José Cuena, que já faleceu) diz respeito à busca bidirecional : engenheiros, quando constroem túneis nas montanhas, começam de ambos os lados simultaneamente e terminam quando se encontram em algum lugar no meio. O motivo é simples: se eles começarem de um lado, é muito provável que haja um grande desvio no outro lado. Iniciar de ambos os lados minimiza simultaneamente o desvio no ponto de encontro.

$^*$

• A lista aberta é apenas a lista de possibilidades abertas que aguardam consideração. Todos os humanos fazem isso, embora não sejamos tão bons quanto computadores que lembram coisas.
• A lista fechada serve apenas para evitar o raciocínio circular ou o raciocínio contínuo a partir de um ponto que já consideramos antes. Isso acontece se você estiver pensando em voz alta e repetir alguma coisa. Então, alguém perceberá e imediatamente dirá "ei cara, você já disse isso antes"

Uma pergunta muito interessante de alguma forma abordada por outros é se os humanos podem executar algum algoritmo e (ainda mais interessante do meu ponto de vista) se esses algoritmos (ou, em geral, a maneira como construímos a Inteligência Artificial) imitam nossos procedimentos inteligentes naturais.

Você já assistiu uma criança aprendendo a navegar em uma sala? Você deve dizer a eles: "Contorne a mesa. AO REDOR ".

O planejamento do caminho humano é um saco de heurísticas, algumas inatas e outras aprendidas. O Lookahead provavelmente está fixo em um número pequeno, certamente não em uma recursão geral como A *.