Optymalny solver krótkowzrocznego labiryntu

Wygłupiałem się z prezentacją Google Blocky's Maze i przypomniałem sobie starą zasadę, że jeśli chcesz rozwiązać labirynt, trzymaj lewą rękę przy ścianie. Działa to dla każdego prostego połączenia labiryntu i może być zrealizowane przez skończony przetwornik.

Niech nasz robot będzie reprezentowany przez przetwornik z następującymi czynnościami i obserwowalnymi:

Czynności: idź do przodu ( $\uparrow$ ), skręć w lewo ( $\leftarrow$ ), skręć w prawo ( $\rightarrow$ )
Obserwowalne: ściana przed ( $\bot$ ), brak ściany przed ( $\top$ )

Następnie możemy zbudować solver lewostronny jako (przepraszam za mój leniwy rysunek):

przetwornik do rozwiązania labiryntu

Widzenie obserwowalnego spowoduje, że będziemy podążać za odpowiednią krawędzią ze stanu podczas wykonywania akcji związanej z tą krawędzią. Ten automat rozwiąże wszystkie po prostu połączone labirynty, chociaż może zająć trochę czasu po ślepych zaułkach. Nazywamy inny automat lepszym niż jeżeli: $B$ $A$

robi znacznie więcej kroków tylko na skończonej liczbie labiryntów i $B$
wykonuje znacznie mniej kroków (średnio; dla wariantów probabilistycznych) na nieskończonej liczbie labiryntów. $B$

Moje dwa pytania:

Czy istnieje automat skończony lepszy niż ten narysowany powyżej? Co jeśli pozwolimy na przetworniki probabilistyczne?
Czy istnieje skończony automat do rozwiązywania labiryntów, które niekoniecznie są po prostu połączone?

automata finite-automata artificial-intelligence

— Artem Kaznatcheev
źródło

@jmad i ja rozmawialiśmy na czacie na temat tego pytania. Jeśli zastanawiasz się nad pytaniem (zwłaszcza definicje lepszego niż ), polecam sprawdzenie zapisu.

— Artem Kaznatcheev

Nie rozumiem, w jaki sposób to pytanie odnosi się do sztucznej inteligencji (w szczególności nasi agenci nie zmieniają swojego zachowania w danych instancji), ale nie jestem ekspertem w tej dziedzinie.

— Raphael

@Raphael rozwiązywanie labiryntów i wyszukiwanie ścieżek (od przeglądu BFS, DFS, do A * i na oddziałach) to podstawowy program nauczania na wstępnym kursie sztucznej inteligencji. Zgadzam się, jako inteligencja, nie jest to szczególnie ekscytujące, ale jeśli sztuczna inteligencja nauczyła mnie czegokolwiek: większość sztucznej inteligencji to tylko problem z wyszukiwaniem.

— Artem Kaznatcheev

Odpowiedzi:

Jeśli dobrze zrozumiałem pytanie, myślę, że możesz zastosować sztuczkę przyspieszającą, aby uzyskać szybsze automaty na nieskończonej liczbie labiryntów (pod warunkiem, że wyjście znajduje się na jednej z granic): możesz po prostu użyć stanów wewnętrznych do przechowywania skończoną liczbę kroków i rozpoznaj ślepe zaułki jak na rysunku:

wprowadź opis zdjęcia tutaj

$A$

W podobny sposób możesz zakodować skończoną liczbę różnych kształtów o stałym rozmiarze, aby uniknąć ślepych zaułków i przyspieszyć swój automat. W rezultacie nie ma „optymalnego” krótkowzrocznego rozwiązania labiryntu dla prostych labiryntów z wyjściem umieszczonym na granicy.

Sztuczka działa, jeśli wejście znajduje się wewnątrz labiryntu, a także wyjście na granicy; ale jeśli wyjście znajduje się w labiryncie, to nie działa, ponieważ wszystkie miejsca muszą zostać odwiedzone, w tym przypadku twój krótkowzroczny solver jest optymalny.

Oczywiście nie można zastosować tej samej sztuczki do rozwiązywania niełatwo połączonych labiryntów (ale powinno to działać, jeśli istnieje stała górna granica wielkości każdego niepołączonego komponentu).

