Wyszukiwanie lokalne online

Podobnie jak wyszukiwanie w głąb, wyszukiwanie ze wspinaczką ma właściwość lokalizacji w rozwinięciach węzłów. W rzeczywistości, ponieważ przechowuje tylko jeden aktualny stan w pamięci, wyszukiwanie wspinaczkowe jest już algorytmem wyszukiwania online! Niestety podstawowy algorytm nie jest zbyt dobry do eksploracji, ponieważ pozostawia agenta siedzącego na lokalnych maksimach bez miejsca, do którego mógłby się udać. Ponadto nie można używać losowych restartów, ponieważ agent nie może teleportować się do nowego stanu startowego. Zamiast losowych restartów, można rozważyć skorzystanie z przypadkowego spaceru w celu zbadania otoczenia. Spacer losowy po prostu wybiera losowo jedną z dostępnych akcji z bieżącego stanu; pierwszeństwo mogą mieć działania, które nie zostały jeszcze wypróbowane. Łatwo jest udowodnić, że losowy spacer w końcu znajdzie cel lub dokończy jego eksplorację, pod warunkiem, że przestrzeń jest skończona i bezpieczna do eksploracji. Z drugiej strony proces może być bardzo powolny. Rysunek  pokazuje środowisko, w którym błądzenie losowe wymaga wykładniczo wielu kroków, aby znaleźć cel, ponieważ dla każdego stanu w górnym wierszu z wyjątkiem S, postęp wstecz jest dwa razy bardziej prawdopodobny niż postęp w przód. Przykład jest oczywiście wymyślony, ale istnieje wiele rzeczywistych przestrzeni stanów, których topologia powoduje tego rodzaju „pułapki” na losowe spacery.

Wspinanie się po wzgórzach za pomocą pamięci, a nie przypadkowości, okazuje się bardziej skutecznym podejściem. Podstawowym pomysłem jest przechowywanie „aktualnego najlepszego oszacowania” H(ów) kosztów, aby osiągnąć cel z każdego odwiedzonego stanu. H(s) zaczyna być tylko oszacowaniem heurystycznym h(s) i jest aktualizowane, gdy agent zdobywa doświadczenie w przestrzeni stanów. Rysunek pokazuje prosty przykład w jednowymiarowej przestrzeni stanów. W (a) agent wydaje się utknąć w płaskim lokalnym minimum w stanie czerwonym. Zamiast pozostawać tam, gdzie jest, agent powinien podążać drogą, która wydaje się być najlepszą ścieżką do celu, biorąc pod uwagę aktualne szacunki kosztów dla sąsiadów. Szacowany koszt dotarcia do celu przez sąsiada s’ to koszt dotarcia do s’ plus szacowany koszt dotarcia do celu stamtąd, czyli .c(s,a,s’) + H(s’ ) . W tym przykładzie są dwie akcje, z szacowanymi kosztami po lewej i po prawej stronie, więc wydaje się, że najlepiej przejść w prawo.

W punkcie (b) wyraźnie widać, że szacunek kosztów 2 dla stanu czerwonego w punkcie (a) był zbyt optymistyczny. Ponieważ najlepszy ruch kosztował 1 i doprowadził do stanu, który jest co najmniej 2 kroki od celu, czerwony stan musi znajdować się co najmniej 3 kroki od celu, więc jego H należy odpowiednio zaktualizować, jak pokazano na rysunku (b). . Kontynuując ten proces, agent będzie się jeszcze dwa razy poruszał tam i z powrotem, za każdym razem aktualizując H i „spłaszczając” lokalne minimum, aż ucieknie w prawo.

Agenta realizującego ten schemat, który nazywa się uczeniem się A* w czasie rzeczywistym (LRTA*), pokazano na rysunku. Podobnie jak ONLINE-DFS-AGENT, buduje mapę środowiska w tabeli wyników. Aktualizuje oszacowanie kosztów dla stanu, który właśnie opuścił, a następnie wybiera „najwyraźniej najlepszy” ruch zgodnie z aktualnymi szacunkami kosztów. Ważnym szczegółem jest to, że zakłada się, że działania, które nie zostały jeszcze wypróbowane w danym stanie, prowadzą natychmiast do celu przy możliwie najmniejszych kosztach, czyli h(s). Ten optymizm w warunkach niepewności skłania agenta do poszukiwania nowych, potencjalnie obiecujących ścieżek.

Agent LRTA* gwarantuje znalezienie celu w każdym ograniczonym, bezpiecznym środowisku. Jednak w przeciwieństwie do A*, nie jest ona zupełna dla nieskończonych przestrzeni stanów — są przypadki, w których może być wyprowadzona na nieskończenie błąd. W najgorszym przypadku może badać środowisko składające się z n stanów w krokach O(n2), ale często działa znacznie lepiej. Agent LRTA* jest tylko jednym z dużej rodziny agentów online, które można zdefiniować, określając na różne sposoby regułę wyboru akcji i regułę aktualizacji. Omawiamy tę rodzinę, opracowaną pierwotnie dla środowisk stochastycznych

