На правах рукописи

Троицкий Виктор Валерьевич

МЕТОДЫ И ПРОГРАММНЫЕ СРЕДСТВА ПРЕДСТАВЛЕНИЯ

ВРЕМЕННЫХ ЗАВИСИМОСТЕЙ В ИНТЕЛЛЕКТУАЛЬНЫХ

СИСТЕМАХ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ

Специальность 05.13.11 – Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва 2004 г.

2

Работа выполнена на кафедре Прикладной математики Московского энергетического института (Технического университета)

Научный руководитель: лауреат премии Президента РФ в области образования доктор технических наук, профессор Александр Павлович Еремеев

Официальные оппоненты: доктор технических наук Игорь Борисович Фоминых кандидат физико-математических наук, профессор Геральд Станиславович Плесневич

Ведущая организация: Институт проблем управления РАН

Защита состоится «23» июня 2004 г. в 16 час. 00 мин. на заседании диссертационного совета Д 212.157.01 при Московском энергетическом институте (Техническом университете) по адресу: 111250, Москва, Красноказарменная ул., 17 (ауд. Г-306).

С диссертацией можно ознакомиться в библиотеке Московского энергетического института (Технического университета).

Отзывы в двух экземплярах, заверенные печатью, просьба направлять по адресу: 111250, г. Москва, ул. Красноказарменная, д.14, Ученый Совет МЭИ(ТУ).

Автореферат разослан «21» мая 2004 г.

Ученый секретарь диссертационного совета Д 212.157. кандидат технических наук, профессор И. И. Ладыгин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

О важности наличия средств представления времени и временных (темпоральных) зависимостей (в данных и знаниях) в интеллектуальных системах (ИС) говорится практически с момента появления таких систем (см., например, работы Д. А. Поспелова и Дж. Маккарти), однако особенно актуальна эта проблема встала именно в связи с появлением и развитием динамических ИС, типичными представителями которых являются интеллектуальные системы поддержки принятия решений реального времени (ИСППР РВ).

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

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

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

Способность представлять временные зависимости, а также временные ограничения на события, происходящие в технической или организационной системе, позволяет существенно сократить поисковые пространства в задачах диагностики, мониторинга, планирования и управления сложными процессами. Однако, в настоящее время отсутствуют развитые средства представления временных зависимостей в современных инструментальных средствах конструирования ИС, включая ИСППР РВ. Известные и дорогостоящие инструментальные комплексы типа G2, RTworks и др., а также языки искусственного интеллекта типа CLIPS имеют лишь примитивные средства отображения фактора времени.

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

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

Цель работы. Целью работы является исследование и разработка моделей, методов и программных средств представления и оперирования временными зависимостями, повышающих эффективность и расширяющих интеллектуальные возможности современных компьютерных систем типа ИСППР РВ.

Для достижения указанной цели необходимо решить следующие задачи:

– исследование методов и моделей представления временных зависимостей в ИС;

– разработка методики построения моделей с явным представлением времени, ориентированных на использование в ИСППР РВ;

– сравнительный анализ и классификация основных моделей представления временных зависимостей в плане их применимости в ИСППР РВ, выделение моделей с полиномиальными алгоритмами;

– разработка архитектуры системы представления временных зависимостей (СПВЗ), на основе которой реализуется временной вывод (временные рассуждения) в ИСППР РВ;

– разработка и программная реализация СПВЗ;

– использование разработанной СПВЗ для решения задачи прогнозирования в рамках прототипа ИСППР РВ для оперативно-диспетчерского персонала энергоблока и в других приложениях.

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

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

Научная новизна. Новыми являются:

1. Классификация моделей представления временных зависимостей.

2. Методика построения моделей времени для ИСППР РВ.

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

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

Практическая значимость работы подтверждается использованием разработанной СПВЗ в прототипе ИСППР РВ для оперативно-диспетчерского персонала энергоблока и в других приложениях, о чем имеются акты о внедрении.

