Содержание к диссертации
Введение
ГЛАВА 1. Анализ функционирования системы планирования маршрута полета и общая постановка задачи
1.1. Описание функционирования системы космического наблюдения при съемке наземных объектов с помощью орбитального КА
1.2. Анализ известных методов планирования маршрута
1.2.1 .Постановка задачи
1.2.2. Метод полного перебора
1.2.3. Обучение нейронной сети с помощью метода ветвей и границ для решения задачи коммивояжера
1.2.4. Использование генетического алгоритма
1.2.5. Метод локального поиска
1.2.6. Эвристический поиск маршрута
1.2.7. Выбор эвристического метода
1.2.8. Приближенное решение задачи коммивояжера большой размерности
1.3. Общий подход к решению задачи выбора критерия маршрутизации в процессе самообучения
1.4. Общая постановка задачи
ГЛАВА 2. Формирование процедуры получения первоначальных аналитических знаний на основе самообучения
2.1. Формирование функции риска для выбора альтернативного направления полета в случае исходного критерия минимума длины маршрута
2.2. Исследование зависимости коэффициентов функции риска принятия решений от сложности обучающих примеров
ГЛАВА 3. Воссоздание вариантов математической модели интегрального функционала качества маршрутизации с помощью решения обратной задачи динамического программирования
3.1. Исходные условия решаемой задачи
3.2. Подход к решению задачи альтернативного выбора, основанного на методе рабочей точки
3.3. Формирование простейшей математической модели критерия приоритетного
обслуживания пунктов назначения, расположенных в задней полусфере
3.4. Формирование других простейших моделей критерия оптимальности поведения при других функциях предпочтения в выборе маршрута съемки
ГЛАВА 4. Формирование правила оптимального поведения при планировании космической съемки с учетом реальных динамических свойств космического аппарата
4.1. Постановка «прямой» задачи динамического программирования и особенности ее решения
4.2. Расчет оптимального правила выбора очередного наземного объекта для съемки в случае приоритетного обслуживания в задней полусфере
4.3. Расчет оптимального правила выбора очередного объекта для съемки в случае приоритетного обслуживания в передней полусфере
ГЛАВА 5. Моделирование системы планирования маршрута
5.1 .Исходные данные для процесса моделирования
5.2.Моделирование системы планирования в случае приоритетного обслуживания объектов, расположенных в «задней полусфере»
5.3.Моделирование системы планирования в случае приоритетного обслуживанияобъектов, расположенных в «передней полусфере»
5.4.Оценка возможности реализации процесса самообучения с помощью нейроподобных структур
Заключение список литературы
- Описание функционирования системы космического наблюдения при съемке наземных объектов с помощью орбитального КА
- Формирование функции риска для выбора альтернативного направления полета в случае исходного критерия минимума длины маршрута
- Исходные условия решаемой задачи
- Постановка «прямой» задачи динамического программирования и особенности ее решения
Введение к работе
Проблема оперативного планирования космической съемки и управления космической системой наблюдения (КСН) относится к тем сложным задачам, когда наряду со строгими методами оптимизации необходимо творческое участие человека, использование его интеллектуальных возможностей. Однако, с дефицитом времени на принятие решений это участие невозможно, и поэтому целесообразно применить методы искусственного интеллекта (ИИ) и интеллектуальные системы управления.
В практике управления сложными техническими объектами (ОУ), такими, как космический аппарат (КА), существуют задачи, когда в меняющихся условиях полета нужно использовать различные критерии оптимальности поведения, чтобы добиться в целом максимальной эффективности.
Как принято в структуре системы интеллектуального управления [1,2,7,8], процесс формирования цели управления, относится к стратегическому уровню принятия решений. Традиционный подход к решению задачи управления объектом предполагает известным заданный в формализованном аналитическом виде критерий качества поведения и динамические свойства объекта, а вследствие этого искомым является закон управления. При этом рассматривается так называемая «прямая» задача оптимального управления -заданы минимизируемый функционал потерь, система дифференциальных уравнений, описывающих поведение объекта, требуется найти оптимальное управление как функцию текущего состояния объекта.
Однако в сложных реальных условиях в задачах управления существуют случаи, когда в меняющейся динамической обстановке возникает необходимость изменять критерии поведения всей системы. В том числе существуют задачи управления, эффективность которых достигается по мере накопления опыта при совершенствовании способа управления, хотя формализованный критерий оптимальности остается заранее неизвестным. Но при известном правиле поведения и известной динамике объекта в
принципе можно попытаться воссоздать исходный критерий оптимальности, чтобы затем применить его для управления новым объектом и тем самым решить актуальную проблему более эффективного использования его свойств. В результате накопления опыта в процессе самообучения можно уточнять формализованные модели критерия оптимальности. Таких критериев может быть несколько в зависимости от динамической обстановки. Поиск и выбор критериев является одной из важнейших, интеллектуальных процедур принятия решений [3,4,5].
На рис. 1.1 представлена общая схема интеллектуальной системы управления. На нижнем уровне показана традиционная система автоматического регулирования с сигналами рассогласования, управления и и состояния объекта х. На верхнем стратегическом уровне имеется классификатор ситуации, а также блок выбора критериев, математические модели которых надо сформировать.
Рис. 1.1. Структура системы интеллектуального управления полетом.
Таким образом, возникает необходимость решения «обратной» задачи: по наблюдениям за объектом с известными свойствами становится известным в результате самообучения рациональное правило управления им, заданы также новые свойства другого объекта. Требуется: восстановить вначале применяемый критерий при известном объекте, а затем «присоединить» новые свойства другого объекта и при решении «прямой» задачи найти «новое правило» управления [6].
Такой подход открывает путь эффективного распространения имеющегося опыта на новые сферы применения. Например, известен способ управления тяжелым слабоманевренным самолетом, и нужно найти закон управления легким маневренным беспилотным самолетом-роботом, или есть опыт поведения человека в игровых задачах, а его надо перенести на группу подвижных роботов с другими свойствами. Наконец, основной пример - известен эффективный способ управления функционирующим на орбите КА, осуществляющим космическую съемку, а нужно найти закон управления новым перспективным КА с новыми динамическими свойствами, чтобы добиться при различной плотности скопления наземных объектов на траверсе наибольшего числа снимков.
Принципиальное отличие рассматриваемого подхода состоит также в том, что обычно внешняя среда рассматривалась как возмущение на объект, а регулятор был функцией вектора координат его состояния. Теперь же изменения внешней среды непосредственно влияют на показатели критериальной части системы, оцениваемые при решении обратной задачи динамического программирования, а уже потом закон управления перестраивается под новые условия [9,10,11].
В частности этот подход может быть использован в задаче космической съемки наземных объектов с орбитального комплекса на заданной орбите с ограниченной угловой скоростью вращения телескопа. В этой задаче весьма важно не пропустить заданные
объекты наблюдения, а с другой стороны, если их много, выбрать наиболее удобные с точки зрения затрат на время обслуживания.
Таким образом, для различных случаев динамической обстановки желательно использовать различные критерии обслуживания объектов наблюдения: когда объектов мало - выбор критерия должен обеспечить обслуживание всех объектов; если объектов много - критерий обслуживания наиболее удобных объектов с целью съемки их максимального числа, явно меньшего, чем их общее количество. Следовательно, становится актуальной задача альтернативного выбора критерия поведения системы в зависимости от динамической обстановки. Как показали результаты предварительного моделирования на ЭВМ, при выборе 2-х критериев вместо одного эффективность обслуживания увеличивается на 10%, а при дальнейшем увеличении числа критериев хотя и растет, но незначительно [44].
В данной работе получены результаты эффективного использования двух критериев, предусматривающих различение двух классов динамических ситуаций -случаи «малого» и «большого» скопления наземных объектов на контролируемой территории.
Очевидно, что использование данного подхода выгодно экономически, т.к. позволяет обслуживать большее количество наземных пунктов или сократить количество космических аппаратов (КА) на обслуживание заданного количества наземных объектов.
Целью данной работы является разработка методов и процедур получения на основе самообучения правил управления прототипом КА, воссоздания интегральных функционалов простейшего вида, и на их основе получить правила управления новым объектом.
Положения, выносимые на защиту:
1.метод воссоздания интегрального критерия оптимальности с помощью правила выбора маршрута полета, полученного на основе самообучения;
2.представление функции риска в выборе очередного объекта космической съемки в виде степенного полинома второго порядка с учетом динамических свойств и ресурсных ограничений КА;
3.результаты моделирования на ЭВМ космической съемки в зависимости от высоты орбиты и количества наблюдаемых пунктов.
Научная новизна работы заключается в следующих результатах:
1.В результате самообучения показано, что не существует однозначной возможности получения единого правила выбора маршрута для различных условий полетной ситуации -числа наблюдаемых объектов в передней и задней полусфере. Предложено использовать четыре простейших модели правила поведения с абсолютным и относительным приоритетом обслуживания в передней и задней полусферах.
2.На основе динамического программирования разработана процедура нахождения минимизируемой функции риска в выборе очередного пункта космической съемки, учитывающая динамику КА. Показано, что найденную функцию возможно представить в виде области притяжения, имеющую вид окружности, центр которой смещается в переднюю полусферу при увеличении объектов наблюдения, находящихся в передней полусфере.
3.Результаты моделирования показали, что совместное применение двух критериев увеличивает производительность КСН на 10-15 % по сравнению с использованием единственного правила поведения.
4.Показано, что в зависимости от высоты орбиты область притяжения целесообразно представлять в виде эллипса, центр которого смещается вправо и деформируется в зависимости от числа объектов передней полусфере.
5.Предложена реализация полученных процедур с помощью нейроподобных структур, что делает возможным применение их как в наземном комплексе, так и на борту КА.
Методы исследования: теоретической и методологической основой исследования являются методы искусственного интеллекта, численные методы оптимизации, метод динамического программирования, методы теории автоматического управления.
Достоверность результатов подтверждается использованием научно обоснованных методов динамического программирования и искусственного интеллекта, а также результатами моделирования на ЭВМ.
Практическая значимость данной работы определяется, во-первых, ожидаемым повышением эффективности космической съемки на 10-15%, что подтверждается актом о внедрении НПО им. Лавочкина. Во-вторых, найденная процедура удобна для реализации на борту КА и в наземном комплексе управления полетом. Кроме того, полученные результаты внедрены в учебный процесс кафедры №301 МАИ в виде лабораторной работы «Планирование космической съемки на основе самообучения» по учебному курсу «Интеллектуальные системы управления» для специальности 21.01.00 «Управление и информатика в технических системах».
Апробация работы: Основные положения и результаты работы докладывались на конференциях и семинарах, частности на XIII Научно-технической конференции "Экстремальная робототехника" (г.С.-Петербург, 2002 г.), на ежегодном Международном научно-техническом семинаре "Современные технологии в задачах управления, автоматизации и обработки информации" (г.Алушта, 2000 -2002 г.г.).
Базовые положения и результаты исследований отражены в 8 публикациях.
Структура и объем работы: диссертационная работа состоит из введения, 5 глав, заключения, списка литературы и приложения. Основная часть работы изложена на 117 страницах, содержит 15 рисунков, 8 таблиц, 1 приложение.
Описание функционирования системы космического наблюдения при съемке наземных объектов с помощью орбитального КА
Планирование космической съемки является одной из задач маршрутизации движения, когда траектория полета должна проходить через заданные пункты [12]. Картина космической съемки показана на рис. 1.2. Для того, чтобы описать процесс функционирования космической системы наблюдения, нужно рассмотреть следующие необходимые компоненты - данные о наземных объектах, данные о летательном аппарате, динамику углового движения КА как ОУ, критерий оптимальной космической съемки, обеспечивающий максимальную эффективность космической системы наблюдения. Что касается наземных объектов, будем считать, что в данной работе рассматриваются точечные объекты (аэродромы, порты, населенные пункты, корабли и т.д.) и поэтому каждый объект характеризуется координатами Xj, у, точки съемки, а также в общем случае - относительной важностью bt полученного снимка. Предполагается, что состав объектов заранее известен. Считается, что съемка производится с помощью группировки орбитальных космических аппаратов, каждый из которых имеет свою полосу обзора на витке, а общее число КА обеспечивает полноту наблюдения всех объектов. В свою очередь каждый КА имеет оптическую систему - телескоп (хотя наблюдение может осуществляться в других диапазонах - инфрокрасном, радиолокационном, радиационном). КА движется по заранее определенной орбите и управление центром тяжести не производится. Главная возможность управления наблюдением за наземными объектами заключается в угловом движении телескопа при перенацеливании с одного объекта на другой. Известно, что в самом общем случае режим управления угловым движением при перенацеливании состоит из 5 этапов: разгон в сторону нового, интересующего нас объекта; этап движения в ту же сторону с постоянной ограниченной угловой скоростью; этап «торможения» для снижения угловой скорости к необходимому минимуму; этап «успокоения», необходимый для демпфирования колебаний оптической системы; этап самой съемки с определенным прецизионным слежением, обеспечивающим минимум «смаза» изображения.
Этапы непосредственно самой съемки и успокоения имеют самостоятельное значение и не относятся к проблеме маршрутизации, поэтому они не рассматриваются в данной работе. Кроме того, в данной работе для упрощения искомого решения исследуются этапы «разгона» и «торможения», считая процесс углового движения с постоянной угловой скоростью непродолжительным. Динамика углового движения КА в упрощенном виде может быть описана дифференциальными уравнениями следующего вида: где и і и2 - угловое ускорение оптической оси телескопа (град/с2), ограниченное максимальным значением 8; w - приведенная угловая скорость космического аппарата, возникающая за счет поступательного движения КА по орбите и последующего перемещения оптической оси телескопа вдоль земной поверхности. Приведенная угловая скорость КА вычисляется по формуле где WKA - угловая скорость КА относительно центра Земли, а м з - угловая скорость вращения Земли. Угловую скорость КА можно приближенно представить как отношение мгновенной линейной скорости FKA к сумме (Н+Лз) Определяющим фактором планирования съемки наземных объектов является критерий оптимальности. Здесь нужно сделать замечание, уточняющее это понятие и отличающее данную работу от известных подходов. Дело в том, что необходимо различать понятие общего критерия эффективности системы и частных критериев оптимальности съемки в определенной динамической обстановке. Согласно представлениям потребителя космической системы наблюдения общий критерий эффективности всей системы в целом весьма прост и понятен - обеспечить максимальную «производительность» системы, подразумевая получение максимального числа наилучших снимков за определенный промежуток времени (один виток), либо, в случае неодинаковой важности объектов, то необходимо обеспечить суммарную важность полученных снимков: где п - число снимков, полученных за период наблюдения Т. Тогда в одном случае при заданном составе п пунктов надо минимизировать «затраты» - длину маршрута, в другом случае - максимизировать отношения «доходов» к «затратам». Условие (1.2) можно преобразовать. Оно адекватно условию минимума: Казалось бы, этого представления достаточно, чтобы определить текущий критерий оптимальности съемки. На самом деле это не так. Обратимся к рис. 1.2 и рассмотрим две возможные ситуации. В первой ситуации количество объектов, которые доступны и попали в зону наблюдения, невелико (см. ситуацию в начале съемки) и поэтому маршрут съемки требует обхода всех объектов по критерию минимума длины маршрута. При этом видно, что в некоторых случаях телескоп разворачивается в заднюю полусферу, чтобы получить снимок пропущенного объекта при пролете КА вдоль полосы. И тогда критерий минимальной длины маршрута при облете всех пунктов, попавших в доступную зону, является критерием оптимальности. Во второй ситуации возможно большое скопление объектов. Все их обследовать не представляется возможньм из-за ограниченных ресурсов управления угловым движением. Поэтому какая-то часть объектов должна быть исключена, другая же часть, имеющая высший приоритет должна быть обслужена. Очевидно это наиболее важные объекты, либо наиболее удобные (находящиеся рядом, но возможно ближе к середине полосы обзора, либо с одной стороны). Возникает вопрос, а какой наилучший критерий при этом надо использовать? Оказывается, что связь между исходным критерием эффективности текущим частным критерием оптимальности весьма неопределенна. Более того, этих критериев должно быть несколько, когда каждый из них используется для каждой конкретной ситуации.
Формирование функции риска для выбора альтернативного направления полета в случае исходного критерия минимума длины маршрута
Рассмотрим следующую задачу - пусть в моделируемую среду заложен неизвестный самообучаемой системе критерий - минимум длины маршрута, пункты облета пока что характеризуются двумя географическими координатами Xj и у} , а нужно найти коэффициенты степенного полинома Fj , характеризующие минимизируемую функцию риска при перелете ЛА в точку xj, yj: Fj = dx (Xj -x) + d2 (yj -y) + d3 (Xj -x)2+d4 {y} - yf + d5 (Xj - x)(yj - y). Взятый в качестве базового критерия вид функции риска в виде степенного полинома второго порядка обусловлен тем, что при dj=d2=ds=:0, d3=d4=l соответствует условию вычисления расстояния до ближайшего объекта. Это отвечает физическому смыслу простого правила - лететь до ближайшего объекта. Добавление же ненулевых членов di=d2=d$ - дает более общий случай случай предпочтения движения вперед, назад, влево, вправо [26, 27, 31-39]. Даны примеры оптимального планирования маршрута полета. Примеры содержат координаты точек облета и номера точек, характеризующие оптимальный маршрут. В рассматриваемой работе проводится оптимизация маршрута по его длине, которая должна быть минимальна. Требуется разработать процедуру автоматического формирования правила маршрутизации в аналитическом виде. В качестве прототипа таких примеров взяты результаты оптимального планирования, найденные с помощью метода ветвей и границ. Рассмотрим один из примеров (рис.2.1.). Как видно маршрут состоит из восьми точек, причем первая и восьмая точки фиксируются, остальные координаты выбираются случайным образом. Также известен порядок облета. Для поиска коэффициентов функционала будем проводить следующую последовательность действий: считаем точку №1 текущей; заносим в массив поиска следующие пять точек (№2-№6); подсчитываем значение функционала в каждой точке из этих пяти. Функционал считается столько раз в каждой точке, сколько возможно сочетаний коэффициентов d\..ds при том, что: каждый из них меняется от 0 до 1 с шагом 0,1; для каждого расчета (пять значений F в пяти точках) выбираем минимальный функционал; если минимум достигнут в следующей точке оптимального маршрута, то запоминаем значения коэффициентов du.ds для этого расчета и заносим их в массив данных; из всего массива подсчитанных функционалов выбираем только те, которые удовлетворяли ранее пройденному маршруту; по достижению последней точки, оставшаяся комбинация параметров dj..ds и формирует искомое правило в аналитической форме. Промоделируем так называемое «полное множество» возможных вариантов. Здесь будем учитывать, что: коэффициенты di..d$ лежат в пределах от 0 до 1. шаг изменения коэффициентов равен 0,1. сумма коэффициентов равна 1. Таким образом все поле коэффициентов будет содержать 713 комбинаций: По мере прохождения маршрута многие варианты отсеиваются (а в некоторых случаях все). При увеличении числа промежуточных пунктов в маршруте, вероятность встретить такое сочетание параметров, которое бы удовлетворяло всему пути, стремится к нулю. Графически эту картину можно представить так: Здесь видно, что на всем поле коэффициентов нет точки, принадлежащей сразу всем множествам (каждая точка маршрута удовлетворяет определенному множеству коэффициентов). Так в рассматриваемом случае пункты №5 и №6 выпадают из общей картины. Вероятно здесь маршрут имеет наиболее нехарактерный излом.
Исходные условия решаемой задачи
Учитывая сложность поставленной задачи, в данной работе рассматривались следующие исходные упрощенные предпосылки. 1.Пусть минимизируемое значение функционала J зависит только от двух координат текущего состояния объекта - х и у, характеризующих положение ЛА в горизонтальной плоскости (высота полета Н считается неизменной), но зато подинтегральное значение /0 имеет не квадратичную форму, а сумму линейной и квадратичной форм следующего вида [30] где vx,v2 - диагональные коэффициенты квадратичной формы, не зависящие от выбираемой альтернативы j(t) (недиагональные элементы матрицы штрафов не учитываются); ру,p2J - коэффициенты линейной формы, от управления зависящие; Я- - свободный член, соответствующий в задаче АКОР [30] слагаемому г и] а оценивающий штраф при х -» 0; у - 0; j(t) - номер пункта, куда надо двигаться из соображений минимального риска. Пусть в качестве движущегося управляемого ЛА взят простейший объект, перемещающийся в выбранном направлении с постоянной скоростью. В частности, считается возможным движение в одном из четырех направлений - в переднюю полусферу, заднюю полусферу, влево и вправо, когда в каждом из рассматриваемых случаев допускается наличие интересующего нас пункта назначения с координатами Xj,yj,(j = 1,2,3,4).Тогда согласно теореме синусов можно составить нужные пропорции, и заменив значения синусов на отношения сторон треугольника получим систему дифференциальных уравнений Уі=\ К сожалению, система уравнений (3.1) является даже в избранном простом случае явно нелинейной, и чтобы привести правую часть этих уравнений к степенному полиному первого порядка (а нам это потребуется для решения обратной задачи), нужно воспользоваться разложением в ряд Тейлора: Из формулы (3.4) видно, что минимизируемая функция Fj(x,y) риска принятия решений приведена к такому же виду степенного полинома второго порядка, что и полученное при самообучении в главе 2 правило поведения, минимизирующее функцию риска. Введем дополнительные обозначения в правило (1.4), найденное в главе 2, чтобы привести в соответствие с формулой (3.4) Предложенных предпосылок достаточно, чтобы приступить к решению задачи. В частности, задаваясь различными предельными случаями значений коэффициентов dj, важными для практики планирования (например, пусть dx =l;d2 =d3 =0, что соответствует условию выбора ближайшего по х пункта назначения), можно найти по формулам (3.6) значения коэффициентов AJ,BJ,CJ,D,E, а с их помощью попытать? решить уравнение Беллмана (3.4) и найти искомые параметры модели Xj,p4,vу.
Постановка «прямой» задачи динамического программирования и особенности ее решения
В данной главе, с одной стороны, ставится классическая задача оптимального управления в обычной постановке - считается, что критерий оптимальности в виде интегрального функционала J задан, также заданы динамические характеристики объекта в виде системы дифференциальных уравнений. При этих условиях необходимо найти закон оптимального управления угловым движением КА, обеспечивающий минимум заданного функционала С другой стороны, можно указать на ряд особенностей решаемой задачи [59,61-67]. Первой особенностью является специфика динамических свойств явно нелинейного объекта, каковым является КА, а именно - существует существенные ограничение по угловому ускорению и скорость углового вращения из-за ограниченного кинетического момента с учетом значительного момента инерции КА, что может быть отражено следующей системой дифференциальных уравнений где хх=х- координата продольного углового движения оси телескопа в направлении движения всего КА по орбите; х2 = у - координата бокового углового движения оси телескопа; w - приведенная угловая скорость, выступающая в роли возмущения за счет поступательного движения КА по орбите, х3- угловая скорость продольного движения оси телескопа КА, хА-угловая скорость бокового движения оси КА, а, Ь - динамические параметры углового движения определяющие переходной процесс на участках разгона и торможения; 8- ограничение по модулю управляющего воздействия, и,;м2-сигналы управления. Как видно из приведенных в обозначениях пояснениях, другой особенностью является наличие возмущения w по продольной угловой 77 скорости. Этого возмущения в простейшей модели динамики КА, использованной в главе 3, не было. Еще одной особенностью является то, что функция критерия /„зависит от двух координат состояния - х =дс, и у =х2, характеризующих лишь координаты положения оптической оси телескопа на земной поверхности, в то время как динамика КА описывается с помощью большего числа - четырех координат х],х2,х3,х4, что в целом усложняет вид функции Беллмана и ее нахождение. Кроме того, в данной работе считается равновесным угловое движение по каждой из осей - х и у, поэтому значения а, Ъ и 8 взяты по двум каналам управления одинаковыми. Заметим, что на участках разгона и торможения значениями а и Ь можно пренебречь, положив а = 0; Ъ = 1. Наконец, последней особенностью задачи является сам характер искомого оптимального управления - оно не линейно, а альтернативно. Поэтому нужно искать функцию переключения этого релейного управления в пространстве состояний вектора х4, что не имеет строгого аналитического решения. Поэтому в данной работе используется приближенный метод, описанный в [ ] и основанный на динамическом программировании альтернативных решений, что требует расчета сначала ординат риска С,+ ,С ,С ь , а затем - функции Fj(x) текущего риска для каждого у -того наземного пункта. Минимум этой функции и даст ответ, съемку какого очередного у -того объекта надо произвести в первую очередь, и таким образом открывается возможность назначить динамические приоритеты в съемке. В данном параграфе рассматривается практически важный случай, когда наблюдаемых наземных объектов мало, ни один из них нельзя пропустить, и поэтому в качестве модели критерия нужно использовать условие (3.30):
