Рис. 1. Два типа неявных ограничений «меньше»
Здесь TLPA–граф согласован по путям, если для каждой пары его вершин существует не более одного соединяющего их ребра и для каждой тройки вершин u, v, w ограничение соответствующее связи (u,l,v) не противоречит ограничениям для (u,l1,w) и (w,l2,v), т.е. выполнено условие l∩l1l2≠.
TLPA–граф содержит в себе неявное ограничение < для вершин v и w, если не существует ни одного «<–пути» от v к w и существует либо связь (v,≠,w) и «≤–путь» от v к w, либо связь (t,≠,u) и «≤–пути» (но не «<–пути») от v к u, от u к w, от v к t и от t к w (рис. 1). Явным TLPA–графом для TLPA–графа G называется TLPA–граф, логически эквивалентный исходному графу G и не содержащий неявных ограничений. Согласованный по путям явный TLPA–граф назовем Time–графом.
Из явного TLPA–графа G выводимо ( ), что:
v=w тогда и только тогда, когда v и w альтернативные имена одной и той же вершины;
v<w тогда и только тогда, когда существует «<–путь» от v к w;
v≤w тогда и только тогда, когда существует «≤–путь» от v к w;
v≠w тогда и только тогда, когда существует «<–путь» от v к w, или существует «<–путь» от w к v, или в графе существует связь между v и w взвешенная ограничением ≠.
Если произвести переход от TLPA–графа к Time–графу, то будут решены задачи SAT и MIN [4].
Для решения ДЗСВО осуществляется переход к задаче на дизъюнктивном графе времени (D–Time–графе) с применением алгоритма поиска с возвратами для поиска согласованного сценария (задача DSAT) или сценариев (ACS). D–Time–графом называется пара <G, >, где G=(W,E,L)–Time-граф; ={i|i=(di1,di2,…dik)} – множество дизъюнктивных ограничений, причем i интерпретируется как (di1 di2…diu), dij={(xl,rl,yl)|xl,ylW,rlBTR} – множество точных ограничений. Определим множество ограничений в точечной алгебре M так, что для каждого  i в M входит один из dij i. Будем считать D–Time–граф согласованным, если существует такое множество M, что TLPA–граф G*=(W,EM,L) является согласованным. M назовем реализацией множества дизъюнктивных ограничений для графа G. Для решения задачи DSAT необходимо убедиться в существовании хотя бы одной реализации, для решения задачи ACS – найти все возможные реализации.
Предложено два способа уменьшения сложности ДЗСВО – упрощение задачи и уменьшение размерности задачи для алгоритмов поиска с возвратами. В первом случае вводится ограниченная ДЗСВО (ОДЗСВО), в которой устанавливается ограничение на размер элементов i множества . Во втором случае осуществляется сокращение множества по правилам сокращения пространства поиска [14]. Множество бинарных PA–дизъюнкций уменьшается до его подмножества ' за счет определения противоречий между точными и дизъюнктивными ограничениями. Алгоритм решения задачи DSAT разбивается на три этапа: на первом этапе решается ЕЗСВО Z с получением Time–графа G, на втором – осуществляется сокращение исходного множества дизъюнкций до его подмножества ' , на третьем – применяется алгоритм поиска с возвратами.
В ИСППР, ориентированных на работу в открытых и динамически изменяющихся ПО, часто требуется модифицировать множество временных ограничений. При этом в интервалах между изменениями необходимо выдавать ответы на запросы о согласованности (задача SAT) и вычислять выполнимые ограничения (задача MIN). Кроме того, при решении ДЗСВО требуется периодическое изменение решенной ЕЗСВО, полученной на основе точных ограничений, по мере вычисления дизъюнктивных ограничений. В этой ситуации целесообразно использовать принцип пошагового анализа модификаций, выполняемых в исходной сети временных ограничений, позволяющий сократить ряд этапов решения ЗСВО. Если применять для решения ЗСВО после каждого из m изменений базовые алгоритмы, то сложность вычислений можно оценить величиной O(m), где – сложность решения ЗСВО на одном шаге. В данной работе предлагается способ решения задачи в таких условиях за меньшее время.
Путем πxy=<x0,x1,..xk>из вершины x в вершину y в графе G называется последовательность вершин, в которой x0=x, xk=y и (xi,xi+1)E для всех 0≤i<k. В качестве веса пути примем w(πxy)= , где  – пометка ребра (xi,xi+1). В случае, если при вычислении веса wxy в графе G существует направленная связь (y,l,x), то в качестве wxy принимается ~l. Будем называть путь πxy существенным, если w(πxy)≠U и w(πxy)≠Ø [15].
Определим P – множество всех направленных путей между всеми вершинами в графе G. Число возможных элементов в P не превышает значение e2, где e – число ограничений, входящих в E. Определим: P' – множество существенных путей в графе G, P' P; множество входящих в вершину x путей Lp(x)={πlx|l≠x,πlx P'} и множество выходящих из вершины x путей Rp(x)={πxm|m≠x,πxmP'}. Предложен алгоритм вычисления выполнимого ограничения между временными переменными x и y (алгоритм 1), сложность которого составляет O(max(|Rp(x)|,|Rp(y)|,|Lp(x)|,|Lp(y)|)) при условии, что множества Rp и Lp могут быть вычислены за время O(k), где k константа.
Алгоритм 1. Алгоритм вычисления выполнимого ограничения
|
Входные данные: x,y–моменты времени; P'–множество всех существенных путей.
Выходные данные: выполнимое ограничение для переменных x и y.
01: ForwardPatches ← Rp(x) ∩ Lp(y)
02: RearwardPatches ← Rp(y) ∩ Lp(x)
03: Rxy =
04: Ryx =
05: return Rxy∩Ryx
|
Алгоритмы создания (алгоритм 2) и удаления ограничений строятся так, что они выполняются над множеством существенных путей и что ограничения, которые могут привести к несогласованности, отсекаются на этапе внесения. Сложность алгоритма 2 оценивается величиной O(|Rp(y)||Lp(x)|), требуемый для работы объем памяти – O(e2). В результате работы алгоритма 2 в множество существенных путей заносятся существенные пути, которые образуются в TLPA–графе в результате создания связи (w,l,v). Сложность алгоритма удаления ограничения существенно выше сложности алгоритма 2 и оценивается в худшем случае величиной O(e2). Алгоритмы пошагового уточнения решения построены так, что они позволяют поддерживать в актуальном состоянии множество всех существенных путей на TLPA–графе G, соответствующему ЗСВО, после каждого изменения. В результате может быть получен только согласованный граф.
Основным преимуществом предложенного подхода является то, что после каждого изменения не требуется вызов дополнительных алгоритмов проверки согласованности и вычисления неявных ограничений. Как показывают тесты (рис.2) это позволяет добиться существенной экономии времени.
    