Реализация результатов. Разработанная СПВЗ использована в ЦНИИКА в рамках блока прогнозирования в прототипе ИСППР РВ для оперативно-диспетчерского персонала энергоблока, в учебно-научном процессе кафедры Прикладной математики МЭИ(ТУ) и кафедры ТОЭ Таганрогского государственного радиотехнического университета (ТГРТУ).

Результаты работы использованы в НИР, выполненных в рамках грантов РФФИ, проекты №99-01-00049 и №02-07-90042 по тематике «Исследование и разработка инструментальных средств создания экспертных систем семиотического типа»; проект №02-07-90042 «AHO» «Модели и методы представления временной (темпоральной) информации в интеллектуальных системах», грантов РФФИ для аспирантов и студентов, проекты №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 страниц машинописного текста.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе проводится обзор наиболее используемых в настоящее время методов и моделей представления временных зависимостей в ИС и дается их сравнительных анализ. Выделяются задачи, характерные для ИСППР РВ и в которых необходимо использовать фактор времени. Эти задачи связаны с моделированием динамических — т.е. меняющих во времени свое состояние — систем и включают в себя задачу представления данных и знаний и задачу вывода на основе этой информации. К таким задачам относятся:

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

• Прогнозирование. Определение состояния ПО (объекта) в заданное время в будущем или, в более общей постановке, построение картины эволюции ПО (объекта) до определенного момента времени в будущем;

• Планирование. Нахождение последовательности воздействий на ПО (объект) с целью перевода её в заданное состояние;

• Обучение правилам изменения. Дается описание ПО (объекта) в различных состояниях и необходимо построить множество правил, обуславливающих изменения в причинно-следственных закономерностях ПО;

• Диагностика. Классификация текущего состояния ПО (объекта) на основе некоторых признаков и, возможно, предыстории. Может включать в себя также и задачу объяснения;

• Мониторинг. Непрерывная интерпретация состояния ПО (объекта) в реальном масштабе времени с сигнализацией ЛПР о возникновении аномальных ситуаций.

Проводится классификация современных подходов к моделированию фактора времени в ИИ и анализируются их достоинства и недостатки в плане использования в ИСППР РВ.

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

В классе подходов и методов, использующих моделирование изменений во времени, базовым примитивом являются сущности, — обычно это некоторые действия, преобразующие одно состояние системы в другое. Состояния системы рассматриваются как «мгновенные снимки мира», не обладающие какой либо длительностью во времени. К этому классу относятся неявные модели времени, используемые в системах, являющихся последователями известных систем GPS и STRIPS1, а также в системах, основанных на ситуационном исчислении. Данные модели и методы, наиболее используемые в ИС, имеют ряд существенных ограничений по представлению сложных временных структур типа: мгновенных действий; событий, имеющих длительность, а также конкурирующих и перекрывающихся во времени; действий и событий, обладающих сложными причинно-следственными взаимосвязями; продолжительных процессов; действий, образующих синергетические эффекты и т.д., что сильно ограничивает возможность их применения в ИСППР РВ.

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

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

General Problem Solver и STanford Research Intellectual Planning System Обосновывается целесообразность использования второго подкласса методов и моделей в ИСППР РВ. Однако отмечается, что при этом необходимо решение проблемы большой вычислительной сложности соответствующих алгоритмов вывода.

Выделяются следующие задачи оперирования временными зависимостями (отношениями и примитивами) — так называемые задачи временных рассуждений (временного вывода), представляющие собой:

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

• ответы на запросы, касающиеся временных аспектов информации (данных и знаний).

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

Обосновывается актуальность разработки СПВЗ, являющейся основой для временного вывода в ИСППР РВ.

Уточняются задачи диссертации в плане разработки СПВЗ для реализации временного вывода (временных рассуждений) в ИСППР РВ на примере задачи прогнозирования.

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

