Программные продукты и системы

В работе [1] была введена так называемая логика движения (ЛД), соединяющая понятия ньютоновой механики и классической логики. В дальнейшем эта логика была развита в [2–4].

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

В данной логике объекты не имеют структуры, то есть фактически являются материальными точками. Однако многие реальные прикладные задачи требуют представления структуры объектов и существует необходимость манипулирования этой структурой. Обычно структура объекта определяется его связями с другими объектами, его компонентами и атрибутами. Такими возможностями обладают языки дескриптивной логики [5].

В работе [6] предложена гибридная логика SHOIQ[LOM], в которой соединены возможности ЛД LOM (logic of motion) и дескриптивной логики SHOIQ. В гибридной логике описание понятия

Самолет⋂

      ∃near(13:00,14:00;10km).Самолет        (1)

определяет множество самолетов, находящихся в период c 13 до 14 часов ближе чем на 10 километров к другому самолету. Структура понятий передается с помощью ролей, которые соответствуют атрибутам (многозначным или однозначным). В частности, однозначные атрибуты в логике SHOIQ[LOM] представляются функциональными ролями. Например, для понятия Самолет можно ввести такие функциональные роли, как тип_са­молета, колич_мест, компания и т.п. Тогда в онтологию, представляющую знание для интеллектуальной информационной системы диспетчерской службы, будут включены следующие предложения:

funct(тип_самолета), funct(колич_мест),

funct(компания), Самолет ⊂ ∃тип_самолета,

Самолет ⊂ ∃колич_мест, Самолет ⊂ ∃компания.

В (1) near – встроенная роль в интерпретаторе гибридной логики SHOIQ[LOM]. Эта роль, которая является бинарным отношением между индивидными константами, вычисляется соответствующей программой интерпретатора логики SHOIQ[LOM]. Авторы работы [6] построили основанный на методе аналитических таблиц алгоритм логического вывода в логике SHOIQ[LOM].

В языках дескриптивной логики принято разделять интенсиональное знание (представляемое в компоненте TBox) и экстенсиональное знание (представляемое в компоненте ABox). Это важный принцип, так как он позволяет отдельно выполнять логический вывод в системе понятий и вывод в системе фактов; последний необходим для вычисления запросов, обращенных к базе фактов (то есть к компоненте ABox, рассматриваемой в предположении замкнутого мира). В гибридной логике SHOIQ[LOM] этот принцип нарушен (как видно из (1)), что является ее большим недостатком. Другой недостаток логики SHOIQ[LOM] в том, что ее язык не является типизированным. (Известно, что типизированные языки обладают важными преимуществами по сравнению с нетипизированными [7].)

В работах [8–10] была предложена система «Бинарная модель знаний» (БМЗ) концептуальных языков для онтологического (концептуального) моделирования. В БМЗ можно естественным образом специфицировать структуру объектов, рассуждать о знании для структурированных объектов и вычислять ответы на запросы, относящиеся к конкретным объектам. В языках БМЗ выполняется принцип разделения интенсионального и экстенсионального знаний. Кроме того, эти языки типизированы.

Система БМЗ включает язык структурной спецификации (ЯСС), в котором, например, структура класса Самолет и бинарной связи NEAR (понятия близости) определяется следующим образом:

Самолет[ТипСамолета:String,

 Компания:String,Колич_мест:Integer],

(Class1 NEAR Class2)

  [TimeInt:(TimeDT,TimeDT),Dist:DistD)].

Второе предложение является встроенным в интерпретатор БМЗ. Здесь NEAR – встроенная бинарная связь (отношение), вычисляемая соответствующей программой интерпретатора. Имена в предложении обозначают параметры с определенными значениями. Так, у параметров Class1 и Class2 значениями служат имена классов, у TimeInt – атрибуты, у TimeDT – спецификации типов данных, у Dist – имена атрибутов, у DistD – имена доменов.

Определяя понятие близости самолетов, мы можем ввести бинарную связь Near1 как специализацию (конкретизацию) бинарной связи NEAR:

(Самолет Near1 Самолет)

[TimeInt:(Time_of_day,Time_of_day),

Dist:Dist_km)].

Предположим, что мы обращаемся к базе фактов с запросом: «Найти пары самолетов, находящиеся на близком расстоянии друг от друга во время с 13 до 14 часов, то есть на расстоянии, не большем 10 километров». Этот запрос записывается в языке запросов системы БМЗ так:

?(X,Y)-(X Near1 Y);

Near1(TimeInt=(13.00,14.00);Dist=10).

