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

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

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

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

кандидата технических наук: Троицкий, Виктор Валерьевич
город: Москва
год: 2004
специальность ВАК РФ: 05.13.11

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

Автореферат диссертации по теме "Методы и программные средства представления временных зависимостей в интеллектуальных системах поддержки принятия решений"

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

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

МЕТОДЫ И ПРОГРАММНЫЕ СРЕДСТВА ПРЕДСТАВЛЕНИЯ ВРЕМЕННЫХ ЗАВИСИМОСТЕЙ В ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМАХ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

Москва 2004 г.

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

Научный руководитель:

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

Официальные оппоненты: доктор технических наук

Игорь Борисович Фоминых

кандидат физико-математических наук, профессор

Геральд Станиславович Плесневич

Ведущая организация:

Институт проблем управления РАН

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

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

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

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

Ученый секретарь

диссертационного совета Д 212.157.01 кандидат технических наук,

профессор

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

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

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

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

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

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

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

Способность представлять временные зависимости, а также временные

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3. Архитектура системы представления временных зависимостей для ИСППР РВ.

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

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

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

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

Результаты работы использованы в НИР, выполненных в рамках грантов РФФИ, проекты №99-01-00049 и №02-07-90042 по тематике «Исследование и разработка инструментальных средств создания экспертных систем семиотического типа»; проект №02-07-90042 «АНО» «Модели и методы представления временной (темпоральной) информации в интеллектуальных системах», грантов РФФИ для аспирантов и студентов, проекты №01-01-06356 «MAC» и №03-07-06034 «MAC» и в рамках Федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 годы по теме «Системы мониторинга и поддержки принятия решений на основе аппарата нетрадиционных логик».

МЭИ(ТУ), (г. Москва, 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 представлена структурная схема модели времени. Анализируется каждый компонент модели. Описываются основные альтернативы при создании компонентов модели, анализируется влияние их свойств на свойства создаваемой модели времени как с точки зрения выразительности модели, так и с точки зрения вычислительной эффективности.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1) конечного множества временных примитивов, .Х^,... ,Хп,!

2) множеств 01,...,0п, таких что для л ю Щ т ь область значений Х{, зависящая от структуры времени;

3) конечного числа ограничений С,,...гт на переменных ,..., Х^), где

Ограничения задаются на основе множества базовых временных отношений (ВТК) между переменными. Ограничение вида С,,- = Г*, ГДе Г* £ ВТИ называется единичным. Все элементы множества ВТЯ должны удовлетворять следующим условиям:

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

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

Далее будем Ихмегь в виду наиболее используемые бинарные ЗСВО с бинарными ограничениями вида С^ С х

Для представления неточных отношений между временными примитивами И X} используется дизъюнктивная форма ограничений вида С^ = {)"1,..., Г к}, к > 0, Г1,...,Гк € ВТ Л, которая интерпретируется как дизъюнкт (Х{ п X]) V ... V (Х{ гк Х}).

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

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

Опр. 4 Отношение выполнимо для переменных тогда и

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

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

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

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

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

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

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

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

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

• дополнение(-1) : -15 =и\Б;

• инверсия{~) : ~ 5 =~ {вь..., в*} = 51,..., ~ й*};

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм 1 Обобщенный алгоритм решения задачи ISAT Procedure ImprovedConststency({C,3},n),

где {С.^} — ЗСВО в виде сети ограничений, и число переменных (интервалов). 1- L-{Cv|0<»,j<n}

2: ¡Гсуществуеттакойполиномиальныйподкласс Pi 6 Subclasses, что £ С Я* then

3. выбрать алгоритм с наименьшей сложностью Algm € AlgSet, такой что (Ру,Л1дт) € BiGraph, гае BiGraph С Subclasses х AlgSet

4. А1дт({С,3},п)

5. else

6: выбрать полиномиальный подкласс Pj € PSC, такой ч i =е i, на котором достигается шах,(|Р, Л L\)

7. выбрать алгоритм с наименьшей сложностью Alg? е AlgSet такой что (Pi,Alg?) € BtGraph

8: ВаскТтасктд({С,,},Pi) с использованием алгоритма Algp в качестве препроцессинга

9: end if_

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

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

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

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

Основные функции СПВЗ следующие: " • выбор используемой модели представления временных зависимостей и её настройка (выбор представления и алгоритмов);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 1.

Основные характеристики модели времени.

Онтология времени Примитивы: моменты, интервалы, длительности с константами времени Отношения: точечные и интервальные качественные и количественные

Теория времени Линейность, неограниченность, дискретность, аксиомы связи интервалов с моментами

Временные ограничения Комбинированные точечно-интервальные ограничения

Временная квалификация Временное овеществление

Теория временных утверждений Предикаты: Holdsjm, Holdsjxt, Occurs Аксиомы: гомогенность Holds on

Язык представления Многосортный продукционный язык

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

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

