В сентябре в журнале Automatica (Automatica 167 (2024) 111795) была опубликована статья старшего научного сотрудника лаборатории № 38 «Управления по неполным данным» Максима Эмонайевича Бузикова и математика той же лаборатории Алины Муратовны Майер «Minimum-time interception of a moving target by a material point in a viscous medium». Мы поговорили с Максимом Эмонайевичем о чём эта статья, и о том, как складывалась его научная биография.
Расскажите, пожалуйста, о статье .
Эту работу мы делали с Алиной Майер из нашей лаборатории. В статье мы описали и математически обосновали алгоритм для решения задачи быстродействия по перемещению объекта управления в заданное положение для одной из моделей движения. Наши разработки позволяют увеличить на порядки быстроту вычисления оптимального управления, а также гарантировать, что на выходе алгоритма не локально оптимальное решение, а именно глобально оптимальное.
Если выражаться проще, то мы сделали алгоритм, который работает очень быстро и на выходе выдаёт правильный ответ. Задача, которую он решает, состоит в построении маршрута для какого-либо транспорта (вертолёта, корабля или дрона). Причём этот маршрут быстрей всего приведёт нас в желаемую точку.
Этому исследованию предшествовали мои наработки для кандидатской диссертации на тему «Построение траектории наискорейшего перехвата движущейся цели» по специальности 1.2.2 «Математическое моделирование, численные методы и комплексы программ», которую я защитил в феврале этого года на факультете ВМК МГУ им. Ломоносова. В ней я описал общий случай построения аналогичного алгоритма для общего класса задач быстродействия, в том числе нелинейных. Наверное, каждый специалист, когда слышит такие слова, начинает подозревать, что либо у этого алгоритма нет гарантий сходимости к оптимальному решению, либо это вычислительно неэффективный алгоритм, либо при имплементации этого алгоритма нужны конструкции, которые сложно просчитать на практике. Мои наработки относятся к последней категории.
Там действительно присутствуют конструкции, которые, в общем случае, вычислить на практике затруднительно. Однако мне удалось описать аналитически, т. е. конструктивно, все эти детали для достаточно важной модели движения, а именно, для модели Дубинса, которая часто используется на практике для построения опорных траекторий движения для колёсного транспорта, кораблей, дронов и других подвижных объектов.
Наша статья по своей сути расширяет пул моделей, для которых можно сделать все эти построения общего алгоритма из диссертации конструктивными. А именно, в качестве модели движения мы рассматривали материальную точку в среде с линейным по скорости коэффициентом сопротивления, управляемую силой, ограниченной по модулю, но не по направлению. Конкурирующие нашим результаты других авторов, а именно серия работ Л.Д. Акуленко и работы Э. Баколаса, останавливались на получении вещественных уравнений, один из корней которых определяет оптимальное управление. Поскольку эти уравнения могут иметь множество корней, то нельзя считать такое представление решения конструктивным алгоритмом, гарантирующим оптимальность. В нашем же случае алгоритм гарантированно сходится к оптимальному решению.
Если говорить об устройстве алгоритма, то принцип его построения относительно прост, хотя его детальное описание и строгое обоснование не обходится без таких витиеватых конструкций как многозначные отображения. Но если опустить все это, то, по сути, нам надо понимать лишь что такое множество достижимости объекта управления, и какие конструкции мы можем получить из принципа максимума для описания этого множества. Множество достижимости — это такой набор положений объекта управления в заданный момент времени, где этот объект может оказаться, если использовать любые входные воздействия.
Грубо говоря, если мы многократно посадим обезьянку за руль машины, дадим ей полную свободу действий и зафиксируем положения машины через равные интервалы времени, то мы получим некоторое описание множества достижимости в виде набора финальных положений. Принцип максимума Понтрягина, грубо говоря, даёт нам параметрическое описание поверхности множества достижимости, т. е. такую границу, которую обезьянка за заданный интервал времени не сможет покинуть никак.
Далее, если мы каким-то образом научимся вычислять расстояние от произвольного положения до множества достижимости, то можно считать, что все остальное доделает наш алгоритм. Он, таким образом, осуществляет поэтапное увеличение оценки снизу для времени быстродействия, используя расстояние до множества достижимости и скорость изменения этого множества. Такой алгоритм относится к методам простой итерации, где мы просто делим расстояние на скорость, получая время, такое, что в течение него достигнуть целевого положения мы все ещё не могли, поэтому мы безопасно можем его прибавить к основному счётчику времени. Делая это шаг за шагом мы получим хорошую оценку времени быстродействия, а по нему уже можно восстановить оптимальное управление.
Работы было много, поэтому мы делали это все поэтапно. Во-первых нужно было описать это множество достижимости. Получив это описание мы представили его на конференции УБС-2023. Во-вторых, нужно было конструктивно уметь вычислять функцию расстояния до множества достижимости. Доклад об этом мы сделали на МКПУ-2023. Затем мы собрали все воедино, проработали все доказательства теорем о сходимости и уже тогда опубликовали работу в Automatica.
Какая может быть практическая польза от таких разработок?
Если говорить о практической пользе, то, думаю, каждый согласится, что приятнее, когда используемый алгоритм быстрее конкурирующих и гарантирует математически свой результат на выходе. Конечно, если речь идёт об однократных запусках, то будет он работать 1 миллисекунду или 1 микросекунду зачастую совсем не важно.
Однако, если пересчитывать надо много раз с разными параметрами, например, при решении комбинаторных задач обхода сразу многих, возможно, движущихся целей, то такая разница критична, т. к. можно перебрать в тысячу раз больше вариантов за то же время. Также примечательно, что для выбранной нами модели движения в качестве оптимальных траекторий получаются гладкие кривые, поэтому представленный алгоритм может быть полезен для гладкой интерполяции по промежуточным точкам.
Как Вы попали в ИПУ?
На Физическом факультете МГУ есть кафедра Физико-математических методов управления, все сотрудники которой работают в ИПУ. Мне понравилось, что многие задачи были направлены на автоматизацию процессов, а не только на описание явлений, как на других кафедрах отделения прикладной математики. Притягивали математические инструменты, которые обслуживали теорию управления, такие как дискретная и непрерывная оптимизация, функциональный анализ и даже формальная логика.
Последней, ещё будучи студентом, я стал заниматься с академиком РАН главным научным сотрудником лаборатории №38 С.Н. Васильевым. Хотя изначально, честно говоря, я хотел заниматься теорией игр, но так сложилось, что соответствующий профессор кафедры полгода отвечал на моё письмо, а за это время меня соблазнило направление автоматического доказательства теорем, которое читал Васильев. И вот, летом 2017 года я устроился на должность инженера-программиста в лабораторию № 3, которая тогда называлась «Систем логического управления».
За время работы со Станиславом Николаевичем я освоился в формальной логике и языках первого порядка и даже по итогу смог запрограммировать свою систему автоматического доказательства теорем. Также я реализовал систему порождения индуктивных знаний в языке первого порядка. Это очень похоже на то, что делают алгоритмы обучения с учителем в машинном обучении, но с тем отличием, что можно автоматически использовать реляционные данные. Т. е., грубо говоря, моя система конструировала признаки из реляционных баз данных (систем таблиц со взаимосвязями), для дальнейшего использования алгоритмами обучения с учителем.
Кризисным для меня стало то, что я не смог масштабировать предложенный подход на работу с большими данными, поэтому я вернулся к идее заниматься чем-то связанным с динамическими системами и играми. Так сложилось, что осенью 2019 года я перешел в лабораторию № 38 к Андрею Алексеевичу Галяеву и стал двигаться в сторону защиты кандидатской диссертации.
Чем Вы занимаетесь в лаборатории?
Большую часть того, что я сделал, можно описать как разработка конструктивных, гарантированных и эффективных алгоритмов для решения задач быстродействия. Под конструктивностью я подразумеваю непосредственную возможность запрограммировать предлагаемые алгоритмы без дополнительных построений, т. е. довожу все решения до уровня «подставить значения параметров на вход, получить численный ответ на выходе». Под гарантированностью, что свойства выхода алгоритма обосновываются теоремами о сходимости к верному решению. Под эффективностью — затраты времени и памяти у компьютера будут меньшими или сопоставимыми с конкурирующими алгоритмами.
Сами задачи быстродействия, которые я рассматриваю, формализуются в рамках оптимального управления или дифференциальных игр. По существу, в рамках этих задач есть некоторая система, будь то корабль, машина или дрон, и нужно изменить положение этой системы из начального в желаемое за наименьшее время. Таким образом, на выходе моих алгоритмов появляется положение, к которому следует стабилизировать систему в данный момент времени, либо можно извлечь всю траекторию, по которой должна проследовать система для перехода в желаемое состояние за наименьшее время, а также можно извлечь само численное значение времени быстродействия. Тут все зависит от практических целей использования.
С точки зрения практики чаще всего нужно извлекать положение, к которому следует стабилизировать систему, т. е. на примере дрона — у него, как правило, уже есть свой автопилот, который может стабилизироваться вдоль траектории, которую ему дашь. Если траектория будет в должной мере учитывать динамику дрона, то и следовать этой траектории он будет успешно. В моей же практике работы по хоз. договорам больше всего ценилось численное значение времени быстродействия. У нас возникала задача обхода объектом управления многих движущихся точек, динамическая задача коммивояжёра. Это комбинаторная задача, которая требует перебора в своём решении, и при этом переборе достаточно важно уметь быстро оценивать наименьшее время движения от одной точки к другой. Для сложной динамики движения объекта управления с этим справляется мой алгоритм.
Главная тема нашей лаборатории — это управление по неполным данным. У нас многие к неполноте данных подходят с вероятностной точки зрения и исследуют стохастические модели. Оптимальное управление и дифференциальные игры без теоретико-вероятностных конструкций тоже помогают при управлении по неполным данным, если считать за эти данные будущее поведение отдельных компонент системы. Например, если рассмотреть игру в догонялки, то за неполные данные можно считать поведение догоняющего или убегающего и исходить при решении задачи из наихудшего возможного сценария.
Так, например, можно получить метод прямого преследования, известный метод наведения, решая соответствующую дифференциальную игру. Если с играми все понятно, то с оптимальным управлением не так очевидно, где тут может быть польза для управления по неполным данным.
Недавно мы с техником нашей лаборатории П.Д. Долгушиным работали над алгоритмом детектирования возможных столкновений с подвижными объектами. Там мы как раз использовали неполноту данных о том, как будут эти объекты двигаться в будущем, ограничиваясь, грубо говоря, знанием о их максимальных ускорениях, манёвренностях и прочем.
Этого всего хватает, чтобы в рамках оптимального управления установить возможность или невозможность столкновения.
Расскажите, пожалуйста, почему Вас привлекла научная карбера и когда Вы поняли, что хотите заниматься прикладной математикой?
Математику я полюбил ещё на последнем году детского сада, когда нам давали карточки с цифрами и знаками сравнения и просили поставить верный знак между числами.
Мне дали две одинаковые карточки «5» и «5», и знак больше/меньше, смотря как повернёшь. Я перебрал все варианты постановки карточки, в том числе стрелочкой вверх и вниз, но воспитателя такое решение не устраивало. Вышел мой друг, взял со стола воспитателя карточку «равно» и прекратил мои страдания. Мне тогда запала в душу та нестандартность, которую требовала ситуация для решения задачи: знак «равно» я тогда ещё не знал.
Во втором классе мне в школе подарили справочник по элементарной математике, Выгодского, кажется. Несмотря на его сухость, меня занимало его чтение перед сном. Радовало, что я мог предлагать различные пари одноклассникам, в духе: «Спорим, ты знаешь, как получилось слово «восемьдесят», но не знаешь как получилось «девяносто?». Когда спрашиваешь, зная ответ, конечно, чувствуешь себя уверенней и умнее, что не может не нравиться.
Моя учительница математики, Татьяна Николаевна Разыграева, смогла усадить меня учиться математике систематически. Мне очень повезло с её уровнем преподавания и понимания, в особенности вещей, которые выходят за рамки школьной программы.
В старших классах меня увлекли физика и информатика. Выбирая между ними, я поступил на Физический факультет МГУ, думая что буду заниматься теоретической физикой. Но потом мне стала интересна прикладная математика, прежде всего, спектром решаемых задач, и я выбрал кафедру физико-математических методов управдения (ФММУ).
Вы собираетесь продолжать работу в выбранном направлении?
Да, на данный момент мы работу в этом направлении продолжается. Недавно мы опубликовали препринт, в котором систематизированы методы решения задач быстродействия для линейных систем. Также, в рамках существующих методов, мы описали новый алгоритм для конструктивного решения задачи. В сравнении с тем, что я сделал в диссертации, класс задач сузился до линейных. Однако это закрывает тот пункт с конструктивным построением функции расстояния до множества достижимости, который оставался подвешенным в диссертации и компенсировался лишь наличием нескольких практически полезных задач, где это построение возможно.
Также мне бы очень хотелось сравнивать качества алгоритмов не в идеальных условиях численных экспериментов, а на конкретном железе. С этой целью я сейчас прохожу курсы по ROS и Gazebo, чтобы архитектурно встроить разработанные алгоритмы для обкатки на роботах.
Беседу вела Л. Бойко