Como encontro minha esposa em um supermercado?

27

Se duas pessoas são perdidas em um labirinto, existe um algoritmo que elas podem usar para se encontrarem sem terem acordado previamente qual algoritmo usarão?

Eu acho que existem algumas características que esse algoritmo terá:

  • Cada pessoa deve ser capaz de derivá-la usando uma lógica que não faça suposições sobre o que a outra pessoa está decidindo, mas, como cada pessoa sabe que a outra está na mesma posição, pode fazer deduções sobre o que a outra deve estar decidindo.
  • Um algoritmo idêntico deve ser derivado por ambas as pessoas, pois há simetria total em suas situações (nenhuma delas tem conhecimento sobre a posição inicial da outra e o labirinto é de tamanho fixo e totalmente mapeado por ambas). Observe que não é necessário que o algoritmo seja determinístico: ele pode ser randomizado.
jl6
fonte
(Um supermercado pode ser um exemplo enganoso, pois há uma área semi-observável saída.) Agora, se ambos tinham um meio para marcar seu caminho de uma maneira que permite a cada um dizer própria de outra , eles poderiam reverter em intervalos triplicando, problemas começando ao encontrar o próprio .
22816
7
A resposta lógica é chamar seu telefone móvel;)
DavidPostill
2
A resposta que não é CS é ir para um ponto de Schelling . Em um supermercado, isso pode ser, por exemplo, o balcão de atendimento ao cliente ou a saída. Observe, no entanto, que na vida humana, os pontos de Schelling geralmente dependem tanto do comportamento e do conhecimento humano, e não da análise algorítmica dos padrões de conectividade, de modo que a perspectiva do CS não fornece muita percepção quando se trata de agentes humanos. Você realmente quer perguntar sobre as pessoas na vida real ou quer fazer uma pergunta matemática sobre agentes robóticos em um ambiente idealizado?
DW

Respostas:

19

Isso é chamado de problema de encontro .

Como o artigo: Mobile Agent Rendezvous: Uma pesquisa mencionada, esse problema é original proposto por Alpern: The Rendezvous Search Problem :

Dois astronautas pousam em um corpo esférico muito maior que o raio de detecção (dentro do qual eles podem se ver). O corpo não possui orientação fixa no espaço, nem possui eixo de rotação, de modo que nenhuma noção comum de posição ou direção esteja disponível para os astronautas para coordenação. Dadas as velocidades unitárias de marcha para os dois astronautas, como eles devem se mover para minimizar o tempo esperado de reunião T (antes que cheguem ao raio de detecção)?

No documento de pesquisa acima,

Resumo: Resultados recentes sobre o problema do encontro de agentes móveis em redes distribuídas são pesquisados, com ênfase no esboço das várias abordagens adotadas por pesquisadores da comunidade teórica da ciência da computação.

Ele abrange "Encontro assimétrico" (na seção 4) e "Encontro simétrico" (na seção 5).


Para o encontro simétrico, o artigo de Alpern mostra:

É mostrado como as simetrias na região de pesquisa podem dificultar o processo, impedindo a coordenação com base em conceitos como norte ou horário.

hengxin
fonte
Marcado da melhor maneira que isso me aponta para o campo de estudo relevante. Se minha leitura desta pesquisa está correta, ainda não se sabe se existe uma solução ideal para o encontro simétrico.
jl6
-1

Na verdade, qualquer esquema pré-arranjado consistente servirá.

Por exemplo:

  1. Vire sempre à esquerda
  2. Se estiver em um beco sem saída para a curva anterior e vire à direita
  3. Um terá que caminhar o dobro da velocidade (pré-arranjada) do outro (ou em termos mais teóricos dos números, as velocidades dos dois agentes devem ser relativamente primárias ou, geralmente, linearmente independentes).

Ou ainda mais simples

  1. Um agente permanece no mesmo local
  2. Enquanto o outro usa um esquema consistente para explorar o labirinto (por exemplo, usando uma abordagem de fio de Ariadne ).
  3. Eventualmente, em tempo finito, eles se encontrarão.

Esse esquema garantirá que as pessoas se encontrem eventualmente (mas pode levar algum tempo)

