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

Опишем алгоритм SNLP (рисунок 7.)

На вход процедуры подаётся множество правил ΣR, а также,

нелинейный план Plan, не обладающий полнотой, который содержит шаги START и FINISH. Далее Plan уточняется путём добавления причинных связей и защитных ограничений, до тех пор, пока не обнаружится такое уточнение, что план либо противоречив, либо обладает полнотой.

Для случая абстрактного планирования, приведённая процедура может быть расширена следующим образом. Необходимо создать иерархию утверждений, которая будет отражать трудность достижения тех или иных условий. Для этого каждому утверждению сопоставляется некоторое число, характеризующее его иерархический уровень. Малые числа могут указывать на низкий уровень иерархичности, большие числа - на высокий уровень иерархичности. Для того чтобы процедура удовлетворяла предусловия, спускаясь с вершины иерархии утверждений, в процедуре SNLP на шаге 3 и 4 можно осуществлять выполнение пунктов а) и b), не произвольным образом, а с учётом более иерархичного предусловия f вовлечённого в причинную связь.

Рисунок 7 - Алгоритм SNLP

Очень часто нелинейные планировщики называют планировщиками, обладающими малой связностью (least commitment).

Неформальный принцип малой связности утверждает, что планировщику следует всегда осуществлять сначала выбор таких действий, которые его меньше связывают. Частичная подстановка - один из примеров малого связывания. Так, при поиске плана можно начать с анализа последствий более конкретного действия, например, MOVE (A, В), а можно выбрать менее связывающее действие, например, MOVE (А, х), где х - некоторая переменная, вместо которой можно подставить любой объект. Нелинейность ещё один пример малого связывания, например, можно выбрать действие Put (А, х) в качестве первого шага плана, с другой стороны, мы можем предположить что Put (А, х) появляется где-то в середине плана без точного указания места.

Однако принцип малой связности не гарантирует нелинейным планировщикам значительного превосходства над линейными .

Планирование как задача удовлетворения ограничений

Многие задачи в ИИ, а также в других областях информатики, могут

быть рассмотрены как задачи удовлетворения ограничений [34, 39], для которых существует множество высокопроизводительных алгоритмов. В связи с этим стала популярной формулировка задачи планирования, как задачи удовлетворения ограничений [28, 32, 17].

CSP-задача предъявляет требования к переменным в форме ограничений. Множество возможных значений переменных конечно, и называется доменом. Ограничения указывают, какие кортежи значений допустимы для определённого множества переменных. Ограничение может быть задано явно, путём перечисления допустимых кортежей или неявно, в форме алгебраического выражения. Решением CSP-задачи является такое означивание переменных, при котором учтены все ограничения.

Задача удовлетворения ограничений - это тройка <V, D, С>, где:

V = {, ., vn} -множество переменных.

D = {D1 ., Dn} - множество доменов. Каждый домен D; - конечное множество, содержащее возможные значения, соответствующей переменной.

С = {, ., } - множество ограничений. Ограничение С - отношение, определённое на подмножестве всех переменных, то есть x .xDn Ê .

Заданное (частичное или полное) означивание переменных удовлетворяет ограничению Q, если каждая переменная получила такое значение, что соответствующий кортеж значений принадлежит . Множество всевозможных означиваний всех переменных является пространством, содержащим решение CSP-задачи.

Решением CSP-задачи является такое означивание всех переменных, при котором все ограничения удовлетворены. Если для некоторой задачи имеется, по крайней мере, одно решение, то задача является разрешимой, иначе неразрешимой, или же противоречивой, или же переограниченной.

В некоторых случаях необходимо получить все решения. Иногда, может быть сформулирована задача ограниченной оптимизации, а именно: найти такое решение, в котором значения переменных оптимизировали бы некоторый заданный функционал. Иногда необходимо просто выяснить, разрешима ли задача. В любом случае вычислительная сложность CSP-задачи NP-полная .