Разработка медицинского автоматизированного манипулятора

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



2. Специальный раздел

2.1 Архитектура комплекса инструментальных средств управления информационного роботизированного комплекса

2.1.1 Архитектура инструментальных программных средств

Основным модулем динамической интеллектуальной системы (далее просто система) (рисунок 9.) является база знаний, в которой содержатся знания, планы, цели функционирования динамической интеллектуальной системы. В системе принят гибридный метод представления знаний, который сочетает системы фреймов и продукционные системы [14, 15].

Модуль анализа и управления анализирует состояния предметной области, моделирует процессы, протекающие в среде, осуществляет динамический вывод, формирует текущие цели системы, и на основе планов в базе знаний моделирует целенаправленное поведение системы.

Модуль интеллектуального планирования осуществляет прогнозирование состояния системы, на основе которого синтезирует план действий по достижению текущих и глобальных целей. Формируемый план обладает устойчивостью к незначительным изменениям в динамической среде. В терминологии системы, план -- это последовательность правил управления, выбираемая системой, исходя из её основных и текущих целей, информации о текущем состоянии среды и динамике её изменения. Исполнение плана приводит систему в состояние, в котором либо достигается основная цель, либо некоторая промежуточная текущая цель.

Важной особенностью системы является асинхронная работа Модуля интеллектуального планирования (МИЛ) и Модуля анализа и управления (МАУ), т.е. МИЛ постоянно формирует планы целенаправленного поведения системы, в то время как МАУ исполняет их.

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

1) от внешнего интерфейса, например, в ходе опроса датчиков.

2) от разработчика -- через интерфейс разработчика.

3) от пользователя -- через интерфейс пользователя.

В начале работы системы, рабочая память содержит множество исходных фактов.

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

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

Рисунок 9. - Архитектура динамической интеллектуальной системы



2.1.2 Средства представления знаний

Основной когнитивной структурой базы знаний является прототип.

Прототип - структура данных, представляющая класс объектов, ситуаций или процессов предметной области. В структуре прототипа декларируются свойства, события, объекты, ситуации, процессы, а также связи между ними, которые минимально необходимы для представления класса объектов, ситуаций, процессов. На множестве прототипов определено отношение наследования, что позволяет одному прототипу наследовать описание другого прототипа.

Объект - сущность, обладающая свойствами и функциональным назначением. Большинство свойств объекта на протяжении большого промежутка времени не меняется. Пример: 'стул', 'стол', 'монитор', 'комната' и т.д.

Ситуация -- поименованный набор элементов предметной области и отношений между ними в текущий момент времени. Пример, 'тревога', 'брак', 'пожар', 'стабильная работа', 'столкновение' и т.д.

Процесс -- описание закономерностей изменения свойств объектов. Например 'подача топлива', 'вращение турбины', 'падение объекта' и т.д.

Объекты, ситуации, процессы обладают свойствами, и с ними могут быть связаны различные события. Например, свойствами объекта (ситуации, процесса) являются такие характеристики, как цвет, масса, объём, рост, длина, а событиями объекта (ситуации, процесса) - такие характеристики, как 'включен', 'выключен', 'сломан', 'нажат' и т.д. События могут быть определены на свойствах, например, событие "повышенная температура тела человека" определено на свойстве 'температура' с областью характерных значений от 38 до 42 градусов.

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

Формально прототип это:

Р = <NP, StrP>;

где NP - имя прототипа, StrP - структура прототипа

StrP: <Attr, Mark, Inst, Rel, Rule>; где Attr - множество атрибутов прототипа, Mark - множество оценок прототипа, Inst - множество примеров, Rel -множество отношений, Rule -множество правил.

Подобная структура позволяет описывать ситуацию реального уровня сложности.

Свойства - слоты прототипа, представляющие знания о свойствах объектов, ситуаций, процессов.

События - слоты, представляющие знания о состояниях объектов, ситуаций, процессов.

Для описания прототипа с помощью других прототипов определён слот - пример прототипа. Пример является представлением конкретного объекта,
ситуации, процесса, созданного на основе прототипа. От родительского
прототипа пример наследует структурную часть.

Определены четыре категории правил:

1) Правила замыкания.

2) Правила переходов.

