Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Паращенко Д.А., Царев Ф.Н., Шалыто А.А. XXV конференция памяти Н.Н.Острякова ЦНИИ «Электроприбор», 10–12 октября 2006 г.

2 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов План доклада 1. Автоматное программирование 2. UniMod 3. Постановка задачи 4. Метод решения задачи 5. Результаты

3 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов План доклада 1. Автоматное программирование 2. UniMod 3. Постановка задачи 4. Метод решения задачи 5. Результаты

4 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Основная идея Программные системы должны разрабатываться так же, как системы управления технологическими процессами Система управления является системой взаимодействующих конечных автоматов Состояния События и входные переменные Выходные воздействия Конечный автомат Система конечных автоматов

5 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Автоматное программирование Система управленияМашина Тьюринга

6 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Как строить программы? Поставщики событий Система конечных автоматов Объекты управления Обратная связь

7 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Применение «Железо» Микропроцессоры Микроконтроллеры Программируемые логические контроллеры Парадигмы Процедурная Объектно-ориентированная Языки контроллеров Лестничные схемы Функциональные схемы Программное обеспечение Системы высокой надежности Военные приложения Аэрокосмическая индустрия Встроенные системы Мобильные системы Визуализаторы Web-приложения Клиент-сервер приложения

8 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Преимущества Применимо как для описания статической структуры, так и для описания поведения программы Компактное представление сложного поведения Сочетается с методами формальной спецификации и проверки моделей Проектная документация Автоматическая генерация кода по диаграммам переходов Применимо в параллельном программировании

9 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов План доклада 1. Автоматное программирование 2. UniMod 3. Постановка задачи 4. Метод решения задачи 5. Результаты

10 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Инструментальное средство

11 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Инструментальное средство Локальная и удаленная отладка диаграмм в терминах состояний Проверка формальных свойств диаграмм Интерпретируемый и компилируемый подходы Запись автоматов в нотации UML-диаграмм классов и состояний Встраиваемый редактор UML-диаграмм для платформы Eclipse Запуск диаграмм в «одно нажатие»

12 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов План доклада 1. Автоматное программирование 2. UniMod 3. Постановка задачи 4. Метод решения задачи 5. Результаты

13 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Цель работы Описание технологии моделирования управления движением одного класса беспилотных летательных объектов на основе автоматного программирования Не создание алгоритма управления, а формальное описание сложной логики с возможностью простой программной реализации по этому описанию

14 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Всесибирская олимпиада Технология иллюстрируется на примере задачи заочного тура VI Открытой Всесибирской олимпиады по программированию им. И.В.Поттосина (2005 год) 5/rus/index.shtml 5/rus/index.shtml

15 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Постановка задачи Соревнование летающих тарелок на дальность полета Две команды по восемь тарелок Управление тарелками осуществляет программа на языке Java Цель – разработка управляющей программы

16 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Цель соревнования Удалиться одной из летающих тарелок команды на максимальное расстояние от линии старта

17 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Трасса соревнований Трасса представляет собой полосу бесконечной длины и заданной ширины Изначально тарелки расположены случайным образом на некотором расстоянии от линии старта

18 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Летающая тарелка Двигатель Бак с топливом Бортовой компьютер Аэродинамические рули

19 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Летающая тарелка Летающая тарелка может: Изменять направление движения Изменять расход топлива (т.е. скорость) Сталкиваться с другими тарелками Выходить за пределы трассы

20 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Движение Тарелка движется в соответствии со II законом Ньютона Коэффициенты c 1, c 2 и с 4 определяются аэродинамическими характеристиками тарелки и характеристиками ее двигателя

21 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Аэродинамическое взаимодействие Области пониженного сопротивления воздуха Области повышенного сопротивления воздуха 20° – – ++

22 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Столкновение объектов Столкновение – абсолютно упругое и описывается законами сохранения энергии и импульса При этом, если относительная скорость столкновения > 1 м/с, то обе тарелки выбывают из соревнования

23 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Подведение итогов соревнования При подведении итогов учитываются только тарелки, нормально завершившие гонку Результатом команды считается максимальное расстояние, на которое удалилась летающая тарелка этой команды

24 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Скриншот

25 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов План доклада 1. Автоматное программирование 2. UniMod 3. Постановка задачи 4. Метод решения задачи 5. Результаты

26 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Как написана программа? Управление летательным объектом осуществляет программа, написанная с использованием автоматного программирования с помощью инструментального средства UniMod Управляющая программа разработана в рамках «Движения за открытую проектную документацию»

27 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Стратегия Одна половина объектов движется вперед и уклоняется от границ коридора и рядом находящихся объектов, а вторая половина объектов разбивается на пары При этом объекты в парах движутся, поддерживая взаимное расположение для использования аэродинамического взаимодействия

28 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Схема связей

29 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Система автоматов 7 автоматов Состояние объекта (3 состояния) Режим полета (4 состояния) Радар (2 состояния) Уклонение от границ коридора и объектов справа и слева (3 состояния) Уклонение от объектов спереди и сзади (3 состояния) Полет первым в паре (3 состояния) Полет вторым в паре (3 состояния) Всего: 21 состояние

30 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Автомат «Состояние агента»

31 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Автомат «Режим полета»

32 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Автомат «Уклонение от границ коридора и объектов справа и слева»

33 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Автомат « Уклонение от объектов спереди и сзади »

34 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Автомат «Радар»

35 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов План доклада 1. Автоматное программирование 2. UniMod 3. Постановка задачи 4. Метод решения задачи 5. Результаты

36 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Исходный код Сгенерировано в 4 раза больше, чем написано вручную!

37 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Тестирование При тестировании использовались две стратегии Простая стратегия – все объекты двигаются строго вперед Агрессивная стратегия – один объект движется строго вперед, остальные пытаются сбить объекты другой команды

38 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Статистика соревнований N OK R our R op Δ Max Min Mean Результаты соревнований с простой стратегией N OK R our R op Δ Max Min Mean Результаты соревнований с агрессивной стратегией

39 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Выводы Простая автоматная модель позволяет описывать достаточно сложное поведение Автоматная модель позволяет формализовать процесс написания кода За счет применения инструментального средства UniMod и автоматической генерации кода повышается качество программ

40 Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Применение автоматного программирования для моделирования группового управления движением одного класса беспилотных летательных объектов Спасибо за внимание!