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

Планирование за конечное время

Затронем вопрос о конечности алгоритма в случае не существования плана.

Если для задачи планирования Т не существует решения, тогда для начальной последовательности init невыполнимо утверждение ħ(init)=plan. Из-за этого алгоритм CRPA будет работать бесконечно. Другими словами, говоря, последовательность init содержит конфликты, которые не могут быть преобразованы к некоторому множеству согласий путём пошагового преобразования конфликтов. Иначе говоря, последовательность init несогласуема. Определим понятие несогласуемой, последовательности в общем случае.

Некоторую последовательность seqeSEQ такую, что CF(seq)≠∅ будем называть несогласуемой последовательностью, если не существует последовательности seq'ÎSEQ такой, что ħ(seq)=seq' и CF(seq')≠∅.

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

Утверждение 4

. Любая последовательность resÎRESseq, полученная из несогласуемой последовательности seq на основе полного разрешения конфликтов также несогласуема.

Доказательство.Разрешение конфликтов в несогласуемой последовательности seqÎSEQ не добавляет какие-либо новые последовательности в SEQ. По определению следует, что любая последовательность resÎRESseq действительно несогласуема.

Утверждение доказано.

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

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

Назовём модифицированный алгоритм CRPA, завершающийся за конечное время, - TCRPA (terminating CRPA).

Рис.12 - Алгоритм TCRPA

Так же как и в алгоритме CRPA, изначально на вход TCRPA подаётся начальная последовательность init. К любой входной последовательности, при рекурсивном вызове, применяется полное разрешение конфликтов. Докажем конечность TCRPA.

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

Теорема 3.

а) Если существует решение задачи планирования Т, то TCRPA вернёт некоторый план за конечное число шагов.

б) Если не существует решения задачи планирования Т, то TCRPA вернёт 0 за конечное число шагов.

Доказательство:Если план существует, то TCRPA найдёт его, так как CRPA находит.

Если план не существует, то начальная последовательность init несогласуема. Тогда, в соответствии с утверждением 2. рано или поздно в любом из вариантов пошагового полного разрешения конфликтов init появится бесполезная подпоследовательность действий. D этом случае TCRPA завершит работу вернув 0. Теорема доказана.

Приведём сформулированное в [59]

утверждение 5.

Утверждение 5.

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

Доказательство:Из пункта 1 алгоритма TCRPA вытекает, что если входная последовательность содержит бесполезную подпоследовательность, то даже если она является планом, алгоритм TCRA вернёт 0.

Из пункта 2 TCRPA вытекает, что если входная последовательность не содержит бесполезную подпоследовательность и является планом, то TCRPA вернёт её.