В настоящей статье показано, как ЛД можно интегрировать в систему БМЗ. Благодаря этому получены средства онтологического (концептуального) моделирования для приложений, включающих поведение движущихся объектов.

Краткие сведения о ЛД

Синтаксис и семантику ЛД авторы определяют соответственно статье [1]. Пусть R – множество всех вещественных чисел, R+ – множество положительных чисел, O – конечное множество имен объектов, VR – множество переменных со значениями в R, VO – множество переменных со значениями в О. Вещественный терм – это элемент R È VR, объектный терм – элемент О È VО.

Атомы ЛД определяются следующим образом.

·       Если о1 и о2 – объектные термы, d, t1, t2 – положительные вещественные термы, то near(о1, о2, d, t1, t2) – атом. Интуитивный смысл: «объекты о1 и о2 находятся друг от друга на расстоянии d в моменты времени из интервала [t1, t2]». Этот атом можно также записать, вставив скобки, чтобы выделить временной интервал: near(о1, о2, d, [t1, t2]).

·       Если о1 и о2 – объектные термы, d, t1, t2 – положительные вещественные термы, то far(о1, о2, d, t1, t2) – атом. Интуитивный смысл: «расстояние между объектами о1 и о2 в моменты времени из интервала [t1, t2] больше d». Этот атом можно также записать, вставив скобки, чтобы выделить временной интервал: far(о1, о2, d, [t1, t2]).

·       Если о – объектный терм, t1, t2 – положительные вещественные термы, х1, у1, х2, у2 – вещественные термы, то in(о, x1, y1, x2, y2, t1, t2) – атом. Интуитивный смысл: «объект о находится в некоторый момент времени из интервала [t1, t2] в прямоугольнике с левой нижней вершиной (x1, y1) и правой верхней вершиной (x2, y2)». Этот атом можно также записать, вставив скобки, чтобы выделить координаты и временной интервал: in(о, (x1, y1), (x2, y2), [t1, t2]).

·       Если о – объектный терм, t1–, t1+, t2–, t2+, v–, v+ – положительные вещественные термы, х1, у1, х2, у2 – вещественные термы, то go(о, x1, y1, x2, y2, t1–, t1+, t2–, t2+, v–, v+) – атом. Интуитивный смысл: объект о покидает точку (x1, y1) в некоторый момент времени из интервала [t1–, t1+], движется по прямой с некоторой скоростью из интервала [v–, v+] и прибывает в точку (x2, y2) в некоторый момент времени из интервала [t2–, t2+]. Этот атом можно также записать, вставив скобки: go(о, (x1, y1), (x2, y2), [t1–, t1+], [t2–, t2+], [v–, v+]).

Предложение ЛД – это атом или булева комбинация атомов, то есть, если α и β – предложения, то предложениями являются ~α, α/\β и α\/β. Выражение α→β также считается предложением и рассматривается как сокращение предложения ~α\/β. Предложение ~α, где α – атом, называется литералом.

Семантика ЛД определяется через понятие интерпретации. Интерпретация – это непрерывная функция I: O ´ R+ → R ´ R. Интуитивный смысл: I(o, t) – положение объекта о в момент времени t.

Атом go(о, (x1, y1), (x2, y2), [t1–, t1+], [t2–, t2+], [v–, v+]) истинен в данной интерпретации I относительно интервала [t1, t2], если

-      t1Î[t1–, t1+], t1Î[t1–, t1+], I(o, t1) = (x1, y1), I(o, t2) = (x2, y2);

-      для всякого момента времени tÎ[t1, t2] точка I(o, t) лежит на отрезке [(x1, y1), (x1, y1)];

-      для всех t, t’Î[t1, t2] с t

-      почти всегда в интервале [t1, t2], то есть кроме конечного числа моментов времени tÎ[t1, t2], существует производная v = d(I(o, t))/dt и vÎ[v1, v2].

Атомы near(о1, о2, d, [t1, t2]), far(о1, о2, d, [t1, t2]), in(о, (x1, y1), (x2, y2), [t1, t2]) истинны в интерпретации I, если соответственно

-      dist(I(o1, t), I(o2, t)) ≤ d для всякого tÎ[t1, t2];

-      dist(I(o1, t), I(o2, t)) > d для всякого tÎ[t1, t2];

-      существуют такие tÎ[t1, t2], хÎ[х1, х2], уÎ[у1, у2], что I(o, t)=(х, у).

Истинность предложений определяется стандартным образом. Если α и β – произвольные предложения, то предложения ~α, α/\β, α\/β истинны в интерпретации I, если соответственно α ложно, α и β истинны, α или β истинны в этой интерпретации.

