Problem wyszukiwania można formalnie zdefiniować w następujący sposób:
* Zbiór możliwych stanów, w których może znajdować się środowisko. Nazywamy to przestrzenią stanów.
* Stan początkowy, w którym uruchamia się agent. Na przykład: Arad.
* Zestaw co najmniej jednego stanu celu. Czasami istnieje jeden stan docelowy (np. Bukareszt), czasami istnieje niewielki zbiór alternatywnych stanów docelowych, a czasami cel jest określony przez właściwość, która odnosi się do wielu stanów (potencjalnie nieskończonej liczby). Na przykład w świecie odkurzaczy celem może być brak brudu w dowolnym miejscu, niezależnie od innych faktów dotyczących stanu. Możemy wyjaśnić wszystkie trzy z tych możliwości, określając metodę IS-GOAL dla problemu. W tym rozdziale będziemy czasami mówić „cel” dla uproszczenia, ale to, co mówimy, odnosi się również do „dowolnego z możliwych stanów celu”.
* Akcje dostępne dla agenta. s ACTIONS(s) danego stanu zwraca skończony zbiór akcji, które mogą być wykonane w. Mówimy, że każda z tych akcji ma zastosowanie w s. Przykład:
ACTIONS(Arad) = {ToSibiu, ToTimisoara, ToZerind}.
* Model przejścia, który opisuje, co robi każda akcja. RESULT(s,a) zwraca stan wynikający z wykonania akcji w stanie s .Na przykład
RESULT(Arad; ToZerind) = Zerind.
* Funkcja kosztu akcji, oznaczana przez ACTION-COST(s,a,s’) kiedy programujemy lub c(s,a,s’) kiedy wykonujemy matematykę, która daje liczbowy koszt zastosowania akcji w stanie osiągnąć stan s”. Agent rozwiązujący problemy powinien używać funkcji kosztu, która odzwierciedla jego własną miarę wydajności; na przykład, w przypadku agentów wyszukujących trasy, kosztem działania może być długość w milach (jak widać na rysunku 3.1 ) lub może to być czas potrzebny na ukończenie działania. Sekwencja działań tworzy ścieżkę, a rozwiązanie jest ścieżką od stanu początkowego do stanu docelowego. Zakładamy, że koszty działania są addytywne; oznacza to, że całkowity koszt ścieżki jest sumą kosztów poszczególnych działań. Optymalne rozwiązanie ma najniższy koszt ścieżki spośród wszystkich rozwiązań. W tym rozdziale zakładamy, że wszystkie koszty działań będą dodatnie, aby uniknąć pewnych komplikacji. Przestrzeń stanów można przedstawić jako graf, w którym wierzchołkami są stany, a skierowane między nimi krawędzie są działaniami. Mapa Rumunii pokazana na rysunku powyżej jest takim wykresem, gdzie każda droga wskazuje dwa działania, po jednym w każdym kierunku.