Agenci wyszukiwania online

Po każdej akcji agent online w obserwowalnym środowisku otrzymuje percept informujący go, jaki stan osiągnął; na podstawie tych informacji może uzupełnić swoją mapę środowiska. Zaktualizowana mapa jest następnie wykorzystywana do planowania dalszych kroków. To przeplatanie się planowania i działania oznacza, że ​​algorytmy wyszukiwania online różnią się znacznie od algorytmów wyszukiwania offline, które widzieliśmy wcześniej: algorytmy offline eksplorują swój model przestrzeni stanów, podczas gdy algorytmy online eksplorują świat rzeczywisty. Na przykład A* może rozwinąć węzeł w jednej części przestrzeni, a następnie natychmiast rozwinąć węzeł w odległej części przestrzeni, ponieważ rozwinięcie węzła obejmuje działania symulowane, a nie rzeczywiste. Z drugiej strony algorytm online może odkryć następców tylko dla stanu, który fizycznie zajmuje. Aby uniknąć podróżowania aż do stanu odległego w celu rozszerzenia następnego węzła, wydaje się, że lepiej jest rozszerzać węzły w kolejności lokalnej. Wyszukiwanie według głębokości ma dokładnie tę właściwość, ponieważ (z wyjątkiem sytuacji, gdy algorytm cofa) następny rozwinięty węzeł jest potomkiem poprzedniego rozwiniętego węzła. Internetowy agent eksploracji w głąb (dla deterministycznych, ale nieznanych działań) pokazano na rysunku. Ten agent przechowuje swoją mapę w tabeli result[s,a], która rejestruje stan wynikający z wykonania akcji w state s. (W przypadku działań niedeterministycznych agent może zarejestrować zestaw stanów w wyniku[s,a].) Zawsze, gdy bieżący stan zawiera niezbadane działania, agent próbuje wykonać jedną z nich. Trudność pojawia się, gdy agent wypróbował wszystkie działania w stanie. W trybie wyszukiwania głębokiego offline stan jest po prostu usuwany z kolejki; w wyszukiwarce online agent musi cofnąć się do świata fizycznego. W wyszukiwaniu dogłębnym oznacza to powrót do stanu, z którego agent ostatnio wszedł w obecny stan. Aby to osiągnąć, algorytm przechowuje kolejną tabelę, która dla każdego stanu zawiera poprzednie stany, do których agent jeszcze się nie cofnął. Jeśli agentowi zabrakło stanów, do których może się cofnąć, wyszukiwanie jest zakończone.

Zalecamy czytelnikowi prześledzenie postępu ONLINE-DFS-AGENT po zastosowaniu go w labiryncie przedstawionym na rysunku powyżej. Dość łatwo zauważyć, że w najgorszym przypadku agent przejdzie przez każde łącze w przestrzeni stanów dokładnie dwa razy. W przypadku eksploracji jest to optymalne; z drugiej strony, jeśli chodzi o znalezienie celu, współczynnik konkurencyjności agenta może być arbitralnie zły, jeśli wyrusza na długą wycieczkę, gdy cel znajduje się tuż obok stanu początkowego. Internetowy wariant pogłębiania iteracyjnego rozwiązuje ten problem; dla środowiska, które jest drzewem jednorodnym, stosunek konkurencyjności takiego agenta jest małą stałą. Ze względu na metodę cofania, ONLINE-DFS-AGENT działa tylko w przestrzeniach stanów, w których akcje są odwracalne. Istnieją nieco bardziej złożone algorytmy, które działają w ogólnych przestrzeniach stanów, ale żaden taki algorytm nie ma ograniczonego współczynnika konkurencyjności.

Problemy z wyszukiwaniem online

Problem wyszukiwania online jest rozwiązywany przez przeplatanie obliczeń, wykrywania i działania. Zaczniemy od założenia deterministycznego i w pełni obserwowalnego środowiska (rozdział 17 rozluźnia te założenia) i zastrzeżemy, że agent wie tylko:

* DZIAŁANIA, czynności prawne w stanie;

* c(s,a,s’) , koszt zastosowania akcji w stanie s, aby dojść s’ do stanu . Zauważ, że nie można tego użyć, dopóki agent nie wie, że wynikiem jest s’.

* Is-GOAL(s), test celu.

W szczególności należy zauważyć, że agent nie może określić WYNIKU(ów, a) z wyjątkiem faktycznego przebywania i wykonywania . Na przykład w problemie labiryntu pokazanym na rysunku , agent nie wie, że przejście w górę z (1,1) prowadzi do (1,2); ani po zrobieniu tego nie wie, że zejście w dół spowoduje powrót do (1,1). Ten stopień ignorancji można zmniejszyć w niektórych zastosowaniach – na przykład eksplorator robota może wiedzieć, jak działają jego ruchy i nie znać tylko lokalizacji przeszkód.

