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

Начнём с примера, демонстрирующего особенности частично-упорядоченных планов.

Пусть, агенту необходимо выполнить несколько задач в комнате А, и несколько задач в комнате В (рисунок 6.)

Рисунок 6 - Иллюстрация к частично упорядоченным планам

Агент способен выполнять:

действия Aj, ., An, , ., Bm, которые доставляют, соответственно, факты (іÎ l .n) и (jÎ l m). Предусловие C() = IN(A), предусловие C() = IN(B).

действие GO (А), которое не имеет предусловий, но имеет в списке добавлений IN(A), а в списке удалений IN (В);

действие GO(B), которое не имеет предусловий, но имеет в списке добавлений IN(B), а в списке удалений IN (А).

Необходимо достичь цели G = {Рb ., Pn, , ., Qm}. Очевидно, что цель G может быть достигнута после исполнения плана

Plan = {GO(A); ; .; An; GO(B); ; .; Bm}.

Заметим, что порядок выполнения действий , и порядок выполнения действий не имеет значения, поскольку они выполняются в разных комнатах. Следовательно, план {GO(A), Аn; .; А1, GO(B), Bm, .; } будет эквивалентен вышеприведённому плану.

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

Введём несколько базовых определений для описания алгоритма SNLP.

Шаг плана - это пара <№, R>, где № - уникальный номер шага, R - некоторое правило.

Два разных шага могут соответствовать одному и тому же правилу. Таким образом, допустимы планы, содержащие более одного вхождения данного правила.

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

Причинная связь - это тройка <S, f, W>, где f - некоторый факт, W - шаг, имеющий в предусловии атом f, S - шаг, имеющий факт f в списке добавлений.

Угроза V для причинной связи <S, f, W> -это шаг, который либо добавляет, либо удаляет факт f, и при этом не является ни шагом S, ни шагом W.

Защитное ограничение - это отношение порядка "<", заданное на шагах плана, при этом S<W означает, что шаг S должен быть

выполнен до шага W, и наоборот, S>W означает, что шаг S должен быть выполнен после шага W.

Нелинейный план Plan = <ST, CL, SO>, где ST-множество шагов, CL - множество причинных связей, SC - множество защитных ограничений.

Топологическая сортировка нелинейного плана Plan - это линейная последовательность всех шагов, которая удовлетворяет следующим условиям:

первый шаг в последовательности - START;

последний шаг в последовательности - FINISH;

для каждой причинной связи <S, f, W> шаг S в последовательности предшествует шагу W;

для каждого защитного ограничения U<V шаг U в последовательности предшествует шагу V.

Топологическая сортировка нелинейного плана является решением, если применение последовательности действий шагов между шагами START и FINISH из начального состояния, которое задаётся списком добавлений шага START, приводит в состояние, в котором содержатся все предусловия шага FINISH.

) Нелинейный план является противоречивым, если на нём невозможно осуществить топологическую сортировку.

Из этого следует, что

противоречивый нелинейный план не является решением задачи планирования.

Алгоритм SNLP является систематичным в том смысле, что в процессе поиска, осуществляемого в пространстве частично-упорядоченных планов, один и тот же план или эквивалентные планы никогда не рассматриваются дважды.