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

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

• Проверка цели, позволяющая определить, является ли данное конкретное состояние целевым состоянием. Иногда имеется явно заданное множество возможных целевых состояний, и эта проверка сводится просто к определению того, является ли данное состояние одним из них. Цель рассматриваемого агента в Румынии представляет собой одноэлементное множество {In {Bucharest) }. Иногда цель задается в виде абстрактного свойства, а не явно перечисленного множества состояний. Например, в шахматах цель состоит в достижении состояния, называемого «матом», в котором король противника атакован и не может уклониться от удара.
• Функция стоимости пути, которая назначает числовое значение стоимости каждому пути. Агент, решающий задачу, выбирает функцию стоимости, которая соответствует его собственным показателям производительности. Для данного агента, пытающегося попасть в Бухарест, важнее всего время, поэтому стоимость пути может измеряться длиной в километрах. Предполагается, что стоимость пути может быть описана как сумма стоимостей отдельных действий, выполняемых вдоль этого пути. Стоимость этапа, связанного с выполнением действия а для перехода из состояния х в состояние у, обозначается как с (х, а, у). Стоимости этапов для Румынии показаны на рисунке в виде дорожных расстояний. Предполагается, что стоимости этапов являются неотрицательными.