dastapov: (Default)
[personal profile] dastapov
Имя команды: li-monad (спасибо aleksey/jabber.ru за идею)
Состав: я, endless-world, [livejournal.com profile] iakovz, при участии blancus.
Итоговый бал: 2234.7171 (12 problems solved)

Поскольку scoreboard традиционно перестал обновляться за пару часов до окончания соревнования, мне сложно сказать, какое же место мы заняли в конце-концов. Если все остальные участники расслаблялись перед финальным свистком и ничего не делали, то это будет 59-е место.  Но скорее всего в расстановке сил перед самым финишем наверняка произошли существенные изменения, и я буду рад, если нас не "выдавят" хотя бы из первой сотни.



Как я уже писал, в этом году я перепутал июнь с июлем, и чуть было не пропустил ICFPC вообще. О том, чтобы собирать команду, не могло быть и речи - на это просто не было ни календарного, ни свободного времени. В результате, в последние два дня перед соревнованием я попытался найти команду, к которой можно было присоединиться, но все места уже были заняты.

В ходе моих поисков на #icfp-contest в последний день, буквально за 6 часов до начала, меня законтачили два человека и предложили объединится в импровизированную команду. Я согласился, тем более, что вероятно было участие еще пары англоязычных персонажей из haskell community. Забегая наперед, с сожалением констатирую, что из этой попытки ничего особо хорошего не вышло, т.к. командного взаимодействия у нас не получилось, и команда буквально развалилась на ходу еще до конца первых суток. Строить общие планы мои соратники по команде не спешили, чем планируют занимаются - не говорили, а в середине второго дня [livejournal.com profile] iakovz вообще пропал, оставив вместо себя полезную ссылку на книгу "Orbital Mechanicas" и приведенного в командную конференцию математика blancus, который честно пытался нам помочь :)

Впочем, обо всем по порядку.

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

Задача сводилась к написанию кода, который выдает "программу" управления спутником для решения задачи по орбитальному пилотированию. Участникам было предложено решить несколько задач с возрастающей степенью сложности, каждую из которых нужно было решить для четырех разных наборов входных данных:
  1. Перевести спутник, движущийся по круговой орбите вокруг центрального тела (Земли), на круговую орбиту с другим радиусом
  2. Произвести "стыковку" с другим спутником, движущимся по круговой орбите
  3. Произвести "стыковку", но при условии, что начальная орбита управляемого спутника и спутника-цели - это не круги, а эллипсы
  4. Пролететь в радиусе 1 км от 11 спутников, движущихся по произвольным орбитам, дозаправляясь топливом на орбитальной заправочной станции и учитывая влияние не только Земли, но и Луны
Программа управления спутником состояла из команд по включению двигателя в определенные моменты времени, которое приводила к мгновенному изменению скорости спутника. Эту программу можно было рассчитывать на листике в клеточку, считать в специализированном ПО вроде MATLAB или Mathematica, или генерировать програмным путем. Для проверки корректности рассчетом можно было скормить свою программу в предоставленный организаторами симулятор движения небесных тел и убедиться, что спутник действительно прилетает куда надо.

Правда, чтобы обеспечить возможность запуска своего кода в любой среде, организаторы скомпилировали свою программу в код некой виртуальной машины, спецификации на которую прилагались в задании. Соответственно, у участников было два пути проверки правильности своих решений - или заливать их на сайт организаторов, где они проходили проверку в течении 5-60 минут, или самостоятельно реализовать описанную виртуальную машину и получить возможность запускать "проверялку" у себя на компьютере.

День первый, старт соревнования в 21:00 EEST 26.06

Мы в течении получаса читали задание, а потом собрались в jabber, чтобы его обсудить. Выяснилось, что понимаем мы его примерно одинаково. После этого мы подключились к gobby и совместно набросали высокоуровневый дизайн решения. Где-то в 23:00 все, кроме меня, отвалились спать, не оставив никаких вещественных результатов. Endless-world сказал, что он пишет VM, и завершит ее завтра с утра. Я написал декодирование байт-кода от организаторов в вид, пригодный для потребления виртуальной машиной и набросал код, который объединяет еще не написанные модули - декодер байт-кодов, VM, поиск решений предложенных задач, формирователь файла с решениями и т.п. - и тоже отправился спать

День второй, 27.06

Организаторы приложили к условию задачи ссылку на страницу на wikipedia с описанием одного из способов решения первой задачи. Казалось бы - бери, кодируй и запускай. Однако, быстро решить первую задачу не получилось. Хотя первая версия VM была готова еще в 10:00, нормальной запустить ее удалось только в 13:40. Мешали как баги, допущенные нами в реализации, так и баги, допущенные организаторами в спецификации. Кроме того, в библиотеке, которую я использовал для побитового декодирования данных, обнаружился мерзкий баг, который периодически приводил к потере данных. Как известно, эффект от независимых багов не складывается, а умножается, что и привело к такой потере темпа.

Еще час был потерян из-за того, что все константы, кроме одной, были указаны в условии в шестнадцатеричном виде. Мы этого при беглом чтении не заметили, и указывали номер задачи в виде 0x1001 вместо 1001.  К 15:00 мы с endless-world независимо друг от друга реализовали две версии решателя, вычисляющего параметры Гомановского перехода на другую круговую орбиту, и выяснили, что мы совсем забыли с институтских времен и физику, и математику, и тригонометрию. Разнообразные досадные ошибки (забыли домножить в нужном месте на массу Земли; забыли, как рассчитать вектор, перпендикулярный к данному; ...) привели к тому, что в 17:00 спутник у нас уже летал, но в цель попасть никак не мог.

