Аспирантский семинар: Разработка автопилота квадрокоптера с применением SDRE-метода / Эффективный алгоритм оптимизации диаметра дерева при добавлении в него одного ребра фиксированного веса

Место: Факультет компьютерных наук, Кочновский проезд, д. 3, ауд. 205
Время: 27 октября, 18:30 – 20:00 

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

Первый доклад

Тема: Разработка автопилота квадрокоптера с применением SDRE-метода
Докладчик:  Александр Семион, аспирант первого года обучения, департамент прикладной математики МИЭМ

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

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

Второй доклад

Тема: Эффективный алгоритм оптимизации диаметра дерева при добавлении в него одного ребра фиксированного веса
Докладчик:  Глеб Евстропов, аспирант первого года обучения, базовая кафедра Яндекс департамента больших данных и информационного поиска факультета компьютерных наук

Shortcut problem — класс задач оптимизации какой-либо из характеристик графа, связанных с расстоянием (средняя длина кратчайшего пути, диаметр, расстояние между фиксированной парой вершин), при условии, что в граф разрешается добавить некоторое, обычно небольшое по сравнению с размером графа, количество рёбер, длины которых порождаются некоторой метрикой. К сожалению, решение эффективнее, чем наивное, как правило, возможно в крайне небольшом количестве видов графов. В докладе будет рассмотрена задача добавления одного ребра фиксированного веса во взвешенное дерево, если ставится задача минимизации диаметра (максимального кратчайшего расстояния по всем парам вершин) взвешенного дерева. Наивный алгоритм позволяет решить данную задачу за время O(n³), в то время как мы рассмотрим сильно-полиномиальное решение задачи за время O(n² log n) и слабо-полиномиальный алгоритм, работающий за время O(n log d), где d — текущий диаметр, а все значения считаются целочисленными.