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

    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.

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

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

    Минусы:
    — без поддержки численных методов, от формул было мало толку (ну это было ясно сначала)
    — т.к. не было «давления ответственности» часто отвлекался на ерунду
    — организаторы могли бы сильнее озаботиться вопросом совместимости различных архитектур, возможно вариантом было бы использование в ВМ только целочисленной арифметики (хотя я с этими проблемами не столкнулся). Ну и баги в заданиях не порадовали.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 13

      +1
      Для одного человека очень даже неплохо, мои поздравления. Если можно, то какое место заняли в конкурсе?
        +1
        За местом я не гнался, кажется где-то во второй сотне. На все просто не хватило рук. Даже если бы я не отвлекся в воскресенье, то результат все равно до первой двадцатки было мало шансов допрыгнуть. В следующий раз буду участвовать хотя бы вдвоем с кем-то, уже должно быть легче. А так приходилось метаться между кодом и математикой (разными к тому же).
        +1
        Статья порадовала.
          +1
          Иногда поражаюсь тому, как люди умело используют для своих задач различные средства, и какими надо быть гениями, чтобы эти средства разработать. Та же, например, Mathematica.
            0
            Matematica действительно очен хороший инструмент. Чего нет там, обычно есть на functions.wolfram.com/. Еще есть www.wolframalpha.com/, но к сожалению эллиптическим секторам её еще не научили)
              +1
              Расскажите, а как вы используете её совместно с питоном? Есть какие-то механизмы или я задаю просто очень глупый вопрос? :)
              Я пока-что пользовался только Маткадом и немного Мэплом? Но как их использовать своместно с питоном даже не представляю :(
                0
                На самом деле особого смысла прикручивать к Matematic'е другие языки программирования нет, её встроенный язык достаточно продвинут сам по себе (например на нем например написана WolframAlpha). Хотя если нужно, то есть интерфейс — MathLink. В поставке есть примеры для Си, Джавы и Дот.Нет.

                К Пиону я её не пытался приделать, просто использовал как визуализатор, с обменом данными через файлы. Да и кстати решить эту задачу на самой Математике можно было в два счета, но это все-таки не спортивно, тк это не ЯП общего назначения)

                Если есть желание посмотреть, что на неё вытворяют есть интересный сайт demonstrations.wolfram.com/ там куча примеров от школьной программы, до ядерной физики
            0
            Отличная статья! Пока читал, возник вопрос, а кто вы по образованию и по профессии? Просто интересно :)
              +2
              По образованию и профессии физик-теоретик. Правда астрофизикой никогда не занимался, так что было интересно покопаться…
                0
                Спасибо, я так и подумал сразу :)
              0
              Тоже не нашел себе команду, но решил не учавствовать :(
              Чет я плохо представляю, как вы за сутки сделали переход между орбитами в декартовых координатах. Можно исходники посмотреть? :)
                0
                Надо было попробовать) Вон ниже пишут, что все равно фан и опыт.

                Я не вполне понял вопрос, какая разница в каких координатах орбиты? ВМ отдавала декартовы, моя программу внутри (в основном) считала в полярных.

                Я не пользовался системами контроля версий, поэтому из исходников представить, что было в первые сутки не возможно) Комментариев там нет, а формулы выглядят примерно так, чтобы занимать меньше места:
                dis=R01*R02*(2*a1*a2 + a1*a1*R01 + a2*a2*R02 - 2*a1*a2*ep1*ep2
                    *math.cos(d1 - d2))*(a2*ep1*R02*math.sin(d1) - a1*ep2*R01*math.sin(d2))**2
                numerator=(*dis + a2*ep1*R02*(a1*R01-a2*R02)*math.cos(d1) 
                  - a1*ep2*R01*(a1*R01 - a2*R02)*math.cos(d2))
                denominator=(a1*a1*ep2*ep2*R01*R01 + a2*a2*ep1*ep1*R02*R02
                  - 2*a1*a2*ep1*ep2*R01*R02*math.cos(d1 - d2))
                alpha1=( math.sqrt(dis)+numerator)/denominator
                alpha2=(-math.sqrt(dis)+numerator)/denominator
                 


                Хотя я же написал «К вечеру субботы все работало и решало 4 первых сценария «по двум точкам»». Это части первой задачи.
                0
                Участвовал, тоже без команды. Ощущения просто фантастические море фана, и адреналина. Решал «3» методом :-) Больше всего было адреналина когда за 15 мин доконца наконецто доделал 3 задачу и начал заливать решения смотря как тикают минуты )))

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое