Файл: Методыискусственногоинтеллекта.pdf

154
Гл. 4. Интеллектуальные динамические системы
Динамическая система, основанная на правилах.
Если X — множество фактов, то каждое правило из П
CL
можно рассматривать как некоторое отображение из 2
X
в 2
X
, а каждое правило из П
T R
— как некоторое отображение из 2
X
× T в 2
X
. Пусть
χ(t) = χ ∈ 2
X
, тогда, обозначив (CL, χ) через Φ(χ), получим функ- цию, которую назовем функцией замыкания. Аналогичным образом,
обозначив (T R, χ) через Ψ(χ, t), получим функцию, которую назовем функцией переходов.
Тогда четверку
D = hX, T , Φ, Ψi,
(4.0)
где
Φ : 2
X
→ 2
X
;
Ψ : 2
X
× T → 2
X
будем называть динамической системой, основанной на правилах.
Разумется, слово динамическая для обозначения такого класса систем выбрано нами не случайно. Под динамической системой пони- мается обычно тройка hU, N, Ψi, где U — топологическое или метри- ческое пространство, N — линейно-упорядоченное множество, а Ψ —
функция из U × N в U [86, 87].
Множество фактов X (т. е. замкнутых атомарных формул языка исчисления предикатов первого порядка) достаточно просто превратить в топологическое пространство, однако сейчас в этом нет необходимо- сти. Важно то, что и в нашем случае очередное состояние системы есть функция предшествующего состояния и времени. Что касается функции замыкания Φ, то она служит для формирования текущего состояния. Можно сказать, что ее применение «очерчивает» границы текущего состояния и, тем самым, снимает вопрос о том, что еще следует включить в состояние.
Заметим здесь, что термин динамическая применяется еще в несколько ином смысле по отношению к таким экспертным системам,
где сами знания системы могут изменяться во времени [91].
Итак, роль стратегии CL и, следовательно, функции Φ системы D
заключаются в пополнении описания текущего состояния; этот про- цесс завершается при стабилизации состояния. Таким образом, всякое состояние такой системы есть решение уравнения неподвижной точки:
Φ(χ) = χ.
(4.1)
Условия существования решения этого уравнения мы рассмотрим ниже; пока же будем считать, что оно существует.

