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

4.4. Особенности баз знаний динамических систем
161
Рис. 4.2
нии подходов, описанных в гл. 3, потребуется построить новый план перемещения в G (пунктир на рис. 4.2, б) либо, используя соображе- ния, описанные выше, вернуться в точку C и дальше действовать по имеющемуся плану (рис.4.2, б). Можно показать, что при доста- точно большой величине отношения суммарной площади поверхности,
занимаемой препятствиями, к общей площади поверхности механизм управления поведением будет работать более эффективно, используя возвраты на имеющуюся траекторию, т. е. обратную связь по траекто- рии.

162
Гл. 4. Интеллектуальные динамические системы
ципа обратной связи считается Джон Уатт. Наиболее общие методы исследования устойчивости и основные понятия современой теории устойчивости движения введены А. М. Ляпуновым. Теория глубокой обратной связи изложена в работе [92]. Ораничения этого метода рассмотрены в статье [93]. В работах [94, 95] исследованы новые типы обратных связей, когда целью синтеза регулятора является не сам оператор обратной связи, но алгоритм его формирования [91]. Здесь будет предложен метод поиска алгоритма ситеза обратной связи, также обеспечивающей стабилизацию объекта управления при неизвестном возмущении. Решение этой задачи, как и предыдущей, будем искать на пути синтеза последовательности правил (т. е. алгоритма), компен- сирующей отклонение поведения системы от полученного на этапе синтеза плана. Смысл такой компенсации состоит в том, что всякий раз реальное состояние, отклоняющееся от «планового» в результате вли- яния возмущения, можно расширить некоторым множеством событий таким образом, чтобы «расширенное» состояние включало «плановое»
и тем самым были бы удовлетворены требования определения 4.3.1.
При этом следует подчеркнуть, что само возмущение обычно неизвест- но — известно лишь отклонение текущего состояния от «планового».
Для этого следует выполнить определенные действия, т. е. построить последовательность правил, приводящих к тому, что «плановое» состо- яние становится подмножеством построенного состояния в результате выполнения указанной последовательности. Иначе говоря, для стаби- лизации системы (4.6) достаточно применения такой обратной связи в состоянии χ(t), которая привела бы к построению множества
Ω(χ(t)) = χ(t)\χ
′
(t).
Действительно, если χ(t) есть плановое состояние системы, а χ
′
(t) —
текущее «возмущенное» состояние системы, то Ω(χ(t)) есть то множе- ство событий, которым необходимо пополнить χ
′
(t) для удовлетворения требованиям определения 4.3.1.
Стратегия FB, реализующая требуемую обратную связь, описана ниже.
Стратегия FB. Пусть
χ(t + 1) и χ
′
(t + 1) — плановое и текущее реальное состояния системы соответственно; C(r), A(r) и D(r) суть условие, множество фактов, добавляемых правилом r и множество уда- ляемых им фактов соответственно; g
0
= χ(t + 1)\χ
′
(t + 1). В начальном состоянии s = G = g
0
, F B — последовательность правил.
Шаг 1. Если G = ∅, то конец, выдать F B.;
Шаг 2. Выбрать очередной факт g из s; если g ∈ G, то G = G\g.
Шаг 3. Выбрать из П
CN
такое правило r, что g ∈ A(r) и D(r) ∩ G = ∅.

