Jak znaleźć żonę w supermarkecie?

27

Jeśli w labiryncie zagubiły się dwie osoby, czy istnieje algorytm, którego oboje mogą użyć do znalezienia siebie nawzajem bez uprzedniego uzgodnienia, jakiego algorytmu będą używać?

Myślę, że ten algorytm ma pewne cechy:

  • Każda osoba musi być w stanie wyprowadzić ją za pomocą logiki, która nie przyjmuje żadnych założeń na temat tego, co druga osoba decyduje, ale ponieważ każda osoba wie, że druga osoba jest w tej samej pozycji, może dokonywać dedukcji na temat tego, co druga musi decydować.
  • Identyczny algorytm musi być wyprowadzony przez obie osoby, ponieważ w ich sytuacjach występuje całkowita symetria (żadna nie ma żadnej wiedzy na temat pozycji początkowej drugiej, a labirynt ma ustalony rozmiar i jest w pełni zmapowany przez obie). Należy pamiętać, że algorytm nie musi być deterministyczny: dopuszcza się losowość.
jl6
źródło
(Supermarket może być mylące przykład, jak tam jest pół-obserwowalny obszar zjazd). Teraz, jeśli obaj mieli środki zaznaczyć swoją ścieżkę w sposób, który pozwala każdemu powiedzieć własny od innych , mogliby odwrócić na trzykrotne odstępach czasu, problemy z uruchomieniem po napotkaniu własnego .
siwobrody
7
Logiczną odpowiedzią jest zadzwonienie na jej telefon komórkowy;)
DavidPostill
2
Odpowiedzią inną niż CS jest przejście do punktu Schellinga . W supermarkecie może to być np. Biuro obsługi klienta lub wyjście. Zauważ jednak, że w życiu ludzkim punkty Schellinga często zależą w większym stopniu od ludzkiego zachowania i wiedzy, a nie od algorytmicznej analizy wzorców połączeń, więc perspektywa CS nie zapewnia tak naprawdę wglądu, gdy mówimy o ludzkich agentach. Czy naprawdę chcesz zapytać o ludzi w prawdziwym życiu, czy może zadajesz matematyczne pytanie na temat robotów w wyidealizowanym otoczeniu?
DW

Odpowiedzi:

19

Nazywa się to problemem spotkania .

Jako artykuł: Mobile Agent Rendezvous: Wspomniane badanie , ten problem został pierwotnie zaproponowany przez Alpern: Problem wyszukiwania Rendezvous :

Dwóch astronautów ląduje na kulistym ciele, które jest znacznie większe niż promień wykrywania (w obrębie którego mogą się widzieć). Ciało nie ma ustalonej orientacji w przestrzeni, ani nie ma osi obrotu, więc astronauci nie mają wspólnego pojęcia pozycji ani kierunku do koordynacji. Biorąc pod uwagę prędkości poruszania się jednostki dla obu astronautów, jak powinni się poruszać, aby zminimalizować oczekiwany czas spotkania T (zanim znajdą się w promieniu wykrywania)?

W powyższym artykule ankietowym

Streszczenie: Ostatnie wyniki dotyczące problemu spotkania agenta mobilnego w sieciach rozproszonych są badane z naciskiem na nakreślenie różnych podejść badaczy z teoretycznej społeczności informatycznej.

Obejmuje on zarówno „Asymetryczne rendez-vous” (w rozdziale 4), jak i „Symetryczne rendez-vous” (w rozdziale 5).


W przypadku symetrycznego spotkania spotkanie Alpern pokazuje:

Pokazano, w jaki sposób symetrie w obszarze wyszukiwania mogą utrudniać proces, uniemożliwiając koordynację opartą na pojęciach takich jak północ lub zgodnie z ruchem wskazówek zegara.

hengxin
źródło
Oznaczone jako najlepsze, ponieważ wskazuje mi odpowiedni kierunek studiów. Jeśli moje czytanie tej ankiety jest słuszne, nie wiadomo jeszcze, czy istnieje optymalne rozwiązanie symetrycznego spotkania.
jl6
-1

Właściwie zrobi to każdy spójny, wstępnie ustalony schemat.

Na przykład:

  1. Skręć zawsze w lewo
  2. Jeśli jesteś w ślepym zaułku, cofnij się do poprzedniego zakrętu i skręć w prawo
  3. Będziesz musiał przejść podwójną (wcześniej ustaloną) prędkość w stosunku do drugiej (lub bardziej teoretycznie liczbowo, prędkości dwóch czynników powinny być względnie pierwsze, lub bardziej ogólnie liniowo niezależne).

Lub nawet prościej

  1. Jeden agent pozostaje w tym samym miejscu
  2. Podczas gdy drugi używa spójnego schematu do eksploracji labiryntu (np. Używając podejścia nitkowego Ariadny ).
  3. W końcu, w skończonym czasie się spotkają.

