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

Введение.

Вспомогательные указатели.

Глава 1. Основные направления исследований в области программирования траекторий движения транспортных средств.

1.1. Обзор работ по проблеме решения траекторных оптимизационных задач.

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

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

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

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

2.1.1. Синтез траекторий движения на основе игровых стратегий.

2.1.2. Исследование устойчивости замкнутой системы "убегающих" и "догоняющих".

2.1.3. Исследование устойчивости замкнутой системы в базисе Фробениуса.

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

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

2.2.1. Математическая формулировка задачи как задачи безусловной оптимизации.

2.2.2. Генерация траекторий движения транспортных средств.

2.3. Интерполяция непрерывных функций оптимальных траекторий движения.

2.3.1. Чебышевские системы функций на множестве состоящем из п+1 точек.

2.3.2. Наилучшее приближение на множестве состоящем из п+1 точек.

2.3.3. Аппроксимация опасных зон выпуклыми множествами.

2.3.4. Наилучшее приближение на компактном множестве из не менее п+1 точек метрического пространства.

2.3.5. Наилучшее приближение на отрезке [а, Ь] вещественной прямой.

2.3.6. Интерполяция функций с помощью полиномиальных сплайнов.

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

3.1. Метод обработки результатов наблюдений.

3.2. Исследование и разработка алгоритма управления транспортным средством.

3.3. Формирование управлений транспортным средством при неполном измерении состояния.

Глава 4. Экспериментальное исследование качества методов программирования оптимальных траекторий и алгоритмов управления транспортным средством.

4.1. Исследование методов программирования оптимальных траекторий движения в условиях неподвижных опасных зон.

4.2. Исследование метода стабилизирующих управлений транспортным средствам на основе игровых стратегий.

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

Работа выполнена на кафедре "Системный анализ и управление" Санкт-Петербургского государственного технического университета.

ВВЕДЕНИЕ

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

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

В третьей главе рассмотрен метод обработки результатов наблюдений за движением и состоянием ТС как объекта управления, необходимый для построения оптимального управления ТС с целью безопасного движения и выполнения поставленного перед экипажем задания. Исследованы алгоритмы стабилизации ТС на программной траектории в рамках теории адаптивного управления: 1) алгоритм стабилизации при ограничении управлений и действии внешних возмущений;

-62) алгоритм адаптивной стабилизации при неполном измерении состояния ТС.

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

ВСПОМОГАТЕЛЬНЫЕ УКАЗАТЕЛИ ТС - транспортные средства

АСУП - автоматизированные системы управления полётом СИПЛ - системы интеллектуальной поддержки лётчика БЦВМ - большая цифровая вычислительная машина МППСС - Международные правила предупреждения столкновений судов

САПР - системы автоматической радиолокационной прокладки ВС - встречные суда

АСУ - автоматизированные системы управления ОЗ - опасные зоны

ЗЛП - задача линейного программирования ЗИП - задача нелинейного программирования ЛА - летательный аппарат ЛТ - лидирующая точка

ВЫВОДЫ

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

2. При управлении замкнутой динамической системой в рамках базиса Фробениуса можно приблизить только последнюю компоненту состояния "догоняющего" к последней компоненте сотояния "убегающего", а прочие будут повторять последнюю компоненту этого "догоняющего" со сдвигом на шаг квантования. При оптимальном управлении каждая компонента "убегающего" зависит только от соответствующей компоненты задающего воздействия на этого "убегающего". Таким образом, путем изменения задающего воздействия можно влиять на характер движения "догоняющего".

ЗАКЛЮЧЕНИЕ

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

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

3. Сформулирована и решена задача управления в условиях подвижных опасных для движения транспортного средства зон в терминах раздела дифференциальных игр - преследование со многими участниками. Экспериментальные исследования подтвердили справедливость формул субоптимального управления устойчивыми минимально-фазовыми динамическими объектами.

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

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

