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

Множество составных событий S - множество всех подмножеств элементарных событий Q.

Определим вероятностную схему домена планирования Р.

Для домена планирования Р вероятностная схема - тройка <𝛺, S, PROB>, где PROB - это распределение вероятностей, определяемое множеством пар <s, р>, в которых sÎS, р - вероятность появления события sÎS.

На множестве событий S представляет интерес подмножество событий U- "появление бесполезной подпоследовательности действий".

Множество событий U={𝜛 | ∀𝜛Î𝛺 𝜛(IS(lseq, mseq)) ≅ 𝜛(IS(mseq, rseq))}. Любое событие в U будем называть "появление бесполезной подпоследовательности действий".

Обозначим через подмножество событий U таких, которые определены на последовательностях заданной длины |seq|, а также на подпоследовательностях заданных длин |lseq|, |mseq|, |rseq|, где mseqÌseq.

Вероятность prob()ÎPROB - это вероятность того, что в произвольной последовательности seqÎSEQ собственная подпоследовательность mseqÌseq, для которой существует левая и правая подпоследовательности lseq и rseq, является бесполезной. Дадим этой величине приблизительную оценку 0 (prob()).

Приблизительная оценка 𝜃 основана на подсчёте суммы вероятности благоприятных исходов. Благоприятным исходом, считается следующее событие: для некоторого конфликта (согласия) по факту f в левом пучке найдётся подобный конфликт (согласие) по факту f в правом пучке.

Для некоторого взаимовлияния по факту f в левом пучке существует одно из пяти возможных взаимовлияний по факту f в правом пучке. То есть, число возможных исходов равно 5:

- исход: конфликт по факту f типа (f, ⌝f);

- исход: конфликт по факту f типа (⌝f, f);

- исход: согласие по факту f типа (f, f);

- исход: согласие по факту f типа (⌝f,⌝f);

- исход: отсутствие взаимовлияния по факту f;

Примечание. В скобках первый элемент факт f(⌝f) - это факт в эффекте некоторого действия mseq, которое состоит во взаимовлиянии с некоторым действием rseq, имеющим в предусловии либо факт f, либо факт -⌝f.

Из этих пяти исходов, для некоторого взаимовлияния в леном пучке, лишь 2 исхода являются благоприятными. Следовательно, вероятность благоприятного исхода для любого взаимовлияния в левом пучке произвольной последовательности seq равна: 2/5.

Определим теперь в произвольной последовательности seq среднюю мощность пучка взаимовлияний подпоследовательностей lseq и mseqÌseq: М |IS(lseq, mseq)|.

Пусть,

М|a| - среднее количество фактов в описании любого действия домена Р;

F - количество фактов, используемых в описании домена Р;

|lseq| - длина подпоследовательности lseq;

|mseq| - длина подпоследовательности mseq;

Тогда,

(1)

Здесь, abs-это операция, возвращающая модуль операнда.

Приближённая оценка вероятности G(prob( )), рассчитывается так:

(2)

В расчетах приблизительной оценки 𝜃, нигде не встречается длина правой подпоследовательности rseq. Это неявляется ошибкой, так как мощность левого пучка подпоследовательности mseq всегда не меньше мощности правого пучка.