Как и во всякой логике, в ЛД имеются понятия логического следствия и логической выполнимости. Пусть Е – множество предложений ЛД и α – предложение. Тогда из Е логически следует α (в записи: Е |= α), если не существует интерпретации, при которой все предложения из Е истинны, а предложение α ложно. Множество Е выполнимо, если существует интерпретация, при которой все предложения из Е истинны.

Задача логического следствия сводится к задаче невыполнимости, так как E |= α ó множество Е U{~α} невыполнимо. На самом деле проблему логического следствия (для конечных Е) можно свести к проблеме невыполнимости литералов (то есть атомов или отрицаний атомов). Для этого можно воспользоваться методом аналитических таблиц.

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

База знаний в ЛД – это конечное множество предложений этой логики. Запросом назовем выражение вида ?α, где α – предложение ЛД. Пусть Е – база знаний и ?α – запрос к этой базе. Ответом на этот запрос может быть одно из сообщений: «Да», «Нет» или «Нет информации» в зависимости от того, что, соответственно, E |= α, E |= ~α или E |≠ α и E |≠ ~α.

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

Краткие сведения о системе БМЗ

Описывая систему БМЗ, авторы следуют работам [9, 10]. Эта система предназначена для спецификации онтологий, их анализа и для работы с ними, а также для управления базами фактов, структурированных в соответствии с онтологиями. Языки системы БМЗ относятся к типу концептуальных (понятийно-ориентированных) языков. Таким образом, семантическими примитивами для этих языков служат формальные понятия, смысл которых близок к смыслу понятий класса или типа объектов.

Каждое формальное понятие С имеет универсум UC и экстенсионал ЕС. Элементами экстенсионала служат имена, обозначающие примеры (экземпляры) понятия С, а элементами универсума – все имена, которые могут служить примерами понятия С. В экстенсионале ЕС также имеется отношение кореференции: два имени, е1 и е2, из ЕС считаются кореферентными (в записи: е1~е2), если обозначают один и тот же объект моделируемой предметной области.

В БМЗ имеются два типа понятий: классы и бинарные связи. Первые представляют множества объектов, вторые – бинарные отношения между объектами.

В качестве имен понятий используются как простые, так и составные имена, которые строятся при помощи соответствующих конструкторов. Если С – простое имя класса и L – простое имя бинарной связи, то

-      С(*) обозначает класс, экземплярами которого служат конечные множества экземпляров понятия С, то есть

UC(*) = {{e1, e2, …, en}| eiÎUC (1≤i≤n, n = 0, 1, 2, …)},

EC(*) = {{e1, e2, …, en}| eiÎEC (1≤i≤ n, n = 0, 1, 2, …)};

-      С(p, q), где p, q – натуральные числа и p≤q, обозначает понятие, экземплярами которого служат конечные множества экземпляров понятия (класса или бинарной связи) С, причем размеры этих множеств заключены в границах чисел p и q; число q можно заменить на символ *, который означает неограниченность размера множеств – экземпляров класса С;

-      L((p, q), (r, s)), где p≤q и r≤s, обозначает бинарную связь, экземплярами которой служат конечные множества экземпляров L; при этом, если множество ЕL((p,q),(r,s)) рассматривать как двудольный граф, степень любой левой (правой) вершины должна быть заключена между числами p и q (соответственно между числами r и s). Для пар (p, q) и (r, s) также применяются вышеупомянутые сокращения;

-      A:C обозначает класс, экземплярами которого служат имена А:х, где х – произвольный экземпляр класса С;

-      (С1, С2, …, Сn) обозначает класс, экземплярами которого служат имена (х1, х2, …, хn), где хi – произвольные экземпляры классов Сi;

-      С1|С2|…|Сn обозначает класс, экземплярами которого служат все экземпляры классов Сi (аналогичный смысл имеет выражение L1|L2|…|Ln, где Li – имена бинарных связей).

В БМЗ входят следующие языки:

-      ЯСС; предложения ЯСС определяют универсумы понятий;

-      язык спецификации типов данных (ЯТД); предложения ЯТД задают абстрактные типы данных, которые используются как домены атрибутов;

-      язык атрибутных условий (ЯАУ); предложения ЯАУ определяют выраженные в терминах атрибутов ограничения на примеры понятий;

-      язык фактов (ЯФ); предложения ЯФ используются для формирования баз фактов;

-      язык запросов (ЯЗ); предложениями ЯЗ служат запросы к базам фактов;