6. Для стабилизации транспортного средства (ЛА) на оптимальной программной траектории движения предложен алгоритм адаптивного управления согласно разработанным формулам субоптимального управления замкнутой системой с использованием эталонной модели (ЛТ), управление которой осуществляется путем задающего воздействия, учитывающего параметры программной оптимальной траектории движения.

1. Планирование траекторий для мобильных роботов. // Пер. с яп. М.: Всероссийский центр переводов. № Н- 42043,1987.

2. Кристофидекс Н. Теория графов (алгоритмический подход).//Пер. с англ. М.: Мир, 1978.

3. Метод Вороного в задачах поиска беспрепятственных маршрутов робота. // Пер. с англ. М.: Всероссийский центр переводов. №ГН-74657,1988.

4. Автономные мобильные роботы. // Пер. с англ. М.: Всероссийский центр переводов. № Р 4075,1988.

5. Движущийся робот на Марсе до 2000 года. // Пер. с англ. М. ЦНИИТЭСТРОЙМАШ. №2823, 1990.

6. Blidberg D.R. Unmanned Submersible Vechicles. // Workshop on Autonomous Ground Vechicles. Leesburg: VA, 1984.

7. GilmoreJ.F. The Autonomous Helicopter Sistem. // SPIE Application of AI. Wachington: D.C., 1983.

8. Чуркин В.И. Оптимальное управление расхождением судов. // Изв. РАН. Теория и системы управления, 1999, № 2.

9. Козлов В.H., Куприянов В.Е., Шашшин В.Н. и др. Бортовые системы управления полётом. СПб, СПбГТУ, 1999.

10. ЛетовАМ. Динамика полёта и управление. М.: Наука, 1969.

11. ЛетовАМ. Математическая теория процессов управления. М.: Наука, 1981.

12. Гвишиани Д.М. Организация и управление. М.: Наука, 1970.

13. Rato S. Cure for Chaos. New York: David McKay Co., 1970.

14. Пупков К.А. Проблемы теории и практики интеллектуальных систем. // Сб. материалов и сообщений "Интеллектуальные системы 94". Махачкала, 1994.

15. Лебедев F.H., Андронов Н.Н., Ковзан Л.А. и др. Многоуровневая интеллектуальная система управления летательным аппаратом. // Тематический сборник научных трудов "Интеллектуальные системы". М.: Изд-во МАИ, 1991.

16. Емельянов С.В., Коровин С.К. Новые типы обратных связей. М.: Наука, 1997.

17. Поспелов Д. А. Ситуационное управление. Теория и практика. М.: Наука, 1986.

18. Алехин Д. А., Буров Ю.Л., Зарепур Г. и др. Новый тип обратных связей в интеллектуальной системе управления полётом. И. // Изв. РАН. Теория и системы управления, 1998, № 6.

19. Моделирование подвижных систем обхода препятствий автономным транспортным роботом. // Пер. с англ. М.: Всероссийский центр переводов. № JI 59706,1986.

20. Lozano-Perez Т. Automatik Planning of Manipulator Transfer Movements. // IEEE Trans. Sistems Man and Cybernetics. 1981. V. SMC-11.

21. Moravec H.P. Robot Rover Visual Navigation. Michigan: UMI Research Press., 1981

22. Brooks R.A. Solving the Find-path Problem by Good represention of Free-space. // IEEE Trans. Systems Man and Cybermetics, 1983, V. SWMC-13, № 3.

23. Chatila R. Patch Planning and Environment Leaning in Mobile Robot

24. Sistem. // Proc. European Conf. Artificial Intelligence. Torsey, France, 1982.

25. Borenstein J., Koren Y. The vector field histogram-fast obstacle avoidence for mbile robot.//IEEE J. Rob. And Autom, 1991, V.7, № 3.

26. Nelson R/С/, Aloimonos J. Y. Using flow field divergence for obstacle avoidance: towards qualitative vision. I 12-nd Inter. Conf. Comput. Vision Tampa. Washington: D.C., 1988.

