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

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

  • Функция Actions(s), которая возвращает список действий, допустимых в состоянии s.
  • Функция стоимости этапа c(s, a, s`); следует отметить, что она не может использоваться до тех пор, пока агент не знает, что результатом является состояние s`.
  • Функция Goal-Test(s).

Следует, в частности, отметить, что агент не может получить доступ к преемникам какого-либо состояния, иначе чем путем фактического опробования всех действий в этом состоянии. Например, в задаче с лабиринтом, показанной на рисунке, агент не знает, что переход в направлении Up из пункта (1, 1) приводит в пункт (1, 2), а выполнив это действие, не знает, позволит ему действие Down вернуться назад в пункт (1, 1). Такая степень неведения в некоторых приложениях может быть уменьшена, например, робот-исследователь может знать, как работают его действия по передвижению, и оставаться в неведении лишь в отношении местонахождения препятствий.

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

Простая задача с лабиринтом. Агент начинает движение с квадрата S и должен достичь квадрата G, но ничего не знает о самой среде 

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

Хотя такое требование по минимизации коэффициента конкурентоспособности может показаться резонным, можно легко доказать, что в некоторых случаях наилучший достижимый коэффициент конкурентоспособности (competitive ratio) является бесконечным. Например, если некоторые действия необратимы, то поиск в оперативном режиме может в конечном итоге перейти в тупиковое состояние, из которого не достижимо целевое состояние.

Возможно, читатель сочтет выражение «в конечном итоге» неубедительным; в конце концов, должен же существовать такой алгоритм, который окажется способным не упираться в тупик в ходе проведения исследований с его помощью! Поэтому уточним приведенное выше утверждение таким образом: ни один алгоритм не позволяет избежать тупиков во всех возможных пространствах состояний. Рассмотрим два пространства состояний с тупиками.

Для алгоритма поиска в оперативном режиме, который посетил состояния S и A, оба эти пространства состояний представляются идентичными, поэтому он должен принять одинаковое решение в обоих из них. Поэтому в одном из этих состояний алгоритм потерпит неудачу. Это — один из примеров возражения противника (adversary argument), поскольку легко себе представить, как противник формирует пространство состояний в ходе того, как это пространство исследуется агентом, и может размещать цели и тупики везде, где пожелает.


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

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

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