-      язык логической спецификации (ЯЛС); предложения ЯЛС специфицируют экстенсионалы понятий; ЯЛС содержит несколько подъязыков.

Онтология в БМЗ – это конечное множество О предложений из ЯСС È ЯТД È ЯЛС.

Предложения ЯСС составляются из примитивных предложений, имеющих следующие формы: C[Е], C[A:E], C[A:T], (C L D), (C LD)[E], (C L D)[A:E], (C L D)[A:T], где C, D – простые имена классов; Е – имя класса (простое или составное); L – имя бинарной связи; Т – спецификация типа данных (выполненная в языке ЯТД).

Произвольные предложения ЯСС получаются путем соединения примитивных предложений, имеющих одинаковую голову. (Головой первых трех указанных примитивных предложений является имя С, а последних четырех – выражение (C L D).) Например, предложение C[Е, A:D(*), K:Integer, B:T] получается из четырех примитивных предложений: C[Е], C[A:D(*)], C[K:Integer] и C[B:T].

Примитивные предложения имеют естественную семантику. Например, примитивное предложение C[A:E] определяет универсум

UC= Surr È Iname È {[A:x] | xÎSurr},

а предложение (С L D)[А:T] – универсум

UL= Surr È Iname È {[C:x, D:y,A:z] | x, yÎSurr, zΫT»}.