4.3. Управляемые динамические системы, основанные на правилах
155
Траектория системы D есть
{Φ(Ψ(χ(t), t))|t ∈ T },
где χ(t) — решение уравнения (4.1).
При этом функция Ψ обладает следующими свойствами: Ψ(χ, 0) = χ
для любого χ ∈ 2
X
, Ψ(Ψ(χ, t
1
), t
2
) = Ψ(χ, t
1
+ t
2
).
В более привычном виде уравнение траектории системы D можно записать следующим образом:
χ(t + 1) = Φ(Ψ(χ(t), t)).
(4.2)
Понятно, что системы определенного выше класса относятся к си- стемам с дискретным временем и не являются гладкими.
Определение динамической системы, основанной на правилах, в том виде, как мы его здесь сформулировали, является достаточно общим.
Чтобы получить более содержательные утверждения, следует исследо- вать частные случаи и ввести дополнительные ограничения.
Рассмотрим управление в динамических системах, основанных на правилах.
4.3. Управляемые динамические системы,
основанные на правилах
Рассмотрим систему
K = hX, T , Φ, Ψ, U i,
(4.3)
где X, T , Φ и Ψ были определены выше, а
U : 2
X
× T → 2
X
Систему (4.3) будем называть управляемой динамической системой,
основанной на правилах.
При этом так же, как Ψ реализуется стратегией T R и множеством правил переходов П
T R
, функция U реализуется стратегией применения правил управления CN и множеством правил управления П
CN
. Стра- тегию CN опишем несколько позже, а сейчас перейдем к рассмотрению задач устойчивости и компенсации возмущений.
Запишем систему (4.3) в следующем виде:
χ(t + 1) = Φ(Ψ(χ(t), t)
[
U (χ(t), t)),
(4.4)
где функция U — управление.

156
Гл. 4. Интеллектуальные динамические системы
4.3.1. Возмущения. Под возмущением будем понимать некоторое множество событий δ(t), появление которого в состоянии χ(t) не явля- ется результатом решения уравнений (4.4) [84].
Будем полагать, что δ ∈ 2
X
, тогда в отсутствии управления
χ(t + 1) = Φ(Ψ(Φ(χ(t) ∪ δ(t)), t)).
(4.5)
Определение 4.3.1. Траектория Ξ называется устойчивой, если для любого t и возмущения δ(t)
Φ(Ψ(χ(t), t)) ⊆ Φ(Ψ(Φ(χ(t) ∪ δ(t)), t)).
Определение 4.3.2. Функцию Φ будем называть монотонной, если из χ
1
⊆ χ
2
следует Φ(χ
1
) ⊆ Φ(χ
2
).
Определение 4.3.3. Функцию Ψ будем называть монотонной по
переменной состояния, если из
χ
1
⊆ χ
2
следует Ψ(χ
1
, t) ⊆ Ψ(χ
2
, t).
В обоих случаях χ
1
, χ
2
∈ 2
X
Утверждение 4.3.1 (достаточное условие устойчивости) [84]. Тра-
ектория
Ξ системы (4.5) устойчива, если функция Φ монотонна, а
Ψ монотонна по переменной состояния.
Д о к а з а т е л ь с т в о. Действительно, если Φ — монотонна, то
Φ(χ(t)) ⊆ Φ(χ(t) ∪ δ(t)), но тогда если Ψ монотонна по перемен- ной состояния, то Ψ(Φ(χ(t)), t) ⊆ Ψ(Φ(χ(t) ∪ δ(t)), t); отсюда следует
Φ(Ψ(Φ(χ(t)), t)) ⊆ Φ(Ψ(Φ(χ(t) ∪ δ(t)), t)). Применяя к левой части по- следнего включения (4.1), получим требуемое утверждение.
4.3.2. Управление как способ компенсации возмущений. Рас- смотрим теперь более общий случай, когда возмущение присутствует в управляемой системе [85], т. е. рассмотрим систему
χ(t + 1) = Φ(Ψ(Φ(χ(t) ∪ δ(t)), t)
[
U (χ(t), t)).
(4.6)
Зададим следующий вопрос: каким образом, располагая управлени- ем U, компенсировать влияние возмущения δ на поведение системы
(4.6)?
Если система (4.6) является моделью объекта, действующего в непрогнозируемой среде, то ситуация складывается следующим об- разом. В силу непрогнозируемости среды, появление возмущения δ(t)
в состоянии χ(t) предвидеть невозможно, поэтому применение управ- ления U для компенсации этого возмущения возможно не ранее сле- дующего состояния, т. е. состояния χ(t + 1) = Φ(Ψ(Φ(χ(t) ∪ δ(t)), t)).
Здесь выражение Φ(χ(t) ∪ δ(t)) означает замыкание возмущеного состояния χ(t) ∪ δ(t).

4.4. Особенности баз знаний динамических систем
157
Однако в системах, основанных на правилах, такая компенсация может быть реализована посредством применения подходящих правил управления, которые, в свою очередь, суть действия. Это означает, что эффект применения в состоянии χ(t) некоторого правила управления r ∈ П
CN
будет наблюдаться в состоянии χ(t + 1). Иначе говоря, если возмущение появилось в состоянии χ(t), его компенсация возможна в состоянии χ(t + 2).
Таким образом, справедливо следующее утверждение.
Теорема 4.3.1. Для компенсации возмущения δ(t) системы (4.6)
достаточно применения управления [86]:
U (χ(t + 1), t + 1)) = Φ(Ψ(χ(t + 1), t + 1))\Φ(Ψ(χ
′
(t + 1), t + 1)).
Действительно, Φ(Ψ(χ(t + 1)), t + 1)) в правой части утверждения теоремы есть невозмущенное состояние χ(t + 2), в которое система должна была перейти при отсутствии возмущения.
Вторая часть (после знака дополнения) есть выражение для со- стояния χ
′
(t + 2), т. е. Φ(Ψ(Φ(Ψ(Φ(χ(t)
S
δ(t)), t)), t + 1)) — состо- яние, в которое перейдет система после появления возмущения δ
в состоянии χ(t). Таким образом, значение функции U есть та- кое подмножество X, объединения которого с текущим состояни- ем достаточно для выполнения χ(t + 2) ⊆ χ
′′
(t + 2), т. е. устойчиво- сти траектории системы в соответствии с определением 4.3.1 (где
χ
′′
(t + 2) = χ
′
(t + 2)
S
U (χ(t + 1), t + 1)). Пусть теперь траектория устойчива, однако χ(t + 2) ⊆ χ
′
(t + 2) не имеет места, так как, напри- мер, функция Ψ немонотонна. Если существует ∆ — минимальное мно- жество, такое что χ(t + 2) ⊆ χ
′
(t + 2)
S
∆, то ∆ = χ(t + 2)\χ
′
(t + 2), и,
полагая, что ∆ = U(χ(t + 1), t + 1)), получим требуемое утверждение.
Как видно из сказанного, как функция U, так и функции Φ и Ψ
реализуются с помощью подходящих систем правил и соответствую- щих стратегий их применения, т. е. с помощью баз знаний. Поэтому далее будут рассмотрены обеспечивающие устойчивость и компенса- цию возмущений архитектурные особенности баз знаний динамических систем, основанных на правилах [86].
По существу, речь здесь идет о синтезе обратной связи некоторого специального вида, которую уместно назвать обратной связью по тра- ектории.
4.4. Особенности баз знаний динамических систем,
основанных на правилах
В динамических системах, основанных на правилах, множество допустимых управлений определяется множеством П
CN
— множеством

158
Гл. 4. Интеллектуальные динамические системы
правил управления. В частности, задача регулирования, с этой точки зрения, состоит в подборе таких правил из множества П
CN
, которые обеспечивают требуемую коррекцию поведения системы, т. е. возврат очередного состояния на расчетную траекторию. Так как каждое пра- вило, по существу, есть некоторое действие, то первый вопрос, который при этом возникает, это вопрос о допустимости тех или иных дей- ствий в текущем состоянии. С формальной точки зрения этот вопрос сводится к вопросу о применимости требуемых правил. Этот вопрос решается для каждой системы правил (т. е. для каждого класса задач)
отдельно, поэтому здесь мы ограничимся включением в соответствую- щие утверждения условия применимости правил управления. Следует подчеркнуть, что правила управления, хотя формально неотличимы от правил переходов, однако, вообще говоря, это — иные правила и содер- жательно соответствуют тем действиям, которые можно выбирать из множества допустимых. Это, собственно, и делает описываемая ниже стратегия управления. Тем не менее, в ряде систем эти два множества правил могут пересекаться.
4.4.1. Синтез обратной связи по траектории. Теорема 4.3.1
из предыдущего параграфа говорит о принципиальной возможности существования такого управления, которое может компенсировать лю- бое возмущение системы (4.6). Разумеется, при этом не учитываются возможные ограничения, существующие на этом пути. Здесь мы рас- смотрим построение требуемого управления с помощью систем правил,
в которых ограничения на применение того или иного действия будут заданы условиями применимости правила к состоянию.
Иначе говоря, рассмотрим реализацию требуемой функции U с по- мощью множества правил управления П
CN
и стратегии применения правил CN [88]. Для этого введем вначале понятие ранга факта.
Определение 4.4.1. Рангом факта F в последовательности пра- вил П называется величина rank
П
(F ), принимающая значение +1,
если в плане П достижения цели g существует правило R
i
, в списке добавлений которого содержится факт F , и не существует правила
R
j
(j > i), содержащего F в списке удалений. В любом ином случае rank
П
(F ) = −1.
Рассмотрим теперь стратегию CN — синтеза последовательности правил для реализации обратной связи по траектории.
Пусть в результате действия возмущения δ(t) система из состо- яния χ(t) перешла в состояние χ
′
(t + 1) вместо состояния χ(t + 1),
в которое она бы перешла в отсутствие возмущения. Тогда χ(t + 2) =
= Φ(Ψ(χ(t + 1)), t + 1)) — очередное невозмущенное состояние. Зада- ча состоит в том, чобы построить такую последовательность правил,
которая состояние χ
′
(t + 1) преобразует в состояние χ
′
(t + 2), такое

4.4. Особенности баз знаний динамических систем
159
что χ(t + 2) ⊆ χ
′
(t + 2). Обозначим через r текущее правило, C(r),
A(r), D(r) — условие, множество фактов, добавляемых и удаляемых правилом r соответственно; G — текущее множество подцелей, s —
начальное состояние. Обозначим через g
0
= χ(t + 2)\χ
′
(t + 1). В на- чальном состоянии s = G = g
0
; CN — последовательность правил.
Стратегия CN.
Шаг 1. Если G = ∅, то конец, выдать CN;
Шаг 2. Выбрать очередной факт g из s; если g ∈ G, то G = G\g;
Шаг 3. Выбрать из П
CN
такое правило r, что g ∈ A(r) и D(r) ∩ G = ∅;
Шаг 4. s := s∪C(r)\A(r); если C(r) ⊆ χ
′
(t + 1), то CN := hr, CN i,
переход к 1;
иначе переход к 2.
Заметим, что возможны случаи, когда требование C(r) ⊆ χ
′
(t + 1),
либо условие D(r) ∩ G = ∅ не удастся удовлетворить; это означает,
что требуемое управление построить невозможно. Приведенная стра- тегия напомнает алгоритм STRIPS (гл. 3), однако обладает некоторы- ми отличиями: выбираемое на шаге 3 правило не должно содержать в множестве удаляемых фактов подцелей, которые ранее не встрети- лись в списке добавлений. Это означает, что ранг каждой подцели в формируемой последовательности правил должен быть равен +1.
Корректность стратегии CN устанавливается следующей теоремой.
Теорема 4.4.1. Управление U(χ(t + 1), t + 1)) системы (4.6) су-
ществует тогда и только тогда, когда в последовательности П
попарно применимых правил из П
CN
, такой что C(r
1
) ⊆ χ
′
(t + 1)
(где C(r
1
) — условие первого правила последовательности П ), для
каждого факта
g ∈ χ(t + 2)\χ
′
(t + 1) справедливо rank
Π
(g) = +1.
Заметим, что расмотреная задача NExpTime-полна, т. е. относится к тому же классу сложности, что и задача перепланирования, т. е.
задача поиска плана ограниченной длины.
Рассмотрим простой пример.
Пример. Пусть заданы 4 правила:
r
1
= h{a, b}; {c}; {d}i,
r
2
= h{f }; {d}; {e}i,
r
3
= h{b}; {e}; {f }i,
r
4
= h{b, c}; {f }i.
Здесь в каждом правиле через точку с запятой выписаны условие,
множество добавляемых фактов и множество удаляемых фактов соот- ветственно. Начальное состояние s
0
= {b, c, d}. В результате, например применения правил r
3
= h{b}; {e}; {f }i и r
4
= h{b, c}; {f }i, система по- следовательно перейдет в состояния s
1
= {b, c, d, e} и s
2
= {b, c, d, e, f }.
Однако если в состоянии s
0
на систему подействует возмущение

