![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
dastapovЭто окончание рассказа. Линки на начало и середину.
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
* Использовали автоматическое дифференцирование значений и выражений, взятое отсюда.
* Научились определять физические параметры мира без выполнения специальных "калибровочных движений" марсоходом (типа, разогнался, чуть проехал, затормозил, сделал левый поворот).
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
* Использовали автоматическое дифференцирование значений и выражений, взятое отсюда.
* Научились определять физические параметры мира без выполнения специальных "калибровочных движений" марсоходом (типа, разогнался, чуть проехал, затормозил, сделал левый поворот).
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
(no subject)
Date: 2008-07-21 03:39 am (UTC)оптимизация
Date: 2008-07-21 04:07 am (UTC)А вот интересно, можно ли придумать алгоритм, который на множестве "приемлемых" траекторий выберет наиболее оптимальную по какому-то заранее заданному условию - например сумма расстояний до всех марсиан, или скорость движения...
А глобально оптимизированный алгоритм - это гарантия победы или разделённого первого места :)
(no subject)
Date: 2008-07-21 05:31 am (UTC)Еще раз хочу сказать спасибо за чудесно проведенные дни :).
(no subject)
Date: 2008-07-21 06:37 am (UTC)(no subject)
Date: 2008-07-21 06:53 am (UTC)А есть ли необходимость в глобальной навигации здесь -- для меня осталось большим вопросом. Ведь карты то мы не знаем, т.е. применить навигацию можно будет в лучшем случае на 4-5 ране. Т.е. оно, конечно, хорошо, но, скорее, как бонус, как по мне.
А еще, странно, что у вас так много времени пошло на парсер. У меня (на Lisp'е) на это ушел от силы час времени.
P.S. Мои мысли по этому поводу участия: http://lisp-univ-etc.blogspot.com/2008/07/icfp-08_16.html
(no subject)
Date: 2008-07-21 07:09 am (UTC)И еще раз хочу подчеркнуть злую иронию того, что мое участие в соревновании по ФП предотвратило оное ФП...
(no subject)
Date: 2008-07-21 08:11 am (UTC)(no subject)
Date: 2008-07-21 10:16 am (UTC)(no subject)
Date: 2008-07-21 10:43 am (UTC)Я вот тоже думал об управлении на основе "поля потенциалов". Почему оно является локальным, а не глобальным? По построению, т.е. вы так запрограммировали, или для глобального оно не подходит? Я что-то вообще границу между локальным и глобальным плохо понимаю, по крайней мере, в контексте данной задачи.
(no subject)
Date: 2008-07-21 10:51 am (UTC)(no subject)
Date: 2008-07-21 01:07 pm (UTC)(no subject)
Date: 2008-07-21 01:17 pm (UTC)(Я не рассматриваю тут граничного случая, который организаторы, конечно, вполне могут предусмотреть, когда в поле зрения попадает вся карта. Хотя вряд ли они на это пойдут: слишком длинная будет строка телеметрии, мне кажется)
(no subject)
Date: 2008-07-21 01:21 pm (UTC)(no subject)
Date: 2008-07-21 01:24 pm (UTC)(no subject)
Date: 2008-07-21 01:31 pm (UTC)(no subject)
Date: 2008-07-21 01:34 pm (UTC)(no subject)
Date: 2008-07-21 01:43 pm (UTC)[ровер -] ----- [кратер -] ---------- [база +]
?
не говоря уже о лабиринтах.
(no subject)
Date: 2008-07-21 01:50 pm (UTC)Нет, бывают ситуации и посложнее, но, как я писал по соседству, у меня есть пара идей, что с ними делать. Надо пробовать, а потом уже говорить.
(no subject)
Date: 2008-07-21 01:55 pm (UTC)(no subject)
Date: 2008-07-21 02:05 pm (UTC)Почему-то Вы видите только проблемы, хотя их решения очевидны.
(no subject)
Date: 2008-07-21 02:11 pm (UTC)(no subject)
Date: 2008-07-21 02:13 pm (UTC)(no subject)
Date: 2008-07-21 02:18 pm (UTC)интересный получился разговор
Date: 2008-07-21 02:18 pm (UTC)Re: интересный получился разговор
Date: 2008-07-21 02:21 pm (UTC)А вот почему же алгоритм локальный я так и не понял. :( Можете пояснить подробнее?