Здесь Surr = {#1, #2, #3, …} – множество суррогатов (то есть системных идентификаторов индивидных объектов); Iname – множество всех имен для обозначения индивидных объектов; «T» – множество всех значений типа данных, определяемого спецификацией Т. Например, если Т есть (F:Integer(*), String), то множество значений «Т» состоит из кортежей вида (F:{x1, x2, …, xn},y), где xiÎInteger (i = 1, 2, …, n) и уÎString.

Семантика составного предложения языка ЯСС определяется семантиками примитивных предложений, из которых это предложение было получено. Например,

UC[Е,A:D(*),K:Integer,B:T] = Surr È Iname È

{[E:x, A:{y1, y2, …, yn}, K:z, B:u] | x, yiÎSurr

(i=1, 2, …), zÎInteger, uΫT»}.

Таким образом, в этот универсум входят кортежи, например кортеж [E:#25, A:{#2, #5}, K:17, B:(F:{0, 3}, abca)], если Т есть (F:Integer(*), String).

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

Факты выражают утверждения о принадлежности имен к классам и к бинарным связям: eÎEC, e∉EC, (e, e’)ÎEL, (e, e’)ÏEL, t.AÎEC, t.AÏEL. К фактам также относятся равенства t.A= v и неравенства t.A≠v. Здесь t – кортеж; А – атрибут этого кортежа; v – значение типа данных. В языке ЯФ эти факты записываются так: +e IN C, –e IN C, +e L e’, –e L e’, +t.A IN C, –t.A IN C, t.A = v, t.A /= v.

В БМЗ базы фактов состоят из таблиц, шапки которых определяются предложениями языка ЯСС. Например, предложение

C[Е, A:D(*), K:Integer, B:(F:Integer, String)]           (2)

определяет следующую шапку таблицы:

Поля этой таблицы определяются атрибутами, имеющими домены: dom(Surr) = Surr, dom(Sign) = ={+, –}, dom(Coref) = (Iname | Surr(*)), dom(K) = =Integer, dom(B) = (F:Integer(*), String).

Пусть в таблицу для указанного класса С входит, например, строка (#22, +, {#5, a}, {#2, #7}, (F:3, aba)}. Тогда эта строка представляет следующие факты и кореферентности:

#22ÎEC (так как #22.Sign = +),

[A:{0, 3}, K:{#2,#7}, B: (F:{0, 3}, aba)]ÎEC,

[A:{0, 3}, K:{#2, #7}, B: (F:{0, 3}, aba)] ~ #22 ~ #5 ~ a.

Элементарное атрибутное условие – это выражение вида S1θS2 или вида S1θс, где S1 и S2 – селекторы; с – константа; θ – оператор сравнения (в частности, равенство и неравенства). Селектор – выражение вида A1.A2.....An, где Ai – атрибуты. Атрибутное условие – конъюнкция λ1; λ2; …; λn элементарных атрибутных условий λi. (Здесь точка с запятой обозначает конъюнкцию.)

Селекторы и атрибутные условия должны быть (синтаксически) корректными. Понятие корректности селектора и атрибутного условия поясним на примерах. Предположим, что в онтологию О входят предложение (2) и предложение D[R:C]. Тогда корректными будут следующие селекторы для класса С: А.R.K и A.R.B.F. Корректность элементарного атрибутного условия S1θS2 предполагает, что его селекторы относятся к одному и тому же понятию и значения также принадлежат к одному и тому же домену. Например, элементарное атрибутное условие А.R.K

Атрибутное условие α для понятия С определяет подпонятие С(α); его примерами служат удовлетворяющие условию α примеры С. Например, если α есть А.R.K

Основным типом запросов к базам фактов являются конъюнктивные запросы. В общем случае конъюнктивный запрос имеет вид ?γ – δ1; δ2; …; δn, где γ называется головой, а δ1; δ2; …; δn – телом запроса. Голова γ – это терм или последовательность термов: γ = τ or γ = (τ1, τ2, …, τm). Компоненты δi тела запроса имеют вид

S θ c, X.S1 θ Y.S2, X.S IN C,

X.S IN C(α), (X L Y),                                               (3)

(X L Y Z),

где C и D – классы; L – бинарная связь; X, Y, Z – переменные; c – константа; S, S1, S2 – селекторы; θ – оператор сравнения; α – атрибутное условие.

В ЯЗ также имеются условные конъюнктивные запросы, которые имеют вид

? – IF ε THEN λ ELSE μ,

где ε – условие; λ и μ – конъюнкции компонент δi.

ЯЛС включает несколько типов предложений. В частности, атрибутные условия также рассматриваются как предложения ЯЛС.

Если α – предложение ЯЛС и С – понятие, то запишем С|=α для обозначения того, что предложение α выполнено для каждого примера понятия С. Например, С |= А.R.K

ЛД в БМЗ

Предикаты near, far, in и go ЛД интегрируются в систему БМЗ путем включения в интерпретатор языка ЯСС соответствующих понятий (бинарных связей и классов). Эти понятия определяются следующими встроенными предложениями:

(Class1 NEAR Class2)

    [TimeInt:(TimeD,TimeD),Dist:DistD)],

(Class1 FAR Class2)

 [TimeInt:(TimeD,TimeD),Dist:DistD)],

IN[Object:Class,

Lower_left:(Real,Real),

Upper_right:(Real,Real),

Time_int:(TimeD,TimeD)],

GO[Object:Class,

Leave:(Coord:(Real,Real),Time:TimeD),

Arrive:(Coord:(Int1:(Real,Real),

Int2:(Real,Real)),

  TimeInt:(TimeD,TimeD)),

Speed:SpeedD].

Замечания. Для простоты предполагается, что пространство двумерное. Определяя понятие Go, предполагается, что координаты в Arrive неточные, но принадлежат интервалам; время также принадлежит интервалу.

Эти предложения входят в онтологию ОЛД-БМЗ, построенную для интегрированной системы ЛД-БМЗ. В эту онтологию также включены предложения, выражающие некоторые семантические ограничения для понятий ЛД. Так, атрибутное условие для класса NEAR TimeInt.1=

(FOR X,Y IN GO)IF X.Object=Y.Object;

X.Arrive.1=Y.Leave.1;

X.Arrive.2.1=

X.ARRIVE.2.2=

THEN(EXIST Z IN GO)

Z.Object=X.Object;

Z.Leave=X.Leave;

Z.Arrive=Y.Arrive.

Значениями параметра TimeD служат имена типов данных, которые могут быть использованы для обозначения моментов времени. Например, можно взять имя Time_of_day для типа данных, элементы которого имеют формат XX.XX. Вместо параметра DistD можно подставить имена типов данных для обозначения расстояний, например, имя Dist_km обозначает тип данных для расстояний в километрах.

Составляя онтологию для конкретного приложения, содержащего движущиеся объекты, разработчик заменяет параметры в предложениях онтологии ОЛД-БМЗ на соответствующие имена для классов и бинарных связей. Таким образом, из параметрической онтологии ОЛД-БМЗ получается онтология, которую можно назвать ОЛД-БМЗ[N], где N – имя приложения. Онтология ОЛД-БМЗ[N] расширяется путем добавления новых атрибутов к ее понятиям и добавления новых понятий и предложений.

Литералы (атомы и отрицания атомов) ЛД представляются фактами в системе БМЗ. Таким образом, знанию, представленному наборами литералов ЛД, соответствует база фактов в БМЗ. Однако эта база фактов состоит не только из таблиц для понятий NEAR, FAR, IN и GO, специализированных в соответствии с конкретным приложением, она включает и таблицы для понятий приложения, которые, в частности, задают структуру движущихся объектов. К этой базе фактов можно обращаться с запросами, сформулированными в языке ЯЗ.

Пример 1. Рассмотрим приложение, связанное с управлением аэротрафиком. Фрагмент онтологии для этого приложения составляют следующие предложения ЯСС:

(Самолет NEAR Самолет)

 [TimeInt:(Time_h:m:s,Time_h:m:s),

 Dist:Dist_km)],

(Самолет FAR Самолет)

 [TimeInt:(Time_h:m:s,Time_h:m:s),

 Dist:Dist_km)],

(Самолет NEAR Аэропорт)

 [TimeInt:(Time_h:m:s,Time_h:m:s),

 Dist:Dist_km)],

IN[Object:Самолет,Lower_left:(Real,Real),

Upper_right:(Real,Real),

Time_int:(Time_h:m:s,Time_h:m:s)],

GO[Object:Самолет,                 (4)

Leave:(Coord:(Real,Real),

Time:Time_h:m:s)),

Arrive:(Coord:(Int1:(Real,Real),

Int2:(Real,Real)),

Time_int:(Time_h:m:s,

Time_h:m:s),

Speed:Speed_km-h],

Самолет[№борта:Integer,Тип:String,Экипаж,

Марка:String,СрокЭкспл:Integer,

Объем_горючего:(Integer|String)],

Экипаж[Командир:Пилот,1-й_пилот:Пилот,

2-пилот:Пилот,Штурман,Стюард(*)],

Аэропорт[Назв:String,Класс:Integer,

Служба(*)],

Полет[Самолет,Рейс:String,

Аэропорт_отпр:Аэропорт,

Аэропорт_назн:Аэропорт,

Время_вылета:Time_of_day,

Ожидаемое_время_прилета:Time_of_day)].

В интегрированной системе ЛД-БМЗ факты записываются с помощью оператора INSERT.

Пример 2. Предположим, что мы должны записать факт о полете борта № 200237. Тогда можно, например, записать

INSERT полет1 IN Полет:

Самолет.№борта=200237;Полет.Рейс=FV 122;

Аэропорт_отпр=Москва(Домодедово);

Аэропорт_назн=Санкт-Петербург(Пулково1).

Время_вылета=16марта10:20;

Ожидаемое_время_прилета=16марта12:35.

Рассмотрим примеры запросов к базе фактов для онтологии ОЛД-БМЗ[Аэротрафик], выраженных в ЯЗ.

Пример 3.

Запрос 1. Найти все самолеты Боинг737 с низким уровнем горючего, находящиеся в настоящий момент вблизи аэропорта Домодедово:

?X.№борта–(Самолет:X NEAR:Y Аэропорт:Z);

 Х.Марка=Боинг737;

 Х.Объект.Объем_горючего=мало;

 Y.TimeInt=(now,now);Y.Dist=10km,

 Z.Назв=Домодедово.

Запрос 2. Имеется ли опасный полет в районе аэропорта Домодедово? Полет считается опасным, если в данный момент самолет имеет мало горючего или вблизи от него находится другой самолет:

?– (X IN Полет);

(X.Объект NEAR:Y Аэропорт:Z);

Х.Объект.Объем_горючего=мало

OR Объект NEAR:Y1 Объект:Z1)

