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

□□3 17158 1

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

Куриленко Иван Евгеньевич

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ И ПРОГРАММНЫХ

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

РЕШЕНИЙ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

о э иЮН да

Москва-2008

003171581

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

Научный руководитель лауреат премии Президента РФ

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

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

Дзегеленок Игорь Игоревич,

кандидат технических наук, доцент Карпов Валерий Эдуардович

Ведущая организация Институт системного анализа Российской

Академии Наук (ИСА РАН)

Защита состоится июня 2008г в /¿_ час СО_ мин на заседании диссертационного совета Д 212 157 01 при Московском энергетическом институте (техническом университете) по адресу Москва, Красноказарменная ул, д 17, ауд ЛШ

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

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

Автореферат разослан //¿¿А. 2008 г

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

диссертационного совета Д 212 157 01 кандидат технических наук, ^

доцент ^ В Фомина

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

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

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

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

Выполненные исследования опираются на результаты работ в области ИИ и конструирования ИС отечественных ученых Д А Поспелова, А Н Аверкина, А А Башлыкова, В Н Вагина, В.В Емельянова, А П Еремеева, О П Кузнецова, В М Курейчика, О И Ларичева, А С Нариньяни, Г С Осипова, А Б Петровского, Г С Плесневича, В Э Попова, Г В Рыбиной, В А Смирнова, В Б Тарасова, В В Троицкого, В К Финна, И Б Фоминых, В Ф Хорошевского и др, зарубежных ученых J Alien, С Demetresku, R Detcher, A Gereviny, G Italiano, A Krokhin, I Mein, L Schubert, T van Alien и др

Объектом исследования являются модели и методы временного вывода Предмет исследования составляют методы поиска решения задач вре-

менного вывода для ИС типа ИСППР РВ

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

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

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

■ определение основных требований и принципов построения СВР для ИСППР РВ,

■ разработка полиномиальных алгоритмов решения задач временного вывода для базовой модели,

■ разработка методов пошагового уточнения решения задач временного вывода для базовой модели,

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

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

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

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

Научная новизна исследования состоит в следующем

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

2 Предложена временная логика TLM (Temporal Logic of Moments) и алгоритмы вывода для нее Показано, что с помощью TLM могут быть решены задачи временного вывода для точечной, интервальной и точечно-интервальной моделей времени.

3 Предложены алгоритмы пошагового уточнения решения задач временного вывода по мере поступления новой информации, оперирующие как качественной, так и метрической информацией

4 Предложена архитектура СВР для ИСППР РВ

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

возможности компьютеров и компьютерных систем, на примере ИСППР РВ для помощи ЛПР при мониторинге и управлении сложными техническими системами и процессами. Практическая значимость работы подтверждается использованием разработанной СВР в составе И С УП sPARK Предложенные в работе методы и алгоритмы временного вывода позволили повысить качество контроля, уровень безопасности и эффективность управления транспортными потоками, в частности, применение ИС УП sPARK на территории ОАО «МОССЕЛЪ-МАШ» позволило существенно увеличить пропускную способность контрольно-пропускных пунктов

Реализация результатов. Разработанная СВР использована в ЗАО «ААМ Автоматик» в ИСППР РВ в составе промышленной ИС УП sPARK для помощи оперативно-диспетчерскому персоналу, в учебно-научном процессе кафедры Прикладной математики (ПМ) МЭИ (ТУ) ИС УП sPARK внедрена на 45 объектах в России и СНГ Результаты работы использованы в НИР, выполняемых кафедрой ПМ в рамках грантов РФФИ № 02-07-90042 «Исследование и разработка инструментальных средств создания экспертных систем семиотического типа» (научн рук д т н , проф Вагин В Н, д т н , проф Еремеев А П), № 0507-90232 «Исследование и разработка инструментальных средств создания экспертных систем поддержки принятия решений» (научн рук Вагин В Н, Еремеев А П), № 08-01-00437 «Модели и методы поиска решения на основе экспертных знаний в интеллектуальных системах поддержки принятия решений» (научн. рук Еремеев А П ), в рамках Федеральной целевой НТП «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 годы (гос контракт от 1 02 2002 г №37 011 11.0021 идоп соглашение от 18 08 2004 г №5), тема «Системы мониторинга и поддержки принятия решений на основе аппарата нетрадиционных чогик» (рук Еремеев А П ) Программная реализация СВР зарегистрирована в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам (свидетельство № 2005610762от31 03 2005 г)

Акты о внедрении и использовании результатов работы прилагаются Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на научных конференциях аспирантов и студентов «Радиотехника, электроника, энергетика» в МЭИ (ТУ), (Москва, 2002-2008 г г), на «Научных сессиях МИФИ» (Москва, 2002-2008 г.г), на 13-й всероссийской межвузовской науч -техн конф «Микроэлектроника и информатика» (Москва, 2006 г), на 2-м междунар науч -практ семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2007 г), на 9-й нац конф по искусственному интеллекту с международным участием КИИ'2007 (Обнинск, 2007 г), на Международных форумах информатизации (Международных конференциях «Информационные средства и технологии») (Москва, 2003-2007 гг), на Международных науч -техн конф «Интеллектуальные системы» AIS (Россия, п Дивноморское, 2004-2007 г г)

Публикации. Основные результаты диссертационной работы, опубликованы в 30 печатных работах, включая 3 работы в изданиях, рекомендуемых ВАК Структура и объем работы. Диссертация содержит 187 стр машинопис-

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

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

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

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

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

■ поддержка согласованности информации о времени — проверка согласованности базы знаний при добавлении в нее новой информации,

■ ответы на временные запросы - от простого нахождения факта, справедливого в заданный момент времени, до определения, когда некоторое множество утверждений истинно в заданный момент времени

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

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

Опр 1 ЗСВО задается как Z = (V,D,BTR,C), где V={V,,V2, ,Ут} - конечное множество временных переменных; D - область значений временных переменных, BTR={rhr2, ,г„} - конечное множество взаимоисключающих бинарных базовых временных ограничений, полное объединение которых является универсальным ограничением U (вообще не накладывающим каких-либо ограничений), C={C,}\C,j-{ri, ,гк], к>О, Г[, Jt EBTR, i,j<jn} - конечное множество ограничений, где CtJ - ограничение над временными переменными V, и Vp интерпретируемое как (F„r/,)^)V V(Vt,rk,Vj) В случае, если C:J состоит только из одного дизъюнкта, то оно называется точным

Для решения задачи выполнимости §АТ необходимо найти такое множество ограничений С*= {СЬ'\С:'={rJ},r)£C,J), что входящие в него точные ограничения не противоречат друг другу Если такое множество находится, то ЗСВО является согласованной, иначе - несогласованной Для решения задачи нахождения согласованных сценариев ACS необходимо вычислить все возможные множества С

