ИНСТИТУТ СИСТЕМНОГО АНАЛИЗА РАН Г.С.Осипов Структура достижимых состояний динамических систем, основанных на правилах

Введение Около 20 лет исследуются так называемые гибридные динамические системы, в которых присутствуют как континуальная так и дискретная части: дифференциальные автоматы, модель Нерода-Кона, модель Брокета и некоторые другие. Поведение таких систем изучается посредством топологизации состояний и сведения задчи к методам, применяемым обычно в системах с континуальными переменными.

Введение Системы, которые в отличие от гибридных систем обладают более сложно устроенными состояниями чем таблица состояний «дискретной» части или вектор фазового пространства «континуальной» части гибридной системы. Область применения - моделирование искусственных, экологических, биологических и иных систем, структура которых и состояния не имеют априорного, а законы поведения и его цели - аналитического описания.

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

Системы, основанные на знаниях Не известны: точные описания состояний; точное описание динамики системы.

ПРИМЕРЫ 12 мая температура воды 14 градусов 12 мая течение слабое Направление течения: северо-западное Соленость воды: низкая Зоопланктон не размножается Цель: изгнание соперника из стада Цель: облет станции

ПРИМЕРЫ Правило 1. УСЛОВИЕ температура воды высокая, солёность низкая или средняя СПИСОК ДОБАВЛЯЕМЫХ ФАКТОВ зоопланктон размножается СПИСОК УДАЛЯЕМЫХ ФАКТОВ зоопланктон не размножается

ПРИМЕРЫ Правило 2. УСЛОВИЕ зоопланктон размножается, течение слабое СПИСОК ДОБАВЛЯЕМЫХ ФАКТОВ рост биомассы популяции, биомасса популяции (t+1) СПИСОК УДАЛЯЕМЫХ ФАКТОВ уменьшение биомассы популяции

ПРИМЕРЫ Правило 3.(ВЫБОР ЦЕЛИ) УСЛОВИЕ направление линии визирования = неизвестно СПИСОК ДОБАВЛЯЕМЫХ ФАКТОВ цель: = поиск станции СПИСОК УДАЛЯЕМЫХ ФАКТОВ остальные цели

ПРИМЕРЫ Правило 4.(ВЫБОР ЦЕЛИ) УСЛОВИЕ угол (АL,V), резерв времени СПИСОК ДОБАВЛЯЕМЫХ ФАКТОВ цель: = зависание СПИСОК УДАЛЯЕМЫХ ФАКТОВ остальные цели

ПРИМЕРЫ Правило 5. (ВЫЧИСЛЕНИЕ ВЕКТОРА И МОМЕНТА СИЛЫ) УСЛОВИЕ цель = сближение, дистанция = D, вектор линии визирования = AL, угол промаха = СПИСОК ДОБАВЛЯЕМЫХ ФАКТОВ вектор силы := F(V,AL, Ox, t), момент силы := M(, F, AL,V, Ox, t)

ПРИМЕРЫ Правило 6.(ВЫБОР КОМБИНАЦИИ ВКЛЮЧАЕМЫХ ДВИГАТЕЛЕЙ) УСЛОВИЕ nтакта= четный, F 0, угол (F,F(Cn)), F - F(Cn) СПИСОК ДОБАВЛЯЕМЫХ ФАКТОВ C(t+1):= Cn СПИСОК УДАЛЯЕМЫХ ФАКТОВ C(t)

ПРИМЕРЫ Правило 7.(ВЫБОР КОМБИНАЦИИ ВКЛЮЧАЕМЫХ ДВИГАТЕЛЕЙ) УСЛОВИЕ nтакта= нечетный, M 0, угол (M,M(Cn)), M - M(Cn) СПИСОК ДОБАВЛЯЕМЫХ ФАКТОВ C(t+1):= Cn СПИСОК УДАЛЯЕМЫХ ФАКТОВ C(t)

ПРАВИЛА Правило: П =, C, A и D - множества атомарных формул языка L - например, многосортный язык исчисления предикатов первого порядка. Факт – замкнутая атомарная формула языка L. Формула превращается в факт в результате подстановок значений на места переменных.

C – условие правила, A – множество формул, таких, что соответствующие им факты добавляются в состояние в результате применения правила, D – множество формул, таких, что соответствующие им факты удаляются из состояния в результате применения правила. Для каждого правила A D=.

ПРАВИЛА Два класса правил R и R. С правилом класса R связывается некоторое действие, производимое исполнительным органом, либо процедура, вычисляющая и присваивающая некоторой переменой значения некоторых атрибутов по значениям других атрибутов. С правилами класса R не связывается никаких действий, они не изменяют окружающей действительности, но изменяют знания о ней.

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

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

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

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

