dastapov: (Default)
[personal profile] 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
* Использовали автоматическое дифференцирование значений и выражений, взятое отсюда.
* Научились определять физические параметры мира без выполнения специальных "калибровочных движений" марсоходом (типа, разогнался, чуть проехал, затормозил, сделал левый поворот).

(no subject)

Date: 2008-07-21 03:39 am (UTC)
From: [identity profile] nzeemin.livejournal.com
Было бы супер если бы вы тоже сделали видео вашего ровера в деле...

оптимизация

Date: 2008-07-21 04:07 am (UTC)
From: [identity profile] dnk-rnk.livejournal.com
Интересный репортаж, спасибо!

А вот интересно, можно ли придумать алгоритм, который на множестве "приемлемых" траекторий выберет наиболее оптимальную по какому-то заранее заданному условию - например сумма расстояний до всех марсиан, или скорость движения...
А глобально оптимизированный алгоритм - это гарантия победы или разделённого первого места :)

(no subject)

Date: 2008-07-21 05:31 am (UTC)
From: [identity profile] dtim.livejournal.com
Замечательный отчет!
Еще раз хочу сказать спасибо за чудесно проведенные дни :).

(no subject)

Date: 2008-07-21 06:37 am (UTC)
From: [identity profile] timyrlan.livejournal.com
Здорово!

(no subject)

Date: 2008-07-21 06:53 am (UTC)
From: [identity profile] pufpuf.livejournal.com
Интересно, что у нас на выходе вышло примерно то же самое :) (за исключением рассчета физических параметров, которые у нас никто так и не сделал, хотя я предлагал...)

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

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

P.S. Мои мысли по этому поводу участия: http://lisp-univ-etc.blogspot.com/2008/07/icfp-08_16.html

(no subject)

Date: 2008-07-21 08:11 am (UTC)
From: [identity profile] yvl.livejournal.com
ну, это пока не пришли умные марисиане глобальная навигация не нужна... Хотя прочитав про количество багов в спеках, я сомневаюсь в умных марсианах...

(no subject)

Date: 2008-07-21 01:17 pm (UTC)
From: [identity profile] pufpuf.livejournal.com
Боюсь, что не помогла бы глобальная навигация справиться с умными марсианами. поскольку мы их, как правило, не видим. А от тех, кого видим нужно сматываться локально, так ведь?

(Я не рассматриваю тут граничного случая, который организаторы, конечно, вполне могут предусмотреть, когда в поле зрения попадает вся карта. Хотя вряд ли они на это пойдут: слишком длинная будет строка телеметрии, мне кажется)

(no subject)

From: [identity profile] yvl.livejournal.com - Date: 2008-07-21 04:57 pm (UTC) - Expand

(no subject)

Date: 2008-07-21 07:09 am (UTC)
From: [identity profile] yvl.livejournal.com
Вот надо было оптимальный контроллер что я "описал" до ума довести, тогда б он крутился как здрасте... А вообще, конечно, за то, что у меня не было времени поучаствовать кто-то должен ответить. Наверное, это будут мои студенты.

И еще раз хочу подчеркнуть злую иронию того, что мое участие в соревновании по ФП предотвратило оное ФП...

(no subject)

Date: 2008-07-21 10:16 am (UTC)
From: [identity profile] dimchansky.livejournal.com
Не могли бы описать здесь оптимальный контроллер или хотя бы ссылкой ответить? Очень интересно.

(no subject)

Date: 2008-07-21 05:04 pm (UTC)
From: [identity profile] yvl.livejournal.com
я его описал только для поворотов - там bang-bang, который решает простую задачу по равноускоренному движению, то есть мы хотим с данного угла и данной моментальной угловой) за кратчайшее время оказаться в другом угле (углу?) и нулевой угловой... Я может позже совсем полный нарешаю, который по waypoints будет ехать за кратчайшее время...

(no subject)

From: [identity profile] dimchansky.livejournal.com - Date: 2008-07-21 05:25 pm (UTC) - Expand
(deleted comment)

(no subject)

Date: 2008-07-21 03:28 pm (UTC)
From: (Anonymous)
Мой марсоход успешно собирал по ходу дела. Я был бы удивлен, если бы кто-то серьезно тратил время на специальные движения для сбора параметров..
Dee Mon.

(no subject)

