Рассмотрение современного подхода к моделированию темпоральных (временных) рассуждений в интеллектуальных системах. Определение значения разработки компьютерных систем временных рассуждений. Ознакомление с алгоритмом создания нового ограничения.
Аннотация к работе
Повышение эффективности алгоритмов вывода для системы временных рассуждений Приводятся методы повышения эффективности алгоритмов вывода для системы временных рассуждений построенной на основе точечной модели времени и предназначенной для интеллектуальных систем поддержки принятия решений реального времени (ИСППР РВ).Это вызвано тем, что при решении задач диагностики, мониторинга, планирования, прогнозирования, управления, обучения, для решения которых создается ИСППР РВ, требуется представлять и обрабатывать множество параметров, изменяющихся со временем [Вагин и др., 2001]. Информация о времени представляется в виде временных зависимостей между временными примитивами (моментами, интервалами или и теми и другими). Решение задачи временных рассуждений основывается на преобразовании TL-графа в Time-граф. Реализацией множества бинарных дизъюнкций D для Time-графа T называется множество отношений в точечной алгебре M, в которое входят по одному дизъюнкту из каждой бинарной дизъюнкции множества D, а Time-граф получаемый дополнением T отношениями из M является согласованным. Дизъюнктивный Time-граф согласован тогда и только тогда, когда существует реализация множества бинарных дизъюнкций D для Time-графа T.В работе затронуты общие принципы построения СВР с учетом требований современных ИС, ориентированных на работу с динамическими ПО, типичным представителем которых является ИСППР РВ. Рассмотрены задачи СВР, вопрос программного представления информации о времени, а также приведены эффективные алгоритмы преобразование временных ограничений в данное представление и решения ЗСВО.
Введение
Разработка компьютерных систем временных рассуждений (СВР), обеспечивающих явное представление времени как особой субстанции, решающе важна для современных интеллектуальных систем (ИС) [Поспелов и др., 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 { 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.