dastapov: (Default)
[personal profile] dastapov
Это вторая часть рассказа. Линк на начало.

12 Jul 2008.

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

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

Линк на продолжение.
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