Пошаговые алгоритмы временных рассуждений для точечной модели времени

И. Е. КУРИЛЕНКО

Московский энергетический институт (технический университет)

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

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

Разработка систем временных рассуждений (СВР), реализующих механизм временных рассуждений, решающе важна для современных интеллектуальных систем [1]. О важности наличия средств представления времени и временных (темпоральных) зависимостей (в данных и знаниях) в ИС говорится практически с момента появления таких систем (см., например, работы [1]). Многие базовые понятия, такие как «изменение», «причина», «следствие» и отношения между ними описываются в терминах времени. Однако особенно актуальной проблема построения формальных систем оперирования темпоральной информацией встала именно в связи с появлением и развитием ИС, ориентированных на открытые и динамические предметные области (ПО), которые в процессе своего функционирования оперируют с большим количеством информации (данных и знаний) изменяющихся со временем. Для таких ИС требуется наличие средств для частой модификация множества временных ограничений. При этом в интервалах между изменениями необходимо выдавать ответы на запросы о согласованности и выполнимости ограничений между заданной парой временных примитивов [2]. В этой ситуации целесообразно реализовать принцип пошагового изменения, позволяющий сократить ряд этапов решения задачи [2]. Актуальность исследования обусловлена тем, что в настоящее время отсутствуют развитые средства представления временных зависимостей в современных средствах конструирования ИС, а большинство из нескольких существующих программных реализаций прототипов СВР являются исследовательскими инструментами, интеграция которых в промышленные ИС является затруднительной. При этом вопрос построения пошаговых алгоритмов временных рассуждений плохо освещен в мировой литературе. Пусть G=(V,E) – ориентированный граф, с пометками на ребрах l={<,≤}. Путь πxy=<x0,x1,..xk>из вершины x в вершину y в графе G есть последовательность вершин, в которой x0=x, xk=y и (xi,xi+1)ϵE для всех 0≤i<k. В качестве веса пути примем , где - пометка ребра (xi,xi+1). Определим как P множество всех направленных путей между всеми вершинами в графе G. |P| = e2, где e – число ограничений, входящих в E. Определим две функции Lp и Rp как: Lp(x)={ πlx : l≠x, l≠y, πlxϵP}; Rp(y)={ πym : m≠x, m≠y, πymϵP}

С помощью данных функций для вершины v можно определить какие пути в нее входят и какие пути из нее выходят. Если в множество P входят все пути между всеми вершинами, то алгоритм вычисления выполнимого ограничения (QueryRelation) между переменными x и y содержит следующие шаги:

1)  ForwardPatches ← Rp(x) ∩ Lp(y) ; RearwardPatches ← Rp(y) ∩ Lp(x)

2)  Rxy = ; Ryx =

3)  return Rxy ∩Ryx

Вычислительная сложность данного алгоритма O(max(|Rp(x)|, |Rp(y)|, |Lp(x)| ,|Lp(y)|)). Для внесения нового ограничения (x r y) в множество P может быть использован следующий алгоритм:

if (QueryRelation(x, y) ∩ r == Ø) return inconsistent;

else {

foreach (πlxϵ Lp(x)) { P = P U πly

foreach (πymϵ Rp(y)) P = P U πlm

}

foreach (πymϵ Rp(y)) P = P U πxm

}

Вычислительная сложность данного алгоритма O(|Rp(y)|×|Lp(x)|). При этом объем памяти требуемый для работы алгоритмов составляет O(e2). Согласованность проверяется на этапе внесения информации. Применение этих алгоритмов позволяет значительно увеличить производительность СВР для систем ориентированных на работу в открытых и динамических ПО.

Список литературы

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

2.  , «Реализация механизма временных рассуждений в современных интеллектуальных системах»– М.: Изв. РАН «Теория и системы управления» №2. 2007. С. 120-136.