Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

SYMBOLIC REGRESSION METHOD BASED ON NETWORK OPERATOR TO SOLVE THE PROBLEM OF CONTROL SYNTHESIS

Diveev A.I. 1 Shmalko E. Y. 1
1 Institution of Russian Academy of Science Dorodnicyn Computing Centre of RAS
The paper concentrates on the problem of control synthesis that is to find a multi-dimentional control function which depends on the coordinates of the state space. Such problem to search a needed mathematical expression relates to symbolic regression tasks. Nowadays it becomes possible to use a computer for symbolic regression calculations. A symbolic regression method based on the network operator is proposed in order to automate the search of a control function. The network operator is a special data structure that allows to present any mathematical expression in the form of a matrix with numbers of unary and binary operations as elements. Changing the elements of the matrix allows to receive new mathematical expressions. Such approach makes possible the usage of various search algorithms to find an optimal mathematical expression. The intellectual evolution algorithm is applied for searching. The paper provides a numerical example of path motion of mobile robot with constraints of state.
mobile robot
genetic algorithm
network operator
control synthesis
regression

Введение

Символьная регрессия представляет собой процедуру написания математических выражений для выявления закономерностей по экспериментальным данным, идентификации моделей исследуемых систем и определения функциональных зависимостей в многофакторном анализе денных. В подавляющем большинстве случаев символьная регрессия выполняется исследователем вручную. Разработчик записывает математическое выражение с точностью до значений параметров. Вычислительный алгоритм использовался для поиска оптимальных значений параметров. После появления генетического программирования [8] стало возможным выполнять символьную регрессию с помощью вычислительной машины. Генетическое программирование использует эволюционный вычислительный алгоритм для поиска решений в форме строки символов. Строка символов при этом кодирует различные часто нечисловые структуры: электронные цепи, химические реакции, технические конструкции и др. К задачам символьной регрессии следует также отнести и задачу синтеза управления. В работе рассматривается метод машинной символьной регрессии на основе метода сетевого оператора [2] для решения задачи синтеза управления.

Постановка задачи

Рассмотрим постановку задачи синтеза управления [1,3].

Задана математическая модель объекта управления

, (1)

где – вектор состояния объекта управления, , , – вектор управления, , , , – ограниченное замкнутое множество.

Задано множество начальных значений

. (2)

Заданы терминальные условия или цель управления

, . (3)

Задан критерий качества управления в виде функционала

, (4)

где – время управления, которое может быть не задано и определяться по условию (3) достижения цели управления.

Необходимо найти управление в виде многомерной функции от компонент вектора пространства состояний

. (5)

Функция должна обладать следующими свойствами. Функция должна удовлетворять ограничениям на управление

, . (6)

При подстановке функции в модель объекта управления (1) получаем систему дифференциальных уравнений . Полученная система уравнений для любого начального значения из заданной области (2) начальных значений имеет решение в форме векторной функции времени . Данное решение за конечное время достигает цели управления (3)

, , (7)

и обеспечивает минимум функционалу (4) качества управления на множестве всех допустимых управлений , удовлетворяющих ограничениям ,

. (8)

Поскольку при решении задачи синтеза необходимо найти вид многомерной функции, то данную задачу следует отнести к классу задач символьной регрессии. Машинные методы символьной регрессии появились с возникновением генетического программирования [8]. В настоящей работе рассматривается решение задачи синтеза управления на основе метода сетевого оператора [2], который относится также к методам символьной регрессии.

Метод сетевого оператора

Сетевой оператор предназначен для описания математических выражений, построенных на множествах переменных, параметров, унарных и бинарных операций.

Множество переменных

. (9)

Множество параметров

. (10)

Множество унарных операций

. (11)

Множество бинарных операций

. (12)

Сетевой оператор представляет собой ориентированный граф со следующими свойствами:

a) в графе отсутствуют циклы;

b) к любому узлу, который не является источником, имеется хотя бы один путь от источника;

c) от любого узла, который не является стоком, имеется хотя бы один путь до узла-стока;

d) каждому узлу-источнику соответствует элемент из множества переменных или параметров;

e) каждому узлу соответствует бинарная операция из множества бинарных операций ;

f) каждой дуге соответствует унарная операция из множества унарных операций .

Любой ориентированный граф с указанными свойствами соответствует какому-либо математическому выражению. Для перевода сетевого оператора в математическое выражение необходимо руководствоваться следующими правилами:

- вычисление унарной операции выполняем только для дуги, которая выходит из узла, не имеющего входящих дуг;

- удаляем дугу из графа после вычисления унарной операции;

- выполняем бинарную операцию в узле сразу после того, как выполнена унарная операция, приводящая в данный узел;

-заканчиваем вычисления, как только пройдены и удалены все дуги в графе.

Рассмотрим сетевой оператор, представленный на рис.1 с двумя узлами-источниками.

fig1

Рис.1. Пример сетевого оператора

Согласно правилам, сначала находим узел-источник, не имеющий входящих дуг. Примем за узел-источник . Далее выбираем исходящую их этого узла-источника дугу и вычисляем бинарную операцию, обозначенную в том узле, куда приводит выбранная дуга. Если бинарная операция для данного узла ранее не выполнялась, то первым аргументом для бинарной операции является единичный элемент данной операции. Вторым аргументом является результат унарной операции, приводящей в данный узел. Так на первой итерации результат бинарной операции равен результату унарной операции. Удаляем дуги и переходим к графу, представленному на рис. 2.