160
Гл. 4. Интеллектуальные динамические системы
δ
0
= {a}, то состояние s
0
= {b, c, d} преобразуется в состояние s
′
0
=
= {a, b, c, d}. К этому состоянию может примениться правило r
1
и система перейдет в состояние s
′
1
= {a, b, c}. Таким образом, возникает задача построения такого управления, которое перевело бы систему из состояния s
′
1
в состояние s
′
2
, такое что s
2
⊆ s
′
2
В соответствии со стратегией CN следует построить последова- тельность правил, достигающих цели {d, e, f} = s
2
\s
′
1
из состояния s
′
1
= {a, b, c}.
Эта последовательность правил такова: CN = hr
4
, r
2
, r
3
, r
4
i. Дей- ствительно, действуя в соответствии со стратегией CN, следует поло- жить g
0
= {d, e, f }. В начальном состоянии s = G = g
0
На первом шаге G 6= ∅, переходим к шагу 2; выбираем из {d, e, f}
факт f; G = G\{f} = {d, e}; выбраем правило r
4
, которое удовлетво- ряет условиям f ∈ A(r
4
) и D(r
4
) ∩ G = ∅. Так как {b, c} ⊆ {a, b, c},
то CN := hr
4
, CNi = hr
4
i, s := s ∪ C(r
4
)\A(r
4
) = {d, e} ∪ {b, c}\∅; пе- реходим к шагу 1; так как G 6= ∅, то выбираем новую подцель,
факт e. Правило, содержащее эту подцель в списке добавлений, —
r
3
. Так как D(r
3
) = {f }, а G = {d, e}; то D(r
3
) ∩ G = ∅; C(r
3
) ⊆ s
′
1
;
полагаем G = G\{e} = {d}, s := {d, b, c}, CN := hr
3
, r
4
i, переходим к шагу 1. Поскольку G 6= ∅, выбираем новую подцель, т. е. d, пола- гаем G = G\{d} = ∅, выбираем правило r
2
, содержащее d в списке добавлений; D(r
2
) ∩ G = ∅. Строим s = {b, c, f }, CN := hr
2
, r
3
, r
4
i.
Так как C(R
2
) = {f }, т. е. C(r
2
) 6⊂ s
′
1
и условие шага 4 не выпол- няется, то переходим к шагу 2, т. е. выбираем правило r
4
, строим s = {b, c, f } ∪ {b, c}\{f } = {b, c}, CN := hr
4
, r
2
, r
3
, r
4
i.
Так как C(r
4
) ⊆ s
′
1
и G = ∅, работа стратегии завершена, CN :=
= hr
4
, r
2
, r
3
, r
4
i.
Предлагаем читателю самому убедиться в том, что применение управления CN, т. е. последовательности правил в порядке слева на- право, переводит систему из состояния s
′
1
в состояние s
′
2
такое, что s
2
⊆ s
′
2
Приведем теперь пример применения развитого здесь подхода в од- ной из прикладных задач.
Пусть некоторое транспортное средство должно переместиться из точки I в точку G, обойдя некоторые препятствия. Маршрут, который будет построен системой управления этого средства, изображен на рис. 4.2, а.
Однако если во время исполнения маршрута (например в точке A)
в систему управления (например от соответствующих датчиков) по- ступает информация о том, что появилось неспрогнозированное пре- пятствие, делающее невозможным перемещение из A в C так, как это изображено на рис. 4.2, а, то система управления выберет переход,
например, в точку B (рис. 4.2, б). Затем из этой точки при примене-