Х.Объект.Объем_горючего=мало;

Y.TimeInt=(now,now);Y.Dist=10km;

Y1.Dist=0.3km;Z.Назв=Домодедово.

Запрос 3. В настоящий момент обнаружено, что борт № 200357 может войти в опасное сближение с бортом № 220498. (Опасное сближение составляет менее 200 м.) Как следует изменить скорость борта № 200357, чтобы возможное сближение составило менее 400 м?

Пусть X и Y – экземпляры понятия GO в (4): X IN GO, X IN GO. На рисунке эти экземпляры условно изображены векторами AB→ и CD→. Точки A, В, С и D имеют следующие координаты:

A.1= X.Leave.Coord.1,                    (5)

A.2= X.Leave.Coord.2,                    (6)

B.1=(1/2)*(X.Leave.Coord.Int1.1+

+X.Leave.Coord.Int2.1),        (7)

B.2=(1/2)*(X.Leave.Coord.Int1.2+

+X.Leave.Coord.Int2.2),        (8)

C.1= Y.Leave.Coord.1,                    (9)

C.2= Y.Leave.Coord.2,                    (10)

D.1=(1/2)*(Y.Leave.Coord.Int1.1+

+Y.Leave.Coord.Int2.1),        (11)

D.2=(1/2)*(Y.Leave.Coord.Int1.2+

+Y.Leave.Coord.Int2.2).        (12)

Заметим, что для B.2 (и для D.2) мы взяли средние значения, учитывая, что точки прибытия определены не точно, а только в соответствующем интервале.

Предположим, что отрезок C’D’ находится от отрезка CD (см. рисунок) на расстоянии (по ординате), соответствующем 200 метрам, а отрезок C”D” – 400 метрам. Тогда точки В’, С’, B” и C” имеют следующие координаты:

B’.1=B.1-200, В’.2=В.2-200,

С’.1=С.1-200, С’.2=С.2-300.

B’’.1=B.1-400, В’’.2=В.2-400,

С’’.1=С.1-400, С’’.2=С.2-400

Точка Е является пересечением отрезков АВ и C”D” E = Intersect([A,B],[C’’,D’’]), где Intersect – встроенная функция, вычисляющая пересечение двух отрезков на плоскости. (Эта функция выдает nil, если отрезки не пересекаются.)

Координаты точки F можно определить следующим образом. Самолет окажется в точке F через время, равное Т1=now-X.Leave.Time, и (если он будет следовать информации, представленной в экземпляре Х понятия GO) должен оказаться в точке В через время, равное

Т2=(1/2)*(X.Arrive.Time_int.1+

+X.Arrive.Time_int.2). 

Следовательно (предполагая, что самолет летит с постоянной скоростью), точка F должна иметь следующие координаты:

F.1=А.1+(T1/T2)*(B.1-А.1)

F.2=А.2+(T1/T2)*(B.2-А.2) 

Пусть R – конъюнкция условий (5)–(10), а P – конъюнкция деклараций точек на рисунке, то есть

R = A IN Point; B IN Point; C IN Point;

 D IN Point; C’IN Point; D’IN Point;

 C’’IN Point; D’’IN Point; E IN Point;

Теперь можно записать параметрический запрос, соответствующий запросу 3 (параметрами этого запроса служат экземпляры X и Y понятия GO):

Q(X,Y):?(Dist(F,E)/Dist(F,B))*X.Speed – R;Q.

Чтобы получить ответ на запрос 3, необходимо сделать вызов Q(go1, go2), где go1 и go2 – конкретные экземпляры понятия GO, которые определены для полета бортов № 200357 и № 220498. Предусловием для вызова Q(go1, go2) является то, что, следуя go1, борт № 200357 должен подлететь к борту № 220498 на расстояние, меньшее 200 м. На рисунке этому предусловию отвечает то, что отрезки АВ и C’D’ пересекаются. Поэтому предусловие можно формально записать как EXIST Intersect([A, B], [C’, D’]).

Это предусловие можно включить в параметрический условный конъюнктивный запрос:

? – R;Q;IF EXIST Intersect([A,B],[C’,D’])

 THEN(Dist(F,E)/Dist(F,B))*X.Speed

 ELSE X.Speed

Произвольное предложение ЛД является булевой комбинацией атомов. Это предложение эквивалентным образом может быть преобразовано так, чтобы знак отрицания стоял непосредственно перед атомами. Таким образом, предложение ЛД можно представить положительной булевой комбинацией (то есть с использованием только операций конъюнкции и дизъюнкции) литералов. Поэтому в интегрированной системе ЛД+БМЗ это предложение представляется положительной булевой комбинацией фактов.

Пусть φ – положительная булева комбинация фактов и f – факт. Тогда для выяснения того, что из φ логически следует f, можно применить метод аналитических таблиц. Если на самом деле φ |= f, результатом применения этого метода будет дерево, все ветви которого замкнутые. Ветвь дерева определяет множество {f1, f2, …, fm} фактов. Замкнутость ветви состоит в том, что множество {f1, f2, …, fm} невыполнимо. Интерпретатор ЛД-БМЗ содержит программу, выясняющую невыполнимость множеств фактов. Эта программа реализует алгоритмы, которые являются модификациями предложенных Ф. Яман алгоритмов.

В заключение можно сделать следующие выводы. ЛД, интегрированная в систему БМЗ, позволяет решать такие задачи, как нахождение расположения структурированных движущихся объектов и зоны достижимости для них, поиск областей пересечения траекторий для движущихся объектов и т.п. Структура движущегося объекта оп- ределяется его атрибутами и бинарными отно- шениями с другими объектами (необязательно движущимися). Благодаря этому значительно повышаются выразительность расширенной ЛД и ее адекватность к моделированию реальных приложений.

