Jak znaleźć te przypadkowe rozwiązania problemów niedeterministycznych? Jak wcześniej zaczynamy od skonstruowania drzew poszukiwań, ale tutaj drzewa mają inny charakter. W środowisku deterministycznym jedyne rozgałęzienie jest wprowadzane przez własne wybory agenta w każdym stanie: mogę wykonać tę akcję lub inną akcję. Nazywamy te węzły OR węzłami. W świecie próżni, na przykład, w węźle OR agent wybiera Lewo, Prawo lub Ssanie. W środowisku anondeterministycznym rozgałęzienie jest również wprowadzane przez wybór wyniku dla każdego działania. Nazywamy te węzły AND węzłami. Na przykład działanie Suck w stanie 1 skutkuje stanem przekonania , więc agent musiałby znaleźć plan dla stanu 5 i dla stanu 7. Te dwa rodzaje węzłów są naprzemienne, co prowadzi do drzewa AND–OR, jak pokazano na rysunku.
Rozwiązaniem problemu wyszukiwania AND-OR jest poddrzewo pełnego drzewa wyszukiwania, które (1) ma węzeł celu na każdym liściu, (2) określa jedną akcję w każdym z węzłów OR i (3) zawiera każdą gałąź wyniku w każdym z jego węzłów AND. Rozwiązanie pokazano na rysunku pogrubionymi liniami; odpowiada planowi podanemu w Równaniu (4.3) . Rysunek przedstawia rekurencyjny algorytm do przeszukiwania grafów AND–OR. Jednym z kluczowych aspektów algorytmu jest sposób, w jaki radzi sobie z cyklami, które często pojawiają się w problemach niedeterministycznych (np. jeśli działanie czasami nie przynosi efektu lub jeśli niezamierzony skutek może zostać skorygowany). Jeśli aktualny stan jest identyczny ze stanem na ścieżce od korzenia, to wraca z niepowodzeniem. Nie oznacza to, że nie ma rozwiązania z obecnego stanu; oznacza to po prostu, że jeśli istnieje rozwiązanie niecykliczne, musi być ono osiągalne z wcześniejszego wcielenia obecnego stanu, aby nowe wcielenie można było odrzucić. Dzięki tej kontroli upewniamy się, że algorytm kończy się w każdej skończonej przestrzeni stanów, ponieważ każda ścieżka musi osiągnąć cel, ślepy zaułek lub powtarzający się stan. Zauważ, że algorytm nie sprawdza, czy aktualny stan jest powtórzeniem stanu na jakiejś innej ścieżce od korzenia, co ma znaczenie dla wydajności.
Wykresy AND–OR mogą być eksplorowane albo wszerz albo w pierwszej kolejności. Pojęcie funkcji heurystycznej musi zostać zmodyfikowane, aby oszacować koszt rozwiązania warunkowego, a nie sekwencji, ale pojęcie dopuszczalności pozostaje nadal i istnieje analogia algorytmu A* do znajdowania optymalnych rozwiązań.