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