ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
14
УДК 021.8 + 025.1
А . А . М а к с и м о в
ОДИН ПОДХОД К ПОСТРОЕНИЮ КОНЕЧНО-
АВТОМАТНОЙ УПРАВЛЯЮЩЕЙ СЕТИ
Рассмотрена одна из разновидностей конечного автомата с пере-
менной структурой и ее использование как элемента управляющей
автоматной сети. Предложен критерий сложности для указанной
сети и разработана процедура ее построения
.
Приведен пример при-
менения разработанного математического аппарата для построения
системы логического управления робототехническим комплексом.
E-mail:
max2@bmstu.ru
Ключевые слова:
конечные автоматы, сети Петри, критерий
сложности, робототехнический комплекс.
Использование различных разновидностей конечных автоматов
для формального описания как объектов управления, так и управля-
щих устройств, – распространенное явление. Разработан ряд алго-
ритмов синтеза управляющих автоматов и сетей автоматов (напри-
мер, [1–2], [4–6]). При этом синтез одного управляющего автомата по
формальному описанию объекта управления, заданного также в виде
конечного автомата, исследован довольно подробно и не представляет
интереса. В случае же, когда нужно построить управляющую автомат-
ную сеть, оптимальную по какому-либо критерию, возникает необхо-
димость полного перебора вариантов (как известно, проблема постро-
ения структуры управляющей системы в общем случае NP-полна, т. е.
трудоемкость ее решения оценивается экспоненциальной функцией от
размерности задачи). Данная работа посвящена разработке алгоритма
построения конечно-автоматной управляющей сети, оптимальной по
объему занимаемой памяти при ее программной реализации.
Модели объектов и алгоритм их совместного функционирования.
Для описания объектов управления будем использовать частично-
определенные инициальные автоматы Мили, в общем случае – неде-
терминированные, на которые наложены отдельные ограничения, ка-
сающиеся управляемости и наблюдаемости:
0
, , , , ,
,
1, , ,
i
i
i
i
i i i
i
A U X Z f h x X i
n
= <
∈ > = …
(1)