На правах рукописи

Алновайни Гази Хассан Али

«МЕТОД ЛОГИЧЕСКОГО СЕТЕВОГО ОПЕРАТОРА ДЛЯ СИНТЕЗА

УПРАВЛЕНИЯ ДИНАМИЧЕСКОЙ ТЕХНИЧЕСКОЙ СИСТЕМОЙ»

Специальность 05.13.01 - Системный анализ,

управление и обработка информации (промышленность)

Автореферат диссертации на соискание ученой степени кандидата технических наук

Москва 2011 1

Работа выполнена в Российском университете дружбы народов на кафедре Кибернетики и мехатроники Инженерного факультета

Научный руководитель:

доктор технических наук, профессор А.И. Дивеев

Официальные оппоненты:

доктор технический наук, профессор Г.С. Садыхов кандидат технических наук, доцент Е.Г. Андрианова

Ведущая организация:

Смоленский филиал Московского университета путей сообщения (МИИТ)

Защита диссертации состоится 12 мая 2011 года в 16 часов 00 мин. на заседании диссертационного совета Д002.017.03 при Учреждении Российской академии наук вычислительном центре им. А.А. Дородницына РАН по адресу:

119333, г. Москва, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке Учреждения Российской академии наук вычислительного центра им. А.А. Дородницына РАН Автореферат разослан « » _ 2011г.

Ученый секретарь Совета по защите докторских и кандидатских диссертаций А.В. Мухин кандидат физико-математических наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Логическое управление, которое определяется тем, что компоненты вектора управления принимают целочисленные значения из ограниченного множества, в частности из множества {0,1}, сегодня имеет большую прикладную потребность в промышленности в частности в системах принятия решения для эффективного управления потоками в сетях.

Работа посвящена решению задачи синтеза логического управления динамической технической системой. Сегодня не известны общие методы решения задачи синтеза логического управления, когда из постановки задачи на основании заданных критериев и математической модели объекта управления с помощью определенных преобразований получают формально логическую функцию, описывающую зависимость управления от состояния объекта.

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

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

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

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

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

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

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

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

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

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

Новизна научных результатов.

• В применении нового вычислительного метода логического сетевого оператора для синтеза системы логико-функционального управления динамическими объектами.

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

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

Апробация результатов, полеченных в диссертации, подтверждается докладами на семинарах кафедры Кибернетики и мехатроники и на ежегодных конференциях профессорско-преподавательского коллектива Российского университета дружбы народов Результаты диссертации опубликованы в 4 научных трудах, общим объемом 2,5 п.л., из которых 3 работы, объемом 1,5 п.л. опубликованы в журналах, рекомендуемых ВАК РФ. В совместных работах результаты принадлежат соавторам в равных долях.

Структура диссертации. Диссертация состоит из введения, четырех разделов, заключения, списка литературы. Объем работы – 115 страниц, включая 32 рисунка и 5 таблиц. Список литературы содержит наименования.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первом разделе приведена постановка задачи синтеза логического управления динамической технической системой. Управление называют логическим, если каждая его компонента принимает только два значения, например 0 или 1. В рассматриваемой задаче синтеза необходимо найти функцию, которая по значению вектора состояния объекта управления, вычисляет значение вектора логического управления.

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

Синтезированная функция должна по состоянию транспортных потоков на участках дорог сети обеспечивать возможность принятия решения для каждого светофора: «переключаться на следующую рабочую фазу или нет».

Рассмотрим формальную постановку задачи синтеза логического управления. Задана модель объекта управления где x(k ) - вектор состояния объекта управления в такт управления k, x(k ) = [x1 (k ) K xn (k )]T, u(k ) - вектор управления, u(k ) = [u1 (k ) K u m (k )]T, Заданы критерии качества управления Заданы начальное значение вектора состояния объекта управления x(0 ) = [x1 (0 ) K xn (0 )]T Необходимо найти управление в виде где h(x ) вектор-функция, h(x ) = [h1 (x ) K hm (x )]T.