Литература

1.     Yaman F., Nau D., Subrahmanian V.S. The Logic of Motion. Proc. 2004 Intern. Conf. on the Principles of Knowledge Representation and Reasoning (KR-2004), Whistler, Canada, June 2–5, 2004.

2.     Yaman F., Nau D. and Subrahmanian V.S. A Motion Clo­sed World Assumption. Proc. 2005 Intern. Joint Conf. on Artificial Intelligence (IJCAI-2005), Edinburgh, Scotland, Aug. 2–5, 2005, pp. 621–626.

3.     Yaman F., Nau D., Subrahmanian V.S. Going Far, Logically. Proc. 2005 Intern. Joint Conf. on Artificial Intelligence (IJCAI-2005), Edinburgh, Scotland, Aug. 2–5, 2005, pp. 615–620.

4.     Parker F., Yaman D., Nau and Subrahmanian V.S. Proba­bilistic Go Theories. Proc. 2007 Intern. Joint Conf. on Artificial Intelligence (IJCAI-2007), Hyderabad, India, Jan. 6–12, 2007.

5.     Baader F., McGuinness D.L., Nardi D., Patel-Schneider P.F. The Description Logic Handbook: theory, implementation, and applications. Cambridge, Cambridge Univ. Press, 2nd ed., 2007.

6.     Grau B.C., Рarsia B., Sirin E., Yaman F. Integrating Description Logics and Logics of Motion. URL: http://citeseerx.ist. psu.edu/viewdoc/summary?doi=10.1.1.65.5959 (дата обращения: 18.04.2014).

7.     Cardelli L. Type systems. In: Handbook of Computer Science and Engineering. CRC Press, 1997.

8.     Plesniewicz G.S. Binary Data and Knowledge Model. In: Stefanuk, Kaijiri (eds.) Knowledge-based software engineering. IOS, 2004.

9.     Плесневич Г.С. Формальные онтологии // Открытые семантические технологии проектирования интеллектуальных систем OSTIS-2012: матер. Междунар. науч.-технич. конф. (Минск, 16–18 февраля 2012 г.). Минск: БГУИР, 2012.

10.  Плесневич Г.С. Бинарные модели знаний // Интегрированные модели и мягкие вычисления в искусственном интеллекте: сб. трудов III Междунар. науч.-практич. семинара (Коломна, 15–17 мая 2005 г.). М.: Физматлит, 2005.

References

1.     Yaman F., Nau D., Subrahmanian V.S. The Logic of Motion. Proc. 2004 Int. Conf. on the Principles of Knowledge Representation and Reasoning (KR-2004). Whistler, Canada, 2004.

2.     Yaman F., Nau D., Subrahmanian V.S. A motion closed world assumption. Proc. 2005 Int.l Joint Conf. on Artificial Intelligence (IJCAI-2005). Edinburgh, Scotland, 2005.

3.     Yaman F., Nau D., Subrahmanian V.S. Going Far, Logically. Proc. 2005 Int. Joint Conf. on Artificial Intelligence (IJCAI-2005). Edinburgh, Scotland, 2005.

4.     Parker A., Yaman F., Nau D., Subrahmanian V.S. Probabilistic goes theories. Proc. 2007 Int. Joint Conf. on Artificial Intelligence (IJCAI-2007). Hyderabad, India, 2007.

5.     Baader F., Calvanese D., McGuinness D.L., Nardi D., Patel-Schneider P.F. The Description logic handbook: theory, implementation, and applications. Cambridge Univ. Press, 2nd ed., 2007.

6.     Grau B.C., Рarsia B., Sirin E., Yaman F. Integrating description logics and logics of motion. Available at: http://cite­seerx.ist.psu.edu/viewdoc/summary?doi =10.1.1.65.5959 (accessed April 18, 2014).

7.     Cardelli L. Type systems. Handbook of computer science and engineering. CRC Press, 1997.

8.     Plesniewicz G.S. Binary data and knowledge model. Knowledge-based software engineering. Stefanuk V., Kaijiri K. (eds.), IOS Press, 2004, 336 p.

9.     Plesniewicz G.S. Formal ontologies. Transact. of 2nd Int. Conf. “Open semantic technologies for designing intelligent systems (OSTIS-2012)”. Minsk, BSIR Publ., 2012, 542 p. (in Russ.).

10.  Plesniewicz G.S. Binary models of knowledge. Transactions of 3rd Int. workshop “Integrated models and soft computing in Artificial Intelligence”. Moscow, Fizmatlit Publ., 2005.