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

Из теоремы 1.

следует, что для любого плана plan, не содержащего бесполезную подпоследовательность действий, существует такой вариант пошагового полного разрешения конфликтов, который приводит к

плану plan. Этот вариант не генерирует на некотором шаге последовательность seq, содержащую бесполезную подпоследовательность действий, так как plan не содержит бесполезной подпоследовательности действий. Утверждение доказано.

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

Эффективность алгоритма

TCRPA

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

В (1.2.4.) было показано, что решение задачи планирования требует экспоненциальных затрат памяти вычислительной системы. В связи с этим, представляется более эффективным использование техник, нацеленных преимущественно на сокращение емкостной сложности алгоритмов планирования. На практике это предположение, подтверждается тем, что алгоритмы, использующие представление пространства состояний без разделения [67, 43, 59], значительно эффективнее иных алгоритмов на ряде доменов планирования [25].

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

Обратимость домена планирования Р - это отношение

,

где - количество последовательностей длины содержащих бесполезные подпоследовательности действий, |SEQ,| - общее количество последовательностей длины 𝓁.

На основании (2.2.3), можно заключить, что существует некоторое целое число к такое, что если длина 𝓁>k, то обратимость равна 1.

Для данной задачи планирования Т, в которой имеется m=|SR| прототипов действий можно определить общее количество последовательностей длины 𝓁: ||=.

Вычисление | значительно сложнее. Общей формулы для различных доменов планирования не существует. Комбинаторный подход также не приемлем, так как при больших 𝓁, экспоненциально возрастает множество , в котором необходимо осуществить поиск последовательности с бесполезной подпоследовательностью действий. По сути, этот подход по сложности эквивалентен задаче планирования.

Определим | | вероятностным способом.

Множество элементарных событий 𝛺 = {𝜛 | 𝜛 = <IS (lseq, mseq), IS (mseq, rseq)>}, где mseqÌseq - некоторая собственная подпоследовательность действий seq, lseq - левая подпоследовательность для mseq, rseq - правая подпоследовательность для mseq, seq - некоторая последовательность в SEQ, IS -пучок взаимовлияний.