Wreszcie agent może mieć dostęp do dopuszczalnej funkcji heurystycznej h(s), która szacuje odległość od stanu bieżącego do stanu docelowego. Na przykład na rysunku powyżej agent może znać lokalizację celu i być w stanie użyć heurystyki odległości Manhattan . Zazwyczaj celem agenta jest osiągnięcie stanu docelowego przy minimalizacji kosztów. (Innym możliwym celem jest po prostu zbadanie całego środowiska). Koszt to całkowity koszt ścieżki, który agent ponosi podczas podróży. Często porównuje się ten koszt z kosztem ścieżki, jaki poniósłby agent, gdyby znał z góry przestrzeń wyszukiwania — to znaczy optymalną ścieżkę w znanym środowisku. W języku algorytmów internetowych porównanie to nazywa się współczynnikiem konkurencyjności; chcielibyśmy, aby był jak najmniejszy. Odkrywcy online są narażeni na ślepe zaułki: stany, z których żaden stan docelowy nie jest osiągalny. Jeśli agent nie wie, co robi każda akcja, może wykonać akcję „skoku w bezdenną otchłań”, a tym samym nigdy nie osiągnąć celu. Ogólnie rzecz biorąc, żaden algorytm nie może uniknąć ślepych zaułków we wszystkich przestrzeniach stanów. Rozważmy dwie martwe przestrzenie stanów na rysunku (a) . Algorytm wyszukiwania online, który odwiedził stany A i S, nie może stwierdzić, czy jest w stanie górnym, czy dolnym; oba wyglądają identycznie w zależności od tego, co widział agent. Dlatego nie może wiedzieć, jak wybrać właściwą akcję w obu przestrzeniach stanów. Jest to przykład argumentu adwersarza — możemy sobie wyobrazić przeciwnika konstruującego przestrzeń stanów, podczas gdy agent ją bada i umieszcza cele i ślepe zaułki, gdziekolwiek chce, jak na rysunku (b).

Ślepe zaułki są prawdziwym utrudnieniem dla eksploracji robotów – klatki schodowe, rampy, klify, ulice jednokierunkowe, a nawet naturalny teren – wszystkie obecne stany, z których niektóre działania są nieodwracalne – nie ma możliwości powrotu do poprzedniego stanu. Algorytm eksploracji, który przedstawimy, gwarantuje działanie tylko w przestrzeniach stanów, które można bezpiecznie eksplorować — to znaczy, że pewien stan docelowy jest osiągalny z każdego stanu osiągalnego. Przestrzenie stanów, w których występują tylko akcje odwracalne, takie jak labirynty i 8 zagadek, są wyraźnie bezpiecznie eksplorowane (jeśli w ogóle mają jakieś rozwiązanie). Temat bezpiecznej eksploracji omówimy bardziej szczegółowo w sekcji 22.3.2. Nawet w środowiskach, w których można bezpiecznie eksplorować, nie można zagwarantować żadnego ograniczonego współczynnika konkurencyjności, jeśli istnieją ścieżki o nieograniczonych kosztach. Łatwo to pokazać w środowiskach z nieodwracalnymi działaniami, ale w rzeczywistości pozostaje to również prawdziwe w przypadku odwracalnym, jak pokazuje Rysunek 4.20(b). Z tego powodu często charakteryzuje się wydajność algorytmów wyszukiwania online pod kątem rozmiaru całej przestrzeni stanów, a nie tylko głębokości najpłytszego celu.

Agenci wyszukiwania online i nieznane środowiska

Do tej pory koncentrowaliśmy się na agentach korzystających z algorytmów wyszukiwania offline. Obliczają kompletne rozwiązanie przed podjęciem pierwszego działania. W przeciwieństwie do tego, internetowy agent wyszukiwania przeplata obliczenia i działanie: najpierw wykonuje działanie, następnie obserwuje środowisko i oblicza następne działanie. Wyszukiwanie online jest dobrym pomysłem w środowiskach dynamicznych lub półdynamicznych, gdzie kara za zbyt długie siedzenie i korzystanie z komputera. Wyszukiwanie online jest również pomocne w domenach niedeterministycznych, ponieważ pozwala agentowi skoncentrować swoje wysiłki obliczeniowe na zdarzeniach, które faktycznie się pojawiają, a nie na tych, które mogą się zdarzyć, ale prawdopodobnie nie nastąpią. Oczywiście jest kompromis: im więcej agent planuje z wyprzedzeniem, tym rzadziej znajdzie się w strumieniu bez wiosła. W nieznanych środowiskach, w których agent nie wie, jakie stany istnieją ani co robią jego działania, agent musi wykorzystać swoje działania jako eksperymenty, aby poznać środowisko. Kanonicznym przykładem wyszukiwania online jest problem z mapowaniem: robot jest umieszczany w nieznanym budynku i musi zbadać, aby zbudować mapę, która może być później wykorzystana do dostania się z do . Metody ucieczki z labiryntów – wiedza wymagana dla aspirujących bohaterów starożytności – to także przykłady algorytmów wyszukiwania w sieci. Eksploracja przestrzenna nie jest jednak jedyną formą eksploracji online. Rozważmy noworodka: ma wiele możliwych działań, ale nie zna skutków żadnego z nich i doświadczyło tylko kilku możliwych stanów, które może osiągnąć.

