?

Log in

No account? Create an account
dump -0f - /dev/mind
Я знаю Haskell, OCaml, GSM, эндофункторы и много других страшных слов
In Soviet Union, the rover moons you! -- отчет о ICFPC'08, часть 3 
21st-Jul-2008 12:30 am
Это окончание рассказа. Линки на начало и середину.

13 Jul 2008. Начало второго полного дня соревнований. До финиша - где-то 35 часов.

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

На утреннем совещании я вывалил на коллег всю информацию, извлеченную из статей по навигации для роботов и мы обсудили методы глобальной навигации, остановившись на "карте в клеточку" (получаемой методом subcell decomposition) и поиску кратчайшего пути на ней модификацией простейшего волнового алгоритма. Мы наметили себе такие цели: добавить чуть интеллекта в локальное управление, чтобы научиться объезжать близлежащие кратеры и марсиан, делать глобальную навигацию, делать модуль, который по наблюдениям за телеметрией и положением руля и педалей вычисляет параметры физической модели мира - те самые неизвестные нам ускорения разгона и торможения, коэффициент трения и ускорения поворота.

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

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

Незаметно наступило 15:00. Существенного прорыва не произошло. Модуль анализа статистики и расчета физ параметров уже был в репозитории, но еще ничего толком не считал. Марсоход по-прежнему ездил по синусоиде, в глобальном управлении у нас были только самые зачатки, зато количество вариантов локальных контроллеров возросло до шести (или семи?). В них были какие-то баги, но они сложно поддавались отладке, т.к. сложно было увязать отладочный вывод с тем, что было видно на экране в процессе работы сервера. Хоть явно об этом никто не говорил, но общий настрой плавно катился к минорному.

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

C GUI работа пошла активнее. К 19:00 у нас уже был марсоход, который умел отворачивать влево для объезда встречающихся по курсу препятствий, еще одна, более успешная, версия контроллера на базе "поля потенциалов", и куча идей по поводу того, что делать дальше.

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

Я в течении дня, похоже, пил слишком много чаю, и к вечеру нажил себе дичайшую головную боль, которая и отправила меня в постель сразу после последнего совещания, в 22:30.

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

День получился какой-то скомканый и без серьезных прорывов. Ближе к финалу (который по Киевскому времени должен был быть в 22:00) вся команда снова собралась в онлайне. Мы еще даже успели сделать и как-то проверить целую серию мелких правок к самому удачному контроллеру, написать скрипт, который собирает релиз нашего кода в виде, пригодном для отправки организаторам, скрестить два самых удачных контроллера и погонять наш марсоход на нескольких хитроумных картах, нарисованных другими участниками соревнования.

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

Сухой остаток
Итого, к финалу мы подошли с такими результатами: наш марсоход умел ехать на базу, управляемый комбинацией из P-контроллера угла направления, стратегии "объезжай препятствия справа или слева - как короче" и стратегии удирания от марсиан (которая включалась, если кол-во марсиан в окрестностях марсохода превышала некий порог). Марсоход пытался регулировать свою скорость так, чтобы не сильно часто биться о камни и падать в кратеры, и иногда это у него даже получалось. Глобальную навигацию мы так и не сделали.

По сравнению с результатами других команд (например, вот видео от team ryba, четвертое место на прошлогоднем ICFPC) я бы оценил наши шансы примерно как шансы никарагуанской команды бобслеистов на зимней Олимпиаде. За счет упорных тренировок и доли везения мы, скорее всего, выйдем из своей подгруппы, но шансы увидеть нас в финале исчезающе малы.

Извлеченные уроки номер два, три и так далее
* Дедушка Ленин завещал учиться, учиться и еще раз учиться, но забыл сказать, что делать это надо до или после контеста. Мне не стоило лезть в дебри оптимального управления, а надо было заниматься глобальной навигацией, сделать которую быстро у меня были все шансы.
* Мы слишком поздно сообразили использовать комплексные числа для представления векторов. Позор на наши седины :(
* Общение на русском - круче, чем общение на английском
* Чем дальше в лес - тем медленнее надо кодить, тем чаще собираться и тем больше разговаривать. У нас в этом году получилось почти наоборот.
* К финальному билду надо начинать готовиться еще в первый день, чтобы не получилось так, что проект не успел собраться за последнюю минуту перед финишем.
* Нужен центральный документ по архитектуре решения и основным дизайнерским решениям, т.к. не все одинаково быстро успевают следить за чатом/почтой/коммитами.

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

Спасибо за внимание, и еще раз спасибо участникам нашей команды!

Отдельное громадное спасибо моей замечательной супруге, благодаря которой я был накормлен, напоен, выслушан и неотвлекаем на протяжении всего соревнования. Иначе, как подвигом, это не назовешь.

PS
Ах да! Сам себя не похвалИшь - как оплеванный сидишь... Дальше может быть интересно только тем, кому такое интересно :)