Рис. 2. Экспериментальное сравнение алгоритмов решения ЗСВО
Алгоритм 2. Алгоритм создания ограничений
|
Входные данные: x,y – моменты времени, r – ограничение, r{<,>,≤,≥}; P' – множество всех существенных путей в графе G.
01: r'← Алгоритм 2(x,y,P')
02: if (r'∩r=Ø) return inconsistent // найдена несогласованность
03: if (r' r) return // Существующее ограничение сильнее вносимого
04: foreach (πlxLp(x)) { // Вычисление существенных путей
05: if ((w(πly)≠U)(w(πly)≠Ø)) P' = P'  πly // πly существенный
06: foreach (πymRp(y)) if ((w(πlm)≠U)(w(πlm)≠Ø)) P' = P' πlm }
07: foreach (πymRp(y)) if ((w(πxm)≠U)(w(πxm)≠Ø)) P' = P' πxm
|
3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ СИСТЕМЫ ВРЕМЕННЫХ РАССУЖДЕНИЙ
Обратимся к программной реализации системы временных рассуждений (СВР). Система временных рассуждений должна обеспечивать: представление и хранение информации о времени; поддержку временной согласованности БЗ при добавлении в нее новой информации (задача SAT); решение задачи поиска минимальной ЗСВО (задача MIN); решение задачи поиска согласованного сценария (или всех возможных согласованных сценариев) (задачи DSAT и ACS); проверку истинности временных утверждений [16].
Система временных рассуждений должна достаточно просто конфигурироваться и встраиваться в более крупные приложения, обеспечивать простой переход с одной модели временного вывода на другую, поддерживать как транзакционный (по запросу), так и автоматический режим работы. Для обеспечения простого подключения СВР к более крупным приложениям, она организуется в виде модуля, в котором сконцентрированы механизмы представления и обработки информации о времени [17]. Этот модуль может взаимодействовать с системами–клиентами через интерфейс связи, который в полной мере обеспечивает набор необходимых системе–клиенту возможностей для оперирования временными зависимостями. СВР содержит два основных блока – контроля и базы моделей (БМ). Блок контроля реализует протокол взаимодействия с ИС и обеспечивает доступ к экземплярам ЗСВО, содержащимся в БМ. БМ может содержать модели, для которых решение ЗСВО основывается на различной алгоритмической базе и внутреннем представлении. При этом клиентские приложения СВР абстрагированы от тонкостей внутренней организации модулей–решателей ЗСВО за счет стандартизированного интерфейса связи и протокола взаимодействия.
Рассмотрим структуры данных, применяемые для построения решателей ЕЗСВО, на базе предлагаемых алгоритмов (рис. 3).
Основными компонентами решателя являются: таблица путей, словарь временных переменных, блок транзакций и индексы. Словарь временных переменных хранит соответствие строковых имен переменных числовым кодам. Существенные пути хранятся в таблице путей. Каждый путь представляется в виде записи в таблице и представляет собой совокупность следующих характеристик:
ID – уникальный идентификатор пути (целое число);
S – вершина, в которой начинается путь (целое число);
T – вершины, в которую ведет путь (целое число);
W – вес пути (вещественное число);
L – индекс присоединенного пути слева (–1, если такого пути нет);
R – индекс присоединенного пути справа (–1,если такого пути нет);
P – порождающий путь.
Рис. 3. Компоненты решателя ЕЗСВО
Индексы служат для ускорения поиска по таблице путей (в частности, для ускорения выполнения запроса на поиск всех существенных путей, выходящих из вершины v). Решатель работает по следующей схеме: каждая временная переменная кодируется целым числом, это соответствие помещается в словарь. Для внесения нового ограничения используется алгоритма 2, который заполняет таблицу путей в порядке возрастания идентификатора пути. Стек транзакций служит для поддержки транзакционного режима. В нем хранится целочисленный идентификатор максимального пути, существующего в таблице путей на момент старта транзакции. В данном решателе алгоритмы возврата и фиксации транзакции обладают вычислительной сложностью O(l), где l – некоторая константа. Это вызвано тем, что для возврата необходимо просто удалить из таблицы путей все пути с большим уникальным идентификатором, чем сохраненный в стеке транзакций.
Система временных рассуждений реализована с применением языка C# и Microsoft .NET Framework [18] и является кроссплатформенной. В частности, были осуществлены тесты этой версии СВР на ЭВМ, управляемых ОС MS Windows Vista, ОС Ubuntu Linux, ОС Suse Linux и ОС Mandriva Linux.
4. ЗАКЛЮЧЕНИЕ
Предложенные в работе алгоритмы и соответствующая программная реализация позволяют расширить область применения механизма временных рассуждений на широкий класс современных интеллектуальных систем.
Литература
McCarthy J., Hayes P.J. Some Philosophical Problems from the Standpoint of Artificial Intelligence// Machine Intelligence. – Edinburgh University Press. – 1969. – №4. – P.463-502.
Поспелов Д.А., Кандрашина Е.Ю., Литвинцева Л.В. Представление знаний о времени и пространстве в интеллектуальных системах/ Под ред. Д.А. Поспелова. – М.: Наука, 1986.
Башлыков А.А., Еремеев А.П. Экспертные системы поддержки принятия решений в энергетике/ Под ред. А.Ф. Дьяконова. – М.: МЭИ, 1994.
Gerevini A., Schubert L. Efficient Algorithms for Qualitative Reasoning about Time// Technical report 496, Department of Computer Science, University of Rochester, Rochester, NY, 1993.
Ladkin P.B., Maddux R.D. The Algebra of Constraint Satisfaction Problems and Temporal Reasoning// Technical Report, Crestel Institute, 1988.
Еремеев А.П., Троицкий В.В. Концепции и модели представления времени и их применение в интеллектуальных системах// Новости искусственного интеллекта. – 2004. – №1. – С.6-29.
Fikes R., Nilsson N. STRIPS: a New Approach to the Application of Theorem Proving to Problem Solving// Artificial Intelligence. – 1971. – №2. – P.189-208.
Бестужева И.И., Руднев В.В. Временные сети Петри. Классификация и сравнительный анализ// Автоматика и телемеханика. – 1990. – №10. – С.3-31.
Еремеев А.П., Троицкий В.В. Методы представления временных зависимостей в интеллектуальных системах поддержки принятия решений// Известия РАН. Теория и системы управления. – 2003. – №5. – С.75-88.
Van Beek P., Manchak D. W. The Design and Experimental Analysis of Algorithms for Temporal Reasoning// Journal of Artificial Intelligence Research. – 1996. – №4. – P.1-18.
Broxvall M., Jonsson P. Point Algebras for Temporal Reasoning: Algorithms and Complexity// Artificial Intelligence. – 2003. – Vol.149, №2. – P.464-469.
Allen J.F. Maintaining Knowledge about Temporal Intervals// Communications of the ACM. – 1983. – Vol.26, №11. – P.832-843.
Allen J.F., Hayes P. Moments and Points in an Interval-based Temporal Logic// Computational Intelligence. – 1989. – Vol.5. – P.225-238.
Еремеев А.П., Куриленко И.Е. Реализация механизма временных рассуждений в современных интеллектуальных системах// Известия РАН. Теория и системы управления. – 2007. – №2. – С.120-136.
Куриленко И.Е. Пошаговые алгоритмы временных рассуждений для точечной модели времени// Сборник трудов научной сессии МИФИ–2008. – М.:МИФИ, 2008. – Т.10. – С. 132–133.
Еремеев А.П., Куриленко И.Е. Реализация временных рассуждений для интеллектуальных систем поддержки принятия решений реального времени// Программные продукты и системы. – 2005. – №2. – С.8-16.
Еремеев А.П., Куриленко И.Е. Архитектура подсистемы темпоральных рассуждений для ИСППР РВ// Тезисы докладов 10–й международной научно–технической конференции студентов и аспирантов «Радиоэлектроника, электротехника и энергетика». – М.: МЭИ, 2004. – С. 320-321.
Троельсен Э. Язык программирования C# 2005 и платформа .NET 2.0: Перевод с англ.. – М.: ООО "Издательский дом Вильямс", 2007.
|
