Program agenta działa całkiem dobrze, ale ma jedną główną słabość: w miarę upływu czasu koszty obliczeniowe związane z wywołaniami ASK rosną i rosną. Dzieje się tak głównie dlatego, że wymagane wnioskowania muszą cofać się coraz dalej w czasie i obejmować coraz więcej symboli zdaniowych. Oczywiście jest to nie do utrzymania – nie możemy mieć agenta, którego czas przetwarzania każdego spostrzeżenia rośnie proporcjonalnie do długości jego życia! To, czego naprawdę potrzebujemy, to stały czas aktualizacji – to znaczy niezależny od t . Oczywistą odpowiedzią jest zapisanie lub buforowanie wyników wnioskowania, aby proces wnioskowania w następnym kroku mógł opierać się, historię perceptów i wszystkie ich rozgałęzienia można zastąpić stanem przekonań – to jest pewną reprezentacją zbioru wszystkich możliwych aktualnych stanów świata. Proces aktualizowania stanu przekonań w miarę pojawiania się nowych percepcji nazywa się estymacją stanu. Podczas gdy stan przekonań był wyraźną listą stanów, tutaj możemy użyć zdania logicznego zawierającego symbole zdań związane z bieżącym krokiem czasowym, a także symbole atemporalne. Na przykład zdanie logiczne
reprezentuje zbiór wszystkich stanów w czasie 1, w którym wumpus żyje, agent znajduje się w [2,1], ten kwadrat jest przewiewny, a w [3,1] lub [2,2] jest dziura , lub obu. Utrzymanie dokładnego stanu przekonań jako logicznej formuły okazuje się nie być łatwe. Jeśli istnieją symbole płynne dla czasu t, to możliwe są 2n stany – to znaczy przyporządkowanie tym symbolom wartości logicznych. Otóż zbiór stanów przekonań jest zbiorem mocy (zbiorem wszystkich podzbiorów) zbioru stanów fizycznych. Istnieją 2n stany fizyczne, stąd 2n stany wiary. Nawet gdybyśmy użyli możliwie najbardziej zwartego kodowania formuł logicznych, z każdym stanem przekonań reprezentowanym przez unikalną liczbę binarną, potrzebowalibyśmy liczb z log2(22n) = 2n bitami do oznaczenia aktualnego stanu przekonań. Oznacza to, że dokładne oszacowanie stanu może wymagać formuł logicznych, których rozmiar jest wykładniczy w liczbie symboli. Jednym z bardzo powszechnych i naturalnych schematów przybliżonego szacowania stanu jest reprezentowanie stanów przekonań jako koniunkcji literałów, czyli formuł 1-CNF. Aby to zrobić, program agenta po prostu próbuje udowodnić Xt i ¬Xt dla każdego symbolu Xt (jak również dla każdego symbolu atemporalnego, którego wartość prawdy nie jest jeszcze znana), biorąc pod uwagę stan wiary w t-1 . Połączenie możliwych do udowodnienia literałów staje się nowym stanem przekonań, a poprzedni stan przekonań zostaje odrzucony. Ważne jest, aby zrozumieć, że ten schemat może z czasem utracić pewne informacje. Na przykład, gdyby zdanie w równaniu było prawdziwym stanem przekonań, to ani P3,1 ani P2,2 nie byłyby indywidualnie udowodnione i żadne z nich nie pojawiłoby się w stanie przekonania 1-CNF. Z drugiej strony, ponieważ każdy literał w stanie przekonań 1-CNF jest udowodniony na podstawie poprzedniego stanu przekonań, a początkowy stan przekonań jest prawdziwym twierdzeniem, wiemy, że cały stan wiary 1-CNF musi być prawdziwy. Zatem zbiór możliwych stanów reprezentowanych przez stan przekonania 1-CNF obejmuje wszystkie stany, które są faktycznie możliwe przy pełnej historii percepcji. Jak pokazano na rysunku 7.21, stan przekonania 1-CNF działa jako prosta zewnętrzna otoczka lub konserwatywne przybliżenie wokół dokładnego stanu przekonania. Uważamy, że idea konserwatywnych przybliżeń do skomplikowanych zestawów jest powracającym motywem w wielu obszarach sztucznej inteligencji.
