ДИНАМИЧЕСКИЕ МОДЕЛИ И ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА, ИСПОЛЬЗУЮЩИЕ ЭМПИРИЧЕСКИЕ И ЭКСПЕРТНЫЕ ЗНАНИЯ

 

Г.С. ОСИПОВ

Институт программных систем РАН

osipov@airec.botik.ru

 

 

            Введение. В конце 1999 года на одной из конференции IEEE НАСА объявило о том, что 17 мая 1999 года удалённый интеллектуальный агент, включенный в замкнутый контур управления, взял на себя управление космическим аппаратом в автономном режиме.

            Это произошло на борту аппарата для исследования глубокого космоса DEEP SPACE ONE на удалении 65 миллионов миль от Земли. Главной целью эксперимента была демонстрация возможностей бортовой интеллектуальной системы автономного управления космическим аппаратом.

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

 

С архитектурной точки зрения интеллектуальный агент включал следующие модули:

            - МОДУЛЬ УПРАВЛЕНИЯ ЗАДАНИЯМИ

            - МОДУЛЬ ПЛАНИРОВАНИЯ

            - МОДУЛЬ ИСПОЛНЕНИЯ

            - МОДУЛЬ ИДЕНТИФИКАЦИИ РЕЖИМОВ И РЕКОНФИГУРАЦИИ

            - СРЕДСТВА МОНИТОРИНГА

            - ПРОГРАММНАЯ СРЕДА РЕАЛЬНОГО ВРЕМЕНИ

            - БОРТОВОЕ ОБОРУДОВАНИЕ.

           

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

 

Проект беспилотного интеллектуального вертолета WITAS – долговременный исследовательский проект, выполняемый, главным образом, в Linkoping University в Швеции. В проекте участвуют и некоторые иные университеты Европы и Америки. В нем, как сообщают сами авторы, использован ряд решений предыдущего проекта, однако, разумеется, имеется много особенностей. С точки зрения архитектуры программных средств можно выделить три уровня:

·        делиберативный уровень – содержит открытое множество инструментов высшего уровня, таких как планировщик, синтезатор траектории, пакет программ распознавания и другие;

·        реактивный уровень – содержит библиотеку программ, реализующих управляющие воздействия и взаимодействующих между собой;

·        уровень процессов – реализует обратные связи в контуре управления, связывая, таким образом, сенсорику и исполнение действий.

 

Основной способ представления знаний– фреймы и правила. Кроме того, используются так называемая «ВРЕМЕННАЯ ЛОГИКА ДЕЙСТВИЙ», разработанная участниками проекта (которая является гораздо более конкретной, нежели известные логика действий и ситуационная логика) и «КОГНИТИВНАЯ ЛОГИКА РОБОТА» - для связи наблюдений, управления и целенаправленного поведения.

 

Можно указать ряд близких проектов, выполняемых в США:

Berkeley Aerobot project;

Atlanta - the Unmanned Aeral Vehicle Research Facility;

Carnegie Mellon University – the Autonomous Helicopter Project;

Stanford University – Aerospace Robotics Laboratory.

 

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

Укажу лишь некоторые:

-         управление коалициями и коллективами искусственных устройств;

-         управление автономными мобильными платформами;

-         автономная роботехника (робокраны, робокары и др.);

-         непрерывная диагностика оборудования (например, турбин);

-         автономные мобильные средства ведения боевых операций;

-         моделирование бизнес - процессов на основе систем бизнес-правил;

-         инжиниринг и реинжиниринг предприятий на основе моделирования бизнес – процессов;

-         моделирование жизненного цикла предприятия;

-         управление сборочным производством и испытаниями сложных технических систем;

-         интеллектуальные системы управления большими телекоммуникационными сетями;

-         интеллектуальные системы мониторинга среды;

и др.

 

Представление знаний и инструментальные средства.

 

В большинстве случаев в таких проектах для представления знаний используется стандартная техника искусственного интеллекта:

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

системы правил, которые являются основным способом синтеза и представления планов; отношения на множестве объектов;

цели и ограничения.

 

