Разработка алгоритмов планирования

Описание задачи планирования

Пусть:

L - язык исчисления предикатов первого порядка;

Р

= <, SR> - домен планирования;

Т = <Р, G> - задача планирования с классическими допущениями.

Введём определение. Факт f - это элементарная ППФ f из L без функциональных символов, либо отрицание f- Øf, либо дизъюнкция - fÚØf.

Далее, вместо термина "правило" будем употреблять формально-эквивалентный термин "действие".

Во избежание трудностей, введём некоторые ограничения на описание домена планирования Р:

) для каждого действия RÎSR:

а) предусловие C(R) задаётся множеством фактов типа f или Øf;

б) список добавлений A(R) и список удалений D(R) задаётся множеством фактов типа f;

в) A(R)ÇD(R) = Æ.

) Состояние s и цель G задаются множеством фактов типа f или Øf.

Для простоты изложения будем полагать, что каждое действие RÎSR полностью конкретизировано, то есть для каждого действия RÎSR выполнены всевозможные подстановки индивидов на места переменных.

Любое действие RÎSR описано безотносительно к некоторому состоянию, к которому может быть применено. Действие RÎSR будем называть действием-прототипом.

Создадим бесконечное множество экземпляров действий Аexe. Каждый экземпляр снабдим уникальным идентификатором.

Экземпляр действия aexeÎAexe=<id, R>, где RÎSR -действие-прототип, которому соответствует действие-экземпляр, id -уникальный идентификатор действия-экземпляра.

Пара экземпляров действий aexe и bexe подобны, если соответствуют одному и тому же прототипу RÎSR. Подобие действий-экземпляров обозначим aexe ~ bexe .

Под проверкой применимости действия будем понимать проверку выполнимости предусловия некоторого экземпляра действия aexeÎAexe, соответствующего прототипу R в конкретном состоянии s.

Сформируем множество всевозможных последовательностей действий-экземпляров SEQ.

Множество SEQ - множество всевозможных последовательностей действий-экземпляров. Длину некоторой последовательности seqÎSEQ обозначим через |seq|.

Отношение полного порядка, заданное на множестве действий некоторой последовательности seqÎSEQ будем называть отношением предшествования, и обозначать так: <.

Предположим, что в некоторой последовательности seqÎSEQ имеет место: aexe <cexe Однако, возможно, что существует действие bexe Îseq такое, что aexe<bexe и bexe<cexe.

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

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

Введём для этих гипотетических множеств действий следующие обозначения - соответственно start и finish. Пополним множество SEQ этими действиями.

Действие start = <С=Æ, A=s0, D=Æ>. Действие finish = <С=G, А=Æ, D=Æ>;

Добавим действие start в начало каждой последовательности множества SEQ, а finish в конец каждой такой последовательности. Последовательность (start, finish) Î SEQ будем называть начальной, и обозначать init. Нумерацию элементов последовательности seq будем вести, начиная с нуля. nÎN будем использовать для обозначения конечного элемента последовательности seq.