В 1995 году Эврим Блюм (Avrim Blum) и Меррик Фурст (Merrick Furst) предложили новый подход к задаче планирования [Blum, Furst, 1995]. В основе нового метода лежит построение и анализ специальной структуры, которую авторы назвали "граф планирования" (Planning Graph). Алгоритм планирования Graphplan является полным и корректным. Он возвращает частично-упорядоченный план (кратчайший или близкий к нему) или извещает об отсутствии плана. Кроме того, алгоритм не чувствителен к порядку объявления целей в задаче планирования.
Следует отметить, что в данном обзоре описывается оригинальный алгоритм Graphplan, предложенный авторами в 1995-ом. Этот алгоритм работает с языком описания задач планирования, оперирующих только конъюнкциями высказываний. Во многих более поздних источниках ([Weld, 1999][Russel, Norwig, 2003]) про Graphplan пишут как про планировщик, оперирующий литералами (в том числе и отрицательными). Описание с литералами охватывает больший спектр задач, более прозрачно и удобно для учебных целей, но мы будем придерживаться точной исторической позиции.
Прежде чем начать поиск плана, Graphplan строит граф планирования (не следует путать "граф планирования" и "граф, описывающий пространство состояний"). Этот граф описывает задачу планирования таким образом, что многие ограничения, неявно присутствующие в постановке задачи, становятся явными, что позволяет сократить пространство поиска. Граф планирования строится за полиномиальное время и имеет полиномиальный размер.
Graphplan использует граф планирования для управления поиском плана. Алгоритм сочетает в себе особенности планировщиков с частичным (partial-order) и полным (total-order) упорядочиванием шагов. Как и полностью-упорядочивающие алгоритмы Graphplan использует сильное связывание для позиционирования действия в плане — каждое действие привязывается к конкретному моменту времени (используется дискретная ось времени, отсчет ведется от единицы). С другой стороны, аналогично частично-упорядочивающим планировщикам Graphplan генерирует планы, в которых с одним моментом времени может быть сопоставлено несколько действий. Семантика этого множественного сопоставления заключается в том, что данный набор действий допустимо упорядочить любым образом (то есть приходим к частичному порядку).
Graphplan, будучи всего лишь средством демонстрации новой идеи, работает с ограниченными STRIPS-описаниями задач планирования. Ограничение заключается в том, что эффекты и предусловия действий могут быть лишь конъюнкциями высказываний [прим. 1]. Это же ограничение относится и к определению начального условия [прим. 2] и цели. Как и в STRIPS, эффект представляется в виде списков добавления и удаления. Кроме действий, непосредственно описанных в домене, вводятся специальные действия с семантикой "ничего не делать"; авторы называют их no-op или frame action [прим. 3]. Задача этих действий — трансляция высказываний во времени (напомним, что каждое действие привязано к какому-либо моменту времени и его предусловия должны выполняться именно в этот момент). Для высказывания prop действие no-op будет иметь в качестве предусловия prop, в качестве списка добавления prop, а список удаления будет пустым.
Как уже упоминалось, несколько действий может происходить в один и тот же момент времени, если они не противоречат друг другу (interfere). Два действия считаются противоречивыми, если одно из них удаляет литерал, который либо является предусловием другого действия, либо добавляется этим другим действием [прим. 4]. В линейном плане действия, сопоставленные одному моменту времени, могут быть упорядочены произвольным образом.
Теперь рассмотрим подробнее устройства графа планирования в планировщике Graphplan, а затем перейдем к изучению алгоритма.
Устройство графа планирования
Граф планирования — это ориентированный многоуровневый граф с двумя видами вершин и тремя видами дуг. Уровни в графе бывают двух видов:
Уровни в графе чередуются. Первым уровнем является уровень высказываний. Он содержит все высказывания, определяющие начальное состояние. Таким образом, уровни в графе представляют собой следующую последовательность:
Дуги графа отражают связи между высказываниями и действиями. "Узлы действий" на уровне действий i связаны:
Действие может появиться на уровне действий i, если все его предусловия содержатся на i-ом уровне высказываний.
Высказывание появляется на уровне высказываний i+1, если оно добавляется каким-либо действием на уровне действий i (даже если на том же уровне есть действия, удаляющие это высказывание). Т.к. всегда есть действие no-op, все высказывания уровня i, появятся также и на i+1 уровне. Т.к. все высказывания уровня i всегда транслируются на уровень i+1, то и все действия уровня i также транслируются на уровень i+1 (их предусловия транслируются, следовательно, действия допустимы).
Граф планирования допускает противоречивость действий, происходящих в один момент времени. Корректный план этого не допускает. Но корректный план является подграфом данного графа и его можно искать в графе планирования. Но прежде, чем начинать поиск, Graphplan осуществляет анализ графа планирования с целью обнаружения взаимно исключающих действий и высказываний. Т.е. накладываются дополнительные ограничения, позволяющие сократить пространство поиска.
Анализ графа планирования
Анализ графа планирования заключается в выявлении и распространении (propagate) отношений взаимного исключения (mutual exclusion или сокр. mutex) между узлами. Два действия на одном уровне действий считаются взаимно исключающими, если нельзя построить корректный план, содержащий оба этих действия на данном уровне. Два высказывания на одном уровне высказываний считаются взаимно исключающими, если не существует корректного плана, в котором оба высказывания могли бы стать истинными.
Graphplan устанавливает отношения взаимного исключения, используя несколько простых правил. Правила не гарантируют нахождение всех таких отношений, но обычно находят большую их часть. Для действий таких правил два.
Для высказываний правило одно.
Алгоритм
Сначала алгоритм строит граф планирования, содержащий только один уровень высказываний, соответствующий начальному состоянию задачи планирования. Затем выполняется расширение графа планирования (этот шаг детально описан ниже) до тех пор, пока не будет найден уровень высказываний, в котором присутствую все высказывания, задающие цель, при условии, что между ними нет отношений взаимного исключения.
Далее алгоритм представляет собой циклический процесс. На каждом шаге цикла выполняется два действия — поиск в новом графе и очередное расширение графа. На каждом шаге i, осуществляется поиск плана длиной i. При этом алгоритм может найти план (и тогда осуществляется выход из цикла) или определить, что цель пока достичь не удастся. Если план не найден, то выполняется попытка найти решение в графе с большим числом уровней. Для этого строится i-ый уровень действий и i+1 уровень высказываний. Циклический процесс повторяется до тех пор, пока не выполнится одно из следующих условий:
Рассмотрим подробнее каждое из действий, выполняющихся в цикле.
Расширение графа планирования
Для конструирования i-ого уровня действий выполняется следующее. Для каждой схемы действий и каждого способа означивания его предусловий посредством высказываний из уровня i добавляем "узел действия", если никакая из пар (использовавшихся для означивания) высказываний не помечена как взаимно исключающая. При добавлении действий сразу добавляются "дуги-предусловий". Кроме действий, основанных на схемах домена, для каждого высказывания добавляются действия no-op. Затем каждый "узел действия" проверяется на взаимное исключение с другими узлами уровня в соответствии с вышеупомянутыми правилами, и для каждого действия создается список "несовместимых действий" (в оригинале, actions-that-I-am-exclusive-of).
Порождение i+1 уровня высказываний осуществляется следующим образом. Просматриваются списки добавления всех действий в новом уровне действий (включая действия no-op) и из этих высказываний строится уровень. Затем устанавливаются соответствующие "дуги-добавления" и "дуги-удаления". Два высказывания помечаются как взаимно исключающие, если все способы достижения первого исключают все способы достижения второго.
Поиск плана
Graphplan ищет план в заданном графе планирования, используя стратегию "обратной цепочки рассуждений" (backward-chaining). Применяется поуровневый поиск для того, чтобы воспользоваться ограничениями взаимного исключения. В частности, для заданного множества целей в момент времени t Graphplan пытается найти множество действий (включая no-op) в момент t-1, содержащих эти цели в списках добавления. Предусловия этих действий формируют новое множество целей для момента t-1. Если цели уровня t-1 будут достигнуты, то будут достигнуты и цели уровня t. Если же цели уровня t-1 недостижимы, то на уровне t выбирается другое множество действий для достижения целей уровня t. Этот процесс продолжается до тех пор, пока либо не будет найдено решение, либо не будет доказано, что изначальное множество целей недостижимо.
Для реализации этой стратегии используется рекурсивный алгоритм поиска. Для каждой цели в момент t выбирается действие в момент t-1, достигающее эту цель. При этом контролируется, чтобы выбранные из уровня t-1 действия не были взаимно исключающими. Предусловия выбранных (на t-1 уровне) действий формируют множество новых целей из высказываний уровня t-1. Эти высказывания также не должны быть взаимно исключающими. После этого выполняется рекурсивный вызов с новым множеством целей. Если рекурсивный вызов приводит к откату, то апробируется другое множество действий, пока не будут перебраны все возможные множества.
Для ускорения поиска авторы использовали кэширование тупиковых ситуаций. Авторы назвали этот механизм memoization (не путать с memorization). Всякий раз, когда доказывается невыполнимость некоторого подмножества целей в некоторый момент времени t, эта информация (множество подцелей и момент времени) запоминается в хэш-таблице. При дальнейшем поиске (например, при выборе других действий на уровне i > t, приводящих к тому же множеству подцелей на уровне t), прежде чем начать проверку множества целей в момент t, Graphplan проверяет по хэш-таблице, не является ли это множество недостижимым. Если по таблице множество оказывается невыполнимым, то откат выполняется сразу.
Остановка алгоритма при решении неразрешимых задач
На каждом шаге цикла алгоритм проверяет, существует ли корректный план. Если план существует, то выполняется выход из цикла. Иначе осуществляется попытка выполнить еще одну итерацию цикла (дополнить граф планирования еще одним уровнем и поискать с учетом этого уровня). Однако если мы решаем неразрешимую задачу, то необходимо избежать зацикливания. Авторами предлагается простой тест, позволяющий, в конечном счете, выявить факт неразрешимости задачи.
Легко показать, что граф планирования в некоторый момент времени достигает такого уровня высказываний P, после которого все последующие уровни высказываний будут точно такими же, как и P. То есть они будут содержать одинаковые множества высказываний и отношения взаимного исключения между высказываниями. Говорят, что граф планирования стабилизируется или выравнивается (level off).
Утверждение о том, что граф, в конечном счете, стабилизируется, справедливо по следующей причине. Благодаря no-op, всякое высказывание, однажды появившись на некотором уровне, будет присутствовать и на всех последующих уровнях. Так как мы рассматриваем конечные множества высказываний, существует уровень Q, после которого множество высказываний в уровне перестанет изменяться. Это происходит, когда предыдущий уровень действий не добавил новых высказываний. Перестает изменяться также и количество действий, так как нет новых предусловий. С другой стороны, если на каком-либо уровне высказывания x и y не были помечены как взаимно исключающие, то и на следующих уровнях они не будут взаимно исключающими. Начиная с уровня Q до некоторого уровня P количество взаимных исключений (как между высказываниями, так и между действиями) будет монотонно убывать (Q <= P). Так как количество взаимных исключений конечно, этот процесс остановится. Начиная с уровня P ни множество высказываний, ни множество действий, ни множество взаимных исключений не будет изменяться.
Обозначим Pn первый уровень высказываний, на котором граф стабилизировался. Проверка на неразрешимость задачи состоит из трех утверждений.
Библиография
| [Blum, Furst, 1995] |
Blum A., Furst M.L., Fast Planning Through Planning Graph Analysis. IJCAI'95, 1995, стр. 1636-1642. |
| [Russel, Norwig, 2003] | Russell S., Norwig P., Artificial Intelligence: A Modern Approach, (2ed). Prentice Hall, 2003. |
| [Weld, 1999] | Weld D.S., Recent Advances in AI Planning. AI Magazine № 20, том 2, стр. 93-123, 1999. |
| [Knoblock, 1994] | Knoblock C., Generating parallel execution plans with a partial-order planner. AIPS'94, стр. 98–103, 1994. |
Примечания
1. Позднее, это ограничение было ослаблено до конъюнкции литералов, а затем и до более сложных конструкций, допускающих кванторы, условные эффекты и др.
2. В оригинальной статье про начальные условия написано ”a set of propositions (literals) called the Initial Conditions”. Речь, конечно, идет о высказываниях, а не литералах. Нет смысла использовать в начальном состоянии отрицательные литералы, если все предусловия и цели могут состоять только из высказываний (положительных литералов). Ясно также, что авторы не предполагают возможность замены в тексте этих понятий с целью обобщения подхода. Промежуточные состояния также содержат только высказывания, т.к. в Graphplan списки добавления состоят только из положительных литералов.
3. В другой литературе используется также maintenance action и persistence actions.
4. Крейг Ноблок (Craig Knoblock) в [Knoblock, 1994] предлагает менее жесткое ограничение. Два действия могут происходить в один и тот же момент времени, даже если одно из них удаляет литерал, который добавляется вторым действием, при условии что этот добавляемый литерал является побочным эффектом (не связан каузальной связью с какой-нибудь подцелью). При линеаризации эта «противоречивость» исчезает.
Трофимов И.В.
июль 2006