Ряд работ выполняется на известных инструментальных средствах, таких как Knowledge Сraft ((Italtel S.I.T. - R & D Laboratories - Settimo Milanese, Italy) –продукт Italsim Carnegie Group с пакетами Simpak и Graphpak. Knowledge Сraft поддерживает мощный язык представления знаний, множественные парадигмы программирования, различные механизмы вывода и средства разработки интерфейсов. Simpak обеспечивает разработчика набором статистических функций, объектно-ориентированным языком программирования и механизмом поддержки календаря дискретных событий. Graphpak обеспечивает графическими утилитами для мониторинга процессов и разработки интерфейсов пользователя.

Существуют работы посвященные разработке языков моделирования больших систем (Sheffield Univ., KEMS);

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

Заметные теоретические результаты (хотя оно ближе к теории управления, чем к ИИ) имеются в области гибридных систем, (дифференциальные автоматы, модель Нерода-Кона, модель Брокета и некоторые другие).

Начало исследований такого рода положено работами Грина, Файкса и Нильсона [1,2] в их работах по так называемым универсальным решателям проблем; соответствующие методы впервые нашли применение в системе STRIPS.

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

В настоящее время имеется обширная библиография по планированию. Здесь важнейшие результаты - теорема МакАлистера и Розенблита [3]о полноте алгоритма частично-упорядоченного планирования. Реализован ряд планировщиков, наиболее известные из которых Prodigy, SNLP, Grafplan, SATPLAN используют поиск в пространстве состояний.

Предпринимались попытки улучшить управление поиском для построения плана, в частности, для неклассических задач планирования - программы NOAN и Nonlin, использующие поиск в пространстве планов. Среди отечественных работ следует указать работы А.Н.Аверкина и Д.А.Поспелова, в которых поиск плана сводился к поиску в пространстве задач, работы В.Л.Стефанюка, который одним из первых исследовал архитектуры динамических интеллектуальных систем.

 

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

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

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

 

1.ПРИМЕРЫ

 

Пусть известны: множество высказываний о значениях лингвистических или логических переменных;

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

 

При этом неизвестны: точные описания состояний; точное описание динамики системы.

 

Рассмотрим несколько примеров:

 

1.1.Параметры состояния :

 

12 мая температура воды 14 градусов;

12 мая течение слабое;

Направление течения: северо-западное;

Соленость воды: низкая.

 

1.2.Экспертные правила

 

Правило 1.(ВЫБОР ЦЕЛИ)

УСЛОВИЕ направление линии визирования = неизвестно

СПИСОК ДОБАВЛЯЕМЫХ ФАКТОВ цель = поиск станции

СПИСОК УДАЛЯЕМЫХ ФАКТОВ все остальные цели

 

Правило 2.(ВЫБОР ЦЕЛИ)

УСЛОВИЕ угол (АL,V)³a, резерв времени <e

СПИСОК ДОБАВЛЯЕМЫХ ФАКТОВ цель = зависание

СПИСОК УДАЛЯЕМЫХ ФАКТОВ все остальные цели

 

Правило 3. (ВЫЧИСЛЕНИЕ ВЕКТОРА И МОМЕНТА СИЛЫ)

УСЛОВИЕ цель = сближение, дистанция = D, вектор линии визирования = AL, угол промаха = a

СПИСОК ДОБАВЛЯЕМЫХ ФАКТОВ вектор силы = F(V,AL, Ox, Dt),
момент силы = M(w, Fw, AL,V, Ox, Dt)

 

Правило 4.(ВЫБОР КОМБИНАЦИИ ВКЛЮЧАЕМЫХ ДВИГАТЕЛЕЙ)

УСЛОВИЕ nтакта= четный, |F|¹0, угол (F,F(Cn))£ea , |F|- |F(Cn)| <el

СПИСОК ДОБАВЛЯЕМЫХ ФАКТОВ C(t+1)= Cn

СПИСОК УДАЛЯЕМЫХ ФАКТОВ C(t)

 

Правило 5.(ВЫБОР КОМБИНАЦИИ ВКЛЮЧАЕМЫХ ДВИГАТЕЛЕЙ)

УСЛОВИЕ nтакта= нечетный, |M|¹0, угол (M,M(Cn))£e r , |M|- |M(Cn)| <en

СПИСОК ДОБАВЛЯЕМЫХ ФАКТОВ C(t+1)= Cn

СПИСОК УДАЛЯЕМЫХ ФАКТОВ C(t)

 

2. СИСТЕМЫ ПРАВИЛ И ОСНОВНЫЕ АЛГОРИТМЫ.

 

Замечу вначале, что понятие правила восходит к системам подстановок Поста и нормальным алгорифмам Маркова [4].Каждое правило имеет следующий вид:

Пi =<Сi , Ai , Di >, где

Di – множество высказываний (фактов), удаляемых в результате применения правила,

Ci, Ai и Di – множества атомарных формул некоторого языка L.

 

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

            Для того, чтобы определить механизм применения правила, следует ввести конструкцию под названием БАЗА ДАННЫХ.

Схема базы данных должна содержать все те отношения, которые соответствуют предикатным символам из С, А и D.

Так, если условие C некоторого правила содержит атомарные формулы

P1(x,…,y), P2(u,…,v) , …, Pn (w,…,z), то база данных должна содержать отношения R1, R2, …,Rn, соответственно; интерпретирующие предикатные символы P1, P2, …,Pn .

Точно таким же образом, если множество А содержит атомарные формулы Q1(x,…,y), Q2(u,…,v) , …, Qm, база данных должна содержать отношения Rn+1, Rn+2,. . ., Rn+m соответственно.

Основной вычислительный механизм системы [5], состоящей из множества правил, базы данных и некоторой стратегии выбора правил - следующий недетерминированный процесс:

в соответствии со стратегией выбора правил выбрать некоторое правило Пi из множества правил;

проверить выполнимость Сi в текущем состоянии базы данных;

если Сi выполнено, то подставить на места всех свободных переменных в формулы из Сi, Аi и Di соответствующие значения параметров из базы данных. Иначе перейти к п.1;

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

Перейти к п.1.

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

 

            A={Q1(x,…,y), Q2(u,…,v) , …, Qm(w)} Þ

 

            A={Q1(a,…,b), Q2(c,…,d) , …, Qm(e)}, где x,y,u,v ,w –

переменные; a,b,c,d,e – константы из записи текущего состояния базы данных, на которой выполнено условие Сi.

 

Обозначим описанный основной вычислительный механизм через К.

 

Если Õ множество правил, то оно содержит два подмножества:

                                                           ПCL Ì Õ                                 (1)

и

                                                            ПTR Ì Õ                                (2),

где первое подмножество правил - ПCL пополняет знания о состоянии, второе – ПTR описывает переходы в очередные состояния.

 

Будем называтьF = (K, ПCL) - процедурой замыкания,

 

Y= (K, ПTR) - процедурой переходов.

 

Если x Ì X, где X – множество событий, то        (K(x), ПCL) = F(x),

 

                                                                                  (K(x), ПTR) = Y(x).

 

3. СОСТОЯНИЯ И ТРАЕКТОРИИ.

 

Будем называть систему D = <X, N, F, Y> -динамической системой, основанной на правилах.

Если множество правил и его подмножества заменить на семантическую сеть и её подсети, соответственно, то получим динамическую семантическую сеть [6].

 

Неподвижную точку уравнения F(x) = x будем называть состоянием системы D.

 

Уместно поставить вопрос о существовании решения этого уравнения. Ответ следующий:

если для каждого правила из множества правил D = Æ, то решение существует и может быть найдено за конечное время. – Достаточное условие. Поэтому, положим для всех правил из ПCL D = Æ.

Вернемся к процедуре переходов Y . Она двуместная (в отличие от Ф), т.к. в правилах из ПTR высказывания, содержащиеся в A и D имеют по отношению к условию С сдвиг на единицу значений временной переменой.

 

x¢(t+1) = Y(x(t), t)

 

x (t+1) = F(Y(x(t), t))

 

Тогда {F(Y(x, t))½tÎN} – траектория системы.

 

 

4. ДОСТИЖИМОСТЬ СОСТОЯНИЙ И ЦЕЛЕНАПРАВЛЕННОЕ ПОВЕДЕНИЕ.

 

Достижимость состояний оказалась связанной с устройством базы знаний системы [7], т.е. тройки:

 

Свойства базы знаний:

 

Коммутативность множества правил

Полнота базы знаний

Замкнутость (слабая);                      Замкнутость (сильная)

 

Рис.1

 

 

Связь свойств базы знаний с поведением динамической системы.

 

 

1. Коммутативность
множества правил

Устойчивость поведения

2. Полнота базы знаний

Существование управлений, компенсирующих возмущения

3.Замкнутость
(слабая)

Частичная достижимость

4. Замкнутость (сильная)

Полная достижимость

 

Целенаправленное поведение.

 

Пусть W Í X –множество целевых состояний; rÍ W´ W - отношение частичного порядка (отношение предпочтения),

Тогда D = < X, W, N, F , Y> будем называть динамической системой с множеством целей. [8]

 

Для исследования целенаправленного поведения таких систем введём понятие плана:

 

x Ì X – множество высказываний,

 

П1, П2 , …,П k из ПTR - последовательность правил.

 

x(П1) = x\D (П1)ИA(П1);

 

если x (П1, П2 , …,П k-1) определено,

 

то x (П1, П2 , …,П k) = x (П1, П2 , …,П k-1) \ D(П k) И A(П k ),

 

Определение 1. Правило Пi назовем допустимым, если С(Пi)Н x(П1, П2 , …,Пi-1), где С – предусловие правила Пi .

 

Определение 2. План достижения состояния х1 из состояния х0

 p= <П1, П2 , …,Пk > последовательность правил из ПTR, таких что:

1)каждое правило последовательности является допустимым;

