Сферический гонщик в ваккуме

[bondkim137]

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

За единственную “аксиому” из неочевидных взял следующее:
- болид всегда должен стараться ехать на грани сцепления резины с дорогой;
это сделало выбор траектории в каждый момент времени одномерной задачей (угол на окружности сцепления с дорогой).

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

Дерево по понятным причинам очень быстро (экспоненциально с глубиной) начало расти.

Для эффективного отсечения я решил применить простой принцип: если в данной точке трека уже есть вариант, имеющий такую же скорость, то еще один туда не нужно совать со всеми его вероятными потомками. Естественно, с допусками, которые подгонялись эмпирически.

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

Но: мне не нравится, что каждый раз траектория робота отличается от предыдущей - в некоторых поворотах значительно. Соответственно, его результат заведомо нельзя считать идеальным.

Прошу помощи:
- как еще можно при подобном моделировании эффективно отсекать ненужные ветки эволюций возможных траекторий, кроме как занимать ячейки в пространстве положение-скорость?
- как лучше подобрать допуски размеров этих ячеек, кроме как эмпирическим путем? (и избавиться от magic numbers)

Ниже кликабельные демки текущего робота.

[Paragraph]

Посмотрите Monte Carlo Tree Search (MCTS) - это к первому вопросу.
На второй вопос - поиск метапараметров на сетке. Адаптивно, градиентно и/или Байесовскими методами. Все подходы вычислительно дорогие.

[bondkim137]

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

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

[12d3]

А если генетический алгоритм прикрутить? Например так: для каждой позиции рассматриваем некоторое фиксированное количество промежутков времени одинаковой длительности. Геном - это по две проекции ускорения на каждом из промежутков, т.е. считаем, что ускорение - это кусочно-постоянная функция. Фитнесс-функция - это расстояние, на которое удалось уехать за это время. Если вылетаем за пределы трека, то оценку для такого генома делаем очень маленькой.
Такой подход я применял для похожей задачки про движение машинки по треку, разница была только в физическом движке - ускорение было ограничено по модулю и присутствовало трение, пропорционально скорости.

[rockclimber]

bondkim137 в сообщении #1270082 писал(а):

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

Мой знакомый, фанат Формулы-1 с двадцатилетним стажем, утверждал (когда N лет назад пытался меня подбить написать игру - менеджер Формулы-1), что реальные пилоты водят практически на пределе, параметры вождения отличаются от идеальных чуть ли не на доли процента. Насколько я понимаю, пруфы у него есть (ну или он как минимум знает, где взять), могу попросить.

bondkim137 в сообщении #1270082 писал(а):

Ниже кликабельные демки текущего робота.

Зеленые точки на первой картинке - ваша рассчитанная траектория? Она не оптимальна, и это видно невооруженным взглядом Она была бы оптимальной (может быть), только если бы финиш был сразу за поворотом.
Кстати, тот же знакомый утверждает, что для серии поворотов оптимальных траекторий может быть больше одной.

[bondkim137]

12d3
Попробую понять разницу: у меня выбирается наиболее удачный потомок, выбирается предпоследний старший предок. Все братья этого предка убиваются со всем потомством. Отца тоже убиваем, отцом он и становится.
Генетический: все живут параллельно. Выбираем победителя и смотрим его историю. Не очень понятно только, как ее (историю) для всех хранить.

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

Или как раз разница в том, что б не убивать неудачников, а держать их в меньшем количестве по отношению к победителям? Интересно, надо попробовать. Спасибо за идею.

P.S. Трение там тоже есть, состоит из качения (константа) + аэродинамического сопротивления (квадрат скорости).

-- 29.11.2017, 16:23 --

rockclimber в сообщении #1270141 писал(а):

что реальные пилоты водят практически на пределе, параметры вождения отличаются от идеальных чуть ли не на доли процента

Я смотрел несколько записей с параметрами телеметрии и показателями ускорения. Мне показалось, что нередко простой бывает (всмысле когда сцепление не максимально и одновременно газ не полностью открыт). Особенно плохо мотоциклисты тормозят в повороте. Боятся потерять сцепление передним колесом и упасть, вероятно.

-- 29.11.2017, 16:27 --

rockclimber в сообщении #1270141 писал(а):

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

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

-- 29.11.2017, 16:30 --

rockclimber в сообщении #1270141 писал(а):

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

У меня тоже есть такое подозрение. По крайней мере, выраженные локальные максимумы точно есть. Пока еще руки не дошли найти конкретный пример.

-- 29.11.2017, 16:32 --

P.S. В F-1 траектории должны еще иметь свою специфику по сравнению с мотоциклами - там немаловажна аэродинамическая прижимная сила, которая грубо пропорциональна квадрату скорости.. ..как и центростремительное ускорение.

[12d3]

bondkim137 в сообщении #1270151 писал(а):

Не очень понятно только, как ее (историю) для всех хранить.