4.5. Элементы теории управляемости
163
Шаг 4. s := s ∪ C(r)\A(r); если C(r) ⊆ χ
′
(t + 1), то F B := hr, F Bi,
переход к 1;
иначе переход к 2.
Легко видеть, что стратегии CN и FB практически совпадают.
Существенное различие между ними заключается лишь в том, что CN
строит план перехода из состояния χ
′
(t + 1) в состояние χ
′′
(t + 2),
такое что χ(t + 2) ⊆ χ
′′
(t + 2), в то время F B строит план перехода из состояния χ
′
(t + 1) в состояние χ
′′
(t + 1), такое что χ(t + 1) ⊆
⊆ χ
′′
(t + 1).
С этим обстоятельством связаны и особенности применения стра- тегий. Они состоят в том, что если возмущение невозможно скомпен- сировать, то его следует парировать (например, обойти препятствие)
и тогда следует применять стратегию CN, в противном случае —
стратегию FB.
4.5. Элементы теории управляемости
интеллектуальных динамических систем
В задачи настоящего параграфа будет входить изучение областей достижимости систем (4.3), условий достижимости и соответствующих требований к архитектурам баз знаний [83, 86].
Пусть T = {0, 1, 2, ...}. Систему (4.3), как было отмечено выше,
можно записать в следующем виде:
χ(t + 1) = Φ(Ψ(χ(t), t) ∪ U (χ(t), t)),
(4.7)
где χ ∈ 2
X
— множество состояний системы, U — управление, Ψ —
функция переходов и Φ — функция замыкания.
Если задана пара точек (χ
0
, χ
1
) ∈ 2
X
× 2
X
, то задача управляе- мости системы (4.4) состоит в установлении условий существования значений управления U(χ(t), t), позволяющих перевести систему (4.4)
из состояния χ(0) ⊆ χ
0
в состояние χ(N), такое что χ
1
⊆ χ(N ), где
N ∈ T .
Определение 4.5.1. Если 2
X
— множество состояний системы
(4.4), то пара точек (χ
0
, χ
1
) в 2
X
× 2
X
называется N-достижимой,
если существуют такие значения управления U(χ(t), t) (t = 0, 1, ..., N −
− 1) системы (4.4), что χ
1
⊆ χ(N ) при начальных условиях χ(0) ⊆ χ
0
,
где χ(N) — решение уравнения (4.4).
Определение 4.5.2. Система (4.4) называется вполне достижи-
мой, если для любой пары точек
(χ
0
, χ
1
) ∈ 2
X
× 2
X
существует N ∈ T ,
такое что пара (χ
0
, χ
1
) является N -достижимой.
6*

164
Гл. 4. Интеллектуальные динамические системы
Теорема 4.5.1. Пара точек (χ
0
, χ
1
) системы (4.4) N -достижима
тогда и только тогда, когда для каждого факта
F ∈ χ
1
в мно-
жестве П
CN
найдется последовательность П попарно применимых
правил, такая что
C(r
1
) ⊆ χ
0
и
rank
Π
(F ) = +1, где C(r
1
) — условие
первого правила последовательности П.
Д о к а з а т е л ь с т в о. Пусть для каждого F ∈ χ
1
найдется после- довательность попарно применимых правил, такая что C(r
1
) ⊆ χ
0
и rank
П
(F ) = +1. Обозначим множество фактов, построенное с по- мощью этих последовательностей, через ∆. Если χ
′
(N ) — реше- ние уравнения (4.4) с нулевыми значениями управления, то, полагая
χ(N ) = χ
′
(N )
S
∆, а χ(0) = C(r
1
), получим χ
1
⊆ χ(N ) и χ(0) ⊆ χ
0
,
доказав тем самым достаточность условия.
Пусть теперь пара точек (χ
0
, χ
1
) системы (4.4) N -достижима, т. е.
существуют такие значения управления U(χ(t), t) (t = 0, 1, ..., N − 1)
системы, что χ
1
⊆ χ(N ) при начальных условиях χ(0) ⊆ χ
0
, где
χ(N ) — решение уравнения, и пусть для некоторого F ∈ χ
1
не най- дется последовательности П попарно применимых правил, такой, что rank
П
(F ) = +1. Это означает, что факт F не принадлежит χ(N ) и
χ
1
⊆ χ(N ) не имеет места. Точно так же дело будет обстоять в случае,
когда C(r
1
) не принадлежит χ
0
, т. е. последовательность П не приме- нима. Таким образом, теорема доказана полностью.
Теорема 4.5.2. Система (4.4) вполне достижима если и только
если:
а) для всякого F ∈ X справедливо F ∈ A, где A — множество
добавляемых фактов одного из правил,
б) существует последовательность П, состоящая из всех пра-
вил П
CN
, таких что для всякого F из П
CN
справедливо
rank
П
(F ) = +1.
Действительно, если для всякого F ∈ X имеет место F ∈ A, то для произвольного χ ⊆ X можно найти такую подпоследовательность
π ⊆ П
CN
, что χ(0) ⊆ ∆, где ∆ — состояние, полученое в результате применения π к состоянию χ(0), что и означает достаточность условия теоремы.
Необходимость легко доказывается от противного: пусть систе- ма (5) вполне достижима и пусть для некоторого достижимого множе- ства χ а) и/или б) не имеют места. Это означает, что для некоторого
F ∈ χ факт F не принадлежит A и/или rank
П
(F ) < 1. Как первый, так и второй случай приводят к противоречию.
Рассмотрим теперь примеры динамических интеллектуальных си- стем.

