Главная arrow Поиск arrow В оперативном режиме
Как начинался компьютер
Компьютерная революция
Двоичный код
Разработки военных лет
Интегральные микросхемы
Микрокомпьютер
Персоны
Сеть
Язык компьютера
Развитие ПО
Гибкие системы
Средства разработки
Информатика
Вычислительная наука
Операционные системы
Искусственный интеллект
Предыстория
Поиск
Знания и рассуждения
Логика
Робототехника
 

 
Локальный поиск в оперативном режиме Печать

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

Вместо перезапуска случайным образом для исследования среды может быть предусмотрено использование случайного блуждания (random walk). В методе случайного блуждания просто выбирается случайным образом одно из действий, доступных из текущего состояния; предпочтение отдается действиям, которые еще не были опробованы. Легко доказать, что метод случайного блуждания позволяет агенту в конечном итоге найти цель или выполнить свою задачу исследования, при условии, что пространство является конечным. С другой стороны, этот процесс может оказаться очень продолжительным. На рисунке показана среда, в которой для поиска цели с помощью метода случайного блуждания может потребоваться количество этапов, измеряемое экспоненциальной зависимостью, поскольку на каждом этапе вероятность шага назад вдвое превышает вероятность шага вперед. Безусловно, что этот пример является надуманным, но существует много реальных пространств состояний, топология которых способствует возникновению «ловушек» такого рода при случайном блуждании.

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

Как оказалось, более эффективным подходом является дополнение метода поиска с восхождением к вершине способностью запоминать, а не способностью выбирать следующее действие случайным образом. Основная идея состоит в том, что необходимо хранить в памяти «текущую наилучшую оценку» H(s) стоимости достижения цели из каждого состояния, которое уже было посещено. На первых порах H(s) представляет собой только эвристическую оценку h(s) и обновляется по мере того, как агент приобретает опыт в исследовании пространства состояний.

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

Оценка стоимости достижения цели через соседнее состояние s` равна оценке стоимости достижения s`, которая складывается с оценкой стоимости достижения цели из s`, т.е. равна c(s, a, s`) + H(s`). В данном примере имеются два действия, с оценками стоимости 1+9 и 1+2, поэтому, по всей видимости, лучше всего двигаться вправо. После этого становится очевидно, что оценка стоимости для этого затененного состояния, равная 2, была слишком оптимистической.

Поскольку стоимость наилучшего хода равна 1 и он ведет в состояние, которое находится по меньшей мере на расстоянии 2 шагов от цели, то затененное состояние должно находиться по меньшей мере на расстоянии 3 шагов от цели, поэтому его оценка я должна быть обновлена соответствующим образом, как показано на рисунке б. Продолжая этот процесс, агент перейдет вперед и назад еще дважды, каждый раз обновляя оценку H и «сглаживая» локальный минимум до тех пор, пока не вырвется из него вправо.

Пять итераций алгоритма LRTA* в одномерном пространстве состояний. Каждое состояние обозначено значением H(s), текущей оценкой стоимости достижения цели, а каждая дуга обозначена соответствующей ей стоимостью этапа. Затененное состояние показывает местонахождение агента, а значения, обновленные после каждой итерации, обозначаются двойным кружком

Алгоритм агента, в котором реализована эта схема, получивший название поиска А* в реальном времени с обучением (Learning Real-Time А* — LRTA*), показан в листинге. Как и в алгоритме Online-DFS-Agent, в данном алгоритме составляется карта среды с использованием таблицы result. Этот алгоритм обновляет оценку стоимости для состояния, которое он только что оставил, а затем выбирает ход, «который представляется наилучшим» в соответствии с его текущими оценками стоимости. Следует отметить одну важную деталь, что действия, которые еще не были опробованы в состоянии s, всегда рассматриваются как ведущие непосредственно к цели с наименьшей возможной стоимостью, а именно h(s). Такой оптимизм в отношении неопределенности побуждает агента исследовать новые пути, которые могут действительно оказаться перспективными.


Функция LRTA*-Agent выбирает действие в соответствии со значениями соседних состояний, которые обновляются по мере того, как агент передвигается в пространстве состояний

function LRTA*-Agent(s') returns действие a
  inputs: s1, восприятие, позволяющее идентифицировать
    текущее состояние
  static: result, таблица, индексированная по действиям и состояниям,
    первоначально пустая
    Я, таблица оценок стоимостей, индексированная по состояниям,
    первоначально пустая
    s, а, предыдущие состояние и действие, первоначально
    неопределенные
    if Goal-Test(s') then return stop
    if s' является одним из новых состояний (отсутствующим в Я)
    then H[s'] <r- his1 )
  unless s является неопределенным
  result[a, s] <— s'
  H[s] <— min LRTA*-Cost (s, b, result[b, s] , Я)
  bOActions(s)
  a <r- одно из действий b среди действий Actions (s1)/ которое
  минимизирует значение LRTA*-Cost(s', Ь, resulttb, s1]/ Я)
  s <- s'
  return a
function LRTA*-Cost(s, a, s', Я) returns оценка стоимости
  if s' является неопределенным then return h(s)
  else return 0E,3,5') + H[s']



Гарантируется, что агент LRTA* найдет цель в любой конечной, безопасно исследуемой среде. Однако, в отличие от А*, в бесконечных пространствах состояний применяемый в этом агенте алгоритм становится неполным, поскольку в некоторых случаях этот алгоритм может вовлечь агента в бесконечные блуждания. В наихудшем случае данный алгоритм позволяет исследовать среду с п состояниями за O(n2) этапов, но чаще всего действует намного лучше. Агент LRTA* представляет собой лишь один пример из большого семейства агентов, выполняющих поиск в оперативном режиме, которые могут быть определены путем задания правила выбора действия и правила обновления различными способами.