¿Cómo encuentro a mi esposa en un supermercado?

27

Si dos personas se pierden en un laberinto, ¿hay algún algoritmo que ambos puedan usar para encontrarse sin haber acordado previamente qué algoritmo usarán?

Creo que hay algunas características que tendrá este algoritmo:

  • Cada persona debe poder derivarlo utilizando una lógica que no haga suposiciones sobre lo que la otra persona está decidiendo, pero como cada persona sabe que la otra está en la misma posición, puede hacer deducciones sobre lo que la otra persona debe decidir.
  • Ambas personas deben derivar un algoritmo idéntico, ya que existe una simetría total en sus situaciones (ninguno de los dos tiene ningún conocimiento sobre la posición inicial del otro, y el laberinto es de un tamaño fijo y ambos están completamente mapeados). Tenga en cuenta que no se requiere que el algoritmo sea determinista: se le permite ser aleatorizado.
jl6
fuente
(Un supermercado puede ser un ejemplo engañosa, ya que hay una zona semi-observables salida.) Ahora bien, si ambos tenían un medio para marcar su camino de una manera que permite a cada uno diga propia de otra , podrían revertir a intervalos triplicando, problemas al comenzar a encontrarse con los propios .
barba gris
77
La respuesta lógica es llamar a su teléfono móvil;)
DavidPostill
2
La respuesta que no es CS es ir a un punto de Schelling . En un supermercado, podría ser, por ejemplo, el mostrador de atención al cliente o la salida. Sin embargo, tenga en cuenta que en la vida humana, los puntos de Schelling a menudo dependen tanto del comportamiento humano y el conocimiento, en lugar del análisis algorítmico de los patrones de conectividad, por lo que la perspectiva de CS realmente no proporciona mucha información cuando hablamos de agentes humanos. ¿Realmente quiere hacer preguntas sobre personas en la vida real, o quiere hacer una pregunta matemática sobre agentes robóticos en un entorno idealizado?
DW

Respuestas:

19

Esto se llama problema de encuentro .

Como el documento: Mobile Agent Rendezvous: una encuesta mencionada, este problema es original propuesto por Alpern: The Rendezvous Search Problem :

Dos astronautas aterrizan en un cuerpo esférico que es mucho más grande que el radio de detección (dentro del cual pueden verse). El cuerpo no tiene una orientación fija en el espacio, ni tiene un eje de rotación, por lo que los astronautas no tienen una noción común de posición o dirección para coordinarse. Dadas las velocidades de marcha de la unidad para ambos astronautas, ¿cómo deben moverse para minimizar el tiempo de reunión T esperado (antes de que entren dentro del radio de detección)?

En la encuesta anterior,

Resumen: Los resultados recientes sobre el problema del encuentro de los agentes móviles en redes distribuidas se analizan con énfasis en describir los diversos enfoques adoptados por los investigadores en la comunidad teórica de la informática.

Cubre tanto "Cita asimétrica" ​​(en la Sección 4) como "Cita simétrica" ​​(en la Sección 5).


Para una cita simétrica, el artículo de Alpern muestra:

Se muestra cómo las simetrías en la región de búsqueda pueden dificultar el proceso al evitar la coordinación basada en conceptos como norte o en sentido horario.

hengxina
fuente
Marcado como mejor, ya que me señala al campo de estudio relevante. Si mi lectura de esta encuesta es correcta, aún no se sabe si existe una solución óptima para el encuentro simétrico.
jl6
-1

En realidad, cualquier esquema preestablecido consistente servirá.

Por ejemplo:

  1. Gire siempre a la izquierda
  2. Si está en un callejón sin salida al giro anterior y gire a la derecha
  3. Uno tendrá que caminar el doble de la velocidad (preestablecida) que el otro (o en términos más teóricos numéricos, las velocidades de los dos agentes deberían ser relativamente primas, o más generalmente ser linealmente independientes).

O incluso más simple

  1. Un agente se queda en el mismo lugar.
  2. Mientras que el otro usa un esquema consistente para explorar el laberinto (por ejemplo, usando un enfoque de hilo de Ariadna ).
  3. Eventualmente, en un tiempo finito, se encontrarán.

Este esquema garantizará que las personas se reúnan eventualmente (pero puede llevar algún tiempo)