А зачем хранить? Итерация алгоритма такова: На входе имеется текущая позиция и текущая скорость. Мы пытаемся просчитать ситуацию на энное количество квантов времени, ГА выдает нам самую лучшую траекторию, которую нашел, мы смотрим, какое ускорение в первый квант времени, гонщик сдвигается на этот квант, конец итерации.
Объем вычислений для ГА зависит от глубины просчета линейно, а не экспоненциально. Популяцию обычно делают размером в десятки-сотни геномов, так что памяти тоже много не потребует, в отличие от кучи вершин дерева. Минус ГА - с увеличением глубины просчета быстро растет вероятность свалиться в плохие локальные максимумы, очень далекие от глобального максимума.

bondkim137 в сообщении #1270151 писал(а):

иначе при ограниченной "популяции" все живые особи благополучно умрут после длинной прямой в первом же повороте из-за недальновидности.

От этой проблемы может спасать MCTS, т.к. он работает таким образом: мы строим дерево, которое изначально состоит из одной вершины. На каждой итерации мы по определенному закону выбираем одну из вершин дерева, добавляем одного потомка к ней ,и симулируем траекторию гонщика из этого потомка до самого конца, используя некий дефолтный алгоритм (который может быть очень тупым и плохим, например, ехать посреди дороги с фиксированной небольшой скоростью), и вот в этом дефолтном алгоритме можно учесть невлетание в стенки на длинных прямых участках. В MCTS дерево растет не равномерно по всем вершинам с последующим отсечением неперспективных, а чем перспективнее вершина, тем больше она будет "проработана" вглубь.
В качестве еще одной идеи, есть beam search. Суть такова: опять же строим дерево с отсечениями, но таким образом: пусть мы имеем на $n$-ой итерации фиксированное количество траекторий глубины $n$, например, 1000. Мы ищем всех потомков у этих траекторий, т.е. до глубины $n+1$, а потом из них выбираем опять же 1000 лучших. Повторяем пока не надоест какое-то фиксированное количество итераций.

[rockclimber]

В общем, смысл моей идеи в чем. Оптимальная траектория в повороте - это окружность минимального радиуса. Но, если за поворотом идет прямой участок, то время, выигранное на повороте с маленьким радиусом, будет проиграно за счет того, что соперник, выбравший менее крутую траекторию, на выходе будет иметь большую скорость. Но чтобы реализовать это преимущество, участок должен иметь достаточную длину.
Я так понимаю, у вас пошаговый анализ? Проанализировали одну точку, выбрали несколько вариантов, потом следующую и так далее?
Я бы предложил выбрать некоторую предельную скорость, близкую к максимально возможной на прямом участке (пока не могу сказать, как ее оценить), потом найти участки, где эта скорость может быть достигнута (то есть гонцик выходит из поворота, разгоняется до этой скорости, потом успевает затормозить перед следующим поворотом). Разбить трассу на сегменты между этими участками и оптимизировать сегмент целиком. Ведь траектория захода в поворот с прямой и точка, в которой надо начинать торможение, зависят от участка впереди. Сначала задать некую "затравочную" траекторию, потом понемногу менять ее. Я пытался задавать опорные точки и аппроксимировать сплайнами («Помогите разобраться со сплайном и его кривизной»). Например, один поворот задавался примерно 5 - 10 опорными точками, по ним строился сплайн, который, опять же, разбивался на 10 - 20 участков, на которых ускорение и радиус кривизны принимались постоянными (только сплайн надо подходящий выбрать). Мне кажется, если строить дерево решений по опорным точкам сплайна, то и ваше дерево сильно поменьше будет, и траектория лучше на выходе.

[bondkim137]

rockclimber в сообщении #1270167 писал(а):

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

Тут вот какое дело. Что б было не скучно, типичный трек содержит повороты-улитки. Тут, например, красная закручивается, зеленая раскручивается. Эти повороты не представляются окружностью. В красном надо сбрасывать скорость. В синем - разгоняться. На практике из-за наличия трения, работающего как дармовой тормоз, получается так, что в красном сильнее наклоняются (выдерживают большее боковое ускорение), чем в синем. Кроме того, бывают S-образные сочленения и двойные повороты в одну сторону (синее). Наиболее выгодное положение между двумя поворотами в этих случаях значительно отличается.

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


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

-- 29.11.2017, 19:50 --

12d3 в сообщении #1270155 писал(а):

Популяцию обычно делают размером в десятки-сотни геномов, так что памяти тоже много не потребует, в отличие от кучи вершин дерева

Вот тут, например, нужно зеленую часть дороги разгоняться в пол, красную - в пол тормозить. Протяженность участка - около 18 секунд, допустим, 180 дискретизаций по времени. Прикиньте грубо на глаз, сколько нужно геномов, что б часть из них случайно догадалась сделать именно так и именно в этом месте перейти на торможение и именно один раз (а не два раза газовать, два тормозить, например). Плюс есть еще положение (левее-правее) на дороге, ибо трек все-таки не одномерный.