Элементы множества V могут интерпретироваться как моменты, интервалы времени или длительности Область значений переменных D, соответствующих моментам времени и длительностям, представляет собой множество вещественных чисел, а для интервальных переменных - множество упорядоченных пар значений Основными операциями над временными ограничениями являются отрицание (~i) -L4=U\LV, инвертирование (~) ~(rIt ,ri)=(~r;, ,~r,j, пересечение SC\T={r r£S,rET}, композиция r«S=(i/, ,tk)*(sb ,sq)=((ti»si), ('№)> XtpSq)). Множество всех возможных временных ограничений, связывающих два временных примитива, состоит из 2:BTRl ограничений, замкнуто относительно операций ->, П, • и образует алгебру временных ограничений

ЗСВО называют единичной (ЕЗСВО) тогда и только тогда, когда в множество С входят только точные ограничения Задачу определения точного ограни-

чения r£ С1р справедливого для переменных Vl и Vp для которых задано неточное ограничение Су={г/, ,гк}, к>\, называют задачей вычисления неточного ограничения Су

Опр 2 Ограничение Су выполнимо для переменных Г, и Vj тогда и только тогда, когда существует хотя бы одно решение ЗСВО, в котором С0 является ограничением для этих переменных Минимальным ограничением С,"'" называется множество, состоящее только из выполнимых ограничений для V, и Vj ЗСВО называют минимальной, если все ее ограничения минимальны

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

Для случаев, когда необходимо обрабатывать неточную информацию не только для двух временных примитивов, в работе введена дизъюнктивная ЗСВО (ДЗСВО)

Опр 3 ДЗСВО определяется как DZ=(Z,Ä), где Z - ЗСВО, A={a,\a,=(a,i, al2, a,k)} - множество дизъюнктивных ограничений, где каждый элемент а, интерпретируется как (a,7Va,2V Уаш), a4~{(xi,ri,yi)\xiyßV,rßBTR}, каждый элемент ау интерпретируется как (xi,rhy,)A Л(хм,гИ1уц) Для решения задачи выполнимости DSAT необходимо найти такое множество ограничений А*-{а, |a*={a,j},a,j£a,}, что ЗСВО Z'=(V,D,BTR,CVA ) имеет решение Для решения задачи АО необходимо найти все возможные множества А

Для решения задачи ШАТ с к элементами в множестве А в худшем случае необходимо проверить разрешимость |ау| \а2\ . |а*| ЕЗСВО Доказано, что в общем случае задачи Ш>§АТ и ACS являются NP-полными

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

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

Во второй главе вводится временная логика TLM (Temporal Logic of Moments) Ее исходными элементами являются

" счетное множество предметных переменных тьШ2, ,тп, , ■ предикатные символы Before, After, Equal,

■ логические связки -i, л, v, —*,

■ специальные символы (,),

■ логические значения. Т (истина), F (ложь)

Правила образованш атомов (атомарных формул TLM) если х и у переменные, то Before^), Afia(x,y), Equal^) - есть атомы, других атомоз нет

Правша образования ППФ всякий атом есть ППФ, если А и В ППФ, то каждое из выражений —А, ЛлВ, AvB, ~А, А—>В есть ППФ, других ППФ нет

Переменные в TLM интерпретируются над множеством вещественных чисел Предикатные символы интерпретируются как ограничения для переменных Before(x,y) г х<у, After(x,y) = х>у, Equa!(xly) = х=у

С помощью Before, After и Equal можно задавать ограничения «раньше», «позже», «одновременно» для моментов времени Приведем примеры высказываний TLM Возьмем ситуацию «После отказа системы охлаждения было зафиксировано предупреждение об опасном росте температуры, потом сработала автоматика аварийного отключения» Выделим моменты времени (переменные TLM) Mi - отказ системы охлаждения, М2 - предупреждение об опасном росте температуры; М3 - сработала автоматика аварийного отключения Соответствующее выражение TLM есть After(Mi,M2) л After(M2,M3) Аналогично для ситуации «Автомобиль с разовой картой не может проезжать через два пункта а и b одновременно», моментами будут Mi и М2- проезд автомобиля через пункты а и b соответственно, а выражением —£qual(Mi,M2).

ППФ А, содержащую переменные Xj^, jc„, будем обозначать А(х^> ■*„) ППФ A(xi^2, -хп) будем называть истинной, если существуют такие значения переменных х1гх2, -хт что A(xl7x2. -х„)=Т ППФ A(xJrt2, х„) называется общезначимой, если при любых означиваниях переменных xljc2> хп она является истинной Будем обозначать общезначимые формулы как М В TLM определяются - равносильные (эквивалентные) формулы

AA(AVB) = А А—>В = (-nAvB) А—»В = -,(Ал-.В) ->(-А.) = А -i(AaB) s -Av -,В -{AvB) s -Ал-iB АлАзА

АлВ = ВлА АуВ^ВУА Ал(ВлС) = (АлВ)лС Ау(ВУС) з (АУВ)УС АЛ(ВУС) = (АЛВ)У(АЛС) Ау(ВЛС) Н (АУВ)Л(АУС) Ау(АЛВ) = А - набор аксиом аксиома полного объединения ограничений

• Before(Jcly)vAfter(xly)vEqual(.t^y) з Т аксиомы инвертирования ограничений

• ~ВеГоге(х,у) = Айег(х,у) = Ве5эге(у,х)

• ~АЙег(х,у) = Вей)ге(х,}') з Айег(у^с)

• ~Equal(x,y) = Ве&ге(х,у)^АЙег(х.1у) аксиомы для операции отрицания

• -|Вейзге(:>с,у) = Айег(х1у)ч^иа1(:с,)')

AvAsA АлТ^А AvT = Т Aa-A = F Av-iA s Т AaF^F AvF = А

• -i Equal(x,}>) = В efore(x.y)vAfter(.t,y)

• -After(,rj.>) = Before(x,jv)vEqual(.x,y)

■ аксиомы противоречий

• Before(x,x)=F

• Añer(^)=F

• Before(xly)ABefore(>:!x)=F

• Añer(x,y)AAfter(y^:)=F

■ аксиомы транзитивности

• Equal(x,y)AEqual(y^) = Equal(jt,z)

• Before(x,y)ABefore(y,z) =Before(x,z)

• After(x,y)AAfter(z,x) = After(z,y)

■ аксиома эквивалентности Equal^) = Equal(y¿c)

- правила вывода

А,А -» В ЛлВ А -» (В -> С)

(1) (Modus ponens) (5) — (9)

A-*B,~iB AvB -iß АЛВ С

(2) ___ ÍModus tolens) (6) (10) _____

(3) ^^ (7) (u) )

W ^ ® ß -> (Л C)

- следующие задачи

■ Доказательство истинности ППФ (задача SAT),

■ Доказательство общезначимости ППФ (задача VAL),

■ Приведение ППФ к минимальному виду (задача MIN - минимизация формулы по числу вхождений предикатов Before, After, Equal),

* Для любых двух переменных хну вычисление ограничений, задаваемых множеством ППФ (задача QUEMO»

■ Вычисление всех возможных согласованных (задача ACS) Предлагается решение перечисленных задач в TLM путем сведения их к

аналогичным задачам для ДЗСВО в точечной алгебре.

Рассмотрим методы решения ЕЗСВО и ДЗСВО Решение ЕЗСВО в точечной алгебре (РА) основывается на преобразовании в задачу на графе, взвешенном временной информацией (ТЪРА-графе)

Опр 4 ТЬРЛ-граф есть граф G={W,E,L), где W- множество вершин, Щ0, E={(wJit,Wj)\w„wJEWJiíeL} - множество связей (ребер), !={<,<,#} - множество возможных пометок на ребрах графа Ребра, взвешенные ограничением < или <, - ориентированные, а ограничением Ф - неориентированные

Каждой вершине weWв ТЬРА-графе G={W,E£) соответствует, по крайней мере, одна временная переменная v6 V точечной ЗСВО Z Если какой-либо из вершин графа соответствует более одной переменной, то они являются альтернативными именами для одного и того же момента времени Ситуация, когда одна и та же переменная соответствует более чем одной вершине, недопустима Будем считать, что существует функция ц W—> V, сопоставляющая вершинам графа из множества W имена временных переменных из множества V

Опр 5 Интерпретацией ТЬрд,-графа G называется тройка <T,I,R>, где Т -упорядоченное множество, I V—>T - функция, такая, что для всех р,р£Р выполнимо, что если /л(р,)^/.1(р;), то I(p)~l{pj), R L-*T - функция, отображающая каждую метку /£L на ребрах графа G в соответствующее бинарное ограничение R{1) на Т Моделью ТЪРА-графа G=()V,E,L) называется такая интерпретация, для которой справедливо если (wi,1,m>2) - ребро в графе G, то для всех р„р^Р, таких, что ¡i(p^)=\vi и m(Pj)~Wj> выполняется <I(p,)J(pj)>ER(l)

Опр б ТЪРА-граф согласован (непротиворечив), если он имеет по крайней мере одну модель Два или более ТЬРА-графа логически эквивалентны, если они обладают одними и теми же моделями

Опр 7 Путем длины п от вершины w0 к вершине w„ в ТЬРА-графе G называется последовательность п ребер, которая задается набором троек (\vi,lj,w2),

(w„.;,/„,w„), где w, (0<i<n) - вершины и IjEL (0<j<n), (w„/„wi+;)6£. Путь в TLPA-графе называется «<-путем» («<-путем») длины п, если //={<} (если /,—{<}), при 0<}<п «<-путь» («<-путь») в ТЬРЛ-графе называется «<-циклом» («<-циклом»), если va=vn

Утверждение 1 ТЬРА-граф согласован тогда и только тогда, когда он не содержит ни одного «<-цшсла» и ни одного «<-цикла», содержащего две вершины, соединенные ребром, взвешенным ограничением ф

Таким образом, для решения задачи SAT необходимо преобразовать ЗСВО в ТЬРА-граф и проверить условия утв 1 Рассмотрим решение задачи МШ

Опр 8 ТЪрл-1раф согласован по путям, если для каждой пары его вершин существует не более одного соединяющего их ребра и для каждой тройки вершин и, v, w ограничение соответствующее связи (uj,v) не противоречит ограничениям для (w,/j,w) и (w,l2,v), т е выполнено условие /П/;«/^0

Опр 9 Будем считать ограничение типа г; сильнее ограничения типа г2 и записывать г]-*>г2, тогда и только тогда, когда из Г/ следует г2, но не его противоречие

Например, ограничение < сильнее, чем ограничение Ф, т к второе следует из первого

Опр 10 ТЬРА-граф содержит в себе неявное ограничение < для вершин v и w, если не существует ни одного «<-пути» от v к w и существует либо связь (у,Ф,у>) и «<путь» от v к w, либо связь (t,^,u) и «<~пути» (но не «<пути») от V к и, от и к W, ОТ V к / и от / к w (рис 1) Явным ТЬРА-графом для 1ЪРА-графа G называется ТЬРА-граф, логически эквивалентный исходному графу G и не содержащий неявных ограничений Согласованный по путям явный ТЬРЛ-граф назовем Time-графом.

Утверждение 2 Из явного TL А-графа G выводимо (h), что

■ v=w тогда и только тогда, когда v и w альтернативные имена одной и той же вершины,

■ v<w тогда и только тогда, когда существует «<-путь» от vkw,

■ v<w тогда и только тогда, когда существует «<-путь» от v к w,

'путь

Пср»мн 1 tm nc»kH*uu шринмчснии тнш < Lin си [К"Ч.Ш!I H И

S-путь

+ путь 'f

'-гутъ.

'' - путь

Вгортш ПК! НСЫНИОМ) I! fMil* I Kill < LI* lirpfMCHHUl v И It

