Интервальная логика Аллена

Существует класс задач по обработке данных, которые возникают при использовании дискретных систем управления, функционирующих в дискретном времени и описываемых дискретными сигналами.

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

Ограниченность автоматной концепции времени привела к созданию временных (темпоральных) логик, в которых непосредственно изучаются высказывания с истинностными значениями, изменяющимися во времени. Все временные логики принято делить на три класса: первопорядковые, модальные и интервальные^[1]. В первопорядковой временной логике, как это имеет место и в общей теории автоматов, времени не приписывается особой роли, оно выражается лишь переменной наряду с пространственными координатами или другими предметными переменными. В модальной временной логике суть нововведений заключается в добавлении к классическим логическим связкам модальных операторов. Например, модальные операторы Until Release, Next, Future, Globally, All и Exists логики Прайора выражают высказывания, истинные на точках либо — с помощью производных операторов — на лучах времени, направленных в прошлое или будущее.

Алгоритмы вывода в темпоральных логиках, являющихся расширением логики предикатов первого порядка, могут базироваться на модификациях классических алгоритмов вывода в этих логиках, например темпоральной резолюции, но эффективность этих алгоритмов вывода довольно низкая. Однако имеются события, которые происходят на конечных временных интервалах, поэтому чисто точечные или лучевые временные логики не могут выражать все типы высказываний. Современные представления о времени позволяют использовать сразу несколько отношений порядка, не только «раньше», «позже», но и «строго раньше», «примыкает», «пересекается», «включает в себя» и т. д. Такие отношения используются в интервальной временной логике, где становятся возможными квантификация и подстановка высказываний в качестве аргументов временных предикатов.

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

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

• • дискретность или непрерывность времени, т. е. определяется ли некий минимальный шаг изменения времени, например 1 с, или можно указать сколь угодно малый интервал времени;
• • полнота или неполнота времени, т. е. существует ли для любой последовательности, принадлежащей некоторой области интерпретации, предел, также принадлежащий этой области, или данное условие не выполняется;
• • ограниченность или неограниченность времени, т. е. рассматривается ли какой-то достаточно большой, но ограниченный интервал времени или интервал не ограничен и возможны события, происходящие через бесконечное время;
• • линейность, ветвистость или цикличность времени_} т. е. существует ли полностью определенное отношение предшествования во времени для временных примитивов (линейное время) или это условие не выполняется (ветвящееся или циклическое время);
• • гомогенность или гетерогенность временных интервалов, т. е. следует или нет из истинности некоторого утверждения над интервалом его истинность над подинтервалами этого интервала.

Временные зависимости могут быть двух типов: количественные и качественные.

Количественные {метрические) зависимости — когда для представления времени используются количественные меры на временной оси, например «Объект работал 8 ч».

Качественные зависимости — когда используется только относительное положение во времени событий или действий, например: «Сначала оператор сел за пульт, а затем включил систему».

Ясно, что это два крайних подхода и выразительность представления увеличится при наличии средств, позволяющих выражать как количественные, так и качественные временные зависимости.

Существует популярная в настоящее время темпоральная интервальная логика Дж. Аллена^[2], характеризующаяся достаточной выразительностью и наличием полиномиальных алгоритмов вывода, что позволяет ее практически применять в интеллектуальных системах поддержки принятия решений в реальном времени (ИСГГПРРВ).

Аллен выделяет четыре основные характеристики темпоральных отношений, которые должны поддерживаться моделью:

• 1) должны поддерживаться как строгие (количественные), так и нестрогие (качественные) отношения;
• 2) должна поддерживаться неполная и неточная информация (могут, например, быть известны ограничения, накладываемые на отношения, но сами отношения могут оставаться неизвестными);
• 3) должны поддерживаться различные единицы измерения времени (при обработке знаний в области схемотехники чаще всего использующейся единицей времени, по всей видимости, будет наносекунда, в области телекоммуникаций — миллисекунда, а при оперировании повседневными знаниями (т.е. знаниями, используемыми в бытовых повседневных вопросах) — часы, минуты, дни и даже года) либо изменение используемых единиц в зависимости от каких-либо условий;
• 4) должен быть реализован механизм рассуждений по умолчанию (например, в условиях неполной информации).

В логике Алленом в качестве временных примитивов используются интервалы.

Временной интервал X — это упорядоченная пара (X^-, Х⁺), такая что Х~ < Х⁺, где Х~ и Х⁺ рассматриваются как моменты времени (например, на вещественной оси).

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

Таблица 6.2

Множество базовых интервальных предикатов.

Окончание табл. 6.2

В этой логике атомарная формула X V У, где X и Y интервалы, а V — временной предикат, выполним в некоторой интерпретации, если сохраняется отношение V между конечными точками интервалов. Для представления неопределенного (нечеткого) отношения между интервалами используется объединение базисных отношений, которые принадлежат множеству из 13² подмножеств множества базовых интервальных отношений. В этом случае формула вида X {V_1? V₂, V_/?} У выполнима в некоторой интерпретации, если все формулы X V, Y, i = 1, 2, п, выполнимы в этой интерпретации.

