Моделирование конфликтов управляемых сложных систем тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат физико-математических наук Нартов, Борис Кимович

• Нартов, Борис Кимович
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Нартов, Борис Кимович

Содержание

Введение

Глава 1. Конкуренция подвижных объектов

§ 1.1. Модели взаимодействия

§ 1.2. Метод возврата. Оптимизация начальных координат

§ 1.3. Метод фиктивных потоков. Оптимизация начальных характеристик

§ 1.4. Комплексная задача размещения группы подвижных

объектов

§ 1.5. Управление направленными воздействиями

§ 1.6. Задачи оптимального преследования

Глава 2. Поиск стационарных целей

§ 2.1. Планирование слепого поиска. Метод упругих функций

§ 2.2. Оптимальное управление поиском

§ 2.3. Двухкритериальная задача

§ 2.4. К задаче коммивояжера

Глава 3. Поиск подвижных целей

§ 3.1. Постановка задачи и общие модели поиска. Разделение вычислительного ресурса

§ 3.2. Схемы поиска и функционалы качества

§ 3.3. Нестационарный поиск и релаксация целей

Библиография

Введение диссертации (часть автореферата) на тему «Моделирование конфликтов управляемых сложных систем»

ВВЕДЕНИЕ

Данную работу объединяет тема конфликта сложных систем, включающих, в общем случае, множества управляемых подвижных объектов с характеристиками, зависящими как от времени, так и от управления [5365]. Основное внимание уделено при этом трем, выделенным в главы, группам задач:

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

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

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

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

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

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

В § 1.1 предложена и обоснована простейшая состоятельная модель вза-имодеиствия групп противодействующих объектов, связывающая характеристики объектов с характеристиками объектов противника, управлением и временем [53]. На примере этой модели демонстрируются далее предлагаемые в Главе 1, достаточно универсальные формализмы и методы.

В § 1.2 описывается метод быстрой направленной оптимизации начальных координат управляемых траекторий группы подвижных объектов. Идея метода состоит в построении сходящегося итеративного процесса, в шагах которого чередуются исходная задача "исчерпывания" и вспомогательная задача "восстановления" ("метод возврата"). Существенно, что предлагаемый метод применим ко всем задачам с непрерывными по времени функционалами качества. Приводится реализующий алгоритм. Описывается также метод оптимизации начальных координат, основанный на решении вспомогательной задачи конкуренции со специальным образом модифицированными динамическими ограничениями [63].

В § 1.3 предлагается метод расчета оптимального - в смысле минимизации избранного функционала качества - размещения данного ресурса подвижных объектов на заданных исходных позициях. Предлагаемый метод основан на дополнении исходной модели взаимодействия "коммутатором фиктивных потоков", позволяющим за время, малое по сравнению с временем управления, перераспределить данный ресурс объектов между исходными позициями ("метод фиктивных потоков", [63]).

В § 1.4 доказывается, что для дифференцируемых уравнений взаимодействия предложенные в §§ 1.2 и 1.3 метод модификации динамических ограничений и метод фиктивных потоков совместимы. Таким образом, формулируется и формализуется до метода комплексная задача оптимального начального размещения группы объектов, то есть задача параллельной оптимизации начальных координат и характеристик объектов [63].

В § 1.5 описаны две модификации модели взаимодействия, исследованной в § 1.1. Эти модели позволяют просто учесть управляемость направленных воздействий подвижных объектов и возможность разделения соответствующего ресурса данного объекта между подвижными объектами конкурента [54].

В § 1.6 рассмотрен новый подход к решению классических задач оптимального преследования. Предлагаемая модель [55] позволяет избавиться от дифференциальных уравнений траекторий объектов и формализовать общий случай задачи оптимального преследования в виде задачи вариационного исчисления или оптимального управления.

В Главе 2 решены некоторые задачи оптимального поиска стационарных целей, интерес к которым стимулировала монография Хеллмана [48].

