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

11

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?

DorkRawk
fonte
3
Os seres humanos podem usar o algoritmo A * pathfinding ... Quero dizer, um algoritmo é apenas uma técnica, certo? Não acho que exista algum algoritmo que um ser humano não possa executar. Suponho que estou tentando entender é que você provavelmente deve ser muito mais claro em termos do que constitui "o processo que os humanos usam em diferentes situações de busca de caminhos". Eu não acho que alguém possa lhe dar uma resposta significativa até você dizer como os humanos realmente fazem isso ... o que provavelmente é problemático no caso geral, e parece ser difícil aqui também.
Patrick87
Além disso, explique em breve o que A * faz e / ou vincula a uma referência. E bem-vindo!
Raphael
@ Patrick87 Certamente os humanos PODEM fazer qualquer algoritmo, mas essa não é uma pergunta muito interessante. O que eu estava tentando entender era como os algoritmos de busca de caminhos se comparam às técnicas usadas pelos humanos quando deixados para resolver um problema por conta própria (sem conhecimento prévio dos algoritmos de busca de caminhos).
DorkRawk
3
Existem estudos sobre o comportamento humano nessas situações: uma resposta razoável pode apontar para estudos reais de como os seres humanos descobrem o caminho.
Suresh
2
Os seres humanos realmente não se dão muito bem com gráficos de milhões de nós, especialmente dados como listas de adjacência, mas funciona bem. (Em outras palavras: como os seres humanos fazem o que exatamente?)A
Jeffe

Respostas:

6

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.

om-nom-nom
fonte
Você pode dizer que a última abordagem é o caminho mais curto apenas para iniciar uma aproximação aproximada do gráfico e refinar o gráfico à medida que avança?
Raphael
@Raphael Sim, na verdade é uma descrição do que as Hierarquias de Contação (há também uma etapa de pré-processamento, que pega o gráfico e o colapta na hierarquia com diferentes níveis de detalhes) fazem e simultaneamente do que eu farei como ser humano
om-nom -nom
4

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.

Carlos Linares López
fonte
O artigo mencionado por Carlos pode ser lido aqui: svn.sable.mcgill.ca/sable/courses/COMP763/oldpapers/…
TFerrell
-2

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 *.

Trevor Blackwell
fonte
1
Essas respostas contêm apenas especulações.
Raphael