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.