'

ИНСТИТУТ СИСТЕМНОГО АНАЛИЗА РАН Г.С.Осипов gos@isa.ru

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

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


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

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


Слайд 15

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


Слайд 16

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


Слайд 17

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


Слайд 18

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


Слайд 19

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


Слайд 20

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


Слайд 21

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


Слайд 22

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


Слайд 23

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


Слайд 24

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


Слайд 25

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


Слайд 26

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


Слайд 27

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


Слайд 28

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


Слайд 29

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


Слайд 30

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


Слайд 31

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


Слайд 32

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


Слайд 33

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


Слайд 34

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


Слайд 35

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


Слайд 36

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


Слайд 37

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


Слайд 38

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


Слайд 39

СВОДКА РЕЗУЛЬТАТОВ Определение 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) - решение уравнения состояния. Определение 4. Если пара точек (x0,x1) N–достижима и в траектории, доставляющей решение уравнению (5.1) каждый факт Ф из x(N) встречается не более, чем в одном правиле, то пара точек (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. Определение 6. Система называется полностью достижимой, если для любой пары точек (x0 , x1), найдется N, что пара (x0 , x1) является эффективно N -достижимой. Теорема 4. Система полностью достижима, если и только если база правил R полна.


Слайд 40

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


Слайд 41

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


Слайд 42

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


Слайд 43

ПУБЛИКАЦИИ ПО ТЕМЕ 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, 1997. Gennady Osipov. Applied semiotics and intelligent control. Proc. of the Second Workshop on Applied Semiotics 7-th Int. Conference AIICSR’97, Slovakia, 1997 Gennady Osipov. Dynamics in Integrated Knowledge-Based Systems. Proceedings of the 1998 IEEE `Symposium on Intelligent control, Gaithersburg, MD, USA, 1998


Слайд 44

Публикации по теме 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


Слайд 45

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


Слайд 46

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


Слайд 47

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


Слайд 48

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


×

HTML:





Ссылка: