Агенты, выполняющие поиск в оперативном режиме После каждого действия агент, выполняющий поиск в оперативном режиме, получает результаты акта восприятия, с помощью которых может узнать, какого состояния он достиг; на основании этой информации агент может дополнить карту своей среды. Текущая карта используется для принятия решения о том, куда двигаться дальше. Такое чередование планирования и выполнения действий означает, что алгоритмы поиска в оперативном режиме весьма значительно отличаются от алгоритмов поиска в автономном режиме, которые рассматривались выше. Например, алгоритмы поиска в автономном режиме, такие как А*, обладают способностью развертывать узел в одной части пространства, а затем немедленно развертывать узел в другой части пространства, поскольку для развертывания узла требуются моделируемые, а не реальные действия. С другой стороны, любой алгоритм поиска в оперативном режиме позволяет агенту развертывать только тот узел, который он физически занимает. Для предотвращения необходимости путешествовать через все дерево, чтобы развернуть следующий узел, представляется более удобным развертывание узлов в локальном порядке. Именно таким свойством обладает поиск в глубину, поскольку (за исключением операции возврата) следующий развертываемый узел является дочерним узлом ранее развернутого узла. Алгоритм агента, выполняющего поиск в глубину в оперативном режиме, приведен в листинге. Агент хранит составленную им карту в таблице 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 используется метод с возвратами, он может применяться только в таких пространствах состояний, где действия являются обратимыми. Существуют также немного более сложные алгоритмы, применимые в пространствах состояний общего вида, но ни один из подобных алгоритмов не характеризуется ограниченным коэффициентом конкурентоспособности.