Агенты, выполняющие поиск в оперативном режиме
После каждого действия агент, выполняющий поиск в оперативном режиме, получает результаты акта восприятия, с помощью которых может узнать, какого состояния он достиг; на основании этой информации агент может дополнить карту своей среды. Текущая карта используется для принятия решения о том, куда двигаться дальше. Такое чередование планирования и выполнения действий означает, что алгоритмы поиска в оперативном режиме весьма значительно отличаются от алгоритмов поиска в автономном режиме, которые рассматривались выше.

Например, алгоритмы поиска в автономном режиме, такие как А*, обладают способностью развертывать узел в одной части пространства, а затем немедленно развертывать узел в другой части пространства, поскольку для развертывания узла требуются моделируемые, а не реальные действия. С другой стороны, любой алгоритм поиска в оперативном режиме позволяет агенту развертывать только тот узел, который он физически занимает. Для предотвращения необходимости путешествовать через все дерево, чтобы развернуть следующий узел, представляется более удобным развертывание узлов в локальном порядке. Именно таким свойством обладает поиск в глубину, поскольку (за исключением операции возврата) следующий развертываемый узел является дочерним узлом ранее развернутого узла.

Алгоритм агента, выполняющего поиск в глубину в оперативном режиме, приведен в листинге. Агент хранит составленную им карту в таблице result[a, s], в которой регистрируются состояния, явившиеся следствием выполнения действия а в состоянии s. Этот агент предпринимает попытку выполнения из текущего состояния любого действия, которое еще не было исследовано в этом состоянии.

Сложности возникают после того, как агент опробовал все действия в некотором состоянии. При поиске в глубину в автономном режиме это состояние удаляется из очереди, а при поиске в оперативном режиме агент должен выполнить возврат физически. При поиске в глубину это равносильно возврату в последнее по времени состояние, из которого агент перешел в текущее состояние. Соответствующая организация работы обеспечивается за счет ведения такой таблицы, где для каждого состояния перечисляются состояния-предшественники, к которым агент еще не выполнял возврат. Если агент исчерпал список состояний, к которым может выполнить возврат, это означает, что проведенный агентом поиск является полным.

Агент, выполняющий поиск в оперативном режиме, который проводит исследование с использованием поиска в глубину. Этот агент может применяться только в пространствах двунаправленного поиска

function Online-DFS-Agent(s*) returns действие action
  inputs: s', восприятие, позволяющее идентифицировать
  текущее состояние
  static: result, таблица, индексированная по действиям и
  состояниям, первоначально пустая
  unexplored, таблица, в которой для каждого посещенного
  состояния перечислены еще не опробованные
  действия
  unbacktracked, таблица, в которой для каждого посещенного
  состояния перечислены еще не опробованные
  возвраты
  s, а, предыдущие состояние и действие, первоначально
  неопределенные
  if Goal-Test(s') then return stop
  if s' представляет собой новое состояние
  then unexplored[sy ] <— Actions(s')
  if s не является неопределенным then do
  result[a, s] <— s'
  добавить s в начало таблицы unbacktracked[s* ]
  if элемент unexplored[s'] пуст then
  if элемент unbacktracked[s'] пуст then return stop
  else a <— действие b, такое что
  result[b, s'] = Pop{unbacktracked[s'])
  else a <— Pop (imexplored[s' ] )
  s <— s'
  return a


Рекомендуем читателю провести трассировку хода выполнения процедуры Online-DFS-Agent применительно к лабиринту. Можно довольно легко убедиться в том, что в наихудшем случае агент в конечном итоге пройдет по каждой связи в данном пространстве состояний точно два раза. При решении задачи обследования такая организация работы является оптимальной; а при решении задачи поиска целей, с другой стороны, коэффициент конкурентоспособности может оказаться сколь угодно неэффективным, если агент будет отправляться в длительные экскурсии, притом что целевое состояние находится непосредственно рядом с начальным состоянием. Такая проблема решается с использованием варианта метода итеративного углубления для работы в оперативном режиме; в среде, представляющей собой однородное дерево, коэффициент конкурентоспособности подобного агента равен небольшой константе.

В связи с тем что в алгоритме Online-DFS -Agent используется метод с возвратами, он может применяться только в таких пространствах состояний, где действия являются обратимыми. Существуют также немного более сложные алгоритмы, применимые в пространствах состояний общего вида, но ни один из подобных алгоритмов не характеризуется ограниченным коэффициентом конкурентоспособности.