thirteen

Отчет участника Rst7 за 2009 год (команда THIRTEEN)

июня 30, 2009 в 13:22 | Новости |

Итак, ICFP 2009 Programming Contest завершился. По результатам на 4 часа до окончания контеста наша команда занимает второе место . Однако, десять решений, попавших в десятку  лучших, организаторы еще будут тестировать на предмет универсальности, а не заточенности под конкретные исходные данные. Я не буду рассказывать, что есть ICFPC (есть гугл), а попробую по горячим следам в двух словах описать ход нашей работы над проектом. На этот раз организационные вопросы имели минимум значения - время проведения контеста выпало на три выходных дня (три - для Украины), был пустующий на выходных офис программерской фирмы (с компами, интернетом, парой спальных мест и, что очень помогло, работающими кондиционерами, в Харькове было очень жарко), который был любезно предоставлен в наше распоряжение.

…День нулевой…

Собравшись вечером 26го июня и вытащив спецификацию, мы увидели что орги приготовили нам следующее развлечение: а) Виртуальный мир с Землей в центре (а в последнем задании - еще и с Луной, тоже гравитирующей) и спутниками, одним из которых мы должны управлять для достижения поставленных в заданиях целей. Всего имелось четыре задания (”проблемы” в терминах оргов) возрастающей сложности. В каждой проблеме имелось 4 подзадания (просто разные исходные данные). б) Эмулятор мира суть виртуальная машина (спецификация на которую содержится в заданиии), для которой орги дали бинарный код, который, выполняясь на этой VM, симулирует виртуальный мир. VM общается с нами через порты ввода (туда мы посылаем наши команды управления) и порты вывода (через них мы видим состояние мира). Естественно, VM тоже нужно было заимплементить - достаточно тривиальная задача (если не гнаться за производительностью, но об этом чуть позже). в) Собственно задания (”проблемы”) - переход с одной круговой орбиты на другую; встреча со спутником, болтающимся на другой круговой орбите; аналогичная встреча, но орбиты могут быть эллиптическими; и последняя жесть - облет десятка спутников, при этом в мире есть Луна и один из спутников летает вокруг нее. г) Имелась система начисления очков за выполнение заданий - была некая пропорция между затраченным временем и израсходованным топливом - где-то между крайними случаями лежал оптимум с максимальным количеством очков. Правда, орги допустили баг в подсчете очков за выполнение первого задания, и топливо было выгодно сжигать целиком. Что, собственно, особо не влияло на конечный результат, если изначально оптимизация траекторий велась по максимизации количества очков (требовалась только замена весовой функции, что и было проделано). д) Результаты надо было сабмитить на сервер оргов в виде лога своих команд, посылаемых через порты ввода в виртуальную машину. Собственно, сервер прогонял решение на референсной VM, и, согласно полученному количеству очков, устанавливал место команды в топлисте. е) Финально орги будут проводить ручное тестирование засабмиченных исходников для лучшего десятка команд на других начальных данных - это для того, чтобы не возникало желания вручную подстроить алгоритмы для конкретных заданий. В качестве исходного толчка для тех, кто вообще не в курсе дела, был приведен пример перехода с круговой на круговую орбиту по гомановской траектории - это случай минимального импульса, но максимального времени выполнения маневра. Итак, задание было раскуренно и мы приступили. Сразу же было принято решение делать не VM в обычном смысле этого слова, а произвести трансляцию бинарного кода в исходный код на Java, затем банально выполнять уже его. В течении первых нескольких часов был написан компилятор и визуализатор - теперь стало возможным увидеть, что происходит в мире. Где-то в этот момент я отправился спать.

…День первый…