Во второй главе исследуются методы построения явных моделей времени в ИС и предлагается методика построения таких моделей в плане реализации на их основе СПВЗ. На рис. 1 представлена структурная схема модели времени. Анализируется каждый компонент модели. Описываются основные альтернативы при создании компонентов модели, анализируется влияние их свойств на свойства создаваемой модели времени как с точки зрения выразительности модели, так и с точки зрения вычислительной эффективности.

Онтология времени представляет собой определение множества примитивов времени и множества базовых временных отношений. В качестве примитивов, как правило, используются моменты (точки) и интервалы (периоды) времени. В качестве базовых отношений, например, можно взять три простых качественных отношения между двумя точками на прямой:. Если временные отношения включают числовую информацию, т.е. являются количественными (метрическими), то необходимо вводить дополнительный базовый примитив — длительность. Структура времени — это область интерпретации временных примитивов и её свойства (упорядоченность, ограниченность/неограниченность, дискретность/непрерывность и т.д.). Структура времени задается посредством множества аксиом, образующих теорию времени.

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

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

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

Примитивные временные отношения и их (логические) комбинации можно рассматривать в качестве ограничений. Например, «момент времени p находится перед моментом времени p » — это ограничение на множество возможных значений для относительного расстояния между p и p. Временные примитивы и допустимые ограничения определяют класс временных ограничений.

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

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

Предложена методика построения моделей явного представления времени с заданными свойствами:

1. Построить онтологию времени:

(a) Выбрать базовые примитивы времени;

(b) Задать базовые отношения между примитивами;

(c) Ввести необходимые элементарные функции преобразования примитивов и отношений;

(d) Задать свойства структуры времени с помощью аксиом, определяющих свойства базовых отношений;

(e) Сформулировать теорию времени, определяющую основные свойства времени в зависимости от ПО.

2. В соответствии с построенной онтологией времени выбрать модель (модели) представления временных зависимостей.

3. Выбрать используемый метод временной квалификации.

4. Построить теорию временных утверждений:

(a) Определить базовые временные утверждения;

(b) Задать их свойства с помощью множества аксиом.

5. Выбрать язык представления.

6. Выбрать (разработать) алгоритмы вывода.

Анализируются базовые решения по каждому пункту методики и даются соответствующие рекомендации.

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

Опр. 1 ЗСВО задается посредством:

1) конечного множества временных примитивов, X1,..., Xn,;

2) множеств D1,..., Dn, таких что для любого i = 1,..., n, Di есть область значений Xi, зависящая от структуры времени;

3) конечного числа ограничений Ci1...im на переменных (Xi1,..., Xim ), где Ограничения задаются на основе множества базовых временных отношений (BT R) между переменными. Ограничение вида Cij = rk, где rk BT R называется единичным. Все элементы множества BT R должны удовлетворять следующим условиям:

• отношения взаимно исключающие;

• объединение всех элементов является универсальным ограничением U (т.е. не накладывающим никаких ограничений).

Далее будем иметь в виду наиболее используемые бинарные ЗСВО с бинарными ограничениями вида Cij Di Dj.

Для представления неточных отношений между временными примитивами Xi и Xj используется дизъюнктивная форма ограничений вида Cij = {r1,..., rk }, k > 0, r1,..., rk BT R, которая интерпретируется как дизъюнкт (Xi r1 Xj )... (Xi rk Xj ).

Опр. 2 Единичная пометка ограничения Cij — это одно из базовых отношений r, такое что r Cij. Единичная пометка ЗСВО — это единичная пометка всех её ограничений. В частично единичной пометке ЗСВО часть ограничений являются дизъюнктивными.

Опр. 3 Решение ЗСВО — это согласованная единичная пометка. Согласованность каждой единичной пометки определяется в соответствии с семантикой соответствующего класса ЗСВО.

Опр. 4 Отношение r BT R выполнимо для переменных Xi и Xj тогда и только тогда, когда существует хотя бы одно решение, в котором r связано с этой парой переменных, т.е. является ограничением между этими переменными.

