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

Программа качественного машинного моделирования, представленная в преды­дущем разделе, главным образом основана на алгоритме QSIM ([84], [85]). Но в целях упрощения введены некоторые различия между программой, приведенной в листинге 20.2, и первоначальным алгоритмом QSIM. В частности, немного иначе трактуются временные интервалы, что позволяет несколько упростить таблицу переходов между качественными состояниями, реализованы не все типы ограничений, данная про­грамма не вырабатывает новые отметки в процессе моделирования, а в алгоритме QSIM все это предусмотрено. Несмотря на эти различия, приведенное ниже описание преимуществ и недостатков в целом относится к методам машинного моделирования, основанным на использовании качественных дифференциальных уравнений.

Начнем с анализа некоторых преимуществ. Как уже было отмечено, задача фор­мирования качественных моделей обычно проще по сравнению с количественными моделями, к тому же качественные модели в большей степени приемлемы для задач некоторых типов. Кроме того, качественное машинное моделирование по типу QSIM имеет существенное преимущество над числовым машинным моделированием в том, что используемый в нем интервал времени моделирования является адаптивным, то­гда как в числовом машинном моделировании интервал времени обычно остается по­стоянным. Такая гибкость качественного моделирования может оказаться особенно удобной по сравнению с числовым моделированием на основе постоянного временно­го интервала в тех случаях, когда поведение моделируемой системы резко изменяет­ся. В качестве иллюстрации подобной ситуации снова рассмотрим ванну. До тех пор

Часть II. Применение языка Prolog а области искусственного интеллет

пока уровень воды остается ниже края (top), система ведет себя в соответствии с ог­раничениями, заданными в модели, а после того как уровень достигает края, может начаться переполнение и переход в другую рабочую область. В связи с этим резко изменяются законы функционирования модели. Поэтому в процессе моделирования важно точно определить тот момент, когда уровень воды достигает края воды. Е ме­тоде QSIM событие, связанное с достижением переменной своей отметки, определяет­ся как качественное изменение, поэтому программа моделирования автоматически фиксирует именно тот момент времени, когда Level=top. С другой стороны, в про­грамме числового моделирования с постоянным временным интервалом вероятность того, что уровень будет точно равен высоте края ванны в один из зафиксированных моментов времени, весьма мала. Более вероятно то, что следующее моделируемое значение уровня будет либо ниже края, либо (что недопустимо) немного выше.

Теперь рассмотрим некоторые проблемы, возникающие в процессе моделирования по методу QSIM. На первый взгляд кажется вполне обоснованным утверждение, что качественное моделирование является более экономичным с вычислительной точки зрения по сравнению с числовым моделированием. Но в действительности, как это ни парадоксально, на практике может оказаться истинным обратное. Причина этого состоит в недетерминированности качественного моделирования. Даже а рассматри­ваемой простой модели ванны формируются три разных варианта поведения, а при использовании более сложных моделей количество возможных вариантов поведения часто растет экспоненциально с увеличением количества переходов между состояни­ем, что может привести к комбинаторному взрыву. При подобных обстоятельствах метод качественного моделирования становится фактически неприемлемым.

В примере с ванной недетерминированность была обусловлена недостаточным объемом информации в модели. Но все три обнаруженные варианта поведения были совместимыми с моделью. Можно действительно найти такие ванны, при заполнении которых водой происходят события, соответствующие трем качественным вариантам поведения, обнаруженным данной программой машинного моделирования. Поэтому вполне оправданно то, что результаты, полученные с помощью этой программы, раз­ветвляются по трем направлениям. Но при использовании машинного моделирова­ния по .методу QSIM возможен также более проблематичный вид комбинаторного ветвления. Моделирование с помощью такого метода может иногда приводить к фор­мированию вариантов поведения, которые не соответствуют какому-либо из конкрет­ных количественных аналогов качественной модели. Такие варианты поведения яв­ляются просто неправильными; они несовместимы с заданной качественной моделью. Эти варианты формально называются фиктивными вариантами поведения (spurious behaviour).

В качестве примера рассмотрим простую колебательную систему, состоящую из скользящего блока и пружины (рис. 20.9). Предполагается, что коэффициент трения между блоком и поверхностью равен нулю. Допустим, что первоначально, в момент времени tO, пружина растянута на свою остаточную длину (X •= zerc) и блок дви­жется с некоторой начальной скоростью vC вправо. После этого значение X возрастет до предела и пружина потянет блок назад, вызывая отрицательное ускорение блока, до тех пор, пока блок не остановится и не начнет движение в противоположном на­правлении. Затем блок пересечет нулевую отметку с некоторой отрицательной скоро­стью, достигнет крайней позиции слева и возвратится в положение X - zero. По­скольку трение отсутствует, можно предположить, что в этот момент времени ско­рость блока снова будет равна vC. В дальнейшем весь этот цикл будет повторяться. Результирующий вариант поведения представляет собой устойчивые колебания.