Каждая компонента hi (x ) может принимать целочисленное значение из определенного ограниченного множества целых чисел hi (x ) 0,1,K, u +.

Решением задачи является множество Парето оптимальных решений Задача (1.1)-(1.8) является задачей многокритериального синтеза логического управления. Для решения данной задачи необходимо получить набор логических функций hi (x ), i = 1, m.

Во втором разделе приведено описание метода логического сетевого оператора, который используется для решения задачи синтеза системы логического управления. В результате использования метода синтеза для задач логического управления мы должны получить вектор управления, компоненты которого принимают целочисленные значения из небольшого диапазона. Сами целочисленные значения можно трактовать как логические выводы. При использовании только двух значений управления 0 и 1, логический вывод имеет обычную трактовку, например «истина»-«ложь», или для логического релейного управления «включить»-«выключить» В этом случае полученная синтезирующая функция является предикатом.

Для значений управления из более широкого, чем множество {0,1}, набора целых чисел синтезирующую функцию можно трактовать как функцию многозначной логики с соответствующими значениями, например, для трех значений {0,1,2} «истина»-«ложь»-«неопределенность».

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

Определим множества целочисленных унарных и бинарных операций Множества унарных и бинарных операций приведены в табл. 2.1 и 2.2, соответственно.

В таблицах z + = u + + 1. В множестве целочисленных унарных операций обязательно должна присутствовать тождественная операция 1 (z ) = z.

Бинарные операции должны удовлетворять свойствам ассоциативности и коммутативности.

Пусть аргумент функции принимает, только два значения, u + = 1.

Оставим в табл. 2.1 и 2.2 первые две функции, получим логический сетевой оператор для представления логической функции исчисления высказываний:

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

В качестве примера рассмотрим логическую функцию в нормальной дизъюнктивной форме Программная запись приведенной логической функции имеет вид Графическая запись имеет вид Граф сетевого оператора примера логической функции приведен рис. 2.1.

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

Особенностью задачи синтеза системы логического управления является получение в качестве решения целочисленной функции. Значение функции является вектором, компоненты которого на каждом такте k управления принимают целые значения из ограниченных множеств чисел Для синтеза целочисленной функции управления введем дискретизацию значения вектора потока.

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

Для поиска решения в виде математического выражения используем генетический алгоритм. При построении генетического алгоритма применяем принцип базисного решения, который позволяет осуществлять поиск решения в пространстве вариаций заданного базисного решения. Для логического сетевого оператора используем собственные вариации, которые не меняют количество узлов в графе сетевого оператора. Собственные вариации логического сетевого оператора приведены в табл. 2.3.

Собственные вариации логического сетевого оператора Номер вариации Описание вариации Для описания вариации сетевого оператора используем вектор вариаций из четырех компонент где w1 - номер вариации, w2, w3 - номера узлов для обозначения дуги (w2, w3 ) при вариациях w1 {0,2,3} или номер узла w2 = w3 при вариации с узлом w1 = 1, w4 номер унарной операции при вариациях w1 {0,2} или номер бинарной операции при вариации w1 = 1.

Вариации сетевого оператора меняют функцию, которую он описывает.

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

Для решения задачи синтеза (1.1) – (1.12) определим пространство сетевых операторов где 0 - матрица базисного сетевого оператора, W j - упорядоченное множество вариаций w i, j - вектор элементарных вариаций Каждое множество вариаций определяет сетевой оператор где символ o описывает операцию изменения матрицы сетевого оператора в результате применения к ней вариации, описываемой вектором вариаций.

С учетом условия изменения сетевого оператора под воздействием упорядоченного множества вариаций пространство сетевых операторов (2.13) эквивалентно мультимножеству где j определяется из соотношения (2.16).

Множество (2.17) допускает включение одинаковых элементов, поэтому его называем мультимножеством. Количество сетевых операторов в (2.17) ограничено из-за ограниченной длины l набора вариаций.