2) х1Н x (П1 , П2 , …, П k).

 

Определение 3. План монотонный, если для всех k

ôS1 \ x (П1, П2 , …,П k)ô< ôS1 \ x (П1, П2 , …,П k-1)ô, где ôМô- мощность М.

Определение 4.План эффективный, если S½A(Пi)½ £ ôS1\ S0ô, (i=1,2,…,k).

 

Имеет место следующее :всякий эффективный план является монотонным.

 

Критерий существования плана.

 

Существует эффективный план достижения x1 x0 если и только если в ПTR найдётся подмножество правил П что

 

(ÈAi)) Ç(ÈDj)) =Æ для всех правил из П.

Схема вычислений:

1.g (W) - выдает цель w0 Î W, наиболее предпочтительную в смысле отношения r. Тогда, p (i,w0) = p (i, g (W)).

2.Если цель w0 = g (W) недостижима, тогда полагается W = W \{g (W)} и строится план p(i, g (W\{g (W))).

3.Если некоторое состояние w1 достигнуто, то из него вновь делается попытка достижения цели w0, т.е попытка построения плана p (i,w0) = p (i, g (W\w1)) и процесс повторяется.

 

 

5.РЕАЛИЗАЦИЯ.

 

Описанные модели легли в основу архитектуры инструментальных средств, реализованных в Центре искусственного интеллекта.

 

Основные модули инструментальных средств приведены на рис.2.

 

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

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

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

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

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

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

Модуль записи в базу знаний является исполнителем всех изменений в базе знаний.

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

Инструментальные программные средства, реализованные на основе описанного подхода были использованы для построения ряда прикладных систем [9,10].

 

Литература

 

1. Newel, A., and Simon, H., A. Humen problem solving // Engelwd Cliffs, N.J.: Prentice-Hall, 1972.

2. Fikes R.E., Nilsson N.J. STRIPS: a new approach to application of theorem proving to problem solving // Artificial Intelligence 1971, №2.

3. McAllester D., Rosenblit D. Systematic nonlinear planning // Proceedings of AAAI-91, Anaheim, Ca, 1991.

4. Марков А.А., Теория алгорифмов. //Тр. Мат. Института им. Стеклова, 38,176-198. 1951

5. Gennady Osipov. Dynamics in Integrated Knowledge-Based Systems. Proceedings of the 1998 IEEE Conference, Gaithersburg, MD, USA, 1998

6. Виноградов А.Н., Осипов Г.С., Жилякова Л.Ю. Динамические интеллектуальные системы. Ч.1. Представление знаний и основные алгоритмы. Известия АН. Теория и системы управления, М: Наука, 2002, №6, 119-127

7. Лебедева Т.Г. Осипов Г.С. Архитектура и управляемость дискретных динамических систем, основанных на знаниях. Известия АН. Теория и системы управления. М: Наука, 2000, №5, 703-709

8. Виноградов А.Н., Осипов Г.С., Жилякова Л.Ю. Динамические интеллектуальные системы. Ч.2. Моделирование целенаправленного поведения. Известия АН. Теория и системы управления, М: Наука, 2003, №1. стр.87-94

9. Бурдаев М.Н., Осипов Г.С., Хачумов В.М. О системе управления относительным движением космических аппаратов с повышенной безопасностью сближения. Материалы Третьих научных чтений памяти М.К.Тихонравова по военной тематике, 4-5 октября 2000 г., 4 ЦНИИ МО РФ, 2000.

10. Бурдаев М.Н., Осипов Г.С. Хачумов В.М. Принципы построения интеллектуальной измерительно-управляющей системы. Доклады Международной космической конференции 2001. Космос без оружия арена мирного сотрудничества в ХХI веке. М.: Изд-во МАИ, 2001.