Проверим эту модель с помощью программы машинного моделирования (см. лис­тинг 20.2). Количественная модель этой системы выглядит так:

А**У. = Ь

Глава 20. Качественные рассуждения

где X — положение блока, А — его ускорение, m — масса, к — коэффициент упруго­сти пружины. Соответствующая качественная модель приведена в листинге 20.5.

пЛАААЛг

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

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

landmarks! х

landmark ks( a,

minf, zero, i n fЬ

* Положение блока % Скорость влока % Ускорение блока

correspond; x:zero, a:zero). [ X, v, A]) :-V)

legalstatet derive У., .,, deriv[ v, A),

MinusA = Й: ,

sum( A, MinusA, a:zero/std), mplus( X, MinusA).

% MinusA = -A

% Пружина тянет блок назад

initial{ [ к:zero/inc, v:vO/std, a:zero/dec]).

Вызовем эту модель на выполнение щего запроса:

?- initial I S), simulate! S, Beh, 11).

Сформированный вариант поведения Beh соответствует ожидаемому вплоть до со­стояния 8, как показано ниже. [ x:minf..zero/inc, v:zero..vO/inc,a:zero..inf/dec]

После этого варианты поведения разветвляются в трех направлениях. В первой ветви поведение развивается следующим образом:

[x: zero/inc,v:vO..inf/std,а:гего/dec)

В данном случае скорость достигает начального значения скорости vO еще до того, как X становится равным нулю. В тот момент, когда X = zero, скорость уже больше vO. Создается впечатление, что при этом возникает ситуация, невозможная с физиче­ской точки зрения, поскольку суммарная энергия в системе возрастает, а сам этот вариант поведения выглядит как возрастание интенсивности колебаний. Во второй ветви за состоянием 8 следуют такие переходы между состояниями:

В данном случае блок достигает позиции X = zero при значении скорости мень­ше vO. При этом суммарная энергия в системе становится меньше, чем в начальном

из начального состояния с помощью следую-

Часть II. Применение языка Prolog в области искусственного интеллекта

состоянии, поэтому создается впечатление, что колебания затухают. А в третьей вет­ви за состоянием 8 следуют переходы [к : zero/inc, v:vO/std,a:zero/dec]

Этот вариант развития событий соответствует ожидаемому варианту с устойчивы­ми колебаниями.

Возникает вопрос: является ли появление этих двух непредвиденных вариантой поведения только следствием отсутствия в качественной модели необходимой инфор­мации, или проблема заключается в самом алгоритме машинного моделирования? Можно показать, что в действительности эта модель, хотя и является качественной, содержит достаточно информации, чтобы допускать формирование только варианта с устойчивыми колебаниями. Поэтому остальные два варианта поведения, с возрас­тающими и затухающими колебаниями, являются математически несовместимыми с данной моделью. Такие варианты называются фиктивными. Недостаток, который приводит к появлению этих вариантов, заключается в алгоритме моделирования. В связи с этим сразу же возникает вопрос о том, почему же нельзя исправить этот дефект в самом алгоритме! Но сложность решения такой задачи состоит в том, что это — не простой дефект, а сложная вычислительная проблема. Для решения ука­панной проблемы необходимо найти способ проверки соответствия качественных ва­риантов поведения всем ограничениям, налагаемым моделью. Алгоритм моделирова­ния по методу QSIM предусматривает проверку совместимости с ограничениями от­дельных состояний, а не всех последовательностей этих состояний в целом. Несмотря на то что удалось найти много способов усовершенствования этого алгоритма, позво­ляющих устранить значительную часть фиктивных вариантов поведения, полное ре­шение этой проблемы еще не обнаружено.

Зная об этом недостатке моделирования по методу QSIM, можем ли мы гаранти­ровать получение приемлемых результатов моделирования? Доказана теорема [84], согласно которой метод QSIM гарантирует выработку всех качественных вариантов поведения, совместимых с моделью. Поэтому неправильные результаты применения этого метода ограничиваются лишь противоположными случаями — при использова­нии метода QSIM наряду со всеми правильными могут вырабатываться и неправиль­ные варианты поведения, несовместимые с моделью (т.е. фиктивные варианты пове­дения). На рис. 20.10 показаны отношения между рассматриваемыми уровнями аб­стракции - обыкновенными дифференциальными уравнениями и их решениями на количественном уровне, с одной стороны, а также качественными дифференциаль­ными уравнениями и качественными вариантами поведения, вырабатываемыми с помощью метода QSIM на качественном уровне, с другой. Те сформированные вари­анты поведения, которые не представляют собой абстракции каких-либо количест­венных решений, являются фиктивными.