— Vor
źródło

To fajna sztuczka w przypadku wejścia-wyjścia na granicy (która jest podklasą labiryntów po prostu połączonych). Pokazuje, że w tym ograniczonym przypadku zdefiniowane przeze mnie zamówienie nie ma minimalnych elementów. Nie sądzę jednak, że można go uogólnić na wszystkie proste labirynty (nad którymi pracuje zestaw po lewej stronie).

— Artem Kaznatcheev

@ArtemKaznatcheev: Myślę, że sztuczka działa na labiryntach z wejściem do labiryntu i wyjściem również na granicy. Ponadto działa na (nieskończenie wielu) labiryntach, w których znajduje się submaze takie jak ten na rysunku. Przeredaguję pytanie, aby wyjaśnić tę kwestię.

— Vor

k

$k$

4 k - 1

$4k-1$

Pytanie 1

Myślę, że twoja definicja lepszego jest zbyt ścisła w tym sensie, że skończona jest zbyt restrykcyjna (ale nie mam lepszej definicji).

$R=(R_i)_i$ $R_i$ $i$ $L$ $A_R$ $A_L$ $R$ $L$ $A_R$ $A_L$

$A_R$ $R$ $A_R$

Prawdopodobnie można wykluczyć probabilistyczne przetworniki, ponieważ deterministyczny przetwornik będzie szybszy na tych nieskończonych zestawach labiryntów.

Pytanie 2 (dzięki dyskusji z PO )

Nie. (Źródło: ten przełomowy artykuł Lothara Budacha. Twierdzenie to jest wyraźniej określone w streszczeniu tego artykułu Franka Hoffmanna.)

— jmad
źródło

tak, musielibyśmy zdefiniować niektóre klasy równoważności w labiryntach w ramach standardowych przekształceń (takich jak obroty i odbicia), aby ściana po lewej i po prawej stronie była równoważna. Niestety, twoja sekcja pytania 1 nie odpowiada na moje pierwsze pytanie . Pokazujesz, że istnieją nieporównywalne (w „lepszym niż” częściowym rozwiązaniu) solwery (takie jak lewa i prawa ręka, jeśli nie przyjmujemy żadnych założeń symetrii), ale to nie dowodzi, że nie ma takiego, który jest lepiej niż lewa ręka.

— Artem Kaznatcheev

A

$A$

B

$B$

A \leq B

$A \leq B$

L

$L$

\exists R

$\exists R$

R ≰ L

$R \not\leq L$

L ≰ R

$L \not\leq R$

\forall A

$\forall A$

A ≰ L

$A \not\leq L$

L \leq A

$L \leq A$

@ArtemKaznatcheev: tak, wiem, że to nie odpowiada na pytanie, powinienem być jaśniejszy. Chodzi mi o to, że myślę, że moglibyśmy zastosować to do LH, ale także, że jest zbyt wrażliwy na tego rodzaju łatwo nieskończone zbiory. (Myślę, że tylko wtedy, gdy jest bardzo podobny do (podzbioru) )

\leq

$≤$

A \leq B

$A≤B$

B

$B$

A

$A$

— jmad

Alternatywną definicją, o której mogę pomyśleć, jest poproszenie złych przykładów o kilka (zamiast skończonych); wielomian lub mniejsza (może log?) liczba złych przykładów i wiele: super-wielomian / wykładnicza liczba dobrych przykładów. Ale tak naprawdę pomyślałem, że to było jeszcze bardziej restrykcyjne, ponieważ musi przewyższać na TAK WIELU przykładach.

A

$A$

B

$B$

— Artem Kaznatcheev

@ArtemKaznatcheev: możesz zrobić coś, co zależy od wielkości labiryntu (coś takiego jak ale jest zarówno wątpliwe, jak i niepraktyczne). Możemy kontynuować czat .

# {A (M) < B (M) ∣ | M | \leq n} / # {M ∣ | M | \leq n} = o (1)

$\#\{A(M)<B(M) ∣ |M|≤n\}/\#\{M ∣ |M|≤n\} = o(1)$

— jmad