Логика ветвящегося времени и ее применение в интеллектуальных системах поддержки принятия решений

Размещено на http://www.allbest.ru/

УДК 007:519.816

ЛОГИКА ВЕТВЯЩЕГОСЯ ВРЕМЕНИ И ЕЕ ПРИМЕНЕНИЕ В ИНТЕЛЛЕКТУАЛЬНЫХ СИСТЕМАХ ПОДДЕРЖКИ ПРИНЯТИЯ РЕШЕНИЙ^** Работа выполнена при финансовой поддержке РФФИ (проект № 05-07-90232)

А.П. Еремеев^1*1 111250, Москва, Красноказарменная 14, МЭИ (ТУ), eremeev@apmsun.mpei.ac.ru

Рассматриваются основные положения темпоральной (временной) логики для ветвящегося времени в плане ее использования в интеллектуальных системах поддержки принятия решений реальноговремени.

Введение

Актуальность наличия развитых средств представления и оперирования темпоральными (временными) зависимостями неоднократно отмечалась уже в ранних работах по кибернетике и искусственному интеллекту (см., например, [Поспелов, 1981; McCarthy et al., 1981; Кандрашина и др., 1989]). Особенно необходимы эти средства при конструировании перспективных интеллектуальных систем (ИС) семиотического типа, способных развиваться и адаптироваться к специфике предметной области (внешней среды) и решаемым задачам [Поспелов, 1981; Поспелов и др., 2002]. Обзор различных моделей и методов представления временного фактора и временных зависимостей (отношений) в плане их применения в ИС и, в частности, ИС поддержки принятия решений реального времени (ИСППР РВ) [Вагин и др., 2001], а также возможности их реализации в рамках ИС и ИСППР РВ, содержится в работах [Еремеев и др., 2003, 2005; Виньков и др., 2003]. Но в них, как правило, основное внимание уделяется моделям (временным логикам) с линейной структурой времени, т.е. когда существует полностью определенное отношение предшествования для временных примитивов (моментов или интервалов) или, иначе говоря, единственное будущее и единственное прошлое. Однако, говоря о топологии времени, необходимо учитывать и возможность ветвящейся (branching) и параллельной структуры времени [Смирнов, 1979; Логический, 1998; Torsun, 1998]. Ветвящаяся структура времени (ветвящееся время) в противоположность линейной допускает множественность (ветвление) будущего и/или прошлого. Такое время соответствует концепции «возможных миров», а параллельная структура времени определяет различные параллельные миры.

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

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

1. Темпоральная логика ветвящегося времени

Темпоральная логика ветвящегося времени (ветвящаяся темпоральная логика) может быть использована для решения задач обучения, прогнозирования и моделирования в ИС, когда необходимо рассматривать время ветвящимся в будущее. Известно, что временная логика может быть построена на основе модальной логики [Смирнов, 1979; Логический, 1998]. Модальный операторы необходимости p может интерпретироваться как «необходимо, что всегда будет p», а модальный оператор возможности p - как «возможно, что будет p», или, другими словами, p истинно в момент времени t, если и только если p истинно при всех t' на всякой ветви времени, выходящей из t, а p истинно при всех t, если и только если p истинно при некотором t' хотя бы на одной ветви, выходящей из t.

В работе [Смирнов, 1979] анализируются различные подходы к темпоральным высказываниям, являющимся утверждениями о будущем. При одном подходе утверждения о будущем рассматриваются аналогично утверждениям о прошлом и настоящем как констатация положения дел (ассерторические утверждения). В этом случае утверждение «когда-нибудь будет p» истинно в момент времени t, если и только если в некоторый момент t', следующий за t, истинно p. Если будущее состояние однозначно детерминировано настоящим, то утверждения о будущем будут либо истинными, либо ложными. Однако более соответствует реальности ситуация, когда допускается, что будущее не предопределено однозначно настоящим и возможны различные варианты развития событий, т.е. возможно ветвление в будущее. При втором (альтернативном) подходе утверждения о будущих событиях рассматриваются не как ассерторические, а как модальные утверждения. В этом случае выражение типа «всегда будет p», «когда-нибудь будет p», «через n единиц времени будет p», корректные (правильно построенные) в случае первого подхода, не являются корректными.

• Правильно построенными выражения будут:

Gp - «необходимо (при любом развитии событий) всегда будет p»;

Gp - «возможно (при некотором развитии событий) всегда будет p»;

Fp - «необходимо когда-нибудь будет p»;

Fp - «возможно когда-нибудь будет p»;

Fnp - «через n единиц времени необходимо будет p»;

Fnp - «через n единиц времени возможно будет p».