Практическая значимость такой "односторонней" правильности метода QSIM со­стоит в следующем. Предположим, что программа машинного моделирования, в ко­торой реализован алгоритм QSIM, сформировала некоторые качественные варианты поведения на основании рассматриваемой модели. Нам известно, что это множество вариантов является полным в том смысле, что в моделируемой системе не существу­ют какие-либо иные варианты поведения, которые еще не включены в состав этих результатов. Мы знаем, что любые другие варианты не могут возникнуть. Но у нас нет гарантии того, что все сформированные варианты поведения моделируемой сис­темы действительно возможны.

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

Глава 20. Качественные рассуждения

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

1 1

- mv² + - кх' = const.

2 2

где п. — масса блока, а к •— коэффициент упругости пружины. Но в данном случае достаточно применить упрощенную версию этого ограничения. А именно, из приве­денной выше формулы сохранения энергии следует, что при X = 0 справедливо вы­ражение V2 = vO2. Эквивалентное ограничение состоит в том, что если V = vO, то X = 0, а если X = 0, то V = vO или V = -vO. При использовании приведенной ниже модификации модели системы, состоящей из блока и пружины {см. листинг 20.5), фиктивные решения не вырабатываются.

legalstatel [ X, V, А]) :-

derivf X, Vj,

deriv( v. A),

MimisA •= а ;_,

sum( A, MinusA, a:zero/std>_P % MinusA = -A

mplus( X, KinusA), % Пружина тянет блок назад

energy[ X, VI. % Слабое ограничение сохранения энергии

energy! X, V) :-

V = v:vO/_, !, У. = x:zero/_ % Если V=vO, то переменная X

% должна окть равна zero

X

x:zero/_, !, V = v:minf..zero/_

% Здесь переменная V % должка Сыть равна -vO

True.

% В прстквном случае X имеет значение, отличное от zero, % и на переменную V не налагаются какие-либо ограничения

ODE

Q3 {фиктивное решение)

DE1

-V-»- S1

DE2

!-*■ S2

ЭЕЗ

S?

Рис. 20.10. Качественные абстракции дифференциальных уравнений и их решений, где QDE — качественная абстрак­ция трех дифференциальных уравнений, DEI, DE2 и DE3. a S1. S2 и S3 - решения этих трех дифференциальных уравнений. Качественные варианты поведения Ql, Q2 и 03 выработаны как решения уравнений QDE; Q1 — качественная абстракция SI, Q2 - абстракция 52 и S3, Q3 - фиктивный вариант, по­скольку он не яеяястся абстракцией решения какого-либо из соответствующих дифференциальных уравнений

Часть II. Применение языка Prolog в области искусственного интеллекта

Резюме

■ Решения, полученные в рамках "теоретической" физики, часто содержат го­раздо больше числовых данных, чем требуется в повседневной жизни, поэтому в подобных случаях более подходящими являются здравый смысл, качествен­ные рассуждения и "обыденные физические представления".

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

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

■ При проведении качественных рассуждений арифметические операции упро­щенно представляются с помощью качественных арифметических действий. Примером может служить качественное суммирование, в котором учитывают­ся лишь положительные и отрицательные знаки, а также нулевыезначения — pos, zero и neg. Как правило, результаты качественных арифметических дей­ствий являются недетерминированными.

■ Качественные дифференциальные уравнения. (Qualitative Differential Equation -QDE) представляют собой абстракцию обыкновенных дифференциальных уравнений. QSIM — это алгоритм качественного моделирования, предназна­ченный для моделей, которые определены с помощью качественных диффе­ренциальных уравнений. Основная предпосылка, лежащая в основе моделиро­вания по методу QSIM, состоит в том, что кривые, на основании которых раз­работана модель, являются гладкими - в пределах одной и той же рабочей области, значения переменных могут изменяться только непрерывно.

■ Сложность обеспечения правильного качественного моделирования состоит в том, что вырабатываемые при этом результаты являются полными, но не все­гда правильными. Можно сравнительно легко добиться того, чтобы программа моделирования выработала все варианты поведения, совместимые с заданными качественными дифференциальными уравнениями. С другой стороны, гораздо сложнее обеспечить формирование только тех вариантов поведения, которые являются совместимыми с заданными качественными дифференциальными уравнениями. Эта проблема известна как проблема выработки фиктивных ва­риантов поведения.

■В этой главе рассматривались следующие понятия:

• качественные рассуждения;

• качественное теоретическое моделирование;

• здравый смысл и обыденные физические представления;

• качественные абстракции;

• отметки;

Глава 20, Качественные рассуждения

качественные арифметические операции;

качественная операция суммирования;

качественное дифференциальное уравнение (Qualitative Differential Equation • -QDE);

монотонные функциональные ограничения;

качественное значение, качественное состояние переменной;

качественное машинное моделирование;

алгоритм QSIM;

применение предположения о гладкости кривых в качественном моделиро­вании динамических систем;

непрерывный переход между качественными состояниями;

фиктивный вариант поведения.