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

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

Кроме того, это свойство позволило бы существенно снизить нагрузку на вычислительную систему, осуществляющую планирование.

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

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

Минимальный план planÎSEQ не содержит бесполезной подпоследовательности действий.

Доказательство:Предположим, plan содержит бесполезную собственную подпоследовательность действий mseq. Удалим бесполезную подпоследовательность действий из plan: plan' =Remove(plan,mseq↻). Получившаяся последовательность plan' также является планом, однако, содержит меньшее количество действий, чем plan. То есть, предположение неверно. Следовательно, plan не содержит бесполезную последовательность действий. Утверждение доказано.

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

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

Существует план, не содержащий бесполезную подпоследовательность действий, и не являющийся минимальным.

Доказательство:Приведём один пример, доказывающий утверждение. Пример.

Пусть дано:

В домене планирования Р существуют действия-прототипы: с эффектом eff()={ f1, f2}; действие а2, с эффектом eff (а2)= { f1}; действие а3 с эффектом eff(a3)={f2}.

В домене планирования Р возможно существование прочих действий, но не имеющих в своём описании фактов f1, f2, f3.

Предположим теперь, что существуют:

) Два неизоморфных плана Plan1 и Р1аn2, не содержащие бесполезные подпоследовательности действий.

Plan1 и Plan2 содержат схожие множества взаимовлияний (согласий), то есть каждому согласию по некоторому факту f в Plan1 можно однозначно сопоставить согласие по факту f в Plan2.

В Plan1 имеется пара согласий cs11 и cs12, соответственно по фактам f1 и f2 - cs1 и cs2 расположены на одном интервале влияния.

В Plan2 имеется пара согласий cs21 и cs22, сходная соответственно с cs11и cs12.

Тогда, возможно, что в плане Plan1 в согласиях cs11 и cs12 левым членом является действие В то время как в плане Plan2 в согласиях cs21 и cs22 левыми членами являются, соответственно, действия и - Из этого ясно, что в схожих согласиях в различных планах, в общем случае, может участвовать различное количество действий. То есть Plan1 и Plan2 могут содержать различное количество действий, несмотря на схожее множество взаимовлияний. Следовательно, один из планов не является минимальным. Утверждение доказано.

Планирование на основе преобразования взаимовлияний

Опишем алгоритм поиска планов в множестве SEQ, который использует понятие взаимовлияния действий в последовательности. Назовём его ITPA (interference transformation planning algorith).

Рис. 10 - Алгоритм ITPA

Изначально на вход алгоритма ITPA подаётся начальная последовательность initÎSEQ, содержащая наименьшее количество действий. На выходе алгоритма ITPA получается план.

В основе алгоритма ITPA лежит переход от текущей, поданной на вход последовательности seq, к рассмотрению одной из последовательностей itsÎITS, в которой множество взаимовлияний INT(its) отличается (не подобно) от множества взаимовлияний INT(seq).