В § 2.1 исследуется задача планирования поиска неподвижных целей с известными функциями плотностей распределения вероятностей. Долгое время не удавалось свести эту задачу к классическим задачам условной оптимизации. Непереборные решения существовали лишь для частных случаев или получались при физически необоснованных ограничениях. Основным препятствием была при этом невозможность аналитического учета пересечений и самопересечений полос поиска. Предлагаемый подход [62] позволяет формализовать общий случай задачи планирования поиска в виде задачи оптимального управления ("метод упругих функций").

В § 2.2 формализована задача управления поиском неподвижных целей в реальном масштабе времени. Даны правила перенормировки плотно-

стей вероятностей координат целей в моменты обнаружений. Показано, что оптимальная траектория поиска, управляемого в реальном масштабе времени, на интервале между двумя последовательными обнаружениями совпадает с траекторией оптимального плана (§ 2.1), рассчитываемого в момент последнего обнаружения [64].

В § 2.3 исследуется расширение формализованной в § 2.1 задачи оптимального поиска на случай, когда на области поиска задана плотность вероятности гибели поисковой единицы, т.е. когда результат поиска зависит не только от просмотренной к данному моменту области, но и от последовательности ее просмотра.

Порождаемая этим дополнительным условием двухкритериальная задача также сведена к задаче оптимального управления [64].

В заключающем Главу 2 параграфе 2.4 приводятся две простые, основанные на результатах Глав 1 и 2, математические модели, позволяющие записать задачу коммивояжера как задачу оптимального управления [64].

В Главе 3 (§ § 3.1-3.3) предложены некоторые достаточно общие модели поиска подвижных целей для систем автоматизированного отображения и анализа реальной физической обстановки. Соответствующие задачи (см., например [37] и [56]) порождаются необходимостью эффективного выборочного просмотра больших двумерных массивов текущей информации.

В качестве основной предложена и исследована "газовая" модель, рассматривающая поиск целей как взаимодействие "газа" целей с подвижной, частично проницаемой "мембраной" - траекторией управляемого поискового маркера [58]. Предлагаемый подход позволяет, в конкретном случае, записать уравнение, связывающее математическое ожидание количества целей, обнаруживаемых за данное время, с параметрами задачи и схемой поиска и оптимизировать параметры конкретной схемы поиска [64].

Список литературы диссертационного исследования кандидат физико-математических наук Нартов, Борис Кимович, 1998 год

Библиография

[1] Авен О.И., Турин H.H., Коган Я.А. оценка качества и оптимизация вычислительных систем. - М., Наука, 1982. - 317 с.

[2] Айзеке Р. Дифференциальные игры. - М.: Мир, 1967. - 479 с.

[3] Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин. - М.: Наука, 1970. - 227 с.

[4] Ансофф И. Стратегическое управление. - М.: Прогресс, 1989. - 324 с.

[5] Аоки М. Введение в методы оптимизации: Основы и приложения нелинейного программирования. - М.: Наука, 1977. - 335 с.

[6] Арнольд В.И. Обыкновенные дифференциальные уравнения. - М.: Наука, 1971. - 239 с.

[7] Асманов В.В. Интегрированная распределенная система цифровой обработки изображений // Тезисы международ, конф. "Обработка изображений и дистанционные исследования", СО АН СССР. - Новосибирск, 1990. - С. 107-112.

[8] Баранов В.И., Стечкин Б.С. Экстремальные комбинаторные задачи и их приложения. - М.: Наука, 1989. - 160 с.

[9] Барлоу Р., Прошан Ф. Математическая теория надежности. - М.: Сов. радио, 1969. - 485 с.

[10] Берж К. Общая теория игр нескольких лиц. - М.: Физматгиз, 1961. -255 с.

[11] Блэкман М. Проектирование систем реального времени. - М.: Наука, 1984.

[12] Большаков И.А. Статистические проблемы выделения потоков сигналов из шума. - М.: Сов. радио, 1969. - 464 с.

[13] Брайсон У., Хо Ю-ши. Прикладная теория оптимального управления. - М.: Мир, 1972. - 544 с.

[14] Буков В.Н. Адаптивные прогнозирующие системы управления полетом. - М.: Наука, 1987. - 232 с.

