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

Введение

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

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

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

§ представление и хранение информации о времени и временных зависимостях;

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

§ определение выполнимых ограничений (поиск минимального представления);

§ ответы на временные запросы, касающиеся временных аспектов знаний. Запросы могут быть простыми, связанными с нахождением факта, справедливого в заданный момент времени, и сложными, например, определить, когда некоторое множество утверждений будет истинно в заданный момент времени;

§ управление множествами временных ограничений и обеспечение возможности рассуждений на множестве ограничений (например, установление логической эквивалентности двух ситуаций во времени).

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

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

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

В последнем случае также можно определить приведет ли создание ограничения к появлению КСС или несогласованности, основываясь на правиле - если создается связь (v, l, w) и l{<,}, то КСС будет образован, если существует путь (w, l1, v), l1{<,} и rank(v) rank(w). Если rank(v) > 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.

Размещено на Allbest.ru