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

Далее рассмотрим алгоритм планирования - Graphplan [17], который использует технику прямого распространения ограничений.

На момент своего создания (1994) Graphplan показал впечатляющие результаты для ряда тестовых задач классического планирования. По производительности он превзошёл планировщики Prodigy [53], UCPOP [42], SNLP'[37], TOCL, POCL, ТОРІ [9].

Создатели Graphplan'a Блюм и Фёст объясняют этот успех способностью Graphplan'a анализировать множество планов одновременно. Однако, как показал Камбхампати [29] производительность Graphplan'a объясняется тем, что он обрабатывает компоненты множества планов без разделения, используя уточнения дизъюнктивных планов.

Graphplan оказал сильное влияние на последующие работы в области планирования. Его алгоритм был модернизирован многими независимыми исследователями. На сегодня популярными постреализациями являются: 1) IPP (Interference Progression Planner) [33] - включена поддержка языка ADL, 2) STAN (STate ANalysis planner) [36] - повышена производительность в сравнении с GraphPlan'oM, 3) TGP (Temporal GraphPlan) [106] - добавлена возможность обработки темпоральных зависимостей, 4) SGP (Sensory)Graphplan принимает на вход стандартное STRIPS-описание задачи планирования и переводит это описание в компактную структуру, которая называется граф планирования (Planning Graf), из которой впоследствии извлекает частично-упорядоченный план. Важно отметить, что граф планирования это не граф состояний, который получается при работе планировщика в пространстве состояний.

Graphplan сочетает в себе свойства как планировщика в пространстве состояний, так и планировщика в пространстве планов. Т.е. он не обладает свойством малого связывания и при этом строит частично-упорядоченные планы.

При изложении Graphplan'a будем пользоваться терминологией из оригинальной работы [17].

Факты F - множество элементарных ППФ без переменных из домена планирования Р.

Перед основной стадией работы Graphplan создаёт множество действий, осуществляя для каждого правила RÎSR всевозможные варианты подстановки индивидов на места всех переменных. Имеется также специальный вид действия 'no-op' - "ничего не делать".

Действия Acts - множество полностью конкретизированных правил из SR, а также действие 'no-op'. Действие 'no-op' имеет предусловие C('no-op')=f, список добавлений А('по-op')=f, и пустой список удалений D('no-op')=0, где f- произвольный факт из F.

Граф планирования PG - ориентированный ярусный граф с двумя типами узлов и с тремя типами рёбер.

Два типа узлов в PG таковы: 1) FN - множество узлов, ассоциированных с фактами F, и 2) AN - множество узлов, ассоциированных с действиями Acts. Ассоциацию некоторого факта fÎF с узлом fnÎPG, будем обозначать как fn®f.

Ассоциацию некоторого действия act Î Acts с узлом anÎANÌ PG, будем обозначать как an®act.

Множество узлов PG разбито на непересекающиеся подмножества <FLo, ALo, FL1, AL1, . ALn.1 FLn>, где FL - ярус, содержащий узлы-факты, AL - ярус, содержащий узлы-действия, FL0 содержит узлы-факты, соответствующие фактам So-

Любой ярус ALiÌPG содержит узлы-действия an®act, такие что Nodes(C(act¬an))Î FLi и не существует fiii, fn2 eNodes(C(act<-an)) и <fr»i, fn2>eMXF, где Nodes(C(act<-an)) - узлы на ярусе FLi, ассоциированные, с фактами из предусловия C(act).

Любой ярус фактов FLiÌPG (i>0) содержит узлы-факты fn®f, такие что, для любого anÎ ALiÌPG справедливо (fÎD(act¬an) ИЛИ fÎA(act¬an)). Рёбра устанавливаются между узлами, расположенными на ярусах. Три типа рёбер PG таковы:

ребро-предусловие - устанавливается между узлом-фактом fh®f на некотором ярусе FLi и узлом-действием an®act на ярусе ALi , если факт fÎC(act);

ребро-добавление - устанавливается между узлом-действием an->act на некотором ярусе ALi и узлом-фактом fh®f на ярусе FLi+1, если f ÎA(act);

ребро-удаление - устанавливается между узлом-действием an®act на некотором ярусе ALi и узлом-фактом fn®f на ярусе FLi+1, если f ÎD(act).

Из определения видно, что ярусы PG чередуются так: ярус фактов | ярус действий и т.д. Первый ярус графа содержит факты, характеризующие начальное состояние. Ярусы в PG от самого первого до последнего содержат:

По сути, граф планирования PG позволяет представлять пространство состояний без разделения. Точнее, множество состояний хранящиеся совместно, например, на ярусе FLi+1, получаются в результате всевозможных альтернативных вариантов применения действий, расположенных в ярусах ALi по ALj (i<j), к некоторому состоянию s, представленному на ярусе фактов FLi. Однако, ясно, что альтернативная перестановка к действий может привести к тому, что одно из действий может удалять эффект, либо предусловие другого действия. Для обработки подобных ситуаций используются, так называемые мьютексы между действиями и мьютексы между фактами. Это позволяет при необходимости, например, на этапе извлечения плана, выделить из графа PG альтернативные компоненты пространства состояний.