[15] Вазан М. Стохастическая аппроксимация. - М.: Мир, 19972. - 296 с.

[16] Васильев Ф.П. Методы решения экстремальных задач. - М.: Наука, 1981. - 298 с.

[17] Витяев Е.Е. и др. Имитатор динамических обстановок для экспертных систем электронной навигации // Тез. международ, конф. "Обработка изображений и дистанционные исследования", СО АН СССР. -Новосибирск, 1990. - С. 34-36.

[18] Гнеденко Б.В., Беляев Ю.К., Соловьев А.Д. Математические методы в теории надежности. - М.: Наука, 1965. - 318 с.

[19] Головинский A.H., Наумов А.Н. Аналитическое решение задач оптимального траекторного управления летательным аппаратом // Изв. АН СССР. Сер. Техн. кибернетика. 1986. №

[20] Горбань А.Н. Обход равновесия. - Новосибирск: Наука, 1984. - 226 с.

[21] Горцев А.М., Назаров A.A., Терпугов А.Ф. Управление и адаптация в системах массового обслуживания. - Томск: Изд-во ТГУ, 1978. - 208 с.

[22] Грицык В.В. Распараллеливание алгоритмов обработки информации в системах реального времени. - Киев: Наукова думка, 1981. - 343 с.

[23] Гршпенко В.А. Асимптотический анализ потока редких событий на ступенчатом случайном процессе . Аналитические методы теории надежности. - Киев: Ин-т математики АН УССР, 1985. - С. 32-42.

Дедков В.К., Северцев H.A. Основные вопросы эксплуатации сложных систем. - М.: Высшая школа, 1976. - 405 с.

Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. - М.: Наука, 1982. - 311 с. Ефимов Е,И. Решатели интеллектуальных задач. - М.: Наука, 1982.

- 192 с.

Зенкевич О. Метод конечных элементов в технике. - М.: Мир, 1975.

- 210 с.

Карась В.М. Устойчивость оптимальной сегментации программ // Программирование. - 1987. - № 5. - С. 75-84.

Клейнрок JI. Теория массового обслуживания. - М.: Машиностроение, 1979. - 432 с.

Климов Г.П. Стохастические системы обслуживания. - М.: Наука, 1966. - 244 с.

Красовский H.H. Управление динамической системой. - М.: Наука, 1985. - 517 с.

Кротов В.Ф., Гурман В.И. Методы и задачи оптимального управления. - М.: Наука, 1973. - 448 с.

Ларионова И.А., Пяткин В.П., Салов Г.И. О вероятности обнаружения линий на изображениях с помощью критерия знаков при перемещении окна наблюдения шагами // Тезисы международ, конф. "Обработка изображений и дистанционные исследования", СО АН СССР. - Новосибирск, 1990. - С. 93-95.

[34] Летов A.M. Выбор оптимизирующего функционала в проблеме аналитического конструирования // Труды III Всесоюз. совещания по автоматическому управлению. - М.: Наука, 1967. - С. 121-143.

[35] Моисеев H.H. Математика ставит эксперимент. - М.: Наука, 1979. -224 с.

Нагаев C.B. Теория вероятностей. - Новосибирск: Наука, 1972. - 285 с.

Обработка изображений // Под ред. Хуанга. - М.: Мир, 1979. - 314

с.

Ортега Дж., Рейнболдт В. Итерационные методы решения нелинейных систем со многими неизвестными. - М.: Мир, 1975. - 473 с. Петросян JI.A. Дифференциальные игры преследования. - JL: Изд-во ЛГУ, 1977. - 220 с.

Писаревский А.Н. и др. Системы технического зрения. - М.: Машиностроение, 1988. - 264 с.

Прэтт У. Цифровая обработка изображений. - М.: Мир, 1982. Т.1-2. Пшеничный Б.Н., Данилов Ю.М. Численные методы в экстремальных задачах. - М.: Наука, 1975. - 315 с.

Рейнгольд Э., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. -М.: Мир, 1980. - 476 с.

Соболь И.М. Численные методы Монте-Карло. - М.: Наука, 1973. -204 с.

Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. -М.: Наука, 1986. - 265 с.

Турчак Л.И. Основы численных методов. - М.: Наука, 1987. - 318 с. Флеминг У., Ришел Р. Оптимальное управление детерминированными стохастическими системами. - М.: Мир, 1978. - 316 с. Хеллман О. Введение в теорию оптимального поиска. - М.: Наука, 1985. - 254 с.

Худсон Д. Статистика для физиков. - М.: Мир, 1970. - 263 с. Черноусько Ф.Л., Баничук Н.В. Вариационные задачи механики и управления. - М.: Наука, 1973. - 327 с. [51] Aggervwal J.К., Martin V.N. Analysis Dynamic Scenes Containing Multiple Moving Objects // Tech. Rep. 125 / Dep. of Computer Sciences. -

The Univ. of Texas at Austin, 1980. - P. 1-44.

[52] Yalamanchili S., Martin V.N., Aggarwal J.K. Extraction of Moving Objects Descriptions via Differencing // Computer Graphics and Image Processing. - 1982. - № 18. - P.188-201.

[53] Потапов В.И., Братцев С.Г., Нартов Б.К. О задачах оптимального управления конкурирующими подвижными объектами. Деп. рук., ВИНИТИ, № 1465-В87, 1987. - 24 с.

[54] Братцев С.Г., Нартов Б.К., Потапов В.И. Оптимальное сегментирование вычислительного ресурса ЭВМ // Тезисы конф. "Информатика и вычислительная техника в учебном процессе и управлении", ОГПИ. - Омск: ОмПИ, 1988. - С. 167-168.

[55] Нартов Б.К., Братцев С.Г. Модель оптимального преследования // Стохастические и детерминированные модели сложных систем. ВЦ СО АН СССР. - Новосибирск, 1988. - С. 86-92.

[56] Братцев С.Г., Мурзин Ф.А., Нартов Б.К. Исследования по обработке динамических изображений // Тезисы международ, конф. "Обработка изображений и дистанционные исследования", СО АН СССР. -Новосибирск, 1990. - С. 41-43.

[57] Нартов Б.К., Соколовский B.C. Способ определения скорости транспортного потока. А.с. № 1587558, G 08G1/08, 1990.

[58] Нартов Б.К., Братцев С.Г. Модель поиска целей // Интеллектуальные системы управления летательных аппаратов. - М.: Изд-во МАИ, 1991. - С. 46-50.

[59] Bratsev S.G., Murzin F.A., Nartov В.К. The Optimum Search of Targes and the Processing of Dynamical Images // Thes. if Intern. Symp. on Visual Analysis and Interface. - Novosibirsk, 1991. - p. 17-18.

[60] Kriuchkov V.N., Nartov B.K., Frolov S.D. Addressing in Small Groups // Constructive Psychology, Transactions "Scientific Siberian", B, AMSE Press, Vol. 1, 1992. - P. 89-100.

[61] Murzin F.A., Bratsev S.G., Nartov B.K. A Parallel Automatic System for Image Processing, in Computer Algebra and Its Applications to Mechanics, Nova Science Publishers, Commack, NY 11725, 1992, 210 p.

[62] Murzin F.A., Bratsev S.G., Nartov B.K. Optimum Target Search and Dynamic Image Processing // Advances in Modelling & Analysis, B, AMSE Press, Vol. 26, № 4, 1993. - P. 1-11.

[63] Nartov B.K. Conflict of Moving Systems. - AMSE Press, Prance, 1994. -87 p.

[64] Нартов Б.К. и др. Конфликт сложных систем. Модели и управление. - М.: Изд-во МАИ, 1995. - 120 с.

[65] Крючков В.Н., Мурзин Ф.А., Нартов Б.К. Исследование связей в коллективах и сетях ЭВМ на основе анализа предпочтений // Проблемы конструирования эффективных и. надежных программ. Институт систем информатики им. А.П. Ершова СО РАН. Новосибирск, 1995. -С. 136-141.