АЛГОРИТМ ПРОВЕРКИ СОГЛАСОВАННОСТИ МНОЖЕСТВА НЕТОЧНЫХ ТОЧЕЧНЫХ ВРЕМЕННЫХ ОГРАНИЧЕНИЙ

 

И.Е. Куриленко

 

(Москва, Московский энергетический институт (Технический университет), Россия)

 

 

 

 

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

 

 

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

 

Информация о времени традиционно представляется в виде временных зависимостей между временными примитивами [2]. В качестве таких примитивов могут использоваться временные моменты, интервалы или и то и другое. Зависимости между временными примитивами трактуются как ограничения на их расположение во времени.

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

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

Задача согласования временных ограничений (ЗСВО) состоит из:

1)     конечного множества m временных переменных V = {,…},

2)     области значений временных переменных - множества D,

3)     конечного числа бинарных временных ограничений C = { |   DxD}, где каждое ограничение  – ограничение между временными переменными  и .

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

Отношения между временными переменными задаются на основе множества базовых временных отношений (BTR) между переменными –  {| DxD}, причем:

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

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

Неточное ограничение между переменными  и  это отношение вида {}, где , k>0 и . {} интерпретируется как . Единичным или точным называется ограничение, которое содержит один дизъюнкт. Задачу определения отношения, справедливого между переменными  и , между которыми задано дизъюнктивное ограничение , называют задачей выявления  неточного отношения. Единичной пометкой ограничения  называется одно из отношений . 

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

Известно, что решение ЗСВО для точечной модели времени с возможностью представления неточной информации является NP-полной задачей. Для проверки согласованности множества неточных точечных временных ограничений обычно используются алгоритмы поиска с возвратами. Будем рассматривать проблему проверки множества точечных ограничений, которое может содержать точные ограничения (T) и бинарные неточные ограничения (D) (PA-дизъюнкции). Известно, что в этом случае производительность алгоритма проверки согласованности может быть увеличена, за счет использования противоречий между точными и неточными временными ограничениями. В этом случае поиск согласующего сценария осуществляется в два этапа:

1)     сокращение пространства поиска с помощью правил анализа PA-дизъюнкций;

2)     выявление неточных отношений с помощью алгоритма поиска с возвратами.

Рассмотрим правила анализа PA-дизъюнкций [4]. Обозначим через T – исходное множество точных временных ограничений, а через Q-множества PA-резольвент. Приведенные ниже правила  должны быть проверены для каждой PA-дизъюнкции D(i) в множестве PA-дизъюнкций D.

 

(1)	Выводимость (T-derivability) Если  или , то дизъюнкция  может не включаться в множество поиска D`.
(2)	Тавтология (T-tautology) a) Если добавление в T ограничения приводит к тому, что из T следует , то дизъюнкция  может не включаться в множество поиска D`. b) Если добавление в T ограничения приводит к тому, что из T следует , то дизъюнкция  может не включаться в множество поиска D`.
(3)	Резолюция (T-resolution) a) Если добавление  в T ограничения  не нарушает его согласованности, а добавление  в T ограничения  нарушает его согласованность, то исключить дизъюнкцию  из множества поиска D`. Добавить  в множество Q. б) Если добавление  в T ограничения не нарушает его согласованности, а добавление  в T связинарушает его согласованность, то исключить дизъюнкцию  из множества поиска D`. Добавить  в множество Q. в) Если внесение в T ограничения нарушает его согласованность и добавление  в T связи нарушает его согласованность, то исходное множество ограничений несогласованно.

 

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

 

(4)

D Пусть  отношение между моментами времени x и y, следуемое из множества T (). Аналогично  - . Если  сильнее  или  сильнее , то D(i) может быть исключена из множества D. Если =Ø и Ø, то D(i) должна быть исключена из множества D, {} должно быть добавлено к множеству Q. Если Ø и =Ø, то D(i) должна быть исключена из множества D, {} должно быть добавлено к множеству Q. Если =Ø и =Ø, то задача не имеет решения.

 

Алгоритм, построенный на основе этого правила, итеративно сокращает пространство поиска. На практике он показал лучшие результаты, чем алгоритм [4], основанный на применении правил (1)-(3) и был включен в состав прототипа  СВР для ИСППР РВ на базе нетрадиционных логик разрабатываемой научной группой кафедры ПМ МЭИ под руководством Еремеева А.П.

 

 

ЛИТЕРАТУРА

1.        Поспелов Д.А., Литвинцева Л.В «Представление знаний о времени и пространстве в интеллектуальных системах». - Под редакцией Д.А. Поспелова. – М.: Наука, 1986. 

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

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

4.        Gereveni 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.