Космический коммивояжер: новая математика сократит время полета к астероидам на 20%

Новый подход, основанный на классической задаче коммивояжера, может сделать космические миссии к нескольким движущимся объектам — например, астероидам — значительно более эффективными. Авторы увлекательного решения — Исаак Рудич из Политехнической школы Монреаля (Канада) и Михаэль Рёмер, аналитик по принятию решений из Билефельдского университета (Германия).

«Наше исследование носит фундаментальный характер в том смысле, что оно разрабатывает математический аппарат, который космические агентства смогут использовать для планирования миссий», — пояснили ученые в интервью порталу Space.com.

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

Именно с этим сталкиваются космические аппараты, которым предстоит посетить несколько небесных тел. Иногда решение очевидно — например, при использовании гравитационных пращей у планет, как это делали «Вояджер-1» и «Вояджер-2». Однако миссия, которая перелетает с одного астероида на другой, полагаясь только на собственное топливо (а не на гравитационные маневры), гораздо сложнее. Астероиды постоянно движутся по орбитам, и расстояния между ними, а значит и время в пути, не являются постоянными.

Решение найдено

Эта, казалось бы, неразрешимая проблема теперь имеет решение благодаря команде Рудича и Рёмера. Они переформулировали задачу как «проблему маршрутизации астероидов» (Asteroid Routing Problem, ARP). Вопрос звучит так: в каком порядке космический аппарат должен посетить несколько астероидов, чтобы минимизировать и время в пути, и расход топлива? Для этого необходимо вычислить оптимальное время отправления и траекторию между каждой парой объектов.

«ARP особенно сложна, потому что определение точной стоимости и времени в пути требует решения другой сложной оптимизационной задачи — проблемы Ламберта», — объяснили Рёмер и Рудич.

Проблема Ламберта была впервые поставлена еще в XVIII веке швейцарским эрудитом Иоганном Генрихом Ламбертом, который размышлял о том, как найти оптимальную траекторию между двумя движущимися объектами. Позже эту задачу математически решил Жозеф-Луи Лагранж — тот самый, чье имя носят знаменитые точки Лагранжа.

Решить проблему Ламберта для двух объектов — одно дело, но когда объектов (астероидов) становится много, задача быстро становится вычислительно сложной, потому что расчет необходимо провести для каждого возможного маршрута между каждой возможной парой объектов.

Диаграммы решений

Чтобы обойти это ограничение, команда Рудича и Рёмера применила так называемые диаграммы решений (Decision Diagrams). Это разновидность деревьев решений, которые отображают проблему выбора в виде графа, где каждый возможный набор решений представлен как путь на этом графе. В диаграмме решений все различные варианты выбора, ведущие к одному и тому же пункту назначения во времени и пространстве, объединяются в один узел графа. Это упрощает задачу и сокращает количество раз, которое необходимо решать проблему Ламберта.

«Наш подход обычно дает решения, которые примерно на 20% лучше, чем при использовании стандартных методов, а для более крупных задач — до 20% лучше», — заявили Рудич и Рёмер. Этот процент объединяет общее время в пути и расход топлива.

Насколько это значимо? Представьте себе миссию к поясу астероидов, которая требует годами маневрировать между десятками объектов. Экономия 20% топлива может означать либо увеличение срока службы аппарата на годы, либо возможность запустить ту же миссию ракетой-носителем меньшего класса, сэкономив сотни миллионов долларов. С другой стороны, сокращение времени в пути на 20% снижает радиационную нагрузку на электронику и риск отказа систем.

Пока что миссий, посещающих несколько астероидов, было немного. Зонд NASA Dawn побывал у Цереры и Весты. Аппарат Lucy в настоящее время направляется к Юпитеру, чтобы исследовать троянские астероиды. На вопрос, насколько оптимален план миссии Lucy с точки зрения их математического подхода, ученые ответили, что это «было бы, безусловно, интересно». Однако они подчеркивают, что ARP — это сильно стилизованная, почти синтетическая задача, которая учитывает лишь некоторые аспекты астродинамики, но далеко не все. «Чтобы точно смоделировать реальную миссию, вероятно, потребовалось бы учесть множество дополнительных факторов», — признают исследователи.

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

Земное применение и будущее

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

Сейчас команда Рудича и Рёмера работает над адаптацией своего алгоритма под реальные астродинамические ограничения: гравитационные поля планет, необходимость окон запуска и неидеальные двигатели. Они надеются, что их работа привлечет внимание NASA, ESA и других космических агентств. Ведь эпоха одиночных «выстрелов» по неподвижным целям уходит в прошлое — будущее за сложными, многоцелевыми миссиями, способными «пасти» целые рои астероидов, и новая математика может стать ключом к этому будущему.

Если их подход подтвердится в реальных симуляциях, то следующее десятилетие может стать свидетелем расцвета «экономных» миссий, которые раньше считались невозможными из-за непомерных топливных затрат. Как образно выразились сами исследователи: «Мы не просто учим коммивояжера быстрее ходить по магазинам — мы учим его делать покупки в городе, где все улицы движутся».