3) Правила управления.

4) Правила целеуказания.

Множество правил можно условно разделить на синхронные правила (категории 1, 3, 4), формирующие состояние системы s(t) на основе фактов в момент времени t, и диахронные (категория 2), формирующие состояние системы s(t+l) на основе фактов в момент времени t.

Правила замыкания выводят наличие фактов в текущем состоянии предметной области, на основе других фактов в тот же момент времени, т.о. достраивая описание состояния системы.

Правила переходов выводят наличие фактов в следующем состоянии, на основе фактов известных в текущем состоянии.

Правила целеуказания формируют множество целевых состояний системы.

Правила управления задают основные параметры управления системой для достижения целевого состояния.

Правила целеуказания и управления формируют целенаправленное поведение системы.

Правила перехода и замыкания формируют динамику изменения предметной области.

Время в системе дискретно. Задаётся временная шкала Т, путём указания единицы измерения времени (с, час, сутки, дни, столетия и т.д.) и дискреты времени ?t. Тогда состояния системы представляются как моменты времени кратные ?t.

Перед запуском системы пользователь описывает цели системы на специальном языке. Цель содержит множество фактов, которые являются целевыми фактами. Состояние, которое содержит множество целевых фактов, называется целевым состоянием. Целевое состояние достигается в результате поиска и выполнения управления. Отсутствие управляющих воздействий рассматривается как один из вариантов управления. Целевые факты могут быть позитивными, при этом система добивается появления таких фактов, или же негативными, тогда система избегает появления таких фактов. Дополнительно можно потребовать от системы: оптимизации некоторого параметра, достижения целевого состояния за конечное время и т.д.

2.1.3 Средства моделирования целенаправленного поведения

Система начинает функционировать после указания целей. Основой целенаправленного поведения системы является формирование и исполнение планов.

Схема функционирования системы такова:

Пока не достигнуты основные цели системы выполнять:

1)Замыкание состояния.

2)Установку текущих целей.

3)Исполнение плана для достижения текущих целей.

4)Переход состояния системы.

На этапе замыкания (1) на основе исходных фактов в рабочей памяти достраивается текущее состояние системы. По сути, здесь происходит выявление правил замыкания, применимых к множеству фактов в текущем состоянии, и исполнение этих правил.

На этапе целеуказания (2) формируется множество текущих целей системы, которые необходимо достичь прежде, чем будет достигнута основная цель. Множество текущих целей формируется на основе правил целеуказания, применимых в текущем состоянии.

После того, как достроено состояние системы и сформированы текущие цели, модуль анализа и управления осуществляет поиск плана в базе знаний, применимого в текущей ситуации, и его исполнение (3). План формируется модулем интеллектуального планирования.

На этапе перехода (3) формируется ядро следующего состояния системы, а именно, исполняется множество правил переходов, применимых в текущем состоянии, которые выводят множество фактов в следующем состоянии системы.

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

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

2.2.1 Описание задачи планирования

Пусть:

L - язык исчисления предикатов первого порядка;

Р = <, R> -- домен планирования;

Т = <Р, G> -- задача планирования с классическими допущениями.

Введём определение. Факт f - это элементарная ППФ f из L без функциональных символов, либо отрицание f- f, либо дизъюнкция - ff.

Далее, вместо термина "правило" будем употреблять формально-эквивалентный термин "действие".

Во избежание трудностей, введём некоторые ограничения на описание домена планирования Р:

1) для каждого действия RR:

а) предусловие C(R) задаётся множеством фактов типа f или f;

б) список добавлений A(R) и список удалений D(R) задаётся множеством фактов типа f;

в) A(R)D(R) = .

2) Состояние s и цель G задаются множеством фактов типа f или f.

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

Любое действие RR описано безотносительно к некоторому состоянию, к которому может быть применено. Действие RR будем называть действием-прототипом.

Создадим бесконечное множество экземпляров действий А_exe. Каждый экземпляр снабдим уникальным идентификатором.

Экземпляр действия _exeA_exe=<id, R>, где RR -действие-прототип, которому соответствует действие-экземпляр, id -уникальный идентификатор действия-экземпляра.

Пара экземпляров действий _exe и _exe подобны, если соответствуют одному и тому же прототипу RR. Подобие действий-экземпляров обозначим _{exe exe} .

