Садовская О.И.
Белорусский государственный университет информатики и
радиоэлектроники, Беларусь
Синтез управления дискретной системы на ориентированном графе
Рассмотрим общее решение задачи синтеза
управления дискретной системой, описываемой множеством логических уравнений с
временным параметром. Определим состояние некоторой системы S в
форме векторов . Разрядные переменные
принимают следующие
значения: 0,1,* (значение * интерпретируется как неопределенность). Имеются
операторы
, каждый из которых в общем случае можно представить с
помощью двух векторов:
. Первый из этих векторов определяет, в каких (или каком)
состоянии оператор можно применять. Например, если этот вектор имеет вид
<**110>, то оператор можно применить в любом состоянии, где разрядные
переменные
равны соответственно
1,1 и 0, а значения разрядных переменных
во внимание не
принимаются. Второй вектор
определяет, как
изменяет данный оператор состояние системы.
Операторы, будучи применены к текущему состоянию
системы, переводят ее в новое состояние согласно следующему правилу:
1. Пусть текущее состояние и применяется
оператор
. Вектор
должен
соответствовать состоянию
, т.е. в тех разрядах, где
или
значение
и
соответственно либо
(в этом последнем случае значение
во внимание не
берется).
2. Новое состояние системы
будет , причем
Таким образом, можно поставить следующую общую
задачу. Даны исходное и конечное
состояния и набор
управляющих векторов
. Требуется построить цепочку управляющих векторов,
переводящих систему из состояния
в состояние
. Под цепочкой управляющих векторов понимается
последовательность
. Операторы применяются последовательно, слева направо,
причем условия их применения должны выполняться. Рассмотрим
следующую систему операторов:
Сформируем
результирующие векторы для этих операторов:
Сформируем
граф предшествования (рис. 1):
Рис.1. Граф
предшествования
В этом
графе нет циклов. Пусть ,
. Будем строить результирующий
управляющий кортеж. Подбираем управляющий оператор для последнего состояния –
. Подходят два оператора
и
. Это означает, что можно начать
строить две последовательности операторов:
,
.
Начнем
с и получаем новое целевое состояние:
. Однако у оператора
есть предусловие, которое должно быть выполнено в момент старта:
. Это состояние следует совместить с
предварительной новой целью
. Получим новое целевое состояние,
которое должно быть достигнуто в момент выполнения оператора
:
. В этом случае ни один из
операторов применить нельзя. Следовательно, построение цепочки
блокируется. У нас остается цепочка
. Как и выше, находим
предварительное новое состояние:
. C
учетом условия срабатывания оператора
получаем новое целевое состояние –
. К этому новому состоянию применимы
операторы:
,
,
. Это дает нам сразу три цепочки.
Рассмотрим первую из них:
. Здесь применим оператор
:
.
Предварительная
цель: . С учетом условия срабатывания
получим окончательно:
. Ни один оператор не подходит для
этой цели. Цепочка обрывается. Рассматриваем следующий вариант
.
.
. Теперь подходит только оператор
. Получаем:
.
.
. Мы видим, наконец, что исходное
состояние
включено в
. Это означает, что результирующее
построение получено и искомая последовательность имеет такой вид:
.
Оценка
сложности этого варианта синтеза определяется как оценка числа путей в графе.
Разумеется, это оценка чересчур завышена. Тем не менее, пусть – число тупиковых вершин в графе,
– число тупиковых вершин в подграфе исходного графа, получающихся
исключением первых
тупиковых вершин и т.д. Тогда число путей не превышает:
,
.
Можно
использовать оценку вида , где
– число вершин в
графе,
– число слоев
(предполагается, что каждый предыдущий слой связан только с очередным
последующим слоем). Значение в скобках указывает среднее число вершин в слое, теоретически
– на возможность экспоненциального роста числа путей, например, при
.
Однако
все зависит от конкретной задачи, поэтому при отсутствии циклов нужно принимать
во внимание число путей. Если граф предшествования имеет вид дерева, то эта
ситуация наилучшая и с точки зрения вычислительных затрат оценивается по числу
вершин в дереве. Но даже и при наличии циклов ситуация может быть вполне
благоприятной с вычислительной точки зрения.
Подобного
рода алгоритмы могут использоваться в задачах типа отыскания пути на местности.
Литература:
1. Нильсон Н. Искусственный
интеллект: методы поиска решений =
Problem-solving Methods in Artificial Intelligence / Пер. с англ. В. Л.
Стефанюка; под ред. С. В. Фомина. – М.: Мир, 1973. – С. 70- 80.
2. Герман, О.В. Одна
полиномиально разрешимая задача синтеза поведения интеллектуального робота /
О.В. Герман, Д.В. Семерюк // Автоматика и телемеханика. – 2001, №2. – С. 15-
24.
3. Герман, О.В. Синтез
управляющего алгоритма в системе продукционных правил с временным параметром /
О.В. Герман, Д.В. Занько // Автоматика и телемеханика. – 2003, № 5. – С. 41-52.