27. Mchrotra R., Krause DM. Obstacle-free path planning for mobile robots. // 3-rd Inter. Conf Image Proc. And Appl. London, 1989.

28. Jorgensen C.C. Neural Network Representatian of Sensor Graphs in Autonomous Robot Path Planning. // IJSNN Intern. Conf. Neural Networks. San Diego. California, 1990, V. 4.

29. Nages War a Rao S. V., Iyengar S.S. Concurrent Algoritms for Autonomoys robot navigation in an unexplored terrain. // IRRR Inter. Conf Rob. and Autom. San. Francisco, 1986, V.2.

30. Иванов A.K. Эксперементальное построение математической модели нейронной сети // Непрерывные и смежные логики в технике, экономике и социологии: Матер, междунар. конф., Пенза, 1996.

31. Агеев Д.А., Истратов А.Ю Нейросетевая реализация задачи поиска оптимального пути // Изв. РАН. Теория и системы управления. 1998, № 1.

32. Ченцов А А., Ченцов А.Г. Маршрутизация последовательногообхода системы подвижных множеств с использованием динамического программирования в условиях неточных вычислений функции Беллмана//Журн. Проблемы управления и информатики. 1999, №2.

33. ЗЪ. Коротаева Л.Н., Сесекин А.Н., Чепцов А.Г. Об одной модификации динамического программирования в задаче последовательного сближения // Журн. вычисл. математики и мат. физики, 1989, № 8.

34. Буслаева Л. Т., Ченцов А.Г. К вопросу о декомпозиции процесса последовательного выбора вариантов // Матем. моделирование. 1991, №4.

35. Коротаева Л. Н., Назаров Э.М., Ченцов А.Г. Динамическое программирование в одной задаче о назначениях // Тез. Докл.

36. V Всесоюз. семинара "Методы синтеза и планирования развития крупномасштабных систем". Звенигород: Ин-т пробл. управления, 1990.

37. Коротаева Л.Н., Назаров Э.М., Ченцов А.Г. Об одной задаче о назначениях//Журн. вычисл. математики и мат. физики. 1993, №4.

38. Chentsov A.G., Korotaeva L.N. The dynamik programming method in the generalized salesman problem // Math. Comput. Modelling. 1997, №1.

39. Тараненко В. Т. Опыт применения методов Ритца, Пуанкаре и Ляпунова к решению задач динамики полёта. М.: ВВИА им. проф. Н.Е. Жуковского, 1968.

40. Тараненко В. Т., Момджи В.Г. Прямой вариационный метод в краевых задачах динамики полёта. М.: Машиностроение, 1986.

41. Нелюбов А.И. Лётные характеристики и боевое маневрирование летательных аппаратов. Вып. 2. Математические методы расчётаманёвров, взлёта и посадки самолётов с поворотом вектора тяги двигателей. M.: ВВИА им. проф. Жуковского, 1986.

42. Потрягин J7.C., Болтянский В.Г., Гамкрелидзе Р.В. и др. Математическая тория оптимальных процессов. М.: Наука, 1969.

43. Василец В.М., Якименко O.A., АнтифеевД.Д. и др. Разаитие концепции бортовой системы интеллектуальной поддержки принятия решения лётчиком с обратной идентификацией // Авиакосмическая техника и технологии. 1996, № 1.

44. Якименко O.A. Содержание "интеллектуализации" борта глазами лётчика // Техника воздушного флота. 1995, № 3,4.

45. Якименко O.A. Упрощённая модификация прямого метода для решения траекторных краевых оптимизационных задач на борту летательного аппарата// Изв. РАН. Теория и системы управления. 1998, №3.

46. Гудмэн С.А., МакГенриВ.К. Управленческие информационные системы на советских предприятиях // УсиМ, 1990, № 6.

47. Мелихин И.С. Информационные системы в процессе управления. Аналитический обзор // Проблемы информатизации. 1992, вып. 3.

