ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 2, с. 120-136
= ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ
УДК 007:519.816
РЕАЛИЗАЦИЯ МЕХАНИЗМА ВРЕМЕННЫХ РАССУЖДЕНИЙ В СОВРЕМЕННЫХ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМАХ*
© 2007 г. А. П. Еремеев, И. Е. Куриленко
Москва, МЭИ (технический ун-т) Поступила в редакцию 18.07.06 г.
Рассматривается современный подход к моделированию темпоральных (временных) рассуждений в интеллектуальных системах, ориентированных на работу с динамическими предметными областями. Определяются цели, задачи и принципы построения систем временных рассуждений.
Введение. Разработка компьютерных систем временных рассуждений (СВР), обеспечивающих явное представление времени как особой субстанции, очень важна для современных интеллектуальных систем (ИС) [1-3]. Применение СВР позволит добиться качественно нового уровня решения многих задач искусственного интеллекта (ИИ), так как важные для ИИ и его приложений понятия, например, "изменение", "причина", "следствие" и отношения между ними описываются в терминах времени. Явное моделирование времени дает возможность строить гибкие формализованные языки, поддерживающие рассуждения, построенные из высказываний, истинностные значения которых приурочены к определенному моменту или интервалу времени и могут с течением времени изменяться.
Исследования проблемы времени, которая, как известно, имеет междисциплинарный характер, активно ведутся достаточно долго. В рамках ИИ она стала особенно актуальной после появления и развития ИС, ориентированных на работу с динамическими предметными областями (ПО). Системы этого типа, характерным представителем которых являются интеллектуальные системы поддержки принятия решений реального времени (ИСППР РВ) [3], в процессе своего функционирования оперируют с большим количеством информации (данных и знаний), изменяющейся со временем. По сути, рассуждения с учетом фактора времени (временные рассуждения) должны использоваться во всех основных блоках ИСППР РВ, включая базы данных и знаний. Системный подход к построению сложных программных комплексов требует выделения СВР как самостоятельной подсистемы (или модели в базе моделей) в составе ИС. Это позволяет избежать дублирования программного кода за счет его повторного
использования в других компонентах системы.
*
Работа выполнена при финансовой поддержке РФФИ
(проект < 05-07-90232).
Из-за важности и обширности применения механизма временных рассуждений возникает требование простоты интеграции и управления СВР. Она должна достаточно просто встраиваться в более крупные приложения и обеспечивать гибкое управление выразительностью представления темпоральных (временных) зависимостей (возможность настройки выразительности под конкретную ПО (задачу)).
СВР должна поддерживать как транзакцион-ный, так и автоматический режимы функционирования. В транзакционном режиме проверка согласованности темпоральных данных осуществляется по запросу; в автоматическом режиме - после каждого изменения информации.
СВР должна обеспечивать также за минимально возможное время способность автоматического возврата к последнему согласованному состоянию базы данных (БД) и/или базы знаний (БЗ) в случае выявления ошибки согласованности. Для некоторых приложений необходимо учитывать объем требуемой для функционирования системы памяти, в частности, при взаимодействии ИСППР РВ с сетью промышленных контроллеров с дисковой (от 512 Мбайт) и оперативной (от 128 Мбайт) памятью.
В целом СВР в составе ИС ориентирована на решение следующих задач [2, 4]:
представление и хранение информации о времени и временных зависимостях;
поддержка временной согласованности - проверка согласованности БД и БЗ при добавлении в них новой информации. В случае несогласованности необходимо локализовать подмножество порождающих ее утверждений;
определение выполнимых ограничений (поиск минимального представления);
ответы на временные запросы - запросы, касающиеся временных аспектов знаний и распространяющиеся от простого нахождения факта, справедливого в заданный момент времени, до
определения, когда некоторое множество утверждений истинно в один момент времени;
управление множествами временных утверждений и обеспечение возможности рассуждений на множестве ограничений (например, установление логической эквивалентности ситуаций во времени).
Для решения этих задач необходима формализация понятия времени и наличие средств представления и манипулирования информацией о времени (временными зависимостями) в СВР. Средства представления должны позволять описывать требуемые временные зависимости, например: интервал времени X дольше интервала времени У на 15 с, а средства (механизм) манипулирования помогают определить истинность соответствующего временного утверждения или установить выполнимость (согласованность) заданных временных ограничений.
1. Темпоральные (временные) логики. Информация о времени представляется в виде временных зависимостей между временными примитивами (моментами, интервалами или и теми и другими). Эти зависимости трактуются как ограничения на реальное время появления указанных примитивов. Основная цель временных рассуждений состоит в порождении выводов на множестве временных ограничений (в основном это новые временные ограничения для непротиворечивых входных множеств) [1].
Обычно множество временных примитивов и отношений между ними представляется в виде задачи согласования временных ограничений (ЗСВО), являющейся конкретизацией более общей задачи согласования ограничений (ЗСО) [2, 5]. Это позволяет использовать для решения ЗСВО методы, применяемые для ЗСО. Кроме того, известно, что такое представление более выгодно с точки зрения эффективности алгоритмов вывода. ЗСВО определяется следующим образом [2]:
1) V = {У1, У2, ..., Ут} - конечное множество временных переменных;
2) В - область значений временных переменных;
3) конечное число бинарных временных ограничений С = {Су|Су с ВхВ}, где Су - ограничение между временными переменными У и Уу.
Элементы множества V могут интерпретироваться как моменты, интервалы времени или длительности. Область значений переменных В, соответствующих моментам времени и длительностям, представляет собой множество чисел, а для интервальных переменных - множество упорядоченных пар значений.
Отношения между временными примитивами задаются на основе множества базовых временных ограничений, таких, что входящие в него отношения являются взаимно исключающими, а их полное объединение является универсальным ограничением и, которое вообще не накладывает
каких-либо условий. Для представления неточных ограничений между переменными Vi и Уу вводится дизъюнктивная форма временных ограничений У { С у , ..., С {у } Уу, где Су с ВхВ, к > 0 интерпретируемая как (УСу У) у .•• у (УСу У). Точным называется ограничение вида УО/У, содержащее только один дизъюнкт. Задачу определения отношения, справедливого между переменными У и Уу, для которых задано дизъюнктивное ограничение, называют задачей выявления неточного отношения, а само это отношение - единичной пометкой. Решение ЗСВО предполагает нахождение единичной пометки для каждого дизъюнктивного ограничения так, чтобы они не противоречили друг другу.
Отношение Су выполнимо для переменных Vi и Уу тогда и только тогда, когда существует хотя бы одно решение, в котором Су выступает ограничением между ними. Минимальным ограниче-
Сшт
у служит множество, состоящее только из выполнимых отношений между У и Уу. ЗСВО называют минимальной, если все ее ограничения Су - минимальны. Известно [2], что для любой ЗСВО всегда можно найти эквивалентную минимальную или показать несогласованность ограничений.
Основными операциями над временными ограничениями являются:
дополнение (—): —Ьу = П\ Ьу; отрицание (инверсия) (~): ~(гх, ..., гк) = (~гх, ..., ~Гк);
пересечение (п): £ п Т - множество, состоящее из одинаковых ограничений в £ и Т;
композиция (•): Т • £ - дизъюнкция индивидуальных композиций всех элементарных отношений в £, т.е. Т• £ = (¿!, ..., к • ..., л,) = ((^ • s1), (¿1 • S2), ..., (¿к • л,)).
Множество всех временных отношений 2БТК, где БТЯ - множество базовых временных отношений, замкнуто относительно этих операций и образует алгебру временных отношений. Основные подзадачи в ЗСВО: определение согласованности множества ограничений (задача выполнимости);
нахождение согласующего сценария; выявление всех выполнимых ограничений (поиск минимального представления);
поиск выполнимых ограничений между заданной парой временных примитивов.
Дадим краткий обзор существующих моделей временных рассуждений, построенных на основе концепции согласования ограничений с целью выбора наиболее подходящей базы СВР для ИС-ППР РВ. Эти модели могут быть классифицированы в зависимости от выбора временных примитивов и отношений, входящих в множество БТЯ.
Таблица 1. Сравнение алгоритмической эффективности алгебр BPA, CPA и PA
Операция BPA CPA PA
Проверка на согласован- O(n + e) O(n2) O(n2)
ность
Определение всех выпол- O(1) O(n3) O(n3 + п2еФ)
нимых ограничении
1.1. Точечная модель времени. В точечной модели временным примитивом является момент времени. В зависимости от выбора допустимых ограничений между двумя моментами времени выделяют следующие алгебры временных отношений [2, 6]: базовую точечную алгебру BPA, выпуклую точечную алгебру CPA и точечную алгебру PA.
Для базовой точечной алгебры множество базовых отношений есть {0, <, =, >, U}. ЗСВО в BPA либо представляет собой строгий частичный порядок на моментах времени, либо является несогласованной. Если ЗСВО согласована, то все исходные ограничения, кроме универсального, минимальные. Таким образом, решение ЗСВО эквивалентно нахождению тотального порядка на множестве моментов времени. Для поиска решения множество временных ограничений обычно преобразуется в ориентированный граф, в котором вершины представляют моменты времени, а связи взвешены отношением "<" и соответствуют ограничениям. Множество временных ограничений несогласовано, если в полученном графе присутствуют петли или существует хотя бы один цикл. Согласованность, таким образом, мо
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.