¿Por qué? Porque el esquema es consistente para ambos y tampoco conduce a un callejón sin salida. Entonces, dado que el laberinto es finito y está conectado, después de un tiempo finito se encontrarán.

Si el esquema no es consistente, no hay garantía de que se cumplirán, ya que pueden dar lugar a lazos cerrados.

Si tienen la misma velocidad, entonces, dependiendo de la arquitectura del laberinto, por ejemplo, un laberinto cíclico, entonces es posible que siempre puedan estar en puntos antidiaméticos del laberinto, por lo tanto, nunca se encontrarán, aunque el esquema sea consistente.

Está claro a partir de lo anterior que el esquema necesita ser arreglado previamente, pero cualquier esquema consistente previamente arreglado servirá.

De lo contrario, se puede confiar en el análisis probabilístico e inferir que con una gran probabilidad se encontrarán, pero esta probabilidad no es una (es decir, en todos los casos).

También se puede considerar lo contrario del problema de la cita , el problema de evitación donde el objetivo es que los agentes siempre se eviten mutuamente .

La solución al problema de la evitación es que los agentes se reflejen entre sí exactamente. Lo que significa que lo que un agente hace al otro debe reflejar eso. Dado que el problema de evitación también tiene una solución , está claro que las estrategias para el problema de la cita que pueden conducir al comportamiento de reflexión de los agentes no pueden garantizar la solución.

Se puede decir que la estrategia para el problema de evitación es la paralelización (es decir, el punto de divergencia máxima), mientras que la estrategia para el problema de encuentro es la ortogonalidad (es decir, el punto de menor convergencia)

El análisis anterior se puede convertir en un algoritmo aleatorio que no asume roles preestablecidos para los agentes, como los siguientes:

  1. Cada agente lanza una moneda sobre qué papel elegir (por ejemplo, permanecer en el lugar o explorar el laberinto)
  2. Luego proceden como se describe anteriormente.

En promedio, esto llevará a que las personas se reúnan eventualmente, pero no está garantizado en todos los casos.

Si suponemos que los agentes pueden dejar rastros , por ejemplo, etiquetas de su dirección y velocidad (actual). Luego, el otro agente puede usar estos rastros como información para ajustar tanto su propia dirección como su velocidad (ver más abajo).

Este tipo de problema es un ejemplo de optimización global utilizando solo información local . O, en otras palabras, una forma de asignar restricciones globales a restricciones locales . Este problema, más general (que subsume el problema de la cita) se aborda en esta publicación de math.se (y sus referencias) "Métodos para traducir restricciones globales a restricciones locales"

Nikos M.
fuente
"Un agente permanece en el mismo lugar" viola la propiedad de simetría que OP desea. donde ambos agentes siguen la misma estrategia.
AndyG
@AndyG, sí, esta parte se responde a continuación, utilizando una serie de enfoques Además, se responde señalando que la solución no está garantizada en este caso
Nikos M.
1
@NikosM. No creo que sea necesario ningún tipo de sincronización. Uno puede modelar este problema como un escenario de evasión de persecución en el que ambos agentes consideran a los demás como evasores. Existen enfoques probabilísticos para resolver este problema, y ​​en un entorno 3D se puede mostrar la cantidad mínima de perseguidores necesarios para garantizar una captura.
AndyG
1
"Siempre girar a la izquierda" no funciona. Suponga que está en el pasillo 2 y su esposa está en el pasillo 5. Caminará hacia arriba y hacia abajo por los pasillos 2 y 3 (o 1 y 2, dependiendo de la forma en que se enfrentó inicialmente) para siempre, y su esposa caminará hacia arriba y hacia abajo. abajo 5 y 6 (o 4 y 5). Alternativamente, si estás en un pequeño supermercado cuyo gráfico de conectividad es un ciclo, podrías terminar caminando por el ciclo para siempre, en la misma dirección y a la misma velocidad.
David Richerby
1
"Un agente se queda en el mismo lugar, el otro hace otra cosa" no funciona ya que ambos agentes pueden optar por quedarse quietos y esperar al otro para siempre. Si los agentes pueden comunicarse para acordar quién se quedará quieto, también pueden comunicar el hecho de que uno de ellos está parado junto a los plátanos.
David Richerby