Стратегия управления 1 Если множество правил упорядочено, например, в алфавитном порядке (по первой букве, затем по второй и т.д.), то стратегия управления имеет следующий вид: 1.Выбрать очередное правило Пi из множества правил; 2.Проверить выполнимость условия Сi в текущем состоянии рабочей памяти; 3.Если Сi выполнено, то подставить на места всех свободных переменных в формулы из Сi, Аi и Di соответствующие значения параметров из базы данных. Иначе перейти к п.1; 4. Применить правило, т.е. записать в рабочую память те значения, на которых оказались выполненными формулы из Аi и удалить из рабочей памяти значения, на которых оказались выполнены формулы из Di. Перейти к п.1. Условием завершения процесса является стабилизация состояния рабочей памяти.

ДИНАМИЧЕСКИЕ СИСТЕМЫ, ОСНОВАННЫЕ НА ПРАВИЛАХ Обозначим описанный процесс через К и положим K(x, П )= (x) K(x, П )= (x), где П R, П R. (x) – функция замыкания, (x) – функция переходов.

ДИНАМИЧЕСКИЕ СИСТЕМЫ, ОСНОВАННЫЕ НА ПРАВИЛАХ Осталось ввести время: для этого в языке выделим сорт переменной t, которая может принимать значения из линейно упорядоченного дискретного множества T.

ДИНАМИЧЕСКИЕ СИСТЕМЫ, ОСНОВАННЫЕ НА ПРАВИЛАХ H = X, T,, - динамическая система, основанная на правилах, где : 2 х 2 х : 2 х Т 2 х

ДИНАМИЧЕСКИЕ СИСТЕМЫ, ОСНОВАННЫЕ НА ПРАВИЛАХ Состояние системы - неподвижная точка уравнения () = Предельное состояние системы - неподвижная точка уравнения ( (), t) = где 2 х индуцируется на 2 х Т функцией индуцируется на 2 х функцией

ДИНАМИЧЕСКАЯ СИСТЕМА С ЦЕЛЕНАПРАВЛЕНЫМ ПОВЕДЕНИЕМ Задано некоторое 2 х с определенным на нем нетранзитивным, асимметричным и антирефлексивным бинарным отношением ( ) - отношение предпочтения; тогда множество целей, а D = - динамическая система с целенаправленным поведением.

ДИНАМИЧЕСКАЯ СИСТЕМА С ЦЕЛЕНАПРАВЛЕННЫМ ПОВЕДЕНИЕМ Пусть Процедура : 2 х 2 х МНОЖЕСТВО ПЛАНОВ, вырабатывающая план достижения цели из состояния - процедура планирования.

ДИНАМИЧЕСКАЯ СИСТЕМА С ЦЕЛЕНАПРАВЛЕННЫМ ПОВЕДЕНИЕМ Стратегия управления Выбирается цель из множества - наиболее предпочтительная в смысле отношения. 2. Выполняется процедура планирования. 3. Если план существует, то реализуется соответствующее поведение и ОСТАНОВ, иначе Выбирается следующая цель 1 в смысле отношения Выполняется процедура планирования, Если план существует, реализуется Стратегия 1 для достижения 1; если нет – переход к п.4., Переход к п.1.

ПРИМЕР поведение обезьяны: «СОПЕРНИК- БАНАН-СОПЕРНИК», поведение активного корабля: «СТЫКОВКА- ОБЛЕТ- СТЫКОВКА».

ДИНАМИЧЕСКАЯ СИСТЕМА С ЦЕЛЕНАПРАВЛЕННЫМ ПОВЕДЕНИЕМ Получены результаты: об устойчивости таких систем и их управляемости (в смысле компенсации возмущений и в смысле достижимости) о связи архитектур баз знаний с достижимостью состояний и существованием планов поведения

Классификация динамических систем, основанных на правилах. Система H1: П= С, P(t, y),, Система H1: П= С, P(t, y),, P(t, y) – добавляемый факт; P(t, y) – добавляемый факт; Система H2: П= С, P(t, y), Ф (t, z), P(t, y) – добавляемый факт, Ф (t, z) - удаляемый факт; Система H2: П= С, P(t, y), Ф (t, z), P(t, y) – добавляемый факт, Ф (t, z) - удаляемый факт; Система H3: П1= С, {P(t, y)}, {Ф (t, z)} Система H3: П1= С, {P(t, y)}, {Ф (t, z)} {P(t, y)} –множество добавляемых фактов, {P(t, y)} –множество добавляемых фактов, {Ф (t, z)} - множество удаляемых фактов. {Ф (t, z)} - множество удаляемых фактов.

