Садовская О.И.

Белорусский государственный университет информатики и радиоэлектроники, Беларусь

Синтез управления дискретной системы на ориентированном графе

Рассмотрим общее решение задачи синтеза управления дискретной системой, описываемой множеством логических уравнений с временным параметром. Определим состояние некоторой системы 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.