Tu przedstawiono algorytmy wyszukiwania, których agent może używać do wybierania sekwencji działań w wielu różnych środowiskach – o ile są one epizodyczne, wykonywane przez jednego agenta, w pełni obserwowalne, deterministyczne, statyczne, dyskretne i całkowicie znane. Należy dokonać kompromisu między czasem potrzebnym na wyszukiwanie, ilością dostępnej pamięci i jakością rozwiązania. Możemy być bardziej wydajni, jeśli dysponujemy wiedzą zależną od dziedziny w postaci funkcji heurystycznej, która szacuje, jak daleko dany stan jest od celu, lub jeśli wstępnie obliczamy częściowe rozwiązania obejmujące wzorce lub punkty orientacyjne. Zanim agent będzie mógł rozpocząć poszukiwania, należy sformułować dobrze zdefiniowany problem. Problem składa się z pięciu części: stanu początkowego, zestawu działań, modelu przejścia opisującego wyniki tych działań, zestawu stanów celu oraz funkcji kosztu działania. Środowisko problemu jest reprezentowane przez graf w przestrzeni stanów. Rozwiązaniem jest ścieżka przez przestrzeń stanów (sekwencja działań) od stanu początkowego do stanu docelowego. Algorytmy wyszukiwania generalnie traktują stany i akcje jako niepodzielne, bez wewnętrznej struktury (chociaż wprowadziliśmy cechy stanów, gdy przyszedł czas na naukę). Algorytmy wyszukiwania są oceniane na podstawie kompletności, optymalności kosztów, złożoności czasowej i złożoności przestrzennej. Nieinformowane metody wyszukiwania mają dostęp tylko do definicji problemu. Algorytmy budują drzewo wyszukiwania, próbując znaleźć rozwiązanie. Algorytmy różnią się w zależności od tego, który węzeł rozwiną jako pierwszy:
– BEARTH-FIRST SEARCH wybiera węzły do rozszerzenia za pomocą funkcji oceny.
–BEARTH-FIRST SEARCH rozwija najpierw najpłytsze węzły; jest kompletna, optymalna dla jednostkowych kosztów działania, ale ma wykładniczą złożoność przestrzeni.
– UNIFORM-COST SEARCH rozszerza węzeł o najniższym koszcie ścieżki g(n) i jest optymalny dla ogólnych kosztów działania.
– DEPTH-FIRST SEARCH rozszerza najgłębszy nierozwinięty węzeł pierwszy. Nie jest ani kompletna, ani optymalna, ale ma liniową złożoność przestrzenną. Wyszukiwanie z ograniczeniem głębokości dodaje granicę głębokości.
– ITERATIVE DEEPENING SEARCH wywołuje wyszukiwanie w głąb z rosnącymi limitami głębokości, aż do znalezienia celu. Jest kompletny, gdy wykonywane jest sprawdzanie pełnego cyklu, optymalne dla kosztów działań jednostkowych, ma złożoność czasową porównywalną z przeszukiwaniem wszerz i ma liniową złożoność przestrzenną.
– WYSZUKIWANIE DWUKIERUNKOWE rozszerza dwie granice, jedną wokół stanu początkowego, a drugą wokół celu, zatrzymując się, gdy obie granice się spotykają.
*Poinformowane metody wyszukiwania mają dostęp do funkcji heurystycznej h(n), która szacuje koszt rozwiązania na podstawie n. Mogą mieć dostęp do dodatkowych informacji, takich jak bazy danych wzorców z kosztami rozwiązania.
– GREEDY BEST-FIRST SEARCH rozszerza węzły z minimalnym h(n). Nie jest optymalny, ale często jest skuteczny.
– A* SEARCH rozwija węzły o minimalnym f(n) = g(n) + h(n). A* jest zupełna i optymalna pod warunkiem, że h(n) jest dopuszczalne. Złożoność przestrzenna A* nadal stanowi problem dla wielu problemów.
– WYSZUKIWANIE DWUKIERUNKOWE A* jest czasami bardziej wydajne niż samo A*.
– IDA* (iterative deepening A* search) jest iteracyjną wersją pogłębiającą A*, a tym samym odnosi się do problemu złożoności przestrzeni.
– RBFS (rekurencyjne wyszukiwanie najlepsze-pierwsze) i SMA* (uproszczone A* ograniczone do pamięci) to niezawodne, optymalne algorytmy wyszukiwania, które wykorzystują ograniczoną ilość pamięci; mając wystarczająco dużo czasu, mogą rozwiązać problemy, dla których A* zabraknie pamięci.
– BEAM SEARCH ogranicza wielkość granicy; to sprawia, że jest niekompletny i nieoptymalny, ale często znajduje dość dobre rozwiązania i działa szybciej niż pełne wyszukiwania.
– Wyszukiwanie z wagą A* koncentruje poszukiwania na celu, rozszerzając mniej węzłów, ale poświęcając optymalność.
* Wydajność algorytmów wyszukiwania heurystycznego zależy od jakości funkcji heurystycznej. Czasami można skonstruować dobrą heurystykę, rozluźniając definicję problemu, przechowując wstępnie obliczone koszty rozwiązania dla podproblemów w bazie danych wzorców, definiując punkty orientacyjne lub ucząc się na podstawie doświadczenia z klasą problemu.