48. Моисеев H.H. Численные методы в теории оптимальных систем. М., 1971.

49. Васильев Ф.П. Численные методы решения экстремальных задач. М., 1980.

50. Лучка А.Ю. Проекционно-итеративные методы решения дифференциальных и интегральных уравнений. Киев: Наук. Думка, 1980.

51. Лучка А.Ю., Нощенко О.Э., Тукалевская Н.И. Вариационноградиентный метод // Журн. вычисл. математики и мат. физики. 1984, №7.

52. Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.

53. Беллман Р. Динамическое программирование // Пер. с англ. М: Изд-во иностр. лит. 1960.

54. СингМ., ТитлиА. Системы: декомпозиция, оптимизация и управление. М.: Машиностроение, 1986.

55. Гурман В.И. Принцип расширения в задачах управления. М.: Наука, 1997.

56. Сю Д., Мейер А. Современная теория автоматического управления и её применение. М.: Машиностроение, 1972.

57. Пугачев B.C.,Казакова И.Е., Евланова Л.Г. Основы статистической теории автоматических систем. М.: Машиностроение, 1974.

58. Лучка А.Ю., Нощенко О.Э.,Тукалевская Н.И. Общая схема одно-шаговых вариационно-градиентных методов для линейных уравнений // Журн. Кибернетика и системный анализ. 1998, № 2.

59. Бодянский Е.В., Воробьев С.А., Штефан А. Алгоритм адаптивной идентификации динамических параметрически нестационарных объектов // Изв. РАН. Теория и системы управления. 1999, № 1.

60. Шашихин В.Н. Оптимизация нелинейных систем на основе метода инетрвальной линеаризации // Изв. РАН. Теория и системы управления. 1999, № 3.

61. WellsteadP.E., Zarrop M.B. Self-tuning Sistem. Control and Signal Processing. Chichester: John Wiley and Sons. 1991.

62. Льют JI. Идентификация систем. Теория для пользователей. М.: Наука, 1991.

63. Фрадков А.Л. Адаптивное управление в сложных системах. М.: Наука, 1990.

64. Габасов Р., Ружицкая Е.А. Синтез оптимальных по быстродействию систем в классе ограниченных непрерывных управлений с ограниченными производными // Изв. РАН. Теория и системы управления. 1998, № 4.

65. Фирсова Е.М. Принцип мультипликативной адаптации в задачах управления нестационарными динамическими системами // Изв. РАН. Теория и системы управления. 1998, № 6.

66. Костюкова О.И. Об одном алгоритме решения задач оптимального управления // Журн. вычисл. математики и мат. физики. 1999.

67. Хиленко В.В. Метод понижения порядка и задач адекватного упрощения моделей САУ с неопределёнными коэффициентами // Кибернетика и системный анализ. 1998, № 3.

68. Соколов C.B., Щербанъ И.В. Синтез локально-оптимального управления с использованием обобщённых вероятностных критериев // Проблемы управления и информатики. 1999, № 2.

69. Цурков В.И. Декомпозиция в задачах большой размерности. М.: Наука, 1981.

70. Медницкий Ю.В. О параллельном использовании метода декомпозиции в паре двойственных задач линейного программирования // Изв. РАН. Теория и системы управления. 1998, № 1.

71. Щеглов А.Ю. Методика планирования распределения ресурсов вычислительной сети // Автоматика и вычисл. техника. 1989, № 1.

72. Щеглов А.Ю. Векторная интерпретация и численный методрешения линейных уравнений // Изв. вузов. Приборостроение. 1993, №9,10.

73. Щеглов А.Ю. Векторный метод оперативного планирования работ в постановке задачи линейного программирования // Изв. РАН. Терия и системы управления. 1998, №4.

74. Плит В.Е. Алгоритмы формирования альтернативных решений на базе модели многокритериального линейного программирования // Кибернетика и системный анализ. 1998, № 2.