['ч; i Дьл пи.a Jiii in. ^ ilrP iini'i;-iii s

■ -\фм тогда и только тогда, когда существует «<-путь» от v к w, или существует «<-путь» от w к V, или в графе существует связь между v и w взвешенная ограничением ф, Если произвести переход от ТЬРА-графа к Time-графу, то будут решены задачи SAT и MIN Рассматриваются алгоритмы преобразования ЗСВО в TLPA-граф, базовые алгоритмы преобразования ТЬРА-графа в Time-граф и способ решения задачи поиска выполнимого ограничения для двух переменных Для решения ДЗСВО предлагается использовать переход к задаче на дизъюнктивном графе времени (D-Time-графе) с применением алгоритма поиска с возвратами для поиска согласованного сценария или сценариев (задачи DSAT и ACS) Опр 11 D-Time-графом называется пара <G,T», где G=(W,E,L) - Time-граф, D = {V\Vr(dlhdj, d^)} - множество дизъюнктивных ограничений, где D, интерпретируется как (d^VdjV Vdlu), d^^xuriy^xtyiEWsßBTR} - множество точных ограничений

Определим множество ограничений в точечной алгебре М так, что для каждого Ъ, £ В в М входит один из du Е D, Будем считать D-Time-граф согласованным, если существует такое множество М, что ТЪРА-граф G*=(W, EüM,L) является согласованным Множество М назовем реализацией множества дизъюнктивных ограничений Т> для графа G Для решения задачи DSAT необходимо убедиться в существовании хотя бы одной реализации, для решения задачи ACS - найти все возможные реализации Известно, что задачи DSAT и ACS являются NP-полными Предложено два способа уменьшения сложности ДЗСВО - упрощение задачи и уменьшение размерности задачи для алгоритмов поиска с возвратами. В первом случае вводится ограниченная ДЗСВО (ОДЗСВО), в которой устанавливается ограничение на размер элементов Х>, множества V Зачастую в практических приложениях достаточно представления неточных временных ограничений в виде Т>, - (x,ri,y)\l(w,r2^) В связи с этим в работе ОДЗСВО определяется как ДЗСВО с бинарными неточными ограничениями Во втором случае осуществляется сокращение множества В по правилам сокращения пространства поиска (ПСПП) Множество бинарных PA-дизъюнкций V уменьшается до его подмножества Т>' за счет определения противоречий между точными и дизъюнктивными ограничениями Алгоритм поиска решения задачи DSAT разбивается на три этапа на первом этапе решается ЕЗСВО Z с получением Time-графа G, на втором - осуществляемся сокращение исходного множества дизъюнкций Ъ до его подмножества VQV, на третьем - применяется алгоритм поиска с возвратами