Для каждого приведенного оператора процесс развития событий представляется в виде дерева, ветвящегося в будущее (рис.1).

Рис. 1. Графическое представление временных операторов

Введенные операторы являются едиными, так называемыми модализированными темпоральными операторами, а не комбинацией модальных и темпоральных операторов. Данный подход весьма перспективен в смысле выразительности представления, но слабо разработан в плане его практической реализации.

2. Пропозициональная темпоральная логика ветвящегося времени

Более проста в плане сложности реализации пропозициональная темпоральная логика ветвящегося времени (BPTL - Branching-Time Propositional Temporal logic), предложенная в [Torsun, 1998] и являющейся расширением пропозициональной темпоральной логики (PTL). PTL является модальной темпоральной логикой, построенной на основе классической логики с добавленными модальными операторами для дискретного линейного времени.

Синтаксис PTL задается следующим образом. Языком L_P PTL является счетное множество пропозициональных символов p, q, r, s,… Формулы строятся, используя следующие символы:

· Множество пропозициональных символов языка L_P;

· Классические связки: T, F, , , , , ;

· Темпоральные операторы будущего времени: унарные - , , ; бинарные - U,W;

· Темпоральные операторы прошлого времени: унарные - , ?, , ; бинарные - J, Z.

Множеством правильно построенных формул (ппф) PTL являются:

· Все пропозициональные символы языка L_P есть ппф;

· Если A и B - ппф, то ппф также будут и следующие выражения: T, F; A, AB, AB, AB, AB; A, A, A, AUB, AWB; ?A, A, A, A, AJB, AZB.

Интуитивный (неформальный) смысл модальных операторов следующий. Унарных: -следующий (next), ? - прошлый (last), - прошлый (last), - всегда в будущем (always in the future), - всегда в прошлом (always in the past), - иногда в будущем (sometime in the future), - иногда в прошлом (sometime in the past); бинарных: U - до тех пор, пока (until), W - пока не (unless), J - с тех пор, как (since), Z - с тех пор, как (zince). Если A и B являются пропозициональными формулами, то интуитивный смысл модальных формул определяется следующим образом: «Ппф A истинна в данный момент (в данном состоянии), если ппф A истинна в следующий момент (состояние); ппф A («always - всегда» A) истинна в данный момент, если и только если A истинна во все будущие моменты (состояниях, включая текущее); ппф A («eventually - в конце концов» A) истинна в данный момент, если и только если A истинна в некоторый будущий момент. Строгая until ппф AUB истинна в данный момент (состояние), если и только если ппф B в конце концов будет истинна, т.е. в момент sn, где n - текущий момент, и ппф A истинна для всех моментов t, таких что nts.

Оператор W есть слабая версия оператора U, когда не гарантируется истинность ппф B в некоторый будущий момент. Темпоральные операторы прошлого времени определяются как строгая версия прошлого времени для соответствующих операторов будущего («будущих» двойников), т.е. прошлое не включает настоящий момент (состояние).

Семантика PTL. Для задания семантики PTL используется семантика возможных миров Крипке (Kripke). Возможный мир рассматривается как множество состояний во времени, связанных темпоральными отношениями из множества допустимых отношений R. Формально мир задается парой А=(S,R), где S - непустое множество возможных состояний, R -бинарное отношение, R SS.

Рассматривая L_P как множество атомных утверждений, модель мира можно определить как M=(R,S,V),где V - функция означивания (valuation function), задающая отображение V: SL_P {T,F}, т.е. вычисляющая пропозициональное значение для каждого состояния sS. Вводя различные ограничения на отношение R, получают различные модельные структуры. Например, если ввести ограничение антирефлексивности (), то получим дискретную модель. Для дискретных линейных моделей множество S можно рассматривать как последовательность состояний, R - как отношение следования (next) или преемника (successor). Интерпретация задается парой M,i. где M - модель, а i - целое число, индексирующее состояния s_iS в модели.

Семантика для темпоральной ппф задается с использованием отношения ¦ между интерпретацией и ппф. Так утверждение M,i¦A означает, что ппф A интерпретируется в модели M как состояние с индексом i. Семантика для неограниченной дискретной линейной темпоральной логики задается следующим образом:

· Для утверждений:

M,i¦A V(i,p)=T для pL_P, где символ используется как сокращение для «если и только если».

· Для связок:

M,i¦T

M,i¦A not M,i¦A

M,i¦AB M,i¦A и M,i¦B

M,i¦AB M,i¦A или M,i¦B.

Семантика для связок и определяется посредством и .

· Для темпоральных модальных операторов:

M,i¦A M,i+1¦A