Все сетевые операторы используем для решения оптимизационной задачи синтеза (1.1) – (1.12). Для поиска решения используем генетический алгоритм многокритериальной оптимизации. Кодировка решения осуществляем с помощью набора векторов вариации (2.14) и базисного решения 0, которое первоначально может быть выбрано в соответствие с конкретной задачей или может быть выбрано случайно, при условии, чтобы матрица 0 отвечало свойствам сетевого оператора. В процессе вычисления базисное решение меняем на наилучшее, найденное к этому моменту, решение.

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

Сегодня наиболее популярными моделями транспортных потоков являются модели Гриншилдса-Гринберга и Лайтхила-Уизема. Модели описывают движения транспортных потоков на основе гидродинамических дифференциальных уравнений в частных производных первого порядка.

Модели транспортных потоков Кюна и Кернера-Конхойзера используют дифференциальные уравнения второго порядка. Указанные модели рассматривают транспортный поток на основе аналога движения жидкости по трубе.

Перечисленные модели не включают явно управление и не могут использоваться для решения задачи синтеза. В работе используем модель, построенную на основе метода управляемых сетей.

Считаем, что длительности рабочих фаз светофоров кратны некоторой величине, которую называем тактом управления. Реально величина такта управления может составлять 1, 2,…, 10 и более секунд. Переключение фаз светофоров и определения количества транспорта в сети допустимо только на каждом такте управления.

Количество дорог в сети n определяет размерность пространства состояний.

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

где xi (k ) - количество транспорта на i -м участке дороги в k -й такт времени, Количество регулируемых перекрестков m в сети определяет размерность управления.

Состояние рабочих фаз на регулируемых перекрестках сети определяем с помощью вектора управления где u j (k ) - компонента вектора управления, которая определяет рабочую фазы светофора на j -м перекрестке в k -й такт времени, j = 1, m.

Номер рабочей фазы светофора является неотрицательной целочисленной величиной, поэтому компоненты управления являются ограниченным положительными целыми числами, где u + - максимальный номер рабочей фазы светофора на j -м перекрестке, При построении модели первоначально определяем граф сети дорог.

Каждому узлу графа соответствует участок дороги сети, а дуге графа – разрешенный маневр на перекрестке с одного участка дороги на другой. Для описания графа сети дорог используем матрицу смежности где значение aij = 1 указывает на возможный маневр с дороги i на дорогу j.

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

Для описания связи номеров перекрестков с компонентами вектора управления используем матрицу управлений где значение cij 0 указывает на номер перекрестка в сети дорог, где осуществляется маневр с дороги i на дорогу j.

Для описания номеров фаз, разрешающих маневр на перекрестке используем матрицу разрешенных фаз где Fij - множество разрешенных для маневра с дороги i на дорогу j рабочих фаз светофора на перекрестке cij. Если cij 0, то Fij = 0,1,K, uc, иначе При запрещении маневра на перекрестке изменяется конфигурация сети дорог. Для описания изменений конфигурации используем матрицу конфигураций где Характеристика маневров определяет матрица пропускных способностей где bij - указывает на количество транспорта, которое совершает маневр с дороги i на дорогу j за один такт управления.

При наличии альтернативы в маневрах транспорта на перекрестке необходимо располагать информацией о долях транспорта, которые совершают маневр по тому или иному направлению. Такую информацию указывает матрица распределений где dij - указывает в долях количество транспорта, которое должно совершить маневр с дороги i на дорогу j по отношению ко всему транспорту, находящемуся на дороге i.

Согласно определению строки матрицы распределений должны удовлетворять соотношению Математическая модель движения транспортных потоков в сети дорог имеет следующее описание:

x(k + 1) = x(k ) BA(u(k )) BA (u(k )) DA(u(k )) x(k )1T 1n + где 1T = [1 K 1], - операция матричного произведения Адамара, - операция натурально вычитания.

Задано начальное количество транспорта в сети дорог Для участков дорог сети заданы ограничения Заданы критерии качества управления где K f - количество тактов управления, I 0 - множество номеров входных дорог, I1 - множество номеров выходных дорог.

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