Классификация динамических систем, основанных на правилах. S0 – начальное состояние систем H2 и H3. Система H21: H2, где P Ф = S0 – начальное состояние систем H2 и H3. Система H21: H2, где P Ф = Система H22: H2, где S0 Ф = Система H22: H2, где S0 Ф = Система H31: Н3, где P Ф 1 = Система H31: Н3, где P Ф 1 = Система H32: Н3, где S0 Ф 2 = Система H32: Н3, где S0 Ф 2 = Система H33: Н3, где P Ф Система H33: Н3, где P Ф S0 Ф, Ф = Ф 1 Ф 2 S0 Ф, Ф = Ф 1 Ф 2

ПРЕДЕЛЬНЫЕ СОСТОЯНИЯ Р – объединение фактов, добавляемых всеми правилами; Ф – объединение фактов, удаляемых всеми правилами; S0 – начальное состояние;

ПРЕДЕЛЬНЫЕ СОСТОЯНИЯ Система Н1: S0 Р; Системы Н21, Н31 : (S0 / Ф) Р; Системы Н22, Н32, Н33: - стабилизация состояний не наступает;

предельные траектории В Н22, Н32, Н33 наступает стабилизация траекторий со второго «витка»

Структура предельных состояний и траекторий Н1 Н21 Н22

Структура предельных состояний и траекторий Н1 Н31 Н32 Н33

Учет применимости правил

СВОДКА РЕЗУЛЬТАТОВ Устойчивость и управляемость. Устойчивость и управляемость. Пусть I - некоторое возмущение в состоянии Si, т.е. i=Si {I}и имеет место I. Тогда для состояния Si+1 имеем Si+1 = ( ( (Si {I}))). Пусть I - некоторое возмущение в состоянии Si, т.е. i=Si {I}и имеет место I. Тогда для состояния Si+1 имеем Si+1 = ( ( (Si {I}))). Определение 1. Траектория называется устойчивой, если для любого состояния Si и возмущения I Определение 1. Траектория называется устойчивой, если для любого состояния Si и возмущения I ( ( (Si))) ( ( (Si {Ii}))). ( ( (Si))) ( ( (Si {Ii}))). Теорема 1. (достаточное условие устойчивости) Теорема 1. (достаточное условие устойчивости) Если и монотонны, то траектория системы устойчива. Если и монотонны, то траектория системы устойчива. Определение 2. База правил R полна в слабом смысле если найдется R1 – подмножество R, и найдется S – подмножество L(R), что S - подмножество A(R1) и пересечение S и D(R1) пусто, где A(R1) - объединение множеств всех фактов, добавляемых правилами из R1, D(R1) - объединение множеств всех фактов, удаляемых правилами из R1. Определение 2. База правил R полна в слабом смысле если найдется R1 – подмножество R, и найдется S – подмножество L(R), что S - подмножество A(R1) и пересечение S и D(R1) пусто, где A(R1) - объединение множеств всех фактов, добавляемых правилами из R1, D(R1) - объединение множеств всех фактов, удаляемых правилами из R1.

СВОДКА РЕЗУЛЬТАТОВ Определение 3. Если X - множество состояний модели, Определение 3. Если X - множество состояний модели, то пара точек (x0,x1) в XґX называется N–достижимой, если существуют такие управления U(j) НL (j=0,1,…,N-1), что x1 Нx(N), при начальных условиях x(0) Н x0 U(0), где x(N) - решение уравнения состояния. то пара точек (x0,x1) в XґX называется N–достижимой, если существуют такие управления U(j) НL (j=0,1,…,N-1), что x1 Нx(N), при начальных условиях x(0) Н x0 U(0), где x(N) - решение уравнения состояния. Определение 4. Если пара точек (x0,x1) N–достижима и в траектории, доставляющей решение уравнению (5.1) каждый факт Ф из x(N) встречается не более, чем в одном правиле, то пара точек (x0,x1) называется эффективно N – достижимой. Теорема 3. База правил R полна в слабом смысле тогда и только тогда, когда в XхX найдутся пара точек (x0,x1) и управления U(j), такие что (x0, x1 ) – эффективно N - достижима. Теорема 3. База правил R полна в слабом смысле тогда и только тогда, когда в XхX найдутся пара точек (x0,x1) и управления U(j), такие что (x0, x1 ) – эффективно N - достижима. Определение 5. База правил R полна, если для всякого Ф L(R), Ф А(R) и A(R) D(R)=, где A(R) - объединение множеств всех фактов, добавляемых правилами из R, D(R) - объединение множеств всех фактов, удаляемых правилами из R. Определение 5. База правил R полна, если для всякого Ф L(R), Ф А(R) и A(R) D(R)=, где A(R) - объединение множеств всех фактов, добавляемых правилами из R, D(R) - объединение множеств всех фактов, удаляемых правилами из R. Определение 6. Система называется полностью достижимой, если для любой пары точек (x0, x1), найдется N, что пара (x0, x1) является эффективно N - достижимой. Определение 6. Система называется полностью достижимой, если для любой пары точек (x0, x1), найдется N, что пара (x0, x1) является эффективно N - достижимой. Теорема 4. Система полностью достижима, если и только если база правил R полна. Теорема 4. Система полностью достижима, если и только если база правил R полна.

