Задачи поиска в оперативном режиме
Любая задача поиска в оперативном режиме может быть решена только агентом, выполняющим и вычисления, и действия, а не осуществляющим лишь вычислительные процессы. Предполагается, что агент обладает только описанными ниже знаниями.
• Функция Actions (s), которая возвращает список действий, допустимых в состоянии s.
• Функция стоимости этапа c{s, a, sl ); следует отметить, что она не может использоваться до тех пор, пока агент не знает, что результатом является состояние s'.
• Функция Goal-Test (s).
Следует, в частности, отметить, что агент не может получить доступ к преемникам какого-либо состояния, иначе чем путем фактического опробования всех действий в этом состоянии. Например, в задаче с лабиринтом, показанной на рис. 4.12, агент не знает, что переход в направлении Up из пункта (1,1) приводит в пункт (1,2), а выполнив это действие, не знает, позволит ему действие Down вернуться назад в пункт (1,1). Такая степень неведения в некоторых приложениях может быть уменьшена, например, робот-исследователь может знать, как работают его действия по передвижению, и оставаться в неведении лишь в отношении местонахождения препятствий.
Мы будем предполагать, что агент всегда может распознать то состояние, которое он уже посещал перед этим, кроме того, будем руководствоваться допущением, что все действия являются детерминированными. (Последние два допущения будут ослаблены в главе 17.) Наконец, агент может иметь доступ к некоторой допустимой эвристической функции h{s), которая оценивает расстояние от текущего состояния до целевого. Например, как показано на рис. 4.12, агент может знать местонахождение цели и быть способным использовать эвристику с манхэттенским расстоянием.
Как правило, назначение агента состоит в том, чтобы достичь целевого состояния, минимизируя при этом стоимость. (Еще одно возможное назначение агента может заключаться в том, чтобы он просто исследовал всю эту среду.) Стоимость представляет собой суммарную стоимость пути, фактически пройденного агентом. Обычно принято сравнивать эту стоимость со стоимостью пути, по которому следовал бы агент, если бы он заранее знал пространство поиска, т.е. со стоимостью фактического кратчайшего пути (или кратчайшего полного обследования). В терминологии алгоритмов поиска в оперативном режиме это соотношение называется коэффициентом конкурентоспособности; желательно, чтобы этот коэффициент был как можно меньше.
Хотя такое требование по минимизации коэффициента конкурентоспособности может показаться резонным, можно легко доказать, что в некоторых случаях наилучший достижимый коэффициент конкурентоспособности (competitive ratio) является бесконечным. Например, если некоторые действия необратимы, то поиск в оперативном режиме может в конечном итоге перейти в тупиковое состояние, из которого не достижимо целевое состояние. Возможно, читатель сочтет выражение "в конечном итоге'4 неубедительным; в конце концов, должен же существовать такой алгоритм, который окажется способным не упираться в тупик в ходе проведения исследований с его помощью! Поэтому уточним приведенное выше утверждение таким образом: & ни один алгоритм не позволяет избежать тупиков во всех возможных пространствах состояний. Рассмотрим два пространства состояний с тупиками, показанные на рис. 4.13, а. Для алгоритма поиска в оперативном режиме, который посетил состояния S и д оба эти пространства состояний представляются идентичными, поэтому он должен принять одинаковое решение в обоих из них. Поэтому в одном из этих состояний алгоритм потерпит неудачу. Это — один из примеров возражения противника (adversary argument), поскольку легко себе представить, как противник формирует пространство состояний в ходе того, как это пространство исследуется агентом, и может размещать цели и тупики везде, где пожелает.
Тупики представляют собой одну из реальных сложностей в области исследований, проводимых с помощью робота, поскольку лестницы, пандусы, обрывы и многие другие формы естественного ландшафта создают предпосылки для необратимых действий. Для того чтобы добиться прогресса, мы будем предполагать, что данное пространство состояний является безопасно исследуемым, т.е. что некоторые целевые состояния достижимы из каждого достижимого состояния. Пространства состояний с обратимыми действиями, такие как лабиринты и задачи игры в восемь, могут рассматриваться как неориентированные графы и, вполне очевидно, являются безопасно исследуемыми.
Но даже в безопасно исследуемых вариантах среды нельзя гарантировать достижение какого-либо ограниченного значения коэффициента конкурентоспособности, если в них имеются маршруты с неограниченной стоимостью. Это утверждение легко доказать применительно к вариантам среды с необратимыми действиями, но фактически оно остается истинным также и для обратимого случая (см. рис. 4.13, б). По этой причине обычно принято описывать производительность алгоритмов поиска в оперативном режиме с учетом размеров всего пространства состояний, а не только глубины самой поверхностной цели.