Далее началась имплементация гомановского перелета и обсуждение последующих задач (по мере продвижения решения первой проблемы). В этот момент я немного отстранился от обсуждения/педаленья для того, чтобы вспомнить все, что мне известно об астродинамике. В детстве/юности было прочитанно достаточно много книг по этой тематике с возрастающим уровнем сложности. Последняя книга, попавшаяся мне лет пять-семь назад, была “Механика космического полета в элементарном изложении” и была тогда с удовольствием прочитана. Собственно, в этой книге были разобраны вопросы с качественной точки зрения (ведь “в элементарном изложении”), теперь пришло время количественного решения задач. Кроме того, рассудив здраво, я понял, что практически проблема с большим номером включает в себя решения проблем с меньшим номером. Примерно помня, какие методы применяются профессионалами для проектирования орбит, и освежая память гуглем, было найдено несколько серьезных книг по астродинамике (как буржуйских, так и наших), в которых было дано описание решения проблемы Ламберта. В двух словах - проблема Ламберта - суть нахождение точной орбиты тела в случае если известен только кусочек орбиты - два радиус-вектора (начало и конец этого кусочка) и время, за которое тело проходит этот кусочек. Более точно, решение проблемы Ламберта дает два вектора скорости на входе в кусочек и на выходе. Собственно алгоритм перелета из точки в точку выглядел бы в первом приближении следующим образом (так он представился мне в мозгу буквально в течении десятка секунд в какой-то момент раскуривания проблемы Ламберта): а) Выбиралась длительность перелета. б) Запуском VM с текущего состояния на время, равном длительности перелета, находилось положение конечной точки. в) Положение начальной и конечной точки плюс время скармливалось решателю проблемы Ламберта, на выходе имели два вектора скорости. г) Собственно перелет представлял из себя сообщение нашему спутнику импульса, равного разности текущего вектора скорости и вектора скорости в начальной точке траектории перелета (это нам вернул Ламберт, после импульса мы выходим на траекторию перелета), затем ожидание (то самое время, которое мы выбирали на этапе “а”), и сообщение выравнивающего импульса, равного разности текущей скорости в конечной точки и скорости цели (т.к. до цели мы уже долетели, разность координат стремится к 0, осталось только выровнять скорость). Благо, было совершенно пофиг, весь импульс (хоть 50км/с) можно было приложить за один тик мира (1 секунда). Кроме того,  в этом виртуальном мире топливо ничего не весило Однако, сначала я решил исследовать поведение решателя проблемы. Был взят MATLAB и сделан первый вариант, подсмотренный в Atmospheric and space flight dynamics К сожалению, код, приведенный в книге, правильно расчитывал тестовое задание (приведенное там же), но почему-то дико глючил на тестовых векторах из нашего мира. Было найдено еще несколько алгоритмов в других книгах, различающихся в деталях решения и, в конце концов, родилась собственная имплементация (пока на MATLAB’е) - основное отличие - использование половинного деления в итерациях, а не метода Ньютона, который почему-то плохо сходился. Где-то в этот момент я отвлекся (для отдыха) и помог в решении проблемы неточности прилета нашего спутника в конечную точку по гомановской траектории. Был заимплементен алгоритм, который банально доруливал до нужной орбиты и выравнивал скорость. После чего вернулся к проблеме Ламберта. Краем уха и глаза я наблюдал, как SAS и Brox пытаются комбинацией гомановских перелетов решать вторую и третью проблемы. Исследования поведения проблемы Ламберта при различных входных t (с постоянными радиус-векторами на входе) показало, что имеются различные минимумы требуемых импульсов. Было принято решение заимплементить простой перебор времени перелета и найти максимальный счет (функция от времени и суммарного требуемого импульса). Кроме того, имело смысл ввести  дополнительную регулируемую задержку первого включения двигателей для поиска оптимального “стартового окна”. В этот момент, я нашел нужным объявить всем, что у меня в общих чертах готов универсальный алгоритм, который позволит решить нам все четыре проблемы: а) Проблема номер один - вешается псевдоспутник, и производится перелет на него (несмотря на то, что первая проблема на данный момент была решена общими усилиями других членов нашей команды). б) Проблема номер два и три - для моего алгоритма не отличаются. в) Проблема номер четыре - требует просто бизнес-логики как надстройки над моим алгоритмом - в простейшем случае просто десять последовательных перелетов либо какой-то более умный выбор последовательности (что и было в конце-концов заимплементено). После некоторого сопротивления, я заставил San’а бросить твиканье текущего решения и заняться имплементацией моего алгоритма. Примерно через час-другой алгоритм заработал и начал приводить нас к цели с довольно приличной погрешностью (километры) (что и было закомиченно на svn San’ом в виде ревизии 874 с весьма льстящим мне комментарием). Что вообщем-то меня не очень испугало, так как я четко понимал, что результаты интеграции уравнений движения (расчет мира в виртуальной машине) и расчет кеплеровского эллипса (проблема Ламберта) не будет сходится с достаточной точностью. Посему, San’у была дана команда заимплементить коррекцию нашей траектории (которую нам дал Ламберт) любым удобным способом - например, градиентным спуском по результатам симуляции траектории. Сам я отправился спать, а под утро San сообщил мне, что все готово (и теперь настала его очередь отдыхать).