4.6. Примеры интеллектуальных динамических систем
165
4.6. Примеры интеллектуальных динамических систем
Пример 1. Проезд нерегулируемых перекрестков
1
). Пусть к не- регулируемому перекрестку подъезжает несколько автомобилей. Преж- де чем приступить к проезду перекрестка, каждый из водителей оце- нивает ситуацию на примыкающих справа и слева дорогах, полосах попутного и встречного движения. Некоторые пытаются вспомнить подходящие правила и лишь затем выезжают на перекресток и продол- жают движение. Если в аналогичной ситуации некоторые из автомоби- лей управляются не водителями, а вычислительными системами, то это означает, что а) «поведение» таких автомобилей должно быть предска- зуемо, б) их системы управления должны обладать «способностями»
к оценке ситуации на дорогах, к выбору и применению подходящих правил дорожного движения.
Далее каждый автомобиль будем рассматривать как динамиче- скую интеллектуальную систему или динамический интеллектуальный агент, действующий в среде других агентов [93].
4.6.1. Описание агентов. Каждый из агентов включает следую- щие компоненты:
• модель автомобиля;
• множество правил;
• параметры (ограничения) процесса безопасного движения;
• базу данных состояний автомобиля (рабочую память) ;
• модель среды (перекрестка).
Модель автомобиля включает:
• идентификатор автомобиля;
• координаты автомобиля;
• вектор скорости автомобиля;
• траекторию движения на перекрестке;
• вектор линейного ускорения;
• положение в соответствии со стороной света;
• полосу проезжей части, по которой движется автомобиль;
• приоритет дороги, по которой движется автомобиль.
Модель среды движения включает:
• взаимные приоритеты дорог;
• геометрические характеристики перекрестка;
• информации обо всех участниках движения.
Ограничения процесса движения:
• перекресток крестообразный;
1
) Пример разработан и реализован С. С. Кузьменковой на основе ПДД
2007 г.

166
Гл. 4. Интеллектуальные динамические системы
• перекресток нерегулируемый;
• в случае однополосного движения запрещен обгон;
• разворот на перекрестке запрещен;
• движение легковых автомобилей;
• разрешенная максимальная скорость движения.
Введем следующие предикатные символы:
PCar (NameCar, Speed, Course, Acceleration), где NameCar — иден- тификатор автомобиля; Speed — скорость автомобиля; Course — пред- полагаемая траектория движения автомобиля; Acceleration — ускорение автомобиля.
PRoad (NameCar, Position, Lane, NumLane, Priority), где
NameCar — идентификатор автомобиля, движущегося по данному участку дороги; Position — положение автомобиля относительно участников движения; Lane — полоса проезжей части, по которой движется автомобиль; NumLane — количество полос проезжей части,
по которой движется автомобиль; Priority — приоритет дороги, по которой движется автомобиль.
Области определения используемых переменных.
Spe Course (направление движения автомобиля в рассматриваемый момент времени):
Значение
Семантика
Примечание переменной
L
На перекрестке автомобиль поворачива- ет налево
R
На перекрестке автомобиль поворачива- ет направо
St
На перекрестке автомобиль едет прямо
Acceleration (ускорение автомобиля в рассматриваемый момент времени):
Значение
Семантика
Примечание переменной
0
Автомобиль едет с постоянной скоро- стью a = 0
+a
Автомобиль движется равноускоренно a — некоторая положитель- ная постоянная
−a
Автомобиль движется равнозамедленно

4.6. Примеры интеллектуальных динамических систем
167
Для перекрестка однополосных равнозначных дорог.
На рис. 4.3 указаны положения участников движения.
Рис. 4.3. Положение автомобилей (см. таблицу Position)
Position (положение автомобиля относительно участников движе- ния):
Значение
Семантика
Примечание переменной
ППЧ
Попутная проезжая часть вблизи пере- крестка
ВПЧ
Встречная проезжая часть вблизи пере- крестка
ПСпПЧ
Примыкающая справа проезжая часть вблизи перекрестка

168
Гл. 4. Интеллектуальные динамические системы
ПСлПЧ
Примыкающая слева проезжая часть вблизи перекрестка

ППЧ
Часть перекрестка, примыкающая к по- путной проезжей части

ПСпПЧ Часть перекрестка, примыкающая к при- мыкающей справа проезжей части

ПСлПЧ Часть перекрестка, примыкающая к при- мыкающей слева проезжей части

ВПЧ
Часть перекрестка,
примыкающая к встречной проезжей части
Lane (полоса движения проезжей части (ПЧ)):
Значение
Семантика
Примечание переменной
LLane
Крайняя левая полоса ПЧ
RLane
Крайняя правая полоса ПЧ
MidLane Средняя полоса ПЧ
NumLane (количество полос движения на ПЧ):
Значение
Семантика
Примечание переменной
1
Одна полоса движения в одном направ- лении
2
Две полосы движения в одном направ- лении
3
Три полосы движения в одном направле- нии
Priority (приоритет дороги):
Значение
Семантика
Примечание переменной
♦
Второстепенная дорога
×
Приоритета нет
Пересечение равно- значных дорог
▽
Главная дорога

4.6. Примеры интеллектуальных динамических систем
169
Course (направление движения автомобиля в рассматриваемый мо- мент времени):
Диапазон
Обозначение скорости
V
0
Нулевая скорость
V
V < V
max
, V
max
— максимально допустимая скорость на участке движения в соответствии с ПДД
Геометрические размеры перекрестка считаем заданными на рисун- ке 4.3.
Введем необходимые функции.
4.6.2. Функции и формулы.
Down(NameCar) — функция уменьшения скорости автомобиля
NameCar и изменения его ускорения на «−a» (торможение).
Семантика: если Down(NameCar)
= −a, то атомарная формула
(Down(NameCar) = −a) принимает истинное значение, иначе — лож- ное. Эту атомарную формулу обозначим через Slow(Down(NameCar)).
Up(NameCar, Vmax) — функция увеличения скорости автомобиля
NameCar не более, чем на максимальную скорость V
max
, и изменения его ускорения на «+a» (разгон).
Семантика: если Up(NameCar)
= a, то формула Speed(Up(Car))
принимает истинное значение, иначе — ложное.
Speed(NameCar) — функция, не изменяющая скорость автомобиля
NameCar и меняющая его ускорение на «0» (равномерное движение).
Семантика: если Acceleration = 0, то формула
Steady(Speed(NameCar))
принимает истинное значение, иначе — ложное.
CanPass(NameCar1, NameCar2) — автомобиль NameCar1 опреде- ляет возможность безопасного проезда перекрестка перед автомобилем
NameCar2.
Семантика: если время проезда перекрестка (выезда за конфликт- ную область) автомобилем NameCar1 меньше времени, за которое
NameCar2 доедет до конфликтной области, то формула принимает истинное значение, иначе — ложное.
DangerZone(NameCar1, NameCar2) — автомобиль (агент) с иден- тификатором NameCar1 определяет конфликтную область между ним и другим агентом с идентификатором NameCar2.
Семантика: функция DangerZone(NameCar1, NameCar2) опреде- ляет конфликтную область для двух автомобилей по следующим пра- вилам: