Основные определения и алгоритмы

На данный момент известно большое количество разнообразных временных логик [Pnuelli, 1977; Смирнов, 1979; Allen, 1983; Gereviny et al., 1993]. Однако на практике препятствием к их широкому внедрению является высокая сложность алгоритмов вывода. В этом плане выделяются логики, построенные на основе представления информации о времени как ограничений (зависимостей) между временными примитивами. В качестве таких примитивов могут использоваться временные моменты, интервалы или их комбинация. Зависимости между временными примитивами трактуются как ограничения на их расположение во времени. Благодаря существованию полиномиальных алгоритмов вывода, а также тому, что в них представимы сложные типы временных зависимостей, они являются предметом активных исследований. Среди них наиболее простой и приемлемой по вычислительной сложности для применения в составе современных ИС является точечная временная логика [Еремеев и др., 2009]. Реализация алгоритмов вывода в точечной временной логике основывается на переходе к задаче согласования временных ограничений (ЗСВО). ЗСВО является конкретизацией более общей задачи согласования ограничений (ЗСО), что позволяет использовать для решения ЗСВО методы, применяемые для ЗСО [Еремеев и др., 2003]. ЗСВО задается как Z = (V, D, BTR, C) [Еремеев и др., 2005]:

• 1. V={V₁, V₂,…, V_m} - конечное множество временных переменных (интерпретируемых как моменты времени);
• 2. D — область значения переменных (множество целых чисел);
• 3. BTR={r₁, r₂,…r_n} - конечное множество взаимоисключающих бинарных базовых временных ограничений, полное объединение которых является универсальным ограничением U (не накладывающим каких-либо ограничений);
• 4. C={C_ij|C_ij={r₁,…r_k};k>0;r₁,…r_kBTR;i, j? m}, конечное множество ограничений, где C_ij — ограничение над временными переменными V_i и V_j, интерпретируемое как (V_i, r₁, V_j)…(V_i, r_k, V_j). Если C_ij состоит только из одного дизъюнкта, то оно называется точным.

Для решения задачи выполнимости SAT необходимо найти множество не противоречащих друг другу ограничений C^*={C_ij^*|C_ij^*={r_l}, r_lC_ij}. Если такого множества построить нельзя, то ЗСВО является несогласованной. Если ЗСВО имеет по крайне мере одно решение, то она называется согласованной.

Основными операциями над временными ограничениями являются:

• 1) отрицание (): L_ij=UL_ij;
• 2) инвертирование (~): ~(r₁,…, r_k)=(~r₁,…,~r_k);
• 3) пересечение: S? T={r|rS, rT};
• 4) композиция: TS={t₁,…t_k}{s₁,…s_q}={t₁s₁, t₁s₂,…t_ks_q}.

Известно [Gereviny et al., 1993], что множество всех возможных типов временных ограничений для двух временных примитивов, состоит из 2^|BTR| типов ограничений, замкнуто относительно операций, ~, ?, и образует алгебру временных ограничений.

ЗСВО называют единичной ЗСВО (ЕЗСВО) тогда и только тогда, когда в множество C входят только точные ограничения. При этом сама ЗСВО сводится к проверке непротиворечивости (согласованности) ограничений из множества C. Задачу определения ограничения r, справедливого для переменных V_i и V_j, для которых задано ограничение C_ij={r₁,…r_k}, при k>1, называют задачей вычисления неточного ограничения C_ij.

Ограничение C_ij выполнимо для переменных V_i и V_j тогда и только тогда, когда существует хотя бы одно решение ЗСВО, в котором С_ij является ограничением для этих переменных. Минимальным ограничением С_ij^min называется множество, состоящее только из выполнимых ограничений для V_i и V_j. ЗСВО называют минимальной, если все ее ограничения минимальны. Задачу вычисления минимальной ЗСВО называют задачей поиска минимального представления MIN. Известно, что для любой ЗСВО всегда можно найти эквивалентную минимальную или показать несогласованность ограничений. алгоритм моделирование темпоральный интеллектуальный Построим на базе точечной временной логики логику ветвящегося времени, применимую в составе современных интеллектуальных систем [Куриленко, 2004; Куриленко, 2009]. Сначала определим на базе ЕЗСВО сценарий как S_i=(V_i, C_i, S_j), где S₀=(V₀, D, BTR, C₀) — ЕЗСВО, интерпретируемая как начальный сценарий; S_i — наследуемый сценарий, который расширяет множество переменных V_j и множество единичных ограничений C_j сценария S_j, j_i и C_i соответственно; D — область определения переменных (множество целых чисел), BTRмножество базовых временных ограничений. Таким образом, сценарий является композитной ЕЗСВО, которую можно построить по иерархии наследования, задаваемой в определением сценария. Для каждого сценария, исходя из определения ЕЗСВО, можно поставить задачи поиска минимального представления и проверки согласованности, то есть можно говорить о согласованном или несогласованном сценарии и сценарии в минимальном представлении. Будем называть текущими сценариями такие сценарии, для которых не существует наследуемых сценариев.

Определим ветвящуюся ЗСВО как множество альтернативных сценариев, унаследованных от одного начального сценария S₀ VZ = {S: S — сценарий}. Определим для ветвящейся ЗСВО следующие подзадачи:

Проверка согласованности — проверка существования как минимум одного текущего согласованного сценария Si VZ.

Проверка истинности каких-либо утверждений для конкретного текущего сценария.

Преобразование всех ЕЗСВО, соответствующих согласованным сценариям, к минимальному виду.

Проверка истинности каких-либо утверждений для всех текущих сценариев или хотя бы для одного текущего сценария.

Рассмотрим пример (рис. 1). Данная задача содержит 16 сценариев, из которых 5 являются несогласованными. Следует отметить, что, исходя из практических соображений, следует допускать наследование только согласованных сценариев. Поэтому сценарии S₂₆ и S₂₇ не участвовали в порождении сценариев-наследников.

Рис. 1 Ветвящаяся ЗСВО

Таким образом, каждый сценарий соответствует возможному варианту развития событий (задаваемому соответствующим множеством ограничений над моментами времени).

Существуют разнообразные стратегии формирования сценариев в ветвящейся ЗСВО. В качестве источника ветвления на каждом шаге являются дизъюнктивные утверждения. Не дизъюнктивные утверждения добавляются к каждому текущему сценарию и не приводят к ветвлению. В случае же если вносятся дизъюнктивные утверждения, то к каждому сценарию добавляется ряд наследников. Например, при добавлении в ветвящуюся ЗСВО ограничения типа C_ij v С_xy для каждого текущего сценария должны быть добавлены три сценария — сценарий, в котором обязательно наличие ограничения C_ij, сценарий, в котором обязательно наличие С_xy и сценарий в котором обязательно наличие как C_ij так и С_xy. Естественно, что при такой постановке ветвление является существенной проблемой, так как ведет к сильному росту числа возможных сценариев (особенно при большом числе дизъюнктов). Однако существует ряд приемов, которые могут быть использованы для ограничения ветвления. Мы рассмотрим их немного позже. На практике может быть предусмотрен вариант внесения ограничений, связанных исключающим или, то есть в рассмотренном примере нет необходимости порождения сценария, в котором обязательно наличие комбинации C_ij и С_xy. Другой возможной стратегией является независимая достройка сценариев (когда каждый сценарий достраивается и разветвляется так, как это необходимо исходя из практической задачи). В этом случае внесение дизъюнктивного ограничения приводит к разветвлению конкретного сценария и может не затронуть все оставшиеся сценарии.

Алгоритмы решения задач ветвящейся ЗСВО могут быть построены на базе алгоритмов решения ЕЗСВО [Gereviny et al., 1993; Еремеев и др., 2005; Куриленко, 2007; Куриленко, 2008]. В частности каждую ЕЗСВО в процессе решения ветвящейся ЗСВО можно решать с помощью перехода к задаче на графе времени TL-графе (Подробно подход к решению ЕЗСВО на основе перехода к задаче на графе рассмотрен в работах [Gereviny et al., 1993; Еремеев и др., 2005]). Однако подобный подход не является оптимальным, так как на практике придется хранить в памяти TL-граф и Time-граф для каждого сценария. С учетом возможного роста числа сценариев хотелось бы построить такое внутреннее представление задачи, которое позволяло бы экономить ресурсы за счет учета наследования сценариев, заложенного в само определение ветвящейся ЗСВО. Также при построении алгоритмов следует учесть, что создание новых сценариев на каждом шаге должно выполняться как можно быстрее, так как в некоторых приложениях, типа ИСППР РВ, глубина анализа (то есть рассмотрение как можно большего числа сценариев) способствует получению более качественного решения. В работах [Куриленко 2008, 2009] предлагаются алгоритмы позволяющие экономить вычислительные ресурсы при последовательном дополнении ЕЗСВО ограничениями, за счет анализа производимых изменений. В случае ветвящейся ЗСВО такие алгоритмы отлично подходят для решения ЕЗСВО для каждого сценария-наследника S_i=(V_i, C_i, S_j), так как они определяются как расширение множества ограничений в сценарии-предке. Коротко рассмотрим этот подход. Для представления ЕЗСВО используется TL граф, определяемый как G=(W, E, L), где W — непустое множество вершин (соответствующее моментам времени), E — множество направленных связей вида (w_i, l, w_j), где w_i, w_jW, lL, L={<,?} [Куриленко, 2008]. Путем р_xy=0,x₁,.x_k>из вершины x в вершину y в графе G называется последовательность вершин, в которой x₀=x, x_k=y и (x_i, x_i+1)E для всех 0? i_xy)=, где — пометка ребра (x_i, x_i+1). В случае если при вычислении веса w_xy в графе G существует направленная связь (y, l, x), то в качестве w_xy принимается ~l. Будем считать путь р_xy существенным, если w (р_xy)?U и w (р_xy)? Ш.

Определим множество P всех направленных путей между всеми вершинами в графе G. Определим: P' - множество существенных путей в графе G, P’P; множество входящих в вершину x путей L_p(x)={р_lx|l?x, р_lxP'} и множество выходящих из вершины x путей R_p(x)={р_xm|m?x, р_xmP'}. Алгоритмы создания и удаления связей строятся таким образом, что их выполнение производится над множеством существенных путей, и что связи, которые могут привести к несогласованности, отсекаются на этапе внесения и не участвуют в порождении путей. Ниже приводится алгоритм, применяемый для создания связей (алг. 1), сложность которого составляет O (|R_p(y)||L_p(x)|). Требуемый для работы объем памяти — O (e²). Существенным отличием алг. 1 является то, что согласованность проверяется на этапе создания связей, и несогласованность определяется сразу при внесении приводящих к ней связей.