Czym sie charakteryzuje agent celowy
Agent celowy poszukuje rozwiązania realizującego cel w zbiorze rozwiązań dopuszczalnych.
Na takiej zasadzie opiera się działanie wielu agentów, np.:
- agenci - obiekty w grach komputerowych, symulatorach
- oprogramowanie przewodników drogi wykorzystujących system GPS
- agenci poszukujący w Internecie stron z żądaną zawartością
Jaka jest różnica między poszukiwaniem nieinformowanym, a informowanym?
Podstawową zasadą poszukiwań nieinformowanych jest korzystanie wyłącznie z definicji zadania - bez wykorzystywania dodatkowych informacji.
Wada: przypominają one próbę dojechania w mieście samochodem na podany adres gdy zna się tylko ten adres oraz reguły prowadzenia samochodu. 🚗
Strategie poszukiwania wykorzystujące dodatkowe informacje o zadaniu nazywa się informowanymi
Idea: dodatkowa informacja może posłużyć do najkorzystniejszego uporządkowania węzłów
przed ich rozwinięciem
Cztery kroki przy poszukiwaniu rozwiązania
- Sformułowanie celu zadania - jaki stan systemu odpowiada osiągnięciu celu?
- Sformułowanie zadania - określenie stanów i rodzajów działań
- Poszukiwanie - określenie optymalnych działań, które należy wykonać aby osiągnąć cel
- Wykonanie zadania
Rodzaje zadań poszukiwania
Zadanie najprostsze:
- Deterministyczne, obserwowalne ⇒ zadanie jednostanowe
- agent wie w jakim jest stanie i w jakim stanie się znajdzie;
rozwiązanie jest ciągiem stanów
Zadania znacznie trudniejsze:
- agent wie w jakim jest stanie i w jakim stanie się znajdzie;
- Nieobserwowalne ⇒ zadanie bez czujników (conformant problem)
- agent nie wie gdzie jest
- Niedeterministyczne lub obserwowalne częściowo ⇒ (contingency problem)
- obserwacje dostarczają nowych informacji o stanie bieżącym
- poszukiwania często przeplatają się z działaniami
- Nieznana przestrzeń stanów ⇒ (exploration problem)
Zadanie jednostanowe - sformułowanie
Zadanie jednostanowe zdefiniowane jest za pomocą czterech elementów:
- stan początkowy, np. „jestem w Arad”
- działanie lub funkcja następstwa
S(x) = zbiór par 〈działanie, stan po działaniu〉$
np. S(Arad) = {〈Arad → Zerind, Zerind〉, …}- test osiągnięcia celu
- jawny, np. x = ”w Bukareszcie”
- niejawny, np. w szachach Mat(x);
- koszt drogi (addytywny)
- np. suma odległości, liczba podjętych działań, etc.
- c(x, a, y) jest kosztem kroku x → y, z założenia c ≥ 0
Rozwiązaniem zadania jednostanowego jest ciąg działań
prowadzących ze stanu początkowego do stanu docelowego.
Rozwiązanie optymalne cechuje najmniejszy koszt.
Co to abstrakcja?
Świat rzeczywisty jest krańcowo skomplikowany, dlatego przestrzeń stanów musi być
abstrakcją stanów rzeczywistych. Abstrakcja oznacza pominięcie szczegółów.
Działanie abstrakcyjne to złożona kombinacja działań rzeczywistych,
np.
Arad→Zerind reprezentuje złożony zbiór możliwych tras, objazdy, parkingi, etc.
Aby zapewnić istnienie rozwiązania, każdy stan rzeczywisty (np.
Arad)
musi prowadzić do jakiegoś stanu rzeczywistego (np. Zerind).
Rozwiązanie abstrakcyjne to zbiór rzeczywistych dróg, które
są rozwiązaniami w świecie rzeczywistym.
Każde działanie abstrakcyjne powinno być łatwiejsze niż rzeczywiste.
Poszukiwania nieinformowane: Algorytmy przeszukiwania drzew
Idea algorytmów przeszukujących:
- ślepe poszukiwania: analiza wszystkich możliwych sekwencji stanów
- koszt rośnie gwałtownie ze wzrostem liczby możliwych
stanów;
- koszt rośnie gwałtownie ze wzrostem liczby możliwych
- poszukiwania poprzez budowę drzewa stanów:
- korzeń - stan początkowy
- węzły i gałęzie - generowane są funkcją następstwa
Algorytm przeszukiwania tworzy (”rozwija”) nowe węzły, wypełnia odpowiednie pola,
a następnie tworzy stany w nowych węzłach.
Jakie struktury wchodza w sklad algorytmow przeszukiwania nieinformowanego
- Stan określa jednoznacznie konfigurację fizyczną obiektu
- Węzeł jest to struktura danych określająca część drzewa poszukiwań, obejmująca np.: stan, węzeł rodzica, węzły dzieci, koszt gałęzi, aktualną głębokość, podejmowane działanie, itp.
- Brzeg (fringe) to zbiór wszystkich węzłów, które nie zostały jeszcze rozwinięte
Strategie algorytmów przeszukiwania drzew
Strategia poszukiwania jest określona kolejnością rozwijania węzłów
Strategie są oceniane wg następujących kryteriów:
- zupełność: możliwość znalezienia rozwiązania, jeżeli istnieje
- złożoność czasowa: proporcjonalna do liczby rozwijanych węzłów
- złożoność pamięciowa: największa liczba węzłów w pamięci
- optymalność: możliwość wyznaczenia najtańszego rozwiązania
🚨 Największą wadą poszukiwań nieinformowanych jest wykładniczy wzrost kosztu obliczeń.
Krytyczna jest zwłaszcza ilość wymaganej pamięci, gdyż może ona być gigantyczna
nawet dla zadań o umiarkowanych wymiarach
Złożoność czasowa i pamięciowa są szacowane za pomocą następujących wielkości:
- b: maksymalny współczynnik rozgałęzienia drzewa poszukiwań
- d: głębokość na której jest rozwiązanie optymalne
- m: maksymalna głębokość przestrzeni stanów
Poszukiwanie wszerz (breadth-first search) BFS
➡️ Zasada: rozwinąć najpłytszy nierozwinięty węzeł na brzegu
Brzeg jest kolejką FIFO, tzn. nowy węzeł wstawiany jest na koniec kolejki
Własności algorytmu:
- ✅ Zupełność: Tak, jeżeli b jest ograniczone
- ⏰ Czas: O(bd+1) (1+b+b2+b3+… +bd + b(bd-1))
- 💾 Pamięć: O(bd+1) (przechowywanie wszystkich węzłów w pamięci)
- 🆗 Optymalność: Tak, jeżeli koszt kroku jest stały
🚨 Pamięć jest największym problemem, większym niż czas poszukiwań
Poszukiwanie w głąb (depth-first search) DFS
➡️ Zasada: rozwinąć najgłębszy nierozwinięty węzeł na brzegu
Brzeg jest kolejką LIFO, tzn. nowy węzeł wstawiany jest na początek kolejki
Własności algorytmu:
- ✅ Zupełność:
- Tak w przestrzeniach skończonych
- Nie w przestrzeniach nieskończonych, z pętlami (wymaga wtedy modyfikacji
w celu uniknięcia powtarzających się stanów)
- ⏰ Czas: O(b^m) - ogromny jeżeli m»_space; d
- 💾 Pamięć: O(bm) - liniowa złożoność względem pamięci
- 🆗 Optymalność: Nie
Poszukiwanie na ograniczoną głębokość (depth-limited search)
➡️ Zasada: jak w algorytmie poszukiwania w głąb ale z głębokością ograniczoną do poziomu l
Własności algorytmu:
- ✅ Zupełność: Tak, jeżeli l ≥ d
- ⏰ Czas: O(b^l)
- 💾 Pamięć: O(bl)
- 🆗 Optymalność: Tak, jeżeli l ≤ d
Poszukiwanie pogłębiane iteracyjnie (iterative deepening search)
➡️ Zasada: wyznaczyć iteracyjnie najlepszą głębokość l
Cel jest osiągnięty na głębokości d odpowiadającej najpłytszemu węzłowi docelowemu.
Algorytm łączy zalety algorytmów poszukiwania wszerz i w głąb.
Własności algorytmu:
- ✅ Zupełność: Tak
- ⏰ Czas: O(b^d)
- 💾 Pamięć: O(bd)
- 🆗 Optymalność: Tak, jeżeli koszt kroku jest stały
Poszukiwanie dwukierunkowe (bidirectional search)
➡️ Zasada: jednoczesne poszukiwanie z początku i końca
Własności algorytmu:
- ✅ Zupełność: Tak, jeżeli oba poszukiwania wszerz
- ⏰ Czas: O(b^{d/2})
- 💾 Pamięć: O(b^{d/2})
- 🆗 Optymalność: Tak, jeżeli oba poszukiwania wszerz
Podsumowanie algorytmow przeszukiwania nieinformowanego
- Rozwiązywanie zadań poprzez przeszukiwanie wymaga
sformułowania zadania w postaci abstrakcyjnej. - Jeżeli zadanie jest deterministyczne i obserwowalne
(jednostanowe), to do jego rozwiązania można użyć
algorytmu poszukiwania nieinformowanego. - Istnieje wiele algorytmów poszukiwania nieinformowanego:
- wszerz
- w głąb
- kosztu jednorodnego
- stałej głębokości
- pogłębiania iteracyjnego
- poszukiwań dwukierunkowych
- Algorytm poszukiwania poprzez pogłębianie iteracyjne jest
najlepszym algorytmem ogólnym - wymaga liniowej pamięci
a czas obliczeń jest niewiele większy niż w przypadku innych
algorytmów. - Agenci działający na zasadzie poszukiwania rozwiązania
są używani w wielu dziedzinach:- wyznaczaniu drogi
- planowaniu układów VLSI
- nawigacji robotów
- poszukiwań internetowych
Czym jest zasada poszukiwania informowanego w sztucznej inteligencji?
Algorytmy poszukiwań informowanych wykorzystują funkcję heurystyczną do szacowania najniższego kosztu ścieżki do celu. Wybór węzła do rozwinięcia opiera się na szacowanej funkcji kosztu f(n) = g(n) + h(n), gdzie g(n) to koszt ścieżki od początku do węzła n, a h(n) to szacowany koszt od n do celu.
Jak wykorzystywana jest funkcja heurystyczna h(n) w poszukiwaniach informowanych?
h(n) jest kluczową częścią poszukiwań informowanych, nie występuje w oryginalnym sformułowaniu problemu. Oszacowuje koszt od węzła n do celu, opierając się na dodatkowych informacjach heurystycznych, co upraszcza proces podejmowania decyzji w skomplikowanych sytuacjach.
Jaka jest rola kolejki priorytetowej w implementacji algorytmów poszukiwań informowanych?
W poszukiwaniach informowanych brzeg drzewa wyszukiwania zarządzany jest jako kolejka priorytetowa, gdzie węzły są priorytetyzowane na podstawie ich szacowanego całkowitego kosztu dotarcia do celu, ocenianego przez funkcję heurystyczną f(n)
Zdefiniuj pojęcie “heurystyki” w kontekście poszukiwań informowanych.
Heurystyka, czyli „reguła kciuka”, to strategia lub metoda ułatwiająca podejmowanie decyzji lub rozwiązywanie problemów bardziej efektywnie poprzez uproszczenie procesu, zwłaszcza gdy dokładne rozwiązanie jest skomplikowane lub nieznane.
Co sprawia, że heurystyka jest “dopuszczalna” lub “zgodna” w poszukiwaniach informowanych?
Heurystyka jest dopuszczalna, jeśli nigdy nie przeszacowuje prawdziwego kosztu dotarcia do celu (h(n) ≤ h^*(n)). Jest zgodna, jeśli spełnia nierówność trójkąta h(n) ≤ c(n,a,n’) + h(n’) dla każdej akcji a prowadzącej od n do n’.
Co oznacza, że jedna heurystyka dominuje nad inną?
Jeśli istnieją dwie dopuszczalne heurystyki h_1(n) i h_2(n) takie, że h^*(n) ≥ h_2(n) ≥ h_1(n) dla każdego węzła n, to h_2 dominuje nad h_1. Dominująca heurystyka jest bardziej efektywna, gdyż dostarcza bliższe oszacowanie prawdziwego kosztu.
Jak można stworzyć dobrą heurystykę dopuszczalną?
Dobrą heurystykę dopuszczalną można stworzyć przez rozluźnienie warunków zadania (rezygnacja z niektórych ograniczeń), co pozwala na wykorzystanie funkcji rozwiązującej problem w uproszczonej formie. Takie podejście zapewnia, że użyta heurystyka nigdy nie przeszacowuje rzeczywistego kosztu, prowadząc do optymalnego rozwiązania.
Czym różni się heurystyka dopuszczalna od zgodnej?
Heurystyka dopuszczalna nigdy nie przeszacowuje kosztów rzeczywistego osiągnięcia celu, podczas gdy heurystyka zgodna dodatkowo spełnia nierówność trójkąta, co oznacza, że koszt szacowany przez heurystykę dla każdego węzła n jest mniejszy lub równy sumie kosztu kroku do następnika n’ i heurystyki tego następnika.
Algorytm najpierw najlepszy (best-first)
Algorytm rozwija węzeł który leży najbliżej celu.