…День второй…

Примерно к обеду моя тестовая “кровать” (RstTestBed.java) вполне хорошо решала проблемы 2 и 3 и было принято решение переходить к проблеме 4. “Кровать” так и осталась в проекте до конца, как платформа для решения всех задач. Для получения вменяемых результатов по быстродействию было принято решение закэшировать положение всех других спутников в течении 3х миллионов секунд (это ограничение сверху на длительность решения проблемы, которое фигурирует в условиях). После этого поиск траектории через решение проблемы Ламберта стал весьма быстр и появилась возможность производить выбор спутника для посещения с точки зрения максимизации счета. Однако, после этого недостаток быстродействия стал вылезать процедуре finetuning’а траектории методом градиентного спуска. Было принято злое решение - захачить непосредственно код оргов для виртуальной машины, чтобы он считал исключительно нашу траекторию, а другие спутники не считал (ведь их положение не зависит от нашего поведения и они закэшированны). Я попробовал было врукопашную захачить java-код, который был сгенерен компилятором из бинарника, однако, удовлетворительных резульатов полученно не было, и San предложил реализовать создание дерева всех референсов регистров данных внутри бинарника, после чего “заказать” компилятору компиляцию только того кода, у которого есть референсы (вложенные в том числе, конечно) к интересующим нас регистрам. Через пару часов результат был получен - примерно десятикратное ускорение расчета градиента. Так как такое решение пахнет отсутствием универсальности, Brox занялся изготовлением тулчейна для получения кастрированных виртуальных машин по заказу, что и было выполено ближе к концу соревнования. Теперь наш код собирается скриптом с автоматической компиляцией нужного кода. А мы в это время продолжили свои занятия: San - имплементацией greedy-алгоритма поиска наилучшей последовательности облета спутников, я - довел до ума задачи 2 и 3 - теперь можно было полностью избавиться от доводчика в нужную точку в конце траектории - импульс торможения теперь учитывался при градиентном спуске, что дало свой результат - попадание в заданную окрестность (мы приняли 200 метров, достаточно было 1км) с ошибкой по скорости в пятом знаке. Правда, иногда метод градиентного спуска плохо сходился, и было принято решение ввести коррекции - если за вменяемое время результат finetuner’а не получен, то оптимизация прекращается, производится пролет по наилучшей пролученной траектории половину расчетного времени и опять выполнение  нашего алгоритма (ламберт,  градиент, и т.д.). В результате мы научились делать коррекции траектории в процессе полета. Причем, обычное значение импульсов в точках коррекции были порядка 0.5-10м/с. В общем, схемы полетов, генерируемые нашим софтом, стали очень походить на схемы полетов  больших братьев из реального мира. Это лично мне добавило количество полученного fun’а. В этот момент орги заменили четвертый бинарник - оказалось, что Луна не гравитировала. При использовании нашего алгоритма на новом бинарнике неучет Луны приводил к разбиванию о ее поверхность. Было принято решение заимплементить переключение системы координат при решении проблемы Ламберта из геоцентрической в селеноцентрическую, если наш спутник находился в сфере действия Луны. San был отправлен спать, Brox и я занялись внесением необходимых перерасчетов. Часа в четыре утра Brox отправился спать, а я продолжил и в 7.28 утра третьего дня закомитил полеты с учетом Луны. При этом, если траектория пересекала границы действия Луны, то происходило переключение системы координат и перерасчет остатка траектории в  другой системе. После чего поднял San’а и Brox’а, доложил им результаты и рассказал про мегажопу - летать мы летаем, флаги посещения спутников в портах вывода виртуальная машина выставляет, а счет - не ведется - летаем впустую! Баг надо было найти и зафиксить, но это легло на плечи San’а, SAS’а и Brox’a - сам я ушел спать с требованием разбудить меня или около трех часов дня (~6 часов сна для очищения головы, если вдруг товарищи не справятся с фиксом и понадобится свежий взгляд) или воплями об удачном фиксе бага (тогда можно просыпаться, вроде особых проблем впереди не будет). …День третий и последний… Полдня я проспал, был разбужен воплями о фиксе (оказалось, что замена printf(”%G”) в компиляторе VM на прямой ввод бинарных данных проблему решил), спросил - “какие-то проблемы сейчас есть?”, получил отрицательный ответ и доспал до трех часов дня. Проснувшись, выпив чашку кофе и покурив (табак! не подумайте;) ), я решил посмотреть, кому какая помощь нужна. Оказалось, что SAS решил допилить проблему номер один под использование решения проблемы Ламберта, однако, кое-что у него не получалось и мы общими усилиями довели дело до ума. При этом был получен максимальный счет - 97 очков за подзадание (хотя, многие в конференциях утверждали о 96ти очках максимум). San засабмитил на сервер оргов все подрешения четвертой проблемы - в результате мы вышли на первое место в топлисте с суммарным счетов в 5025 очков. Правда, через некоторое время появилась команда (человек?) pepsiso, у которой суммарный результат был 5171, и мы спустились на второе место. Где-то в это время общая таблица перестала обновляться, и дальнейшую смену мест мы не знаем. Затем SAS и я допилили решение проблем 2 и 3 для получения максимальных результатов. Однако, выигрыш был невелик, буквально, 2-3 очка (проблема оказалась в неточном соответствии нашей функции подсчета очков и функции, имплементированной оргами в виртуальной машине) (счет достиг 5036 очков). В общем, возврат на первое место на данный момент зависел только от San’a, который оптимизировал перебор спутников - там можно было вполне выиграть 150 очков. Все подключились к решению задачи, однако, в последние часы более оптимального алгоритма полученно не было - оказалось, что иногда очень медленно сходится градиент и нам просто не хватило времени на вычисления. Собственно говоря,

