Изменения

Перейти к: навигация, поиск

Задача планирования движения

2860 байт добавлено, 23 январь
Отмена правки 80465, сделанной NikolayPlyusnin (обсуждение)
{{В разработке}} Планирование движения (также известное как планирование пути и проблема навигации) — это вычислительная проблема для задача поиска последовательности допустимых конфигураций, которая перемещает объект от источника к месту назначения.
== Постановка задачи ==
== Этапы ==
[[Файл:MotionPlanningMLUsage.png|left|thumb|600px|''Рисунок 3.'' Доля машинного обучения в используемых на каждом этапе методах<ref name="lyft-ml-motion-planning"/>]]
<div style="clear:{{{1|both}}};"></div>
=== Восприятие/анализ обстановки (англ. ''Perception'')===
[[Файл:AutoCarPerception.jpg|left|thumb|450px|''Рисунок 4.'' Визуализация восприятия автомобилем изображения с камеры<ref>[https://www.eenewsautomotive.com/news/deep-learning-method-improves-environment-perception-self-driving-cars Christoph Hammerschmidt (2020) "Deep learning method improves environment perception of self-driving cars"]</ref>]]
Анализ данных об окружении, выделение объектов и препятствий, определение их размеров, скоростей, и расстояний до них.
Зачастую осуществляется путем применения алгоритмов машинного обучения для [[Задача нахождения объектов на изображении|распознавания объектов]] на изображениях и прочих массивах данных (таких как данные с датчиков).
 
<div style="clear:{{{1|both}}};"></div>
=== Предсказание движения объектов (англ. ''Prediction'') ===
 
[[Файл:AutoCarPrediction.png|left|thumb|450px|''Рисунок 5.'' Предсказание движения окружающих объектов<ref>[https://medium.com/lyftself-driving/fueling-self-driving-research-with-level-5s-open-prediction-dataset-f0175e2b0cf8 Sacha Arnoud, Peter Ondruska (2020) "Fueling Self-Driving Research with Level 5’s Open Prediction Dataset"]</ref>]]
Анализ собранных за время наблюдения данных об окружающих объектах для последующего построение модели их движения и предсказания их траекторий.
Этот этап будет подробно рассмотрен далее.
 
<div style="clear:{{{1|both}}};"></div>
=== Принятие решения/планирование траектории движения (англ. ''Planning'') ===
[[Файл:AutoCarPlanning.png|left|thumb|450px|''Рисунок 6.'' Планирование траектории движения<ref>[https://medium.com/lyftself-driving/virtual-validation-a-scalable-solution-to-test-navigate-the-autonomous-road-ahead-e1a7d1fe1538 Robert Morgan, Mason Lee (2020) "Virtual Validation: A Scalable Solution to Test & Navigate the Autonomous Road Ahead"]</ref>]]
Построение потенциальных траекторий движения и выбор итоговой на основе собранных на предыдущих этапах данных.
Как правило осуществляется с помощью дискретизации пространства и последующего применения алгоритмов на графах, например различных вариаций [https://en.wikipedia.org/wiki/Rapidly-exploring_random_tree RRT алгоритмов], для поиска оптимальной траектории. В последнее время также становятся более актуальными решения с применением машинного обучения {{---}} в частности, подходы на основе имитационного обучения и обратного [[Обучение с подкреплением|обучения с подкреплением]]<ref>[https://towardsdatascience.com/inverse-reinforcement-learning-6453b7cdc90d Alexandre Gonfalonieri (2018) "Inverse Reinforcement Learning {{---}} Introduction and Main Issues"]</ref><ref>[https://link.springer.com/referenceworkentry/10.1007%2F978-0-387-30164-8_417 Abbeel P., Ng A.Y. (2011) "Inverse Reinforcement Learning"]</ref>, обученные на большом количестве примеров, предоставленных человеком<refname="lyft-ml-motion-planning">[https://medium.com/lyftself-driving/the-next-frontier-in-self-driving-using-machine-learning-to-solve-motion-planning-a259b814e9ad Peter Ondruska, Sammy Omari (2020) "The Next Frontier in Self-Driving: Using Machine Learning to Solve Motion Planning"]</ref>. <div style="clear:{{{1|both}}};"></div>
== Предсказание траекторий движения объектов ==
=== Стандартный подход ===
[[Файл:IMMPrecision.png|right|thumb|400px|''Рисунок 7.'' Точность IMM по сравнению с точностью одной модели (константной скорости) с высокой и низкой степенью доверия предсказанию<ref>[https://www.mathworks.com/help/fusion/ug/tracking-maneuvering-targets.html "Tracking Maneuvering Targets", MathWorks]</ref>]]
 
Одна из основных сложностей в предсказании траекторий движения объектов заключается в неопределенности, которая появляется из-за погрешностей в измерениях сенсоров и невозможности однозначно предсказать действия объектов. Для смягчения этой проблемы применяются фильтры, которые приближают текущую позицию исходя из измерений сенсоров и наших предсказаний, а также степени уверенности в результатах обоих.
Также проблематичным является тот факт, что одной модели (особенно простой) как правило недостаточно для описания траектории движения объекта. В связи с этим существует алгоритм, использующий множество взаимодействующих моделей (англ. ''Interacting Multiple Model, IMM'') {{---}} подход применения сразу нескольких моделей, для каждой из которых поддерживается актуальная (меняющаяся по мере прошествия времени и получения новых измерений) вероятность того, что объект двигается согласно этой модели. Таким образом, используя, например, по модели модель для каждого возможного движения (, такого как поворот, или ускорение, и так далее), мы можем делать более точные предположения о том, где объект будет находиться в будущем. [[Файл:IMMDiagram.png|left|thumb|750px|''Рисунок 8.'' Диаграмма процесса работы IMM<ref>[https://www.ksae.org/func/download_journal.php?path=L2hvbWUvdmlydHVhbC9rc2FlL2h0ZG9jcy91cGxvYWQvam91cm5hbC8yMDE5MTIyODE5MzI1OS44MDUxLjMuMS5wZGY=&filename=MTlBS1NBRV9EMDYyLnBkZg==&bsid=46256 Jongwon Park, Jaeho Choi, Kunsoo Huh (2019) "Interacting Multiple Model Filter for Multi-Sensor Data Fusion System"]</ref>. На картинке KF означает [https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%BB%D1%8C%D1%82%D1%80_%D0%9A%D0%B0%D0%BB%D0%BC%D0%B0%D0%BD%D0%B0 фильтр Калмана] (англ. ''Kalman filter'') {{---}} один из возможных предсказательных алгоритмов]]<div style="clear:{{{1|both}}};"></div>
Существуют и другие, более специализированные, подходы, опирающиеся на ряд заранее заданных правил, моделей и предположений об используемом пространстве.
так и для его замены (иногда применяя тот же самый принцип<ref>[https://deepai.org/publication/an-rnn-based-imm-filter-surrogate Stefan 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.pdf Mustafa Ozan Tezcan (2017) "Motion Estimation Using Convolutional Neural Networks"]</ref>.
== Решение задачи для беспилотных автомобилей (англ. ''Self-driving cars'') ==
Тем не менее такая модель все еще имеет множество проблем, которые необходимо решить. Автомобиль обладает рядом довольно существенных ограничений. У автомобиля есть текущее направление, угол поворота колес, и он не может просто оказаться на два метра левее от текущего местоположения, это очень сложно. Он может ехать примерно вперед, поворачивая на какой-то угол, но тем не менее, перемещение очень сильно ограничено. И на траекторию движения влияют ограничениям, которые следуют из кинематики. Например, невозможно мгновенно разогнаться и мгновенно увеличить свое ускорение.
Для планирования дальнейшего движения автомобиля можно использовать [[Нейронные сети, перцептрон|нейронные сети]], передавая информацию со всех датчиков и камер в сеть, предварительно ее обучив на человеческих перемещениях. Обучить, в каких ситуациях куда нужно крутить руль, увеличивать или снижать скорость и так далее. В теории такой подход представляется хорошим решением задачи, но на практике выяснилось, что нужно слишком много данных и слишком большая нейросеть, чтобы успешно повторять все за человеком в различных ситуациях. В этом направлении ведется активная работа, и пока большинство успешных решений задачи опирается на нейросети лишь частично, доверяя бо́льшую часть работы проверенным алгоритмам.
=== Алгоритмы на графах ===
* Разбиение пространства на клетки и построение графа на них.
* Построение графа из регулярных примитивов движения (например, дуг).
* И другиеДругие, более специализированные подходы, основанные на особенностях конкретной системы.
Самым популярным и зачастую самым оптимальным является [[Алгоритм A*|алгоритм А*]].
'''Недостатки:'''
* В пространствах малой размерности путь редко является кинематически выполнимым (зависит от метода построения графа).
* В пространствах большой размерности время наблюдается заметное увеличение времени работы заметно ухудшается.
=== Оптимизационные алгоритмы ===
Идея [https://ru.wikipedia.org/wiki/%D0%9E%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) оптимизационных] алгоритмов заключается в следующем: рассмотрим траекторию нашего положения во времени, <tex>x</tex> и <tex>y</tex>{{---}} координаты, зависящие от времени <tex>t</tex>, то есть поймем, в какой точке мы хотим оказаться в момент времени <tex>t</tex>. Не составит труда определить угол касательной через арктангенс от производных, можно Можно сказать, что оптимальной в этом случае будет траектория, которая минимизирует функционал<tex>J</tex>, являющийся интегралом некоторой функции от траектории по времени вперед от какой.  <tex>J[\text{x}(t)] = \int\limits_{t_0}^{t_0 + T} L(\text{x}, \text{x}', \text{x}'', \text{x}''') dt</tex>, где <tex>\text{x}(t) = (x(t), y(t))^T</tex> {{---то функции от траектории}} траектория.  Функция от траектории <tex>L</tex> здесь каким-либо образом нас штрафует за резкие повороты, резкие разгоны, нахождение близко к препятствиям и так далее. Тогда, если просуммировать вдоль траектории все необходимые штрафы и попытаться это минимизировать стандартным математическим аппаратомс помощью стандартного математического аппарата, никак не связанным связанного с автомобилями в целом и беспилотными автомобилями в частности, то это решит задачу в каком-то общем виде.
Что лучше рассмотреть в качестве штрафов? Например, можно сказать, что не нужно подъезжать близко к препятствиям, учитывать это с каким-то весом, или что скорость не должна быть гораздо выше или ниже заранее определенной скорости. Можно штрафовать за вторую производную, которая является ускорением, потому что машина не должна резко ускоряться или замедляться.
{|align="center" cellpadding="0" cellspacing="0" style="margin: 0 auto;"
|[[Файл:CarCircleRepresentation.png|thumb|400px|''Рисунок 39.'' Для удобства вычисления расстояний представим автомобиль в виде набора окружностей<ref name="yandex-lecture">[https://habr.com/ru/company/yandex/blog/340674/ Клюев Л. (2017) "Алгоритмы построения пути для беспилотного автомобиля. Лекция Яндекса", Хабр]</ref>]] |[[Файл:SpaceObstacleGradientField.png|thumb|400px|''Рисунок 410.'' Для плавной функции расстояния до препятствий введем поле градиентов<ref name="yandex-lecture"/>]]
|}
От окружностей очень легко считать расстояния до чего угодно и очень легко проверять окружность на пересечения с остальными геометрическими примитивами. Если расстояние до центра меньше, чем радиус, то вот пересечениеможно утверждать, иначе все хорошочто объекты пересекаются.
Что нужно, чтобы плавно изменялось расстояние? Евклидово расстояние до невыпуклых многоугольников не обладает необходимыми свойствами и плохо дифференцируемо в местах, где возникает наблюдается отсутствие выпуклости. Поэтому можно построить псевдорасстояние по градиентному полю до ломаной, которая обозначена на ''Рис. 410'' красным и представляет собой препятствие. Введем поле расстояний от каждой точки до этой ломаной, которое направлено в сторону ломаной и обладает необходимыми свойствами дифференцируемости — пусть и не являясь строго кратчайшим. Это позволит построить гладкую и аккуратную траекторию.
'''Преимущества:'''
=== Стохастические алгоритмы ===
Существуют также [https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%BE%D1%85%D0%B0%D1%81%D1%82%D0%B8%D1%87%D0%BD%D0%BE%D1%81%D1%82%D1%8C стохастические] алгоритмы, которые работают некоторым случайным образом, но зато и позволяют нам построить какой-то приближенный маршрут достаточно быстро и удобно. Мы каждый раз исследуем пространство, но очень агрессивно. Мы Алгоритм не ищем ищет оптимальные способы объехать препятствие, а просто направляемся в разные стороныразных направлениях исследует пространство, но каждый раз делая это из наиболее исследованного участка нашего пространства к наименее исследованномуизученному.
[[Файл:RRT_animation.gif|right|thumb|300px| ''Рисунок 11.''. Анимация 10000 итераций работы алгоритма RRT <ref name="RRT_wiki">[https://en.wikipedia.org/wiki/Rapidly-exploring_random_tree Rapidly-exploring random tree]</ref>]]
Самым распространенным стохастическим алгоритмом является построение быстро исследующего случайного дерева ([https://en.wikipedia.org/wiki/Rapidly-exploring_random_tree Rapidly-exploring Random Tree, RRT]) или деревьев на его основе (RRT*<ref>[https://theclassytim.medium.com/robotic-path-planning-rrt-and-rrt-212319121378 Tim Chin (2019) "Robotic Path Planning: RRT and RRT*: Exploring the optimized version of a orthodox path planning algorithm"]</ref> и прочие).
Принцип заключается в итеративном построении дерева. На каждой итерации происходят следующие действия:
=== Специализированные алгоритмы ===
[[Файл:LaneChangePaths.png|thumb|500px;left|''Рисунок 612.'' Построение и выбор плавной траектории смещения<ref name="yandex-lecture"/>]]
В городе нет абстрактных точек А и Б и неструктурированного окружения со случайными препятствиями. На подобных сценах все относительно понятно: есть конкретные полосы и движение машины почти всегда заключается в том, что автомобиль едет примерно по центру полосы; иногда смещается левее или правее, чтобы объехать препятствие; иногда перестраивается, чтобы по правилам дорожного движения повернуть в нужном направлении.
72
правки

Навигация