Анализ методов интеллектуального планирования.

Планировщики, использующие такой способ представления пространства состояний, получили название дизъюнктивных планировщиков.

Дадим формальное определение понятию мьютекс.

Мьютекс - это отношение взаимоисключения между двумя узлами на одном ярусе. Существуют мьютексы между действиями и между фактами.

Мьютексы MXF - отношения взаимоисключения между

узлами-фактами < fn1, fn2>, где fn1 fn2 - узлы-факты, находящиеся на одном

ярусе, такие, что: либо, 1) все действия на предыдущем ярусе, добавляющие факт fn1|, удаляют факт fn2; либо, 2) все действия на предыдущем ярусе добавляющие факт fn2, удаляют факт fn1.

Мьютексы МХА - отношения взаимоисключения между

узлами-действиями <аn1 аn2>, где аn1 аn2 - узлы-действия, находящиеся на одном ярусе, такие, что: либо, 1) действие аn1 удаляет предусловие или же эффект действия аn2 либо, 2) предусловие действия аn1 и предусловие действия аn2 состоят в мьютексе mxf Î MXF.

Заметим, что мьютекс между парой узлов n1 и n2, может иметь место на некотором ярусе L, и не иметь место на некотором последующем ярусе L¢, С другой стороны, если между парой узлов n1 и n2 на некотором ярусе L не существует мьютекса, то и на последующих ярусах после L, пара узлов n1 и n2 не будут состоять в мьютексе.

Мьютексы превращают граф планирования в граф ограничений в смысле CSP-задачи. Метод, который используется для построения графа планирования, называется прямым распространением ограничений.

Пара ярусов фактов FLi и FLj - идентичны, если FLi и FLj содержат: 1) одинаковые факты, И 2) одинаковые мьютексы.

Граф Планирования PG

является стабилизированным, если существуют пара смежных ярусов фактов FLi и FLi+1 и FLj идентичен FLi+1.

Пусть граф PG стабилизирован, и имеется пара идентичных ярусов-фактов FLi, FLi+1 ÎPG. Тогда ярус фактов FLk ÎPG идентичен ярусу фактов FLi ÎPG, где k>iÎN.

Доказательство: Действительно, во-первых, из-за существования "nо-ор"-действий, факт f однажды появившись на некотором ярусе фактов, будет иметь место во всех последующих ярусах фактов. Во-вторых, множество фактов, которые могут быть созданы STRIPS-правилами конечно. Следовательно, должен существовать такой ярус фактов Q, содержащий факты, которые будут иметь место во всех последующих ярусах фактов. В-третьих, если два факта р и q, появившиеся на одном ярусе, не состоят в мьютексе, то и в последующих ярусах они также не будут состоять в мьютексе. Таким образом, должен существовать такой ярус фактов Р после Q, что все последующие ярусы фактов имеют множества мьютексов идентичные тем, что в Р. Утверждение доказано.

Цель G является разрешимой (достижимой) в 2-х случаях: 1) если она удовлетворяется тривиальным образом, т.е. компоненты цели G имеют место в начальном ярусе фактов, 2) если в графе PG существует подграф Plan, который состоит из множества путей, идущих от начального яруса фактов к ярусу фактов, содержащему G, и в этом множестве путей нет ни одной пары узлов, состоящих в мьютексе.

Пусть задача планирования Т имеет план длиной n .

План длиной n можно извлечь из графа планирования PG, содержащего n ярусов-действий [17].

Алгоритм GraphPlan возвращает "план не существует", только если цель G не достижима [17].

Алгоритм GraphPlan обладает полнотой [17].

Опишем алгоритм GraphPlan (рисунок 8.1., рисунок 8.2.).

В начале Graphplan формирует первичный ярус фактов FL0. Graphplan работает по стадиям (переменная t в алгоритме). В каждой стадии выполняется:

- расширение графа планирования PG,

- поиск плана в графе PG.

На этапе расширения графа PG на основе текущего яруса фактов создаётся новый ярус действий, а затем, на основе нового яруса действий, формируется новый ярус фактов. Во вновь сформированных ярусах выявляются мьютексы MXF и МХА (процедура Расширение Графа Планирования).

Graphplan строит частично-упорядоченный план. Извлечение плана осуществляется с помощью техники обратного хода от текущего яруса к начальному ярусу. Как утверждает автор Graphplan'a, эта техника позволяет более эффективно использовать информацию о мьютексах между действиями и фактами в графе PG.

Опишем эту технику.

Перед поиском плана Graphplan проверяет следующее условие: "справедливо ли, что GNcÍFLTCK и для каждой пары узлов gn1 , gn2 ÎGN и gn1, gn2Ïmxf, где GN-множество целевых фактов, ассоциированных с узлами на ярусе FLTCK "'.

Если это так, тогда возможно план существует, и Graphplan приступает к поиску.