[12d3]

bondkim137 в сообщении #1270177 писал(а):

Прикиньте на глаз, сколько нужно геномов, что б часть из них случайно догадалась сделать именно так и именно в этом месте перейти на торможение и именно один раз.

Надо скорректировать фитнесс-функцию, чтобы она поощряла врезания в стенку на меньшей скорости. Тогда, если прям все врезаются, то они будут стремиться затормозить и наконец кто-нибудь перестанет врезаться.

[rockclimber]

bondkim137
Мне кажется, вы не поняли всю гениальность моего замысла
Вот смотрите.
1. Отмечаем опорные точки - массив пар чисел $(x_i, y_i)$
2. Добавляем параметр $t$ и строим параметрическую кривую по функциям $x(t)$ и $y(t)$
3. Для каждого значения параметра $t$ мы можем рассчитать радиус кривизны параметрической кривой
4. Зная радиус кривизны траектории в точке и параметры резины, можем рассчитать для каждой точки траектории максимальную скорость
5. Дальше находим локальные минимумы скорости, и проходя назад, убеждаемся, что успеваем затормозить на данном участке. Если не успеваем - корректируем максимальную скорость для данного участка. Как следствие, гонщика уже гарантированно не занесет. Теперь осталось проехать по траектории.
И здесь нигде нет окружностей!
Дальше, двигая опорные точки (и, может быть, добавляя/удаляя), делаем перерасчет и считаем время прохождения трассы.

Вот пример картинки, как это выглядело в моей программе (взял вашу карту за основу, только цвета подкорректировал, чтобы не слишком с моими сливались). Цветом обозначена кривизна - чем меньше радиус, тем краснее. Маленькие красные кружки - опорные точки:



-- 29.11.2017, 23:46 --

bondkim137 в сообщении #1270177 писал(а):

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

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

[Paragraph]

Описанный подход с контрольными точками и эвристиками описывает policy, улучшение текущей полиси - это policy iteration. Поясните подробнее, что Вас тут смущает? Должно работать, как описано. Если результаты получаются разными из разных прогонов, то надо фиксировать random seed. Потом повторить обучение с разными seed-ами, выбрать лучший результат.

Итерации в пространстве полиси должны сойтись (гораздо) быстрее, чем табличные методы или глубокое обучение. При условии, естесственно, что они построены так, что не ухудшают предыдущий результат. Но методы основанные на эвристиках и полиси гарантии абсолютного минимума не дают. Откуда известно, что оптимальное решение принадлежит классу, которым Вы ограничили оптимизацию? Если решать в более общем классе, то варианты динамического программирования - табличные методы, включая тот же MCTS, - на дискретном пространстве состояний могут дать более оптимальное решение. Загляните, например, в http://www.ozon.ru/context/detail/id/7107485/ Ваша задача точно соответствует теме этой книги. Ее бесплатный английский pdf гуглится (и это не бутлег, насколько я понимаю).

[bondkim137]

rockclimber в сообщении #1270238 писал(а):

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

Это уже интересно, спасибо. Если предложите алгоритм его улучшения, будет вообще замечательно.
Или, если есть возможность, хотя бы сформулируйте скалярную оценку траектории (на пальцах которая - максимальные радиусы в поворотах, как я понял), что б было от чего отталкиваться.

Также совершенно не очевидно, что подобная траектория будет являться оптимальной. В частности, если бы это было так, она была бы оптимальна в обоих направлениях. Но если ехать в противоположном направлении, траектория однозначно должна быть другая. Как минимум - из-за того, что разгон и торможение имеют различный предел (тормозить, как правило, проще, чем разгоняться, по крайней мере в рамках данной модели, в т.ч. из-за трения и ограниченной мощности двигателя). Говоря другими словами, строить тректорию с большим радиусом сразу после маневра с маленьким бессмысленно, т.к. скорость все равно будет небольшая.

-- 30.11.2017, 03:04 --

12d3 в сообщении #1270196 писал(а):

Надо скорректировать фитнесс-функцию, чтобы она поощряла врезания в стенку на меньшей скорости. Тогда, если прям все врезаются, то они будут стремиться затормозить и наконец кто-нибудь перестанет врезаться

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

[bondkim137]

Paragraph в сообщении #1270262 писал(а):

Поясните подробнее, что Вас тут смущает?

Честно говоря, в контексте конретного алгоритма, я ваше предложение пока еще не понял от слова "совсем". К глубокому моему сожалению.

[rockclimber]

bondkim137 в сообщении #1270264 писал(а):

хотя бы сформулируйте скалярную оценку траектории

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

bondkim137 в сообщении #1270264 писал(а):

Также совершенно не очевидно, что подобная траектория будет являться оптимальной.

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