…21 час по киевскому времени…

был встречен без каких либо воплей разочарования - “ну второе место, так второе”, кроме того, еще предстоит запуск решений оргами на других задачах, там посмотрим, как себя поведут наши и чужие алгоритмы… Следует небольшой релакс, первое спокойное обсуждение и подведение итогов - все сошлись во мнении, что каждый получил достаточную дозу fun’а. Ну, как собственно и планировалось. И на посошок, лично мои общие впечатления: а) Мы (как команда) уже третий раз участвуем (ICFPC2008, Sapka и уже прошедший ICFPC2009) - каждый раз ощущения от происходящего все лучше и лучше. Кроме того, намного лучше расчитали свои силы. И я, торжественно пообещав в самом начале, что тупить не буду (как на ICFPC2008 - ниасилил не то, что заимплементить, а даже подумать о применении банального PID-регулятора для управления ровером), свое обещание выполнил - выдал универсальный алгоритм, который лег в основу решения всех проблем. б) Отрицательные впечатления о стиле программирования “пишем скелет функции, втыкаем точку останова, запускаем и допиливаем все на ходу”. Именно такой стиль программизма у San’а. Я так не могу, не хочу, не буду и вообще - “Это не наш метод!” (С). в) Зря бросил MATLAB. Надо было поисследовать поведение градиентного спуска. Но в целом - fun получен, все - rulezzz! PS Совсем забыл     svn://avarie.org.ua/ICFPC2009 svn://hub.kharkov.ua/ICFPC2009 login=guest; pass=guest