43
правки
Изменения
Добавление примечаний, источников информации и части ссылок, частичное исправление форматирования
=== Принятие решения/планирование траектории движения ===
Построение потенциальных траекторий движения и выбор итоговой на основе собранных на предыдущих этапах данных.
Как правило осуществляется с помощью дискретизации пространства и последующего применения алгоритмов на графах (таких как A*, RRT*, и прочих вариаций RRT, а также других) для поиска оптимальной траектории. В последнее время также становятся более актуальными решения с применением машинного обучения --- в частности, подходы на основе имитационного обучения и обратного обучения с подкреплением, обученные на большом количестве примеров, предоставленных человеком (<ref>[https://medium.com/lyftself-driving/the-next-frontier-in-self-driving-using-machine-learning-to-solve-motion-planning-a259b814e9adPeter Ondruska and Sammy Omari (2020)"The Next Frontier in Self-Driving: Using Machine Learning to Solve Motion Planning"]</ref>.
== Предсказание траекторий движения объектов ==
=== Стандартный подход ===
Одна из основных сложностей в предсказании траекторий движения объектов заключается в неопределенности, которая появляется из-за погрешностей в измерениях сенсоров и невозможности однозначно предсказать действия объектов. Для смягчения этой проблемы применяются фильтры, которые приближают текущую позицию исходя из измерений сенсоров и наших предсказаний, а также степени уверенности в результатах обоих.
Также проблематичным является тот факт, что одной модели (особенно простой) как правило недостаточно для описания траектории движения объекта. В связи с этим существует алгоритм множества взаимодействующих моделей (Interacting Multiple Model, IMM) {{--- }} подход применения сразу нескольких моделей, для каждой из которых поддерживается актуальная (меняющаяся по мере прошествия времени и получения новых измерений) вероятность того, что объект двигается согласно этой модели. Таким образом, используя, например, по модели для каждого возможного движения (поворот, ускорение, и так далее), мы можем делать более точные предположения о том, где объект будет находиться в будущем (https://www.youtube.com/watch?v=hJG08iWlres).
Существуют и другие, более специализированные, подходы, опирающиеся на ряд заранее заданных правил, моделей и предположений об используемом пространстве.
=== Применение машинного обучения ===
Стандартные инженерные подходы (в том числе IMM) также обладают своими недостатками как в точности (особенно при необходимости долговременного предсказания), так и в скорости, в связи с чем появились и подходы, использующие машинное обучение, конкретнее в частности {{--- }} рекуррентные нейронные сети. Они применяются как для улучшения производительности самого алгоритма IMM (<ref>[https://iopscience.iop.org/article/10.1088/1742-6596/1518/1/012055 Lichuan Deng, Da Li and Ruifang Li (2020)"Improved IMM Algorithm based on RNNs"]</ref>, так и для его замены (<ref>[https://deepai.org/publication/an-rnn-based-imm-filter-surrogateStefan Becker, Ronny Hug, Wolfgang Hübner, and Michael Arens (2019)"An RNN-based IMM Filter Surrogate"]</ref>. Существуют и другие алгоритмы, основанные на машинном обучении (в основном использующие сверточные нейронные сети), и не опирающиеся на принцип работы IMM (<ref>[https://arxiv.org/pdf/1808.05819.pdf Nemanja Djuric, Vladan Radosavljevic, Henggang Cui, Thi Nguyen, Fang-Chieh Chou, Tsung-Han Lin, Nitin Singh, Jeff Schneider (2020) "Uncertainty-aware Short-term Motion Prediction of Traffic Actors for Autonomous Driving"]</ref><ref>[https://arxiv.org/pdf/1908.00219.pdf Henggang Cui, Thi Nguyen, Fang-Chieh Chou, Tsung-Han Lin, Jeff Schneider, David Bradley, Nemanja Djuric (2020) "Deep Kinematic Models for Kinematically Feasible Vehicle Trajectory Predictions"]</ref><ref>[http://www.bu.edu/vip/files/pubs/reports/MOT17-04buece.pdfMustafa Ozan Tezcan (2017)"Motion Estimation Using Convolutional Neural Networks"]</ref>.
== Решение проблемы для беспилотных автомобилей (self-driving cars) ==
Для организации управления беспилотным автомобилем можно воспользоваться классическим подходом из робототехники. Разобьем задачу самостоятельного передвижения на четыре модуля. Модуль локализации отвечает за то, чтобы машина понимала, где она находится. Модуль распознавания — за то, что находится вокруг машины. Модуль планирования обладает информацией о том, что находится вокруг, и зная, куда хочется приехать, строит маршрут. Модуль управления говорит, как же ехать по маршруту, чтобы приехать, выполнить эту траекторию. Но все же случай беспилотных автомобилей не так прост, как это может показаться в первом приближении.
Автомобиль обладает рядом довольно существенных ограничений. Это не шар в пространстве, который может катиться в любую сторону и условно мгновенно останавливаться и замедляться. У автомобиля есть текущее направление, угол поворота колес, и он не может просто оказаться на два метра левее от текущего местоположения, это очень сложно. Он может ехать примерно вперед, поворачивая на какой-то угол, но тем не менее, перемещение очень сильно ограничено. И на траекторию движения влияют ограничениям, которые следуют из кинематики. Например, невозможно мгновенно разогнаться и мгновенно увеличить свое ускорение.
Для планирования дальнейшего движения автомобиля можно использовать нейросети, передавая информацию со всех датчиков и камер в нейросеть, предварительно ее обучив на каких-нибудь человеческих перемещениях. Обучить, в каких ситуациях куда нужно крутить руль, увеличивать или снижать скорость и т.д. В теории такой подход представляется хорошим решением проблемы, но на практике выяснилось, что нужно все-таки слишком много данных, нужна слишком большая нейросеть, чтобы за человеком все успешно повторять в различных ситуациях. В этом направлении ведется активная работа, и пока большинство успешных решений проблемы опирается на нейросети лишь частично, доверяя бо́льшую часть работы проверенным алгоритмам.
=== Алгоритмы на графах ===
Существует несколько алгоритмов на графах, позволяющих решить проблему, но для их использования нужно понять, как построить граф по имеющейся информации. Для этого аналогично существует несколько подходов:
* Разбиение пространства на клетки и построение графа на них.* Построение графа из регулярных примитивов движения (например, дуг).* И другие, более специализированные подходы, основанные на особенностях конкретной системы. Самым популярным и зачастую самым оптимальным является [[Алгоритм A*|алгоритм А* http://neerc]].ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_A*
Преимущества:
* Гарантированно находит кратчайший (в дискретизированном пространстве) путь.
Недостатки:
* В пространствах малой размерности путь редко является кинематически выполнимым (зависит от метода построения графа).* В пространствах большой размерности время работы заметно ухудшается.
=== Оптимизационные алгоритмы ===
Постановка задачи может быть такой: рассмотрим траекторию нашего положения во времени, <tex>x </tex> и <tex>y</tex>, зависящие от времени <tex>t</tex>, то есть поймем, в какой точке мы хотим оказаться в момент времени <tex>t</tex>. Мы можем определить угол касательной через арктангенс от производных, можем сказать, что оптимальной в этом случае будет траектория, которая минимизирует функционал, являющийся интегралом по времени вперед от какой-то функции от траектории. Функция от траектории здесь каким-либо образом нас штрафует за резкие повороты, резкие разгоны, нахождение близко к препятствиям и т. д. Тогда, если мы просуммируем вдоль нашей траектории все необходимые штрафы и попытаемся это минимизировать стандартным математическим аппаратом, никак не связанным с автомобилями в целом и беспилотными автомобилями в частности, то мы решим задачу в каком-то общем виде.
Что лучше рассмотреть в качестве штрафов? Например, можно сказать, что мы не хотим подъезжать близко к препятствиям, учитывать это с каким-то весом, не хотим, чтобы наша скорость была гораздо выше или ниже желаемой скорости, которую мы для себя определили. Мы можем штрафовать себя за вторую производную, которая является ускорением, потому что мы не хотим, чтобы машина резко ускорялась или замедлялась.
Можем рассмотреть третью производную, которая является рывком, то есть мы не хотим, чтобы ускорение тоже менялось достаточно резко, поскольку это может сказаться на состоянии пассажиров. Если ускорение фиксированное и машина просто все время разгоняется, то, как показывают исследования, людей не укачивает. Также мы можем не хотеть делать крутые повороты, ограничиваем наш угол. И есть дополнительные ограничения, которые говорят, что машина физически не может разгоняться быстрее какого-то ускорения. Если все мы это учтем каким-то образом, то сможем решить задачу с помощью абстрактного алгоритма минимизации функции и получим некий результат.
Отдельно хочется поговорить про вычисления расстояний, потому что в большинстве методов оптимизации очень любят работать с плавными функциями, которые хорошо дифференцируемые, гладкие. Тогда там все работает хорошо. А наша машина — {{---}} объект довольно сложной формы, и препятствия, которые мы объезжаем, это тоже объекты хитрых форм. Поэтому тут нужно производить какое-то упрощение. Например, мы можем сказать, что машина — {{---}} не что-то сложное, а просто пять окружностей.
Что нужно, чтобы плавно изменялось расстояние? Евклидово расстояние до невыпуклых многоугольников не обладает необходимыми нам свойствами и плохо дифференцируемо в местах, где возникает отсутствие выпуклости. Поэтому мы можем построить такое псевдо расстояние по градиентному полю до нашей ломаной, она здесь обозначена красным и представляет собой препятствие. Мы можем довольно несложно ввести поле расстояний от каждой точки до этой ломаной, которая направлена в сторону ломаной и обладает необходимыми свойствами дифференцируемости — пусть и не являясь строго кратчайшей. Если мы все это сделаем — сможем построить гладкую, красивую и аккуратную траекторию.
Преимущества:
* Пространство управления непрерывно
Недостатки:
* Сходится к локальным минимумам
* Ограничения должны быть заданы дифференцируемыми функциями
К преимуществам таких методов мы относим то, что получается хорошая траектория и пространство управления непрерывно. Мы можем по нему ехать, все ограничения в той или иной степени соблюдаются. Но к сожалению, большинство оптимизационных методов или даже почти все так или иначе страдают от локальных минимумов, где их попытки что-либо оптимизировать застревают и не находят достаточно хорошего решения. Очень сложно все формулировать в виде математических дифференцируемых функций, это тоже не всегда получается.
=== Стохастические алгоритмы ===
Самым распространенным стохастическим алгоритмом является построение быстро исследующего случайного дерева (Rapidly-exploring Random Tree, RRT [https://en.wikipedia.org/wiki/Rapidly-exploring_random_treeRapidly-exploring Random Tree, RRT]) или деревьев на его основе (RRT* и прочие). Принцип заключается в итеративном построении дерева. На каждой итерации происходят следующие действия:
# Выбор случайной точки пространства.
# Нахождения ближайшего к этой точке узла уже построенного дерева.
# Построение ребра в сторону новой точки с помощью симуляции проезда нескольких метров.
За счет этого мы довольно быстро получаем картину, где в разные стороны распространяются пути, которые как-то покрывают наше пространство. Возможно, неоптимально, но довольно быстро. Квадратик в углу — {{---}} наша стартовая позиция. Потом мы можем получить какой-то путь к цели, который выглядит, возможно, не совсем оптимально, но зато получен достаточно быстрым способом.
Преимущества:
* Высокая скорость работы в пространствах большой размерности
* Пути можно подавать практически напрямую в управляющий блок
Недостатки:
* Отсутствие гарантий на оптимальность
== Области применения решений проблемы планирования движения ==
* [https://ru.wikipedia.org/wiki/%D0%91%D0%B5%D1%81%D0%BF%D0%B8%D0%BB%D0%BE%D1%82%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%BE%D0%B1%D0%B8%D0%BB%D1%8C Беспилотные автомобили (self-driving cars)].
* [https://ru.wikipedia.org/wiki/%D0%A0%D0%BE%D0%B1%D0%BE%D1%82%D0%B8%D0%B7%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D0%B0%D1%8F_%D1%85%D0%B8%D1%80%D1%83%D1%80%D0%B3%D0%B8%D1%8F Роботизированная хирургия — ] {{---}} хирургия с использованием робота во время операции. Поскольку один из способов проведения такого рода операций — {{---}} автоматический, возникает необходимость решения проблемы планирования движения робота.
* [https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80%D0%BD%D0%B0%D1%8F_%D0%B0%D0%BD%D0%B8%D0%BC%D0%B0%D1%86%D0%B8%D1%8F Компьютерная анимация — ] {{---}} вид трехмерной анимации, создаваемый при помощи трёхмерной компьютерной графики. Процедурная анимация полностью или частично рассчитывается компьютером, например:
** Симуляция физического взаимодействия твёрдых тел.
** Имитация движения систем частиц, жидкостей и газов.
** Имитация автономного движения персонажа.
* [https://ru.wikipedia.org/wiki/%D0%A4%D0%BE%D0%BB%D0%B4%D0%B8%D0%BD%D0%B3_%D0%B1%D0%B5%D0%BB%D0%BA%D0%B0 Фолдинг белка — ] {{---}} процесс спонтанного свертывания полипептидной цепи в уникальную нативную пространственную структуру. Механизм сворачивания белков до конца не изучен, но аминокислотная последовательность белка обычно известна. Поэтому учёные пытаются использовать различные биофизические методы, чтобы предсказать пространственную структуру белка. * [https://en.wikipedia.org/wiki/Architectural_Design Архитектурный дизайн] * [https://ru.wikipedia.org/wiki/%D0%90%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F Автоматизация процессов] == См. также =='''into the abyss'''
== Источники информации ==* Автоматизация процессов[https://en.wikipedia.org/wiki/Motion_planning "Motion Planning", Wikipedia]* [https://cyberleninka.ru/article/n/obzor-sovremennyh-metodov-planirovaniya-dvizheniya Казаков К.А. и Семенов В.А. (2016) "Обзор современных методов планирования движения"]* [https://habr.com/ru/company/yandex/blog/340674/ Клюев Л. (2017) "Алгоритмы построения пути для беспилотного автомобиля. Лекция Яндекса", Хабр]* [https://www.youtube.com/watch?v=hJG08iWlres Brian Douglas (2019) "Understanding Sensor Fusion and Tracking, Part 4: Tracking a Single Object With an IMM Filter", YouTube]* [https://www.youtube.com/watch?v=QR3U1dgc5RE Brian Douglas (2020) "Autonomous Navigation, Part 4: Path Planning with A* and RRT", YouTube]
[[Категория: Машинное обучение]]