где h(x ) - векторная функция, определяющая зависимость номеров рабочих фаз светофоров на перекрестках от количества транспорта на дорогах, в качестве примера рассмотрим сеть дорог, представленную на рис. 3.1.

В сети имеем n = 12 дорог, из которых дороги I 0 = {,K,5} - входные, дороги 6, 7 – внутренние, а дороги I1 = {8,K,12} - выходные.

В сети имеем три системы светофоров, m = 3 регулируемых перекрестка.

Возможные маневры на перекрестках при разрешающих сигналах светофоров на рис. 3.1. показаны пунктирными линиями.

Базовый граф сети дорог приведен на рис. 3.3.

Матрица смежности A базового графа сети дорог и матрица управлений C имеют вид:

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

представленный на рис.3.3.

Рис. 3.3. Граф конфигурации сети при управлении u(k ) = [1 0 2]T Матрица конфигурации графа, представленного на рис. 3.3, имеет вид Если заданы предпочтительные маршруты движения транспортных потоков в сети, то разбиваем поток на слагаемые потоки где xl (k ) - вектор слагаемого потока.

Для описания маршрута движения используем матрицу маршрутов Математическая модель управления транспортными потоками с учетом знания о маршрутах движения имеет вид

T T T T T T

где Bl, Dl, Pl (u(k )) - матрицы пропускных способностей, распределений и конфигураций маршрутов для слагаемого потока xl (k ).

В четвертом разделе рассмотрены вычислительные эксперименты.

В одном из экспериментов рассматривалась сеть дорог с тремя регулируемыми перекрестками, представленная на рис.3.1.

Рассматривался случай, когда части транспортных потоков известны маршруты движения. Маневры для одной части сети дорог приведены на рис. 4.1.

Рис. 4.1. Маневры в сети дорог для части транспортного потока Граф для сети, приведенный на рис. 4.3. представлен на рис. 4.2.

Рис. 4.2. Граф маршрутов для части транспортного потока Матрица путей для данной части потока имеет вид Для второй части потока направления движения не известны, поэтому считаем, что для него матрица маршрутов совпадает с матрицей смежности базового графа сети P 2 = A.

Для обеих частей транспортных потоков должны быть известны матрицы распределений Начальные состояния: x1 (0 ) = [0 256 256 256 256 20 20 0 0 0 0 0]T, Синтезированное с помощью генетического алгоритма управление имело следующий вид:

Значения функционалов составило следующие величины: J1 = 105, J2 = 4.

ЗАКЛЮЧЕНИЕ

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

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

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

3. Сформулирована задача синтеза системы логического управления транспортными потоками в сети городских дорог. Формулировка задачи включает два функционала. Один функционал определяет разность суммарных величин транспортных потоков на всех входных и выходных участках дорог.

Второй функционал учитывает нарушение ограничений на величину транспортного потока на внутренних участках дорог.

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

Программный комплекс апробирован на решении практических задач.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Алновайни Г.Х.А., Дивеев А.И., Пупков К.А., Софронова Е.А. Метод логического сетевого оператора для синтеза управления потоками транспорта в сети городских дорог// Вестник РУДН. Серия инженерные исследования. 2010, № 4. С. 94-102.

2. Алновайни Г.Х.А., Дивеев А.И., Пупков К.А., Софронова Е,А.

Вычислительный метод для синтеза системы управления транспортными потоками в сети городских дорог// Труды ИСА РАН.

Под ред. Ю.С. Попкова Т. 53(1). 2010. С. 94-102.

3. Алновайни Г.Х.А., Дивеев А.И. Синтез системы управления транспортными потоками в сети городских дорог с учетом маршрутов движения// Труды ИСА РАН Под ред. Ю.С. Попкова Т. 53(1). 2010. С. 153-161.

4. Алновайни Г.Х.А., Дивеев А.И., Пупков К.А., Софронова Е.А.

Комплекс программ для синтеза системы управления транспортными потоками в сети городских дорог// Труды международной конференции Инженерные системы 2011. ТЕСИС. Москва 6-8 апреля 2011. С. 204-208.