Vp € Pump 3i,j,k е Interval 31 e Time (Holds_on(state(p,off),i) к (1) Holds_on( fl&wrate(TK30F0l,normal), j) к {{during, overlaps, starts}j

(Выключение любого насоса (р) приводит к снижению расхода воды на расходомере (TK30F01) в диапазоне от 3 до 5 секунд.)

Vi 3j, к £ Interval (Holds_on(flowrate{TK30F0l,low),i) к (2)

Holds_on(level(TK4Q,normal), j) к overlaps(j,i) Holds_on(level(TK40, low), к) к meets(j, к) к (start(k) - start(i)) £ [l',2'])

(Падение расхода воды на расходомере (TK30F01) приводит к снижению уровня в расходном баке (ТК40) в диапазоне от 1 до 2-х минут.)

Vi € Interval 3t 6 Time {Holds_on[level{TK40, low), i) (3)

Occur s{AZl,t) k(t- begin(i)) G [5", 15"])

(Снижение уровня в расходном баке приводит к срабатыванию аварийной защиты (AZi) в диапазоне от 5 до 15 секунд.)

На основе этих правил можно сделать прогноз о том, что в ситуации выключения насоса TK22D01 в момент времен^аварийная защита (AZ1) включится между моментами времени ii + 68" и ti + 140" (рис. 6).

Применение правил

СПВЗ

о Оссиге(Аг1)

С. [60-,120"] Г,

[3' 5')

« Г.

Гг^Яо^га^КЗОРОио^

Время

Рис. б. Построение прогноза с использованием СПВЗ.

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

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

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

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

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

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

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

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

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

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

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

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

1. Еремеев А. П., Троицкий В. В. Основные способы формализации временных зависимостей при построении интеллектуальных систем // Тр. седьмой нац. конф. по искусственному интеллекту с междунар. участием, КИИ'2000. В 2 т. - Т. 2. - М.: ФизМатЛит, 2000. - С. 652-662.

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

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

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

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

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

7. Троицкий В. В. О представлении причинно-следственных (каузальных) отношений в интеллектуальных системах // Сб. тр. третьей междунар. летней школы-семинара по искусственному интеллекту для студентов и аспирантов (Браславская школа). — Минск: БГУИР, 1999.— С. 186-190.

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

Я06 0 &

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.

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

Оглавление автор диссертации — кандидата технических наук Троицкий, Виктор Валерьевич

ОГЛАВЛЕНИЕ.

СПИСОК ОСНОВНЫХ СОКРАЩЕНИЙ.

ВВЕДЕНИЕ.

ГЛАВА 1. Моделирование времени в искусственном интеллекте.

1.1. Значение и основные свойства времени.

1.2. Моделирование времени в ИИ и компьютерных науках.

1.2.1. Фактор времени в ИИ.

1.2.2. Области приложения и направления исследований.

1.2.3. Основные задачи, использующие фактор времени.

1.2.4. Основные подходы к представлению времени в ИИ.

1.2.5. Задачи, связанные с введением фактора времени.

1.2.6. Направления исследований.

1.3. Сравнительный анализ систем

1.4. Фактор времени в ИСППР — уточнение задач исследования

1.4.1. Время в современных инструментальных средствах разработки ЭС

1.4.2. ИСППР РВ семиотического типа

1.4.3. Особенности ИСППР РВ для помощи ЛПР при управлении сложными техническими объектами.

1.4.4. Требования к разработке моделей времени в ИСППР РВ.

1.5. Выводы по главе 1.

ГЛАВА 2. Методика построения моделей времени.

2.1. Требования к разработке моделей времени

2.2. Структура модели времени.

2.3. Онтология времени

2.4. Теории времени.57.

2.4.1. Алгебраическое представление структуры времени.

2.4.2. Сравнительный анализ теорий времени.

2.5. Методы временной квалификации.

2.5.1. Метод временных аргументов.

2.5.2. Модальная временная логика.

2.5.3. Метод овеществления утверждений

2.5.4. Расширения метода овеществления.

2.6. Теория временных утверждений

2.7. Языки представления и механизмы вывода.

2.8. Сравнение моделей времени.

2.9. Методика построения моделей явного представления времени

2.10. Выводы по главе

ГЛАВА 3. Алгебраические методы представления временных зависимостей.

3.1. Задача согласования временных ограничений

3.1.1. Основные определения и задачи.

3.1.2. Методы решения ЗСВО

3.2. Модели на основе качественной точечной ЗСВО.

3.3. Качественные интервальные ЗСВО: алгебра Аллена.

3.3.1. Определения.

3.3.2. Полиномиальные подклассы.

3.3.3. Алгоритмы решения ЗСВО.

3.4. Обобщенный алгоритм решения ЗСВО.

3.5. Качественные точечно-интервальные ЗСВО.

3.6. Метрические точечные ЗСВО.

3.7. Комбинированные качественные и метрические ЗСВО.

3.8. Комбинированные ЗСВО с длительностями.

3.9. Сравнительный анализ моделей.137.

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

3.11. Выводы по главе 3.

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

4.1. Основные требования и функции СПВЗ.

4.2. Принципы построения СПВЗ.

4.3. Архитектура СПВЗ

4.4. Программная реализация СПВЗ.

4.5. Экспериментальное исследование алгоритмов.

4.5.1. Методы получения тестовых данных.

4.5.2. Методы проведения экспериментов и анализа результатов.

4.5.3. Результаты экспериментов.

4.6. Выводы по главе

ГЛАВА 5. Пример применения системы представления временных зависимостей в интеллектуальной системе поддержки принятия решений реального времени.

5.1. Описание объекта.

5.2. Прототип ИСППР РВ.

5.2.1. Схема функционирования.

5.2.2. Прогнозирование с временными зависимостями

5.3. Описание разработанной модели времени.

5.3.1. Онтология времени

5.3.2. Методы представления временных зависимостей

5.3.3. Метод временной квалификации.

5.3.4. Теория временных утверждений.

5.3.5. Язык представления и алгоритмы вывода.

5.4. Модель прогнозирования состояния НТУ СУЗ.

5.4.1. Описание параметров НТУ СУЗ.184.

5.4.2. Диагнозы на входе блока прогнозирования

5.4.3. Правила прогнозирования состояния элементов НТУ СУЗ.

5.5. Пример прогнозирования последствий аномальных ситуаций.

5.6. Выводы по гпаве 5.

Введение 2004 год, диссертация по информатике, вычислительной технике и управлению, Троицкий, Виктор Валерьевич

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

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

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

Актуальность темы исследования.

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

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

О важности наличия средств представления времени и временных (тем-, поральных) зависимостей (в данных и знаниях) в ИС говорится практически с момента появления таких систем (см., например, работы [2-5]), однако особенно актуальна эта проблема встала именно в связи с появлением и развитием динамических ИС, типичными представителями которых являются интеллектуальные системы поддержки принятия решений реального времени (ИСППР РВ) [1,6-8].

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

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

Выполненные исследования опираются на результаты работ в области ИИ и конструирования ИС Д. А. Поспелова, Э. В. Попова, О. Й. Ларичева, А. А. Башлыкова, В. Н. Вагина, В. В. Емельянова, А. П. Еремеева, О. П. Кузнецова, В. М. Курейчика, А. С. Нариньяни, Г. С. Осипова, Г. С. Плесневича, В; А. Смирнова, И. Б. Фоминых и др., а также зарубежных ученых J. Allen, R. Dechter, J; McCarthy, F. Barber, P. van Beek, В: 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. Архитектура системы представления временных зависимостей для-ИСППР РВ.

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

Результаты работы использованы в НИР, выполненных в.рамках грантов РФФИ, проекты №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 г.г.), на Международной научно-технической конференций «Интеллектуальные системы» АПЗ'ОЗ (Россия, п. Дивноморское, 2003 г.).

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

Заключение диссертация на тему "Методы и программные средства представления временных зависимостей в интеллектуальных системах поддержки принятия решений"

Основные результаты диссертационной работы:

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

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

Перечислим основные направления дальнейших исследований:

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

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

ЗАКЛЮЧЕНИЕ

Библиография Троицкий, Виктор Валерьевич, диссертация по теме Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

1. Башлыков А. А., Еремеев А. П. Экспертные системы поддержки принятия решений в энергетике / Под ред. А. Ф. Дьякова,— М.: Издательство МЭИ, 1994.-216 с.

2. Попов Э. В., Фридман Г. Р. Алгоритмические основы интеллектуальных роботов и искусственного интеллекта. — М.: Наука. Гл. ред. физ.-мат. лит., 1976.

3. Поспелов Д. А. Логико лингвистические модели в системах управления и искусственного интеллекта. — М.: Наука. Гл. ред. физ.-мат. лит., 1981.

4. Поспелов Д. ^. Ситуационное управление: теория и практика. — М.: Наука. Гл. ред. физ.-мат. лит., 1986.

5. McCarthy J., Hayes P. J. Some philosophical problems from the standpoint of artificial intelligence // Machine Intelligence 4 / Ed. by B. Meitzer, D. Michie.— Edinburgh University Press, 1969.— Pp. 463-502.— reprinted in McC90.

6. Вагин В. H., Еремеев А. П. Некоторые базовые принципы построения интеллектуальных систем поддержки принятия решений реального времени // Известия РАН. Теория и системы управления.—2001.— № 6.— С. 114-123.

7. Статические и динамические экспертные системы: Учеб. пособие / Э. В. Попов, И. Б. Фоминых, Е. Б. Кисель, М. Д. Шапот. — М.: Финансы и статистика, 1996.— 320 с.

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

9. Люгер Д. Ф. Искусственный интеллект: стратегии и методы решения сложных проблем, Пер. с англ. — 4-е изд. — М.: Издательский дом "Вильяме", 2003. 864 с.

10. Джексон П. Введение в экспертные системы.: Пер. с англ.: Уч. пос. — М.: Издательский дом "Вильяме", 2001.— 624 с.

11. Кандрашина Е. Ю., Литвинцева Л. В., Поспелов Д. А. Представление знаний о времени и пространстве в интеллектуальных системах / Под ред. Д. А. Поспелова. Пробл. искусств, интеллекта.— М.: Наука. Гл. ред. физ.-мат. лит, 1989.— 328 с.

12. Грюнбаум А. Философские проблемы пространства и времени. — М.: Прогресс, 1969. 590 с.

13. Рейхенбах Г. Философия пространства и времени: Пер. с англ. / Под ред. О. ред. А.А.Логунова; Послесл. А.А.Ло1унова и И.А.Акчурина.— М.: Прогресс, 1985. — 344 с.

14. Уитроу Д. Естественная философия времени. — М.: Прогресс, 1964. — 431 с.

15. Sweeney L. That's AI? A history and critique of the field: Tech. Rep. CMU-CS-03-106. — Pittsburgh, Pennsylvania, USA: Carnegie Mellon University, School of Computer Science, 2003.

16. Allen J. F. AI growing up: The changes and opportunities // AI Magazine. — 1998.- Vol. 19, no. 4.- Pp. 13-23.

17. Shoham Y. Reasoning about Change: Time and Causation from the Standpoint of Artificial Intelligence. — Boston, MA: MIT Press, 1988.

18. Логический подход к искусственному интеллекту: От классичекой логики к логическому программированию. Пер. с франц. / А. Тейз, П. Гри-бомон, Ж. И. Луи и др. — М.: Мир, 1990. — 432 с.

19. Тейз А., Грибомон П., Юлен Г. Логический подход к искусственному интеллекту: От модальной логики к логике баз данных. Пер. с франц.— М.: Мир, 1998.-494 с.

20. Попов Э. В. Общение с ЭВМ на естественном языке,— М.: Наука, 1982.-360 с.

21. Vila L. A survey on temporal reasoning in artificial intelligence // Al Communications.— 1994.— Vol. 7, no. 1.— Pp. 4-28. citeseer.nj.nec.com/vila94survey.html.

22. Зинненко JI. А., Курейчик В. M. Применение интервальной алгебры в динамических алгоритмах эволюционного моделирования с накоплением знаний // Тр. междунар. конгресса «Искуственный интеллект в XXI веке». — М.: Изд-во физ.-мат. лит., 2001,— С. 606-621.

23. Fisher М. A survey of concurrent METATEM the language and its applications // Proceedings of First International Conference on Temporal Logic (ICTL). Bonn, Germany.— Vol. 827 of Lecture Notes in Computer Science. — Springer-Verlag, 1994.

24. Ladkin P. B. Using the temporal logic of actions: A tutorial on TLA verification. — 1997.

25. METATEM: a framework for programming in temporal logic: Tech. Rep. UMCS-89-10-4 / H. Barringer, M. Fisher, G. Gabbay et al.: Dept. CS, University of Manchester, 1989.

26. Koubarakis M. Foundations of Temporal Constraint Databases: Ph.D. thesis. — 1993. citeseer.nj.nec.com/151421.html.

27. Koubarakis M. Reasoning about time and change: A knowledge base management perspective, citeseer.nj.nec.com/koubarakis90reasoning.html.

28. Logical design for temporal databases with multiple granularities / X. S. Wang, C. Bettini, A. Brodsky, S. Jajodia // ACM Transactions on Database Systems. — 1997. Vol. 22, no. 2. — Pp. 115-170.

29. Гаврилов С., Малышков А., Плесневич Г. Бинарная модель данных и знаний // КИИ'2002, Труды конференции в 2 т.— Т. 1.— М.: Физ.-мат. лит., 2002.-С. 398-405.

30. Mackworth А. К. Consistency in networks of relations // Artificial Intelligence.- 1977.- Vol. 8.- Pp. 99-118.

31. Mackworth A., Freuder E. C. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems // Artificial Intelligence. 1985: — Vol. 25, no. 1. — Pp. 65-74.

32. Нариньяни А. С. Недоопределенность в системе представления и обработки знаний // Изв. АН СССР, Техническая кибернетика.— 1986. — №5.-С. 3-28.

33. Недоопределенное календарное планирование: новые возможности / А. С. Нариньяни, Д. А. Иванов, С. В. Седреев, С. А. Фролов // Информационные технологии. — 1997. — № 1.

34. Программирование в ограничениях и недоопределенные модели / А. С. Нариньяни, В. В. Телерман, Д. И. Ушаков, И. Е. Швецов // Информационные технологии. — 1998. — № 7.

35. Eaton P. S., Freuder E. C., Wallace R. J. Constraints and agents. Conforming ignorance I IAI Magazine. — 1998. — Summer. — Vol. 19, no. 2. — Pp. 51-65. .

36. Hog solver — constraint-based optimization engine. http://www.ilog.com/products/solver/.

37. Chip v5, the second-generation constraint programming tool. http://www.cosytec.com/productionscheduling/chip/optimizationproductchip.htm.

38. Трахтенгерц Э. А. Компьютерная поддержка принятия решений. Серия «Информатизация России на пороге XXI века». — М.: СИНТЕГ, 1998. — 376 с.

39. Ларичев О. И., Мошкович Е. М. Качественные методы принятия решений.—М.: Наука, 1996.

40. Ларичев О. И. Теория и методы принятия решений, а также хроника событий в волшебных странах. — М.: Логос, 2000.

41. Ларичев О. И. Новое направление в теории принятия решений: вербальный анализ решений // Новости искусственного интеллекта. — 2001. — №1.-С. 26-31.

42. Shahar Y. Timing is everything: Temporal reasoning and temporal data maintenance in medicine // Lecture Notes in Computer Science. — 1999. — Vol. 1620.— Pp. 30-47. citeseer.ist.psu.edu/shahar99timing.html.

43. Shahar Y. Dynamic temporal interpretation contexts for temporal abstraction // Annals of Mathematics and Artificial Intelligence. — 1998. — Vol. 22, no. 1-2.- Pp. 159-192. citeseer.ist.psu.edu/526047.html.

44. A problem-solving architecture for managing temporal data and their abstractions / Y. Shahar, S. Tu, A. Das, Mi Musen // Proc. AAAI-92 Workshop on Implementing Temporal Reasoning.— 1992. citeseer.ist.psu.edu/article/shahar92problemsolving.html.

45. Shahar Y. A framework for knowledge-based temporal abstraction I I Artificial Intelligence.- 1997.- Vol. 90, no. 1-2.- Pp. 79-133. citeseer.ist.psu.edu/shahar97framework.html.

46. ShaharY., Combi С. Timing is everything: Timeoriented clinical information systems // Western Journal of Medicine. — 1997. — Vol. 168. — Pp. 105-113. . citeseer.ist.psu.edu/shahar98timing.html.

47. Temporal reasoning in REAKT: An environment for real-time knowledge-based systems / F. Barber, V. Botti, E. Onaindia, A. Crespo // AI Communications1994. —Vol 7, no. 3. —Pp. 175-202.

48. Башлыков А: А:, Еремеев А. П. Экспертная диагностическая система как компонент интеллектуальной системы поддержки принятия решений реального времени // Новости Искусственного Интеллекта, — 2002.— № 3.-С. 35-40.

49. Гаврилова Т. А., Хорошевский В. Ф. Базы знаний интеллектуальных систем. — СПб.: Питер, 2000. — 384 с.

50. Плесневич Г., Цешинский А. Компиляция знаний для бинарной модели данных // КИИ'2000, Труды конференции в 2 т. — Т. 1.— М.: Физ.-мат. лит., 2000. С. 222-230.

51. Попов Э. В. Корпоративные системы управления знаниями // Новости Искусственного Интеллекта. — 2001. — № 1. — С. 14-25.

52. The DARPA agent markup language homepage, http://www.daml.org/.

53. TimeML: Markup language for temporal and event expressions. http://www.cs.brandeis.edu/jamesp/arda/time/.64: Staab S., Maedche A. Knowledge portals: Ontologies at work // AI Magazine. — 2001. — Vol. 22, no. 2. — Pp. 63-75.

54. Ankolenkar A., Burstein M., Hobbs J. R. et al. DAML-S: Web service description for the semantic web.— Presented at The First International Semantic Web Conference (ISWC).- 2002. http://www.cs.cmu.edu/ terryp/Pubs/ISWC2002-DAMLS.pdf.

55. Kotenko I., Stankevich L. The control of teams of autonomus objects in the time-constrained environments // Proc. IEEE International Conf. on Artificial1.telligence Systems (ICAIS 2002) 5-10 Sept. 2002, Divnomorskoe, Russia. 2002. - Pp. 158-163.

56. Wooldridge M. Temporal Belief Logics for Modelling Distributed AI Systems // Foundations of DAI / Ed. by G. M. P. O'Hare, N. R. Jennings.— Wiley Interscience, 1995.

57. Wooldridge M. Time, Knowledge, and Choice // Intelligent Agents / Ed. by M. Wooldridge, J: P. Mueller, M. Tambe. Springer-Verlag, 1996. — Vol. II.

58. Next generation remote agent planner / A. K. Jonsson, P. H. Morris, N. Muscettola, K. Rajan // Proceedings of the Fifth International Symposium on Artificial Intelligence, Robotics and Automation in Space (iSAIRAS99). — 1999.

59. Planning in interplanetary space: theory and practice: Tech. rep. / A. K. Jonsson, P. H. Morris, N. Muscettola, K. Rajan: NASA Ames Research Center, 1999.

60. Laborie P., Ghallab M. IxTeT: An integrated approach for plan generation and scheduling.

61. Muscettola N. HSTS: Integrating planning and scheduling // Intelligent Scheduling / Ed. by M. Zweben, M. S. Fox.— San Mateo, CA: Morgan Kaufmann, 1994.-Pp. 169-212.

62. Issues in temporal reasoning for autonomous control systems / N. Muscettola, P. Morris, B. Pell, B. Smith. 1998.

63. Remote agent: To boldly go where no AI system has gone before / N. Muscettola, P. P. Nayak, B. Pell, B. C. William II Artificial Intelligence.— 1998. Vol. 103, no. 1-2. - Pp. 5-48.

64. Smith D. E., Frank J., Jonsson A. AT. Bridging the gap between planning and scheduling // Knowledge Engineering Review. — 2000. — Vol. 15, no. 1.

65. Garrido A., Barber F. Integrating planning and scheduling // Applied Artificial Intelligence. An International Journal.—2001.— Vol. 15, no. 5.— Pp. 471-491. citeseer.nj.nec.com/563871.html.

66. Еремеев А. П., Шутова П. В., Тихонов Д. А. Поддержка принятия решений в условиях неопределенности на основе немарковской модели // Изв. РАН. Теория и системы управления. — 1999. — № 5. — С. 87-93.

67. A robust system for natural spoken dialogue / J. F. Allen, B. W. Miller, E. K. Ringger, T. Sikorski // Proceedings of the 1996 Annual Meeting of the Association for Computational Linguistics (ACL'96), June. — 1996. — Pp. 62-70.

68. Towards conversational human-computer interaction / J. Allen; D. Byron, M. Dzikovska etal. // АГMagazine. — 2001; — Vol. 22, no. 4. — Pp. 27-38.

69. Попов Э. В. Общение с базами данных на ограниченном естественном языке: прошлое, настоящее и будущее // Новости Искусственного Интеллекта. — 2002. — № 1. — С. 21-26.

70. Осипов Г. С. От ситуационного управления к прикладной семиотике // Новости Искусственного Интеллекта. — 2002. — № 6.—С. 3-7.

71. Осипов Г. С. Приобретение знаний интеллектуальными системами: Основы теории и технологии. Проблемы искусственного интеллекта. — М.: Наука. Физматлит, 1997. — 112с.

72. Shoham Y., Goyal //. Representing time and action in artificial intelligence // Frontiers of Artificial Intelligence. — 1988.

73. Нилъсон Н. Принципы искусственного интеллекта, Пер. с англ. — М.: Радио и Связь, 1985. — 376 с.

74. Allen J. F., Ferguson G. Actions and events in interval temporal logic: Tech. Rep. TR521: Rochester University, 1994; citeseer.nj.nec.com/allen94actions.html.

75. Chittaro L., Montanari A. Temporal representation and reasoning in artificial intelligence: Issues and approaches // Annals of Mathematics and Artificial Intelligence. 2000. - Vol. 28, no. 1-4. — Pp. 47-106.

76. Poesio M., Brachman R. J. Metric constraints for maintaining appointments: Dates and repeated activities // National Conference on Artificial Intelligence.— 1991. — Pp. 253—259. citeseer.nj.nec.com/poesio91metric.html.

77. Salum L. Representing time as a state in petri nets // Proc. 2nd ICRM-2002, Gaziantep, Turkey. 2001. - Pp. 955-960.

78. Joubel C., Raiman O. How time changes assumptions // Proc. 9th ECAI, Stockholm. 1990.

79. Loesel C., Charpillet F„ Haton J.-P. Temporal and hypothetical reasoning as a support for qualitative reasoning // Proc. of the 1992 IEEE Int. Conf. on Tools with AI. Arlington, VA, Nov. 1992. - Pp. 424-427.

80. Raiman O. Order of magnitude reasoning // Artificial Intelligence. — 1991. — Vol. 51.-Pp. 11-38.

81. Williams В. C. Doing time: Putting qualitative reasoning on firmer ground // Proc. 5th AAAI, Philadelphia Pensylvanie, / AAAI. — 1986. Pp. 105-112.

82. Dixon C., Fisher M., Johnson R. Parallel temporal resolution//Proceedings of the Second International Workshop on Temporal Representation and Reasoning (TIME-95). Melbourne Beach, Florida: 1995.

83. Towards the implementation of first-order temporal resolution: the expanding domain case / B. Konev, A. Degtyarev, C. Dixon et al. // Proceedings of TIME-ICTL 2003, July 2003, Cairns, Queensland, Australia.- IEEE CS Press, 2003.

84. Fisher M„ Dixon С., Peim M. Clausal temporal resolution // ACM Transactions on Computational Logic. — 2001.—January. — Vol. 2, no. 1. —. Pp. 12-56.

85. Wooldridge M., Dixon С., Fisher M. A tableau-based proof method for temporal logics of knowledge and belief I I Journal ofApplied Non-Classical Logics. — 1998.- Vol. 8, no. 3.- Pp. 225-258.

86. Dixon С., Nalon С., Fisher M. Tableaux for temporal logics of knowledge: Synchronous systems of perfect recall or no learning // Proceedings of TIME-ICTL 2003, July 2003, Cairns, Queensland, Australia.- IEEE CS Press, 2003.

87. Dixon C., Fisher M., Wooldridge M. Resolution for temporal logics of knowledge // Journal of Logic and Computation. — 1998. — Vol. 8, no. 3. — Pp. 345-372.

88. Schwalb E., Vila L. Logic programming with temporal constraints // Proc. of TIME-96.- 1996.

89. Schwalb E. Temporal Reasoning With Constraints: Ph.D. thesis / UCI ICS. — 1998.

90. Console L., Terenziani P., Dupre D. T. Local reasoning and knowledge compilation for efficient temporal abduction // IEEE Transactions on Knowledge and Data Engineering.— 2002.— November/December.— Vol. 14, no. 6. Pp. 1230-1248.

91. An efficient algorithm for temporal abduction / V. Brusoni, L. Console, P. Terenziani, D. T. Dupre // APIA.- 1997.- Pp. 195-206. citeseer.nj.nec.com/brusoni97efficient.html.

92. Nebel В., Backstrom С. On the computational complexity of temporal projection, planning, and plan validation // Artificial Intelligence. — 1994.—. Vol. 66, no. l.-Pp. 125-160.

93. Vila L., Godo L. On fuzzy temporal constraint networks // Mathware and Soft Computing. 1994. —Vol. 1, no. 3. —Pp. 315-334.

94. Godo L., Vila L. Possibilistic temporal reasoning based on fuzzy temporal constraints // Proc. of 11САГ95. — 1995.

95. Goodwin S. D., Neufeld Е., Trudel A. Probabilistic temporal representation and reasoning // International Journal of Expert Systems.— 1994.— Vol; 7, no. 3.-Pp. 261-288.

96. Kirillov V.t Honavar V. Simple stochastic temporal constraint networks: Tech. Rep. IASTATECS//TR95-16: 1995.-27. citeseer.ist.psu.edu/40031.html.

97. Dubois D., Prade H. Processing fuzzy temporal knowledge // IEEE Transactions on Systems, Man, and Cybernetics. — 1989. — august. — Vol. 19, no. 4.- Pp. 729-744.

98. Bovenkamp E., van der Lubbe J. Towards a fuzzy time structure for temporal reasoning with uncertainty // EUFIT-96, Aachen Germany, September 2-5 1996. Vol. 1. - Verlag Mainz, 1996. - Pp. 558-562.

99. Bovenkamp E., van der Lubbe. J. Temporal reasoning with fuzzy time-objects // Proc. of TIME-97. 1997.

100. Tin E., Актап V. Situated nonmonotonic temporal reasoning with BABYSIT // AI Communications. 1997. - Vol. 10. - Pp. 93-109.

101. ВинъковМ. М., Фоминых И. Б. Преобразование пропозициональных временных теорий с умолчаниями в расширенные логические программы // # Тр. междунар. конгресса «Искусственный интеллект в XXI веке». — М.: Физ.-мат. лит., 2001.- С. 92-105.

102. Schwalb Е., Vila L. Temporal constraints: A survey // Constraints. — 1998. — Vol. 3, no. 2/3.— Pp. 129-149. citeseer.nj.nec.com/article/schwalb98temporal.html.

103. VidalT., Ghallab M. Efficient temporal management through an apllication dependent graph decomposition // Proc. of TIME-95. — 1995.

104. Vidal Т., Ghallab M. Temporal constraints in planning: Free or not free? — 1995.

105. Penberty J. S„ Weld D. S. Temporal planning with continuous change // Proc. 12thNational Conf. on AI.- 1994.-Pp. 1010-1015.

106. Allen J. F. Maintaining knowledge about temporal intervals // Communications of the ACM. — 1983. — November. — Vol. 26, no. 11.— Pp. 832-843.

107. The TRAINS project: A case study in building a conversational planning agent / J. F. Allen, L. K. Schubert,, G. Ferguson et al. // Journal of Experimental and Theoretical AI. — 1995. — Vol. 7. — Pp. 7-48.

108. The design and implementation of the TRAINS-96 system: A prototype mixed-initiative planning assistant: Tech. Rep. TN96-5 / G. M. Ferguson, J. F. Allen, B. W. Miller, E. K. Ringger: Computer Science Dept., U. Rochester, 1996.

109. Ferguson G., Allen J. F. TRIPS: An integrated intelligent problem-solving assistant // Proceedings of the Fifteenth National Conference on AI (AAAI- . 98), Madison, WI, 26-30 July. 1998.

110. Ferguson G. Explicit representation of events, actions, and plans for assumption-based plan reasoning: Tech. Rep. 428: University of Rochester Comp.Science Department, 1992.

111. Fox M., Long D. PDDL+: Planning with time and metric resources: Tech. rep. — UK: Department of Computer Science, 21/02, University of Durham, 2002. http:/www.dur.ac.uk/d.p.long/competition.html.

112. McDermott D., Committee A. P. C. PDDL the planning domain definition language: Tech. rep.: 1998; www.cs.yale.edu/homes/dvm.

113. McDermott D. The 1998 AI planning systems competition // AI Magazine. — 2000. -Vol. 21, no. 2.

114. Long D., Fox M. An overview and analysis of the results of the 3rd international planning competition // Journal'of'AI Research. — 2003.

115. Yampratoom E., Allen J. F. Performance of temporal reasoning systems // SIGARTBulletin.- 1993.- Vol; 4, no. 3.

116. Boddy M.S. Temporal reasoning for planning and scheduling// A CM SIGART Bulletin. — 1993.-Vol. 4, no. 3.

117. Boddy M. S. Temporal Reasoning for Planning and Scheduling in Complex Domains: Lessons Learned // Advanced Planning Technology Technological Achievements of the ARPA/Rome Laboratory Planning Initiative / Ed. by A. Tate. AAAI Press, 1996;

118. Gerevini A., Schubert L., Schaejfer S. The temporal reasoning systems Timegraph I-II: Tech. Rep. TR494: 1994. citeseer.nj.nec.com/gerevini94temporal.html.

119. Gerevini A., Schubert ¿. Efficient algorithms for qualitative reasoning about time // Artificial Intelligence. 1995. - Vol. 74, no. 3. — Pp. 207-248.

120. Barber F. A metric time-point and duration-based temporal model // SIGART Bulletin.- 1993.- Vol. 4, no. 3.- Pp. 30-49. citeseer.nj.nec.com/barber93metric.html.

121. Bettini C., Wang X. S., Jajodia S. Solving multi-granularity temporal constraint networks // Artificial Intelligence. — 2002.— Vol. 140, no. 1-2.— Pp. 107-152.

122. Brusoni V., Console L., Terenziani P. Efficient query answering in LaTeR // Proc. of the Second International Workshop on Temporal Representation and Reasoning TIME-95.- 1995.-Pp. 121-128.

123. Dechter R., Meiri I., Pearl J. Temporal constraint networks // Artificial Intelligence. 1991. - Vol. 49. - Pp. 61-95.

124. Емельянов В. В., Ясиновский С. Я. Введение в интеллектуальное имитационное моделирование сложных дискретных систем и процессов. Язык РДО. М.: "АНВИК", 1998. - 427 с.

125. Еремеев А. П., Симонов Д. Н., Чибизова Н. В. Реализация прототипа системы поддержки принятия решений реального времени на основе инструментального комплекса G2 // Программные продукты и системы. — 1996. -№3. с. 21-26.

126. Allen J. F. Towards a general theory of action and time // Artificial Intelligence.- 1984.-Vol. 23.-Pp. 123-154.

127. Ma J., Knight B. Reified temporal logics: An overview // Artificial Intelligence Review.-2001. — Vol. 15. — Pp. 189-217.

128. Vila L. Revisiting time and temporal incidence. — 1996.

129. Shoham Y. Time for action // Proceedings 11th IJCAI.- 1989. Pp. 954959.

130. Galton A. A critical examination of Allen's theory of action and time // Artificial Intelligence. 1990. - Vol. 42. - Pp. 159-188.

131. Shoham Y. Temporal logics for AI: Semantical and ontological consideration // Artificial Intelligence. — 1987. — Vol. 33. — Pp. 89-104.

132. Knight B., Peng T., Mz J. Reasoning about change over time: Actions, events, and their effects // Formalization of Commonsense Reasoning. — 1998. — Pp. 183-197.

133. Ladkin P. B. The Logic of Time Representation: Ph.D. thesis / Group in Logic and Methodology of Science, University of California at Berkeley.— Berkeley, CA, US, 1987.

134. Vila L., Yoshino H. Time in automated legal reasoning: Tech. Rep. ICS-TR-96-57: 1996. citeseer.nj.nec.com/321912.html.

135. Ma J., Knight B. A general temporal theory // The Computer Journal.— 1994.-Vol. 37, no. 2.-Pp. 114-123.

136. Hayes P. J. A catalog of temporal theories. — MIT Press. — 1989.

137. Ma J., Knight B. A reified temporal logic // The Computer Journal. — 1996. — Vol. 39, no. 9.-Pp. 800-807.

138. Vila L. IP: An instant-period-based theory of time // Proc. ECAI'94 Workshop on Spatial and Temporal Reasoning / Ed. by R. Rodriguez. — 1994.

139. Freksa C. Temporal reasoning based on semi-intervals // Artificial Intelligence.— 1992.— Vol. 54, no. 1.- Pp. 199-227. citeseer.nj.nec.com/freksa92temporal.html.

140. Vilain M., Kautz H., van Beek P. Constraint propagation algorithms for temporal reasoning: A revised report // Readings in Qualitative Reasoning about Physical Systems.— San Mateo, CA: Morgan Kaufman, 1990. — Pp. 373-381.

141. Wetprasit R., Sattar A. Temporal reasoning with qualitative and quantitative information about points and durations//AAAI/IAAI. — 1998. — Pp. 656663. citeseer.nj.nec.com/wetprasit98temporal.html.

142. Bettini C., WangX. S., Jajodia S. A general framework for time granularity and its application to temporal reasoning // Annals of Mathematics and Artificial Intelligence. — 1998.- Vol. 22, no. 1-2. — Pp. 29-58.

143. Staab S., Hahn U. Scalable temporal reasoning // IJCAI. 1999. - Pp. 12471252. citeseer.nj.nec.com/272263.html,

144. Euzenat J. An algebraic approach for granularity in qualitative time and space representation // Proc. 14th International Joint

145. Conference on Artificial Intelligence (IJCAI), Montreal (CA).— San-Mateo (CA US): Morgan Kauffman, 1995.- Pp. 894-900. ftp://ftp.inrialpes.fr/pub/sherpa/publications/euzenat95e.ps.gz.

146. Euzenat J. A categorical approach to time representation: first study on qualitative aspects // Proc. IJCAI workshop on spatial and temporal reasoning, Montreal (CA).— 1995.— Pp. 145-152. йр://Лр.{ппа1рез.&/риЬ/5Ьефа/риЬНсайоп8/еигепа195с1.р8^г.

147. Bettini C., Rujfini S. Direct conversions among multi-granularity temporal constraints // Proc. of AAAI Workshop on Spatial and Temporal reasoning, Technical Report WS-02-17. — AAAI Press, 2002.- Pp. 20-26.

148. Hobbs J. R. Granularity // Proceedings of IJCAI-95 / AAAI.- 1985.-Pp. 432-435.

149. Ligozat G., Vila L. Ontology and Theory of Time // Time in Artificial Intelligence. — forthcoming, citeseer.nj.nec.com/ligozat98ontology.html.

150. Giisgen H.-W., Ladkin P. B. An algebraic approach to general boolean constraint problems // ? — 1995.

151. Ladkin Р. В., Maddux R. D. On binary constraint problems // Journal of the ACM.- 1994:- Vol 41, no. 3.- Pp. 435-469.citeseer.nj.nec.com/ladkin94binary.html.

152. Андерсон Д. А. Дискретная математика и комбинаторика: Пер. с англ. — М.: Издательский дом "Вильяме", 2003. — 960 с.

153. Krokhin A., Jeavons P., Jonsson P. Reasoning about temporal constraints: Classifying the complexity in Allen's algebra by using an alebraic technique: Tech. Rep. PRG-RR-01-02: 2001. citeseer.nj.nec.com/495284.html.

154. Reich A. J. Intervals, points, and branching time // International Workshop on Temporal Representation and Reasoning, TIME-1994. — 1994. — Pp. 121-. 133.

155. Allen J. F., Hayes P. Moments and points in an interval-based temporal logic // Computational Intelligence. — 1989. — Vol. 5. — Pp. 225-238.

156. Ligozat G. Generalized intervals: A guided tour // Proceedings of the ECAI-98 Workshop on Spatial and Temporal Reasoning, Brighton, UK. — 1998. citeseer.ist.psu.edu/ligozat98generalized.html.

157. McDermott D. Temporal logic for reasoning about processes and plans // Cognitive Science. — 1982. — Vol. 6. — Pp. 101-155.

158. Tsang E. P. Time structures for artificial intelligence // Proc., 10th International Joint Conference on Artificial Intelligence (IJCAI), August 1987.- 1987.-Pp. 456-461.

159. Knight B., Ma J.Time representation: A taxonomy of temporal models // Artificial Intelligence Review. 1994. - Vol. 7. - Pp. 401-419.

160. Galton A. Reified temporal theories and how unreify them // Proc. UCAI'91. — 1991.-Pp. 1177-1182.

161. Bacchus F., Tennenberg J., Koomen J. A non-reified temporal logic // Artificial Intelligence. 1991.-Vol. 52. -Pp. 87-108.

162. Reichgelt H. A comparison of first-order and modal logics of time // Logic-based Knowledge Representation / Ed. by P. Jackson, H. Reichgelt,. F. van Harmelen. The MIT press, 1989: — Pp. 143-176.

163. Vila L., Reichgelt H. The token reification approach to temporal reasoning: Technical Report 93-1: Dept. of Computer Science, UWI, 1993.

164. Artale A., Franconi E. A temporal description logic for reasoning about actions and plans // Journal of Artificial Intelligence Research. — 1998. — Vol. 9.-Pp. 463-506.

165. Artale A., Franconi E. Temporal Description Logics // Handbook of Time and Reasoning in Artificial Intelligence / Ed. by D. Gabbay, M. Fisher, L. Vila. — MIT Press, (forthcoming).

166. Bettini C. Time dependent concepts: Representation and reasoning using temporal description logics 11 Data and Knowledge Engineering. — 1997. — Vol. 22, no. l.-Pp. 1-38.

167. Armando A., Castellini C., Giunchiglia E. SAT-based procedures for temporal reasoning // ECP.— 1999.- Pp. 97-108. citeseer.nj.nec.com/article/armando99satbased.html.

168. Angelsmark O., Jonsson P. Some observations on durations, scheduling and Allen's algebra // Proceedings of the 6th Conference on Constraint Programming (CP'00). — Vol. 1894 of Lecture Notes in Computer Science. — Springer-Verlag, 2000. Pp. 484-488.

169. Vilain M., Kautz H. Constraint propagation algorithms for temporal reasoning // Proceedings of the Fifth National Conference of Artificial Intelligence / (AAAI).- 1986.- Pp. 377-382.

170. Krokhin A., Jeavons P., Jonsson /^ Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra I I Journal of the ACM.— 2003. Vol. 50, no. 5. - Pp. 591-640. - printed.

171. BalbianiP., Condotta J.-F., Ligozat G. Reasoning about generalized intervals: Horn representability and tractability // TIME.— 2000.- Pp. 23-30. citeseer.nj.nec.com/balbiani00reasoning.html.

172. Balbiani P., Condotta J.-F., del Cerro L. F. A new tractable subclass of the rectangle algebra // IJCAI.— 1999.- Pp. 442-447. citeseer.nj.nec.com/balbiani99new.html.

173. Broxvall M, Jonsson P. Disjunctive temporal reasoning in partially ordered models of time // AAAI/IAAL— 2000.- Pp. 464-469.citeseer.nj.nec.com/broxvallOOdisjunctive.html.,

174. Broxvall M, Jonsson P. Point algebras for temporal reasoning: Algorithms and complexity // Artificial Intelligence. — 2003.— Vol. 149, no. 2.— Pp. 179-220.

175. Broxvall M. — Computational complexity of point algebras for nonlinear time.— Master's thesis, Department of Computer Science, Linkoping, Sweden, 1999.- Master Thesis Report LiTH-IDA-Ex-99/48.citeseer.nj.nec.com/broxvallOOcomputational.html.

176. Broxvall M., Jonsson P. Towards a complete classification of tractability in point algebras for nonlinear time // Principles and Practice of Constraint. Programming. — 1999.—Pp. 129-143. citeseer.nj.nec.com/broxvall99towards.html.

177. Condotta J.-F. Tractable sets of the generalized interval algebra. — Pp. 78-82. citeseer.nj.nec.com/condotta00tractable.html.

178. Drakengren Т., Jonsson P. Maximal tractable subclasses of Allen's interval algebra: Preliminary report // Proc. AAAI'96. — AAAI Press/MIT Press,1996.-Pp. 389-394.

179. Drakengren Т., Jonsson P. Eight maximal tractable subclasses of Allen's algebra with metric time // Journal of Artificial Intelligence Research.—1997. — Vol. 7. — Pp. 25—45. citeseer.nj.nec.com/article/drakengren97eight.html.

180. Drakengren Т., Jonsson P. Twenty-one large tractable subclasses of Allen's algebra // Artificial Intelligence. 1997. - Vol. 93. — Pp. 297-319.

181. Drakengren Т., Jonsson P. A complete classification of tractability in Allen's algebra relative to subsets of basic relations // Artificial Intelligence.—1998.- Vol. 106, no. 2.- Pp. 205-219.

182. Jonsson P., Backstrom C. A unifying approach to temporal constraint reasoning // Artificial Intelligence. — 1998. — Vol. 102, no. 1.— Pp. 143155. citeseer.nj.nec.com/429592.html.

183. Jonsson P., Drakengren Т., Backstrom C. Computational complexity of relating time points with intervals // Artificial Intelligence.— 1999.— Vol. 109, no. 1-2.— Pp. 273-295. citeseer.nj.nec.com/jonsson99computational.html.

184. Koubarakis M. Tractable disjunctions of linear constraints: Basic results and application to temporal reasoning // Theoretical Computer Science. — 2001. — Vol. 266, no. 1-2. — Pp. 311-339. — printed.

185. Krokhin A., Jonsson P. Extending the point algebra into the qualitative algebra // Proceedings pf 9th Symposium on Temporal Representation and Reasoning, TIME'02. — 2002. — Pp. 28-35. citeseer.nj.nec.com/600339.html.

186. Krokhin A., Jeavons P., Jonsson P. Constraint satisfaction problems on intervals and lengths // SIAM Journal of Discrete Mathematics.— 2004.— Vol. 17, no. 3.- Pp. 453-477.

187. Nebel B., Burckert H.-J. Reasoning about temporal relations: A maximal tractable subclass of Allen's interval algebra II Journal of the ACM. — 1995. — Vol. 1, no. 42.-Pp. 43-66.

188. Pujari A., Sattar A. A new framework for reasoning about points, intervals and durations // Proceedings of the Int. Joint Conference on Artificial Intelligence (IJCAF99).- 1999.

189. Bessière C., Isli A., Ligozat G. Global consistency in interval algebra networks: Tractable subclasses.— Pp. 3-7. citeseer.ist.psu.edu/bessiere96global.html.

190. Wetprasit R., Sattar A., Khatib L A generalised framework for reasoning with multi-point events, citeseer.nj.nec.com/162590.html.

191. Bessiere C. A simple way to improve path consistency in interval algebra networks // Proceedings of AAAI-96 / AAAI.— AAAI Press, 1996.— Pp. 375-380.

192. Bhavani D., Pujari A. K. Efficient backtrack-free method for temporal CSP using evidential constraints // Proceedings of ??— 2002. citeseer.nj.nec.com/bhavani02efficient.html.

193. Delgrande J. P., Gupta A. Updating <, <-chains. — 2002.

194. Dorn J. Temporal reasoning in sequence graphs // Proc. of the 10th (US) National Conference on Artificial Intelligence (AAAI-92).— 1992.— Pp. 735-740. citeseer.nj.nec.com/dorn92temporal.html.

195. Galipienso M. I. A., Barber F. Representation and.reasoning with disjunctive temporal constraints // Proceedings of TIME'2002, Manchester. — 2002.

196. Garcia F., Laborie P. Hiérarchisation of the seach space in temporal planning // New Directions in AI Planning / Ed. by M. Ghallab, A. Milani.- IOS Press (Amsterdam), 1996.— Pp. 217-232. citeseer.nj.nec.com/garcia96hierarchisation.html.

197. Gerevini A., Schubert L. On computing the minimal labels in time point algebra networks: Tech. Rep. TR495: 1994. citeseer.nj.nec.com/gerevini95computing.html.

198. Gerevini A., Schubert L. Efficient algorithms for qualitative reasoning about time: Tech. Rep. TR496: 1994. citeseer.nj.nec.com/gerevini95efFicient.html.

199. Gerevini A., Schubert L. On point-based temporal disjointness // AI Journal- 1994.- Vol. 70.- Pp. 347-361.citeseer.nj.nec.com/gerevini94pointbased.html.

200. Kautz H. A., Ladkin P. B. Integrating metric and qualitative temporal reasoning // Proceedings of AAAI-91 National Conference on Artificial Intelligence. — 1991. — Pp. 241-246. citeseer.nj.nec.cora/kautz91 integrating.html.

201. Ladkin P. B:, Reinefeld A. Fast algebraic methods for interval constraint problems // Annals of Mathematics and Artificial Intelligence. — 1997. — Vol. 19, no. 3-4.— Pp. 383-411. citeseer.nj.nec.com/article/ladkin97fast.html.

202. Mouhoub M., Charpillet F., Haton J. P. Experimental analysis of numeric and symbolic constraint satisfaction techniques for temporal reasoning // Constraints.— 1998.— Vol. 3, no. 2/3.— Pp. 151-164. citeseer.ist.psu.edu/402885.html.

203. Nebel B. Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-horn class // European Conference on Artificial Intelligence.— 1996,— Pp. 38-42. citeseer.nj.nec.com/nebel97solving.htmL

204. Salido M., Garrido A., Barber F. Evaluation of algorithms to satisfy disjunctive temporal constraints in planning and scheduling problems // Proceedings of the AISB'OO Symposium on AI Planning and Intelligent Agents. 2000. - Pp. 33-40.

205. Song F. Extending temporal reasoning with hierarchical1 constraint // International Workshop on Temporal Representation and Reasoning, TIME-1994.- 1994.-Pp. 21-28.

206. Stergiou K., Koubarakis M. Backtracking algorithms for disjunctions of temporal constraints I I Artificial Intelligence. — 2000.— Vol. 120, no. 1.— Pp. 81-117. citeseer.nj.nec.com/stergiou98backtracking.html.

207. Stergiou К., Koubarakis M. Backtracking algorithms for disjunctions of temporal constraints // Proceedings of the 15th. National Conference on Artificial Intelligence (AAAI-98).- 1998.

208. Dechter R. From local to global consistency // Artificial Intelligence.— 1992.- Vol. 55.- Pp. 87-107.

209. Dorn J. Hybrid temporal reasoning // Proc. of the 11th European Conference on Artificial Intelligence (ECAI-94) / Ed. by A. G. Cohn. Wiley, 1994. -Pp. 625-629. citeseer.nj.nec.com/dom94hybrid.html.

210. Koubarakis M., Skiadopoulos S. Querying temporal constraint networks in PTIME // AAAI/IAAI. — 1999.- Pp. 745-750.citeseer.nj.nec.com/koubarakis99querying.html.

211. Nebel В. Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-horn class // Constraints. — 1997.— Vol. 3, no. l.-Pp. 175-190.

212. Schwalb E^, Dechter R. Coping with disjunctions in temporal constraint satisfaction problems // National Conference on Artificial Intelligence.—1993.— Pp. 127-132. citeseer.nj.nec.com/schwalb93coping.htmI.

213. Schwalb E., Dechter R. Processing temporal constraint networks // In Proceedings of the Twelfth National Conference on Artificial Intelligence,1994.— 1994. citeseer.nj.nec.com/schwalb94processing.html.

214. Schwalb E., Dechter R. Processing disjunctions in temporal constraint networks // Artificial Intelligence. — 1997. — Vol. 93. — Pp. 29-61.

215. Song F., Cohen R. Strengthened algorithm for temporal reasoning about plans // Computational Intelligence.— 1996.— Vol. 12, no. 2.— Pp. 331356.

216. Троицкий В. В. Временная логика Аллена — алгоритмы вывода // Четвертая международная летняя школа-семинар по искусственному интеллекту для студентов и аспирантов (Браславская школа — 2000): Сборник научных труцов. — Минск: БГУ, 2000. — С. 92-96.

217. Solving overconstrained temporal reasoning problems / M. Beaumont, A. Sattar, M. J. Maher, J. Thornton // Australian Joint Conference on Artificial Intelligence. — 2001. — Pp. 37-49. citeseer.nj.nec.com/477310.html.

218. Barber F. Reasoning on interval and point-based disjunctive metric constraints in temporal contexts I I Journal of Artificial Intelligence Research.— 2000.— Vol. 12.— Pp. 35-86. citeseer.nj.nec.com/barberOOreasoning.html.

219. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. : Пер. с англ.: Уч. Пос. — М.: Изд. дом. "Вильяме", 2000. — 384 с.

220. Кормен Т., Лейзерсон Ривест Р. Алгоритмы: построение и анализ.— М.: МЦНМО, 1999.—960 с.

221. Куриленко И. Е., Еремеев А. П. Некоторые принципы построения подсистемы временных рассуждений для СППР РВ // Сб. научн. трудов Научной сессии МИФИ-2004. В 15 томах. Т. 3.- М.: МИФИ, 2004.-С. 58-59.

222. Meiri I. Combining qualitative and quantitative constraints in temporal reasoning// Artificial Intelligence. — 1996.—Vol. 87, no. 1-2. —Pp. 343-385.

223. Schlieder C. Diagrammatic reasoning about alien's interval relations. citeseer.nj.nec.com/410767.html.

224. Morris P., Muscettola N. Execution of temporal plans with uncertainty 11 ? — 2000.

225. Navarrete I., Marin R. Qualitative temporal reasoning with points and durations 11 Proceedings of the 15th International Joint Conference on Artificial Intelligence (IJCAI-97).- 1997. Pp. 1454-1459.

226. Wetprasit R., Sattar A. Qualitative and quantitative temporal reasoning with points and durations (an extended abstract) // TIME. — 1998.— Pp. 69-73.citeseer.nj.nec.com/wetprasit98qualitative.html.

227. Badaloni S., Berati M. Hybrid temporal reasoning for planning and scheduling // Proceedings of the 3th Int. Workshop on Temporal Representation and Reasoning (TIME'96). — 1996.

228. Dechter R. Constraint Networks // Encyclopedia of Artificial Intelligence. — John Wiley&Sons Inc., 1992.

229. Jeavons P., Cohen D., Gyssens M. How to determine the expressive power of constraints // Constraints: An International Journal.— 1999.— Vol. 4.— Pp. 113-131.

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

231. Троицкий В. В. Архитектура системы темпоральных рассуждений // Второй международный конгресс студентов, молодых ученых и специалистов «Молодежь и наука — третье тысячелетие», Тезисы, Часть 2. — Т. 1.-М.: Изд. Профессионал, 2002. — С. 35-36.

232. Троицкий В. В. Система темпоральных рассуждений // Радиоэлектроника, электротехника и энергетика: Девятая международная научно-техническая конференция студентов и аспирантов МЭИ-2003: Тез. докл. В 3-х т. — Т. 3.- М.: Изд. МЭИ, 2003.- С. 313-314.

233. Ghallab М., Vidal Т. Temporal constraint in planning: Free or not free? // Proc. of FLAIRS-95 Workshop on Constraint Reasoning. — 1995.

234. Страуструп Б. Язык программирования С++.— 3-е изд.— СПб.; М.: «Невский Диалект» «Издательство БИНОМ», 1999.— 991 с.

235. Вандевурд Д., Джосаттис Н. М. Шаблоны С++: справочник разработчика.: Пер. с англ. — М.: Издательский дом "Вильяме", 2003.— 544 с.

236. Приемы объектно-ориентированного проектирования. Паттерны проектирования. / Э. Гамма, Р. Хелм, Р. Джонсон, Д. Влиссидес. Серия «Библиотека программиста», — СПб.: Питер, 2001.— 368 с.

237. Мейерс С. Эффективное использование STL. Библиотека программиста. — СПб.: Питер, 2002. — 224 с.

238. Бек К. Экстремальное программирование. Серия «Библиотека программиста». — СПб.: Питер, 2002. — 224 с.

239. НИКИЭТ, М. — Временный технологический регламент по эксплуатации I блока Игналинской АЭС с реактором РБМК-1500, 1983.

240. Маргулова Т. X. Атомные электрические станции: Учебник для вузов. — 4-е изд., перераб. и доп. изд. — М.: Высш. шк., 1984. — 304 с.

241. НИКИЭТ, М. — Технический проект АСУТП АС с реактором РБМК-1500, 1978.

242. МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ (Технический Университет)1. На правах рукописи

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

244. МЕТОДЫ И ПРОГРАММНЫЕ СРЕДСТВА ПРЕДСТАВЛЕНИЯ ВРЕМЕННЫХ ЗАВИСИМОСТЕЙ В ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМАХ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ

Похожие работы

Информатика, вычислительная техника и управление
05.13.00