Задача может быть формально определена с помощью четырех компонентов, описанных ниже.

•    Начальное состояние, в котором агент приступает к работе. Например, начальное состояние для нашего агента в Румынии может быть описано как пребывание в Араде, In (Arad).

•    Описание возможных действий, доступных агенту. В наиболее общей формулировке используется функция определения преемника. Если задано конкретное состояние х, то функция Successor-Fn(x) возвращает множество упорядоченных пар <action, successor>, где каждое действие action представляет собой одно из допустимых действий в состоянии х, а каждый преемник successor представляет собой состояние, которое может быть достигнуто из х путем применения этого действия. Например, из состояния in(Arad) функция определения преемника для данной задачи проезда по Румынии возвратит следующее:

{<Go{Sibiu) , In{Sibiu)>, <Go(Timisoara) , In{Timisoara) >, <Go{Zerind), In(Zerind)>}

Начальное состояние и функция определения преемника, вместе взятые, неявно задают пространство состояний данной задачи — множество всех состояний, достижимых из начального состояния. Пространство состояний образует граф, узлами которого являются состояния, а дугами между узлами — действия. (Карта Румынии, показанная на рис. 3.1, может интерпретироваться как граф пространства состояний, если каждая дорога рассматривается как обозначающая два действия проезда на автомобиле, по одному в каждом направлении.) Путем в пространстве состояний является последовательность состояний, соединенных последовательностью действий.

Рис. 3.1. Упрощенная дорожная карта части Румынии