ICFP Contest 2009
Команда "Покрышкин"
Шура Голубев - Java
Шура Киреев - Scala
Я - Scala
2009-06-26
20:00 Создали репозитарий на Bitbucket. Настроили доступ по ssh.
20:50 Сайт организаторов лежит.
21:00:16 Официальное начало соревнования. Сайт в полном дауне.
21:05 Удаётся скачать задание. Распечатываем, читаем. Тема - управление космическим кораблём. Всего 4 задачи по 4 задания:
- переход с круговой орбиты на круговую,
- старт с круговой орбиты и стыковка со спутником на другой круговой орбите,
- старт с произвольной эллиптической орбиты и стыковка со спутником на другой эллиптической орбите,
- операция "Чистое небо" - сборка космического мусора.
Там же дана спецификация виртуальной машины, для которой организаторами написаны симуляторы космических полётов.
Выбираем название для команды. Решили назвать команду Pokryshkin в честь лётчика-аса Александра Ивановича Покрышкина - нам понравилось известная фраза: "Achtung! Achtung! Pokryschkin ist in der Luft! (Ахтунг! Ахтунг! Покрышкин в воздухе!)".
Посидели до 11, обсудили спецификацию, решили, кто чем будет заниматься (я - физикой полёта, Шура Киреев (далее просто Шура - для краткости :)) - виртуалкой, Шура Голубев - визуализатором) и разошлись спать.
2009-06-27
8:30 Приехал с утра в офис. Начал искать информацию по теории космических полётов.
К обеду Шура закончил виртуалку. Тогда я в срочном порядке набросал автопилот для выполнения манёвра Хохмана, который был нужен для первой задачи. Шура проверил - работает!
Потом Шура провозился некоторое время с записью результата в некотором формате. Некоторое время ничего не получалось - на нашей локальной виртуалке было всё ОК, а на сайте организаторов на это же решение нам писали, что мы врезались в землю, или всё закончилось тайм-аутом. Но, наконец, Шура нашел ошибку в записи бинарника с решением, и нам начислили баллы за первую задачу.
Взялись за задачу стыковки на круговой орбите. Решение было простым - использовать тот же самый манёвр Хохмана, но рассчитать время начала манёвра таким образом, чтобы выйти на вторую орбиту в той точке, где будет находится цель. Сложности это не представляло: угловые скорости и время манёвра можно было вычислить.
К вечеру новый автопилот был готов. Точность вычислений позволяла сразу выйти на цель в пределах заданной погрешности (до 1 км) в 3-х из 4-х заданиях этой задачи. В четвёртом задании после манёвра расстояние между спутниками было слишком большим: несколько десятков километров. Оказалось, что расстояние между орбитами было очень большим, и небольшая погрешность при старте давала большое расхождение. А так как время в системе было дискретным с точностью до 1 секунды, время старта приходилось округлять, что и давало эту самую ошибку. В качестве быстрого решения поменял критерий старта: если округление было большим, ждал следующего удобного момента. Наконец, решение было найдено и отправлено.
В это время Шура занимался проблемой максимизации потраченного топлива в первой задаче. В спецификации было написано, что нужно потратить как можно меньше топлива, а на самом деле больше баллов получало решение, которое тратило топливо по максимуму. Организаторы, когда им сказали об этом несоответствии, выкрутились - сказали, что это не баг, а фича - и оставили всё как есть. Вот Шура и сжигал лишнее топливо, перемещаясь с орбиты на орбиту, перед тем как выйти на заданную. В результате мы вплотную приблизились к десятке лидеров: у десятой команды было 1200 баллов, а у нас - 1100. На этом мы закончили и пошли спать.
2009-06-28
11:00 Решил хорошо выспаться, так как накануне я поспал 5-6 часов, и мне весь день хотелось спать. Приехал в офис самым последним.
Посмотрели турнирную таблицу, которая уже показывает все команды, которые получили хоть сколько-то баллов. За ночь мы опустились на 41 место.
Шура пытается решить 3-ю задачу (стыковку при движении по произвольным эллиптическим орбитам) с помощью всё того же манёвра Хохмана, вычисляя момент, когда можно оказаться рядом со спутником-целью. Это решение было явно неоптимальным по расходу топлива, и поэтому я решил разрабатывать своё, решив задачу оптимизации времени и векторов корректирующих импульсов численными методами. Для этого мне надо было перво-наперво реализовать нахождение параметров эллиптической орбиты по заданным координатам и вектору скорости, а затем, зная эти параметры, определять координаты спутника в любой момент времени. Причём, как Шура уже выяснил, задача вычисления координат аналитического решения не имела. Сам Шура говорит, что будет пока определять траекторию движения спутников, просто подождав, пока они сделают один оборот и проинтерполировав полученные точки.
Другой Шура, Голубев, продолжает улучшать свой визуализатор.
После обеда Шура Киреев приносит радостные новости: он отладил стыковку на произвольной эллиптической орбите и одно за другим решил задания третей задачи. Мы поднимаемся в турнирной таблице и попадаем во второй десяток. Я говорю Шуре вставить тот же автопилот в четвёртую задачу и сбить хотя бы по одному спутнику в каждом задании. Шура говорит, что уже этим занят. :)
Я заканчиваю свой вычислитель эллиптических орбит и начинаю его тестировать на второй задаче (круговых орбитах). Вычисленная орбита действительно близка к круговой (эксцентриситет очень мал), объект движется по правильному радиусу с правильной скоростью, но очень сильно сдвинут по фазе. Через полчаса нахожу, в чём дело - результат выдаётся в системе координат, связанной с эллипсом, надо преобразовать его в глобальную систему координат.
В это время Шура Киреев получает первые результаты и отправляет их на сайт. Мы быстро поднимаемся, и, наконец, мы в десятке! Шура продолжает улучшать свой алгоритм, и вот мы уже на 7 месте. Тут организаторы что-то меняют и пересчитывают баллы за 4-ю задачу: лидеры вдруг сильно теряют очки, и мы уже на втором месте! Оказалось это ещё не всё: Шура отправляет очередное решение, и мы, обогнав лидера на сотые доли балла, оказываемся на 1 месте. Потом нас обгоняют. Потом опять мы в топе.
23:30 Опустились на 3-е место. Наконец мы с Шурой Киреевым решаем идти спать (Шура Голубев уехал ещё раньше). Идём пешком до Ботанического Сада, обсуждая стратегию на завтра.
2009-06-29
Начинаю писать код для поиска оптимального манёвра для перехода с орбиты на орбиту. Для этого нужен алгоритм поиска локальных экстремумов. Собираюсь использовать метод Нелдера - Мида. Нашёл его готовую реализацию на Java, очень обрадовался. Написал функцию - критерий оптимальности перехода с орбиты на орбиту за 3 импульса. После доводки получил какой-то результат, но проверить не успел.
Прибежал Шура:
- Вовчик, ты видел плакат "Посмотри, какую х$%ню ты написал"? Это про тебя! Я же просил протестировать эллиптические орбиты!
Не работает мой расчёт координат при движении по эллиптической орбите. Причём на круговых - работает, а на эллиптических - лажа: спутник сначала движется по орбите, похожей на правильную, но где-то на 20% ближе к Земле, чем надо, а потом вообще начинает лететь в противоположном направлении.
Начал разбираться с размером эллипса: длинна большой полуоси явно вычисляется неверно. Формулы вроде бы правильные. Вычислил по-другому, через энергию орбиты. Получилось правильное число. Но проблема с внезапным разворотом и полётом в обратном направлении никуда не делась. Копаю, закапываюсь в недра алгоритма численного решения уравнения Кеплера.
16:10 Наконец-то понимаю, в чём дело, и исправляю. Шура говорит, что теперь вычисление координат работает правильно, а я возвращаюсь к разработке оптимизатора.
17:20 Шура просит написать функцию вычисления времени подлёта к заданной точке при известных параметрах орбиты. Это просто - добавляю такую функцию.
До зачётного времени остаётся пара часов. Бросаю разработку оптимизатора перехода с орбиты на орбиту и берусь за более простую разработку - автомата самонаведения на цель. Идея - численными методами найти оптимальный корректирующий импульс, чтобы в результате оба спутника оказались в одной точке с учётом дискретности времени.
До окончания конкурса остаётся меньше часа. Вставляю свой автомат самонаведения в написанный Шурой автопилот для 4-й задачи. Наведение работает отлично - на встречных курсах в 4-ом задании точность попадания - меньше метра. Прогоняю задания 4-й задачи, в 1, 3 и 4 задании результаты существенно улучшаются, особенно в 4-м (встречные курсы). Во 2-м задании (вытянутые эллиптические орбиты) всё плохо - постоянно врезаемся в землю.
20:30 Мы с Шурой пытаемся устранить столкновения с Землёй во 2-м задании, но успеха наши попытки не приносят. Кроме того, иногда автомат наведения всё-таки промазывает, и автопилот тогда подвисает в состоянии "наведение". Позже выяснилось, что я, когда вставлял свой автомат наведения, поломал проверку на промах, которая была у Шуры, и переход автопилота в состояние поиска.
21:00:16 Финальный свисток. У нас 3800 с небольшим баллов. Таблица с результатами была заморожена за четыре часа до этого, но всё равно понятно, что до призовых мест нам далеко. Интересно, попали ли мы хотя бы в десятку? Результаты будут объявлены на конференции ICFP в конце августа - начале сентября.
Выводы
Выбором Scala в качестве языка разработки мы остались довольны. Теперь что-то писать на Java совершенно не хочется.
Времени было сравнительно много в начале, но его как всегда чуть-чуть не хватило в конце. :)