Опр. 5 Минимальное ограничение Cij — это ограничение, состоящее только из выполнимых отношений между Xi и Xj. Когда все ограничения минимальны, ЗСВО называется минимальной (минимальное представление).

Известно, что для любой ЗСВО всегда можно найти эквивалентную минимальную ЗСВО или показать несогласованность ограничений.

Процесс решения ЗСВО включает решение следующих её подзадач:

• определение согласованности множества ограничений, или задача выполнимости (задача ISAT);

• нахождение согласующего сценария;

• нахождение минимального представления, определение всех выполнимых отношений (задача ISI);

• определение выполнимых ограничений между заданной парой временных примитивов.

Опр. 6 Пусть S и T — ограничения. Основные операции над временными ограничениями определяются на основе операций над базовыми отношениями из BT R следующим образом:

• дополнение (¬) : ¬S = U \ S;

• пересечение () : S T — теоретико-множественное пересечение базовых отношений S и T ;

• объединение () : S T — теоретико-множественное объединение базовых отношений S и T ;

• композиция () : S T — объединение индивидуальных композиций всех базовых отношений в S со всеми базовыми отношениями в T, а именно:

В множество BT R входит отношение равенства, нейтральное по отношению к операции композиции. Отметим, что операции инверсии () и композиции () над базовыми отношениями из BT R определяются для каждого класса ЗСВО отдельно. Множество всех временных ограничений 2BT R замкнуто относительно этих операций и является алгеброй временных отношений.

В большинстве моделей ЗСВО в общем случае является NP-полной, поэтому особое внимание в работе уделяется выделению моделей, обладающих полиномиальными алгоритмами, для последующего использования их в СПВЗ для ИСППР РВ. Выявляются подходы к объединению этих моделей в рамках единой системы.

Детально анализируются (в плане выразительности и алгоритмической эффективности):

• качественные точечные ЗСВО, которые являются классическим представлением временных зависимостей в виде набора моментов времени, связанных качественными отношениями: и =. Данный класс ЗСВО является наиболее предпочтительным с точки зрения сложности алгоритмов;

• качественные интервальные ЗСВО, основанные на понятии отношения между парой интервалов, и которым соответствует интервальная алгебра • ЗСВО на основе точечно-интервальной алгебры, базирующейся на понятиях точек, интервалов и бинарных отношений между ними и интегрирующей выразительные возможности точечной и интервальной алгебр;

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

• ЗСВО, использующие в качестве временных примитивов длительности промежутков времени и позволяющие задавать ограничения на этих длительностях, что характерно при решении задач диагностики, мониторинга и управления сложными объектами и процессами в реальном времени;

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

Проводится сравнительный анализ и предлагается классификация рассмотренных моделей представления временных зависимостей, на основе которой выделяются модели для использования в СПВЗ для ИСППР РВ.

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

Рис. 2. Иерархия моделей представления временных зависимостей.

В левой части рис. 2 показаны качественные модели, в правой части — модели с метрическими ограничениями. STP означает полиномиальный подкласс метрических точечных моделей, TCSP-LPC — метрические точечные модели с использованием алгоритма LPC в качестве приближенного алгоритма распространения ограничений, TCSP — произвольные метрические точечные модели. Точечно-интервальная алгебра — это интегрированная модель, допускающая качественные ограничения на интервалах и моментах времени (т.е.

любые комбинации отношений между моментами и интервалами времени).

Анализируются алгоритмы решения ЗСВО в моделях, предназначенных для использования в СПВЗ для ИСППР РВ. Предлагается обобщенный алгоритм решения ЗСВО, основанный на использовании множества полиномиальных подклассов (SubClasses) для проверки принадлежности ЗСВО одному из них, после чего полученная информация используется для выбора из множества реализованных алгоритмов (AlgSet) наиболее подходящего алгоритма решения ЗСВО. Соответствие между подклассами и алгоритмами решения задачи ISAT задается в виде двудольного графа BiGraph(SubClasses, AlgSet, E) на множествах вершин SubClasses, AlgSet и множестве ребер E, E SubClasses AlgSet, причем ребро ek = (Pi, Aj ) E тогда и только тогда, когда алгоритм Aj решает задачу ISAT в полиномиальном подклассе Pi.