Ten program zagwarantuje, że ludzie się spotkają (ale może to zająć trochę czasu)

Czemu? Ponieważ schemat jest spójny dla obu i nie prowadzi do ślepej uliczki. Ponieważ labirynt jest skończony i połączony, po skończonym czasie się spotkają.

Jeśli schemat nie jest spójny, nie ma gwarancji, że spełnią, ponieważ mogą doprowadzić do zamkniętych pętli.

Jeśli mają tę samą prędkość, to w zależności od architektury labiryntu, np. Labiryntu cyklicznego, możliwe jest, że zawsze znajdą się w punktach antydymetrycznych labiryntu, a zatem nigdy się nie spotkają, mimo że schemat jest spójny.

Z powyższego jasno wynika, że ​​program musi być wstępnie ustalony, ale zrobi to każdy spójny wstępnie ustalony schemat.

W przeciwnym razie można polegać na analizie probabilistycznej i wnioskować, że z dużym prawdopodobieństwem się spełnią, ale prawdopodobieństwo to nie jest jedno (tj. We wszystkich przypadkach).

Można również rozważyć coś przeciwnego do zbornego problemu , z problemu unikania gdzie celem jest dla agentów zawsze unikać siebie .

Rozwiązaniem problemu unikania jest dokładne odzwierciedlenie siebie przez agentów. Oznacza to, że to, co robi jeden agent drugi, powinno to odzwierciedlać. Ponieważ problem unikania ma również rozwiązanie , jasne jest, że strategie dla problemu spotkania, które mogą prowadzić do refleksyjnych zachowań agentów, nie mogą zagwarantować rozwiązania.

Można powiedzieć, że strategią problemu unikania jest równoległość (tj. Maksymalny punkt rozbieżności), podczas gdy strategią problemu spotkania jest ortogonalność (tzn. Najmniej zbieżny punkt)

Powyższą analizę można przekształcić w algorytm losowy, który nie przyjmuje wstępnie ustalonych ról dla agentów, takich jak:

  1. Każdy agent rzuca monetą, którą rolę wybrać (np. Pozostanie na miejscu lub eksploracja labiryntu)
  2. Następnie postępują jak opisano powyżej.

To średnio doprowadzi do spotkania ludzi, ale nie jest to zagwarantowane we wszystkich przypadkach.

Jeśli założymy, że agenci mogą pozostawić ślady , np. Etykiety ich (bieżącego) kierunku i prędkości. Następnie drugi agent może wykorzystać te ślady jako informacje do dostosowania zarówno własnego kierunku, jak i prędkości (patrz poniżej).

Ten rodzaj problemu jest przykładem globalnej optymalizacji wykorzystującej tylko informacje lokalne . Innymi słowy, sposób mapowania globalnych ograniczeń na lokalne . Ten bardziej ogólny problem (który obejmuje problem spotkania) jest omawiany w tym poście math.se (i odnośnikach) „Metody przełożenia globalnych ograniczeń na lokalne”

Nikos M.
źródło
„Jeden agent zostaje w tym samym miejscu” narusza właściwość symetrii, której chce OP. gdzie obaj agenci stosują tę samą strategię.
AndyG
@AndyG, tak, na tę część odpowiedziano poniżej, stosując szereg podejść Plus, odpowiada się, zauważając, że rozwiązanie nie jest gwarantowane w tym przypadku
Nikos M.
1
@NikosM. Nie sądzę, aby jakakolwiek synchronizacja była konieczna. Można modelować ten problem jako scenariusz pościgu, w którym obaj agenci uważają innych za oszustów. Istnieją probabilistyczne podejścia do rozwiązania tego problemu, aw środowisku 3D można pokazać minimalną liczbę prześladowców wymaganych do zagwarantowania przechwytywania.
AndyG
1
„Zawsze skręcaj w lewo” nie działa. Załóżmy, że jesteś na przejściu 2, a twoja żona jest na przejściu 5. Będziesz chodził w górę i w dół do przejść 2 i 3 (lub 1 i 2, w zależności od tego, w którą stronę początkowo się zmierzałeś) na zawsze, a twoja żona będzie chodzić i w dół 5 i 6 (lub 4 i 5). Alternatywnie, jeśli jesteś w małym supermarkecie, którego grafem połączeń jest cykl, możesz po prostu chodzić po całym cyklu na zawsze, w tym samym kierunku i z tą samą prędkością.
David Richerby
1
„Jeden agent pozostaje w tym samym miejscu, drugi robi coś innego” nie działa, ponieważ obaj agenci mogą zdecydować się pozostać w miejscu i czekać na drugiego na zawsze. Jeśli agenci mogą się porozumieć w celu uzgodnienia, kto będzie stać w miejscu, równie dobrze mogą poinformować fakt, że jeden z nich stoi przy bananach.
David Richerby