Por quê? Porque o esquema é consistente para ambos e não leva a um beco sem saída. Então, como o labirinto é finito e está conectado, depois de um tempo finito, eles se encontrarão.

Se o esquema não for consistente, não há garantia de que eles atendam, pois podem resultar em loops fechados.

Se eles tiverem a mesma velocidade, dependendo da arquitetura do labirinto, por exemplo, um labirinto cíclico, é possível que eles sempre estejam em pontos anti-diamétricos do labirinto e, portanto, nunca se encontrem, mesmo que o esquema seja consistente.

Fica claro pelo exposto acima que o esquema precisa ser pré-arranjado, mas qualquer esquema pré-arranjado consistente será necessário.

Caso contrário, pode-se confiar na análise probabilística e inferir que, com uma grande probabilidade, eles se encontrarão, mas essa probabilidade não é uma (ou seja, em todos os casos).

Pode-se também considerar o inverso do problema do encontro , o problema da prevenção, onde o objetivo é que os agentes sempre se evitem .

A solução para o problema da prevenção é que os agentes se reflitam exatamente. Significando que o que um agente faz o outro deve refletir isso. Como o problema de esquiva também tem uma solução , fica claro que estratégias para o problema de encontro que podem levar ao comportamento de reflexão dos agentes não podem garantir solução.

Pode-se dizer que a estratégia para o problema da prevenção é a paralelização (ou seja, ponto divergente máximo) enquanto a estratégia para o problema do encontro é a ortogonalidade (ou seja, ponto menos convergente)

A análise acima pode ser transformada em um algoritmo aleatório que não assume funções pré-organizadas para os agentes, como o seguinte:

  1. Cada agente joga uma moeda sobre qual papel escolher (por exemplo, permanecer no local ou explorar o labirinto)
  2. Então eles procedem como descrito acima.

Em média, isso levará as pessoas a se encontrarem, mas não é garantido em todos os casos.

Se assumirmos que os agentes podem deixar rastros , por exemplo, rótulos de sua direção (atual) e velocidade. Em seguida, o outro agente pode usar esses rastreamentos como informações para ajustar sua própria direção e velocidade (veja abaixo).

Esse tipo de problema é um exemplo de otimização global usando apenas informações locais . Ou, em outras palavras, uma maneira de mapear restrições globais para restrições locais . Esse problema mais geral (que inclui o problema de encontro) é abordado neste post do math.se (e suas referências) "Métodos para converter restrições globais em restrições locais"

Nikos M.
fonte
"Um agente permanece no mesmo local" viola a propriedade de simetria que o OP deseja. onde os dois agentes seguem a mesma estratégia.
AndyG
@AndyG, sim esta parte é respondida abaixo, usando um número de abordagens Além disso, ele é respondida por referir que a solução não é garantida neste caso
Nikos M.
11
@NikosM. Não acredito que seja necessário nenhum tipo de sincronização. Pode-se modelar esse problema como um cenário de evasão de perseguição, em que ambos os agentes consideram os outros um evasor. Existem abordagens probabilísticas para resolver esse problema e, em um ambiente 3D, é possível mostrar o número mínimo de perseguidores necessários para garantir uma captura.
precisa saber é o seguinte
11
"Sempre vire à esquerda" não funciona. Suponha que você esteja no corredor 2 e sua esposa no corredor 5. Você andará para cima e para baixo nos corredores 2 e 3 (ou 1 e 2, dependendo do caminho em que estava inicialmente) para sempre, e sua esposa andará para cima e para baixo. 5 e 6 (ou 4 e 5). Como alternativa, se você estiver em um pequeno supermercado cujo gráfico de conectividade é um ciclo, você pode acabar andando pelo ciclo para sempre, na mesma direção e na mesma velocidade.
precisa saber é o seguinte
11
"Um agente fica no mesmo lugar, o outro faz outra coisa" não funciona, pois os dois podem decidir ficar quietos e esperar o outro para sempre. Se os agentes puderem se comunicar para concordar com quem ficará parado, eles também poderão comunicar o fato de que um deles está de pé junto às bananas.
precisa saber é o seguinte