Начитавшись отчетов о предыдущих двух контестах (2006, 2007) ждал в этом году продолжения, но
А вот организация контеста сильно подкачала. LiveCD, необходимый для тестирования бота в среде близкой к системе организаторов (knoppix), был выложен всего за сутки до начала контеста. И содержал немалое количество багов. На LiveCD было несколько компиляторов, для сборки бота перед запуском и до последних минут контеста шло обсуждение проблем с невключенными в состав библиотеками компиляторов (в частности почти в самом самом конце обнаружилось, что работать с сетью орговский Haskell не может, библиотек нет).
С симулятором возникло не меньше проблем. Мало того, что были версии только под Linux и MacOS (т.е. пользователи Windows получили дополнительный геморрой), так он еще и не работал с многими видео-картами. Народ на официальном
По самому заданию
В любом случае, опыт получен интересный и соответствующие выводы сделаны. В следующий раз (если он будет) результат будет куда более серьезным, т. к. даже ругая организаторов, стоит признать что и в постановке работы внутри нашей команды были организационные проблемы. Тот результат, который мы получили в понедельник к вечеру, мы могли бы иметь уже в воскресенье утром, ну и соответственно потратили бы оставшееся время на более точное управление ботом, более умный поиск пути и многое другое,
Результаты организаторы обещают объявить в сентябре. Вот даже за это их стоит посадить на кол и сжечь на костре, невозможно ж столько ждать :)
Июль 15th, 2008 at 10:26 пп #fedotawa
Прошу простить меня за занудство, но по-моему, здесь очень не хватает скепсису.
Цитата: “Тот результат, который мы получили в понедельник к вечеру, мы могли бы иметь уже в воскресенье утром, ну и соответственно потратили бы оставшееся время на более точное управление ботом, более умный поиск пути и многое другое, что-то бы в любом случае смогли бы улучшить.”
Давайте (конструктивно) попробуем понять, что избрав этот путь, принципиально ничего улучшить мы не смогли бы.
Вкратце, алгоритм продвижения к цели был выбран следующий:
1) Берем курс на HomeBase
2) На пути встретилось препятствие
3.1) Для объезда препятствия (если его можно объехать) нужно найти:
a) точку касания прямой проходящей через нас к окружности-препятствию
б) точку касания прямой, проведенной из центра homebase, и окружности препятствия
3.2) Подъезжаем к точке a)
3.3) Осуществляем поворот по криволинейной траектории к точке б)
3.4) Переход на 1)
4) Если препятствие объехать нельзя, применить алгоритм к препятствию, расположенному рядом.
Каждый пункт алгоритма имеет свои нюансы (некоторые пункты были реализованы автором настоящего комментария), которые здесь не описаны (к сожалению, они не были приняты во внимание автором алгоритма). Я не буду обсуждать детали чисто геометрического характера (мне удалось найти как минимум два случая, для которых необходимо применять специальное поведение), по причинам о которых скажу ниже. Рассмотрим нюансы из области механики (которые тоже не были учтены автором).
Следует сказать, что возможности управления марсоходом весьма скромны - доступно всего четыре команды: разгон, торможение, поворот вправо и влево. Можно заметить, что фактически, это команды доступные при управлении игрушечной машинкой с джойстика. И, на мой взгляд, основная проблема контеста состояла в выборе оптимального способа сопоставления физических параметров движущегося марсохода (скорость, направление движения) с временем воздействия на него этими командами (причем, этот способ должен хорошо сочетаться с выбранным алгоритмом поиска пути). Если эта проблема не решена, то говорить об алгоритме, использующем дискретные сегменты пути (алгоритм предложенный выше является именно таким) не имеет смысла.
Нюанс 1 - перемещение в заданную точку. Выбранным способом для совершения данного маневра был разворот и выход на линейную траекторию с установкой заданной скорости. Однако из-за необходимости разворачиваться (которая тоже имеет свои нюансы), актуальная длина пройденного пути не может быть вычислена точно, а следовательно и время, которое должен осуществляться этот маневр (перемещение в точку), из-за чего в место назначение можно попасть с весьма ощутимой погрешностью. Кроме того, из-за довольно большой дискретизации времени, траектория отличается от линейной (траектория представляет собой синусойду), в виду того, что между командами корректировки пути проходит довольно большой промежуток времени.
Нюанс 2 - выбор направления разворота. Целесообразно выбирать направление разворота при изменении курса, в зависимости от величины угла поворота и расстояния от находящихся рядом препятствий. Это не было учтено автором алгоритма.
Нюанс 3 - маневр по криволинейной траектории. Этот маневр необходимо осуществить при выполнении пункта 3.3. Для получения заданной кривизны траектории нужно вычислить центростремительное ускорение при повороте (это требует задания определенного значения линейной скорости в момент начала поворота). Кроме того, нужно вычислить длину сегмента дуги, по которой осуществляется поворот (задается временем поворота). Это не может быть рассчитано достаточно точно, по причинам, указанным выше, и не было учтено автором.
Естественно, данные нюансы не были реализованы так как задумано (теория управления марсоходом, к сожалению, так и не была разработана, чем, ради общего блага, вполне мог заняться автор алгоритма), и на мой взгляд, не могут быть реализованы при выбранном алгоритме поиска пути. Если автор считает иначе, я предлагаю ему реализовать их, используя свои любимые инструменты (автору известно ,что эмулятором можно управлять по сети, используя виртуальную машину). Автор настоящего комментария в свою очередь, будет пытаться реализовать алгоритм потенциальных полей.
На мой взгляд, лучшим решением был бы выбор алгоритма, не требующего точного задания дискретный участков пути, например, вычисление срединной траектории при езде по клеткам или определении углового расстояния между препятствиями (и фактического, так как известно расстояние до них, но здесь есть проблема проекции, и в последнем случае, хранения истории).
Проблемы геометрического характера автору предлагается обнаружить решить самостоятельно.
Июль 15th, 2008 at 10:35 пп #DeVoid
Очень интересно было почитать Вашу заметку. Надеюсь будете участвовать и пистать отчеты еще! Спасибо.
Июль 15th, 2008 at 10:49 пп #Roman Yankovsky
Вот те пункты, которые ты перечислил, должны были стать основной алгоритма, “болванкой”. Да, есть нюансы, но времени на них не хватило бы в любом случае, даже болванка была готова к вечеру понедельника. Если ты забыл, то формулы для контроля скорости и красивых поворотов проработал alius. Но мы забили, было уже некогда. Много на что забили.
Да, болванка не идеальна, но “бот, умеющий объехать препятствие” - это самый базис, подходящий под очень многое. И три члена команды из четырех в субботу вечером решили с этого начать. А ты до сих пор продолжаешь ебать мозг, ничего КОНКРЕТНОГО не предлагая взамен. Мы больше суток УГОВАРИВАЛИ тебя, Андрей, начать кодинг, ибо только ТЫ мог это делать не вслепую, а silver восстанавливал систему, моя система не тянула виртуальную убунту, а на alius’а мы изначально расчитывали только как на генератора идей.
Разрабатывай и исследуй у себя дома, что хочешь. А в узких временных рамках и в команде ты похоже работать не умеешь, а жаль. Все это не умаляет твоих заслуг, большая часть кода твоя лично. Но следовало начинать раньше, я об этом высказался, а ты решил перейти на личности.
Последующие твои посты буду удалять, уж извини. Если очень хочется, то в почту. Публичных разборок не люблю.
Июль 16th, 2008 at 12:56 дп #silver
Андрей, пойми - мы с трудом успели реализовать минимум. С ним мы и остались. Мне обидно и досадно за это.
Но продолжай мы дальше разговоры - не было бы совсем ничего.
Тебе, кстати, спасибо за все сделанное. Только благодаря тебе мы отослали хоть что то.
Август 1st, 2008 at 3:39 дп #dump -0f - /dev/mind - Вдогонку: около-ICFPC-шные ссылки (2008)
[...] ICFPC: http://sharpc.livejournal.com/28176.html. Еще одно подобное мнение: http://kerkzone.net/2008/07/15/icfp-2008/.* Отчет участника, написавшего решение на … TeX! [...]