Под проверкой применимости действия будем понимать проверку выполнимости предусловия некоторого экземпляра действия _exeA_exe, соответствующего прототипу R в конкретном состоянии s.

Сформируем множество всевозможных последовательностей действий-экземпляров SEQ.

Множество SEQ - множество всевозможных
последовательностей действий-экземпляров. Длину некоторой последовательности seqSEQ обозначим через |seq|.

Отношение полного порядка, заданное на множестве действий некоторой последовательности seqSEQ будем называть отношением предшествования, и обозначать так: <.

Предположим, что в некоторой последовательности seqSEQ имеет место: _exe <_exe Однако, возможно, что существует действие _exe seq такое, что _exe<_exe и _exe<_exe.

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

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

Введём для этих гипотетических множеств действий следующие обозначения -- соответственно start и finish. Пополним множество SEQ этими действиями.

Действие start = <С=, A=s₀, D=>. Действие finish = <С=G, А=, D=>;

Добавим действие start в начало каждой последовательности множества SEQ, а finish в конец каждой такой последовательности. Последовательность (start, finish) SEQ будем называть начальной, и обозначать init. Нумерацию элементов последовательности seq будем вести, начиная с нуля. nN будем использовать для обозначения конечного элемента последовательности seq.

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

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

APL

вход: seq

выход: DM=<so, s₁ ..., s_n>

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

применить к s₀

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

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

Последовательность seq называется полностью применимой, если каждое действие a_tseq применимо. Иначе, последовательность seq называется не полностью применимой. Полностью применимая последовательность действий является решением задачи планирования Т, если состояние s_n, полученное в результате применения последнего действия _n seq, является целевым состоянием, то есть Gs_n.

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

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

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

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

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

l)fЦ()

2)fЦ(ч)

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

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

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

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

либо (1) feff() & ?fpre(ч) & f ??f?pre(ч),

либо (2) ?feff() & fpre(ч) & f??f?pre(ч).

Конфликт будем обозначать ^fvч.

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

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

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



либо (1) feff() & (fpre(ч) v (f??fpre(ч)) ),

либо (2) ?feff() & (?fpre(ч) v (f??fpre(ч)) ).

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

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

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

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

Пучок взаимовлияний подпоследовательностей и subseq₂ последовательности seq - это некоторое множество взаимовлияний IS(, subseq₂)INT(seq), в котором любое взаимовлияние ?f?IS таково, что и subseq₂, где , subseq₂seq и subseq₂ = .

Пучок взаимовлияний IS(, subseq₂) подобен пучку взаимовлияний IS(subseq₃, subseq₄), если любая пара подобных взаимовлияний inteIS(subseqi,subseq₂) и int'IS(subseq3,subseq₄) такова, что:

либо 1) int -- согласие и int? - согласие;

либо 2) int -- конфликт и - конфликт.

Подобие пучков взаимовлияний обозначим так: IS(, subseq₂) = IS(subseq₃,).

Замечание. Наиболее короткая подпоследовательность состоит из одного действия.

Выделим в seq некоторую подпоследовательность mseq, не включающую действия start и finish.

Некоторую подпоследовательность mseqseq будем называть собственной подпоследовательностью, если mseq не включает действий start и finish, то есть, и . Подпоследовательность действий lseqseq такую, что для любых действий lseq и mseq верно, что < и lseqmseq=, будем называть левой подпоследовательностью для mseq.

Подпоследовательность действий rseqseq такую, что для любых действий mseq и rseq верно, что < и mseqrseq=, будем называть правой подпоследовательностью для mseq

Собственную подпоследовательность mseq будем называть бесполезной подпоследовательностью действий и обозначать mseq>?, если IS(lseq, mseq) ? IS(mseq, rseq), где lseq -- левая подпоследовательность действий для mseq, rseq - правая подпоследовательность действий для mseq.

Удаление бесполезной собственной подпоследовательности mseq из seq приводит к последовательности seq' такой, что для любого взаимовлияния int=?f?INT(seq):

либо, 1) имеет место либо обычное преобразование, либо НЕ-преобразование int в такое взаимовлияние int=????f????INT(seq'), что:

либо 1.а) int и int' являются конфликтами;

