Изменения

{{В разработке}} Планирование движения (также известное как планирование пути и проблема навигации) — это вычислительная проблема для задача поиска последовательности допустимых конфигураций, которая перемещает объект от источника к месту назначения.

Как правило осуществляется с помощью дискретизации пространства и последующего применения алгоритмов на графах, например различных вариаций [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>

Также проблематичным является тот факт, что одной модели (особенно простой) как правило недостаточно для описания траектории движения объекта. В связи с этим существует алгоритм, использующий множество взаимодействующих моделей (англ. ''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>

Существуют и другие алгоритмы, основанные на машинном обучении (в основном использующие [[Сверточные нейронные сети|сверточные нейронные сети]]), и не опирающиеся на принцип работы 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>.

Для планирования дальнейшего движения автомобиля можно использовать [[Нейронные сети, перцептрон|нейронные сети]], передавая информацию со всех датчиков и камер в сеть, предварительно ее обучив на человеческих перемещениях. Обучить, в каких ситуациях куда нужно крутить руль, увеличивать или снижать скорость и так далее. В теории такой подход представляется хорошим решением задачи, но на практике выяснилось, что нужно слишком много данных и слишком большая нейросеть, чтобы успешно повторять все за человеком в различных ситуациях. В этом направлении ведется активная работа, и пока большинство успешных решений задачи опирается на нейросети лишь частично, доверяя бо́льшую часть работы проверенным алгоритмам.

* И другиеДругие, более специализированные подходы, основанные на особенностях конкретной системы.

* В пространствах большой размерности время наблюдается заметное увеличение времени работы заметно ухудшается.

Идея [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> здесь каким-либо образом нас штрафует за резкие повороты, резкие разгоны, нахождение близко к препятствиям и так далее. Тогда, если просуммировать вдоль траектории все необходимые штрафы и попытаться это минимизировать стандартным математическим аппаратомс помощью стандартного математического аппарата, никак не связанным связанного с автомобилями в целом и беспилотными автомобилями в частности, то это решит задачу в каком-то общем виде.

|[[Файл: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| ''Рисунок 511.''. Анимация 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"/>]]