Описание алгоритма:

Алгоритм 1 Обобщенный алгоритм решения задачи ISAT Procedure ImprovedConsistency({Cij }, n), где {Cij } — ЗСВО в виде сети ограничений, n число переменных (интервалов).

2: if существует такой полиномиальный подкласс Pk SubClasses, что L Pk then выбрать алгоритм с наименьшей сложностью Algm AlgSet, такой что (Pk, Algm ) BiGraph, где BiGraph SubClasses AlgSet 5: else выбрать полиномиальный подкласс Pl P SC, такой что l = i, на котором достигается выбрать алгоритм с наименьшей сложностью Algp AlgSet такой что (Pl, Algp ) BackT racking({Cij }, Pl ) с использованием алгоритма Algp в качестве препроцессинга 9: end if Основным преимуществом предложенного алгоритма по сравнению с известными является сокращение среднего времени поиска решения, что подтверждено результатами компьютерного моделирования.

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

Основными принципами являются: принцип множественности моделей, направленный на использование в СПВЗ совокупности моделей представления временных зависимостей различных классов; принцип многоуровневости представления, направленный на реализацию нескольких уровней моделей представления временных зависимостей с различной степенью выразительности, что обеспечивает возможность смены моделей в процессе работы СПВЗ;

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

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

Основные функции СПВЗ следующие:

• выбор используемой модели представления временных зависимостей и её настройка (выбор представления и алгоритмов);

• добавление и удаление временных примитивов в выбранную модель;

• обновление, добавление, удаление временных ограничений между заданными временными примитивами;

• определение согласованности ограничений на множестве временных примитивов;

• ответы на различные запросы о временных ограничениях и примитивах, среди которых выделяют:

– в случае несогласованности найти невыполнимые ограничения между временными примитивами;

– найти минимальное выполнимое ограничение между указанными временными примитивами;

– найти временные примитивы, удовлетворяющие заданным ограничениям;

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

Рис. 3. Архитектура СПВЗ как многоуровневой системы.

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

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

На основе предложенной архитектуры выполнена программная реализация СПВЗ.

Описаны методы получения тестовых примеров для экспериментального сравнения алгоритмов решения ЗСВО в разработанной СПВЗ.

Рис. 4. Реализация модели представления временных зависимостей.

Приведены результаты тестирования СПВЗ и результаты проведенных экспериментов по сравнению алгоритмов поиска решения в СПВЗ на примере качественной интервальной ЗСВО (рис. 5).

Рис. 5. Экспериментальное сравнение алгоритмов по среднему времени работы.

Анализ полученных результатов подтвердил эффективность предложенного алгоритма.

В пятой главе рассматривается использование СПВЗ для решения задачи прогнозирования состояния технического объекта на примере насоснотеплообменной установки системы управления и защиты ядерного реактора РБМК-1500 для прототипа ИСППР РВ.

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

Онтология времени Примитивы: моменты, интервалы, длительности с константами времени Теория времени Линейность, неограниченность, Временные ограничения Комбинированные точечно-интервальные ограничения Временная квалификация Временное овеществление Теория временных Предикаты: Holds_on, Holds_at, Occurs утверждений Аксиомы: гомогенность Holds_on Язык представления Многосортный продукционный язык Разработанная модель позволяет отображать экспертные правила, формализующие причинно-следственные зависимости между элементами технического объекта, с явным учетом временных зависимостей между событиями и свойствами.

Рассмотрим примеры правил, используемых в блоке прогнозирования:

p P ump i, j, k Interval t T ime (Holds_on(state(p, of f ), i) & (1) Holds_on(f lowrate(T K30F 01, normal), j) & i{during, overlaps, starts}j Holds_on(f lowrate(T K30F 01, low), k) & (start(k) start(i)) [3, 5 ] & meets(j, k)) (Выключение любого насоса (p) приводит к снижению расхода воды на расходомере (T K30F 01) в диапазоне от 3 до 5 секунд.) i j, k Interval (Holds_on(f lowrate(T K30F 01, low), i) & (2) Holds_on(level(T K40, normal), j) & overlaps(j, i) Holds_on(level(T K40, low), k) & meets(j, k) & (start(k) start(i)) [1, 2 ]) (Падение расхода воды на расходомере (T K30F 01) приводит к снижению уровня в расходном баке (T K40) в диапазоне от 1 до 2-х минут.) (Снижение уровня в расходном баке приводит к срабатыванию аварийной защиты (AZ1) в диапазоне от 5 до 15 секунд.) На основе этих правил можно сделать прогноз о том, что в ситуации выключения насоса T K22D01 в момент времени t1 аварийная защита (AZ1) включится между моментами времени t1 + 68 и t1 + 140 (рис. 6).

t2 flowrate(TK30F01,low) t1 state(TK22D01,off) Рис. 6. Построение прогноза с использованием СПВЗ.

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

Показана эффективность применения СПВЗ для решения задач прогнозирования в рамках прототипа ИСППР РВ на основе нетрадиционных логик, разрабатываемого на кафедре ПМ МЭИ(ТУ) для мониторинга и управления сложными объектами типа энергоблоков.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Проведено исследование способов построения моделей времени в ИИ и установлено, что для построения моделей времени, удовлетворяющих требованиям к современным ИСППР РВ, необходимо использовать подход на основе явного представления времени (временных зависимостей).

2. Разработана методика построения модели явного представления времени, позволяющая получать модели с заданными свойствами. Эффективность методики показана на примере разработки модели для подсистемы прогнозирования в рамках прототипа ИСППР РВ.

3. Предложена классификация основных алгебраических моделей представления временных зависимостей на основе ЗСВО по выразительным возможностям, позволяющая выбирать модель с заданными свойствами для СПВЗ. Выделены модели с наличием полиномиальных подклассов для использования в СПВЗ для ИСППР РВ.

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

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

6. Выполнена реализация программных средств представления временных зависимостей в виде СПВЗ для ИСППР РВ.

7. Разработанные методы и программные средства применены для решения задачи прогнозирования в рамках прототипа ИСППР РВ для одной из подсистем энергоблока РБМК-1500 и в других приложениях, о чем имеются акты о внедрении.

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Еремеев А. П., Троицкий В. В. Основные способы формализации временных зависимостей при построении интеллектуальных систем // Тр.

седьмой нац. конф. по искусственному интеллекту с междунар. участием, КИИ’2000. В 2 т. — Т. 2. — М.: ФизМатЛит, 2000. — С. 652–662.

2. Еремеев А. П., Троицкий В. В. Представление временных и причинноследственных зависимостей в системах поддержки принятия решений реального времени семиотического типа // Перспективные информационные технологии и интеллектуальные системы. — 2000. — № 3. — С. 25–31.

3. Еремеев А. П., Троицкий В. В. Представление временных ограничений в интеллектуальных системах: Обзор // Тр. междунар. конгресса «Искусственный интеллект в XXI веке». — М.: ФизМатЛит, 2001. — С. 61–74.

4. Еремеев А. П., Троицкий В. В. Методы представления временных зависимостей в интеллектуальных системах поддержки принятия решений // Междунар. журнал компьютерных систем. Перевод журнала «Известия РАН. Теория и системы управления». — 2003. — Т. 42, № 5. — С. 732– 743. — (на англ. яз.).