75. Жадан В.Г. Прямо-двойствненый метод Ньютона для задач линейного программирования // Журн. вычисл. математикики мат. физики. 1999, № 1.

76. Жадан ВТ. О сходимости прямо-двойственного метода Ньютона для задач линейного программирования // Журн. вычисл. математики и мат. физики. 1999, № 3.

77. Малоземов В.Н. Необходимые и достаточные условия мини-макса. В кн.: Оптимизация, вып. 10/27, Новосибирск, Наука, 1973.

78. Малоземов В.Н. Альтернансная форма условной оптиальности. В кн.: Вопросы теории и элементы программного обеспечения минимаксных задач. JI. Изд-во ЛГУ, 1977.

79. Малоземов В.Н., ПевныйА.Б. Альтернансные свойства решений нелинейных минимаксных задач.- Докл. АН СССР, 1973, т. 212, № 1, с. 37-39.

80. Даугавет В.А., МалоземовВ.Н. Альтернансные свойства решений нелинейных минимаксных задач с невыпуклыми ограничениями. Докл. АН СССР, 1975, т. 225, № 2, с. 253-255.

81. Малоземов В.Н, ПевныйА.Б. Аппроксимация сплайнами произвольного дефекта.- Докл. АН СССР, 1978, т. 243, № 3, с. 572-575.

82. Малоземов В.Н. Задача синтеза многополосной электрического фильтра// Журн. вычисл. математики и мат. физики. 1979, т. 19, №3, с. 601-609.

83. Васильев A.A., Малоземов В.Н., Певный А.Б. Интерполирование и аппроксимация сплайнами произвольного дефекта//Вестн. Ленингр. ун-та, 1980, №19.

84. Василенко В. А. Сплайн-функция: теория, алгоритмы, программы. Новосибирск, 1983.

85. Треногий В.А. Функциональный анализ. М.: Наука, 1993.

86. Родионов В.В. Блочно-параметрический метод отыскания кратчайших расстояний на графе // Журн. вычисл. математики и мат. физики. 1999, том 39, № 4.

87. Козлов В.Н, Куприянов В.Е., Заборовский B.C. Вычислительные методы синтеза систем автоматического управления. Л.: Изд-во ЛГУ, 1989.

88. Зуховицкий С.И.Авдеев A.M. Линейное и выпуклое программирование // М.: Наука, 1964.

89. Кузнецов Ю.Н., Кутузов В.И., Волощенко А.Б. Математическое программирование // М.: Высшая шкоала,1980.

90. Карманов ВТ. Математическое программирование // М.: Наука, 1986.

91. Яглом ИМ., Болтянский В.Г. Выпуклые фигуры // Сборник задач. М.-Л.Д951.

92. Виденский B.C. Лекции о применении торемы Хелли в конструктивной теории функций // Сборник статей, Ростов-на-Дону, 1972.

93. Дзядык В.К. Введение в теорию равномерного приближения-158функций полиномами // М., 1977.

94. Пшеничный Б.Н. Об одной задаче группового преследования // Кибернетика. 1976, № 6.

95. Петров H.H. Одна задача группового преследования с фазовыми граничениями // Нелин. колебания и теория управления. Ижевск: изд-во Удмурт. Ун-та, 1987.

96. Вайсборд Э.М., Жуковский В.И. Введение в дифференциальные игры нескольких лиц и их приложения. М.: Советское радио, 1980.

97. Петров H.H. Одна задача уклонения от многих преследователей // Изв. РАН. Теория и системы управления. 1998, № 1.

98. Афанасьев В.Н., Колмановский В.Б., Носов В.Р. Математическая теория конструирования систем управления. М.: Высшая школа. 1998.

99. Фомин В.Н., Фрадков A.JI., Якубович В.А. Адаптивное управление динамическими объектами. М.: Наука, 1981.

100. Елисеев В.Д. Математичиские модели летательного аппарата в проектировании САУ // М., 1992.

101. Михалев И.А. и другие Системы автоматического управления самолетом // М., 1995.