СВОДКА РЕЗУЛЬТАТОВ Существование плана и достижимость Определение 7. Планом достижения состояния из состояния будем называть последовательность П = правил П1, П2, …, Пk и управлений U1, U2,…,U k удовлетворяющие следующим свойствам: Определение 7. Планом достижения состояния из состояния будем называть последовательность П = правил П1, П2, …, Пk и управлений U1, U2,…,U k удовлетворяющие следующим свойствам: 1)каждое правило последовательности является допустимым; 1)каждое правило последовательности является допустимым; 2) Н S (П1, П2, …, Пk). 2) Н S (П1, П2, …, Пk). Определение 8. Пусть Mi – состояние, которое достигнуто перед применением правила Пi+1. Правило Пi назовем результативным, если A(Пi)З Mi 0. Определение 8. Пусть Mi – состояние, которое достигнуто перед применением правила Пi+1. Правило Пi назовем результативным, если A(Пi)З Mi 0.

СВОДКА РЕЗУЛЬТАТОВ Теорема 5. Следующая процедура есть процедура планирования: Теорема 5. Следующая процедура есть процедура планирования: 1.Пусть S есть целевое состояние, Mi текущее состояние, а П1, П2, …, Пk–множество результативных правил. 1.Пусть S есть целевое состояние, Mi текущее состояние, а П1, П2, …, Пk–множество результативных правил. 2. Пусть текущим является правило Пi, тогда 2. Пусть текущим является правило Пi, тогда Mi-1 = Mi\ A(Пi ) ИC(Пi); Mi-1 = Mi\ A(Пi ) ИC(Пi); 3. Выполняется проверка MjНMi-1, где j>i-1. Если это выполняется, то текущим множеством целей становится Mi- 1, в противном случае текущим становится правило Пi Выполняется проверка MjНMi-1, где j>i-1. Если это выполняется, то текущим множеством целей становится Mi- 1, в противном случае текущим становится правило Пi Если результативных правил не осталось, то текущим множеством целей становится Mi+1, правило же, приведшее к Mi считается неудачным. 4. Если результативных правил не осталось, то текущим множеством целей становится Mi+1, правило же, приведшее к Mi считается неудачным. Правила остановки: Правила остановки: 1. MiН S0 1. MiН S0 2. Mi =S и результативных правил не осталось. 2. Mi =S и результативных правил не осталось..

Сводка результатов Теорема 6. Для всякой пары точек (x0,x1) XхX план П = П = существует тогда и только тогда, когда (x0, x1 ) – N - достижима Теорема 6. Для всякой пары точек (x0,x1) XхX план П = П = существует тогда и только тогда, когда (x0, x1 ) – N - достижима

ПУБЛИКАЦИИ ПО ТЕМЕ Gennady Osipov. Developing Models of a World with Regard for its Dynamics - General Principles. Proc. of SCI'97 - World Multiconference on Systemics, Cybernetics and Informatics, Vol.3, Caracas, Venezuela, Gennady Osipov. Developing Models of a World with Regard for its Dynamics - General Principles. Proc. of SCI'97 - World Multiconference on Systemics, Cybernetics and Informatics, Vol.3, Caracas, Venezuela, Gennady Osipov. Applied semiotics and intelligent control. Proc. of the Second Workshop on Applied Semiotics 7-th Int. Conference AIICSR97, Slovakia, 1997 Gennady Osipov. Applied semiotics and intelligent control. Proc. of the Second Workshop on Applied Semiotics 7-th Int. Conference AIICSR97, Slovakia, 1997 Gennady Osipov. Dynamics in Integrated Knowledge- Based Systems. Proceedings of the 1998 IEEE `Symposium on Intelligent control, Gaithersburg, MD, USA, 1998 Gennady Osipov. Dynamics in Integrated Knowledge- Based Systems. Proceedings of the 1998 IEEE `Symposium on Intelligent control, Gaithersburg, MD, USA, 1998

Публикации по теме Osipov G. Sazonova L., Intelligent system for fish stock prediction and allowable catch evaluation. Environmental modelling & software, Elsevier Science Ltd., Volume 14, issue 5, 1999 Osipov G. Sazonova L., Intelligent system for fish stock prediction and allowable catch evaluation. Environmental modelling & software, Elsevier Science Ltd., Volume 14, issue 5, 1999 А.Б.Беляев, Е.П.Куршев, Г.С. Осипов. Интеллектуальная технология поддержки лечебно- диагностического процесса. Сб. Программные системы: Теоретические основы и приложения. М. Наука, Физматлит, 1999 А.Б.Беляев, Е.П.Куршев, Г.С. Осипов. Интеллектуальная технология поддержки лечебно- диагностического процесса. Сб. Программные системы: Теоретические основы и приложения. М. Наука, Физматлит, 1999

ПУБЛИКАЦИИ ПО ТЕМЕ Осипов Г.С. Дискретные динамические модели, основанные на знаниях: архитектура, планирование, управляемость. Труды 4-го международного семинара по прикладной семиотике, семиотическому и интеллектуальному управлению ASC99, Москва, ПАИМС, 1999 Осипов Г.С. Дискретные динамические модели, основанные на знаниях: архитектура, планирование, управляемость. Труды 4-го международного семинара по прикладной семиотике, семиотическому и интеллектуальному управлению ASC99, Москва, ПАИМС, 1999 Лебедева Т.Г. Осипов Г.С. Архитектура и управляемость дискретных динамических систем, основанных на знаниях. Известия АН. Теория и системы управления. М: Наука, 2000, 5, Лебедева Т.Г. Осипов Г.С. Архитектура и управляемость дискретных динамических систем, основанных на знаниях. Известия АН. Теория и системы управления. М: Наука, 2000, 5, Gennady Osipov. Attainable Sets and Knowledge Base Architecture in Discrete Dynamic Knowledge-based Systems. Proc. of the ECAI th European Conference of Artificial Intelligence. Berlin.2000, Gennady Osipov. Attainable Sets and Knowledge Base Architecture in Discrete Dynamic Knowledge-based Systems. Proc. of the ECAI th European Conference of Artificial Intelligence. Berlin.2000, 39-43

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

ПУБЛИКАЦИИ ПО ТЕМЕ Г.С.Осипов. Интеллектуальные динамические системы и целенаправленное поведение. Научно - теоретический журнал «Искусственный интеллект», IПШI «Наука i ocвiтa», 2002, 2, Г.С.Осипов. Интеллектуальные динамические системы и целенаправленное поведение. Научно - теоретический журнал «Искусственный интеллект», IПШI «Наука i ocвiтa», 2002, 2, Виноградов А. Н., Осипов Г.С., Жилякова Л.Ю. Динамические интеллектуальные системы. Ч.1. Представление знаний и основные алгоритмы. Известия АН. Теория и системы управления, М: Наука, 2002, 6, Виноградов А. Н., Осипов Г.С., Жилякова Л.Ю. Динамические интеллектуальные системы. Ч.1. Представление знаний и основные алгоритмы. Известия АН. Теория и системы управления, М: Наука, 2002, 6, Виноградов А. Н., Осипов Г.С., Жилякова Л. Ю. Динамические интеллектуальные системы. Ч.2. Моделирование целенаправленного поведения. Известия АН. Теория и системы управления, М: Наука, 2003, 1. Виноградов А. Н., Осипов Г.С., Жилякова Л. Ю. Динамические интеллектуальные системы. Ч.2. Моделирование целенаправленного поведения. Известия АН. Теория и системы управления, М: Наука, 2003, 1.

Публикации по теме Осипов Г.С. Динамические модели и инструментальные программные средства, использующие экспертные и эмпирические знания. Труды 3-его расширенного семинара "Использование методов искусственного интеллекта и высокопроизводительных вычислений в аэрокосмических исследованиях." (АКИИ-03) Переславль-Залесский, 2003, с Осипов Г.С. Динамические модели и инструментальные программные средства, использующие экспертные и эмпирические знания. Труды 3-его расширенного семинара "Использование методов искусственного интеллекта и высокопроизводительных вычислений в аэрокосмических исследованиях." (АКИИ-03) Переславль-Залесский, 2003, с Г.И. Назаренко, Г.С. Осипов. Основы теории медицинских технологических процессов. Часть1.- М.: ФИЗМАТЛИТ, 2005 Г.И. Назаренко, Г.С. Осипов. Основы теории медицинских технологических процессов. Часть1.- М.: ФИЗМАТЛИТ, 2005