Jak znaleźć żonę w supermarkecie?

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ść.

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.

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”