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

Если входная последовательность seq не содержит конфликты, то seq является планом и ITPA возвращает seq.

Алгоритм ITPA можно улучшить.

Планирование на основе полного разрешения конфликтов

Напомним, что в плане любая пара действий, состоящих во взаимовлиянии, согласована. Этот факт можно использовать для поиска планов.

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

Разрешение конфликта cf=a⬍f⬍𝜒ÎCF(seq) - это обычное преобразование взаимовлияния a⬍f⬍𝜒ÎINT(seq) таким действием b', что: (fÎpre(b') или f∨⌝fÎpre(b')) и ⌝fÎeff(b').

Действие b' будем называть действием, разрешающим конфликт cf, или просто разрешающим действием.

Действия a и 𝜒 будем называть родительскими действиями для действия b'.

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

Поскольку заранее неизвестно, какой из вариантов разрешения конфликтов приведёт к плану, то необходимо учитывать все варианты разрешения конфликта.

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

Определим операцию разрешения всех конфликтов в последовательности.

Разрешение всех конфликтов CF(seq) будем называть полным разрешением конфликтов в последовательности seq. Полное разрешение конфликтов обозначим: ResolveAll (seq).

RESseq - множество последовательностей, возвращаемое операцией ResolveAll (seq).

Пусть ко всем конфликтам последовательности seq применяется операция полного разрешения, RESseq =ResolveAll (seq).

Сформулируем и докажем теорему, которая показывает возможность использования операции полного разрешения конфликтов для поиска планов.

Пусть имеется последовательность seq, не являющаяся планом, и последовательность plan, являющаяся некоторым конкретным планом.

Приведём теорему 1 описанную в [59].

Теорема 1.

Полное разрешение конфликтов последовательности seq такое, что ħ(seq)=plan и seq≠plan возвращает одну и только одну последовательность resÎ RESseqÌSEQ такую, что ħ(res)=plan, либо res≅plan.

Доказательство:

А. Докажем существование последовательности действий res, такой что ħ(res)=plan.

Рассмотрим произвольный конфликт cf=a⬍f⬍𝜒Î CF(seq).

. В соответствии с основным положением ħ(seq)=plan, существуют действия ħ(a)=a', ħ(𝜒)=𝜒' где a',𝜒'Îplаn Напомним, что в плане не существует конфликтных действий. Следовательно, должно существовать некоторое действие b', не позволяющее конфликтовать паре действий ħ(a)=a' и ħ(𝜒)=𝜒', такое, что: a'<b'<𝜒'Îplan.

. По определению полного разрешения конфликтов некоторая последовательность resÎRESseq содержит действие b"Îres, которое подобно b'Îplan и является действием, разрешающим конфликт cf=a⬍f⬍𝜒Î CF(seq).Заметим, в множестве результирующих последовательностей RESseq имеются всевозможные варианты расположения b" между действиями ħ(a'')=a и ħ(𝜒")=𝜒, где a",𝜒"Îres.