И. Е. КУРИЛЕНКО
Московский энергетический институт (технический университет)
ПОВЫШЕНИЕ БЫСТРОДЕЙСТВИЯ АЛГОРИТМОВ ВРЕМЕННЫХ РАССУЖДЕНИЙ ДЛЯ КАЧЕСТВЕННОЙ ТОЧЕЧНОЙ МОДЕЛИ ВРЕМЕНИ
Рассматривается проблема увеличения быстродействия систем временных рассуждений, входящих в состав интеллектуальных систем ориентированных на работу в динамических предметных областях.
Разработка систем временных рассуждений (СВР), реализующих механизм временных рассуждений, решающе важна для современных интеллектуальных систем [1, 2, 3]. Для реализации этого механизма необходимо формализовать понятие времени и обеспечить возможность представления и рассуждения о временных аспектах знаний. СВР, соответственно, должна предоставлять:
1) средства представления информации о времени (которые должны позволять описывать, что истинно или ложно во времени);
2) механизм манипулирования информацией о времени (обеспечивающий проверку истинности любого временного утверждения).
Традиционно информация о времени представляется в виде временных зависимостей между временными примитивами. Зависимости между временными примитивами трактуются как ограничения на их реальное время появления. Основной целью временных рассуждений является порождение выводов из множества временных ограничений (а это могут быть в основном новые временные ограничения для непротиворечивых входных множеств) [2]. Обычно множество временных примитивов и отношений между ними представляется в виде задачи согласования временных ограничений (ЗСВО). Это позволяет использовать в решении задач временных рассуждений методы, применяемые для решения ЗСО. Кроме того, известно, что такое представление выгодно с точки зрения эффективности алгоритмов.
В некоторых приложениях, ориентированных на работу в динамических предметных областях (например, ИСППР РВ), требуется частая модификация множества временных ограничений (МВО). При этом в интервалах между изменениями от СВР требуется ответы на запросы о согласованности и на выполнимое ограничение между заданной парой временных примитивов. Также примером такого использования СВР могут послужить планировщики, которые используют информацию о времени. Алгоритмы, на основе которых они построены, при выборе нового шага для занесения в план осуществляют проверку, не приводит ли он к временной несогласованности. Для таких приложений может быть недостаточно механизма транзакций, который должна реализовывать СВР. Для повышения быстродействия механизма временных рассуждений в таких приложениях в СВР, основанную на базе качественной точечной модели времени, были добавлены алгоритмы использующие полученное решение ЗСВО для исходного МВО в качестве опоры для решения ЗСВО для расширенного МВО. Основным преимуществом этих алгоритмов является то, что они позволяют сократить ряд этапов решения ЗСВО и тем самым уменьшают требуемое для решения время.
При модификации МВО предварительно отслеживается ситуация, когда изменение TL-графа не может затронуть Time-граф (например, эквивалентность моментов времени, на которые накладывается новое ограничение). Число вершин в Time-графе может измениться в случае, если изменение приводит к изменению числа компонент сильной связности (КСС) в TL-графе. Существует тип ограничения, который не приводит к образованию новых КСС – {
}. В случае его создания или удаления необходимо просто вызвать алгоритмы выявления неявных ограничений. Создание ограничения {=} приводит к слиянию объединяемых вершин в одну. В случае создания одного из ограничений {<},{
},{>},{
} также можно определить приведет ли это к появлению КСС или несогласованности, основываясь на правиле: если создается связь (v l w) и l
{<,}, то КСС будет образован, если существует путь (w l1 v), l1{<,} и rank(v) rank(w) (где rank(v) – псевдовремя вершины v). (В случае, когда rank(v) > rank(w), КСС не может быть образован исходя из свойств Time-графа).
Список литературы
1. Представление знаний о времени и пространстве в интеллектуальных системах / Под редакцией . М.: Наука, 1986.
2. , Еремеев базовые принципы построения интеллектуальных систем поддержки принятия решений реального времени // Изв. РАН. Теория и системы управления. 2001. № 1.
3. , Еремеев системы поддержки принятия решений в энергетике. М.: Издательство МЭИ, 1994.
4. Gereviny A. and Schubert L. Efficient Algorithms for Qualitative Reasoning about Time. Technical report 496, University of Rochester, Rochester, NY, 1993.
