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

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

Представление времени и темпоральных (временных) зависимостей необходимо для решения основных задач ИСППР РВ. Для систем этого типа требуется мощный механизм временных рассуждений, базирующийся на достаточно выразительной модели времени [Еремеев и др., 2003, 2005]. Это вызвано тем, что при решении задач диагностики, мониторинга, планирования, прогнозирования, управления, обучения, для решения которых создается ИСППР РВ, требуется представлять и обрабатывать множество параметров, изменяющихся со временем [Вагин и др., 2001]. По сути, рассуждения с учетом фактора времени (временные рассуждения) должны использоваться во всех основных блоках ИСППР РВ, включая базы данных и знаний. Системный подход к построению сложных программных комплексов требует выделения СВР как самостоятельной подсистемы в составе ИС. Это позволяет избежать дублирования программного кода за счет его повторного использования в других компонентах системы.

Из-за обширности применения механизма временных рассуждений возникает требование простоты интеграции и управления СВР. Она должна достаточно просто встраиваться в более крупные приложения (ИС) и обеспечивать гибкое управление выразительностью представления временных зависимостей, а также возможность настройки этой выразительности под конкретную предметную область (ПО). СВР должна поддерживать как транзакционный, так и автоматический режимы функционирования. В транзакционном режиме проверка согласованности темпоральных данных осуществляется по запросу; в автоматическом режиме — после каждого изменения информации. СВР должна обеспечивать также возможность автоматического возврата к последнему согласованному состоянию базы данных (БД) и/или базы знаний (БЗ) в случае выявления ошибки согласованности за минимально возможное время. В целом СВР в составе ИС должна обеспечивать решение следующих задач [Еремеев и др., 2005]:

• § представление и хранение информации о времени и временных зависимостях;
• § поддержка временной согласованности — проверка согласованности БД и БЗ при добавлении в них новой информации. В случае несогласованности необходимо локализовать подмножество утверждений, вызывающих несогласованность;
• § определение выполнимых ограничений (поиск минимального представления);
• § ответы на временные запросы, касающиеся временных аспектов знаний. Запросы могут быть простыми, связанными с нахождением факта, справедливого в заданный момент времени, и сложными, например, определить, когда некоторое множество утверждений будет истинно в заданный момент времени;
• § управление множествами временных ограничений и обеспечение возможности рассуждений на множестве ограничений (например, установление логической эквивалентности двух ситуаций во времени).

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

Основные определения и алгоритмы. Обычно множество временных примитивов и отношений между ними представляется в виде задачи согласования временных ограничений (ЗСВО), являющейся конкретизацией более общей задачи согласования ограничений (ЗСО) [Еремеев и др., 2003]. Это позволяет использовать для решения ЗСВО методы, применяемые для ЗСО. Кроме того, известно, что такое представление более предпочтительно с точки зрения эффективности алгоритмов вывода.

В работе [Еремеев и др., 2005] показано, что исходя из требований эффективности, в рамках ИСППР РВ предпочтительнее использование точечных моделей времени (BPA, CPA, PA) либо полиномиальных подклассов интервальной модели (CIA, ORD-Horn).

Для решения ЗСВО множество временных переменных и отношений между ними преобразуется в граф, взвешенный временной информацией. Граф, взвешенный временной информацией G=(V, E), далее TL-граф, это граф содержащий, по крайней мере, одну вершину (V) и набор взвешенных ребер (w, l, v)E. Ребра в TL-графе могут быть ориентированными и взвешенными отношениями < или и неориентированными. Неориентированные ребра представляют собой связи взвешенные отношениями = или. Таким образом, l{}.

Интерпретацией TL-графа G называется тройка, где: T — упорядоченное множество; I — функция, такая, что для всех, P выполнено, что если () =(), то I () = I (); R — функция, отображающая каждую метку l на ребрах графа G в соответствующее бинарное отношение R (l) на T.

Моделью TL-графа G называется такая интерпретация, при которой если — ребро в графе G, тогда для всех, P, таких, что ()=и ()=, выполняется R (l). TL-граф согласуем (непротиворечив), если он имеет по крайней мере одну модель. Два или более TL-графа логически эквивалентны, если обладают одними и теми же моделями.

Решение задачи временных рассуждений основывается на преобразовании TL-графа в Time-граф. TL-граф содержит в себе неявное отношение < между вершинами и, если не существует ни одного <-пути от к и существует либо ребро, взвешенное отношением ипуть от к, либо две вершины t и u, между которыми есть ребро, помеченное отношением, и существуют пути (но не <-пути) от к u, от u к, от к t и от t к. Явным TL-графом для TL-графа G называется TL-граф, логически эквивалентный исходному графу G и не содержащий неявных отношений. Известно, что из явного TL-графа следует, что:

• § = тогда и только тогда, когда и альтернативные имена одной и той же вершины;
• § < тогда и только тогда, когда существует <-путь от к ;
• § тогда и только тогда, когда существуетпуть от к ;
• § тогда и только тогда, когда существует <-путь от к, или существует <-путь от к, или в графе существует связь между и, взвешенная отношением [Gereveni at al., 1993].

Графом времени (Time-графом) является явный TL-граф, распадающийся на набор временных цепей, причем каждая вершина может принадлежать одной и только одной временной цепи. Если произвести переход от TL-графа к Time-графу, то будут автоматически решены задачи выполнимости и выявления всех выполнимых ограничений.

При обработке неточной информации после решения задачи для множества точных ограничений используются алгоритмы поиска с возвратами для обработки множества неточных точечных ограничений D = {D (i) :}. Дизъюнктивным графом времени называется пара (T, D), где T — Time-граф и D — набор бинарных дизъюнкций в точечной алгебре. Элементы множества D — (x, y, z, w — временные переменные, -отношения, i=1.n. Реализацией множества бинарных дизъюнкций D для Time-графа T называется множество отношений в точечной алгебре M, в которое входят по одному дизъюнкту из каждой бинарной дизъюнкции множества D, а Time-граф получаемый дополнением T отношениями из M является согласованным.

Дизъюнктивный Time-граф согласован тогда и только тогда, когда существует реализация множества бинарных дизъюнкций D для Time-графа T. Дизъюнктивный Time-граф называется явным, если он согласован и не содержит неявных отношений. Для получения явного дизъюнктивного time-графа необходимо определить реализацию множества бинарных дизъюнкций D для графа T. В общем случае, для решения этой задачи для k дизъюнкций в множестве D необходимо проверить в худшем случае возможных вариантов реализаций. Такая проверка может быть выполнена за экспоненциальное время, а определение согласованности дизъюнктивного Time-графа является NP-полной задачей. Поэтому для поиска решения будем использовать модификацию алгоритмов поиска с возвратами.

Рассмотрим возможность увеличения производительности СВР, построенной на базе качественной точечной модели времени на основе алгоритмов, приведенных в работах [Gereveni at al., 1993, Еремеев и др., 2003, 2005]. В некоторых ИСППР РВ, ориентированных на работу в динамических предметных областях, требуется частая модификация множества временных ограничений. При этом в интервалах между изменениями от СВР требуются ответы на запросы о согласованности и на выполнимое ограничение между заданной парой временных примитивов. Примером такого использования СВР являются планировщики, которые используют информацию о времени. Алгоритмы, на основе которых они построены, при выборе очередного варианта действия для занесения в план осуществляют проверку на временную согласованность.

Производительность СВР может быть увеличена за счет:

• § сокращения временных затрат на переход от TL-графа к Time-графу;
• § применения пошаговых алгоритмов решения задачи для динамически изменяющегося множества временных ограничений;
• § сокращения размерности задачи для алгоритмов поиска с возвратами, использование решения полученного для множества точных ограничений при поиске решения для множества неточных ограничений;
• § оптимизации под наиболее частотные запросы.

Рассмотрим алгоритмы, позволяющие избежать полного повторного решения задачи для измененного множества временных ограничений за счет анализа изменений выполняемых в исходном множестве. Рассмотрим пример (рис. 1), на котором приведен TL-граф и соответствующий ему Time-граф, а также модифицированный TL-граф.

Предположим, что исходный TL-граф был модифицирован. Были внесены ограничения (V4 V2) и (V3 V7). Ясно, что логическая модель в результате этой модификации не поменяется, однако, при использовании базового алгоритма [Gereveni at all, 1993], СВР после завершения транзакции очистит Time-граф и повторит все этапы решения ЗСВО для измененной сети временных ограничений. Принцип пошаговой модификации состоит в использовании существующего Time-графа для анализа изменений с целью сокращения ряда этапов решения ЗСВО.

Рис. 1. Пример TL-графов и Time-графа Введем для TL-графа две характеристики: isconsistent — указывающую, согласовано ли множество временных ограничений, представленных TL-графом, и ischanged — указывающую, изменялось ли множество временных ограничений, представленных TL-графом. На рис. 2 приведен алгоритм создания нового временного ограничения, использующий информацию о существующих временных ограничениях и введенные характеристики.

Предварительно отслеживается ситуация, когда изменение TL-графа не может затронуть Time-граф (эквивалентность моментов времени, на которые накладывается ограничение). В случае, когда моменты времени не эквивалентны, то новое ограничение может привести к образованию компонента сильной связности (КСС), что, в свою очередь, требует сверки вершин, входящих в КСС, в одну и повторения всех этапов построения графа времени. Однако, ограничение не приводит к образованию новых КСС и необходимо просто вызвать алгоритмы выявления неявных ограничений; если создается ограничение типа =, то это приводит к слиянию объединяемых вершин в одну; в противном случае создается одно из ограничений — {,}.

Рис. 2. Алгоритм создания нового ограничения (v, l, w).

В последнем случае также можно определить приведет ли создание ограничения к появлению КСС или несогласованности, основываясь на правиле — если создается связь (v, l, w) и l{<,}, то КСС будет образован, если существует путь (w, l1, v), l1{ rank (w), то КСС не может быть образован исходя из свойств Time-графа и необходимо вызвать алгоритм определения nextgreater-связей.

Аналогичным образом может быть построен алгоритм удаления временных ограничений. Очевидно, что если множество временных ограничений S согласованно, то удаление элемента из S не может привести к несогласованности. Однако удаление временных ограничений может привести к распаду КСС, изменению рангов и временных цепей. Тем не менее, при удалении определенных типов связей можно предсказать последствия этого изменения. Например, при удалении связи, взвешенной отношением, необходимо удалить автоматически созданные ребра, вернуть удаленные в процессе выявления данного ограничения ребра и обновить nextgreater-связи. Предположим, что из TL-графа удаляется связь, взвешенная отношением l {,}, вершины которой принадлежат разным КСС. В этом случае не будут нарушены согласованность и КСС, но могут быть нарушены временные цепи и ранги. Однако, если эти вершины принадлежат одной временной цепи, то можно отследить ситуацию, когда не будут нарушены ни ранги, ни временные цепи. В этой ситуации если тип удаляемого ограничения — <, то необходимо осуществить обновление связей, иначе () связь может быть удалена, а логическая модель графа не поменяется. темпоральный компьютерный интеллектуальный В случае, когда удаляется связь, вершины которой принадлежат одному КСС, необходимо проверить приводит ли ее удаление к распаду КСС и изменению логической модели графа.

Алгоритмы создания и удаления моментов времени проще по сложности и реализации соответствующих алгоритмов для связей и здесь не приводятся. Отметим, что создание нового момента времени не может повлиять на согласованность и не требует повторного выполнения шагов преобразования TL-графа в Time-граф. При удалении момента времени ситуация несколько сложнее, так как удаление момента вызывает каскадное удаление всех временных ограничений, в которых он фигурирует. Но и в этом случае повторное выполнение преобразований необходимо не всегда. Так, если момент не участвует в ограничениях, то он может быть удален из модели без нарушения согласованности; в противном случае необходимо проверить, выходят ли эти ограничения за пределы КСС и не приведет ли их удаление к распаду КСС.

Заключение

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

Реализованная СВР зарегистрирована в реестре Федеральной службы по интеллектуальной собственности, патентам и товарным знакам. В настоящее время разрабатываются дополнительные модули СВР, упрощающие ее работу с интервальной и интервально-точечной моделями времени, а также, модуль оперирования метрической информацией.

• 1. Поспелов и др., 1986 Поспелов Д. А., Литвинцева Л. В Представление знаний о времени и пространстве в интеллектуальных системах / Под ред. Д. А. Поспелова. — М.: Наука, 1986.
• 2. Вагин и др., 2001 Вагин В. Н., Еремеев А. П. Некоторые базовые принципы построения интеллектуальных систем поддержки принятия решений реального времени.// Изв. РАН. Теория и системы управления, 2001, N6, с.114−123.
• 3. Gereviny et al., 1993 Gereviny A. and Schubert L. Efficient Algorithms for Qualitative Reasoning about Time. Technical report 496, Department of Computer Science, University of Rochester, Rochester, NY, 1993.
• 4. Еремеев и др., 2003 Еремеев А. П., Троицкий В. В. Модели представления временных зависимостей в интеллектуальных системах поддержки принятия решений // Изв. РАН. Теория и системы управления, 2003, № 5, с.75−88
• 5. Еремеев и др., 2005 Еремеев А. П., Куриленко И. Е. Реализация временных рассуждений для интеллектуальных систем поддержки принятия решений реального времени // Программные продукты и системы 2005, № 2, с.4−16
• 6. Борисов и др., 2005 Борисов А. В., Куриленко И. Е. Модель временных рассуждений В распределенной системе УЧЕТА автотранспорта // ИТМУ 2005, № 5, с 786−794.