Dmitry Astapov (_adept_) wrote,
Dmitry Astapov
_adept_

Categories:

In Soviet Union, the rover moons you! -- отчет о ICFPC'08, часть 2

Это вторая часть рассказа. Линк на начало.

12 Jul 2008.

Однако, я только и успел, что выписать определения сообщений, которые придется принимать от марсохода и передавать ему. Сразу после этого в jabber-е прорезался yvl, который двигает науку в области робототехники. Сам он по стечению обстоятельств в соревновании участия не принимал, но интересовался моим мнением о задаче.

У нас завязался увлекательный разговор, первые пятнадцать минут которого напоминали скорее монолог: yvl вещал, я записывал на листик неизвестные мне термины и понятия. В результате я вынес из нашего общения несколько ценных крупиц знаний:
1)Все могло бы быть и хуже - например, марсоход мог бы не знать своих собственных координат в текущий момент времени. Или иметь сенсоры, которые передают необработанную информацию о окружающем мире (вместо "вижу камень размера r в точке x,y" было бы "вижу что-то серое по азимуту A")
2)Впрочем, все могло бы быть и лучше - в частности, было бы удобно управлять скоростью марсохода, а не ускорением, т.к. с ускорением нам придется помучиться (пророческие слова!)
3)Сначала надо научиться рулить, т.к. без этого все остальное смысла не имеет. Для управления, скорее всего, физическая модель не нужна - достаточно следить за тем, куда мы едем после поворота руля или нажатия газа/тормоза, и вовремя переводить ручку в противоположное состояние.
4)Потом - научиться делать local navigation, объезжая ближайшие препятствия и убегая от ближайших врагов
5)На закуску надо сделать global navigation (pathfinding), которая будет строить маршрут по всей карте в целом, чтобы потом двигаться по этому маршруту с помощью локальной навигации.
Кинув в меня на прощание пачкой PDF-ов со статьями по методам навигации и прокладывания пути, yvl отправился нести свет знаний китайским канадским студентам.

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

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

Между первым и вторым - перерывчик в 9 часов

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

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

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

Наш марсоход пока еще даже не умел нормально общаться с сервером. Мы решили быстро устранить все недоделки, и через два часа, в 11:00, собраться еще раз для формулирования дальнейшего плана действий. Предположительно, к этому времени у нас уже должен был быть основной "костяк" кода, и у нас оставалось бы еще около 10-11 часов до завершения первых суток соревнования. За это время мы могли бы успеть реализовать какую-никакую стратегию доезжания до дома и поучаствовать в lightning round - отдельном чемпионате среди решений, сделанных за первые 24 часа.

Meeting 3, 11:50 12 Jul 2008

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

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

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

Баш на баш. 12:30 12 Jul 2008
После обеда я понял, что взял себе кусок работы, который сейчас нормально сделать не в состоянии. Я подрядился написать простой контроллер марсохода, который будет разворачивать его "к лесу задом", а к базе - передом, и давить на газ, не обращая внимания на препятствия. Но все прочитанные мной до сих пор статьи были гораздо более высокоуровневыми - они рассуждали о глобальной навигации по сложной карте, исходя из предположения, что мы умеем направить робота в определенную точку, и он туда приедет.

Тут я вспомнил, что прошлым вечером на первой общей встрече Глеб предлагал какие-то идеи по написанию контроллера и писал при этом умные формулы. Мы быстренько махнулись задачами: он взялся за контроллер, а я - за доведение до ума парсера.

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

Через 15 минут подобной работы я психанул и сел переписывать парсер на Parsec. На доведение до ума парсера и тестов к нему, прикручивание результата к остальному коду и доведения этой смеси до состояния "запускается, не падает, выдает какие-то результаты" у меня ушло два часа с перерывом на еще одно совещание. На часах было 15:00.

Отсюда можно вынести урок номер один: если кусок кода получился фиговым, незачем пытаться реанимировать труп и всеми силами вдохнуть в него жизнь. Такой код надо безжалостно выкидывать и переделывать заново - благодаря накопленным знания и уже известным проблемам переписывание занимает мало времени, а результат получается гораздо красивее и ... эээ ... manageable. Мы потратили на парсер в общей сложности где-то 10-18 человеко-часов. В прошлом году мы тщетно пытались вложить второе дыхание в криво задизайненый компилятор dna-to-rna и потеряли на этом сутки чистого времени и где-то 60 человеко-часов. Я надеюсь, что в следующем году мы либо еще больше уменьшим цифру потерь, либо постараемся вообще не попасть в эту засаду. Вторым возможным подходом является быстрое создание кривонаколенного как-то работающего прототипа часов за шесть, выкидывание его подчистую и рестарт разработки с нуля. Возможно, я идеалист, но для случая распределенной команды может быть лучше, чтобы такой прототип сделал каждый участник независимо друг от друга.

Дальше у нас, как мне кажется, наметился небольшой застой из-за скудности наших знаний и невозможности делать какие-то улучшения в коде мелкими инкрементами. Я в течении где-то трех часов (если судить по логам) занимался вообще не пойми чем - вычищал из кода какие-то старые/неиспользуемые куски (еще один довод в пользу прототипа), фиксил какие-то мелкие баги, сделал несколько хитрых карт для тестирования и т.п. В какой-то момент я опять пошел читать статьи про роботов.

Наконец, где-то в 19:00 у нас начался merge нескольких больших кусков кода, и ближе к 20:00 произошел очередной прорыв: наш марсоход умел нормально общаться с сервером, держать в голове информацию о карте и обновлять ее сведениями о всех увиденных объектах, и у нас даже был вожделенный простой контроллер, который направлял марсоход на базу и давил на газ. Даже более того - у нас было две разных версии подобного контроллера от двух разных авторов :)

До окончания lightning round-а оставалось два часа, но уже было видно, что ничего достойного мы на него выставить не можем. Сейчас, положа руку на сердце, я даже не могу вспомнить, послали ли мы какой-то вариант до истечения первых суток или нет.

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

В этот момент я образцово-показательно ступил, и вместо того, чтобы заниматься глобальной навигацией (это в чистом виде алгоритмы на графах и соседние с ними области, в которых я ориентируюсь достаточно свободно) я зачем-то стал разбираться, почему наш марсоход ездит по синусоиде :( Конечно, жажда знаний - это сильный стимул, но надо же уметь себя контролировать :) В результате за какой-то час я узнал по верхам о том, что такое PID-контроллер, Bang-bang контроллер, "дискретное управление", вспомнил какие-то куски курса почти десятилетней давности под названием "методы оптимального управления" и для проверки своих знаний написал свою реализацию PID-контроллера угла направления. (Вполне ожидаемо, что набранные впопыхах знания не включали в себя информацию о том, что PID-контроллер для нашей задачи подходит слабо, нужно что-то вроде bang-bang controller-а плюс четкое понимание законов движения марсохода).

Удивительно, но мой PID-контроллер работал! И даже вел марсоход на базу по прямой, которая в окошке с разрешением 800x800 выглядела почти прямой. И даже намертво выжатая в пол педаль газа не портила картину. Успех вскружил мне голову. Плевать, что это уже третья реализация примерно одних и тех же принципов, находящаяся в нашем репозитории (впрочем, тогда я об этом еще не знал). Будущее стало снова выглядеть радужным и простым. На часах было 23:00, пора было отдохнуть, и я отправился спать, полный радужных планов о том, как завтра мы научим марсоход ездить по лабиринтам.

Линк на продолжение.
Tags: icfpc
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 4 comments