Рассмотрим пример использования интервальной динамической области^[3].

Предметные переменные-высказывания имеют истинностные значения, которые изменяются во времени. В этом случае каждую предметную переменную можно представить как интервал времени, формируемый из тех его моментов, при которых эта переменная выполнима, т. е. имеет истинное значение. Интерпретация логических операций временными диаграммами сигналов представлена на рис. 6.29.

Предикаты М₀ = (а > Ь) и М_{ = {а < Ь) являются модальными и предназначены для конструирования интервалов, не выразимых формулами со стандартными логическими операциями. Предикат М₀ имеет исходное значение 0, принимает значение 1 в момент выполнения а и переходит в исходное значение 0 в момент выполнения Ь. Предикат М_{ имеет исходное значение 1, принимает значение 0 в момент выполнения —? а (отрицательный фронт сигнала) и переходит в исходное значение 1 в момент выполненияIb (положительный фронт сигнала).

Таблица исполнения модальных операций на временной диаграмме (<-" — эквивалентность):

Докажем истинность формулын (ф > |/) <-" —i (p < —ij/, где ср и |/ — формулы. Построим таблицу истинности всех ее подформул с учетом статического определения модальных операций М₀ и М_х (табл. 6.3).

Рис. 6.29. Интерпретация формул.

Таблица 63

Таблица истинности модальных операций М₀ и М_х

Сравнивая последние два столбца табл. 6.3, убеждаемся, что формула является тождественно истинным высказыванием (тавтологией) в данной интерпретации.

Известна теорема, которая формулируется следующим образом.

Теорема 6.1. Каковы бы пи были одновременные изменения значений формул ф и |/, итоговые значения модальных операторов ф > |/ и ф < |/ определяются значениями формул М₀ и М_х соответственно.

Другая область интерпретации интервальной динамической логики — прагматика. В отличие от первой области — статической, вторую называют динамической и используют для представления и вывода свойств дискретных динамических объектов, определяемых дискретными сигналами в дискретные моменты времени. Прагматика операций интервальной динамической логики может быть представлена комбинационными и запоминающими /^-триггерами на рис. 6.30.

Рис. 630. Элементы динамической логики.

Следует заметить, что в соответствии с теоремой 6.1 вход R триггера (>) и вход S триггера (<) более приоритетны, чем соответствующие входы S и R.

Построим для формулыi ((p > |/) -i (p < —ij/ схемы а и (3, соответствующие левой и правой частям эквивалентности (рис. 6.31).

Рис. 631. Схемы, реализующие формулу.

а 6

На схеме рис. 6.31, а триггер устаналивается положительными фронтами, а на схеме рис. 6.31, б — отрицательными фронтами.

Если положительный фронт сигнала ср наступит позже положительного фронта сигнала хр, то триггер > всегда установится в единицу (а = 0). В противном случае, если передний фронт сигнала ср наступит раньше переднего фронта сигнала vp или совпадет с ним, триггер > всегда сбросится в нуль (а = 1). С другой стороны, если передний фронт сигнала ср наступит позже переднего фронта сигнала р, то триггер < задним фронтом сигнала —icp всегда сбросится в нуль ((3 = 0). В противном случае, если передний фронт сигнала ср наступит раньше переднего фронта сигнала р или совпадет с ним, триггер < задним фронтом сигнала —ip всегда установится в единицу (р = 1). Отсюда заключаем, что, каковы бы ни были сигналы ср и р, р = а и формула является тавтологией в динамической интерпретации.

Пример 6.5^[4]

Рассмотрим модель автоматической остановки поезда. В кабине машиниста каждые 60 с загорается световой сигнал, чтобы проверить, контролирует ли он идущий поезд. Если машинист проигнорирует этот сигнал, через 6 с включается звуковой сигнал. Затем, если машинист не деактивирует его в течение 3 с, срабатывает механизм аварийного торможения.

Модель процесса для данного примера, представленная на рис. 6.32, содержит шесть мест:

ContrSyst — элемент, контролирующий систему;

Console — консоль в кабине для отображения сигналов;

Brake — механизм торможения;

Driver — машинист поезда;

Timer 1 и Timer2 — таймеры и пять переходов:

TurnOnLS — включение светового сигнала;

TurnOnSS — включение звукового сигнала;

TurnOnBrake — запуск механизма торможения;

Disactivate — дезактивация машинистом сигналов;

Activity — моделирование действий машиниста.

Контрольные сигналы обозначены как токены.

Рис. 6.32. Модель системы остановки поезда.

Задана начальная маркировка, начальные значения временных меток равны нулю и опущены. Переход Disactivate имеет приоритет 1, остальные переходы — 0 (опущены на схеме). Весовые и временные выражения дуг разделены знаком @. Если временное выражение равно нулю, то оно опущено. Каждая дуга с двумя стрелками заменяет для наглядности пару дуг.

Состояние сети представляет собой пару (М, 5), где М — маркировка, функция на множестве мест Р, a S — временной вектор, ставящий в соответствие каждому месту сети число — временную метку. Начальное состояние сети (М₀, Sq) будет выглядеть так:

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

• 1) срабатыванием перехода t е Т в подстановке b (обозначает функцию, которая замещает каждую переменную в защитной функции G (t), функциях весовых и временных значений сигналов Е_м, E_s, влияющих на переход t)
• 2) временными ограничениями (постепенноеуменьшение каждой временной метки на фиксированную величину, пока не появится переход, который может сработать).

Следует отметить, что безусловный приоритет при смене состояний сети имеет событие срабатывания перехода. Течение времени позволяет только дожидаться момента, когда может сработать очередной переход. Для рассматриваемого примера в начальном состоянии могут сработать два перехода: TurnOnLS и Activity. Рассмотрим изменение состояния сети при срабатывании первого перехода. На переходе TurnOnLS защитная функция всегда принимает значение true, поэтому переход срабатывает в так называемой тривиальной подстановке Ь = (). Результатом срабатывания перехода TurnOnLS в начальном состоянии будет являться состояние (M_v S_{)

При срабатывании перехода фишки-токены извлекаются и помещаются в места, связанные с переходом, в соответствии со значениями весовых выражений дуг, временные метки входных мест обнуляются, а временные метки выходных мест определяются в соответствии со значением временных выражений дуг, идущих из перехода к этим местам. В соответствии с условиями, накладываемыми защитной функцией, переход Activity может сработать в трех различных подстановках: b_i = (х/п), Ь₂ = (у/п) и Ъ_ъ = (z/n), где х е (0; б), у е (6; 9), z > 9. Для удобства анализа примем х = 5, у = 8, z = 10. Результатом срабатывания перехода Activity в подстановке Ь₂ будет состояние (Л/₂, S₂):

Ни один переход не может сработать в этом состоянии. Необходимо подождать т = 6 с, чтобы временная метка в месте Console позволила сработать переходу TurnOnSS (машинист нс реагирует на световой сигнал):

После срабатывания перехода TurnOnSS в тривиальной подстановке сеть перейдет в новое состояние (М₃, 5*₃):

Модель системы остановки поезда, построенная с помощью логики Аллена, представлена на рис. 6.33.

Рис. 6.33. Модель системы остановки поезда с темпоральной логикой.

Рассмотренную последовательность смены состояний сети графически можно представить в следующем виде:

Переход к логике Аллена привел к разбиению сети на две несвязные подсети, одна из которых определяет работу механизма аварийного торможения, а другая моделирует действия машиниста. Формулы логики Аллена применены в данном случае как защитные функции переходов DisactLS и DisactSS, обозначающих своевременную реакцию лица, принимающего решения (машинист), на световой и звуковой сигналы соответственно. Главным преимуществом в данном случае является возможность задавать не конкретное время реакции, а интервалы, на которых машинист может дезактивировать систему и каждый из которых определяет дальнейшее поведение модели. Таким образом, включение в модель аппарата интервальных темпоральных логик позволило адекватно отразить неопределенность, присущую задаче.

Множества базовых интервальных отношений Аллена оказывается достаточно для описания встречающихся на практике временных зависимостей между работами проекта. Кроме того, вариант логики Аллена для точечноинтервальной структуры времени позволяет описывать временные связи между интервалами и точками, а также вводить ограничения на длительности интервалов и возможные моменты наступления точечных событий.

Интервальная логика Аллена позволяет адекватно моделировать процессы, протекающие в сложных динамических системах, а также проводить верификацию таких моделей. Ее целесообразно использовать в интеллектуальных системах поддержки принятия решений реального времени.

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

• [1] Стоянова О. ВДли М. И., Васицына А. И. Анализ современных подходов к решениюзадачи построения моделей сложных проектов // Вестник СГТУ. 2012. № 1 (64). Вып. 2.С. 374−378.
• [2] Allen J. F. Maintaining knowledge about temporal intervals // Communications of the ACM.1983. Vol. 26. № 11. P. 832−843.
• [3] Вергер Л. Е., Выхованец В. С. Применение интервальной динамической логикидля мониторинга крупномасштабных процессов // Материалы VI Международной конференции «Управление развитием крупномасштабных проблем» (MLSD'2012). М.: Изд-воИПУ РАН, 2012. Т. 2. С. 358−363.
• [4] Еремеев Л. Я., Королев Ю. И. Реализация интеллектуальных систем реального временина основе сетей Петри с поддержкой темпоральных зависимостей // Программные продуктыи системы. 2013. № 3. С. 88—94.