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

Таким образом, в любой последовательности seqÎSEQ начальное действие =start, конечное действие =finish. Действие start всегда применимо.

Опишем алгоритм APL применения последовательности действий seq=(a0, ., ai, ai+1, ., an)ÎSEQ:

APL

вход

:

seq

выход

:

DM=<so, s1 ., sn>

. начиная с a0Îseq последовательно для каждого применимого действия aÎseq

применить

a

к s0

На вход APL подаётся последовательность действий seq. Первое действие a0 всегда применимо и формирует начальное состояние s0. В результате работы APL возвращает динамическую модель среды DM - последовательность состояний <s0, s0, ., sn>, в которой каждое состояние st

(t=0 n) получено применением действия atÎseq.

Последовательность seq называется полностью применимой, если каждое действие atÎseq применимо. Иначе, последовательность seq называется не полностью применимой.

Полностью применимая последовательность действий является решением задачи планирования Т, если состояние sn, полученное в результате применения последнего действия an Î seq, является целевым состоянием, то есть GÌsn.

Задача планирования - это задача поиска в множестве SEQ полностью применимой последовательности действий, которая преобразует начальное состояние s0 в snÉ G, где G - цель задачи планирования.

Взаимовлияние действий: конфликты и согласия

Определения, данные в предыдущем разделе, позволяют рассмотреть

отношения между действиями в последовательности.

Взаимовлияние по факту между действиями a,χ,βÎseq, где a< χ, имеет место, если:

l)fÎΦ(a)

2)fÎΦ(χ)

3) не существует действия βÎseq такого, что a<β<χ и (f(⌝f)Îeff(β) либо f(⌝f)Îeff(β))

Взаимовлияние будем обозначать a⬍f⬍χ. INT(seq) - множество взаимовлияний последовательности seq.

Пара взаимовлияний int, int'Î INT(seq) подобны, если имеет место подобие фактов взаимовлияния.

Конфликт по факту f между действиями a,χÎseq - это тип взаимовлияния a⬍f⬍χ такой, что:

либо (1) fÎeff(a) & ⌝fÎpre(χ) & f ˅⌝f∉pre(χ),

либо (2) ⌝fÎeff(a) & fÎpre(χ) & f˅⌝f∉pre(χ).

Конфликт будем обозначать a↑f↓χ.

CF(seq) - множество конфликтов, в которых состоят действия последовательности seq.

Последовательность seq будем называть бесконфликтной, если CF(seq)=0.

Согласие по факту f между действиями a,χ Îseq - это тип взаимовлияния a⬍f⬍χ такой, что:

либо (1) fÎeff(a) & (fÎpre(χ) v (f˅⌝fÎpre(χ)) ),

либо (2) ⌝fÎeff(a) & (⌝fÎpre(χ) v (f˅⌝fÎpre(χ)) ).

Согласие будем обозначать a↑f↑χ .

CS(seq) - множество согласий, в которых состоят действия последовательности seq.

Минимальные планы. Бесполезные действия

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