Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 45
А вы не пробовали на большой глубине уменьшать точность симуляции переходом к 5 или даже 1 итреации физики на тик? Особенно если там UNKNOWN_TILE. Или, например, для соперников менее точно считать?
Про использование шин — очень элегантно. Круто.
Классная история, вы молодец. Скажите, много времени ушло на стратегию? Писали каждый день?
А будет ссылка на видео, где можно посмотреть, кто как себя вёл?
Как было в прошлом году с хоккеями, было интересно наблюдать, как ИИ играет — один ошибается, второй обыгрывает, а первый потом снова востанавливается и одерживает интеллектуальную победу :)
Как было в прошлом году с хоккеями, было интересно наблюдать, как ИИ играет — один ошибается, второй обыгрывает, а первый потом снова востанавливается и одерживает интеллектуальную победу :)
russianaicup.ru/profile/santa324 — тут записи игр
Написано интересно, не ожидал такого количества сложных моментов. Реквестирую игру, где игрок мог бы управлять машинкой, соревнуясь с машинками, управляемыми вашей стратегией, чтобы на собственной шкуре оценить, насколько силён ИИ.
В принципе, это можно сделать локально с помощью russianaicup.ru/p/localrunner и исходников любой стратегии
Выиграть ИИ вообще нереально. У меня стратегия была на 400+ месте, и я не мог с ней соревноваться. Если сравнивать себя с победителями — они и на круг могут успеть обогнать.
Как тут уже написали, можно скачать исходники, собрать и localrunner с нужными настройками, но, возможно, придётся потвикать стратегию для улучшения производительности, иначе вы играть не сможете из-за 10-30 фпс.
Нда, если в 2013 году можно было выкарабкаться на python, то дальше с каждым годом все хуже. Хорошо хоть в этом году numpy и scipy разрешили использовать, а то было совсем печально. Дерево вариентов я пробоввл сделать, но тупо не вписывался по времени. Только с одной итерацией на шаг и то еле-еле, а это оценка хороша только на 20-30 тиков как максимум. В следующем году надеюсь будут еще языки компилируемые добавлены. Rust например…
В этом году в финале 2 питониста, в сотне — четверо. По итогам заездов понятно, что выиграть питонячья стратегия не могла, но побороться за двадцатку — вполне.
Для компенсации такого неравенства можно попробовать разрешить присылать гибридные стратегии (т.е. питоновые исходники + C extension), в Джаве разрешить JNI. Только я сомневаюсь, что организаторы на это пойдут.
Для компенсации такого неравенства можно попробовать разрешить присылать гибридные стратегии (т.е. питоновые исходники + C extension), в Джаве разрешить JNI. Только я сомневаюсь, что организаторы на это пойдут.
Поздравляю с победой! Я считаю, что победу дал именно алгоритм поиска траекторий с помощью таких «деревьев». Я до такого не додумался :) Да и вообще думал, что это нереально считать «хорошие» траектории, особенно с точностью в 10 подтиков, на глубину 450 тиков.
А можно попросить снять видео с визуализацией того, как порождаются такие деревья в самом начале?
PS. Я могу вкратце описать тут в комментариях, как был устроен мой алгоритм. Надо?
А можно попросить снять видео с визуализацией того, как порождаются такие деревья в самом начале?
PS. Я могу вкратце описать тут в комментариях, как был устроен мой алгоритм. Надо?
Конечно, особенно учитывая его, повидимому, меньшую ресурсоемкость.
Спасибо. Сделал небольшое видео, извиняюсь за плохое качество, не было времени разбираться:
youtu.be/dJ37tF_QwYY
youtu.be/dJ37tF_QwYY
Очень круто. До сих пор не верю, что можно симулировать столько траекторий и укладываться во времени. Особенно с точностью 10 подтиков.
PS. Я могу вкратце описать тут в комментариях, как был устроен мой алгоритм. Надо?
Да, интересно
Конечно, надо! И остальные ТОПеры если напишут, будет здорово.
del
Писал комментарий, который вырос во что-то огромное и, в общем, решил всё-таки написать отдельную тему: habrahabr.ru/post/273745
Я тоже участвовал. Заслуженная победа, поздравляю!!!
Первый круг машины едут не пойми куда — оно и понятно, но почему на втором-то круге они опять делают какие-то петли и заезжают в те же тупики — правильный путь известен же!
Расчет оптимальной траектории — это же задача на теорию оптимального управления! Тут бы вам матан применить. Начать можно хотя бы с вариационного исчисления — его проще освоить, а потом перейти к принципу максимума Понтрягина. Придется, правда, решать краевые задачи на дифуры, что тоже вычислительно затратно, но зато имеется прочный математический фундамент. Может быть, удастся и сэкономить время расчета за счет упрощений или если удастся получить аналитическое решение для участков траекторий.
Да, это именно то, что очень хочется применить! :)
К сожалению, «идеально» решить систему не хватает времени. На весь конкурс отведено полтора месяца, при этом не все узнают о начале «до начала». А нужно много кодировать, тестировать и т.п.
При этом, я не уверен, что здесь вообще удастся аналитические решения найти, вся система очень дискретна, при этом есть много внешних факторов случайной или псевдослучайной природы.
К сожалению, «идеально» решить систему не хватает времени. На весь конкурс отведено полтора месяца, при этом не все узнают о начале «до начала». А нужно много кодировать, тестировать и т.п.
При этом, я не уверен, что здесь вообще удастся аналитические решения найти, вся система очень дискретна, при этом есть много внешних факторов случайной или псевдослучайной природы.
ТОУ применима и к дискретным системам, просто непрерывный случай более лаконично описывается на языке математики, поэтому его легче понять. К тому же, при достаточной гладкости траекторий дикретные решения будут стремиться к непрерывным. Случайные погрешности также могут быть учтены при рассмотрении в рамках ТОУ, эти вещи в нее изначально закладывались, ведь теория разрабатывалась главным образом для расчета систем управления ракет.
Мне кажется, главный барьер здесь — понимание ТОУ, сложность математического аппарата. Я вон уже больше года ломаю голову над учебником, и до сих пор не достиг полного просветления.
Мне кажется, главный барьер здесь — понимание ТОУ, сложность математического аппарата. Я вон уже больше года ломаю голову над учебником, и до сих пор не достиг полного просветления.
Игровой «движок» дискретный, простая симуляция обычно работает гораздо быстрее чем аналитическое решение. Я пытался что-то подобное применить в первом соревновании (танках)- ничего хорошего не получилось.
И на трассе есть противники, которые активно противодействуют — это не очень вписывается в теорию оптимального управления.
И на трассе есть противники, которые активно противодействуют — это не очень вписывается в теорию оптимального управления.
простая симуляция обычно работает гораздо быстрее чем аналитическое решение
Простая симуляция по сути дела есть численное решение дифференциальных или разностных уравнений. В этой связи нет особой разницы, решаете ли вы уравнения движения системы, или уравнения ТОУ. Однако последние могут за меньшее число итераций привести вас к оптимальному решению.
И на трассе есть противники, которые активно противодействуют — это не очень вписывается в теорию оптимального управления.
Прекрасно вписываются, только это относится уже к углубленным разделам теории, которые сложнее понять и применить. Все эти задачи в свое время ставились и решались для военной техники, например, рассмотрения поединка самолета и противовоздушной ракеты. См. по ключевым словам "дифференциальные игры".
При свободно движущихся объектах, вроде ракеты и самолета, найти аналитическое решение ещё возможно. Но в данном соревновании действия происходят в узких коридорах. Столкновения с ограждениями, столкновения с шинами, столкновения машин между собой. Каким образом Вы будете писать для них уравнения движениями, тем более, решать их численно быстрее чем простой симуляцией?
Я не вижу способа применить аналитическое решение даже небольшого участка траектории. Как я уже писал, я пытался, в первом соревновании (танках). Я по образованию физик, и это было даже естественнее для меня. Но потом все пришлось выкинуть и переписать на симуляцию.
Не будьте голословны, приведите пример того, как это можно применить.
Я не вижу способа применить аналитическое решение даже небольшого участка траектории. Как я уже писал, я пытался, в первом соревновании (танках). Я по образованию физик, и это было даже естественнее для меня. Но потом все пришлось выкинуть и переписать на симуляцию.
Не будьте голословны, приведите пример того, как это можно применить.
Например, в танках я нашёл аналитическое решение уравнения движения танка. Пытался применить его для нахождения кратчайшего пути к бонусу, но учесть размеры и формы танка и бонуса (подобрать можно чиркнув углом) в уравнении движения практически невозможно. Я уже не говорю про столкновения. И даже если получится, уравнения будут столь сложными, что их численное решение будет намного медленнее симуляции с обработкой столкновений. А ещё точность будет хуже, так как «движок» дискретный.
Каким образом Вы будете писать для них уравнения движениями, тем более, решать их численно быстрее чем простой симуляцией?
Начнем с того, что «простая симуляция» есть численное решение системы разностных уравнений, которые в случае дискретной системы являются «истинными» уравнениями движения, а в случае непрерывной системы — приближением к «истинным» дифурам, которые описывают систему.
Нужно ли решать эти уравнения аналитически? Все зависит от рассматриваемой задачи. Например, когда имеют место столкновения, то можно рассматривать аналитические решения от столкновения к столкновению, если их удастся найти. Иногда бывает, что хоть аналитическое решение найти не удается, но можно применить другой (не «в лоб», как при простой симуляции) численный метод их решения. Так, если уравнения линейные — то большой прирост скорости дают методы, основанные на преобразовании Фурье.
Но я вел речь не о решении уравнений движения. Понятно, что так или иначе их решить можно (хотя бы численно). Но вот, если перед вами стоит следующая задача:
1) Заданы уравнения движения («простой симуляции») вида x(t) = f(x(t-1), u(t-1), t), где x — вектор переменных состояния системы в зависимости от времени, u — вектор управляющих воздействий, f — векторная функция. Например, x — это могут быть координаты и скорости машины, u — вектор, в который входит положение руля, педалей газа и тормоза и т.д.
2) Требуется найти векторную функцию u(t), такую, чтобы x(t0) = x0, x(t1)=t1 (т.е. чтобы автомобиль в начальный и конечный момент времени имел заданные координаты и скорость)
3) Среди всех функций u(t), удовлетворяющих условию 2), требуется найти такую, чтобы функционал I(x(t), u(t), t)) принимал наименьшее значение. Это условие оптимальности решения — функционал является оценкой решения по выбранным вами критериям.
Эту задачу уже нельзя решить с помощью «простой симуляции». Вы можете симулировать систему множество раз, перебирая различные варианты для u(t), но если делать это вслепую — то понятное дело, что не всегда даже удастся так подобрать u(t), чтобы автомобиль приехал куда надо, не говоря уже об оптимальности решения — слишком велико пространство для перебора.
Рассмотренная задача — это задача на оптимальное программное управление, и в ТОУ разработан ряд методов для ее решения.
Если вам нужны более конкретные примеры — обратитесь, приведу парочку.
Вряд ли есть смысл искать оптимальное программное управление сразу для всей трассы, т.к. на ней появляются случайные бонусы, противники совершают непредсказуемые маневры и т.д. Но можно попытаться применить теорию для поиска оптимальных траекторий прохождения поворотов или взятия бонусов.
Наверно не зря это теория «оптимального» управления. Если вы решаете задачу управления роботом на конвейере на заводе — это одно. Ваши вычислительные ресурсы и время жестко не ограничены, можно попытаться найти оптимальное решение. Тут же за отведенные временные рамки (ограничение процессорного времени) найти оптимальное решение не представляется возможным. Нужно найти хотя бы просто хорошее решение. Преобразование Фурье и подобные вещи не такие уж легкие в этом плане.
По поводу того чтобы искать аналитическое решение от столкновения к столкновению: столкновения очень важная часть оценочной функции, на основании которой выбирается траектория. Если рассматривать участок траектории только между столкновениями — то практически не остается критериев по которым выбирать.
Основная проблема применимости этой математики в подобном соревновании — то что критерии оптимальности не известны. Единственный точно известный критерий — надо набрать больше всего очков в гонке. Какой функционал должен принимать максимальное значение не известно. И какой смысл искать абсолютный максимум некоторого выдуманного функционала — если вы даже не уверены он ли вам нужен?
Подход с перебором траекторий в этом плане очень удобен, можно менять критерии выбора очень легко, ничего не переделывая.
По поводу того чтобы искать аналитическое решение от столкновения к столкновению: столкновения очень важная часть оценочной функции, на основании которой выбирается траектория. Если рассматривать участок траектории только между столкновениями — то практически не остается критериев по которым выбирать.
Основная проблема применимости этой математики в подобном соревновании — то что критерии оптимальности не известны. Единственный точно известный критерий — надо набрать больше всего очков в гонке. Какой функционал должен принимать максимальное значение не известно. И какой смысл искать абсолютный максимум некоторого выдуманного функционала — если вы даже не уверены он ли вам нужен?
Подход с перебором траекторий в этом плане очень удобен, можно менять критерии выбора очень легко, ничего не переделывая.
Ваши вычислительные ресурсы и время жестко не ограничены, можно попытаться найти оптимальное решение
Цели любой теории решения каких-либо задач (в данном случае оптимального управления) состоят не только в поиске методов, которые вообще работают, но и в поиске методов, решающих задачу с минимальными затратами вычислительных и прочих ресурсов. В том числе приближенных методов, жертвующих точность в угоду скорости расчета.
В этом свете странно, что вы так упорно отвергаете ТОУ, так как именно она занимается решением тех задач, что пришлось решать вам. Быть может, вы даже изобрели новый приближенный метод поиска оптимального управления, который превосходит существующие в каких-то аспектах. Могли бы опубликоваться в научном журнале.
Преобразование Фурье и подобные вещи не такие уж легкие в этом плане.
Преобразование Фурье (за счет существования алгоритма БПФ) многократно облегчает (по вычислительным затратам) решение широкого круга задач. Я не уверен, что в вашем случае применимы какие-либо методы, основанные на БПФ, просто хочу обратить ваше внимание, что если при решении какой-то задачи можно использовать БПФ — то это обычно очень хороший знак.
Если рассматривать участок траектории только между столкновениями — то практически не остается критериев по которым выбирать.
Пример: я недавно считал интегралы от кусочно-полиномиальных функций (сплайнов). То, что удалось найти интеграл аналитически на промежутках между точками склейки, позволило не вычислять его численно на всем интервале интегрирования, а обрабатывать данные только в точках склейки.
Возможно, что подобным образом, если известно аналитическое решение вашей задачи между столкновениями, можно было бы оптимизировать (по вычислительным затратам) решение вашей задачи в целом. Из непрерывной ваша задача превратилась бы в «кусочную», что в расчеты входили бы только данные на концах промежутков времени, где известны аналитические решения.
Основная проблема применимости этой математики в подобном соревновании — то что критерии оптимальности не известны. Единственный точно известный критерий — надо набрать больше всего очков в гонке. Какой функционал должен принимать максимальное значение не известно.
Вам просто нужно выразить правила игры и начисления очков на языке математики. Как раз и получится функционал — зависимость числа очков от траектории (и от управляющих воздействий).
Я не отрицаю ТОУ. Просто утверждения вроде «начать можно хотя бы с вариационного исчисления — его проще освоить» подразумевает что собеседник не знает вариационного исчисления, а если бы знал — легко применил. А я утверждаю что применить все это тут с пользой — очень сложно, я пытался — не получилось.
Возможно, мои познания мат. анализа не достаточны, все же около 7 лет назад изучал. Попробуйте сами поучаствовать, если удастся добиться хорошего результата с применением ТОУ — с удовольствием послушаю как Вам это удалось.
Возможно, мои познания мат. анализа не достаточны, все же около 7 лет назад изучал. Попробуйте сами поучаствовать, если удастся добиться хорошего результата с применением ТОУ — с удовольствием послушаю как Вам это удалось.
подразумевает что собеседник не знает вариационного исчисления, а если бы знал — легко применил
Нет, я имел в виду то, что освоение ТОУ необходимо начать с вариационного исчисления, т.к. «продвинутые» методы в какой-то мере на нем основаны. Само по себе вариационное исчисление, скорее всего, неприменимо в рассматриваемой задаче, т.к. в ней существует множество ограничений, которые не могут быть учтены классическими методами.
Попробуйте сами поучаствовать, если удастся добиться хорошего результата с применением ТОУ — с удовольствием послушаю как Вам это удалось
Боюсь, что мои познания пока что тоже для этого недостаточны. Просто хотел подкинуть идею. Но, может быть, когда-нибудь и созрею. Есть шанс попробовать с помощью Матлаба, Optimization Toolbox, там не надо глубоко разбираться в теории, достаточно вызвать библиотечные функции.
Проблема в еще одном очевидном ограничении — времени внедрения. Видимо большинство участников не настолько погружены в предмет (динамические системы с дискретным временем) чтобы сходу в предложенные сроки(1.5 недели до первого приличного прототипа) данный подход реализовать.
Вот этот довод я могу понять. ТОУ — это крепкий орешек, тут знанием одного матана не отделаешься. Я уже говорил, что работаю над учебником уже длительное время, но пока что не могу сказать, что все освоил. Если включаешься в конкурс без должной подготовки — то за отведенное время не уложиться, это факт.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
История победы на ежегодном соревновании Russian AI Cup 2015