Введем множество ограничений Q, которые должны быть в каждой реализации множества PA-дизъюнкций Ъ для графа G-(W,E,L) Для ОДЗСВО в работе предлагается объединенное правило выводимости и резолюции, применяемое к каждой входящей в множество D дизъюнкции T>,~(x,i, rtl,yli)\l{xl2, г,2, у,2) (1) Пусть г® - ограничение между моментами времени xtl и у,/, следуемое из Time-графа G, а г2с - ограничение между х,2 и у,2 Если (rf -»r,;)V(r2c -» r,2), то Т), можно исключить из Ъ Если (г,;Пг1с=0)Л(г,2Пг2с#0), то V, можно исключить из D, ß<— Q\J {(xü,rt2y,2)} Если (^;Пг1с^0)Д(г,2Пг2с= 0), то 2), можно исключить

из Т>, Q<-QV{(x,if,iJ>u)} Если (г,,Пг?= 0)Л(г,2Пг2с=0), то D-Time-граф <G,Z>> несогласован

На основе этого правила разработан алгоритм предварительной обработки (алг 1), особенностью которого является то, что после первого просмотра всего множества РА-дизъюнкций D полученное множество РА-резольвент Q добавляется к графу и оставшееся множество дизъюнкций анализируется повторно Этот процесс продолжается до тех пор, пока будет добавлен хотя бы один элемент в множество Q и исходное множество D не пусто_

Алгоритм 1. Предварительная обработка дизъюнктивных ограничений_

Входные данные <G,D> - D-Time-граф, где G = (W,E,L) Выходные данные <G \V *> - упрощенный D-Time-граф

01 E'<—E,V'<—V, G'*-G

02 do {

03 е-0

04 foreach ((2J',={((*, rhy) V (w, r2, z))})e W) {

05 rf G'h(x,r{,y),r? G'b(w,rf,z)

06 r{— г, П rf, r2'<- r2 Л r2c

07 if ((if ri) v (r2c rj) V (rl=0) V (r2'=0)) {

08 Z)'<—D'\Z)',

09 if (^'=0 Л r2V0) 6 <- 2U{0> r2, z)}

10 if(ri^0Ari=0)e«-fiU{(r,ry,^)}

11 if (ri'=0 Л r2'=0) return inconsistent

12 } II foreach

13 £'<-£Ug, G'=(I£ £")

14 }

15 while ((ОФ0) Л (D#0))

16 return <G'=(W E') V>_

Для ДЗСВО разработаны адаптированные ПСПП

(2) Выводимости если существует с4€ 2)„ такое, что Gbdlk, то дизъюнктивное ограничение Ъ, может не включаться в множество поиска Т>'

(3) Резолюции если существует с/,аЕ Т>„ такое, что граф G =(W,Eud,k) - явтяется согласованным, и для всех D„ 1фк, граф G* ={W,Elid,i) - является несогласованным, то дизъюнктивное ограничение V, может не включаться в множество

поисками

В случае ДЗСВО дизъюнкции могут содержать более двух элементов и возможна ситуация, когда по правилу резолюции будет невозможно исключить из рассмотрения дизъюнкцию В, Однако в случае, если существует d,h£ Т>„ такой, что граф G'=(W,EUd,h,L) является несогласованным, то нет необходимости в рассмотрении d,i, с помощью алгоритма поиска с возвратами, т к попытка активации ограничений из d,h приведет к возврату В этом случае пространство поиска может быть уменьшено не исключением целого дизъюнктивного ограничения, а за счет исключения дизъюнкта (дизъюнктов) из дизъюнкции Предложены алгоритмы сокращения пространства поиска на основе предлагаемых правил

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

веты на запросы о согласованности (задача SAT) и вычислять выполнимые ограничения (задача МЩ) Кроме того, при решении ДЗСВО требуется периодическое изменение решенной ЕЗСВО, полученной на основе точных ограничений, по мере вычисления дизъюнктивных ограничений В этой ситуации целесообразно использовать принцип пошагового анализа модификаций, выполняемых в исходной сети временных ограничений, позволяющий сократить ряд этапов решения ЗСВО Если применять для решения ЗСВО после каждого из т изменений базовые алгоритмы, то сложность вычислений можно оценить величиной О(тш), где со -сложность решения ЗСВО на одном шаге Предлагаются алгоритмы, позволяющие уменьшить сложность во-первых, это алгоритмы, исключающие ряд этапов решения ЗСВО и ДЗСВО за счет анализа производимых изменений, во-вторых, предложены новые алгоритмы для решения ЗСВО и ДЗСВО по мере поступления информации, основанные на представлении ТЬРА-графа в виде множества существенных путей

Опр 12 Путем 7rxi,=<x(hxi, хк>т вершины х в вершину у в графе G называется последовательность вершин, в которой х0=х, хк=у и {хих,г1)£Е для всех 0<г<к В качестве веса пути примем w(^„)=nfjoX wxtxl+^ гДе wxtxl+1 ~ пометка ребра (х„х,4 ¡) В случае, если при вычислении веса wry в графе G существует направленная связь (у,Ifс), то в качестве wly принимается ~/ Будем называть путь пху существенным, если и w(7rxy)/0

Определим Р - множество всех направленных путей между всеми вершинами в графе G Число возможных элементов в Р не превышает значение е , где е - число ограничений, входящих в Е Определим: Р' - множество существенных путей в графе G, P'QP, множество входящих в вершину х путей Lp{x)={ж^Цх: Kix£P'} и множество выходящих из вершины х путей Яр(х)={жхт\ тфх,жш£Р'} Предложен алгоритм вычисления выполнимого ограничения между временными переменными х и у (алг 2), сложность которого составляет 0(max(\Rp(х)\,\Rp(y)\,\LP(x)\,\Lp(y)\)) при условии, что множества Rp и Lp могут

быть вычислены за время О(к), где к константа_

Алгоритм 2 Алгоритм вычисления выполнимого ограничения_

Входные данные дучиоменты времени, Р -множество всех существенных путей Выходные данные выполнимое ограничение для переменных хну

01 ForwardPatches <- Rp(x) П Lp(y)

02 RearwardPatchei «- Rp(y) П Lp(x)

03 Rxy -Dn:ljeForwardPatcheswinij)

04 Ryx i=riniJeRearwardPatchesw(nij)

05 return R„CiR„_

Алгоритмы создания (алг 3) и удаления ограничений строятся так, что они выполняются над множеством существенных путей и что ограничения, которые могут привести к несогласованности, отсекаются на этапе внесения Сложность алг 3 оценивается величиной 0(\Rp(y)\ |Lp(x)|), требуемый для работы объем памяти - 0(е~)_

Алгоритм 3 Алгоритм создания ограничений_

Входные данные ху - моменты времени, г - ограничение, г£{<,>,<>}, Р' - множество всех существенных путей в графе G_

01 ; '<— Алгоритм 2(iy,P")

02 if (r'f)r=0) return inconsistent H найдена несогласованность

03 if (r'-»r) return II Сушеивующее ограничение сильнее вносимого

04 foreach {KhfcLp(x)) {// Вычисление существенных nyiefi

05 if Р' = Р'иж,у," ith существенный

06 foreach (vim€Rp{y)) if ((vf(^;„,)/U)A(H(ж1т)Ф0)) P'-P' U щт // ж/т - существенным

07 } // forcach ïïIx€Lp(x)

08 foreach (ж„еКр(у)) if ((^у(жхт)Ф\])л(и{жх„)ФО)) Р' = Р'У жх„Н nr„ - существенный_

Алг 3 в результате работы вносит в множество существенных путей пути, которые образуются в TLPA-графе в результате создания связи (w,/,v) Сложность алгоритма удаления ограничения существенно выше сложности алг 3 и оценивается в худшем случае величиной 0(е2) Алгоритмы пошагового уточнения решения построены так, что они позволяют поддерживать в актуальном состоянии множество всех существенных путей на ТХРА-графе G, соответствующему ЗСВО, после каждого изменения В результате может быть получен только согласованный граф Основным преимуществом предложенного подхода является то, что после каждого изменения не требуется вызов допочнительных алгоритмов проверки согласованности и вычисления неявных ограничений

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

В третьей главе рассматриваются вопросы, связанные с программной реализацией СВР Формулируются требования к СВР, рассматриваются базовые принципы реализации СВР, которая должна обеспечивать представление и хранение информации о времени, поддержку временной согласованности БЗ при добавлении в нее новой информации (задача SAT), решение задачи поиска минимальной ЗСВО (задача ММ), решение задачи поиска согласованного сценария (или всех возможных согласованных сценариев) (задачи ©§АТ и ACS), проверку истинности временных утверждений

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

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

ложенный в работе язык запросов СВР - TQL (Temporal Query Language).

Рассматривается разработанный модуль интеграции СВР с инструментальным средством конструирования ИС CLIPS (С Language Integrated Production System). Описываются разработанные программные средства - интерпретатор TQL, графический редактор сетей временных ограничений (рис. 3) и монитор нагрузки СВР. Приводятся результаты тестирования СВР в разных режимах функционирования и результаты проведенных экспериментов по сравнению предложенных и улучшенных алгоритмов решения ЗСВО с базовыми (рис. 4). Анализ полученных результатов подтвердил оправданность реализации предложенных улучшений и существенное превосходство разработанных алгоритмов решения ЗСВО по сравнению с базовыми алгоритмами.

f хранилище моделей

Стандартизированный протопоп взаимодействия

Улряапснмс моделями

Блок контроля СВР

Рис. 2. Базовая архитектура СВР

Рис. 3. Экран графического редактора СВР

Время решений ЗСВО пошагово

Я

S 1

V

а К

_____________

Базовый алгоритм

-------------

/

Предложенный улучшении! алгоритм

Предложенный алгоритм пошагового уточнения решения ЗСВО

150Q 2000 Число ограничений

Рис. 4. Экспериментальное сравнение алгоритмов решения ЗСВО по мере поступления

информации

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

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

входит обеспечение контроля проезда на территорию комплекса, учет владельцев транспортных средств, предотвращение угона, препятствие несанкционированному доступу на территорию и обеспечение управления соответствующим оборудованием В качестве объекта доступа выступает автомобиль, а исполнительных устройств - шлагбаумы и ворота После принятия решения «доступ разрешен» необходимо проконтролировать факт проезда автомобиля на территорию с учетом временного фактора Рассматривается способ построения ИСППР РВ для ИС УП на основе СВР Приводится разработанная архитектура, определяется набор правил с представлением временных зависимостей для задачи предотвращения злоупотреблений со стороны посетителей и обслуживающего персонала (ЛПР) Отмечается, что за счет применения СВР становятся доступными дополнительные механизмы контроля Для управления жизненным циклом точек въезда/выезда используются продукционные правила, в которых явно вводятся временные ограничения Пример правила «Если в момент времени tj была активирована операция въезда айв момент времени t2 t2-t{>2 5 мин операция а все еще активна, то обратить внимание оператора на задержку на въезде» При анализе последовательностей событий с помощью СВР можно выделять подозрительные (нештатные) ситуации, например, на угон (рис 5)

) стоянка саг2 | движение caf2 " (

[ челоаеттрнвлижавтся 1:машин»carg [ f- движение carl j ( стоянка саг! [ -L_-«рем,--►

' I J__I _____

' появление человека , Начало движемий!

! || нзмашннысаг1__i I машинысаг2

"И ачалоиа6п»едемиа Останоьха Потери DtvekTa человм иэ виду ,

> за машиной carl j , машины cart рядом с машиной car2 I

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

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

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

Система временных рассуждений

База типовых штатных скгуаций (модели времени)

База типовых

нештатных, ситуаций I— (модели времени) I

Решатель на основе прецедентов

X

Влынайямных нештатных ситуация (модели времени)

_ Л.....

База найденных

нештатных ситуации (модели времени)

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

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

В Приложения вынесены вспомогательные таблицы и алгоритмы, а также обзор разработанного языка Т(ЗЬ и правила управления и контроля, примененные в разработанной ИС УП

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

2 Рассмотрены основные требования к СВР и принципы ее построения Определены основные задачи и функции СВР, необходимые в клиентских приложениях Предложен принцип взаимодействия СВР и ИС

3 Определена временная логика ТЬМ Предложен метод решения задач ТЬМ, основанный на преобразовании множества утверждений ТЬМ в ДЗСВО

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

5 Предложены методы ускорения процесса решения точечных ЕЗСВО Исследованы алгоритмы решения ДЗСВО и определены методы снижения их вычислительной сложности. Введено понятие ограниченной ДЗСВО и приведены методы ее решения Предложено правило, позволяющее уменьшить число модификаций ТЬРА-графа в процессе решения ДЗСВО

6 Рассмотрены методы сокращения пространства поиска для алгоритмов поиска с возвратами для решения ОДЗСВО и ДЗСВО Предложены схема применения ПСПП, позволяющая сократить множество дизъюнктивных ограниче-

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

7 Предложены алгоритмы пошагового уточнения решения качественных точечных ЕЗСВО и ДЗСВО

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

9 Предложена архитектура и программная реализация СВР. Исследованы особенности построения решателей ЕЗСВО и ДЗСВО, предложена базовая архитектура решателя Разработан язык временных запросов TQL Рассмотрены возможности интеграции СВР со средством построения ИС CLIPS

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

11 Рассмотрено практическое применение СВР в ИСППР РВ в составе ИС УП sPARK, решающей задачу помощи ЛПР при анализе нештатных ситуаций и управлении проездом автотранспорта. ИС УП установлена на ряде объектов на территории РФ и СНГ, о чем получены акты о внедрении Результаты диссертационной работы использованы также в научно-учебном процессе кафедры прикладной математики МЭИ (ТУ)

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

1. Еремеев АП, Куритенко ИЕ Реализация временных рассуждений для интеллектуальных систем поддержки принятия решений реального вречени И «Программные продукты и системы» Притоъе-ние к межд}нар журналу «Пробтемы теории и практики управления», X» 2,2005, с 8-16.

2 Еремеев А П., Куриленко И Е. Реализация механизма временных рассуждений в современных интеллектуальных системах // Изв. РАН Теория и системы управ пения, 2007, № 2, с 120-136

3 Еремеев А П, Куриленко И Е «Моделирование временных рассуждений в интеллектуальных системах реального времени»//Вестник МЭИ, 2008 №1 С 114-123

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

5 Еремеев А П, Куриленко И Е Архитектура подсистемы темпоральных рассуждений для ИСППР РВ // Тез док 10-й междунар научно-техн конф студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» в 3 т -Т1,-М Изд МЭИ, 2004,-С 320-321

6 Куриленко И Е Разработка единого внутреннего представления временных ограничений, заданных в терминах точечной модели времени//Тез док 11-й междунар научно-техн конф студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» в 3 т -Т 1,-М Изд МЭИ, 2005,-С 340-341

7 Куриленко И Е Унифицированный алгоритм проверки согласованности множества отношений для точечной модета времени//Сб тр научной сессии МИФИ-2005 в 15 т - ТЗ -М МИФИ, 2005 - С 156-157

8 Еремеев А П, Виноградов О В , Куриленко И Е Расширение языка CLIPS в плане конструирования интеллектуальных систем поддержки принятия решений реального времени Н Сб тр междунар науч-техк конф «Интеллектуальные системы» в 3 т-Т 1 -M ФизМатЛит, 2004, с 286-294

9 Куриленко И Е Алгоритм проверки согласованности множества неточных точечных временных ограничений Ч Труды междунар науч-техн конф «Информационные средства и технологии» -M Янус-К, 2005-Т 2-С 24-27

10 Еремеев А П, Куриленко И Е Интеграция системы временных рассуждений со средой CLIPS // Сб тр междунар науч -техн конф «Интеллектуальные системы» и «Интеллектуальные САПР» в 3 т - Т1 - М ФизМатЛит, 2005, С 301-312

11 Борисов А В , Казарицкий А С , Куриленко И Е О современных подходах к построению систем учета автотранспорта Программно-аппаратные средства// Информационные технологии в моделировании и управлении -2005 -Вып 5(23) - С 636-642

12 Борисов А В, Куриленко И Е Модель временных рассуждений в распределенной системе учета автотранспорта // Информационные технологии в моделировании и управлении -2005 -№5(23) -С 786-794

13 Борисов А В , Куриленко И Е, Хотимчук К Ю Модель временных рассуждений в распределенной системе платного доступа автотранспорта // Труды междунар науч -техн конф «Информалионные средства и технологии»-М Янус-К, 2005 -T 2 -С 20-24

14 Куриленко И Е Адаптация алгоритмов временного вывода для качественной точечной модели времени к динамическому изменению исходного множества временных ограничений // Тез док 12-й междунар науч-техн конф студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» в 3 т - T 1, -М Изд МЭИ, 2006, - С 402-403

15 Куриленко И Е Применение механизма временных рассуждений в системе контроля доступа автотранспорта // Сб тр междунар науч-техн конф «Информационные средства и технологии» в 3 т-ТЗ-М Янус-К, 2006 -С 118-121

16 Куриленко И Е Повышение эффективности алгоритмов вывода для системы временных рассуждений // Десятая нац конф по искусственному интеллекту с междунар участием КИИ-2006 (25 -28 сентября 2006 г, г Обнинск) Тр конф в 3 т -T 1 -М ФизМатЛит, 2006, - С 365-373

17 Еремеев АП, Куриленко ИЕ Применение механизма временных рассуждений в системе автоматизации гарковочного комплекса // Сб тр междунар науч -техн конф «Интеллектуальные системы» и «Интеллектуальные САПР» в 3 т-Т 1 -М ФизМатЛит,2006,-С 208-218

18 Куриленко И F Применение механизма временных рассуждений в системе автоматизации парковок // Тез док 13-й всероссийской межвузовской науч-техн конф «Мнкроэтектроника и информатика 2006» -M МИЭТ,2006 -С203

19 Куриленко И Е Повышение быстродействия алгоритмов временных рассуждений для качественной точечной модели времени//Сб тр научной сессииМИФИ-2006 в 15 т-ТЗ -М МИФИ, 2006 -С 154-155

20 Еремеев А П, Куриленко И Е Моделирование временных рассуждений в интеллектуальных системах // Сб тр междунар науч -техн конф «Интеллектуальные системы» и «Интллекгуальные САПР» Науч изд в 4 T-T2-M ФизМатЛит, 2007,-С 22-32

21 Eremeev А Р , Kunlenko IЕ Temporal reasoning for intelligent systems II In proc Of the International Scientific Conferences "Intelligent Systems" (AIS'07) In 4 volumes Vol 4 - Moscow Physmathht, 2007, pp 96 Еремеев А П, Куриленко И E Временные рассуждения в интеллектуальных системах // Сб тр междунар науч -техн конф «Интеллектуальные системы» AIS'07 Науч изд в 4 т -Т 4 -М ФизМатЛит, 2007,-С 96

22 Куриленко И Е Применение механизма временных рассуждений при построении систем учета автотранспорта//Тез док 13-й междунар науч-техн конф студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» в 3 г-Т 1,-М Изд МЭИ, 2007,-С 370-371

23 Куриленко И Е Представление метрической информации с помошью ТЬ-графов (графов, взвешенных временной информации) // Труды междунар науч-техн конф «Информационные средства и технологии» -М МЭИ,2007 -Т 3 -С 52-55

24 Борисов А В, Куриленко И Е Применение управляемой программной архитектуры при разработке систем автоматизации парковочных комплексов // Труды междунар науч -техн конф «Информационные средства и технологии МФИ-2007» - М МЭИ, 2007 -Т 3 -С 35-38

25 Еремееа А П, Куриленко И Е Применение временных рассуждений в интеллектуальных системах реального времени // Интеллектуальные системы Коллективная монография Выпуск второй / Под Ред В М Курейчика -М ФизМатЛит, 2007,114-130

26 Eremeev А Р, Kunlenko IЕ Implementation of the Temporal Reasoning Mechanism in Modern Intelligent Systems // J of Computer and Systems Sciences International, 2007 Vol 46 №2 Pp 279-294

Еремеев А П, Куриленко И E Реализация временных рассуждений в современных интеллектуальных системах // Международный журнал компьютерных и системных исследований, 2007 том 46 №2 С 279-294

27 Куриленко ИЕ О методах улучшения алгоритмов вывода для системы временных рассуждений II Сб тр IV-й междунар научно-практической конф Интегрированные модели и мягкие вычисления в искусственном интеллекте в 2 т - Т 1 - М ФизМатЛит, 2007 - С 149-156

28 Куриленко И Е Система временных рассуждений для интеллектуальных систем // Тез док 14-й междунар науч -техн конф студентов и аспирантов «Радиоэлектроника, электротехника и энергетика» в 3 т - Т 1 -М Изд МЭИ,2008 -С 299-301

29 Куриленко И Е «Обработка отношений неперекрываемости интервалов времени» // Сб тр научной сессии МИФИ-2007в 17т -ТЗ -М МИФИ,2007 -С 198-199

30 Куриленко И Е «Пошаговые алгоритмы временных рассуждений для точечной модели времени» // Сб тр научной сессии МИФИ-2008 в 15 т -TIO -М МИФИ,2008 -С 132-133

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

Зак

Тир Пл 1,5

ОГЛАВЛЕНИЕ.

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

ВВЕДЕНИЕ.

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

1.1. Области применения временного вывода.

1.2. Способы представления информации о времени.

1.3. Неявное моделирование времени.

1.4. Явное моделирование времени.

1.5. Временные расширения сетей Петри.

1.6. Модальные временные логики.

1.7. Модели времени на основе парадигмы согласования ограничений

1.7.1. Качественная точечная модель времени.

1.7.2. Интервальная модель времени.

1.7.3. Точечно-интервальная качественная модель времени.

1.7.4. Проблема временной неперекрываемости.

1.7.5. Точечная метрическая модель времени.

1.7.6. Качественная алгебра.

1.7.7. Выбор формализма для построения системы временных рассуждений.

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

ГЛАВА 2. Алгоритмы решения задач временного вывода.

2.1. Временная логика TLM.

2.2. Построение процедур вывода для временной логики TLM.

2.3. Решение качественных точечных ЗСВО.

2.3.1. Решение задачи

§АТ.

2.3.2. Решение задачи МИМ.

2.3.3. Алгоритм проверки согласованности.

2.3.4. Решение задачи QUERY.

2.3.5. Вычисления всех выполнимых ограничений.

2.3.6. Сравнение вычислительной сложности ВРА, CPA и РА.

2.4. Решение дизъюнктивных ЗСВО.

2.4.1. Базовые алгоритмы решения ограниченных дизъюнктивных ЗСВО.

2.4.2. Алгоритмы сокращения пространства поиска при решении ограниченных дизъюнктивных ЗСВО.

2.4.3. Решение дизъюнктивных ЗСВО.

2.5. Улучшенные алгоритмы решения единичных ЗСВО.

2.6. Пошаговые алгоритмы решения ЗСВО.

2.6.1. Алгоритмы предотвращения полного повторного решения единичных ЗСВО.

2.6.2. Пошаговое решение дизъюнктивных ЗСВО.

2.6.3. Пошаговые алгоритмы решения единичных ЗСВО.

2.7. Решение интервальных и точечно-интервальных ЗСВО.

2.7.1 Решение интервальных ЗСВО.

2.7.2. Представление ограничений временной неперекрываемости.

2.7.3. Решение точечно-интервальных ЗСВО.

2.8. Обработка метрической информации.

2.9. Качественная алгебра.

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

ГЛАВА 3. Реализация системы временных рассуждений.

3.1. Требования к СВР.

3.2. Базовые принципы реализации СВР.

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

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

3.5. Графический редактор сетей временных ограничений.

3.6. Интеграция СВР со средой CLIPS.

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

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

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

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

ГЛАВА 4. Практическое применение СВР.

4.1. Назначение интеллектуальной системы управления парковками.

4.2. Элементы предметной области.

4.3. Реализация ИС УП.

4.4. Решение задачи анализа аварийных ситуаций.

4.5. Выводы по главе 4.

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

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

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

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

Исследования проблемы времени, которая, как известно, имеет междисциплинарный характер, активно ведутся достаточно долго - понятие времени и его свойства давно являются предметом научных и философских исследований и занимают в них исключительно важное место. Время является одним из фундаментальных понятий при описании реального мира [1]. При этом вопрос о природе и, прежде всего об объективности времени, его существовании независимо от человеческого сознания на протяжении этих веков решался по-разному [2]. Различные философские концепции времени сменяли друг друга [3], однако в XX веке интерес к категории времени резко возрос уже не только в философии, айв других, прежде всего естественных, науках. Дифференциация знания привела к увеличению количества контекстов для понимания времени [4], и вслед за «физическим временем» началась разработка других естественнонаучных категорий времени, например, времени геологического и биологического. В середине прошлого столетия вопрос о структуре времени появился в рамках искусственного интеллекта (ИИ) и в настоящее время ведутся активные исследования в плане создания средств моделирования рассуждений с учетом временного фактора — временного темпоральных) вывода (рассуждений) [5].

О важности наличия средств представления времени и временных зависимостей (в данных и знаниях) в ИС говорится практически с момента появления таких систем [6]. Многие базовые понятия, такие как «изменение», «причина», «следствие» и отношения между ними описываются в терминах времени. Однако особенно актуальной проблема построения формальных систем оперирования темпоральной информацией встала именно в связи с появлением и развитием ИС, ориентированных на открытые и динамические предметные области (ПО), которые в процессе своего функционирования оперируют с большим количеством информации, изменяющейся со временем [7]. Типичными представителями таких систем являются ИСППР РВ [8], предназначенные для помощи человеку (ЛПР - лицу, принимающему решения) при мониторинге и управлении сложными объектами и процессами, при этом поиск решения должен обеспечиваться в условиях достаточно жестких временных ограничений и различного вида неопределенностей в исходных данных и знаниях [9]. Необходимость представления знаний меняющихся со временем (например, показаний датчиков, значений управляющих параметров, выполняемых операторами действий) возникает при решении многих задач ИСППР РВ [10]. Например, задач диагностики, мониторинга, планирования, прогнозирования и др. [11]. Использование при решении этих задач информации о времени позволяет сократить поисковые пространства и повысить скорость реакции системы [12].

Для реализации механизма временных рассуждений (МБР), реализующего временной вывод, необходимо формализовать понятие времени и обеспечить возможность представления и рассуждения о временных аспектах знаний [13]. Системный подход к построению сложных программных комплексов (ПК) требует при реализации выделения этого механизма в отдельную независимую систему - СВР [14]. Это позволяет избежать дублирования программного кода за счет его повторного использования (как в составе одной ИС в ее различных компонентах (блоках и моделях), так и в разных ИС).

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

Выполненные исследования опираются на результаты работ в области ИИ и конструирования ИС отечественных ученых Д.А. Поспелова, А.Н. Аверкина, А.А. Башлыкова, А.В. Борисова, В.Н. Вагина, В.В. Емельянова, А.П. Еремеева, О.И. Ларичева, О.П. Кузнецова, В.М. Курейчика, А.С. На-риньяни, Г.С. Осипова, А.Б. Петровского, Г.С. Плесневича, В.Э. Попова, Г.В. Рыбиной, В.А. Смирнова, В.Л. Стефанюка, В.В. Троицкого, В.К. Финна, И.Б. Фоминых, В.Ф. Хорошевского и др., а также зарубежных ученых J.Allen, С. Demetresku, R. Detcher, A. Gereviny, G. Italiano, A. Krokhin, I. Meiri, L. Schubert, T. van Allen и др.

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

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

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

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

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

Научная новизна исследования состоит в следующем: составлена развернутая классификация формальных систем оперирования временем. Классифицированы существующие и предложены новые методы улучшения алгоритмов решения задач временных рассуждений; предложена временная логика TLM (Temporal Logic of Moments) и алгоритмы вывода для нее. Показано, что с помощью TLM могут быть решены задачи временного вывода для точечной, интервальной и точечно-интервальной моделей времени; предложены алгоритмы пошагового уточнения решения задач временного вывода по мере поступления новой информации, оперирующие как с качественной, так и с метрической информацией; предложена компонентная архитектура СВР для ИСППР РВ.

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

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

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

Разработанная ИС УП sPARK внедрена на 48 объектах в России и СНГ. Так, в результате применения ИС УП на территории ОАО «МОССЕЛЬ-МАШ» удалось сократить число пробок на территории и увеличить пропускную способность контрольно-пропускных пунктов.

Результаты работы использованы в НИР, выполняемых в рамках грантов РФФИ: проект №02-07-90042 «Исследование и разработка инструментальных средств создания экспертных систем семиотического типа» (науч. рук.: д.т.н., проф. Вагин В.Н., д.т.н., проф. Еремеев А.П.); проект №05-07-90232 «Исследование и разработка инструментальных средств создания экспертных систем поддержки принятия решений» (науч. рук.: д.т.н., проф. Вагин В.Н., д.т.н., проф. Еремеев А.П.), № 08-01-00437 «Модели и методы поиска решения на основе экспертных знаний в интеллектуальных системах поддержки принятия решений» (науч. рук. Еремеев А.П.) и в рамках Федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 гг. (гос. контракт от 1.02.2002 г. №37.011.11.0021 и дополнительное соглашение от 18 августа 2004 г. №5), Раздел - «Информационно-телекоммуникационные технологии и электроника», подраздел — «Информационные технологии», по теме «Системы мониторинга и поддержки принятия решений на основе аппарата нетрадиционных логик» (науч. рук. д.т.н., проф. Еремеев А.П.).

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

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на научных конференциях аспирантов и студентов «Радиотехника, электроника, энергетика» в МЭИ (ТУ), (г. Москва, 2002-2008 гг.), на «Научных сессиях МИФИ» (г. Москва, 2002-2008 гг.), на 13-й всероссийской межвузовской научно-технической конференции «Микроэлектроника и информатика 2006» (г. Москва, 2006 г.), на 2-м международном научно-практическом семинаре «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (г. Коломна, 2007 г.), на 9-й национальной конференции по искусственному интеллекту с международным участием КИИ'2007 (г. Обнинск, 2007 г.), на конференциях «Информационные средства и технологии» (г. Москва, 2003-2007 гг.), на Международных научно-технических конференциях «Интеллектуальные системы» AIS (Россия, п. Дивноморское, 2004-2007 г.г.).

Публикации. Основные результаты, полученные при выполнении диссертационной работы, опубликованы в 30 печатных работах, включая 3 работы в изданиях, рекомендуемых ВАК.

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

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

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

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

3. Определена временная (темпоральная) логика TLM. Предложен метод решения задач TLM, основанный на преобразовании множества утверждений TLM в ДЗСВО.

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

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

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

7. Предложены алгоритмы пошагового уточнения решения качественных точечных ЕЗСВО, ДЗСВО, а также МЗСВО.

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

9. Предложена внутренняя архитектура СВР. Выполнена программная реализация СВР. Рассмотрены особенности построения решателей ЕЗСВО и ДЗСВО. Описана предлагаемая стандартная архитектура решателя, схема работы и структуры данных. Разработан язык временных запросов TQL для СВР. Рассмотрены возможности разработанного модуля интеграции СВР со средой CLIPS.

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

11. Рассмотрено практическое применение СВР в ИСППР РВ в составе ИС УП sPARK, решающей задачу помощи J111P при анализе нештатных ситуаций и управления проездом автотранспорта. ИС УП установлена и работает на ряде объектов на территории СНГ, о чем получены акты о внедрении. Результаты работы использованы также в научно-учебном процессе кафедры прикладной математики МЭИ (ТУ).

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

Разработка модуля пошагового решения ЗСВО и МЗСВО на основе современных промышленных БД;

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

ЗАКЛЮЧЕНИЕ

1. Трубников Н.И. Проблемы времени в свете философского мировоззрения // Вопросы философии. 1978. №2. С. 111-121.

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

3. Молчанов Ю.Б Четыре концепции времени в философии и физике. М.: Наука, 1977. - 192 С.

4. Рейхенбах Г. Философия пространства и времени: Пер. с англ. М.: Прогресс, 1985. - 344 С.

5. McCarthy J., Hayes P.J. Some philosophical problems from the standpoint of artificial intelligence // Machine Intelligence. Edinburgh University Press, 1969. №4. - Pp. 463-502.

6. Поспелов Д. А., Кандрашина Е.Ю., Литвинцева JI. В. Представление знаний о времени и пространстве в интеллектуальных системах. / Под редакцией Д.А. Поспелова М.: Наука, 1986. - 328 С.

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

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

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

10. Башлыков А.А., Еремеев А.П. Экспертная диагностическая система как компонент интеллектуальной системы поддержки принятия решений реального времени //Новости искусственного интеллекта. 2001. №3. С. 3540.

11. Еремеев А.П., Троицкий В.В. Концепции и модели представления времени и их применение в интеллектуальных системах. // Новости искусственного интеллекта. 2004. №1. С. 6-29.

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

13. Еремеев А.П., Куриленко И.Е. Реализация механизма временных рассуждений в современных интеллектуальных системах // Известия РАН. Теория и системы управления. 2007. № 2. С. 120-136.

14. Allen J.F., Yampartoom Е. Performance of temporal reasoning systems. // SIGART Bulletin, Vol. 4, no. 3., 1993. TN-93-1.

15. Kautz H. A formal theory of plan recognition and its implementations. In J.F. Allen, H. Kautz, R. Pelavin, and J. Tenenverg, editors, Reasoning about plans, San Mateo, CA, 1991. Morgan-Kauffman.

16. Penberty J.S., WeldD.S. Temporal planning with continious change // Proc. 12thNational conf. on AI. 1994. Pp. 1010-1015.

17. Allen J.F. Maintaining Knowledge about Temporal Intervals. // Communications of the ACM. 1983. Vol. 26, no. 11. Pp. 832-843.

18. Shahar Y. Timing is everything: Temporal reasoning and temporal data maintenance in medicine // Lecture Notes in Computer Science. 1999. Vol. 1620. Pp. 30-47.

19. Попов Э.В. Общение с ЭВМ на естественном языке. М.: Наука. Гл. ред. физ.-мат. лит., 1982.

20. Allen J.F., Byron D., Dzikovska M. et al. Towards conversational human-computer interaction. // AI Magazine. 2001. - Vol. 22, №4. - Pp. 27-38.

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

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

23. Hildebrandt W., Katz В., Lin J. Answering definition questions with multiple knowledge sources. // In Proceedings of the 2004 Human Language Technology Conference (HLT/NAACL 2004). 2004. Pp/ 49-56.

24. Малъковский M.F. Диалог с системой искусственного интеллекта. М.:МГУ, 1985.

25. Кап Lo К., Lam W. Using semantic relations with world knowledge for question answering // In proceedings of the Fifteenth Text REtrieval Conference (TREC 2006). 2006. Pp. 403.

26. PnuelliA. The temporal logic of programs. Proc. 18th Ann. Symp. Found. Computational Science, 1977. Pp. 46-57.

27. Валиев M.K. Применение временной логики к спецификации программ // Программирование. 1998. №2. С. 3-9.

28. PnuelliA. The temporal semantics of concurrent programs // Theor. Computer Science, 1981. V. 13. Pp. 45-60.

29. Manna Z., Pnuelli A. Proving precedence properties: the temporal way. Proc. Intern. Coll. on Automata, Languages, Programming. // LNCS. 1983. №154. P. 491-512.

30. Koubarakis M. Foundations of Temporal Constraint Databases. // Ph.D. thesis. 1993.

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

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

33. Koubarakis M. Reasoning about time and change: A knowledge base management perspective. // Intelligence (IJCAI'91), 1991, Pp. 472-477.

34. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. Науки об искусственном. М.: Эдиториал УРСС, 2002. - 352 с.

35. Cunningham J. Temporal Agents (Chapter in book Mistakes of Reason: Essays in Honour of John Woods.) University of Toronto Press. 2005. Pp. 380-397.

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

37. Staab S., MaedcheA. Knowledge portals: Ontologies at work // AI Magazine. 2001. Vol. 22, no. 2. Pp. 63-57.

38. Augusto J.C., Nugent C.D. The Use of Temporal Reasoning and Management of Compex Events in Smart Homes // European Conference on Artificial Intelligence. 2004. Pp. 778-782.

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

40. Еремеев А.П., Куриленко И.Е. Реализация временных рассуждений для интеллектуальных систем поддержки принятия решений реального времени. // Программные продукты и системы. 2005. №2. С. 5-16.

41. Слинина Я. А., Караваева Э.Ф., Мигунова А.И. Символическая логика. -СПб.: Изд-во С.-Петерб. ун-та, 2005. 506 с.

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

43. Fikes R., Nilsson N. STRIPS: a new approach to the application of theorem proving to problem solving. // Artificial Intelligence. 1971. №2. Pp. 189-208.

44. Троицкий B.B. Методы и программные средства представления временных зависимостей в интеллектуальных системах поддержки принятия решения. // Диссертация на соискание ученой степени к.т.н. М.: МЭИ, 2004.

45. Petri С.А. Kommunikation mit Automaten. // Ph. D. Thesis. University of Bonn. 1962.

46. Котов В. Сети Петри. М.: Наука, 1984.

47. Бестуэюева И.И., Руднев В.В. Временные сети Петри. Классификация и сравнительный анализ. // Автоматика и телемеханика. 1990. №10. С. 3-31.

48. Russel S., NorvigP. Artificial Intelligence: A modern approach. Prentice Hall. 2002. 1132 pages.

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

50. Merlin P.M. A methodology for the design and implementation of communication protocols. // IBM. T.J. Watson Res. Center. Yorktown. Meights. N.Y., 10598, rep. RC-5541. June 1975.

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

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

53. Vila L. A survey on temporal reasoning in artificial intelligence. // AI Communications. 1994. Vol.7, no. 1. - Pp. 4-28.

54. Emerson E.A. Temporal and modal logic. Handbook of Computer Science, vol. B. MIT Press.1990.

55. Emerson E.A., Halpern J.Y. Decision procedures and expressiveness in the temporal logic of branching time. // Journal of Computer and System Scuences. 1985. Vol. 30., no. l.Pp. 1-24.

56. Ladkin P.B. The Logic of Time Representation. // Ph.D. thesis. University of California at Berkeley. Berkeley, CA, US, 1987.

57. Meiri I. Temporal reasoning: A constraint-based approach. Ph. D. dissertation, University of California, 1992.

58. Окуниишикова E.B. Временные сети Петри без перекрытий интервалов срабатывания // Программирование. №5. 1998. С. 15-29.

59. Смирнов В.А. Логические системы с модальными временными операторами // Тр. II Советско-финского коллоквиума по логике «Модальные и временные логики». М.: Ин-т философии АН СССР, 1979.62 .Аристотель. Собрание сочинений. М.:Мысль, 1976.

60. Prior A.N. Diodorian modalities // The Philosophical Quarterly. 1955. V.5, no 20.

61. LemmonJ., Scott D. An introduction to modal logic. 1977. Oxford: Blackwell.

62. Фон Вригт Г.Н. Логико-филосовские исследования. Избранные труды. М.: Прогресс, 1986.

63. Torsunl.S. Foundations of Intelligent Knowledge-Based Systems // ACADEMIC PRESS, London, 1998. ■

64. Валиев M.K. О логике ветвящегося времени. // Всесоюзная конференция по логике, методологии и философии науки. Паланга, 1982.

65. Еремеев А.П. Об интеграции моделей в интеллектуальных системах поддержки принятия решений // Девятая национальная конферен-ция по искусственному интеллекту с международным участием КИИ-2004: Тр. конф. В 3-х т. Т.2. М.: Физматлит, 2004, с. 815-823.

66. Prior A.N. Time and Modality. 1957. Oxford: Clarendon Press.

67. Prior A.N. Past, present and future. 1967. Oxford: Clarendon Press.

68. Prior A.N. Papers on Time and Tense. 1969. Oxford: Clarendon Press.

69. KampJ.A. Tense logic and the teory of linear order. Ph. D. thesis, University of California, Los Angeles. 1968.

70. Sistla A.P., Vardi M., WolperP. Reasoning about infinite computation paths.// Proc. 24 IEEE FOCS. 1983. Pp. 185-194.

71. Миронов A.M. Математическая теория программных систем. // http://intsys.msu.ru/study/mironov/mthprogsys.pdf.

72. Миронов A.M., Жуков Д.Ю. Математическая модель и методы верификации программных систем. Интеллектуальные системы. Том 9. 2005. Москва. С. 209-252.

73. Manna Z., Wolper P. Synthesis of communicating processes from temporal logic specifications // ACM Trans. Progr. Lang. Systems. 1984. V6. №1. P. 68-93.

74. Mackworth A.K. Consistency in networks of relations // Artificial Intelligence. 1977. Vol. 8. Pp. 99-118.

75. Bachus F., van BeekP. On the conversion between non-binary and binary constraint satisfaction problems // Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-98) AAA! Press, 1998. Pp. 311-318.

76. Ladkin P.B., Maddux R.D. The algebra of constraint satisfaction problems and temporal reasoning // Technical Report, Crestel Institute, 1988.

77. Gerevini A., Schubert L. On computing minimal labels in time point algebra networks // Technical report 9408-10, Instituto per la Ricerca Scientifica e Tecnologica, 1994.

78. Alfonso М., Barber F. Representation and reasoning with disjunctive temporal constraints // Proceedings of the Ninth Symposium on Temporal Representation and Reasoning (TIME*02), 2002. Pp. 46-48.

79. Gerevini A., Schubert L. Efficient Algorithms for Qualitative Reasoning about Time. // Technical report 496, Department of Computer Science, University of Rochester, Rochester; NY, 1993.

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

81. Tarjan R. Depth-first search and linear graph algorithms. // SIAM №1, pages 146-160, 1973.

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

83. StergiouK., Koubarakis М. Backtracking algorithms for disjunctions of temporal constraints // Artificial Intelligence. 2000. - Vol. 120, №1. Pp. 81-117.

84. Gennari R. Temporal reasoning and constraint programming: A survey. // CWI Quarterly, Vol. 11, no 2-3, 1998. Pp. 163-214.

85. Ghallab M., Laborie P. IxTeT: An integrated approach for plan generation and cheduling.// Proceedings of Emerging Technologies and Factory Automation. 1995. Vol. l.Pp. 485-495.

86. Van BeekP. Exact and Approximate Reasoning about Qualitative Temporal Relations. //PhD thesis, Dept. of Computer Science, University of Waterloo. -Waterloo, Ontario, Canada, 1990.

87. Van Веек P., ManchakD. W. The Design and Experimental Analysis of Algorithms for Temporal Reasoning. // Journal of Artificial Intelligence Research №4. 1996. Pp. 1-18.

88. Van BeekP. Reasoning about qualitative temporal information // Artificial Intelligence. 1992. № 58. Pp. 297-326.

89. Broxvall M., Jonsson P. Point algebras for temporal reasoning: Algorithms and complexity. // Artificial Intelligence. 2003. Vol. 149, no. 2. Pp. 464-469.

90. Broxvall M., Jonsson P. Disjunctive temporal reasoning in partially ordered models of time //AAAI/IAAI. 2000. Pp. 464-469.

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

92. Mitra D. Theoretical and practical implications of an algorithm for finding all consistent temporal models // Proceedings of the Second IEEE International Workshop on Temporal Representation and Reasoning Regina (CA): University of Regina, 1995.

93. Allen J.F. Planning as temporal reasoning. // Second International Conference on Principles of Knowledge Representation and Reasoning, Cambridge, April 1991.

94. Allen J.F., Ferguson G. Actions and events in interval temporal logic: Tech. Rep. TR521: Rochester University, 1994.

95. Krokhin A., Jonsson P. Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra. // Technical Report PRG-RR-01-12. Computing Laboratory, Oxford University, 2001.

96. Van BeekP. Temporal query processing with indefinite information. // Artificial Intelligence in Medicine 3, 1991. Pp. 325-339.

97. Nebel B. Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-Horn class // ЕСАГ96 (12th European Conference on Artificial Intelligence).

98. Ladkin P.В., Reinefeld A. Effective solution of qualitative interval constraint problems //Artificial Intelligence. 1992. №57. Pp. 105-124.

99. Krokhin A., Jeavons P., Jonsson P. The complexity of constraints on intervals and lengths. // STACS 2002, pages 443-454, France 2002.

100. Jonsson P., Drakengren Т., Backstrom C. Computational complexity of relating time points and intervals. // Artificial Intelligence, 109(1-2), 1999. Pp. 273-295.

101. Tsamardionis I. Constraint-based temporal reasoning algorithms with application to planning. // Ph. D. dissertation, University of Pittsburgh.

102. Gerevini A., Schubert L. On point-based temporal disjointness. // Technical report 497, Department of Computer Science, University of Rochester, Rochester, NY, 1994.

103. Schwalb E. M. Temporal reasoning with constraints // Ph. D. dissertation, University of California, Irvine, 1998.

104. Krokhin A., Jonsson P. Extending the Point Algebra into the Qualitative Algebra. // Technical Report PRG-RR-03-12. Computing Laboratory, Oxford University, 2003.

105. Meiri. I. Combining qualitative and quantitative constraints in temporal reasoning. // Proceedings of the Ninth National Conference on Artificial Intelligence. Menlo Park, California: AAA! Press, 1991. Pp. 260-267.

106. Kautz H., Ladkin P. Integrating Metric and Qualitative Temporal Reasoning. //AAAI, 1991, Pp. 12-19.

107. Dechter R., Meiri I., Pearl J. Temporal Constraint Networks. // Artificial Intelligence №49, 1991. Pp. 61-95.

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

109. Gerevini A., Schubert L. Efficient temporal reasoning through timegraphs. // IJCAI-1993, Pp. 648-654.

110. Gerevini A., Schubert L. An efficient method for managing disjunctions in qualitative temporal reasoning // In principles of knowledge representation and reasoning: Proceedings of the Fourth International Conference, San Francisco, CA, 1994.

111. Demetrescu C., Italiano J. A new approach to dynamic all pairs shortest paths. // Journal of the ACM. 2004. Proceedings 42nd IEEE Symposium on Foundations of Computer Science. 2004. Pp. 968-992.

112. Ladkin P.В., Maddux R.D. The algebra of convex time intervals. 1987.

113. Еремеев А.П., Куриленко И.Е. Архитектура подсистемы темпоральных рассуждений для ИСППР РВ // Десятая международная научно-техническая конференция студентов и аспирантов 2004 (Сборник научных трудов), Том 1, с 320.

114. Еремеев А.П., Куриленко И.Е. Архитектура подсистемы темпоральных рассуждений для ИСППР РВ. // Труды десятой международной научно-технической конференции студентов и аспирантов Радиоэлектроника, электротехника и энергетика 2004, т. 1. С. 320-322.

115. Gerevini A., Schubert L., Schaeffer S. The Temporal Reasoning Systems TimeGraph I-II //Tech. Rep. 494, Univ. of Rochester, Computer Science Dept., April 1994.

116. Трелъсен Э. Модель COM и применение ATL 3.0: Пер. с англ. СПб.: БХВ-Петербург. 2005. 928 С.

117. Троельсен Э. Язык программирования С# 2005 и платформа .NET 2.0 : Пер. с англ. М.: ООО "И.Д. Вильяме", 2007 - 1168 С.

118. Мейер Б. Объектно-ориентированное конструирование программных систем. Пер. с англ. М.гРусская редакция, 2005. - 1232 С.

119. Gerevini A., Schubert L., Schaeffer S. Temporal reasoning in TimeGraph I-II. SIGART Bulletin, 4(3): 1993. Pp.21-25.

120. Van Allen Т., Delgrande J.P., Gupta A. Point-based Approaches to Qualitative Temporal Reasoning // Proceedings of the 5th Pacific Rim International Conference on Artificial Intelligence. 2002. Pp. 305-316.

121. Куриленко И.Е. Разработка единого внутреннего представления временных ограничений заданных в терминах точечной модели времени. // Одиннадцатая международная научно-техническая конференция студентов и аспирантов 2005, Том 1, С. 340.

122. Golumbic М.С., ShamirR. Complexity and alghoritms for reasoning about time: A graph-theoretic approach. I I Journal of the ACM, 40(5), pages 1108-1133, 1993.

123. ШефердД. Программирование на Microsoft Visual С++ .NET : Пер. с англ. M.: Русская редакция, 2003. - 928 С.

124. Теплее М. Borland С++ Builder: библиотека программиста. // СПб: Питер Ком, 1998.- 512 С.

125. Ramerez А. О. Programming Bits: Meeting С# and Mono. // Linux Gazette, №84, November 2002.

126. Частиков А.П., Гаврилова Т.А., Белов Д.Л. Разработка экспертных систем. Среда CLIPS. // СПб: BHV-Санкт-Петербург, 2003 г., 606 С.

127. Popolizio J. CLIPS: NASA's COSMIC Shell // Artificial Intelligence Research, 1988.

128. Джексон П. Введение в экспертные системы. // М.: Вильяме, 2001.

129. Виноградов О.В., Еремеев А.П., Куриленко И.Е. Расширение языка CLIPS в плане конструирования интеллектуальных систем поддержки принятия решений реального времени. // Труды международной научно-технической конференции IEEE AIS'04, 2004. С.285-295.

130. Еремеев А.П., Куриленко И.Е. Интеграция системы временных рассуждений со средой CLIPS // Труды международной конференции «Информационные технологии» (IEEE AIS'05). 2005.

131. Еремеев А.П., Куриленко И.Е. Свидетельство о регистрации программного средства №2005610762, выданное Федеральной службой по интеллектуальной собственности, патентам и товарным знакам.

132. Борисов А.В., Кин Е.С. Современные подходы к построению систем платного доступа учета автотранспорта// Алгоритмы безопасности. 2005. -№6. - С. 63-70.

133. Борисов А.В., Куриленко И.Е. О современных подходах к построению систем учета автотранспорта. Программные и аппаратные средства. // Информационные технологии моделирования и управления. 2005. №5. С. 786-794.

134. Абрамов А., Никулин О., Петрушин А. Системы управления доступом. -М.: Оберег-РБ, 1998 190 С.

135. Борисов А.В., Куриленко И.Е. Модель временных рассуждений в распределенной системе платного доступа автотранспорта // Сборник научных трудов конференции МФИ 2005. С. 20-32.

136. Борисов А.В., Куриленко И.Е. Применение управляемой программной архитектуры при разработке систем автоматизации парковочных комплексов // Международный форум информатизации 2007. С. 35-38.

137. Варшавский П.Р., Еремеев А.П. Поиск решения на основе структурной аналогии для интеллектуальных систем поддержки принятия решений // Изв. РАН. Теория и системы управления. № 2. - 2005. - С. 97-109.

138. Варшавский П.Р. Применение метода аналогий в рассуждении на основе прецедентов для ИСППР // 9 Национальная конференция по искусственному интеллекту КИИ-2004. Труды в Зх томах. Т.1. М.:Физматлит, 2004, С. 218226.

139. VilainM., Kautz Н., van Beek P. Constraint propagation algorithms for temporal reasoning: a revised report. // In Readings in Qualitative Reasoning about Physical Systems, pages 373-381, Morgan Kaufmann, San Mateo, CA, 1990.

140. Schwalb E.M., Dechter R. Coping with disjunctions in Temporal Constraint Satisfaction Problems, In Proc. AAAI-93, 127-132,1993.

141. Искусственный интеллект, справочник в 3-х томах. М.: Радио и связь, 1990, под ред. Захарова В.Н. и Хорошевского В.Ф.

142. Henschen L., Wos L. Unit refutations and Horn Sets. // Journal of the Association for Computing Machinery (ACM), № 21, 1974. Pp. 590-605.

143. Вагин В.Н. НЕ-факторы знания и нетрадиционные логики // Сборник научных трудов III международной школы-семинара по искусственному интеллекту для студентов и аспирантов (Браславская школа'99). Минск: БГУИР, 1999.-С.10-14.

144. Вагин В.Н. Знание в интеллектуальных системах // Новости искусственного интеллекта. 2002. - №6. - С. 8-18.

145. Krzysztof R., Monfroy Е. Constraint programming viewed as rule-based programming I I Theory and Practice of Logic Programming, Vol. 1 (Issue 6), 2001, Pp. 713-750.