либо 1.6) int и int' являются согласиями,

либо, 2) имеет место нуль-преобразование int.

Если в некоторой последовательности seq существуют подпоследовательности mseq' и mseq" такие, что:

а) mseq'mseq", причём =", где ' - первое действие mseq', " - первое
действие mseq",

б) IS(lseq^,,mseq^,)=IS(lseq",mseq"), где lseq=lseq" - левая подпоследовательность
для mseq' и mseq",

в) IS(mseq',rseq')?IS(mseq", rseq"), где rseq' -- правая подпоследовательность для
mseq', rseq" - правая подпоследовательность для mseq",

тогда собственная подпоследовательность mseqcseq такая, что mseqmseq" и

mseqmseq', является бесполезной.

При пошаговом преобразовании некоторой исходной последовательности seqSEQ путём добавления действий, существует шаг L, на котором будет сформирована последовательность seq'SEQ, содержащая бесполезную подпоследовательность mseqseq'.

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

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

Утверждение 1. Минимальный план planSEQ не содержит бесполезной подпоследовательности действий.

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

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

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

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

Пусть дано:

В домене планирования Р существуют действия-прототипы: с эффектом eff()={ f₁, f₂}; действие а₂, с эффектом eff (а₂)= { f₁}; действие а₃ с эффектом eff(a₃)={f₂}.

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

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

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

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

В Plan₁ имеется пара согласий cs¹₁ и cs¹₂, соответственно по фактам f₁ и f₂ - cs₁ и cs₂ расположены на одном интервале влияния.

В Plan₂ имеется пара согласий cs²₁ и cs²₂, сходная соответственно с cs¹₁и cs¹₂.

Тогда, возможно, что в плане Plan₁ в согласиях cs¹₁ и cs¹₂ левым членом является действие В то время как в плане Plan₂ в согласиях cs²₁ и cs²₂ левыми членами являются, соответственно, действия и - Из этого ясно, что в схожих согласиях в различных планах, в общем случае, может участвовать различное количество действий. То есть Plan₁ и Plan₂ могут содержать различное количество действий, несмотря на схожее множество взаимовлияний. Следовательно, один из планов не является минимальным. Утверждение доказано.

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

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

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

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

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

Если входная последовательность seq не содержит конфликты, то seq является планом и ITPA возвращает seq.

Алгоритм ITPA можно улучшить.



2.2.5 Планирование на основе полного разрешения конфликтов

Напомним, что в плане любая пара действий, состоящих во взаимовлиянии, согласована. Этот факт можно использовать для поиска планов.

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

Разрешение конфликта cf=?f???CF(seq) -- это обычное преобразование взаимовлияния ?f???INT(seq) таким действием ', что: (fpre(') или f??fpre(')) и ?feff(').

Действие ' будем называть действием, разрешающим конфликт cf, или просто разрешающим действием.

Действия и ?? будем называть родительскими действиями для действия '.

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

Поскольку заранее неизвестно, какой из вариантов разрешения конфликтов приведёт к плану, то необходимо учитывать все варианты разрешения конфликта.

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

Определим операцию разрешения всех конфликтов в последовательности.

Разрешение всех конфликтов CF(seq) будем называть полным разрешением конфликтов в последовательности seq. Полное разрешение конфликтов обозначим: ResolveAll (seq).

RES^seq - множество последовательностей, возвращаемое операцией ResolveAll (seq).

Пусть ко всем конфликтам последовательности seq применяется операция полного разрешения, RES^seq =ResolveAll (seq).

Сформулируем и докажем теорему, которая показывает возможность использования операции полного разрешения конфликтов для поиска планов.

Пусть имеется последовательность seq, не являющаяся планом, и последовательность plan, являющаяся некоторым конкретным планом.

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

Теорема 1. Полное разрешение конфликтов последовательности seq такое, что h(seq)=plan и seq?plan возвращает одну и только одну последовательность res RES^seqSEQ такую, что h(res)=plan, либо res?plan.

Доказательство:

А. Докажем существование последовательности действий res, такой что h(res)=plan.

Рассмотрим произвольный конфликт cf=?f??? CF(seq).