Agent dla środowisk częściowo obserwowalnych

Agent dla środowisk częściowo obserwowalnych formułuje problem, wywołuje algorytm wyszukiwania (taki jak AND-LUB-SEARCH) w celu jego rozwiązania i wykonuje rozwiązanie. Istnieją dwie główne różnice między tym agentem a tym dla w pełni obserwowalnych środowisk deterministycznych. Po pierwsze, rozwiązaniem będzie plan warunkowy, a nie sekwencja; aby wykonać wyrażenie if-then-else, agent będzie musiał przetestować warunek i wykonać odpowiednią gałąź warunku. Po drugie, agent będzie musiał utrzymać swój stan wiary podczas wykonywania działań i odbierania percepcji. Proces ten przypomina proces przewidywania-obserwacji-aktualizacji w równaniu ), ale w rzeczywistości jest prostszy, ponieważ percepcja jest przekazywana przez środowisko, a nie obliczana przez agenta. Biorąc pod uwagę początkowy stan przekonań , działanie i percepcję , nowy stan przekonań to:

Rozważmy przedszkolny świat próżni, w którym agenci wyczuwają tylko stan swojego obecnego placu, a każdy plac może się zabrudzić w dowolnym momencie, chyba że agent aktywnie go czyści w danym momencie. Rysunek przedstawia stan przekonania utrzymywany w tym środowisku.

W środowiskach częściowo obserwowalnych – które obejmują zdecydowaną większość środowisk świata rzeczywistego – utrzymywanie własnego stanu wiary jest podstawową funkcją każdego inteligentnego systemu. Ta funkcja nosi różne nazwy, w tym monitorowanie, filtrowanie i estymację stanu. Równanie powyższe nazywa się rekurencyjnym estymatorem stanu, ponieważ oblicza nowy stan przekonania z poprzedniego, a nie przez badanie całej sekwencji percepcji. Jeśli agent nie ma „zostać w tyle”, obliczenia muszą odbywać się tak szybko, jak pojawiają się spostrzeżenia. Gdy środowisko staje się bardziej złożone, agent będzie miał tylko czas na obliczenie przybliżonego stanu przekonań, być może skupiając się na implikacjach postrzeganie aspektów środowiska będących przedmiotem bieżącego zainteresowania. Większość prac nad tym problemem została wykonana dla stochastycznych środowisk o stanie ciągłym za pomocą narzędzi teorii prawdopodobieństwa

W częściowo obserwowalnych środowiskach — które obejmują zdecydowaną większość rzeczywistych środowisk — utrzymywanie własnego stanu wiary jest podstawową funkcją każdego inteligentnego systemu. Ta funkcja nosi różne nazwy, w tym monitorowanie, filtrowanie i estymację stanu. Równanie powyższe jest nazywane rekurencyjnym estymatorem stanu, ponieważ oblicza nowy stan przekonania z poprzedniego, a nie przez badanie całej sekwencji percepcji. Jeśli agent nie ma „zostać w tyle”, obliczenia muszą odbywać się tak szybko, jak pojawiają się spostrzeżenia. Gdy środowisko staje się bardziej złożone, agent będzie miał tylko czas na obliczenie przybliżonego stanu przekonań, być może skupiając się na implikacjach postrzeganie aspektów środowiska będących przedmiotem aktualnego zainteresowania. Większość prac nad tym problemem została wykonana dla stochastycznych środowisk o stanie ciągłym za pomocą narzędzi teorii prawdopodobieństwa. W tej sekcji pokażemy przykład w dyskretnym środowisku z czujnikami deterministycznymi i działaniami niedeterministycznymi. Przykład dotyczy robota z konkretnym zadaniem oceny stanu zwanym lokalizacją: ustaleniem, gdzie się znajduje, mając do dyspozycji mapę świata oraz sekwencję percepcji i działań. Nasz robot znajduje się w podobnym do labiryntu środowisku z rysunku 4.18. Robot jest wyposażony w cztery czujniki sonaru, które informują, czy w każdym z czterech kierunków kompasu znajduje się przeszkoda — zewnętrzna ściana czy ciemny kwadrat na figurze. Percept ma postać wektora bitowego, po jednym bitu dla każdego kierunku północ, wschód, południe i zachód w tej kolejności, więc 1011 oznacza, że ​​istnieją przeszkody na północy, południu i zachodzie, ale nie na wschodzie.

Zakładamy, że czujniki podają idealnie poprawne dane, a robot ma poprawną mapę otoczenia. Niestety, system nawigacyjny robota jest zepsuty, więc wykonując akcję Właściwą, porusza się on losowo na jedno z sąsiednich pól. Zadaniem robota jest określenie jego aktualnej lokalizacji. Załóżmy, że robot został właśnie włączony i nie wie, gdzie jest – jego inicjał to stan przekonania składa się ze zbioru wszystkich lokalizacji. Następnie robot odbiera percept 1011 i dokonuje aktualizacji przy użyciu równania b0 = UPDATE(1011) , dając 4 lokalizacje pokazane na rysunku 4.18(a) . Możesz zbadać labirynt, aby zobaczyć, że są to jedyne cztery lokalizacje, które dają percepcję 1011. Następnie robot wykonuje akcję Właściwą, ale wynik jest niedeterministyczny. Nowy stan przekonania, ba = PREDICT(b0,RIGHT) , zawiera wszystkie lokalizacje, które są o jeden krok od lokalizacji w . Kiedy pojawia się drugi percept, 1010, robot wykonuje UPDATE(1010) i stwierdza, że ​​stan przekonania zapadł się do pojedynczej lokalizacji pokazanej na rysunku 4.18(b). To jedyna lokalizacja, która może być wynikiem

W przypadku działań niedeterministycznych krok PREDICT zwiększa stan przekonania, ale krok UPDATE zmniejsza go z powrotem, o ile spostrzeżenia dostarczają użytecznych informacji identyfikacyjnych. Czasami percepcje nie pomagają zbytnio w lokalizacji: gdyby istniał jeden lub więcej długich korytarzy wschód-zachód, robot mógłby otrzymać długą sekwencję 1010 percepcji, ale nigdy nie wiedział, gdzie w korytarzu (korytarzach) się znajdował. Jednak w środowiskach o rozsądnej zmienności geograficznej lokalizacja często szybko zbliża się do jednego punktu, nawet jeśli działania nie są deterministyczne. Co się stanie, jeśli czujniki są uszkodzone? Jeśli możemy rozumować tylko za pomocą logiki Boole’a, to musimy traktować każdy bit czujnika jako poprawny lub niepoprawny, co jest równoznaczne z brakiem jakichkolwiek informacji percepcyjnych. Zobaczymy jednak, że rozumowanie probabilistyczne (rozdział 12) pozwala nam wydobyć użyteczne informacje z wadliwego czujnika, o ile jest on błędny przez mniej niż połowę czasu.

Rozwiązywanie problemów częściowo obserwowalnych

Poprzednia sekcja pokazała, jak wyprowadzić funkcję WYNIKÓW dla niedeterministycznego problemu stanu przekonań z ukrytego problemu fizycznego, biorąc pod uwagę funkcję PERCEPT. Dzięki temu sformułowaniu algorytm wyszukiwania AND–OR może być zastosowany bezpośrednio do uzyskania rozwiązania. Rysunek poniżej przedstawia część drzewa poszukiwań świata próżni z wykrywaniem lokalnym, przy założeniu początkowej percepcji [A,Dirty]. Rozwiązaniem jest plan warunkowy

Zauważ, że ponieważ dostarczyliśmy problem stanu przekonań do algorytmu wyszukiwania AND-OR, zwrócił on plan warunkowy, który testuje stan przekonań, a nie stan faktyczny. Tak właśnie powinno być: w częściowo obserwowalnym środowisku agent nie będzie znał faktycznego stanu. Podobnie jak w przypadku standardowych algorytmów wyszukiwania stosowanych do problemów bezczujnikowych, algorytm wyszukiwania AND–OR traktuje stany przekonań jako czarne skrzynki, tak jak wszystkie inne stany. Można to poprawić, sprawdzając wcześniej wygenerowane stany przekonań, które są podzbiorami lub nadzbiorami obecnego stanu, podobnie jak w przypadku problemów bezczujnikowych. Można również wyprowadzić przyrostowe algorytmy wyszukiwania, analogiczne do tych opisanych dla problemów bezczujnikowych, które zapewniają znaczne przyspieszenie w porównaniu z podejściem czarnej skrzynki.

Wyszukiwanie w częściowo obserwowalnych środowiskach

Wielu problemów nie da się rozwiązać bez wykrywania. Na przykład bezczujnikowa 8-łamigłówka jest niemożliwa. Z drugiej strony, odrobina wyczuwania może zajść daleko: możemy rozwiązać 8-zagadek, jeśli widzimy tylko kwadrat w lewym górnym rogu. Rozwiązanie polega na przenoszeniu każdego kafelka po kolei na obserwowalny kwadrat i od tego momentu śledzeniu jego lokalizacji. W przypadku częściowo obserwowalnego problemu, specyfikacja problemu będzie określać funkcję Percept(s), która zwraca percept odebrany przez agenta w danym stanie. Jeśli wykrywanie jest niedeterministyczne, możemy użyć funkcji PERCEPTS, która zwraca zestaw możliwych perceptów. Dla problemów w pełni obserwowalnych Percept(s) = s lub każdy stan , a dla problemów bezczujnikowych percept(s) = null. Rozważmy świat próżni z wykrywaniem lokalnym, w którym agent ma czujnik położenia, który daje wynik L w lewym kwadracie i R w prawym kwadracie, oraz czujnik zanieczyszczenia, który pokazuje Brudny, gdy bieżący kwadrat jest brudny i Czysty, gdy jest brudny. to czyste. Zatem PERCEPT w stanie 1 to [L,Dirty]. Przy częściowej obserwowalności zwykle będzie tak, że kilka stanów wytwarza to samo postrzeganie; stan 3 również wygeneruje [L,Dirty]. Zatem, biorąc pod uwagę to początkowe spostrzeżenie, początkowy stan przekonań będzie {1,3} . Możemy myśleć, że model przejścia między stanami przekonań dla częściowo obserwowalnych problemów występuje w trzech etapach, jak pokazano na rysunku:

