Содержание к диссертации
Введение
ГЛАВА 1. Моделирование временных рассуждений в интеллектуальных системах 15
1.1. Области применения временного вывода 15
1.2. Способы представления информации о времени 20
1.3. Неявное моделирование времени 21
1.4. Явное моделирование времени 23
1.5. Временные расширения сетей Петри 25
1.6. Модальные временные логики 27
1.7. Модели времени на основе парадигмы согласования ограничений 36
1.7.1. Качественная точечная модель времени 39
1.7.2. Интервальная модель времени 46
1.7.3. Точечно-интервальная качественная модель времени 48
1.7.4. Проблема временной неперекрываемости 49
1.7.5. Точечная метрическая модель времени 52
1.7.6. Качественная алгебра 55
1.7.7. Выбор формализма для построения системы временных рассуждений 57
1.8. Выводы по главе 1 59
ГЛАВА 2. Алгоритмы решения задач временного вывода 60
2.1. Временная логика TLM 60
2.2. Построение процедур вывода для временной логики TLM 63
2.3. Решение качественных точечных ЗСВО 64
2.3.1. Решение задачи АТ 67
2.3.2. Решение задачи МИМ 68
2.3.3. Алгоритм проверки согласованности 69
2.3.4. Решение задачи QUERY 73
2.3.5. Вычисления всех выполнимых ограничений 80
2.3.6. Сравнение вычислительной сложности ВРА, СРА и РА 82
2.4. Решение дизъюнктивных ЗСВО 83
2.4.1. Базовые алгоритмы решения ограниченных дизъюнктивных ЗСВО 84
2.4.2. Алгоритмы сокращения пространства поиска при решении ограниченных дизъюнктивных ЗСВО 90
2.4.3. Решение дизъюнктивных ЗСВО 94
2.5. Улучшенные алгоритмы решения единичных ЗСВО 97
2.6. Пошаговые алгоритмы решения ЗСВО 101
2.6.1. Алгоритмы предотвращения полного повторного решения единичных ЗСВО 102
2.6.2. Пошаговое решение дизъюнктивных ЗСВО 108
2.6.3. Пошаговые алгоритмы решения единичных ЗСВО ПО
2.7. Решение интервальных и точечно-интервальных ЗСВО 114
2.7.1 Решение интервальных ЗСВО 115
2.7.2. Представление ограничений временной неперекрываемости. 118
2.7.3. Решение точечно-интервальных ЗСВО 119
2.8. Обработка метрической информации 120
2.9. Качественная алгебра 122
2.10. Выводы по главе 2 123
ГЛАВА 3. Реализация системы временных рассуждений 126
3.1. Требования к СВР 126
3.2. Базовые принципы реализации СВР 128
3.3. Язык представления временных ограничений 130
3.4. Программная реализация СВР 132
3.5. Графический редактор сетей временных ограничений 143
3.6. Интеграция СВР со средой CLIPS 148
3.7. Экспериментальное исследование алгоритмов 152
3.7.1. Методика проведения экспериментов и анализа результатов 153
3.7.2. Результаты экспериментов 153
3.8. Выводы по главе 3 162
ГЛАВА 4. Практическое применение СВР 164
4.1. Назначение интеллектуальной системы управления парковками. 164
4.2. Элементы предметной области 166
4.3. Реализация ИС УП 169
4.4. Решение задачи анализа аварийных ситуаций 172
4.5. Выводы по главе 4 176
Заключение 177
Список литературы
- Способы представления информации о времени
- Построение процедур вывода для временной логики TLM
- Базовые принципы реализации СВР
- Элементы предметной области
Введение к работе
В диссертационной работе исследованы и реализованы методы и программные средства временного (темпорального) вывода для интеллектуальных систем (ИС) типа ИС поддержки принятия решений (ИСППР).
На базе полученных результатов предложена расширяемая архитектура и выполнена программная реализация системы временного вывода (временных рассуждений) (СВР), предназначенной для использования в составе современных ИС, в том числе и ИСППР реального времени (ИСППР РВ).
Реализованная СВР применена в рамках ИС управления крупными пар-ковочными комплексами (ИС УП) при решении задач мониторинга и управления точками доступа, а также задач диагностики аварийных ситуаций.
Актуальность темы исследования.
Исследования проблемы времени, которая, как известно, имеет междисциплинарный характер, активно ведутся достаточно долго - понятие времени и его свойства давно являются предметом научных и философских исследований и занимают в них исключительно важное место. Время является одним из фундаментальных понятий при описании реального мира [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 приложений.
Краткий обзор содержания работы.
В первой главе дается краткий обзор областей применения временного вывода. Производится анализ методов и средств моделирования времени в ИС. Приводится развернутая классификация формальных систем оперирования временем. Для каждого рассмотренного формализма приводятся его дос-
тоинства и недостатки в плане применения в ИС, ориентированных на работу в открытых и динамических ПО. Особое внимание уделяется вычислительной сложности алгоритмов. Из существующих формализмов выбирается наиболее подходящий в качестве основы для конструирования СВР.
Во второй главе определяется временная логика событий. Предлагается метод построения процедур вывода для этой логики. Рассматриваются базовые алгоритмы решения задачи временного вывода, приводятся оценки их вычислительной сложности. Рассматриваются предлагаемые улучшения базовых алгоритмов. Предлагаются алгоритмы пошагового уточнения решения задачи временного вывода по мере поступления новой информации, разработанные с учетом специфики применения в составе ИС, ориентированных на работу в открытых и динамических ПО.
В третьей главе рассматриваются вопросы, связанные с реализацией СВР. Формулируются требования к СВР, рассматриваются базовые принципы реализации СВР. Детализируется внутренняя архитектура СВР и ее функциональные возможности. Вводится язык запросов СВР - TQL (Temporal Query Language). Рассматривается модуль интеграции СВР с инструментальным средством конструирования ИС CLIPS. Приводятся результаты экспериментальных испытаний методов и алгоритмов, рассмотренных в главе 2.
В четвертой главе рассматривается практическое применение СВР в составе ИС УП на примере ИСППР для диагностики аварийных ситуаций и в составе блока управления движением. Формулируются цели внедрения ИС УП, решаемые задачи, особенности ПО. Приводится архитектура ИС УП. Рассматривается набор правил, использующих возможности представления временных зависимостей, применяемый для организации работы ИС УП. Обосновывается важность учета временных характеристик при решении задачи предотвращения злоупотреблений со стороны посетителей и обслуживающего персонала.
В приложения вынесены вспомогательные таблицы и алгоритмы.
Способы представления информации о времени
Рассмотрим классификацию формальных систем оперирования временем (Приложение 1). В качестве критериев классификации будем использовать: способ представления времени; вычислительную сложность; характер представляемой информации - качественная или количественная (метрическая). Современные подходы представления времени и временных зависимостей в программных системах можно разбить на два основных класса - основанные на моделировании изменений во времени и основанные на явном моделировании времени [12]. Для первого класса подходов время представляется неявно посредством моделирования изменений состояний системы во времени, которые рассматриваются как мгновенные снимки мира, не обладающие длительностью.
Явное моделирование времени дает возможность строить «гибкие» формализованные языки, позволяющие осуществлять рассуждения, на основе высказываний, истинностные значения которых приурочены к определенному моменту или интервалу времени и могут с течением времени изменяться [43]. Время представляется явно с учетом его свойств. В этот класс входят различные временные логики. Причем, время может представляться как синтаксически (используются явные средства представления времени), так и семантически (типичными представителями этого подхода являются модальные логики). При явном моделировании времени возникают специфические задачи временных рассуждений [44]: ? поддержка согласованности информации о времени - проверка согласованности БЗ при добавлении в нее новой информации; ? ответы на запросы, касающиеся временных аспектов знаний — от про стого нахождения факта, справедливого в заданный момент времени, до определения, когда некоторое множество утверждений истинно в некоторый момент времени. Далее детально рассмотрим характерных представителей обоих классов.
Основные представители подхода, в котором время моделируется через изменения, - ситуационное исчисление, планирующие системы типа STRIPS и сети Петри (СП).
В ситуационном исчислении вводятся [5]: HOLD — специальный предикат, который истинен, если некое утверждение справедливо в некоторой ситуации; RESULT - функция, возвращающая ситуацию после применения некоторого действия. С помощью HOLD и RESULT задается множество правил. Правила применяются к текущей ситуации и в результате получается новая ситуация. Например, пусть: т - идентификатор мотора; startup - функция, запускающая мотор; shutdown - функция, останавливающая мотор. В этом случае можно определить, например, следующие правила: Vm{HOLD{m,IDLE) з Н О LD {RE SULT {star tup, т), ACTIVE)) «Для любого мотора т в ситуации, если он выключен, в результате действия включения он начнет работать»; Vm {HOLD{т.,ACTIVE) з HOLD{RESULT{shutdown,m),IDLE)) «Для любого мотора т в ситуации, если он работает, в результате действия выключения он выключится».
В STRIPS-системах [45] определяются база фактов (БФ) F={FI ...FJ и база правил R={R],...Rm). БФ задает текущую ситуацию. Каждое правило в базе правил R задает возможное действие по изменению ситуации и представляет СОбоЙ ТрОЙКу Rl= RCond,FdeleteJradd , ГДЄ Rcond - ПреДуСЛОВИЯ; Fdeiet,, множество фактов для удаления из БФ; Fadd множество фактов для внесения в БФ. База правил циклически просматривается до тех пор, пока есть возможность применить к текущей ситуации какое-нибудь правило.
С помощью ситуационного исчисления и STRIPS-систем можно моделировать последовательности событий, однако некоторые сложные типы временных зависимостей (например, конкурирующие события) в них непред-ставимы [46].
Сети Петри - являются аппаратом для моделирования динамических дискретных систем (преимущественно асинхронных параллельных процессов). Основой СП является понятие условно-событийной системы [47]. Компоненты системы и их действия представляются абстрактными событиями. Событие может произойти (реализоваться) один раз, повториться многократно или не произойти ни разу. Совокупность действий, возникающих как реализация событий при функционировании системы, образует процесс, порождаемый этой системой. В общем случае одна и та же система может функционировать в одних и тех же условиях по-разному, порождая некоторое множество процессов [48]. Формально СП определяется как N = Р,Т,1,0 , где: Р - {Р],...,Р„} - конечное множество позиций (или мест), гі 0; Т -{Тi,...,Tи} - конечное множество переходов, А 0; 1:Т- Р - входная функция, сопоставляющая переходу мультимножество его входных позиций (мультимножество - множество, допускающее вхождение нескольких экземпляров одного и того же элемента); О: Т Р - выходная функция, сопоставляющая переходу мультимножество его выходных позиций.
Позиция рЕР называется входом для перехода tET, QcsmpElft). Позиция рЕР называется выходом для перехода tET, еслиpEO(t). Аналогично для каждой позиции р определяются множества ее входных и выходных переходов.
В СП N циркулируют фишки. Их распределение по местам определяется разметкой т:Р- М+, где М+ - множество целых неотрицательных чисел. Начальное распределение фишек задается начальной разметкой то. Изменение внутреннего состояния СП - ее разметки - происходит в результате срабатывания возбужденных переходов.
Построение процедур вывода для временной логики TLM
Для решения задач TLM предлагается осуществлять переход к ЗСВО в точечной алгебре, что позволит использовать базовые полиномиальные алгоритмы решения ЗСВО. Множество ППФ TLM может быть преобразовано в ДЗСВО в точечной алгебре путем сопоставления переменных TLM переменным ДЗСВО и преобразования атомарных формул TLM (Before, After, Equal) в ограничения.
Доказательство истинности формулы TLM сводится к решению задачи PSAT. При этом, если формула TLM не содержит дизъюнктивных ограничений, то доказательство ее истинности может быть сведено к задаче SAT и осуществлено за полиномиальное время.
Для доказательства общезначимости формулы A TLM необходимо доказать противоречие формулы -Л. Для этого формула —Л преобразуется к конъюнктивной нормальной форме, после чего может быть осуществлен переход к ДЗСВО с последующим решением задачи DSAT. Сложность этой задачи существенно выше, чем задачи доказательства истинности, т.к. в случае, если задача EDSAT не имеет решения, а это и требуется доказать, придется проанализировать все возможные сценарии и убедиться, что ни один из них невыполним.
Приведение формулы TLM к минимальному виду (задача ШШ) решается путем перехода к ДЗСВО и решению задачи ШШ в постановке ЗСВО.
Для решения задачи вычисления для любых двух переменных хну ограничений, задаваемых множеством формул TLM, необходимо осуществить переход к ДЗСВО, решить задачи SAT и ШШ, после чего воспользоваться алгоритмами поиска пути на TL-графе для вычисления выполнимого ограничения.
Решение задачи вычисления всех возможных согласованных сценариев основывается на переходе к ДЗСВО и решению задачи ACS.
Таким образом, процедуры вывода в логике TLM могут быть построены на базе алгоритмов решения задач SAT, DSAT, МШ, ACS и QUERY для ДЗСВО в точечной алгебре. Далее рассмотрим базовые алгоритмы решения этих задач и предлагаемые в работе улучшения.
Определение 12. Качественная точечная ЕЗСВО задается как Z=(V,D, BTR,C), где V={Vi,...,Vm} - конечное множество временных переменных, соответствующих моментам времени; D - область значений временных переменных - множество целых чисел; і?ГІ?={=, , , , , } - конечное множество бинарных базовых временных ограничений, С={Су\ Су={гу},ГуЕВТІІ,і т, j m) - конечное множество ограничений, где Су - ограничение над временными переменными Vi и Vj. Каждое ограничение С,у из множества С является точным ограничением. Задача выполнимости SAT состоит в проверке, не противоречат ли ограничения в множестве С.
Будем основывать решение ЕЗСВО на переходе к задаче на графе временных ограничений, в котором вершины соответствуют моментам времени, а связи соответствуют ограничениям.
Определение 13. ТЬРЛ-граф есть G=(W EJS), где W — множество вершин, W0; E={(whlkiWj)\wi,WjEW,li,EL} - множество связей; 1={ , ,Ф} - множество допустимых пометок на ребрах. Каждое ребро (yvhlk,Wj) ТЬРА-графа соединяет пару вершин Wj и Wj. Ребра, взвешенные ограничением или - ориентированные, взвешенные ограничением ф - неориентированные.
С помощью ТЪРЛ-графа можно представить ЕЗСВО и для двух других алгебр временных ограничений - ВРА и СРА, для которых накладываются ограничения на множество возможных меток на ребрах графа (в случае ВРА ={ }; для СРА L={ , }). TL-графы, для которых введены такие ограничения, далее будем называть ТЬВРА-графами и ТЬСРА-графами соответственно.
Будем считать, что каждой вершине wEW в ТЪРА-графе G-(W,E,L) соответствует, по крайней мере, одна переменная vEVточечной ЕЗСВО Z=(V,D, BTR,C). Если какой-либо из вершин графа соответствует более одной переменной, то они являются альтернативными именами для одного и того же момента времени. Ситуация, когда одна и та же переменная соответствует более чем одной вершине, недопустима. Будем считать, что существует функция ju:W- V, которая сопоставляет вершинам ТЬРА-графа из множества W имена временных переменных из множества V. Введем понятия модели и интерпретации ТЬРА-графа.
Определение 14. Интерпретацией ТЬРА-графа G=(W,E,L) называется тройка TJ,R , где Т - упорядоченное множество; LV-+T- функция, такая, что для всех PHPJEP выполнено, что если p(pi)=/x(pj), то I(pj)=I(pj); R:L— T -функция, отображающая каждую метку lEL на ребрах графа G в соответствующее бинарное ограничение R(f) на Т. Моделью TL -графа называется такая интерпретация, для которой справедливо: если (wj,l,w2)EE - ребро в графе G, тогда для всех p„pjEP, таких, что f.i(pl)=wi и ju(pj)=w2, выполняется I(p,)J(pjy ER{l).
Базовые принципы реализации СВР
Прежде чем рассмотреть алгоритм проверки согласованности решающий задачу SAT, рассмотрим структуры данных, которые будут использоваться в этом и последующих алгоритмах. Будем считать последовательность однотипных элементов L=(//,/2,..4) - списком длины п 0. Введем функцию size{L)=n, возвращающую длину списка. Если size(L)=Q, то будем называть L пустым списком и считать, что L=0. Определим для списка L операцию Lub так, что она заносит элемент Ъ в конец списка L. Также введем функцию sort(L,a,b), которая осуществляет сортировку списка L по критерию, задаваемому функцией а и флагом b (если b=true, то результирующая последовательность будет отсортирована по возрастанию значений функции а, иначе -по убыванию). Будем считать, что функция indexof[l,L) - возвращает индекс элемента / в списке L; функция pop(L) - удаляет первый элемент из списка L и возвращает его в качестве результата.
Определим как стек последовательность однотипных элементов S=(si,...s„). Введем функцию size(S)=n, которая возвращает размер стека. Если size(S)=Q, то будем называть 5 пустым стеком и считать, что S=0. Определим на стеке операции: push(S,e), помещающую в начало стека S=(si,...sn) элемент е; pop(S), удаляющую первый элемент из стека S и возвращающую его в качестве результата.
Определение согласованности ТЬРЛ-графа G может быть выполнено за два шага. Первый шаг заключается в определении всех КСС в G без учета связей, взвешенных ограничением ф. Алгоритм определения КСС приведен в Приложении 9, его вычислительная сложность 0(п+ё). Второй шаг заключается в поиске КСС содержащего пару вершин, между которыми существует связь, взвешенная ограничением типа /Є{ , }. Из теор. 1 следует, что TL-граф согласован только тогда, когда такого КСС не существует. Если граф согласован, то каждый КСС может быть свернут в любую из своих вершин w. Все связи, которые покидают или входят в вершины КСС, ассоциируются с этой вершиной. Все связи внутри одного КСС могут быть удалены. Имена переменных вершин этого компонента становятся альтернативными именами для вершины w. Пусть {Si,S2)...,Sb} - множество всех полученных КСС. Связи между Si,S2,...,Sk могут быть определены на основе исходного множества ограничений С как Q;- - ПУЄ5І CVW i,j=l,...,m. Если для какого-либо ребра WESj будет получено пустое ограничение 0, то это свидетельствует о несогласованности [83]. Рассмотрим пример на рис. 8 (а). Представленный граф содержит три КСС: Si = {Vi,V2,V3}, S2={V4,V5}, S3={V6). При вычислении временных ограничений, накладываемых на Sj и S3, будет получено: С13 «- П vss1 Cvw= С24П wes3 Cj4nCjj={ ,=}D{ }n{ ,=}={ }. Обратимся к рис. 8 (б). Ограничение СЦ В КСС Si={V/,V2,V3} приводит к несогласованности. Вычисляем С12 = nve51ci;w=ci/nc/2nc2inc/inc2/nci2={ }n{ =}n{ =}n{ }n{ =}n{ ,=}=0. wes2 (а) согласованное множество времен- (") несогласованное множество вре ных ограничений менных ограничений
Пример работы алгоритма определения согласованности Использование операции пересечения предполагает преобразования ограничений и в дизъюнктивную форму. Этого преобразования можно избежать, если использовать табличную форму операции пересечения для базовых ограничений. Из определения КСС следует, что получаемый после свертки КСС граф является ациклическим и логически эквивалентен исходному ТЪРА-графу. Таким образом, ТЬРА-граф G может быть проверен на согласованность и в случае согласованности может быть свернут в логически эквивалентный ациклический ТЬРА-граф G за время 0(e), где е - число связей в G. Ниже приведен алгоритм проверки согласованности (алг. 6). Алг. 6 заносит в Time-граф по одной вершине для каждого КСС. Затем осуществляется перебор всех активных ограничений (связей) в TL-графе. Если для какой-либо связи (w,/,v), при /Є{ , } на этом этапе выявляется, что вершины ее начала и конца принадлежат одному КСС, то выявлена несогласованность. В противном случае (если вершины начала и конца связи не принадлежат одному КСС), эта связь заносится в Time-граф между вершинами Time-графа, соответствующими КСС вершин начала и конца связи в TL-графе (рис. 9). Алгоритм 6. Алгоритм проверки согласованности Входные данные: G=(W,E,L) - PAL-граф, У = {УІ\УІ = {w ,... wik], wtj Є W] - множество KCC в PAL-графе G.
Исходный граф, содержащий цикл Полученный ациклический граф Рис. 9. Пример работы алгоритма определения согласованности
Алг. 6 может быть улучшен. На этапе создания связи (v,l,w) в Time-графе можно внести улучшение, которое позволит реализовать на этапе преобразования TL-графа в Time-граф первый этап решения задачи поиска минимального представления, заключающийся в обеспечении не более чем одной связи между любой парой вершин. На строках 11-12 алг. 6 создание связи (v,l,w) осуществляется по следующему правилу: Если между вершинами Time-графа v и w не существует связи, то занести связь (v,l,w) в Time-граф, иначе, если уже имеется связь (v,r,w), то заменить г на гП1.
Элементы предметной области
Рассмотрим базовые принципы реализации СВР. Для того чтобы обеспечить простое подключение СВР к более крупным приложениям, она организуется в виде отдельного самостоятельного модуля, который может взаимодействовать с системами-клиентами через интерфейс связи (рис. 20) [117]. В этом модуле сконцентрированы механизмы представления информации о времени и механизмы ее обработки. Интерфейс связи должен в полной мере обеспечивать набор необходимых системе-клиенту возможностей для оперирования временными зависимостями [118]. Стандартизированный протокол взаимодействия -Управление моделями —Конфигурирование Запросы Ответы Клиентское приложение (ИС)
Рис. 20. Базовая схема организации СВР Учитывая опыт предыдущих разработок СВР (системы TimeGraph 2 [119], ІхТеТ [89]), можно констатировать, что внутреннее представление ЗСВО оказывает существенное влияние на быстродействие системы (в частности, на время ответа на запросы) [15]. Как показано в главе 2, эффективной формой для структурного выражения ЗСВО является представление ее в виде графа ограничений, вершины которого соответствуют переменным, а ребра -временным ограничениям [83]. Однако, разрабатываемая СВР должна обеспечивать возможность реализации алгоритмов вывода на основе разных внутренних представлений, чтобы обеспечить достаточно простую возможность выбора алгоритмической базы для конкретного приложения СВР. При этом форма задания временных ограничений и форма подачи запросов со стороны клиентской системы должна оставаться унифицированной, что позволит упростить задачу перехода с одной модели на другую. Эту задачу решает интерфейс связи, обеспечивающий стандартный протокол взаимодействия между ИС и элементами СВР. Рассмотрим предоставляемые им возмож ности. Основные внешние функции СВР можно логически разделить на зависимые и независимые от типа используемой модели времени [112]. К независимым функциям относятся: ? управление моделями в БЗ; ? управление режимом контроля согласованности содержания БД и БЗ (обеспечивается автоматический контроль целостности данных и контроль по запросу систем-клиентов); ? очистка БД и БЗ; ? возможность возврата к последнему согласованному состоянию; ? нахождение согласованного сценария; ? вычисление всех выполнимых ограничений. К зависимым от типа модели времени относятся следующие функции: ? создание временных переменных; ? создание ограничений между двумя временными переменными; ? удаление временных переменных; ? удаление ограничений между временными переменными; ? проверка на существование временной переменной в базе и выдача информации о переменной; ? вычисление выполнимых ограничений между заданной парой временных примитивов.
СВР состоит из двух основных блоков - блока контроля и хранилища -базы моделей (БМ). Блок контроля реализует протокол взаимодействия с ИС и обеспечивает доступ к экземплярам ЗСВО, содержащимся в БМ. Каждая модель в БМ является совокупностью ЗСВО во внутреннем формате и метаданных, содержащих информацию о типе ЗСВО, ее численных характеристиках (например, число ограничений, число переменных и т.д.), ссылку на модуль решения ЗСВО и его настройки. Таким образом, БМ может содержать модели, для которых решение ЗСВО основывается на различной алгоритми ческой базе и внутреннем представлении. При этом клиентские приложения СВР абстрагированы от тонкостей внутренней организации модулей-решателей ЗСВО за счет стандартизированного интерфейса связи и протокола взаимодействия.
Важным элементом стандартного протокола взаимодействия между СВР и ИС является язык темпоральных запросов TQL, разработанный в рамках работ по созданию СВР для ИС РВ. Определена грамматика TQL и реализован интерпретатор TQL. TQL обеспечивает: ? возможность задания ЗСВО в текстовой форме; ? единую форму представления ЗСВО, которая позволяет решать одни и те же задачи при помощи различных решателей. TQL содержит как средства манипулирования темпоральной информацией, так и средства управления СВР. Рассмотрим основные команды TQL: ? CREATE - используется для создания временных примитивов, ограничений, моделей; ? DELETE - используется для удаления временных примитивов, ограничений, моделей; ? QUERY - используется для запросов к СВР; ? TRANSACTION - используется для организации транзакций; ? USING - используется для активации моделей времени; ? CONFIG - используется для установки настроек СВР; ? MAN - используется для получения полнотекстовой справочной информации по командам TQL.