1. В соответствии с основным положением h(seq)=plan, существуют действия h()=', h(??)=??' где ',??'plаn Напомним, что в плане не существует конфликтных действий. Следовательно, должно существовать некоторое действие ', не позволяющее конфликтовать паре действий h()=' и h(??)=??', такое, что: '<'<??'plan.

2. По определению полного разрешения конфликтов некоторая
последовательность resRES^seq содержит действие "res, которое подобно
'plan и является действием, разрешающим конфликт cf=?f??? CF(seq).
Заметим, в множестве результирующих последовательностей RES^seq имеются всевозможные варианты расположения " между действиями h('')= и h(??")=??, где ",??"res.

3. а) для любого действия ??"?"res верно, что (??")=??seq,

б) для любого действия ??seq верно, что h(??)=??'рlan,

в) из а) и б) следует что, ??"~??'.

4. Количество альтернативных расположений 'plan среди действий plan'a, подобных действиям из res (имеется в виду подобие, выведенное в 3 пункте: ??"~??') и между действиями h()=' и h(??)=??' конечно.

5. из 2, 3, 4 и по определению гомоморфизма последовательностей следует, что существует такая последовательность действий resRES^seq, что h(res)=plan.

B. Единственность существования res, такого, что h(res)=plan, следует из того факта, что не существует альтернативного порядка следования действий в res, для которого сохранилось бы утверждение h(res)=plan. Следовательно, последовательность res единственна.

C. Докажем возможность res=plan.

В любой последовательности resRES^seq количество действий больше чем в seq.

Количество действий в плане конечно.

3. Тогда из А.5, C.l, С.2 следует, что в одном из вариантов пошагового
разрешения действительно имеет место res?plan.

Теорема доказана.

Обратим внимание, на интересное свойство последовательности init. Начальная последовательность init такова, что h (I,it) = plan, где plan -- это любой существующий план для задачи Т.

Очевидно. Теперь мы можем модифицировать алгоритм ITPA. Назовём его CRPA (conflict resolution planning algorithm).

Рис. 11 - Алгоритм CRPA



Основной идеей алгоритма CRPA является полное разрешение конфликтов некоторой исходной последовательности действий seq, дли которой справедливо h(seq)=plan. Полное разрешение конфликтов приводит к множеству последовательностей, которые в свою очередь могут также содержать конфликты. Разрешение конфликтов продолжается для очередных последовательностей, до тех пор, пока не будут получены бесконфликтные последовательности действий.

Алгоритм CRPA начинает свою работу с разрешения конфликтов в последовательности init=(start, finish). Более того, задача планирования Т может оказаться тривиально разрешимой, то есть G, и как следствие eff(start)=pre(flnish) без каких-либо конфликтов. Множество взаимовлияний, порождаемое последовательностью init, будем называть первичными взаимовлияниями.

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

Теорема 2. Если для задачи планирования Т существует решение, то алгоритм CRPA найдёт план.

Доказательство:

l.Ha вход CRPA подаётся последовательность seq⁼init, обладающая свойством h (seq) = plan, где plan - это некоторый конкретный план.

2. Алгоритм CRPA есть не что иное, как процедурная реализация пошагового полного разрешения конфликтов входной последовательности seq.

3. Из 1 и 2, и в соответствии с теоремой 1. следует, что существует одна из рекурсивных ветвей алгоритма, которая возвращает конкретный план plan. Теорема доказана.

Опишем утверждение 3 приведённое в [59].

Утверждение 3. Если для задачи планирования Т существует решение, то алгоритм CRPA найдёт все планы.

Доказательство: Это так поскольку, относительно любого плана plan, решающего задачу планирования Т, справедливо утверждение h(init)=plan.

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

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

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

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

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

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

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

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

Заметим, что, вообще говоря, в одном из вариантов пошагового разрешения конфликтов в согласуемой начальной последовательности 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 вернёт её.

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

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

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

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

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

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

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

,

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

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

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

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

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

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

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

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

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

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

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

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

Вероятность prob()PROB - это вероятность того, что в произвольной последовательности seqSEQ собственная подпоследовательность mseqseq, для которой существует левая и правая подпоследовательности 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 и mseqseq: М |IS(lseq, mseq)|.

Пусть,

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

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

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

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

Тогда,



(1)

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

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

(2)

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

Будем считать, что подпоследовательности длины равной 1, всегда полезны, так как обычно в домене планирования действия описываются так, что при применении производят какие-либо изменения в состоянии. Поэтому, далее будем рассчитывать вероятность для подпоследовательностей длиной больше чем 1.

Множество = {| |seq| = ??} является множеством событий появления бесполезной подпоследовательности действий mseq? произвольной длины (|mseq|?|seq|-2) в произвольной последовательности seq, при фиксированном |seq| = ??.

Множество событий :

1) совместны, так как появление одного из событий не исключает
появления другого.