* Etap przewidywania oblicza stan przekonania wynikający z działania, RESULT(b,a) , dokładnie tak samo jak w przypadku problemów bezczujnikowych. Aby podkreślić, że jest to przewidywanie, używamy notacji

gdzie „kapelusz” oznacza „szacowany”, a także używamy PREDICT(b,a) jako synonimu RESULT(b,a).

* Etap możliwych percepcji oblicza zbiór percepcji, które można zaobserwować w przewidywanym stanie przekonań (używając litery do obserwacji):

* Etap aktualizacji oblicza, dla każdego możliwego spostrzeżenia, stan przekonania, który wynikałby z tego spostrzeżenia. Zaktualizowany stan przekonania b0 jest zbiorem stanów, w których mógł powstać percepcja

Agent musi poradzić sobie z możliwymi spostrzeżeniami w czasie planowania, ponieważ nie będzie znał rzeczywistych percepcji, dopóki nie wykona planu. Zauważ, że niedeterminizm w środowisku fizycznym może powiększyć stan przekonania na etapie przewidywania, ale każdy zaktualizowany stan przekonania b0 nie może być większy niż przewidywany stan przekonania ; obserwacje mogą jedynie pomóc w zmniejszeniu niepewności. Co więcej, w przypadku odczuwania deterministycznego stany przekonań dla różnych możliwych percepcji będą rozłączne, tworząc podział pierwotnego przewidywanego stanu przekonań. Łącząc te trzy etapy, otrzymujemy możliwe stany przekonań wynikające z danego działania oraz kolejne możliwe spostrzeżenia:

Wyszukiwanie bez obserwacji

Kiedy percepcje agenta nie dostarczają żadnych informacji, mamy coś, co nazywamy problemem bezczujnikowym (lub problemem zgodnym). Na początku możesz pomyśleć, że agent bezczujnikowy nie ma nadziei na rozwiązanie problemu, jeśli nie ma pojęcia, w jakim stanie zaczyna, ale rozwiązania bezczujnikowe są zaskakująco powszechne i przydatne, głównie dlatego, że nie opierają się na prawidłowym działaniu czujników. Na przykład w systemach produkcyjnych opracowano wiele pomysłowych metod prawidłowego orientowania części z nieznanej pozycji początkowej za pomocą sekwencji działań bez żadnego wykrywania. Czasami plan bezczujnikowy jest lepszy, nawet jeśli dostępny jest plan warunkowy z wykrywaniem. Na przykład lekarze często przepisują antybiotyk o szerokim spektrum działania, zamiast stosować warunkowy plan wykonania badania krwi, a następnie czekania na powrót wyników, a następnie przepisywania bardziej specyficznego antybiotyku. Plan bezczujnikowy oszczędza czas i pieniądze oraz zapobiega ryzyku pogorszenia infekcji przed udostępnieniem wyników testu. Rozważmy bezczujnikową wersję (deterministycznego) świata próżni. Załóż, że agent zna geografię swojego świata, ale nie zna własnego położenia czy rozmieszczenia brudu. W takim przypadku początkowy stan przekonania to {1,2,3,4,5,6,7,8} (patrz Rysunek 4.9 ). Teraz, jeśli agent poruszy się w prawo, będzie w jednym ze stanów {2,4,6,8} — agent uzyskał informacje, nie dostrzegając czegokolwiek! Po [Right,Suck] agent zawsze znajdzie się w jednym ze stanów {4,8}. Wreszcie, po [Right,Suck,Left,Suck] agent ma zagwarantowane osiągnięcie stanu docelowego 7, bez względu na stan początkowy. Mówimy, że agent może zmusić świat do stanu 7.

Rozwiązaniem problemu bezczujnikowego jest sekwencja działań, a nie plan warunkowy (bo nie ma percepcji). Ale szukamy raczej w przestrzeni stanów przekonań niż stanów fizycznych. W przestrzeni stanów przekonań problem jest w pełni obserwowalny, ponieważ podmiot zawsze zna swój stan przekonań. Co więcej, rozwiązaniem (jeśli istnieje) problemu bezczujnikowego jest zawsze sekwencja działań. Dzieje się tak, ponieważ, jak w zwykłych problemach z rozdziału 3, percepcje otrzymywane po każdym działaniu są całkowicie przewidywalne — zawsze są puste! Nie ma więc żadnych nieprzewidzianych okoliczności do planowania. Dzieje się tak, nawet jeśli środowisko jest niedeterministyczne. Moglibyśmy wprowadzić nowe algorytmy rozwiązywania problemów wyszukiwania bezczujnikowego. Ale zamiast tego możemy użyć istniejącego algorytmy, jeśli przekształcimy leżący u jego podstaw problem fizyczny w problem stanu przekonań, w którym poszukujemy raczej stanów przekonań niż stanów fizycznych. Pierwotny problem P ma komponenty ActionsP, ResultP itd., a problem stanu przekonań składa się z następujących komponentów:

* STATES: Przestrzeń stanów przekonań zawiera każdy możliwy podzbiór stanów fizycznych. Jeśli P ma N stanów, to problem stanów przekonań ma 2N stanów przekonań, chociaż wiele z nich może być nieosiągalnych ze stanu początkowego.

* INITIAL STATE: Zazwyczaj stan przekonań składający się ze wszystkich stanów w P , chociaż w niektórych przypadkach agent będzie miał więcej wiedzy niż ta.

* ACTIONS: Jest to nieco trudne. Załóżmy, że agent jest w stanie przekonania b = {s1,s2}, ale wtedy agent nie jest pewien, które działania są legalne. Jeśli założymy, że nielegalne działania nie mają wpływu na środowisko, można bezpiecznie połączyć wszystkie działania w dowolnym stanie fizycznym w obecnym stanie przekonań b:

Z drugiej strony, jeśli nielegalne działanie może prowadzić do katastrofy, bezpieczniej jest dopuścić tylko skrzyżowanie, czyli zestaw działań legalnych we wszystkich stanach. W świecie próżni każde państwo ma takie same działania prawne, więc obie metody dają ten sam wynik.

  * TRANSITION MODEL: W przypadku działań deterministycznych nowy stan przekonań ma jeden stan wynikowy dla każdego z obecnych możliwych stanów (chociaż niektóre stany wynikowe mogą być takie same):

W przypadku niedeterminizmu nowy stan przekonań składa się ze wszystkich możliwych wyników zastosowania działania do dowolnego ze stanów obecnego stanu przekonań:

Rozmiar b’ będzie taki sam lub mniejszy niż w przypadku działań deterministycznych, ale może być większy niż w przypadku działań niedeterministycznych

* GOAL TEST: Agent prawdopodobnie osiąga cel, jeśli jakikolwiek stan w stanie przekonań spełnia test celu leżącego u podstaw problemu, IS-GOALP(s) . Agent koniecznie osiąga cel, jeśli każdy stan spełnia IS-GOALP(s). Naszym celem jest koniecznie osiągnięcie celu.

* ACTION COST: To też jest trudne. Jeśli to samo działanie może mieć różne koszty w różnych stanach, to koszt podjęcia działania w danym stanie przekonań może być jedną z kilku wartości. Na razie zakładamy, że koszt działania jest taki sam we wszystkich stanach, a więc może być przeniesiony bezpośrednio z podstawowego problemu fizycznego.

Rysunek przedstawia osiągalną przestrzeń stanów przekonań dla deterministycznego, bezczujnikowego świata próżni. Jest tylko 12 osiągalnych stanów przekonań spośród 28 = 256 możliwych stanów przekonań.

