УСЛОВНОЕ ПЛАНИРОВАНИЕ
Условное планирование представляет собой один из способов учета неопределенности путем проверки того, что фактически происходит в среде при выполнении заранее заданных пунктов плана. Условное планирование можно проще всего объяснить на примере полностью наблюдаемых вариантов среды, поэтому начнем его описание с такого случая. Случай с частично наблюдаемой средой является более сложным, но и более интересным.
Условное планирование в полностью наблюдаемых вариантах среды
Полная наблюдаемость означает, что агент всегда знает текущее состояние. Но если среда является недетерминированной, то агент не будет способен предвидеть результат своих действий. Агент, занимающийся условным планированием, преодолевает такую недетерминированность, встраивая в свой план (на этапе планирования) условные этапы, в которых проверяется состояние среды (на этапе выполнения), для определения того, что делать дальше. Поэтому проблема состоит в том, как создавать такие условные планы.
Мы будем использовать в качестве примера проблемной области почтенный мир пылесоса, пространство состояний которого для данного детерминированного случая описано на с. 117. Напомним, что доступными действиями являются Left, Right и Suck. Нам потребуются определенные высказывания для описания этих состояний. Допустим, что предикат AtL (AtR) будет истинным, если агент находится в левом (правом) квадрате5, а предикат CleanL (CleanR) истинен, если левый (правый) квадрат чист. Прежде всего необходимо дополнить язык Strips для того, чтобы он позволял учитывать недетерминированность. Для этого предусмотрено, чтобы действия имели дизъюнктивные результаты, а это означает, что действие может иметь два или несколько различных результатов при каждом его выполнении. Например, допустим, что действие по перемещению Left (Влево) иногда оканчивается неудачей. В таком случае следующее обычное описание действия:
ActioniLeft, Precond: AtR, Effect: AtL A -nAtR)
должно быть модифицировано так, чтобы в него был включен следующий дизъюнктивный результат:
Action (Left,Precond: AtЈ,Effect: AtL v AtR) (12.1)
Авторы сочли также целесообразным, чтобы действия имели условные результаты, когда результат действия зависит от состояния, в котором оно выполняется. Условные результаты присутствуют в слоте Effect действия и имеют синтаксис
"when
Action(Suck,Precond:,Effect: (when AtL: CleanL) л (when AtR: CleanR)})
Условные результаты не вносят недетерминированность, но позволяют ее моделировать. Например, предположим, что в нашем распоряжении имеется не совсем исправный пылесос, который иногда оставляет мусор в квадрате назначения в процессе своего передвижения, но только если этот квадрат чист. Такую ситуацию можно промоделировать с помощью следующего описания, которое одновременно является и дизъюнктивным, и условным6:
Action (Left, Precond: Afci?, Effect: AtL v (AtL л when CleanL: -CleanL))
Для создания условных планов требуются условные этапы. Мы будем записывать их с использованием синтаксиса "if
Нам требуются условные планы, которые работают невзирая на то, какие результаты действий фактически будут получены. Такая проблема уже встречалась раньше в данной книге, но немного в другом виде. В играх с двумя игроками (см. главу 6) была поставлена задача найти ходы, которые приводят к выигрышу независимо от того, какие ходы делает противник. По этой причине задачи недетерминированного планирования часто называют играми против природы.
Рассмотрим конкретный пример из мира пылесоса. В начальном состоянии робот-агент находится в правом квадрате мира, в котором нет мусора; поскольку среда полностью наблюдаема, агент знает полное описание состояния, AtR л CleanL л CleanR. В целевом состоянии робот должен находиться в левом квадрате мира, в котором нет мусора. Такая задача была бы совершенно тривиальной, если бы пылесос не подчинялся "двойному закону Мэрфи" и не оставлял иногда мусор при его перемещении в чистый квадрат назначения, а иногда — при выполнении действия Suck в чистом квадрате.
"Дерево игры" для этой среды показано на рис. 12.6. Действия выполняются роботом в узлах "состояния" этого дерева, а природа решает, каким должен быть результат в узлах "жеребьевки", обозначенных кружками. Решением является поддерево, в котором, во-первых, рядом с каждым листовым узлом имеется целевой узел, во-вторых, задается одно действие в каждом из узлов "состояния" и, в третьих, включена каждая ветвь результата в каждом из узлов "жеребьевки". Решение на этом рисунке показано жирными линиями; оно соответствует плану [Left, if AtL л CleanL л CleanR then [] else Suck]. (На данное время, поскольку используется планировщик в пространстве состояний, проверки в условных этапах приводят к получению полных описаний состояния.)
Для получения точных решений в играх используется алгоритм минимакса (см. листинг 6.1), а для условного планирования обычно применяются две его модификации. Во-первых, узлы МАХ и MIN могут быть преобразованы в узлы OR и AND. Интуитивно кажется очевидным, что в плане требуется предпринимать некоторые действия в каждом достигнутом в нем состоянии, но должны учитываться все результаты предпринятого действия. Во-вторых, алгоритм должен возвращать условный план, а не просто отдельный ход. В узле OR план состоит в выборе действия, за которым следует то, что должно произойти. А в узле AND план представляет собой вложенный ряд этапов "if—then—else" с определением субпланов для каждого результата; проверки в этих этапах возвращают полные описания состояния7.
Формально говоря, определенное нами пространство поиска представляет собой граф AND-OR. В главе 7 графы AND—OR рассматривались в контексте пропозиционального вывода на основе хорновских выражений, а в этой главе ветвями являются действия, а не этапы логического вывода, но алгоритм остается тем же самым. В листинге 12.4 приведен рекурсивный алгоритм поиска в глубину, предназначенный для поиска в графе AND—OR.
Одной из ключевых особенностей этого алгоритма является тот способ, с помощью которого он справляется с циклами, часто возникающими в задачах недетерминированного планирования (например, если какое-то действие иногда не имеет результата или если может быть исправлен нежелательный результат). Если текущее состояние идентично одному из состояний в пути от корня, то алгоритм выполняет возврат с индикатором неудачи. Это не означает, что нет решения, достижимого из текущего состояния; просто такая ситуация свидетельствует о том, что если есть нециклическое решение, оно должно быть достижимым из более раннего воплощения текущего состояния, поэтому его новое воплощение может быть отброшено. С помощью этой проверки можно гарантировать, что алгоритм завершит свою работу в любом конечном пространстве состояний, поскольку каждый путь должен достигнуть цели, тупика или повторяющегося состояния. Обратите внимание на то, что в алгоритме не осуществляется проверка, не является ли текущее состояние повторением какого-то состояния в каком-то другом пути от корня; этот вопрос исследуется в упр. 12.15.
Листинг 12.4. Алгоритм поиска в графах AND-OR, сформированных в условиях недетерминированных вариантов среды. Предполагается, что функция Successors возвращает список действий, каждое из которых связано с множеством возможных результатов. Задача состоит в том, чтобы найти условный план, который достигает целевого состояния во всех обстоятельствах
function And-Or-Graph-Search(problem) returns условный план или индикатор неудачи failure Or-Search(Initial-State[problem], problem, [])
function Or-Search(state, problem, path) returns условный план или индикатор неудачи failure if Goal-Test[problem](state) then return пустой план if состояние state входит в состав path then return failure for each action, state_set in Successors[problem](state) do plan <— And-Search(state_set, problem, [state\path]) if plan Ф failure then return [action\pi an] return failure
function And-Search(state_set, problem, path) returns условный план или индикатор неудачи failure for each si in state_set do
plani <— Or-Search (si, problem, path) if plan - failure then return failure return [if si then plani else if s2 then plan2 else ... if sn-i then plann-x else plann]
Планы, возвращаемые алгоритмом And-Or-Graph-Search, содержат условные шаги, в которых проверяется описание всего состояния для выбора следующей ветви. Но во многих случаях можно справиться с этой работой с помощью менее исчерпывающих проверок. Например, план решения на рис. 12.6 может быть записан просто как [Left, if CleanL then [ ] else Suck]. Это связано с тем, что достаточно провести единственную проверку, CleanL, для разделения состояния в узле AND на два одноэлементных множества, чтобы после проверки агент мог точно определить, в каком состоянии он находится. В действительности проведение ряда проверок по принципу "if—then—else" отдельных переменных всегда позволяет разделить множество состояний на одноэлементные множества, при условии, что среда является полностью наблюдаемой. Поэтому можно без потери общности ограничиться проведением проверок отдельных переменных.
В недетерминированных проблемных областях часто возникает еще одна, последняя сложность: не всегда удается выполнить текущую операцию с первого раза, поэтому приходится предпринимать еще одну попытку. Например, рассмотрим пылесос в мире с "тройным законом Мэрфи", который (кроме ранее указанных его недостатков) иногда отказывается переходить туда, куда требует переданная ему команда, например, действие Left может иметь дизъюнктивный результат AtL v AfcjR, как в уравнении 12.1. Теперь уже нельзя гарантировать, что план [Left, if CleanL then [ ] else Suck] будет работать. Часть нового графа поиска показана на рис. 12.7 ; очевидно, что больше нет каких-либо нециклических решений и алгоритм And-Or-Graph-Search выполняет возврат с индикатором неудачи. Тем не менее существует циклическое решение, которое заключается в том, что нужно продолжать попытки выполнять действие Left до тех пор, пока одна из попыток не достигнет успеха. Это решение можно выразить, введя метку для обозначения некоторой части плана и используя эту метку позднее, вместо повторения самого плана. Таким образом, соответствующее циклическое решение может выглядеть таким образом:
[Ьц Left, if AtR then Li else if CleanL then [] else Suck]
(Более удобный синтаксис для циклической части этого плана мог бы предусматривать применение конструкции "while AfcjR do Left".) Изменения, необходимые для внесения в алгоритм And-Or-Graph-Search, рассматриваются в упр. 12.16. Из этого следует основной вывод, что цикл в пространстве состояний, ведущий в состояние L, преобразуется в цикл в плане, ведущий в ту точку, где выполнялся субплан для состояния L.
Теперь мы получили возможность синтезировать сложные планы, которые во многом выглядят как программы, с условными выражениями и циклами. К сожалению, эти циклы, в принципе, могут стать бесконечными. Например, в представлении действия для мира с "тройным законом Мэрфи" ничего не сказано, что действие Left в конечном итоге закончится успешно. Поэтому циклические планы не столь желательны, как ациклические, но вполне могут рассматриваться как решения, при условии, что каждый листовой узел представляет собой целевое состояние и любой листовой узел достижим из каждой точки в плане.
Условное планирование в частично наблюдаемых вариантах среды
В предыдущем разделе рассматривались полностью наблюдаемые варианты среды, преимущество которых состоит с том, что во время условных проверок можно задавать любые вопросы и быть уверенным в том, что будет получен ответ. Но в реальном мире гораздо чаще встречается частичная наблюдаемость. В начальном состоянии частично наблюдаемой задачи планирования агент обладает лишь некоторым объемом знаний о действительном состоянии. Простейший способ промоделировать такую ситуацию состоит в том, чтобы принять предположение, что начальное состояние принадлежит к множеству состояний; множество состояний представляет собой способ описания начального доверительного состояния агента8.
Предположим следующее: агенту в мире пылесоса известно, что он находится в правом квадрате и что этот квадрат чист, но он не может определить с помощью датчиков наличие или отсутствие мусора в других квадратах. В таком случае, насколько известно агенту, он может находиться в одном из двух состояний: левый квадрат может быть либо чистым, либо грязным. Это доверительное состояние обозначено на рис. 12.8 буквой А На этом рисунке показана часть графа AND—OR для мира пылесоса с "альтернативным двойным законом Мэрфи", в котором мусор может иногда оставаться сзади, после того как агент покидает чистый квадрат9. Если бы этот мир был полностью наблюдаемым, то агент имел бы возможность сформировать циклическое решение в такой форме: "Продолжать двигаться влево и вправо, всасывая мусор везде, где он появляется, до тех пор, пока оба квадрата не станут чистыми, а я не буду находиться в левом квадрате" (см. упр. 12.16). К сожалению, при использовании лишь локального датчика грязи этот план является невыполнимым, поскольку невозможно определить истинностное значение проверки "оба квадрата стали чистыми".
Рассмотрим, как формируется граф AND—OR. Из доверительного состояния А мы показываем результат перемещения с помощью действия Left (другие действия не имеют смысла). Поскольку агент может оставить за собой мусор, эти два возможных начальных состояния мира становятся четырьмя возможными состояниями, как показано в прямоугольниках в и С. Эти состояния формируют два различных доверительных состояния, которые классифицируются по доступной информации датчика10. В доверительном состоянии В агент имеет информацию CleanL, а в доверительном состоянии С — информацию -CleanL. В результате уборки мусора в состоянии С агент переходит в состояние В. После перехода с помощью действия Right из состояния в агент может оставить или не оставить за собой мусор, поэтому снова возникают четыре возможные состояния мира, которые подразделяются в соответствии со знаниями агента о том, является ли правый квадрат чистым, CleanR (возврат в состояние А), или грязным, -CleanR (переход в доверительное состояние D).
Подводя итог, можно отметить, что недетерминированные частично наблюдаемые варианты среды приводят к получению графа AND—OR доверительных состояний. Поэтому для поиска условных планов может применяться точно такой же алгоритм, как и в случае полностью наблюдаемой среды, а именно And-Or-Graph-Search. Еще один способ понять, что происходит, состоит в следующем: необходимо отметить, что доверительное состояние агента всегда является полностью наблюдаемым, т.е. агент всегда знает о том, что он знает. Решение "стандартной" задачи в полностью наблюдаемой среде представляет собой частный случай, в котором каждое доверительное состояние является одноэлементным множеством, содержащим одно и только одно физическое состояние.
Можем ли мы на этом завершить описание данной темы? Не совсем! Еще необходимо определить, как должны быть представлены доверительные состояния, как работают средства сбора информации (датчики) и как в этой новой постановке задачи должны записываться описания действий.
Для описания доверительных состояний могут применяться три описанных ниже основных варианта.
1. Множества полных описаний состояния. Например, начальное доверитель-
ное состояние на рис. 12.8 может быть описано следующим образом:
{ {AtR л CleanR л CleanL) , (AtR л CleanR л -CleanL) }
Это представление является простым в использовании, но очень дорогостоящим: если имеется п булевых высказываний, определяющих состояние, то доверительное состояние может содержать 0(2П) описаний физических состояний, каждый из которых имеет размер О(п). А если агент знает только небольшую часть этих высказываний, то могут возникать экспоненциально большие доверительные состояния, поскольку, чем меньше знает агент, тем больше количество возможных состояний, в которых он может находиться.
2. Логические высказывания, которые точно представляют множество возмож-
ных миров в доверительном состоянии. Например, определение начального
состояния можно записать следующим образом:
AtR л CleanR
Очевидно, что каждое доверительное состояние можно представить с помощью одного и только одного логического высказывания; в случае необходимости можно было бы использовать дизъюнкцию всех конъюнктивных описаний состояния, но рассматриваемый пример показывает, что могут существовать более компактные высказывания.
Один из недостатков общих логических высказываний состоит в том, что может существовать много различных, логически эквивалентных высказываний, которые описывают одно и то же доверительное состояние, поэтому проверка повторяющихся состояний в алгоритме поиска в графе может потребовать применения средств общего доказательства теорем. По этой причине желательно было бы использовать для высказываний каноническое представление, в котором каждое доверительное состояние соответствует одному и только одному высказыванию11. В одном из таких представлений используется конъюнкция литералов, упорядоченных по именам термов; в качестве примера можно привести AtR л CleanR. Такое представление можно рассматривать как стандартное представление состояния с учетом предположения об открытом мире, описанного в главе 11. Не все логические высказывания могут быть записаны в указанной форме (например, не существует способа представления высказывания AtL v CleanR), но такой метод представления доверительных состояний может применяться во многих проблемных областях.
3. Высказывания с оценкой знаний, описывающие знания агента (см. также раз-
дел 7.7). Для данного начального состояния такое высказывание имеет сле-
дующий вид:
К{AtR) A K(CleanR) где X обозначает "знает, что", а К(Р) указывает, что агент знает12 об истинности высказывания Р. В сочетании с высказываниями с оценкой знаний используется предположение о замкнутом мире — если высказывания с оценкой знаний нет в списке, оно рассматривается как ложное. Например, в приведенном выше высказывании неявно присутствуют термы -,К(CleanL) и -K(-nCleanL), поэтому оно представляет тот факт, что агент не знает истинностного значения терма CleanL.
Как оказалось, второй и третий из описанных выше вариантов являются приблизительно эквивалентными, но мы будем использовать третий вариант — высказывания с оценкой знаний, поскольку они позволяют получить более реалистичное описание процесса получения информации с помощью датчиков и поскольку нам уже известно, как составлять описания Strips при использовании предположения о замкнутом мире.
В обоих вариантах каждый пропозициональный символ может быть представлен в одном из трех видов: положительный, отрицательный или неизвестный. Поэтому существует точно Зп возможных доверительных состояний, которые могут быть описаны таким образом. С другой стороны, множество доверительных состояний представляет собой показательное множество (множество всех подмножеств) множества физических состояний. Количество физических состояний равно 2П, поэтому количество доверительных состояний равно 22 , что намного превышает Зп; это означает, что варианты 2 и 3 являются чрезвычайно ограниченными с точки зрения представления доверительных состояний. В настоящее время такая ситуация считается неизбежной, поскольку & любая схема, способная представить любое возможное доверительное состояние, в наихудшем случае для представления каждого из них потребует 0(log222 ) )=0(2П) битов. Наши простые схемы требуют только О(п) битов для представления каждого доверительного состояния, поэтому позволяют достичь компромисса, в котором выразительность принесена в жертву компактности. В частности, если происходит некоторое действие, одно из предусловий которого неизвестно, то результирующее доверительное состояние не будет точно представимым и результат действия также станет неизвестным.
Теперь необходимо решить, как должны действовать средства сбора информации с помощью датчиков. В данном случае имеются два варианта. Можно применить автоматический сбор информации с помощью датчиков, который означает, что на каждом временном этапе агент получает все доступные данные восприятия. В примере, приведенном на рис. 12.8, предполагается, что с помощью датчиков происходит автоматический сбор информации о местонахождении агента и наличии мусора в локальном квадрате. Еще один вариант состоит в том, что можно настаивать на использовании средств активного сбора информации с помощью датчиков, а это означает, что данные восприятия приобретаются только в результате выполнения конкретных действий по сбору информации с помощью датчиков, таких как CheckDirt и CheckLocation. Мы будем по очереди рассматривать каждый метод сбора информации с помощью датчиков.
Теперь сформулируем одно из описаний действия с использованием высказываний о знаниях. Предположим, что агент в мире "альтернативного двойного закона Мэрфи" перемещается с помощью действия Left, применяя автоматические средства сбора информации о наличии мусора в локальном квадрате; согласно правилам для этого мира, агент может оставить или не оставить за собой мусор, если квадрат был чистым. Этот результат, рассматриваемый как изменение физического состояния, должен быть дизъюнктивным, но если он рассматривается как результат изменения знаний, то просто сводится к тому, что у агента удаляются знания об истинности терма CleanR. Агент должен также знать, является ли истинным терм CleanL, получив эти знания тем или иным способом, поскольку для сбора информации о наличии мусора в локальном квадрате предусмотрены датчики; кроме того, агент знает, что он находится в квадрате AtL. Вся эта информация записывается следующим образом:
Action (Left, Precond: AtR
Effect: К (AtL) л -iK{AtR) л when CleanR: -K(CleanR) л when CleanL: К(CleanL) л
when -CleanL: K(CleanL)) (12.2)
Обратите внимание на то, что предусловия и условия when представляют собой простые высказывания, а не высказывания с оценкой знаний. Так и должно быть, поскольку результаты действий зависят от фактического состояния мира, но как мы могли бы проверить истинность этих условий, если все, что мы знаем, представляет собой доверительное состояние? Если агент знает истинность высказывания, например, К (AtR) в текущем доверительном состоянии, то это высказывание должно быть истинным в текущем физическом состоянии и, безусловно, соответствующее действие является применимым. Если же агент не знает истинность какого-то высказывания (например, условия CleanL конструкции when), то данное доверительное состояние должно включать миры, в которых терм CleanL является истинным, и миры, в которых CI eanL является ложным. Именно поэтому в результате данного действия возникает множество доверительных состояний. Таким образом, если начальным состоянием является (К (AtR) л К (CleanR) ), то после движения Left двумя результирующими доверительными состояниями становятся (К(AtL) л K(CleanL)) и (к(AtL) л K(-iCleanL) ). В обоих случаях истинностное значение терма CleanL известно, поэтому в плане может использоваться проверка терма CleanL.
При использовании активных средств сбора информации с помощью датчиков (в отличие от автоматических средств сбора информации с помощью датчиков) агент получает новые данные восприятия только после выдачи запроса на их получение. Таким образом, после перемещения с помощью действия Left агент не знает, является ли левый квадрат грязным, поэтому два последних условных результата больше не появляются в описании действия в уравнении 12.2. Чтобы узнать, есть ли в квадрате мусор, агент может выполнить действие CheckDirt следующим образом:
Action (CheckDirt, Effect: when AtL л CleanL: K(CleanL) л when AtL л —iCleanL: K(-iCleanL) л when AtR A CleanR: К (CleanR) л
when AtR A -CleanR: K(-CleanR) ) (12.3)
Можно легко показать, что выполнение действия Left, за которым следует действие CheckDirt, при организации работы с помощью активных средств сбора информации приводит к получению тех же двух доверительных состояний, к которым приводило действие Left при использовании организации работы с помощью средств автоматического сбора информации. При активном сборе информации всегда имеет место то, что физические действия отображают доверительное состояние в единственное доверительное состояние-преемник. Многочисленные доверительные состояния могут быть введены только с помощью действий по сбору информации датчиками, которые позволяют получить конкретные знания и поэтому дают возможность использовать в планах условные проверки.
Выше был описан общий подход к условному планированию на основе поиска в пространстве состояний AND—OR. Такой подход зарекомендовал себя как чрезвычайно эффективный применительно к некоторым контрольным задачам, но другие задачи оказались трудноразрешимыми. Теоретически можно доказать, что условное планирование принадлежит к более трудному классу сложности, чем классическое планирование. Напомним, что определение класса задач NP состоит в том, что потенциальное решение может быть проверено для определения того, действительно ли оно является решением, за полиномиальное время. Это определение относится к классическим планам (по крайней мере, к планам, имеющим полиномиальные размеры), поэтому задача классического планирования относится к числу NP-трудных. Но в условном планировании потенциальное решение должно быть проверено для определения того, что для всех возможных состояний существует некоторый путь через план, позволяющий достичь цели. Проверка такой комбинации "все/некоторые" не может быть выполнена за полиномиальное время, поэтому условное планирование труднее, чем NP. Единственный способ выхода из этой ситуации состоит в том, чтобы игнорировать некоторые из возможных непредвиденных ситуаций, которые могут рассматриваться на этапе планирования, и реагировать на них, только когда они действительно возникают. Именно этот подход рассматривается в следующем разделе.