Содержание к диссертации
Введение
ГЛАВА 1. Моделирование времени в искусственном интеллекте 15
1.1. Значение и основные свойства времени 15
1.2. Моделирование времени в ИИ и компьютерных науках 20
1.2.1. Фактор времени в ИИ 20
1.2.2. Области приложения и направления исследований 21
1.2.3. Основные задачи, использующие фактор времени 25
1.2.4. Основные подходы к представлению времени в ИИ 27
1.2.5. Задачи, связанные с введением фактора времени 30
1.2.6. Направления исследований 33
1.3. Сравнительный анализ систем 34
1.4. Фактор времени в ИСППР — уточнение задач исследования 37
1.4.1. Время в современных инструментальных средствах разработки ЭС 37
1.4.2. ИСППР РВ семиотического типа 39
1.4.3. Особенности ИСППР РВ для помощи ЛПР при управлении сложными техническими объектами 41
1.4.4. Требования к разработке моделей времени в ИСППР РВ 45
1.5. Выводы по главе 1 46
ГЛАВА 2. Методика построения моделей времени 47
2.1. Требования к разработке моделей времени 47
2.2. Структура модели времени 50
2.3. Онтология времени 53
2.4. Теории времени 57.
2.4.1. Алгебраическое представление структуры времени 58
2.4.2. Сравнительный анализ теорий времени 59
2.5. Методы временной квалификации 65
2.5.1. Метод временных аргументов 67
2.5.2. Модальная временная логика 68
2.5.3. Метод овеществления утверждений 69
2.5.4. Расширения метода овеществления 72
2.6. Теория временных утверждений 74
2.7. Языки представления и механизмы вывода 78
2.8. Сравнение моделей времени 83
2.9. Методика построения моделей явного представления времени . 83
2.10. Выводы по главе 2 86
ГЛАВА 3. Алгебраические методы представления временных зависимостей 87
3.1. Задача согласования временных ограничений 87
3.1.1. Основные определения и задачи 88
3.1.2. Методы решения ЗСВО 91
3.2. Модели на основе качественной точечной ЗСВО 93
3.3. Качественные интервальные ЗСВО: алгебра Аллена 98
3.3.1. Определения 98
3.3.2. Полиномиальные подклассы 102
3.3.3. Алгоритмы решения ЗСВО 106
3.4. Обобщенный алгоритм решения ЗСВО 119
3.5. Качественные точечно-интервальные ЗСВО 123
3.6. Метрические точечные ЗСВО 127
3.7. Комбинированные качественные и метрические ЗСВО 133
3.8. Комбинированные ЗСВО с длительностями.. 135
3.9. Сравнительный анализ моделей ... 137.
3.10. Классификация моделей представления временных зависимостей.. 141
3.11. Выводы по главе 3 143
ГЛАВА 4. Реализация системы представления временных зависимостей 144
4.1. Основные требования и функции СПВЗ 144
4.2. Принципы построения СПВЗ 147
4.3. Архитектура СПВЗ 150
4.4. Программная реализация СПВЗ 157
4.5. Экспериментальное исследование алгоритмов 159
4.5.1. Методы получения тестовых данных 159
4.5.2. Методы проведения экспериментов и анализа результатов 161
4.5.3. Результаты экспериментов 162
4.6. Выводы по главе 4 166
ГЛАВА 5. Пример применения системы представления временных зависимостей в интеллектуальной системе поддержки принятия решений реального времени . 168
5.1. Описание объекта .. 168
5.2. Прототип ИСППР РВ ... 170
5.2.1. Схема функционирования . 170
5.2.2. Прогнозирование с временными зависимостями 170
5.3. Описание разработанной модели времени 176
5.3.1. Онтология времени 176
5.3.2. Методы представления временных зависимостей 179
5.3.3. Метод временной квалификации 181
5.3.4. Теория временных утверждений 181
5.3.5. Язык представления и алгоритмы вывода 182
5.4. Модель прогнозирования состояния НТУ СУЗ 184
5.4.1. Описание параметров НТУ СУЗ 184.
5.4.2. Диагнозы на входе блока прогнозирования 185
5.4.3. Правила прогнозирования состояния элементов НТУ СУЗ 186
5.5. Пример прогнозирования последствий аномальных ситуаций 190
5.6. Выводы по главе 5 191
Заключение 193
Литература 195
Приложения 225
- Основные подходы к представлению времени в ИИ
- Особенности ИСППР РВ для помощи ЛПР при управлении сложными техническими объектами
- Методика построения моделей явного представления времени
- Прогнозирование с временными зависимостями
Введение к работе
В диссертационной работе исследованы и реализованы методы, модели и программные средства представления временных (темпоральных) зависимостей в интеллектуальных системах (ИС) типа интеллектуальных систем поддержки принятия решений (ИСППР).
На основе полученных результатов разработана архитектура и выполнена программная реализация системы представления временных зависимостей (СПВЗ), предназначенной для использования ее в составе современных ИС типа ИСППР реального времени (ИСППР РВ) [1].
Реализованная СПВЗ применена при решении задачи прогнозирования в рамках прототипа ИСППР РВ для поддержки операторов сложных технических объектов на примере энергоблока.
Актуальность темы исследования.
Время является неотъемлемым атрибутом любой эволюционирующей системы. Каждое изменение происходит во времени, будь то процесс управления сложным техническим объектом, выполнение компьютерной программы и т.д.
Функционирование любого сложного объекта состоит из множества процессов, происходящих во времени. Соответственно, для мониторинга и управления таким объектом необходимо уметь не только отслеживать и представлять происходящие во времени процессы и изменения, но и прогнозировать развитие процессов и последствия принимаемых решений, используя при необходимости предысторию развития для анализа произошедших изменений с целью выработки качественных решений для требуемого воздействия на объект.
В последнее время активно разрабатываются сложные компьютерные системы, предназначенные для помощи лицам, принимающим решения (ЛПР), при управлении сложными объектами и процессами различной природы в условиях жестких временных ограничений.
О важности наличия средств представления времени и временных (тем-, поральных) зависимостей (в данных и знаниях) в ИС говорится практически с момента появления таких систем (см., например, работы [2-5]), однако особенно актуальна эта проблема встала именно в связи с появлением и развитием динамических ИС, типичными представителями которых являются интеллектуальные системы поддержки принятия решений реального времени (ИСППР РВ) [1,6-8].
ИСППР РВ предназначены для помощи ЛПР при управлении сложными объектами и процессами в условиях жестких временных ограничений и наличия различного рода неопределенностей (неполноты, нечеткости, противоречивости и т.п.) как в поступающей извне информации, так и в заложенных (или полученных в процессе обучения) в систему экспертных знаниях, что влечет, в свою очередь, необходимость корректировки и пополнения информации непосредственно в процессе принятия решений.
ИСППР РВ относятся к классу интегрированных ИС, сочетающих строгие математические методы и модели поиска решения с нестрогими, эвристическими (логико-лингвистическими) моделями и методами, базирующимися на знаниях специалистов-экспертов, моделях человеческих рассуждений и накопленном системой опыте.
Важнейшей задачей при создании перспективных ИСППР РВ семиотического типа, способных к модификации и адаптации в процессе поиска решений, является задача представления и оперирования временными зависимостями, т.е. задача построения эффективных моделей времени, на основе которых можно моделировать рассуждения с учетом фактора времени. Учет временного фактора необходим при решении задач диагностики и мониторинга сложного объекта или процесса, планирования действий для достижения поставленной цели, прогнозирования последствий принимаемых решений, управления в реальном времени и обучения (тренировки) ЛПР [1,6,9].
Способность представлять временные зависимости, а также временные ограничения на события, происходящие в технической или организационной, системе, позволяет существенно сократить поисковые пространства в задачах диагностики, мониторинга, планирования и управления сложными процессами [8-Ю]. Однако, в настоящее время отсутствуют развитые средства представления временных зависимостей в современных инструментальных средствах конструирования ИС, включая ИСППР РВ. Известные и дорогостоящие инструментальные комплексы типа G2, RTworks и др., а также языки искусственного интеллекта типа CLIPS имеют лишь примитивные средства отображения фактора времени.
Большая практическая значимость ИСППР РВ и необходимость использования в них адекватных предметным областям (ПО) и эффективных (в плане выразительности и реализуемости) моделей времени обуславливает актуальность исследования.
Отметим, что возможность представления временных зависимостей также важна для понимания естественного языка, при программировании автономных агентов (роботов), формировании корпоративных баз знаний ив других многочисленных приложениях ИИ.
Выполненные исследования опираются на результаты работ в области ИИ и конструирования ИС Д. А. Поспелова, Э. В. Попова, О. Й. Ларичева, A. А. Башлыкова, В. Н. Вагина, В. В. Емельянова, А. П. Еремеева, О. П. Кузнецова, В. М. Курейчика, А. С. Нариньяни, Г. С. Осипова, Г. С. Плесневича, B. А. Смирнова, И. Б. Фоминых и др., а также зарубежных ученых J. Allen, R. Dechter, J; McCarthy, F. Barber, P. van Веек, В: Nebel, A. Gerevini, P. Hayes, L. Vila, E. Schwalb, H; Kautz, P. Ladkin, M. Koubarakis, S. Staab, P. Jonsson, D. McDermott, Y. Shoham, G. Ferguson.
Целью работы является исследование и разработка моделей, методов и программных средств представления и оперирования временными зависимо стями, повышающих эффективность и расширяющих интеллектуальные возможности современных компьютерных систем типа ИСППР РВ.
Для достижения указанной цели необходимо решить следующие задачи:
- исследование методов и моделей представления временных зависимостей в ИС;
- разработка методики построения моделей с явным представлением времени, ориентированных на использование в ИСППР РВ;
- сравнительный анализ и классификация основных моделей представления временных зависимостей в плане их применимости в ИСППР РВГ выделение моделей с полиномиальными алгоритмами;
- разработка архитектуры СПВЗ, на основе которой реализуется временной вывод (временные рассуждения) в ИСППР РВ;
- разработка и программная реализация СПВЗ;
- использование разработанной СПВЗ для решения задачи прогнозирования в рамках прототипа ИСППР РВ для оперативно-диспетчерского персонала энергоблока и в других приложениях.
Методы исследования. Поставленные задачи решаются с использованием методов дискретной математики, математической логики, искусственного интеллекта, теории графов, теории алгебраических моделей и методов анализа вычислительной сложности алгоритмов.
Достоверность научных положений. Достоверность научных результатов подтверждена теоретическими выкладками, данными компьютерного моделирования, а также сравнением полученных результатов с результатами, приведенными в научной литературе.
Научная новизна.
Новыми являются:
1. Классификация моделей представления временных зависимостей, позволяющая выбирать модель с заданными свойствами.
2. Методика построения моделей времени для ИСППР РВ.
3. Архитектура системы представления временных зависимостей для. ИСППР РВ.
4. Обобщенный алгоритм решения задачи согласования временных ограничений, позволяющий сократить среднее время поиска решения.
Практическая значимость. Практическая значимость работы заключается в создании программной системы представления временных зависимостей, повышающей эффективность и расширяющей интеллектуальные возможности компьютеров и компьютерных систем на примере ИСППР РВ при решении задач мониторинга и управления сложными объектами и процессами.
Практическая значимость работы подтверждается использованием разработанной СПВЗ в прототипе ИСППР РВ для оперативно-диспетчерского персонала энергоблока и в других приложениях, о чем имеются акты о внедрении.
Реализация результатов. Разработанная СПВЗ использована в ЦНИИКА в составе блока прогнозирования прототипа ИСППР РВ для оперативно-диспетчерского персонала энергоблока, в учебно-научном процессе кафедры Прикладной математики МЭИ(ТУ) и кафедры ТОЭ Таганрогского государственного радиотехнического университета (ТІ РТУ), что подтверждается соответствующими актами о внедрении, приведенными в приложениях.
Результаты работы использованы в НИР, выполненных в.рамках грантов РФФИ, проекты №99-01-00049 и №02-07-90042 по тематике «Исследование и разработка инструментальных средств создания экспертных систем семиотического типа»; проект №02-07-90042 «АНО» «Модели и методы представления временной (темпоральной) информации в интеллектуальных системах», грантов РФФИ для аспирантов и стуцентов, проекты №01-01-06356 «МАС» и №03-07-06034 «МАС» и в рамках Федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 годы по теме «Системы мониторинга и. поддержки принятия решений на основе аппарата нетрадиционных логик».
Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на 5-й, 6-ой, 7-ой, 8-ой и 9-ой научных конференциях аспирантов и студентов «Радиотехника, электроника, энергетшса» в МЭИ(ТУ), (г. Москва, 1999 - 2003 г.г.), на 3-й и 4-ой международных летних школах-семинарах по искусственно интеллекту для студентов и аспирантов (Браславская школа) (Беларусь, г. Браслав, 1999, 2000 г.г.), на международной научно-технической конференции «Интеллектуальные САПР» (Россия, п. Дивноморское, 2000 г.), на 2-м международном конгрессе студентов, молодых ученых и специалистов «Молодежь и наука — третье тысячелетие» (г. Москва, 2002 г.), на «Научных сессиях МИФИ» (г. Москва, 2000 - 2004 г.г.), на 7-й национальной конференщш по искусственному интеллекту с международным участием КИИ 2000 (г. Переславль-Залесский, 2000 г.), на Международном конгрессе «Искусственный интеллект в XXI веке» (Россия, п. Дивно-морское, 2001 г.), на 8-й национальной конференции по искусственному интеллекту с международным участием КИИ 2002 (г. Коломна, 2002 г.), на Международных форумах информатизации МФИ-2001 и МФИ-2003 (Международные конференции «Информационные средства и технолопш») (г. Москва, 2001, 2003 г.г.), на Международной научно-технической конференций «Интеллектуальные системы» AIS 03 (Россия, п. Дивноморское, 2003 г.).
Публикации. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 19 печатных работах.
Структура и объем работы Диссертация состоит из введения, пяти глав, заключения, списка использованной литературы (285 наименований) и приложений. Диссертация содержит 240 страниц машинописного текста.
Краткое содержание
В первой главе проводится анализ методов и моделей представления, временных зависимостей в ИИ, выделяются два основных класса способов учета фактора времени в ИИ. Анализируются недостатки и достоинства выделенных классов и показывается необходимость построения моделей явного представления времени для использования в ИСППР РВ. Уточняются задачи диссертации в плане разработки методики построения моделей явного представления времени для ИСППР РВ и СПВЗ. Формулируются основные требования к разработке СПВЗ для использования её в составе ИСППР РВ для решения задачи прогнозирования.
Во второй главе исследуются методы построения моделей явного представления времени в ИИ. Предлагается методика построения моделей явного представления времени для использования в ИСППР РВ. Анализируются ключевые решения при построении таких моделей. Описываются основные альтернативы при задании свойств создаваемой модели времени и результаты влияния принятых альтернатив на получаемую модель времени, как с точки зрения выразительности модели времени, так и вычислительной эффективности алгоритмов вывода.
В третьей главе проводится анализ основных алгебраических моделей представления временных зависимостей в виде задачи согласования временных ограничений (ЗСВО). Выделяются модели с полиномиальными подклассами для использования в СПВЗ для ИСППР РВ. Исследуются алгоритмы решения ЗСВО для выделенных моделей и определяются пути модификации этих алгоритмов в плане улучшения производительности. Предлагается обобщенный алгоритм поиска решения на примере интервальной качественной ЗСВО. Разрабатывается классификация основных алгебраических моделей представления временных зависимостей на основе ЗСВО по выразительным возможностям, позволяющая выбирать модель с заданными свойствами для СПВЗ:
В четвертой главе формулируются принципы построения СПВЗ для ИСППР РВ. Разрабатывается интерфейс и архитектура СПВЗ. Описывается программная реализация СПВЗ. Приводятся результаты экспериментов по сравнению предложенного обобщенного алгоритма решения ЗСВО с известными. Показывается его эффективность в плане сокращения среднего времени поиска решения ЗСВО на тестовых примерах.
В пятой главе рассматривается пример практического применения СПВЗ для решения задачи прогнозирования состояния сложного технического объекта в рамках ИСППР РВ. Описывается архитектура подсистемы прогнозирования с СПВЗ. Показывается применимость предложенной методики построения моделей явного представления времени для создания модели и языка представления данных/знаний, меняющихся во времени для подсистемы прогнозирования развития аномальных состояний в технологических системах АЭС. Показывается применимость СПВЗ для решения задачи прогнозирования в рамках прототипа ИСППР РВ на основе нетрадиционных логик, реализуемого на кафедре ПМ МЭИ(ТУ) совместно с ЦНИИКА для мониторинга и управления сложными объектами типа энергоблоков.
Основные подходы к представлению времени в ИИ
Временные базы данных и языки запросов. Область исследований, связанная с введением временного фактора в реляционную модель данных, разработкой языков запросов и построением систем на этой основе. Многие работы пересекаются с работами в области ИИ, поскольку базы данных (БД) с временной размерностью необходимы и используются во многих областях и приложениях ИИ. Более детально вопросы временных БД освящены в [35-38];
Календарное планирование. Область исследований, традиционно относящаяся к исследованию операций. Основные задачи — это распределение ограниченных ресурсов между множеством потребителей во времени. Для решения таких задач используются методы линейного программирования и различные оптимизационные методы. Время рассматривается как ресурс с особыми свойствами. Одним из методов решения задач в данном формализме является сведение их к задаче согласования ограничений -[39,40]. При этом возникает так называемое программирование в ограничениях ИЛИ недоопределенные вычисления [41-44]. Известно достаточно большое количество языков описания задач согласования ограничений и систем, в том числе и коммерческих, предназначенных для решения этих задач [42,43,45-47];
Разработка экспертных систем и СППР. Обширная область, охватывающая как конструирование ЭС и СППР, так и их применение [6,7, И, 12,48]. Если рассматривать статические экспертные системы, то введение фактора времени актуально, например, для ЭС в области медицины, в частности для диагностики и планирования терапии (рассуждение о времени появления симптомов и назначенном лечении) [49-56], в области диагностики и прогнозирования различных событий в природных, социальных и технических системах [1,48,50,57,58] ив других приложениях. Для динамических ЭС и СППР РВ, предназначенных для диагностики, мониторинга и управления сложными техническими объ-. ектами, фактор времени особенно важен, поскольку они должны решать задачи, связанные с прогнозом и анализом ситуаций, меняющихся во времени [6,7,10,48,58]. Более детально особенности построения моделей времени для таких систем будут рассмотрены далее в связи с основной целью диссертационной работы;
Корпоративные базы знаний, онтологии. Область представления знаний и разработки баз знаний является одной из центральных в ИИ [3,.1 Г, 38,59,60]. Многие современные приложения, в частности, разработка перспективных корпоративных баз знаний [61], опираются на структурированное (связное) описание объектов и понятий ПО, а также знаний о них и отношениях между ними, представленных виде так называемых онтологии [59]. Фактор времени является неотъемлемым при разработке онтологии, поскольку формализация понятия времени и его свойств важна для многих ПО, например, для разработки систем релевантного поиска в текстах [59,62-64];
Моделирование агентов. Онтологии являются основой для разработки различных распределенных систем, в частности, для моделирования агентов в МАС. Для описания агентов разрабатываются специальные языки, например, язык DAML (DARPA Agent Modelling Language) [62,65], в который включен язык TimeML и онтология, описывающая временные примитивы и отношения между ними [63]. Программирование агентов, т.е. построение модели их поведения и восприятия окружающего мира, опирается на моделирование действий агента, которые он может совершать по отношению к внешнему миру и другим агентам, а также событий, которые он может воспринимать извне [32]. В свою очередь, языки для представления действий и событий опираются на различные модели времени [66-68] Создание интеллектуальных автономных агентов тесно связано с областью планирования и управления роботами;
Планирование и робототехника. Достаточно обширная и бурно развивающаяся область, направленная на решение задач составления планов и их выполнения для управления различными автономными системами (роботами, зондами, и др.) [69-74]. В этой области важно уметь решать целый спектр задач, основанных на представлении и рассуждении о действиях и событиях, происходящих во времени, начиная от задач составления планов, распределения и согласования действий плана во времени (календарное планирование) и заканчивая задачами выполнения и коррекции планов в зависимости от внешних воздействий, прогнозирования состояния внешнего мира по наблюдаемым событиям и т.д. В последнее время наблюдается тенденция к усложнению используемых моделей времени в данной области [75-78];
Машинное обучение. При выделении общих принципов из последовательности действий или цепочки наблюдаемых явлений, в плане обучения необходимо использовать модели времени. Представление и оперирование временными зависимостями является инструментом, используемым в машинном обучении [79];
Понимание естественного языка и семантическое моделирование. Время—это неотъемлемый атрибут любого естественного языка (ЕЯ) [3,13]. Соответственно, системы понимания смысла ЕЯ требуют построения различных и достаточно богатых моделей времени, соответствующих моделируемому языковому фрагменту [80,81]. В последнее время перспективным подходом к пониманию смысла ЕЯ является использование онтологии. Исследования в области ЕЯ и семантического моделирования чрезвычайно актуальны и активно развиваются в настоящее время. Построенные ЕЯ-системы используются в различных, начиная от ЕЯ-запросов к БД [25,82], до семантического поиска и аннотирования (реферирования) документов в Интернете [65];
Особенности ИСППР РВ для помощи ЛПР при управлении сложными техническими объектами
Выделим задачи в рамках современных ИСППР РВ, предназначенных для помощи ЛПР при управлении сложными техническими объектами, где использование временных зависимостей и обеспечение временного вывода (поиска решений с использованием явных временных зависимостей) позволит повысить эффективность и расширить их возможности.
Рассмотрим современное состояние и требования по представлению временных зависимостей на примере системы «СПРИНТ РВ» [1,58], предназначенной для помощи оперативно-диспетчерскому персоналу энергоблоков при решении задач диагностики и управления, и прототипа ИСППР РВ для одной из подсистем энергоблока, созданной в среде G2-GDA [144].
В системе «СПРИНТ РВ» явные средства представления временных зависимостей не используются. Состояние технологического объекта управления (ТОУ) рассматривается как мгновенный снимок параметров объекта, используемый для решения задачи диагностики в режиме мониторинга и выдачи рекомендации ЛПР. Полученный вектор параметров объекта сохраняется в архиве для последующего анализа и документирования процесса управления. Таким образом, используется неявное представление времени, недостатки которого рассмотрены в п.п. 1.2.4. ТОУ характеризуются наличием как дискретных, так и непрерывных параметров. Диапазон значений непрерывных параметров обычно разбивают на диапазоны значений, важные для выполнения мониторинга и/или прогнозирования.
В то же время, технологические и регламентные инструкции для сложного ТОУ (типа энергоблока) характеризуются большим количеством временных ограничений, описывающих временные задержки при активизации и изменении режимов работы компонентов ТОУ Учет этих ограничений важен как на этапе выполнения последовательности действий для смены режимов функционирования ТОУ (ввода в эксплуатацию, ввод/выведение в/из режим(а) регламентного обслуживания и т.д.), так и при построении прогнозных моделей, позволяющих прогнозировать состояния ТОУ в реальном масштабе времени.
Отметим, что для ИСППР РВ подобного типа важно наличие единого языка запросов к архиву предыстории. Переход от точечной неявной модели времени на явную модель времени в данном случае представляется очень важным и перспективным, поскольку позволяет унифицированным образом формулировать запросы к архиву с учетом явных временных зависимостей. Наличие такого языка запросов с учетом временных зависимостей позволит повысить качество решения следующих задач: поиск причин и диагностика произошедших изменений в ОУ; обучение ЛПР; выявление неявных знаний ЛПР, путем анализа архива и построения экспертных правил, учитывающих временные зависимости. Для прогнозирования состояния ТОУ могут использоваться различные модели прогнозирования как непрерывные, основанные на дифференциальных уравнениях в частных производных и используемые в случае отсутствия нефакторов, так и качественные — экспертные модели, основанные на причинно-следственных зависимостях между элементами ТОУ, представленных с помощью различных логических методов и используемых в аномальных режимах функционирования ТОУ. Различные модели могут быть интегрированы в рамках единой ИСППР РВ семиотического типа. В данной работе идет речь о качественных моделях. Прогнозные модели могут строится на основе использования причинно-следственных зависимостей, описывающих поведение отдельных элементов объекта управления. При формализации причинно-следственных зависимостей вида: «если насос вышел из строя, то сработает защита теплообменника» для уточнения взаимоотношений между причинами и их последствиями необходимо задавать временные зависимости в явном виде. В результате уточнения может быть получена информация типа: «если насос вышел из строя, то защита теплообменника сработает в диапазоне от 2 до 5 минут». Таким образом, можно выделить следующие составляющие знаний о ПО: причинно-следственные зависимости о событиях, действиях и значениях параметров в ПО; временные зависимости, уточняющие взаимное положение причин, их последствий (эффектов) и длительностей. Подобная прогнозная модель, явно учитывающая временные зависимости, может быть использована для прогноза последствий текущей (или некоторой заданной) ситуации и ответа на запросы о будущем состоянии ТОУ. При этом, запросы могут быть как о времени появления некоторых событий (о времени истинности заданных утверждений), так и о факте наличия событий в определенный момент времени (какие утверждения истинны в заданный момент времени). Наличие такой подсистемы позволит ЛПР получать информацию (прогноз) о том, к чему приведет текущее отклонение в состоянии ТОУ. Разработка моделей, методов и программных средств представления временных зависимостей для построения таких подсистем в рамках ИСППР РВ является основной задачей данной работы. В настоящий момент в «СПРИНТ РВ» реализовано решение следующих задач: 1. Определение наличия отклонения в состоянии ТОУ (ответ на вопрос: «Есть ли аномалии?»). 2. Классификация отклонения по степени угрозы и определение причины аномального состояния ТОУ (ответ на вопрос: «Каков тип аномалии, степень её угрозы и причины?»). По результатам решения этих задач выдаются рекомендации ЛПР по приведению ТОУ в нормальный режим функционирования. Однако, прогнозных моделей с явным учетом временных зависимостей в системе нет. Определение последствий аномальной ситуации, т.е. ответ на вопрос: «К чему приведет данная ситуация?», позволит поднять уровень поддержки ЛПР в подобных ситуациях на качественно новый уровень.
Методика построения моделей явного представления времени
Механизмы вывода. Механизмы вывода являются производными от всех изложенных выше компонентов моделей времени. Они также зависят от задачи, в которой используются. В то же время, можно выделить основные направления в построения механизмов вывода.
Во-первых, это подход, основанный на расширение механизмов вывода, уже имеющихся в языке представления. Сюда также относятся механизмы, основанные на расширении дедуктивных механизмов вывода для логики предикатов первого порядка [95,97,99, 100]. В определенной степени близки к ним подходы построения механизмов вывода для модальных временных логик [115].
Интересным является подход формализации методов вывода в моделях времени в терминах задачи выполнимости множества формул исчисления высказываний [192].
Преобладающим подходом к построению механизмов вывода и ответов на запросы является использование (для проверки истинности временных зависимостей и вывода новых) методов решения задачи согласования временных ограничений, основанных на алгебраических моделях представления и манипулирования примитивами времени и отношениями между ними [122,155,193].
Рассмотрению алгебраических моделей представления временных зависимостей и методов решений задач согласования временных ограничений посвящена глава 3.
Теории, лежащие в основе механизма представления времени, влияют на основные свойства механизмов вывода и ответа на запросы о временных утверждениях и зависимостях в различных системах. Например в системах, отвечающих на запросы с временной компонентой, типа: «Был ли сбой в питании, когда контроллер послал аварийный сигнал?», «Когда были включены одновременно насос и охладитель?». Теория времени характеризует область определения временных ограничений и влияет на свойства процедуры согласования ограничений. Тогда как, теория временных утверждений оказывает влияние на полноту всей процедуры вывода на временных утверждениях.
Рассмотрим, например, параллельное выполнение двух задач, конкурирующих за некоторый ресурс. Теория временных утверждений позволяет вывести, что временные периоды, в течении которых эти задачи используют общий ресурс, не пересекаются1. Что, в свою очередь, приводит к распространению этого ограничения на остальные ограничения в базе и сокращению пространства поиска.
В продукционных языках для обеспечения работы механизма вывода на правилах необходимо определить процедуру поиска по образцу (унификации). Эта задача разбивается на две независимые подзадачи по унификации временных утверждений стандартными для многосортных языков способами и унификации временных зависимостей с помощью специальных алгоритмов ответов на запросы в рамках алгебраической модели представления временных зависимостей, реализованной в СПВЗ. После чего, полученные результаты объединяются. В соответствии с этим, ключевым моментом при встраивании в продукционные языки моделей времени является наличие СПВЗ, способной отвечать на запросы (осуществлять поиск образцу временных утверждений). СПВЗ также должна обеспечивать вывод с использованием временных зависимостей.
Соответственно наличие СПВЗ является важным и неотъемлемым компонентом любой системы представления и манипулирования знаниями, меняющимися во времени. Т.к. свойство не пересечения во времени событий типа «использование общего ресурса» задается в теории временных утверждений. В табл. 2.2 приведены сравнительные характеристики наиболее известных моделей времени [122,142,180,194] в соответствии с предложенной в п. 2.2. схемой. 2.9. Методика построения моделей явного представления времени Опишем методику построения явных моделей времени для ИСППР РВ, построенную на основе проведенного анализа. Подробные комментарии к каждому пункту методики, поясняющие тот или иной вариант выбора на каждом этапе были даны в соответствующих разделах данной главы. Таким образом, при построении модели явного представления времени для заданной ПО необходимо выполнить следующие этапы: 1. Построить онтологию времени: (a) Выбрать базовые примитивы времени. Использовать моменты и/или интервалы времени. При необходимости, использовать константы времени для обозначения моментов времени и интервалов (секунды, минуты, часы, дни, даты, время и т.д), а также примитив «длительность», соответствующий расстоянию между моментами времени; (b) Задать базовые отношения между примитивами. В соответствии с выбранными примитивами задать базовые отношения между ними; (c) Ввести необходимые элементарные функции преобразования примитивов и отношений. Часть функций строится на основе базовых отношений и является их функциональной версией. Функции позволяют осуществлять преобразования между временными примитивами.
Прогнозирование с временными зависимостями
Идея алгоритма согласования по путям заключается в следующем. Выбираются любые три вершины i,j и к в сети. Веса на ребрах (i,j) и (j,k) потенциально ограничивают значения весов на ребре (г, к), которое замыкает треугольник. Например, рассмотрим три вершины Stack(A, В), Оп(А, В) и «Целевое состояние» на рис. 3.2.
Из отношений между временными примитивами Stack(A,B) {m} Оп(А,В) и Оп(А,В) {сГ1} «Целевое состояние» можно заключить, что Stack(A, В) {Ь} «Целевое состояние» и, следовательно, можно изменить метку ребра на единичное множество, состоящие только из {b}. Для обеспечения такого вывода алгоритм использует операции пересечения (П) и композиции (о) ограничений и проверку Сік = С, - П ( о Сд- , где dk ограничение на ребре (г, к). В том случае, если С,- изменилось, это ребро может в дальнейшем ограничивать другие ребра и добавляется в список необработанных ребер при условии, что оно там не находилось. Алгоритм работает до тех пор, пока будут происходить какие либо изменения. Унарная операция инверсии также используется в алгоритме. Инверсия ребра— это инвертирование отношения, взвешивающего это ребро.
Для обеспечения эффективной работы алгоритма операции пересечения и композиции интервальных отношений должны быть реализованы эффективным образом (шаги 5 и 11). Пересечение. Операцию пересечения можно эффективно реализовать, если представлять интервальные отношения в виде битовых векторов, 13 младших бит 16 разрядного целого числа. Тогда операция пересечения двух отношений реализуется с помощью логической операции «И» над двумя целыми числами.
Композиция. Для оптимизации вычисления операции композиции используется ряд методов. Наилучший способ реализовывать композицию отношений — это использовать заранее вычисленную таблицу размером 213 х 213 = 67108864 ячеек памяти (минимум необходимо 2 байта под кодирование каждого отношения и необходима только верхне-диагональная матрица), где 213 = 8192 различных отношений. Т.е. под такую таблицу необходимо отвести около 64Мб памяти, что допустимо не всегда, поскольку сама ЗСВО требует для своего хранения также большого объема памяти. Однако, такой метод является предпочтительным с точки зрения производительности.
Существует несколько практически приемлемых методов для вычисления композиции с меньшими затратами памяти, например, в [122] предложен метод для вычисления композиции, который использует таблицу композиции базовых отношений размером 13 х 13 (см табл. 3.5). Композиция двух множеств отношений вычисляется с помощью вложенного цикла, который формирует объединение композиций пар базисных отношений, входящих в эти отношения. Этот метод является самым медленным из предложенных.
В [247] предложен метод вычисления композиции с использованием четырех таблиц вместо одной, размером 27 х 27 (биты 1-7 первого отношения и биты 1-7 второго отношения), 27 х 2б (биты 1-7 первого отношения и биты 8-13 второго отношения), 26 х 27 (биты 8-13 первого отношения и биты 1-7 второго отношения) и 26 х 26 (биты 8-13 первого отношения и биты 8-13 второго отношения). Что требует в сумме около 72Кб памяти. Композиция двух меток ребер вычисляется как объединение результатов из 4-х таблиц с использованием 3-х логических сдвигов и нескольких операций «И».
По аналогии с предыдущим методом предложен метод вычисления композиции с использованием двух таблиц, первая содержит композицию 7 младших битов отношения, а вторая 6 старших. В сумме такой подход требует около 3Мб памяти, а композиция вычисляется с помощью одного логического сдвига и одной операции «ИЛИ».
Применяются также различные методы для сокращения числа необходимых операций композиции. Один из таких методов — пропускать вычисление композиции, когда полученное в результате отношение заведомо не изменит (не ограничит) прежнее отношение, замыкающее треугольник. Это происходит в том случае, когда полученное в результате композиции отношение является универсальным Т. Основные случаи, когда это происходит показаны на рис. 3.4.
Другим методом ускорения алгоритма является метод упорядочивания ребер. Эффективность применения этого метода заключаются в следующем. Одно и то же ребро может появляться в списке обрабатывае мых ребер L много раз, постепенно уменьшая мощность отношения на нем. Количество появлений конкретного ребра в списке может быть сокращено за счет его предварительного упорядочивания. Например, рассмотрим ребра (3;1) и (3,5) на рис. 3.2 (напомним; что неотображенные ребра имеют универсальное отношение Т).