2) независимы, так как возникновение бесполезной
подпоследовательности действий в одной части последовательности seq
практически никак не влияет на появление бесполезной подпоследовательности
в другой части seq.

Заметим, что мощность || = k, где k - количество собственных подпоследовательностей в некоторой последовательности seq, которое подсчитывается по формуле:

(3)

Определим вероятность prob||), которая рассчитывается по формуле сложения вероятности k совместных и независимых событий.

Однако вначале для более удобной записи формулы упорядочим множество в ряд из к элементов следующим образом: для каждого |mseq| = 2 до ??-2 расположим в конце ряда в произвольном порядке очередные (??-|mseq|)+l событий . Далее, запись означает элемент с номером і ряда .

Ниже приведена формула вычисления prob():

Prob()

(4)

Здесь, в квадратных скобках определены итераторы по тем элементам ряда UE', которые участвуют в произведении вероятностей.

В формуле prob() сумма на нижней строке вычитается, если k -чётное число, и прибавляется, если k - нечётное число.

Вычислим математическое ожидание М || количества последовательностей длины ??, которые содержат бесполезные подпоследовательности действий:

М || =||*prob()

Охарактеризуем свойство обратимости, на примере следующих доменов планирования: "Мир кубиков", "Логистика",

"Задача о коммивояжёре".

Домен планирования "Мир кубиков" содержит:

8 объектов (индивиды),

144 действия (правил),

33 факта (предикатов).

Домен планирования "Логистика" содержит:

20 объектов,

234 действия,

87 фактов.

Домен планирования "Задача о коммивояжоре" содержит:

5 объектов (городов),

10 фактов,

32 действия.

Для данных доменов планирования построим графики зависимости мощностей | и || от длины ??, где длина ?? варьируется от 1 до 11 действий.

На графике: по горизонтальной оси отложена длина ??, по вертикальной оси - мощность ||= (на рисунке - SEQ), а также - мощность || (на рисунке - SEQ (БПД)).



Рис.13 - "Мир Кубиков"

Рис. 14 - "Логистика"

Рис. 15 - "Задача о коммивояжёре"



Примечание.

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

Пример 1.

Для домена планирования "Мир кубиков" количество последовательностей длины 5 равно 144⁵ = 61 917 364 224. Из них количество последовательностей, содержащих БПД, равно 1 609 851 470, что составляет примерно 2% от общего количества.

Пример 2.

Для домена планирования "Логистика" количество последовательностей длины 3 равно 12 812 904. Из них количество последовательностей, содержащих БПД, равно 384 387, что составляет примерно 3% от общего количества.

Пример 3.

Для домена планирования "Задача коммивояжёра" количество последовательностей длины 8 равно 1 099 511 627 776. Из них количество последовательностей, содержащих БПД, равно 87 960 930 222, что составляет примерно 8% от общего количества.

В соответствии с пунктом (2.2.3.) графики SEQ и SEQ (БПД) сойдутся при некоторой длине L.

Очевидно, что график SEQ (БПД) всегда возрастает.

Алгоритм TCRPA, использующий технику выявления бесполезной подпоследовательности действий, будет осуществлять перебор в множестве SEQ' = / , где n - наибольшая длина плана, который не содержит бесполезные подпоследовательности действий, - множество всех последовательностей длиной меньше либо равной n. Алгоритмы, не использующие соответствующей техники, будут искать план во всём множестве .



2.3 Требования к интерфейсу системы

2.3.1 Интерфейс системы

Интерфейс - совокупность средств, методов и правил взаимодействия между элементами системы.

Основным модулем системы, является база знаний в которой содержатся знания, планы, цели функционирования системы.

Структура разработанной системы (рисунок 9.), общается с компонентами ИРК с помощью внешнего интерфейса.

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

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

2.3.2 Входные и выходные данные.

На вход системы поступают факты и состояния процессов внешней среды, а так же задачи необходимые к выполнению.

На основе данных полученных от внешних источников, система формирует представление о текущей ситуации и пополняет рабочую память системы. Более подробно процесс обработки данных и нахождения минимального плана действий для цели, описан в (2.1. , 2.2.).

На выход системы подаётся минимальный план, полученный в результате работы алгоритма TCRPA(2.2.7), виде логической последовательности действий.



3. Технологический раздел

3.1 Информационное обеспечение

3.1.1 Представление данных

В системе принят гибридный метод представления знаний, который сочетает системы фреймов и продукционные системы описанный в (2.1.2).

Данные в информационно робототизированном комплексе (ИРК), представляется на языке логики первого порядка(исчисления предикатов).

Язык логики первого порядка строится на основе сигнатуры, состоящей из множества функциональных символов  и множества предикатных символов . С каждым функциональным и предикатным символом связана арность, то есть число возможных аргументов. Допускаются как функциональные, так и предикатные символы арности 0. Первые иногда выделяют в отдельное множество констант. Кроме того, используются следующие дополнительные символы

Символы переменных (обычно  и т. д.),

Пропозициональные связки: ,

Кванторы: всеобщности  и существования ,

Служебные символы: скобки и запятая.

Перечисленные символы вместе с символами из  и  образуют алфавит логики первого порядка. Более сложные конструкции определяются индуктивно:

Терм есть символ переменной, либо имеет вид , где  -- функциональный символ арности , а  -- термы.

Атом имеет вид , где  -- предикатный символ арности , а  -- термы.

Формула -- это либо атом, либо одна из следующих конструкций: , где  -- формулы, а  -- переменная.

Переменная  называется связанной в формуле , если  имеет вид  либо , или же представима в одной из форм , причем  уже связанна в ,  и . Если  не связанна в , ее называют свободной в . Формулу без свободных переменных называют замкнутой формулой, или предложением. Теорией первого порядка называют любое множество предложений.

Логика первого порядка обладает рядом полезных свойств, которые делают ее очень привлекательной в качестве основного инструмента формализации математики. Главными из них являются полнота (это означает, что для любой формулы выводима либо она сама, либо ее отрицание) и непротиворечивость (ни одна формула не может быть выведена одновременно со своим отрицанием). При этом если непротиворечивость более или менее очевидна, то полнота -- нетривиальный результат, полученный Гёделем в 1930 году (теорема Гёделя о полноте). По сути теорема Гёделя [56] устанавливает фундаментальную эквивалентность понятий доказуемости и общезначимост.

Логика первого порядка обладает свойством компактности: если некоторое множество формул невыполнимо, то невыполнимо также некоторое его конечное подмножество.

Согласно теореме Лёвенгейма-Сколема если множество формул имеет модель, то оно также имеет модель не более чем счетной мощности. С этой теоремой связан парадокс Сколема, который, однако, является лишь мнимым парадоксом.

3.1.2 Требования к информационному обеспечению

Для успешного построения ИРК, на основе архитектуры комплекса инструментальных средств управления ИРК(2.1) и алгоритмов планирования (2.2), необходимо:

1) Исследование предметной области, в рамках которой будет функционировать ИРК.

а) Исследование объектов, ситуаций, процессов предметной области.

б) Постановка основных целей и ограничений, необходимых для работы ИРК.

в) Разработка начальных планов действий для системы, для достижения ряда целей поставленных перед ИРК.

2) Описание полученных сведений на языке логики первого порядка, для организации начального наполнения базы знаний ИРК.

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

3.2 Программное обеспечение

3.2.1 Требования к программному обеспечению

Программное обеспечение (ПО) - совокупность программ, позволяющая организовать решение задач на компьютере.

При создании программной реализации системы построения минимальных планов ИРК, необходимо учитывать и использовать:

1) Архитектуру комплекса инструментальных программных средств, описанную в (2.1.1).

2) Средства представления знаний, описанные в (2.1.2).