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

Суть поиска плана сводится к тому, чтобы от целевых фактов в текущем ярусе GNÍFLTCK, выделить путь, ведущий к ярусу FL0. В пути не должны содержаться мьютексные действия. На основе выделенного пути формируется план.

Более точно происходит следующее.

Изначально формируется множество GS - хранилище (под)целевых наборов GS i t. GS i t - множество целей, выбираемые из яруса фактов с номером і, при поиске плана на стадии t. Начиная с текущего яруса FLi (вначале i=t) в GS i t заносятся целевые факты GNÍFLi. Далее на ярусе действий с номером і-l выделяются всевозможные комбинации действий (Аcomb), доставляющие GS i t (множество Comb). Устанавливается подцель GS i-1 t, в которую помещаются предусловия выделенных действий, расположенные на ярусе фактов FLm. Для каждой из комбинаций действий АcombÍComb процесс продолжается рекурсивно, до тех пор, пока GS i-1 t окажется тривиально разрешимой, либо не найдётся комбинации действий, доставляющей GS i-1 t, т.е. Comb = Æ.

Если подцель GS i-1 t оказывается разрешимой, то при возврате из рекурсии в план Plan помещаются тройки < GS i-1 t, Acomb, GS i t , в которой для каждого действия из Acomb, известно какие (под)цели из GSit достигает действие, и какие цели из GS i-1 t необходимо достичь, прежде чем выполнить действие. Для получения линейного плана необходимо выполнить топологическую сортировку нелинейного плана Plan, с учётом целевых ограничений GSit.

Рисунок 8.1 - Алгоритм GraphPlan

Рисунок 8.2 - Алгоритм GraphPlan

Опишем ещё одну незначительную, но интересную особенность Graphplan'a.

В практической реализации алгоритма для повышения эффективности обратной техники извлечения плана, используется хеширование. В хеш-таблице на каждой стадии t запоминаются целевые наборы GSit , которые оказались НЕ разрешимыми в ярусе фактов і. На каждой стадии при поиске плана проверяется наличие в хэш-таблице разрешаемой подцели GS i-1 t . Если подцель GS i-1 t в хеш-таблице, то поиск плана немедленно прекращается, и исходная цель GSit, также помещается в хеш, как неразрешимая.

Постановка задачи

В настоящей главе дана постановка задачи интеллектуального планирования при классических допущениях. Показано, что задача планирования даже в простых случаях является PSPACE-полной. В связи с чем, большинство исследований посвящено поиску эффективных алгоритмов, решающих эту задачу.

Анализ работ в области интеллектуального планирования при классических допущениях позволяет выделить следующие подходы:

)планирование как доказательство теорем;

)планирование как поиск в пространстве состояний;

)планирование как поиск в пространстве планов;

)иерархическое планирование;

)планирование как CSP-задача, SAT-задача, ILP-задача, BDD-задача;

В качестве ключевых работ в области классического планирования следует отметить: STRIPS [24] - решение проблемы фрейма, SNLP [37] - доказательство полноты алгоритма частично-упорядоченного планирования, GRAPHPLAN [17] - значительное повышение производительности за счёт использования техники удовлетворения ограничений, SATPLAN [32] - использование эффективных методов решения задачи выполнимости пропозициональных формул, HSP [18] - для повышения скорости поиска планов использована эвристика, извлекаемая из описания задачи планирования.

Планирование является основой моделирования целенаправленного поведения. Поэтому поиск новых идей, которые позволили бы увеличить скорость синтеза планов, сохранит высокую степень актуальности в ближайшем будущем.