СИСТЕМА ВРЕМЕННОГО ВЫВОДА ДЛЯ ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ*
Куриленко И.Е., к.т.н., ассистент
ГОУВПО Московский Энергетический Институт
e-mail: ivan@appmat.ru
1. ВВЕДЕНИЕ
О важности наличия средств представления времени и временных (темпоральных) зависимостей (в данных и знаниях) в интеллектуальных системах (ИС) говорится практически с момента их появления (см. например работы Д.А. Поспелова, Дж. Маккарти и др.) [1, 2]. Однако особенно актуальной проблема построения формальных систем оперирования темпоральной информацией встала именно в связи с появлением и развитием ИС, ориентированных на открытые и динамические предметные области (ПО), которые в процессе своего функционирования оперируют с большим объемом информации, изменяющейся со временем. Типичными представителями таких систем являются ИС поддержки принятия решений реального времени (ИСППР РВ) [3]. Необходимость представления информации, меняющейся со временем (показаний датчиков, значений управляющих параметров, выполняемых операторами действий и т.д.) возникает при решении многих задач ИСППР РВ, например, задач диагностики, мониторинга, планирования, прогнозирования и др. Использование при решении этих задач фактора времени и средств временного (темпорального) вывода (временных рассуждений) позволяет сократить поисковые пространства и повысить скорость реакции системы.
Однако в настоящее время отсутствуют развитые средства представления временных зависимостей в инструментальных средствах конструирования ИС, а имеющиеся программные реализации являются исследовательскими системами, интеграция которых в промышленные ИС является затруднительной [4,5]. В связи с этим важной является задача построения системы временных рассуждений (вывода) (СВР) с открытым исходным кодом, модульной структурой и предназначенной для многократного повторного использования.
Существующие подходы представления времени и временных зависимостей в программных системах можно разбить на два основных класса − основанные на моделировании изменений во времени и основанные на явном моделировании времени [6]. В первом случае время представляется неявно посредством моделирования изменений состояний системы во времени, которые рассматриваются как мгновенные снимки мира. Типовые представители данного класса – ситуационное исчисление, планирующие системы типа STRIPS и сети Петри [7, 8]. Они обладают существенными ограничениями по представлению сложных временных и причинно-следственных зависимостей [9]. В научной литературе можно найти различные способы по устранению этих сложностей, однако в большинстве своем они сводятся к введению явной модели времени.
Явное моделирование времени дает возможность строить «гибкие» формализованные языки, позволяющие осуществлять вывод на основе высказываний, истинностные значения которых приурочены к определенному моменту или интервалу времени и могут с течением времени изменяться. В этот класс входят различные временные (темпоральные) логики, в которых время представляется явно с учетом его свойств либо синтаксически (используются явные средства представления) либо семантически (например, на основе модальных логик). При явном моделировании времени возникают специфические задачи временного вывода (временных рассуждений): поддержка согласованности информации о времени – проверка согласованности базы знаний при дополнении ее новой информацей; ответы на временные запросы – от простого нахождения факта, справедливого в заданный момент времени, до определения, когда некоторое множество утверждений истинно в заданный момент времени.
В данном классе подходов можно выделить три большие группы: временные расширения подходов на основе моделирования изменений; введение фактора времени в логику; модели, построенные на основе парадигмы согласования ограничений. Первая группа возникла в результате исследований, целью которых было сокращение недостатков подхода на основе моделирования изменений. Во вторую группу входят модели, полученные путем введения фактора времени в логику. Например, широко известен метод временных аргументов, в котором время вводится в логику предикатов первого порядка в качестве дополнительного параметра. Применительно к спецификации и верификации свойств программ развитие получили модальные временные логики, построенные путем добавления к логике высказываний новых знаков, отражающих свойства времени. К этой же группе относятся и темпоральные логики ветвящегося времени, разработанные для ИС, в которых время необходимо рассматривать ветвящимся в будущее. В третью группу входят модели, построенные на основе представления информации о времени в виде ограничений (зависимостей) между временными примитивами (моментами, интервалами или их комбинациями). Зависимости между примитивами трактуются как ограничения на их расположение во времени. Основной задачей временного вывода является порождение выводов на множестве временных ограничений, т.е., по сути, порождение новых ограничений для непротиворечивых входных множеств. Множество временных примитивов и отношений между ними представляется в виде задачи согласования временных ограничений (ЗСВО), являющейся конкретизацией более общей задачи согласования ограничений (ЗСО), что позволяет использовать для решения ЗСВО методы, применяемые для ЗСО.
Задача согласования временных ограничений задается как Z = (V,D,BTR,C), где V={V1,V2,…,Vm} – конечное множество временных переменных; D – область значений временных переменных; BTR={r1,r2,…,rn} – конечное множество взаимоисключающих бинарных базовых временных ограничений, полное объединение которых является универсальным ограничением U (вообще не накладывающим каких–либо ограничений); C={Cij|Cij={r1,…,rk}; k>0; r1,…,rk BTR; i,j≤m} – конечное множество ограничений, где Cij – ограничение над временными переменными Vi и Vj, интерпретируемое как (Vi,r1,Vj)…(Vi,rk,Vj). В случае, если Cij состоит только из одного дизъюнкта, то оно называется точным.
Для решения задачи выполнимости SAT необходимо найти такое множество ограничений C*= {Cij*|Cij*={rj},rjCij}, что входящие в него точные ограничения не противоречат друг другу. Если такое множество находится, то ЗСВО является согласованной, иначе – несогласованной. Для решения задачи нахождения согласованных сценариев ACS необходимо вычислить все возможные множества C*.
Элементы множества V могут интерпретироваться как моменты, интервалы времени или длительности. Область значений переменных D, соответствующих моментам времени и длительностям, представляет собой множество вещественных чисел, а для интервальных переменных – множество упорядоченных пар значений. Основными операциями над временными ограничениями являются: отрицание (): Lij=U\Lij; инвертирование (~): ~(r1,…,rk)=(~r1,…,~rk); пересечение: S∩T={r:rS,rT}; композиция: TS=(t1,…,tk)(s1,…,sq)= ((t1s1),(t1s2),…,(tksq)). Множество всех возможных временных ограничений, связывающих два временных примитива, состоит из 2|BTR| ограничений, замкнуто относительно операций , ~, ∩, и образует алгебру временных ограничений [10].
Задача согласования временных ограничений называют единичной (ЕЗСВО) тогда и только тогда, когда в множество C входят только точные ограничения. Задачу определения точного ограничения rCij, справедливого для переменных Vi и Vj, для которых задано неточное ограничение Cij={r1,…,rk}, k>1, называют задачей вычисления неточного ограничения Cij.
Ограничение Cij выполнимо для переменных Vi и Vj тогда и только тогда, когда существует хотя бы одно решение ЗСВО, в котором Сij является ограничением для этих переменных. Минимальным ограничением Сijmin называется множество, состоящее только из выполнимых ограничений для Vi и Vj. ЗСВО называют минимальной, если все ее ограничения минимальны.
Задачу вычисления минимальной ЗСВО называют задачей поиска минимального представления MIN. Известно, что для любой ЗСВО всегда можно найти эквивалентную минимальную или показать несогласованность.
Для случаев, когда необходимо обрабатывать неточную информацию вводится дизъюнктивная ЗСВО (ДЗСВО), которая определяется как DZ=(Z,A), где Z – ЗСВО; A={ai|ai=(ai1, ai2,…aik)} – множество дизъюнктивных ограничений, где каждый элемент ai интерпретируется как (ai1ai2…aiu), aij={(xl,rl,yl)|xl,ylV,rlBTR}, каждый элемент aij интерпретируется как (x1,r1,y1)…(xu,ru,yu). Для решения задачи выполнимости DSAT необходимо найти такое множество ограничений A*={ai*|ai*={aij},aijai}, что ЗСВО Z'=(V,D,BTR,CA*) имеет решение. Для решения задачи ACS необходимо найти все возможные множества A*. Для решения задачи DSAT с k элементами в множестве A в худшем случае необходимо проверить разрешимость |a1||a2|…|ak| ЕЗСВО. Доказано, что в общем случае задачи DSAT и ACS являются NP–полными.
Различные модели отличаются сложностью и выразительными способностями. В зависимости от типа ограничений, входящих в множество BTR, ЗСВО подразделяются на качественные, метрические и гибридные. В зависимости от выбора временных примитивов различаются точечная (на базе моментов времени) [11], интервальная (на базе интервалов времени) [12] и интервально–точечная (допустимы и моменты и интервалы) [13] модели времени. Качественная точечная модель времени хорошо подходит как основа для построения СВР. Она проста и приемлема по вычислительной сложности, что дает возможность применять ее в составе промышленных ИСППР РВ. Кроме того, т.к. интервальные и точечно–интервальные ЗСВО могут быть сведены к точечным ЗСВО, целесообразным является реализация в рамках СВР быстрых алгоритмов решения точечных ЗСВО, а для интервально–точечных и интервальных ЗСВО предлагается предварительное их преобразование в точечную ЗСВО. Такая единая основа позволяет упростить переход с одной модели на другую и уменьшить сложность реализации.
2. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ СОГЛАСОВАНИЯ ВРЕМЕННЫХ ОГРАНИЧЕНИЙ
Рассмотрим методы решения ЕЗСВО и ДЗСВО. Решение ЕЗСВО в точечной алгебре (PA) основывается на преобразовании в задачу на графе, взвешенном временной информацией (TLPA–графе). TLPA–граф есть граф G=(W,E,L), где W – множество вершин, W≠Ø, E={(wi,lk,wj)|wi,wjW,lkL} – множество связей (ребер), L={<,≤,≠} – множество возможных пометок на ребрах графа. Ребра, взвешенные ограничением < или ≤, – ориентированные, а ограничением ≠ – неориентированные. Каждой вершине в TLPA–графе G=(W,E,L) соответствует, по крайней мере, одна временная переменная. Если какой–либо из вершин графа соответствует более одной переменной, то они являются альтернативными именами для одного и того же момента времени. Ситуация, когда одна и та же переменная соответствует более чем одной вершине, недопустима. Будем считать, что существует функция μ:W→V, сопоставляющая вершинам графа из множества W имена временных переменных из множества V.
Интерпретацией TLPA–графа G называется тройка <T,I,R>, где T – упорядоченное множество; I:V→T – функция, такая, что для всех pi,pjP выполнимо, что если μ(pi)=μ(pj), то I(pi)=I(pj); R:L→T – функция, отображающая каждую метку lL на ребрах графа G в соответствующее бинарное ограничение R(l) на T. Моделью TLPA–графа G=(W,E,L) называется такая интерпретация, для которой справедливо: если (w1,l,w2)E – ребро в графе G, то для всех pi,pjP, таких, что μ(pi)=w1 и μ(pj)=w2, выполняется <I(pi),I(pj)>R(l). TLPA–граф согласован (непротиворечив), если он имеет по крайней мере одну модель. Два или более TLPA–графа логически эквивалентны, если они обладают одними и теми же моделями.
Путем длины n от вершины w0 к вершине wn в TLPA-графе G называется последовательность n ребер, которая задается набором троек (w1,l1,w2), …(wn-1,ln,wn), где wi(0≤i≤n) – вершины и ljL (0≤j≤n), (wi,li,wi+1)E. Путь в TLPA-графе называется «<–путем» («≤–путем») длины n, если lj={<} (если lj={≤}), при 0≤j≤n. «<-путь» («≤–путь») в TLPA-графе называется «<–циклом» («≤–циклом»), если v0=vn.
Доказано, что TLPA–граф согласован тогда и только тогда, когда он не содержит ни одного «<–цикла» и ни одного «≤–цикла», содержащего две вершины, соединенные ребром, взвешенным ограничением ≠ [4]. Таким образом, для решения задачи SAT необходимо преобразовать ЗСВО в TLPA–граф и проверить эти условия. Рассмотрим решение задачи MIN.
|