Перепробовав несколько вариантов расчета перпендикуляра, "смотрящего" в нужную нам сторону (да-да, и нечего смеяться), пересчитав несколько раз формулы из wikipedia по найденной умной книге и оптимизировав VM, чтобы она не отжирала память при работе, мы в конце-концов получили в 19:00 код, решающий первую задачу, для всех четырех вариантов известных старторвых условий.

Ура! Получается, что мы еще успеваем сдать какие-то результаты для участия в т.н. lightning round - соревновании по результатам, полученным в течении первых суток. Но не тут-то было - отосланные организаторам программы управления были проверены и получили оценку "CRASHED!"

Возможных причин было несколько: неправильный формат файла с результатами, спутник врезался в Землю или спутник истратил в ходе маневров все топливо. Т.к. я был уверен, что летаем мы правильно и топливо экономим, я принялся сличать генерируемый нами файл с описанием формата в спецификации. Вроде бы все делаем правильно, а результат не засчитывают - ну, хоть убейся. В конце-концов я смирился с тем, что в формате файла ошибок у нас нет. Получается, мы плохо управляем спутником?

Как выяснилось - мы плохо прочитали и поняли условие задачи. Нам казалось, что если в программе записано "в момент времени T подать имульс V в направлении a", то двигатели включатся и выключатся. А по спецификации получалось, что они включатся и будут работать до тех пор, пока в программе не встретится команда "в момент времени T' подать импульс величиной 0". Соответственно, по мнению организаторов все наши программы врубали газ на полную и летели, куда глаза глядят, вплоть до исчерпания запасов топлива.

К сожалению, осознание этого факта пришло ко мне уже после окончания lightning round-а. Первые наши результаты были приняты уже 28-го числа, сразу после полуночи.

День третий, 28.06

Выяснилось, что организаторы ошиблись в своем коде, и для первой задачи можно получить больше баллов не экономя топливо, а наоборот - тратя его :) Организаторы сказали, что так уже и будет - для первой задачи больше балов получают "растратчики", а для всех следующих - те, кто экономит топливо.

Endless-world прочел об этом в блоге организаторов и реализовал хак, который сжигает остатки топлива после выхода на целевую орбиту, и мы получили за первую задачу 382 балла из 400 возможных!

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

Кроме этого, в коде решателя первой задачи (который я хотел переиспользовать для решения второй задачи) нашлись два бага, которые компенсировали друг друга. Со скрипом и проблемами, с многочисленными правками физических рассчетов, к 16:00 появилась версия решения, которая пыталась выполнить phasign -- тот самый маневр по догонянию спутника-цели.

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

Попытки сделать какой-то "подруливатель" успехом не увенчались - становилось только хуже. Во второй половине дня я плюнул, взял Mathematica и самостоятельно вывел решение задачи phasing-а с нуля. Результат получился выше всяких похвал - маневр завершался в пределах +-50 метров от цели, и в течении 900 секунд мы отлетали максимум метров на 100-200. Вторая задача пошла в зачет :)

Мы не писали какого-то отдельного специального визуализатора - наша VM выводила отладочный лог с координатами нашего и целевого спутников на каждом шаге, а я использовал gnuplot для рисования красивых по этому логу:



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

На втором графике видно, как менялось расстояние до цели (синяя кривая) и расстояние от нашего спутника до Земли (красная кривая) с течением времени.

День третий, 29.06

В общем чат-логе за этот день нет ни одной строчки - все куда-то окончательно разбежались :(

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

К сожалению, все доступные мне источники знаний, как сговорившись, рассказывали о том, как рассчитать параметры орбиты по двум наблюдениям летящего тела - т.е. нам известны только два расстояния от летящего тела до земли и угол между векторами наблюдения. Это так называемая задача Ламберта. Она не может быть решена в общем виде аналитически, требуется составлять и решать численными методами дифференциальные уравнения. Я потратил пол-дня, пытаясь реализовать искомое, но безуспешно. К середине дня мною был найден в сети документ, описывающий значительно более простой метод Гиббса, позволяющий вычислить в аналитическом виде параметры орбиты по трем наблюдениям.

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

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

Отдельно хотелось бы поблагодарить любимую [livejournal.com profile] yulanta за предоставленную возможность предаваться сомнительным развлечениям :)

Официальный scoreboard, по состоянию за 5 часов до окончания соревнования

И, наконец, немного статистики и всяких фактов
Объем кода: 1077 строк (из них 100 - VM, и 100 - базовые функции для физических рассчетов), язык - Haskell
Скорость работы VM: ~10 секунд на любой сценарий задачи 1
Кол-во commit-ов в репозиторий: 170 (151 - я, 14 - endless-world, 5 - [livejournal.com profile] iakovz)
Кол-во найденных в сети и просмотренных книг по орбитальной механике: 15
Из них полезных: 3
Кол-во памяти, потребляемой первой версией VM: от 400 до 3000 Мб, в зависимости от сценария (из-за неудачного design decision сборщик мусора не мог собрать старые версии состояния VM)
Кол-во памяти, потребляемой VM после оптимизации: от 5 до 20 мб

Финальная версия кода
http://adept.homeunix.net/icfpc2009

Отчеты и репозитории других команд (список будет пополняться)
From:
Anonymous
OpenID
Identity URL: 
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

Profile

dastapov: (Default)
Dmitry Astapov

July 2017

M T W T F S S
     12
3456789
1011 1213141516
17181920212223
24252627282930
31      

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags