Математики разработали алгоритм, который решает сложнейшую задачу планирования межорбитальных полетов к астероидам. Новая математическая модель рассчитывает абсолютно лучший маршрут для космического корабля за считанные часы вместо недель неопределенности. О своем алгоритме авторы рассказали в статье журнала INFORMS Journal on Computing.
В земных условиях задача коммивояжера — поиск кратчайшего пути между неподвижными городами — решается сравнительно легко. Но если перенести ее в космос, сложность возрастает многократно. Астероиды движутся со скоростями в десятки тысяч километров в час, и их точное положение непрерывно меняется в зависимости от времени старта корабля.
Устранение вычислительного тупика
Ранее для планирования многоцелевых космических миссий инженерам приходилось полагаться на эвристические методы, то есть на приблизительные оценки и догадки. Точный расчет требовал колоссальных вычислительных мощностей, так как при изменении времени прибытия к одному астероиду мгновенно менялись условия полета ко всем последующим.
Новая научная работа описывает многоэтапный метод решения этой проблемы. Математики начали со схемы «диаграммы решений», представив все возможные маршруты в виде компактного послойного графа. Чтобы упростить расчеты на первом этапе, они убрали временное ограничение на ожидание на орбите, приняв его стоимость за ноль.
Метод точного отсечения
Затем ученые применили разработанную ими технологию под названием Peel-and-Bound. Алгоритм выбирает наиболее перспективные ветви на диаграмме и запускает для них полный цикл баллистических расчетов, сравнивая результаты. Если находится более выгодный маршрут, все заведомо проигрышные варианты баллистики мгновенно отсекаются.
В ходе тестов система всего за два часа рассчитала математически идеальную траекторию для последовательного посещения десяти движущихся астероидов. При увеличении числа целей до 15−30 объектов новый алгоритм в разы превзошел все существующие методы по скорости вычислений, установив новый мировой рекорд.
У модели есть ограничения — она пока рассчитана на мгновенное изменение скорости двигателями, в то время как будущие аппараты получат ионные двигатели малой тяги. Тем не менее, этот прорыв закладывает основу для будущей промышленной добычи ресурсов на астероидах и планирования сложных исследовательских миссий.
Ранее американский ученый заметил в произведении «Ад» Данте описание падения астероида.