5. Еремеев А. П., Троицкий В. В. Методы представления временных зависимостей в интеллектуальных системах поддержки принятия решений // Известия РАН. Теория и системы управления. — 2003. — № 5. — С. 75–88.

6. Еремеев А. П., Троицкий В. В. Темпоральные рассуждения в интеллектуальных системах поддержки принятия решений // Тр. междунар. научнотехнических конф. «Интеллектуальные системы» и «Интеллектуальные САПР». В 3-х т. — Т. 2. — М.: ФизМатЛит, 2003. — С. 403–411.

7. Троицкий В. В. О представлении причинно-следственных (каузальных) отношений в интеллектуальных системах // Сб. тр. третьей междунар.

летней школы-семинара по искусственному интеллекту для студентов и аспирантов (Браславская школа). — Минск: БГУИР, 1999. — С. 186–190.

8. Троицкий В. В. Алгоритмы вывода во временных логиках // Сб. тр. Научной сессии МИФИ-2000. В 13 т. — Т. 3. — М.: МИФИ, 2000. — С. 173–174.

9. Троицкий В. В. Временная логика Аллена — алгоритмы вывода // Сб. тр.

четвертой междунар. летней школы-семинара по искусственному интеллекту для студентов и аспирантов (Браславская школа). — Минск: БГУ, 2000. — С. 92–96.

10. Троицкий В. В. Временные логики — алгоритмы вывода // Радиоэлектроника, электротехника и энергетика: Тез. докл. шестой междунар. научнотехн. конф. студентов и аспирантов. В 3-х т. — Т. 1. — М.: МЭИ, 2000. — С. 245–246.

11. Троицкий В. В. Алгоритмы вывода во временной интервальной логике // Сб. тр. Научной сессии МИФИ-2001. В 14 т. — Т. 3. — М.: МИФИ, 2001. — С. 206–207.

12. Троицкий В. В. Временные рассуждения, как задача согласования ограничений // Радиоэлектроника, электротехника и энергетика: Тез. докл. седьмой междунар. научно-техн. конф. студентов и аспирантов. В 3-х т. — Т. 1. — М.: Изд. МЭИ, 2001. — С. 275–276.

13. Троицкий В. В. Система темпоральных рассуждений // Междунар. форум информатизации–2001: Докл. междунар. конф. «Информационные средства и технологии». В 3-х т. — Т. 3. — М.: Станкин, 2001. — С. 14–17.

14. Троицкий В. В. Архитектура системы темпоральных рассуждений // Сб.

тр. Научной сессии МИФИ-2002. В 14 т. — Т. 3. — М.: МИФИ, 2002. — С. 153–154.

15. Троицкий В. В. Модели времени в задачах планирования // Радиоэлектроника, электротехника и энергетика: Тез. докл. восьмой междунар. научнотехн. конф. студентов и аспирантов. В 3-х т. — Т. 1. — М.: Изд. МЭИ, 2002. — С. 291–292.

16. Троицкий В. В. Принципы построения системы темпоральных рассуждений // Тр. восьмой нац. конф. по искусственному интеллекту с междунар.

участием, КИИ’2002. В 2 т. — Т. 2. — М.: ФизМатЛит, 2002. — С. 656–664.

17. Троицкий В. В. Области применения системы темпоральных рассуждений // Междунар. форум информатизации–2003: Докл. междунар. конф.

«Информационные средства и технологии». В 3-х т. — Т. 3. — М.: Станкин, 2003. — С. 14–17.

18. Троицкий В. В. Система темпоральных рассуждений и ее приложения // Сб. тр. Научной сессии МИФИ-2003. В 14 т. — Т. 3. — М.: МИФИ, 2003. — С. 107–108.

19. Троицкий В. В. Иерархические модели времени в системе темпоральных рассуждений // Сб. тр. Научной сессии МИФИ-2004. В 14 т. — Т. 3. — М.:

МИФИ, 2004. — С. 124–125.

Полиграфический центр МЭИ (ТУ) Красноказарменная ул., д.