Технические детали решения
* Язык - Haskell, несколько скриптов на shell и perl
* 27 модулей (3 - чужих), 1800 строк кода.
* 298 коммитов в репозитории
* Свой GUI на gtk2hs
* Использовали автоматическое дифференцирование значений и выражений, взятое отсюда.
* Научились определять физические параметры мира без выполнения специальных "калибровочных движений" марсоходом (типа, разогнался, чуть проехал, затормозил, сделал левый поворот).
Comments 
21st-Jul-2008 03:39 am (UTC)
Было бы супер если бы вы тоже сделали видео вашего ровера в деле...
21st-Jul-2008 04:07 am (UTC) - оптимизация
Интересный репортаж, спасибо!

А вот интересно, можно ли придумать алгоритм, который на множестве "приемлемых" траекторий выберет наиболее оптимальную по какому-то заранее заданному условию - например сумма расстояний до всех марсиан, или скорость движения...
А глобально оптимизированный алгоритм - это гарантия победы или разделённого первого места :)
21st-Jul-2008 05:31 am (UTC)
Замечательный отчет!
Еще раз хочу сказать спасибо за чудесно проведенные дни :).
21st-Jul-2008 06:37 am (UTC)
Здорово!
21st-Jul-2008 06:53 am (UTC)
Интересно, что у нас на выходе вышло примерно то же самое :) (за исключением рассчета физических параметров, которые у нас никто так и не сделал, хотя я предлагал...)

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

А еще, странно, что у вас так много времени пошло на парсер. У меня (на Lisp'е) на это ушел от силы час времени.

P.S. Мои мысли по этому поводу участия: http://lisp-univ-etc.blogspot.com/2008/07/icfp-08_16.html
21st-Jul-2008 08:11 am (UTC)
ну, это пока не пришли умные марисиане глобальная навигация не нужна... Хотя прочитав про количество багов в спеках, я сомневаюсь в умных марсианах...
21st-Jul-2008 07:09 am (UTC)
Вот надо было оптимальный контроллер что я "описал" до ума довести, тогда б он крутился как здрасте... А вообще, конечно, за то, что у меня не было времени поучаствовать кто-то должен ответить. Наверное, это будут мои студенты.

И еще раз хочу подчеркнуть злую иронию того, что мое участие в соревновании по ФП предотвратило оное ФП...
21st-Jul-2008 10:16 am (UTC)
Не могли бы описать здесь оптимальный контроллер или хотя бы ссылкой ответить? Очень интересно.
(Deleted comment)
21st-Jul-2008 03:28 pm (UTC)
Anonymous
Мой марсоход успешно собирал по ходу дела. Я был бы удивлен, если бы кто-то серьезно тратил время на специальные движения для сбора параметров..
Dee Mon.
(no subject) - Anonymous - Expand
21st-Jul-2008 10:43 am (UTC)
Отличный отчёт! Даже за $50 вряд ли получилось бы лучше. ;)))

Я вот тоже думал об управлении на основе "поля потенциалов". Почему оно является локальным, а не глобальным? По построению, т.е. вы так запрограммировали, или для глобального оно не подходит? Я что-то вообще границу между локальным и глобальным плохо понимаю, по крайней мере, в контексте данной задачи.
21st-Jul-2008 10:51 am (UTC)
в поле потенциалов могут быть потенциальные ямы, в которых роверу будет настолько комфортно, что он никуда больше не захочет ехать. невозможно придумать такую функцию, которая бы позволяла роверу искать путь в лабиринте (доказательства, правда, у меня нет).
(no subject) - Anonymous - Expand
21st-Jul-2008 03:25 pm (UTC)
Anonymous
Вы написали про представление вектора комплексными числами, а чем такое представление лучше стандартного?
21st-Jul-2008 08:24 pm (UTC)
не то чтобы лучше. дело было вечером, думать было нечем, и я умудрился наделать багов в сложении арктангенса с константой :). этих багов можно было бы избежать, если бы с самого начала воспользовались библиотечными функциями преобразования между полярным и декартовым представлением комплексных чисел.
21st-Jul-2008 05:05 pm (UTC)
Увлекательно. И про управление роботами я узнал больше, чем до этого.
22nd-Jul-2008 04:23 pm (UTC)
23rd-Jul-2008 11:21 am (UTC)
Я в течении дня, похоже, пил слишком много чаю, и к вечеру нажил себе дичайшую головную боль, которая и отправила меня в постель сразу после последнего совещания, в 22:30.

http://www.medportal.ru/mednovosti/news/2008/07/22/water/
27th-Jul-2008 12:46 pm (UTC)
Всё было немного хуже. Когда модуль физики появился в репозитории, он тупо вешался при попытке включить измерения. Мы вдвоём с lomeo так и не сумели понять, в чём глюк, и стали интегрировать физику в контроллер. И только твой ход с переносом физических параметров в мир окончательно разрулил ситуацию.
Правда, была потеряна куча времени - я одновременно переколбашивал физику под новое API и ловил баги в самой физике.
28th-Jul-2008 09:38 pm (UTC)
Anonymous
http://www.youtube.com/watch?v=M4TVNKTIUs4
Наш марсоходег на Ruby
17th-Aug-2008 11:05 pm (UTC)
сырцы бы поглядеть крайне интересно было.... :Ь
5th-Aug-2008 07:01 am (UTC) - Спасибо
Как всегда здорово!
This page was loaded Sep 18th 2018, 4:15 pm GMT.