Автоматика и телемеханика, № 3, 2014
Логическое управление
© 2014 г. О.О. ВАСИЛЬЕВ, канд. техн. наук (Институт проблем управления им. В.А. Трапезникова РАН, Москва; Российский государственный университет нефти и газа им. И.М. Губкина, Москва)
ГЕОМЕТРИЧЕСКИ МИНИМАЛЬНЫЕ РЕАЛИЗАЦИИ БУЛЕВЫХ УПРАВЛЯЕМЫХ СИСТЕМ1
Рассматривается новый подход к проблеме генерации — описанию всевозможных систем с заданным внешним поведением — в теории реализации над полукольцами. Введено понятие геометрической редукции и геометрически минимальной реализации, основанное не на введении некоторого инварианта типа размерности, но на преобразованиях произвольных реализаций данного импульсного ответа друг в друга. Проведено исследование этого понятия в случае систем над булевым полукольцом: классифицированы геометрические редукции, изучены различные свойства геометрически минимальных реализаций. Рассмотрен ряд примеров. Рассмотрен один класс редукций, не являющихся геометрическими, с помощью чего объяснена структура некоторых множеств геометрически минимальных реализаций.
1. Введение
Данная работа посвящена рассмотрению одного нового подхода к проблеме генерации в теории реализации линейных стационарных управляемых систем дискретного времени.
Задача (полной) реализации есть задача реконструкции управляемой системы, принадлежащей к некоторому заранее заданному классу, по внешнему поведению этой системы, которое предполагается известным полностью и точно. Обычно считается, что такая реализация должна удовлетворять некоторым условиям минимальности — в классических случаях речь чаще всего идет о минимальности размерности пространства состояний системы.
Впервые эта задача рассматривалась в [1], а теория для случая систем над полями (например, вещественными или комплексными числами) была разработана в 1960-х гг. Р. Калманом, Г. Розеброком, Р. Силверманом, Б. Хо и другими.
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проекты № 11-08-00223-а "Методы 11-оптимизации в теории управления" и № 14-07-00067-а "Современные методы обработки больших объемов данных и их приложения к задачам оптимизации и управления").
В рамках этой теории было показано существование единственной с точностью до замены координат в пространстве состояний реализации минимальной размерности, которая при этом оказывалась достижимой и наблюдаемой.
Впоследствии были построены обобщения этой теории на различные категории. Основателями этого направления стали М. Арбиб, Э. Мейнс, Б. Андерсон, С. Эйленберг [2-4]. Их работы стали предпосылками к развитию теории автоматов в категориях и коалгебр.
Однако данная общая теория не вполне исчерпывала проблемы теории реализации как таковой. Дело в том, что уже в случае систем над коммутативными кольцами оказывается важным рассматривать системы не над произвольными модулями, а, например, лишь над свободными или же проективными, т.е., в частности, такие системы, для которых возможна матрично-векторная запись определяющих уравнений системы.
Тем самым проблематика теории реализации над кольцами и в особенности над полукольцами, такими как М+, М, (тах, +)-полукольца, оказалась существенно отличающейся от таковой в классическом случае. Здесь можно отметить работы Ф. Баччелли, Г. Коэна, С. Гобера, Ж-П. Куадра, Х. Маэда, С. Кодама, Ж. ван ден Хоф и других [5-13].
Следуя обзорам [6, 8], можно выделить следующие проблемы:
1. Описание класса функций, допускающих конечномерную реализацию, -проблема существования.
2. Оценка минимальной размерности конечномерной реализации - проблема минимальности.
3. Алгоритмическое построение канонической (достижимой и наблюдаемой) реализации, реализации минимальной размерности.
4. Описание всевозможных реализаций различного типа (например, минимальной размерности) - проблема генерации.
5. Различные проблемы теории частичной реализации — случай, когда известен лишь определенный "конечный" фрагмент импульсного ответа.
В данной работе рассматривается новый подход к проблеме генерации, главным образом, на примере систем над булевым полукольцом — двухэлементным полукольцом с операциями конъюнкции и дизъюнкции.
Вообще говоря, проблема генерации, которая в наиболее стандартном варианте формулируется как задача описания всевозможных реализаций минимальной размерности — одна из наименее изученных в теории реализации.
Для классического случая систем над полями эта проблема была изучена в работах по алгебро-геометрической теории систем 1970-х-1980-х гг., когда при участии Р. Калмана, Р. Бирнса, П. Фалба, М. Харта, У. Хелмке, В. Ло-мадзе, В.Е. Белозерова, Н.И. Осетинского и других были построены пространства, параметризующие линейные стационарные управляемые системы над полями, и было установлено, что классы эквивалентности минимальных реализаций относительно замены координат в пространстве состояний представляют собой конструктивные алгебраические множества. Этой тематике посвящены, например, монографии П. Фалба [14, 15] и А. Танненбаума [16], обзоры Н.И. Осетинского [17, 18].
В случае систем над кольцами были получены результаты, описывающие границы, до которых верны прямые обобщения результатов относительно систем над полями [19, 20].
Простейшие утверждения о проблеме генерации в теории реализации для положительных систем доказаны в [11, 12].
Наконец, в недавней статье В. Блондел, С. Гобер, Н. Портье [21] было показано, что над полукольцами с идемпотентным (удовлетворяющим тождеству а + а = а) сложением множества реализаций данной функции вход-выход заданной размерности полуполиэдральны, т.е. определяются конечным числом уравнений и неравенств полиномиальных в данном полукольце. Это является аналогом утверждения о конструктивности классов эквивалентности относительно замены координат в пространстве состояний в случае систем над полями. В [21] также представлен алгоритм вычисления таких множеств, имеющий, однако, трижды экспоненциальную сложность.
Особняком стоят работа Л. ле Брюйна и М. Рейнеке [22], посвященная изучению пространства, параметризующего достижимые и наблюдаемые системы всех размерностей одновременно, и статья Э. Зонтага [23], посвященная классификации реализаций минимальной размерности над кольцом и над его полем частных.
В данной работе предложен новый подход к изучению реализаций заданного импульсного ответа или функции вход-выход, основанный не на конструировании реализаций минимальной размерности, а на изучении всех конечномерных свободных (задаваемых в векторно-матричной форме) реализаций и всевозможных их преобразований, редуцирующих реализацию более высокой размерности к реализации меньшей размерности. Эта идея в определенной степени связана с подходом Л. Силвермана [24, 25], который в случае систем над полем рассматривал редукции некоторой реализации произвольной размерности к канонической. Однако в случае систем над полем такая каноническая реализация свободна, а редукция к ней существует и единственна с точностью до эквивалентности, что принципиально отличается от картины, имеющей место в рассматриваемой ситуации.
Статья организована следующим образом. Раздел 2 посвящен формулировке основных определений теории полуколец, теории систем и теории реализации. В разделе 3 вводятся ключевые понятия статьи — понятия геометрической редукции как последовательного рассмотрения свободной подсистемы и свободной факторсистемы и геометрически минимальной системы как системы, у которой не существует геометрических редукций. Также в этом разделе изучена связь геометрически минимальных реализаций с реализациями минимальной размерности, введены понятия достижимой и наблюдаемой аппроксимации канонической реализации. Раздел 4 посвящен введению основных понятий теории булевых линейных стационарных управляемых систем дискретного времени, интерпретации их динамики как потока булевых значений на ориентированном графе. Сформулированы известные ранее результаты относительно теории реализации булевых систем [26-29]. Там же дано описание булевых последовательностей, каноническая реализация которых свободна. В разделе 5 формулируется и доказывается теорема о 6 ре-
дукциях, которая дает описание возможных геометрических редукций для булевых систем. Показано, что свободные подсистемы можно разделить на три класса, связанные с удалением недостижимых элементов канонического базиса, идентификацией неразличимых элементов канонического базиса и с взятием в качестве элементов канонического базиса состояний, имеющих уникальный "маркирующий" элемент. По двойственности Калмана аналогичное утверждение можно сформулировать и для свободных факторсистем. Также в этом разделе показано, что геометрически минимальные реализации не имеют нетривиальных симметрий. Раздел 6 посвящен изучению примеров реализаций различных булевых последовательностей. В частности, для одного класса циклических булевых последовательностей построена серия геометрически минимальных реализаций различной размерности. Их графы оказываются дизъюнктными объединениями ориентированных циклов различной попарно взаимно простой длины. В разделе 7 этот феномен получает свое объяснение. В нем формулируется и доказывается теорема об одной редукции, находящейся за пределами геометрической минимальности. Оказывается, что если некоторая часть графа системы допускает несколько инвариантных относительно динамики системы разбиений множества вершин, которые удовлетворяют свойству "ортогональности", то (несвободная) подсистема, порожденная соответствующим подполумодулем, допускает факторизацию до свободной. В Приложении приведены доказательства полученных результатов.
2. Основные понятия алгебраической теории реализации
Введем определение полукольца — алгебраической структуры, обобщающей понятия кольца и поля, а именно: (коммутативным) полукольцом называется множество с двумя коммутативными и ассоциативными бинарными операциями: сложением и умножением. При этом умножение дистрибутивно относительно сложения, имеется ноль и единица.
Среди примеров полуколец — вещественные, целые, рациональные, комплексные числа, положительн
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.