Локальный поиск в оперативном режиме
Как и поиск в глубину, поиск с восхождением к вершине обладает свойством локализации применительно к операциям развертывания в нем узлов. В действительности сам поиск с восхождением к вершине уже можно считать алгоритмом поиска в оперативном режиме, поскольку предусматривает хранение в памяти только одного текущего состояния! К сожалению, в своей простейшей форме этот алгоритм не очень полезен, так как оставляет агента в таком положении, что последний не может покинуть локальный максимум и отправиться куда-то еще. Более того, в этом алгоритме не может использоваться перезапуск случайным образом, поскольку агент не способен перенести самого себя в новое состояние.
Вместо перезапуска случайным образом для исследования среды может быть предусмотрено использование случайного блуждания (random walk). В методе случайного блуждания просто выбирается случайным образом одно из действий, доступных из текущего состояния; предпочтение отдается действиям, которые еще не были опробованы. Легко доказать, что метод случайного блуждания позволяет агенту в конечном итоге найти цель или выполнить свою задачу исследования, при условии, что пространство является конечным15. С другой стороны, этот процесс может оказаться очень продолжительным. На рис. 4.14 показана среда, в которой для поиска цели с помощью метода случайного блуждания может потребоваться количество этапов, измеряемое экспоненциальной зависимостью, поскольку на каждом этапе вероятность шага назад вдвое превышает вероятность шага вперед. Безусловно, что этот пример является надуманным, но существует много реальных пространств состояний, топология которых способствует возникновению "ловушек" такого рода при случайном блуждании.
Как оказалось, более эффективным подходом является дополнение метода поиска с восхождением к вершине способностью запоминать, а не способностью выбирать следующее действие случайным образом. Основная идея состоит в том, что необходимо хранить в памяти "текущую наилучшую оценку" H(s) стоимости достижения цели из каждого состояния, которое уже было посещено. На первых порах H(s) представляет собой только эвристическую оценку h(s) и обновляется по мере того, как агент приобретает опыт в исследовании пространства состояний. На рис. 4.15 показан простой пример одномерного пространства состояний. На рис. 4.15, а показано, что агент, по-видимому, зашел в тупик, попав в плоский локальный минимум, соответствующий затененному состоянию. Вместо того чтобы оставаться там, где находится, агент должен последовать по тому пути, который может рассматриваться как наилучший путь к цели согласно текущим оценкам стоимостей для соседних состояний. Оценка стоимости достижения цели через соседнее состояние s' равна оценке стоимости достижения s', которая складывается с оценкой стоимости достижения цели из s', т.е. равна c{s, a, s' )+Я(s' ). В данном примере имеются два действия, с оценками стоимости 1 + 9 и 1+2, поэтому, по всей видимости, лучше всего двигаться вправо. После этого становится очевидно, что оценка стоимости для этого затененного состояния, равная 2, была слишком оптимистической. Поскольку стоимость наилучшего хода равна 1 и он ведет в состояние, которое находится по меньшей мере на расстоянии 2 шагов от цели, то затененное состояние должно находиться по меньшей мере на расстоянии 3 шагов от цели, поэтому его оценка я должна быть обновлена соответствующим образом, как показано на рис. 4.15, б. Продолжая этот процесс, агент перейдет вперед и назад еще дважды, каждый раз обновляя оценку я и "сглаживая" локальный минимум до тех пор, пока не вырвется из него вправо.
Алгоритм агента, в котором реализована эта схема, получивший название поиска А* в реальном времени с обучением (Learning Real-Time А* — LRTA*), показан в листинге 4.6. Как и в алгоритме Online-DFS-Agent, в данном алгоритме составляется карта среды с использованием таблицы result. Этот алгоритм обновляет оценку стоимости для состояния, которое он только что оставил, а затем выбирает ход, "который представляется наилучшим" в соответствии с его текущими оценками стоимости. Следует отметить одну важную деталь, что действия, которые еще не были опробованы в состоянии s, всегда рассматриваются как ведущие непосредственно к цели с наименьшей возможной стоимостью, а именно h(s). Такой оптимизм в отношении неопределенности побуждает агента исследовать новые пути, которые могут действительно оказаться перспективными.
Листинг 4.6. Функция LRTA* -Agent выбирает действие в соответствии со значениями соседних состояний, которые обновляются по мере того, как агент передвигается в пространстве состояний
function LRTA*-Agent(s1) returns действие a
inputs: s\ восприятие, позволяющее идентифицировать текущее состояние
static: result, таблица, индексированная по действиям и состояниям, первоначально пустая Я, таблица оценок стоимостей, индексированная по состояниям,
первоначально пустая s, а, предыдущие состояние и действие, первоначально неопределенные
if Goal-Test(s') then return stop
if s' является одним из новых состояний (отсутствующим в Я)
then H[s} ] h(s' ) unless s является неопределенным
result[a, s] <— s'
H[s]
a <— одно из действий b среди действий Actions(s')/ которое
минимизирует значение LRTA*-Cost(s1, b, result[b, s1], Я)
S