Pull to refresh

Миниотчет об участии в ICFPC 2009

Sport programming *
ICFPC это ежегодный конкурс программистов. Здесь мой отчет об участии.

Задание описано сто раз, можно посмотреть здесь habrahabr.ru/blogs/icfpc/63279

В двух словах:
Вокруг земли крутится несколько спутников, мы управляем одним из них. Надо выполнить задания, написав серию включений двигателей. Задания проверялись на виртуальной машине-симуляторе, программы для которой предоставили организаторы.

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

Напомню список задач (в каждой по 4 сценария)
  1. Перейти с одной круговой орбиты на другую круговую
  2. Тоже только на второй орбите есть другой спутник и нам надо к нему приблизиться и следовать за ним
  3. Тоже только орбиты обоих спутников — произвольные эллипсы
  4. Спутников 10 штук + заправочная станция. Надо посетить их все (пролететь рядом)


Пятница 26, Вечер. Уходя с работы, я заглянул через плечо коллеги, читавшего задание, и успел выловил только пару ключевых слов «виртуальная машина» и «спутник». По пути домой в поезде я гадал каким может быть задание и решил, что скорее всего придется писать компилятор в язык какой-то ВМ. Добравшись домой и прочитав наконец задание, я понял, что написание компилятора отменяется — ВМ была просто тривиальной. Написать компилятор можно было, но в обратную сторону — с языка ВМ в машинный код.

Языком был выбран Питон. Для визуализации я планировал использовать Mathematica. Т.к. рабочий ноутбук с лицензионной Математикой был забыт на работе, она была срочно скачана с торрентов и установлена.

Я решил не морочить голову поначалу и накатал меньше чем за час ОрбитальнуюМашину на Питоне. После чего потратил час на поиски неуловимого бага, который был найден в конце концов… в тексте задания. К тому моменту организаторы выложили новую версию спецификации, в которой по-другому был определен параметр сравнения. После фикса «бага» всё заработало и в последствии ни разу не глюкнуло. Между делом, отлаживая ВМ, я вытащил из кода организаторов значения физических констант (они отличались от спецификации в паре бит). Так прошел вечер Пятницы и я пошел спать.

Суббота:
Задача явно разбивалась на две части. Во-первых у нас есть физика движения спутников, которую не плохо было бы реализовать. Во-вторых ВМ работает с конечной точностью, поэтому даже точные решения надо подгонять, плюс в четвертой задаче явно просматривается необходимость глобальной оптимизации функции SCORE(Fuel,Time), что можно сделать только численно. Подумав я решил, что есть три стратегии, которые я привожу по возрастанию сложности:
1. Чисто численный метод грубой силы
2. Чисто аналитический вариант
3. Комбинированный

Метод №1, нет физики: Просто симулируем траекторию с какими-то начальными параметрами взятыми с потолка, которые улучшаем методами численной оптимизации (градиентный спуск, Монте-Карло и тд). Нужна очень быстрая ВМ и немного эвристики. Идеально подходит для одиночек, желающих получить «максимум очков любой ценой». Он 100% решает первых три задачи, а вот в 4ой уже будет напряг, т.к. пространство параметров для оптимизации огромно и алгоритмы будут сходиться очень медленно.

Метод №2, только физика + немного эвристики: Все задачи в том виде, в котором они были сформулированы в первой версии условия, решаются точно (потом добавили Луну в 4ую задачу, что немного всё усложнило). Поэтому можно засесть за формулы и сделать «умное» решение. Недостаток в том, что как я писал выше, точные решения не подходят их надо корректировать.

Метод №3, берет лучшее от первых двух. Пользуемся точными решениями (которые корректируем численно). Наличие хорошего начального приближения существенно ускорит глобальную оптимизацию про «времени-топливу». Недостаток — слишком много работы для одного человека.

Я решил начать с Пункта 2 и по возможности двигаться в сторону оптимального решения 3.

Первым делом было логично реализовать описанный в википедии т.н. переход Гомана. Суть в том, что мы делаем два управляющих импульса: первый переводит на промежуточную орбиту, второй на конечную.

На картинке: момент перехода на целевую орбиту, жирным отмечено место включения двигателей.


Решалась задача с прицелом на будущее и я сразу написал довольно продвинутый класс Orbit, который в последствии много раз расширялся. Интересно что многие нашли книгу Orbital Mechanics и считали траектории по трем точкам. Но в нашей задаче, кроме положения также известна скорость, поэтому можно считать траектории по ДВУМ точкам. Кроме стандартных параметров орбиты, сразу считалась куча полезных вещей: полуоси, эксцентриситет, энергия, момент импульса, период обращения.

Забегая, вперед скажу, что толковый интегратор у меня так и не дошли руки написать. Все расчеты были основаны на двух последних точках симуляции ВМ и третьей (следующей) предсказанной волшебной функцией getNextXY (можно сказать, что это эмбрион интегратора-предсказателя, если его запустить в цикле получится полноценный предсказатель, но медленный))))