fig2

Рис. 2. Пример сетевого оператора после 1-ой итерации

Далее в соответствии с правилами a)-d) выполняем все последующие итерации. Если бинарная операция для данного узла выполняется не первый раз, то ее предыдущий результат присваивается одному из ее аргументов. Выполняем вычисления, пока имеется хотя бы одна дуга в графе.

fig3

Рис. 3. Пример сетевого оператора после 2-ой итерации

fig7

Рис. 4. Пример сетевого оператора перед последней итерацией

fig8

Рис. 5. Пример сетевого оператора после всех итераций

В результате получаем четыре математических выражения:

, , , .

Итоговый вид математических выражений зависит от элементов множеств унарных и бинарных операций. В работе [2] используют 24 унарных и 8 бинарных операций.

, , , , , , , , , , , , , , , , , , , , , , , ,

, , , , , , , .

Все бинарные операции являются коммутативными, ассоциативными и имеют следующие единичные элементы. Нумерация бинарных операций начинается с нуля, так чтобы номера наиболее часто используемых операций сложения и умножения совпадали с их единичными элементами.

Подставим элементы описанных множеств в полученные после вычислений по примеру сетевого оператора математические выражения, получаем

,

,

,

.

В памяти компьютера сетевой оператор представляется в виде матрицы сетевого оператора (NOM = Network Operator Matrix). Она формируется на основе матрицы смежности орграфа , , , где – количество узлов в графе.

Рассмотрим сетевой оператор, представленный на рис.1. Первоначально пронумеруем узлы графа, используя топологическую сортировку: номер узла, откуда выходит дуга, должен быть меньше номера узла, куда входит дуга. На рис. 6 приведен граф сетевого оператора с топологической нумерацией узлов.

fig10

Рис. 6. Граф с топологической нумерацией

Граф, представленный на рис.10, имеет следующие матрицу смежности и матрицу сетевого оператора.

, .

Матрицы сетевого оператора не достаточно для написания математического выражения, так как она не хранит данных о переменных и параметрах. Эта информация содержится в начальных значениях вектора узлов , который в процессе вычисления используется для хранения промежуточных результатов.

Для получения математического выражения по матрице сетевого оператора необходимо пройти по каждому ряду последовательно . В каждом ряду мы рассматриваем элементы, следующие за диагональным элементом . Если встречается ненулевой элемент, то производим вычисления согласно уравнению

если. (13)

где , .

Для рассматриваемого примера имеем

,, , , , , , , ,, , , , , .

В результате получаем те же результаты, что и при вычислении по графу: , , , .

Синтез управления мобильным роботом

Математическая модель объекта управления имеет вид [4,6]

, (14)

, (15)

, (16)

где , − координаты положения центра масс объекта на плоскости, φ – угол между вектором скорости объекта и осью , , − компоненты вектора управления , регулирующие уровень напряжения на левом и правом двигателях колес робота.

Заданы ограничения на управление

, . (17)

В отличие от модели из [6,7] компоненты управления могут иметь отрицательные значения, обеспечивающие движение робота назад.

Задано терминальное состояние

. (18)

Задано множество начальных условий

(19)

Заданы функционалы, определяющие критерии качества управления

, (20)

, (21)

где индекс означает, что вычислено для начальных условий ,

,

– малая положительная величина; − заданное максимальное время процесса управления.

Задача синтеза заключается в нахождении функции управления. Необходимо синтезировать систему управления в виде

, (22)

, (23)

где − вектор параметров, который также ищем в процессе решения задачи.

Для решения рассматриваемой задачи синтеза (1)–(8) согласно методу сетевого оператора было сформировано базисное решение.

, (24)

, (25)

где .

При синтезе задано терминальное состояние и множество начальных условий

.

Для получения решения был использован программной комплекс для синтеза систем управления методом интеллектуальной эволюции [4, 5].

В результате было получено следующее решение

, ,

где , , , .

Траектория движения объекта из четырех начальных положений, при которых осуществлялся синтез управления, представлена на рис.7.

Рис. 7. Траектория движения объекта при синтезированном управлении

На рис. 8 представлено движение робота от точки к точке в обход заданных препятствий. Графики управлений приведены на рис. 9 и 10.

pic1_y_x

Рис. 8. Движение объекта по заданной траектории

pic3_ul_t

Рис. 9. Компонента управления при движении объекта по траектории

pic4_ur_t

Рис. 10. Компонента управления при движении объекта по траектории

По результатам графиков видно, что нелинейная синтезированная система управления позволяет двигаться мобильному роботу практически точно по заданным точкам траектории. Характер пути вполне сохраняет форму траектории, но в каждой заданной точке при получении новой цели управления происходит коррекция направления движения.

Из сказанного следует вывод, что метод сетевого оператора позволяет синтезировать нелинейную систему управления, обеспечивающую качественное движение мобильного робота по траектории.

Работа выполнена по теме гранта РФФИ № 11-08-00532-а.

Рецензенты:

Дикусар Василий Васильевич, профессор, доктор физико-математических наук, главный научный сотрудник отдела прикладных проблем оптимизации Федерального государственного бюджетного учреждения науки Вычислительного центра им. А. А. Дородницына Российской академии наук, г. Москва.

Юрков Николай Кондратьевич, профессор, доктор технических наук, заведующий кафедрой конструирование и производство радиоаппаратуры Пензенского государственного университета, г. Пенза.