M,i¦A (ji)(M,j¦A)

M,i¦A (ji)(M,j¦A)

M,i¦ AUB (ji)(M,j¦B и (k)((ikj) M,k¦A)

M,i¦?A i=0 или M,i-1¦A

M,i¦A i>0 и M,i-1¦A

M,i¦A (j,0j<i)(M,j¦A)

M,i¦A (j,0j<i)(M,j¦A)

M,i¦ A J B (j,0j<i)(M,j¦B и (k)((jki) M,k¦A)

M,i¦ A Z B M,i¦ A J B или M,i¦A.

Интуитивная семантика для модальных операторов определяется следующим образом:

· A - ппф A истинна в текущем состоянии, если и только если ппф A истинна в следующем состоянии;

· A - ппф A истинна в текущем состоянии, если и только если ппф A истинна во всех состояниях в будущем;

· A - ппф A истинна в текущем состоянии, если и только если ппф A истинна в каком-либо состоянии в будущем;

· AUB - строгая until ппф AUB истинна в текущем состоянии s_i, если и только если ппф B будет в конце концов истинна, например, в состоянии s_j, j>i, и ппф A истинна для всех состояний s_k, ik<j;

· AWB - слабая until ппф AWB (называемая unless ппф) означает, что A должна быть истинной до состояния, когда B станет истинной.

Различие между ппф AUB и AWB состоит в том, что для истинности AUB требуется когда-нибудь в будущем истинность B, а для AWB этого не требуется. Модальные операторы прошлого времени (past-time modal operators) определяются как зеркальное отображение модальных операторов будущего. Однако, операторы («всегда в прошлом») и («когда-нибудь в прошлом») интерпретируются как строгие, что означает, что текущий индекс не включается в их определение. Кроме того предполагается, что время в прошлом ограничено и имеет начало. Также различаются два других оператора прошлого времени и ?. Ппф A является ложной, в то время как ппф ?A истинна, только когда интерпретация дается в начале времени. Ппф ?false истинна, когда интерпретация дается для начала времени, в остальное время она ложна. Следовательно ?true можно использовать для определения начала (начального момента) времени. Справедливо: A ?A.

Понятия выполнимости (satisfaction) и общезначимости (validity) ппф определяются следующим образом:

· ппф A выполнима в модели M в состоянии s_i, если и только если M,i¦A; и ппф A выполнима в модели M, если и только если A выполнима в M в состоянии s₀;

· ппф A общезначима (¦A), если и только если A истинна во всех моделях M.

Доказано, что PTL разрешима (M¦A) [Torsun, 1998].

Аксиоматика PTL. Аксиоматическая система для PTL включает следующие элементы:

· (A₀) - все элементы общезначимой схемы пропозициональной логики;

· аксиомы для оператора :

(A₁): (AB)( AB) - схема для нормальной логики K;

(A₂): A A - существование и уникальность преемника;

· аксиомы для операторов и :

(A₃): A - аксиома двойственности;

(A₄): (AB)( AB) - K аксиома;

· аксиомы, описывающие связь между операторами и :

(A₅): A(AA A);

(A₆): (AA)(AA);

· аксиомы, характеризующие оператор U:

(A₇): AUB (B(A(AUB)));

(A₈): (F(F(B(AF)))) AUB, где F - произвольная ппф.

Правилами вывода являются правила modus ponens (MP) и необходимости (N): (MP): если¦A и¦AB, то¦B; (N): если¦A, то ¦A.

Система аксиом для линейной PTL непротиворечива (sound) и полна (complete). Доказано, что ппф доказуема в аксиоматической системе линейной PTL, если и только если она общезначима в PTL [Torsun, 1998].

В линейной дискретной PTL моделью времени является упорядоченная последовательность натуральных чисел. Следовательно, каждое состояние имеет одного и только одного преемника. В ветвящейся логике BPTL для каждого состояния не обязательно наличие единственного преемника и может быть множество возможных путей (последовательностей состояний) из любого данного состояния и, следовательно, возможно несколько различных «будущих». Моделью времени в BPTL является инфинитное дерево, но каждая вершина которого имеет финитное, ненулевое число преемников. Вершина дерева может рассматриваться как возможное состояние, а ветвь или путь - как история возможного мира. Допускается существование лишь одного прошлого, но разрешается будущему быть открытым.

Чтобы специфицировать состояния дерева, для которых ппф является истинной, необходимо идентифицировать путь, содержащий это состояние, и позицию состояния на этом пути. Таким образом делается различие между формулой пути (path formulae) и формулой состояния (state formulae). Формула пути является формулой PTL, а формула состояния указывает тот путь, на котором следует интерпретировать формулу пути, т.е. эта формула интерпретируется на данном состоянии пути. Например, если p есть утверждение и s есть состояние, то формула p будет истинной в интерпретации «если существует путь, порождаемый в s и на котором все состояния удовлетворяют p». Обобщенно, если p есть формула пути, то p и p - формулы состояния. В состоянии s формула p интерпретируется как истинная, если формула p истинна для всех путей, ветвящихся (исходящих) из s, а формула p интерпретируется как истинная, если p истинна хотя бы на одном пути, исходящим из s.

Используя PTL, определены синтаксис и семантика BPTL. Формальная семантика BPTL определяется в терминах модельной структуры M = (S,R,V), где S, R и V определяются аналогично PTL. Концепция ветвящегося времени требует введения условия линейности влево (в прошлое) и транзитивности R. Ппф BPTL являются формулами состояния, а формулы пути - вспомогательные объекты, вводимые для того, чтобы облегчить задание (выражение) семантики формул состояния.

Ппф является непротиворечивой (consistent), если она истинна в некотором состоянии при некоторой интерпретации, и общезначимой (valid), если она истинна в каждом состоянии при каждой интерпретации. Отрицанием общезначимой ппф является невыполнимая (inconsistent) ппф. Определена система аксиом K_b для BPTL. Доказано, что BPTL полна по отношению ко всем структурам ветвящегося времени, т.е. для любой ппф A справедливо + K_bA, если и только если A истинна во всех структурах

Заключение

логика темпоральный решение

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

В настоящее время на кафедре Прикладной математики МЭИ (ТУ) в плане разработки моделей, методов и базовых инструментальных средств конструирования ИСППР РВ семиотического типа на основе нетрадиционных логик разрабатывается СВР, интегрирующая различные модели представления временных зависимостей (для метрического, интервального, смешанного представления времени, для линейной и ветвящейся структур времени, количественных и качественных временных зависимостей и т.д.) применительно к прототипу ИСППР РВ для мониторинга и управления сложными техническими объектами.

Список литературы

[Поспелов, 1981] Поспелов Д.А. Логико-лингвистические модели в системах управления. - М.: Энегоиздат, 1981.

[McCarthy et al., 1981] McCarthy J. M., Hayes P. J. Some Philosophical Problems from the Standpoint of AI. // Readings in AI. TP Co., Palo Alto, 1981.

[Кандрашина и др., 1989] Кандрашина Е.Ю., Литвинцева Л.В., Поспелов Д.А. Представление знаний о времени и пространстве в интеллектуальных системах. / Под ред. Д.А. Поспелова. М.: Наука. Гл. ред. физ.-мат. лит., 1989.

[Поспелов и др., 2002] Поспелов Д.А., Осипов Г.С. Введение в прикладную семиотику // Новости искусственного интеллекта. 2002, № 6.

[Башлыков и др., 1994] Башлыков А.А., Еремеев А.П. Экспертные системы поддержки принятия решений в энергетике. М.: Изд-во МЭИ, 1994.

[Вагин и др., 2001] Вагин В.Н., Еремеев А.П. Некоторые базовые принципы построения интеллектуальных систем поддержки принятия решений реального времени // Изв. РАН. Теория и системы управления. 2001, № 6.

[Еремеев и др., 2003] Еремеев А.П., Троицкий В.В. Модели представления временных зависимостей в интеллектуальных системах поддержки принятия решений // Изв. РАН. Теория и системы управления, 2003, № 5.

[Еремеев и др., 2005] Еремеев А.П., Куриленко И.Е. Реализация временных рассуждений для интеллектуальных систем поддержки принятия решений реального времени // Программные продукты и системы, 2005, № 2.

[Виньков и др., 2003] Виньков М.М., Фоминых И.Б. Формализмы немонотонных рассужденийна базе темпоральной линейной логики с часами // Тр. Междунар. конф. «Интеллектуальные системы» (IEEE AIS'03)» и «Интеллектуальные САПР» (CAD-2003). В 3-х томах. Том 1.- М.: Физматлит, 2003.

[Смирнов, 1979] Смирнов В.А. Логические системы с модальными временными операторами // Материалы II Советско-финского коллоквиума по логике «Модальные и временные логики». - М.: Институт философии АН СССР, 1979.

[Логический., 1998] Логический подход к искусственному интеллекту: От модальной логики к логике баз данных: Пер. с франц. / Тейз А., Грибомон П., Юлен Г. и др. - М.: Мир, 1998.

[Torsun, 1998] Torsun I.S. Foundations of Intelligent Knowledge-Based Systems // ACADEMIC PRESS, London, 1998.

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