В качестве координат я выбрал, полярные с Землей в центре. В этих координатах все возможные свободные орбиты описываются одним уравнением с тремя параметрами:
R(PHI)=a*(1-e^2)/(1+e*cos(delta+PHI)),
где а — большая полуось, е — эксцентриситет, delta — угол поворота орбиты.

По ходу дела я вывел формулы для касательных к эллипсу в произвольной точке и формулу для эллипсов касающихся друг друга в заданной точке (на самом деле таких эллипсов бесконечно много). Для третьей задачи я хотел вывести формулу находящую по двум заданным орбитам третью касательную к ним. Но подходил конец Lightning Round и я решил засабмитить хоть что-то, но не успел написать сериализацию решения в файл.



Занятно, что в первой проблеме во всех сценариях точные решения заработали без напильника. Это было довольно впечатляюще: делалось два шага симуляции, по ним рассчитывались траектории и импульсы двигателя, которые потом просто выполнялись до конца безо всякой обратной связи.

После окончания Lightning Round, организаторы выложили новую версию задания, в котором добавили сложностей в виде луны в четвертой задаче. Это исключало её из класса точно решаемых. Но т.к. Луна легче Земли, можно рассчитать приближенные траектории, которые будут достаточно точными несколько оборотов и брать их как исходные для оптимизации. Фактически это тот же эллипс, ось которого медленно изменяется со временем (гораздо меньшим периода обращения).

К вечеру субботы все работало и решало 4 первых сценария «по двум точкам», решения были проверены и залиты на сервер. Под конец я вывел формулу для нахождения точек пересечения эллиптических орбит, чтобы утром добавить полеты по некасательным траекториям и пошел спать.



Утром воскресенья, перечитывая очередную по счету ревизию условия, меня заинтересовало то что в первой задаче оказывается дают больше очков если спалить максимум топлива. Это оказалось фатальным для дальнейшего прогресса.

Сначала я написал простейший алгоритм «сжигания» топлива, считаем сколько надо для перехода, потом излишек тратим, дёргая тягу «туда-сюда» мелкими импульсами и корректируя орбиту если она отклоняется больше чем на 0.1%. Это дало практически в полтора раза больше очков чем в субботу.

И тут мне подумалось «а какой способ оптимальный? наверное гиперболическая орбита!». И меня заклинило (а расклинить было некому). Всё воскресенье я потратил на обобщение моего практически готового кода. К работающим эллипсам (которые потом в ходе дела были не раз сломаны) я хотел добавить гиперболы и параболы. И к вечеру воскресенья мой код уже решал первую задачу «оптимальным способом, по двум точкам» перелетая сразу с третьего шага во времени на нужную орбиту и тормозя там.



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

По ходу дела я напутал в знаках, но всё работало. Зато когда я всё-таки нарисовал траекторию, чуть не лопнул со смеху. Спутник летел до нужной траектории и там резко поворачивал и летел в обратную сторону. Зеленая линия — рассчитанная траектория, красная — как летели.


Остаток вечера воскресенья я провел вылавливая ошибки в знаках, т.к. все формулы сильно зависели от взаимного положения орбит и знаков координат.

На следующий день (проспав три часа), уже на работе, я чуть-чуть подчистил код того, что работало и быстро решил вторую задачу. Но почему-то, не смотря на то, что мой спутник следовал за целью с точностью лучше 900 метров, очков не давали. Я добавил автоматическую стабилизацию орбиты и добился точности нескольких сантиметров в течении десятков тысяч секунд, но очков не давали. Побыв в ступоре минут 15, у меня чуть было не случилась истерика. Я понял, что я летал за «призраком», а точнее за отражением цели. Т.к. организаторам было лень нарисовать картинку в задании, я напутал в знаках и вектор цели был обратным! Добавление минусов в чтение параметров сразу решило все проблемы.

Учитывая что очков у меня и так было мало, я умудрился в последний момент залить одно неработающее решение и потерять еще порядка 100. В итоге там около 1000.

Выводы:
Плюсы:
— получил море фана (а это была цель)
— написал кучу формул и даже частично применил их

в команде, где каждый концентрируется на одной подзадаче, эти формулы принесли бы большую пользу

Минусы:
— без поддержки численных методов, от формул было мало толку (ну это было ясно сначала)
— т.к. не было «давления ответственности» часто отвлекался на ерунду
— организаторы могли бы сильнее озаботиться вопросом совместимости различных архитектур, возможно вариантом было бы использование в ВМ только целочисленной арифметики (хотя я с этими проблемами не столкнулся). Ну и баги в заданиях не порадовали.
Tags:
Hubs:
Total votes 29: ↑27 and ↓2 +25
Views 640
Comments Comments 13