Powyższe definicje umożliwiają automatyczne skonstruowanie sformułowania problemu stanu przekonań na podstawie definicji leżącego u jego podstaw problemu fizycznego. Gdy to zrobimy, możemy rozwiązać problemy bezczujnikowe za pomocą dowolnego zwykłego algorytmu wyszukiwania z rozdziału 3 . W zwykłym przeszukiwaniu wykresów nowo osiągnięte stany są testowane, aby sprawdzić, czy zostały wcześniej osiągnięte. Działa to również w przypadku stanów przekonań; na przykład na rysunku sekwencja działań [Ssanie,Lewo,Ssanie] rozpoczynająca się w stanie początkowym osiąga ten sam stan przekonania co [Prawo,Lewo,Ssanie], a mianowicie {5,7} . Rozważmy teraz stan wiary osiągnięty przez [Z lewej], a mianowicie {1,3,5,7}. Oczywiście nie jest to identyczne z {5,7} , ale jest to nadzbiór. Możemy odrzucić (przyciąć) każdy taki superzbiór stanów przekonań. Czemu? Ponieważ rozwiązanie z {1,3,5,7} musi być rozwiązaniem dla każdego z poszczególnych stanów 1, 3, 5 i 7, a więc jest rozwiązaniem dla dowolnej kombinacji tych poszczególnych stanów, np. {5 ,7}; dlatego nie musimy próbować rozwiązać {1,3,5,7}, możemy skoncentrować się na próbie rozwiązania ściśle łatwiejszego stanu wiary {5,7}. I odwrotnie, jeśli {1,3,5,7} zostało już wygenerowane i uznane za możliwe do rozwiązania, to każdy podzbiór, taki jak {5,7} , jest gwarantowany. (Jeśli mam rozwiązanie, które działa, gdy jestem bardzo zdezorientowany co do tego, w jakim się jestem stanie, będzie nadal działać, gdy jestem mniej zdezorientowany.) Ten dodatkowy poziom przycinania może znacznie poprawić skuteczność rozwiązywania problemów bezczujnikowych. Jednak nawet przy tym ulepszeniu, bezczujnikowe rozwiązywanie problemów, jak to opisaliśmy, rzadko jest możliwe w praktyce. Jedną z kwestii jest ogrom przestrzeni stanów przekonań — widzieliśmy w poprzednim rozdziale, że często przestrzeń poszukiwań o rozmiarze N jest zbyt duża, a teraz mamy przestrzenie poszukiwań o rozmiarze 2N . Ponadto każdy element przestrzeni wyszukiwania to zestaw do N elementów. W przypadku dużego N nie będziemy w stanie przedstawić nawet jednego stanu przekonań bez wyczerpania pamięci. Jednym z rozwiązań jest przedstawienie stanu przekonań za pomocą bardziej zwięzłego opisu. W języku angielskim moglibyśmy powiedzieć, że agent nie wie „Nic” w stanie początkowym; po przesunięciu w lewo możemy powiedzieć „Nie w skrajnej prawej kolumnie” i tak dalej. Rozdział 7 wyjaśnia, jak to zrobić w formalnym schemacie reprezentacji. Innym podejściem jest unikanie standardowych algorytmów wyszukiwania, które traktują stany przekonań jako czarne skrzynki, tak jak każdy inny stan problemowy. Zamiast tego możemy zajrzeć do wnętrza stanów przekonań i opracować przyrostowe algorytmy wyszukiwania stanów przekonań, które budują rozwiązanie ol_lowerromann świat próżni bezczujnikowej, początkowy stan przekonań to {1,2,3,4,5,6,7,8} i musimy znaleźć sekwencję akcji, która działa we wszystkich 8 stanach. Możemy to zrobić, najpierw znajdując rozwiązanie, które działa dla stanu 1; następnie sprawdzamy, czy działa dla stanu 2; jeśli nie, wróć i znajdź inne rozwiązanie dla stanu 1 i tak dalej. Podobnie jak wyszukiwanie AND–OR musi znaleźć rozwiązanie dla każdej gałęzi w węźle AND, ten algorytm musi znaleźć rozwiązanie dla każdego stanu w stanie przekonania; różnica polega na tym, że wyszukiwanie AND–OR może znaleźć inne rozwiązanie dla każdej gałęzi, podczas gdy przyrostowe wyszukiwanie stanów przekonań musi znaleźć jedno rozwiązanie, które działa dla wszystkich stanów. Główną zaletą podejścia przyrostowego jest to, że zazwyczaj jest ono w stanie szybko wykryć niepowodzenie – gdy stan przekonania jest nierozwiązywalny, zwykle jest tak, że mały podzbiór stanu przekonania, składający się z kilku pierwszych zbadanych stanów, jest również nierozwiązywalny. . W niektórych przypadkach prowadzi to do przyspieszenia proporcjonalnego do wielkości stanów przekonań, które same mogą być tak duże, jak sama przestrzeń stanów fizycznych.

Spróbuj, spróbuj ponownie

Rozważmy śliski świat próżni, który jest identyczny ze zwykłym (niezmiennym) światem próżni, z tą różnicą, że ruchy czasami kończą się niepowodzeniem, pozostawiając agenta w tym samym miejscu. Na przykład przesunięcie w prawo w stanie 1 prowadzi do stanu przekonań {1,2}. Rysunek przedstawia część wykresu wyszukiwania; widać, że nie ma już acyklicznych rozwiązań ze stanu 1, a ANDORSEARCH wróci z porażką.

Istnieje jednak cykliczne rozwiązanie, które polega na próbowaniu Prawidłowo, dopóki nie zadziała. Możemy to wyrazić za pomocą nowej konstrukcji while:

[Suck,while State = 5 do Right, Suck]

lub dodając etykietę oznaczającą część planu i odnosząc się do tej etykiety później:

[Suck,L1 : Right, if State = 5 then L1 else Suck]

Kiedy plan cykliczny jest rozwiązaniem? Minimalnym warunkiem jest to, że każdy liść jest stanem docelowym i że liść jest osiągalny z każdego punktu planu. Oprócz tego musimy rozważyć przyczynę niedeterminizmu. Jeśli rzeczywiście jest tak, że mechanizm napędowy robota próżniowego przez jakiś czas działa, ale w innych przypadkach ślizga się losowo i niezależnie, to agent może być pewien, że jeśli czynność zostanie powtórzona wystarczająco dużo razy, w końcu zadziała i plan zadziała. odnieść sukces. Ale jeśli niedeterminizm jest spowodowany jakimś niezauważonym faktem dotyczącym robota lub środowiska — na przykład pękł pasek napędowy i robot nigdy się nie poruszy — to powtórzenie czynności nie pomoże. Jednym ze sposobów zrozumienia tej decyzji jest stwierdzenie, że początkowe sformułowanie problemu (w pełni obserwowalne, niedeterministyczne) jest porzucane na rzecz innego sformułowania (częściowo obserwowalnego, deterministycznego), w którym niepowodzenie planu cyklicznego przypisuje się nieobserwowanej właściwości popędu pasek.