From: [identity profile] gabriel-irk.livejournal.com - Date: 2008-07-21 03:48 pm (UTC) - Expand

(no subject)

From: (Anonymous) - Date: 2008-07-21 04:25 pm (UTC) - Expand

(no subject)

Date: 2008-07-27 12:30 pm (UTC)
From: [identity profile] nealar.livejournal.com
Да, по ходу дела. Но специальные движения всё равно были нужны - без них достоверность данных наступала слишком поздно. Например, первые данные об эффективности тормозов появляются, когда водила первый раз нажмёт на тормоз.

(no subject)

Date: 2008-07-21 10:43 am (UTC)
From: [identity profile] gabriel-irk.livejournal.com
Отличный отчёт! Даже за $50 вряд ли получилось бы лучше. ;)))

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

(no subject)

Date: 2008-07-21 10:51 am (UTC)
From: [identity profile] palm-mute.livejournal.com
в поле потенциалов могут быть потенциальные ямы, в которых роверу будет настолько комфортно, что он никуда больше не захочет ехать. невозможно придумать такую функцию, которая бы позволяла роверу искать путь в лабиринте (доказательства, правда, у меня нет).

(no subject)

From: [identity profile] lomeo.livejournal.com - Date: 2008-07-21 01:07 pm (UTC) - Expand

(no subject)

From: [identity profile] gabriel-irk.livejournal.com - Date: 2008-07-21 01:21 pm (UTC) - Expand

(no subject)

From: [identity profile] gabriel-irk.livejournal.com - Date: 2008-07-21 01:24 pm (UTC) - Expand

(no subject)

From: [identity profile] palm-mute.livejournal.com - Date: 2008-07-21 01:31 pm (UTC) - Expand

(no subject)

From: [identity profile] gabriel-irk.livejournal.com - Date: 2008-07-21 01:34 pm (UTC) - Expand

(no subject)

From: [identity profile] palm-mute.livejournal.com - Date: 2008-07-21 01:43 pm (UTC) - Expand

(no subject)

From: [identity profile] gabriel-irk.livejournal.com - Date: 2008-07-21 01:50 pm (UTC) - Expand

(no subject)

From: [identity profile] palm-mute.livejournal.com - Date: 2008-07-21 01:55 pm (UTC) - Expand

(no subject)

From: [identity profile] gabriel-irk.livejournal.com - Date: 2008-07-21 02:05 pm (UTC) - Expand

(no subject)

From: [identity profile] palm-mute.livejournal.com - Date: 2008-07-21 02:46 pm (UTC) - Expand

(no subject)

From: [identity profile] gabriel-irk.livejournal.com - Date: 2008-07-21 03:00 pm (UTC) - Expand

Time Keeps on Slippin'

From: [identity profile] dimiii.livejournal.com - Date: 2008-07-22 06:35 am (UTC) - Expand

Re: Time Keeps on Slippin'

From: [identity profile] gabriel-irk.livejournal.com - Date: 2008-07-22 02:06 pm (UTC) - Expand

Re: Time Keeps on Slippin'

From: [identity profile] dimiii.livejournal.com - Date: 2008-07-22 03:16 pm (UTC) - Expand

(no subject)

From: [identity profile] nealar.livejournal.com - Date: 2008-07-27 12:34 pm (UTC) - Expand

(no subject)

From: [identity profile] gabriel-irk.livejournal.com - Date: 2008-07-28 08:32 am (UTC) - Expand

(no subject)

From: [identity profile] nealar.livejournal.com - Date: 2008-07-29 07:17 am (UTC) - Expand

(no subject)

From: [identity profile] gabriel-irk.livejournal.com - Date: 2008-07-29 08:44 am (UTC) - Expand

(no subject)

From: [identity profile] nealar.livejournal.com - Date: 2008-07-29 09:48 am (UTC) - Expand

(no subject)

From: [identity profile] gabriel-irk.livejournal.com - Date: 2008-07-29 08:47 am (UTC) - Expand

(no subject)

From: [identity profile] ark-kun - Date: 2013-07-30 07:40 pm (UTC) - Expand

(no subject)

From: [identity profile] gabriel-irk.livejournal.com - Date: 2013-08-03 02:12 pm (UTC) - Expand

(no subject)

From: [identity profile] ark-kun - Date: 2014-02-16 08:47 pm (UTC) - Expand

(no subject)

From: [identity profile] ark-kun - Date: 2014-02-16 08:48 pm (UTC) - Expand

(no subject)

From: [identity profile] ark-kun - Date: 2014-02-16 08:48 pm (UTC) - Expand

(no subject)

From: [identity profile] ark-kun - Date: 2014-02-16 08:49 pm (UTC) - Expand

(no subject)

From: [identity profile] uptheirons.livejournal.com - Date: 2008-07-21 02:11 pm (UTC) - Expand

(no subject)

From: [identity profile] uptheirons.livejournal.com - Date: 2008-07-21 02:13 pm (UTC) - Expand

(no subject)

From: [identity profile] gabriel-irk.livejournal.com - Date: 2008-07-21 02:18 pm (UTC) - Expand

(no subject)

From: [identity profile] uptheirons.livejournal.com - Date: 2008-07-21 02:28 pm (UTC) - Expand

(no subject)

From: (Anonymous) - Date: 2008-07-21 03:30 pm (UTC) - Expand

http://www.thedeemon.com/icfpc08/

Date: 2008-07-21 03:26 pm (UTC)
From: (Anonymous)
Про поле потенциалов навроде закона Кулона:
1. Почему не годится как глобальное решение: представьте карту, где ровер отделен от базы длинной сплошной стеной. У поля будет отличненький локальный минимум у той части стены, что ближе всего к базе, объезжать стену ровер не поедет. Собственно, уральцы (hackerdom.ru) выкладывали хорошую карту - dijksta-rulez.wrld, помедитируйте над ней.

2. Попробуйте в любом удобном инструменте построить потенциальное поле для карты с большим числом объектов (типа small08, хотя small-scatter тоже годится). Локальных минимумов там будет выше крыши.

3. Если считать поле как обычно - сумму всех сил, то при неравномерном распределении объектов глобальный минимум смещается от базы в сторону. Еще раз рекомендую построить и убедиться.

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

(no subject)

Date: 2008-07-21 03:25 pm (UTC)
From: (Anonymous)
Вы написали про представление вектора комплексными числами, а чем такое представление лучше стандартного?

(no subject)

Date: 2008-07-21 08:24 pm (UTC)
From: [identity profile] palm-mute.livejournal.com
не то чтобы лучше. дело было вечером, думать было нечем, и я умудрился наделать багов в сложении арктангенса с константой :). этих багов можно было бы избежать, если бы с самого начала воспользовались библиотечными функциями преобразования между полярным и декартовым представлением комплексных чисел.

(no subject)

Date: 2008-07-21 05:05 pm (UTC)
From: [identity profile] alogic.livejournal.com
Увлекательно. И про управление роботами я узнал больше, чем до этого.

(no subject)

Date: 2008-07-22 04:23 pm (UTC)

(no subject)

Date: 2008-07-23 11:21 am (UTC)
From: [identity profile] lionet.livejournal.com
Я в течении дня, похоже, пил слишком много чаю, и к вечеру нажил себе дичайшую головную боль, которая и отправила меня в постель сразу после последнего совещания, в 22:30.

http://www.medportal.ru/mednovosti/news/2008/07/22/water/

(no subject)

Date: 2008-07-27 12:46 pm (UTC)
From: [identity profile] nealar.livejournal.com
Всё было немного хуже. Когда модуль физики появился в репозитории, он тупо вешался при попытке включить измерения. Мы вдвоём с lomeo так и не сумели понять, в чём глюк, и стали интегрировать физику в контроллер. И только твой ход с переносом физических параметров в мир окончательно разрулил ситуацию.
Правда, была потеряна куча времени - я одновременно переколбашивал физику под новое API и ловил баги в самой физике.

(no subject)

Date: 2008-07-28 09:38 pm (UTC)
From: (Anonymous)
http://www.youtube.com/watch?v=M4TVNKTIUs4
Наш марсоходег на Ruby

(no subject)

Date: 2008-08-17 11:05 pm (UTC)
From: [identity profile] sh0ckfile.livejournal.com
сырцы бы поглядеть крайне интересно было.... :Ь

(no subject)

From: [identity profile] http://users.livejournal.com/_adept_/ - Date: 2008-08-18 11:42 am (UTC) - Expand

Спасибо

Date: 2008-08-05 07:01 am (UTC)
From: [identity profile] pipll.livejournal.com
Как всегда здорово!

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