Изменения

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

{{Задача|definition = Пусть задана сцена как задано непустое множество препятствий <tex>O \subset W</tex> в области евклидова пространства <tex>W \subset E^N,\ N \in \{2,3\}</tex>. Пусть также задано твердое тело либо кинематическая цепь <tex>A \subset W</tex> , либо [https://ru.wikipedia.org/wiki/%D0%9A%D0%B8%D0%BD%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D1%86%D0%B5%D0%BF%D1%8C кинематическая цепь ] <tex>A \langle B, J \rangle</tex>, где <tex>B = \{B_1, B_2, \dots, B_n\} \subset W</tex> — множество твердотельных звеньев(элементов кинематической цепи), а <tex>J = (J_1, J_2, \dots, J_k)</tex> {{---}} множество кинематических ограничений таких, что при корректной конфигурации цепи предикаты ограничений <tex>J_1(c), J_2(c), \dots, J_k(c)</tex> принимают истинное значение. Под конфигурацией <tex>c \in C_A</tex> здесь понимается набор значений параметров, однозначно определяющий положение точек объекта <tex>A</tex> в пространстве сцены. Обычно используется минимальный набор параметров, соответствующий количеству степеней свободы объекта и определяющий пространство состояний или конфигурационное пространство объекта <tex>C_A</tex>.}}

|definition = Пространством допустимых состояний <tex>C_{free}</tex> назовем множество всех конфигураций объекта <tex>c \in C_A</tex>, удовлетворяющих кинематическим ограничениям и исключающих столкновения с препятствиями сцены . <tex>C_{free} = \{c \in C_A | J_1(c) \wedge J_2(c), \wedge \dots, \wedge J_KJ_k(c) \wedge , B_1(c) \cap O = \varnothing,…, B_n(c) \cap O = \varnothing\}</tex>. Для простого твердого тела свободное множество определяется как для кинетической цепи; <tex>C_{free} = \{c \in C_A | A(c) \cap O = \varnothing\}</tex>для простого твердого тела. Тогда постановка задачи поиска пути может быть сформулирована следующим образом. Для пары заданных бесконфликтных конфигураций <tex>c_{init},\ c_{goal} \in C_{free}</tex> требуется найти непрерывный путь <tex>p(\tau): [0,1] \rightarrow C_{free}</tex> такой, что <tex>p(0) = c_{init}</tex> и <tex>p(1) = c_{goal}</tex>

|[[Файл:ConfigurationSpaceSolidBody.jpg|thumb|400px|''Рис. Рисунок 1.'' Конфигурационные пространства двумерного твердого тела<ref name="motion-planning-overview">[https://cyberleninka.ru/article/n/obzor-sovremennyh-metodov-planirovaniya-dvizheniya Казаков К.А. и Семенов В.А. (2016) "Обзор современных методов планирования движения"]</ref>]] |[[Файл:ConfigurationSpaceRobot.jpg|thumb|400px|''Рис. Рисунок 2.'' Конфигурационные пространства двухзвенного манипуляционного робота<ref name="motion-planning-overview"/>. Углы поворота верхнего и нижнего звена соответствуют углу поворота образующей окружности тора и угловой координате точки на этой окружности соответственно]]

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

=== Восприятие/анализ обстановки (англ. ''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>]]

Как правило осуществляется с помощью дискретизации пространства и последующего применения алгоритмов на графах (таких как A*, RRT*, и прочих например различных вариаций RRT, а также других, см[https://en.wikipedia. [[Задача планирования движения#Решение проблемы для беспилотных автомобилей (selforg/wiki/Rapidly-driving cars)|далее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 and , 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) также обладают своими недостатками как в точности (особенно при необходимости долговременного предсказания), так и в скорости, в связи с чем появились стали применяться и подходы, использующие машинное обучение, в частности {{---}} [[Рекуррентные нейронные сети|рекуррентные нейронные сети]].

Они применяются как для улучшения производительности самого алгоритма 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-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англ. ''Self-driving cars'') ==

Тем не менее такая модель все еще имеет множество проблем, которые необходимо решить. Автомобиль обладает рядом довольно существенных ограничений. Это не шар в пространстве, который может катиться в любую сторону и условно мгновенно останавливаться и замедляться. У автомобиля есть текущее направление, угол поворота колес, и он не может просто оказаться на два метра левее от текущего местоположения, это очень сложно. Он может ехать примерно вперед, поворачивая на какой-то угол, но тем не менее, перемещение очень сильно ограничено. И на траекторию движения влияют ограничениям, которые следуют из кинематики. Например, невозможно мгновенно разогнаться и мгновенно увеличить свое ускорение.

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

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

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

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

Идея этого вида [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|''Рис. 3Рисунок 9.'' Для удобства вычисления расстояний представим автомобиль в виде набора окружностей<ref name="yandex-lecture">[https://habr.com/ru/company/yandex/blog/340674/ Клюев Л. (2017) "Алгоритмы построения пути для беспилотного автомобиля. Лекция Яндекса", Хабр]</ref>]] |[[Файл:SpaceObstacleGradientField.png|thumb|400px|''Рис. 4Рисунок 10.'' Для плавной функции расстояния до препятствий введем поле градиентов<ref name="yandex-lecture"/>]]

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

Что нужно, чтобы плавно изменялось расстояние? Евклидово расстояние до невыпуклых многоугольников не обладает необходимыми нам свойствами и плохо дифференцируемо в местах, где возникает наблюдается отсутствие выпуклости. Поэтому мы можем можно построить такое псевдо расстояние псевдорасстояние по градиентному полю до нашей ломаной, она здесь которая обозначена на ''Рис. 10'' красным и представляет собой препятствие. Мы можем довольно несложно ввести Введем поле расстояний от каждой точки до этой ломаной, которая направлена которое направлено в сторону ломаной и обладает необходимыми свойствами дифференцируемости — пусть и не являясь строго кратчайшейкратчайшим. Если мы все это сделаем — сможем Это позволит построить гладкую, красивую и аккуратную траекторию.

К преимуществам таких методов мы относим то, что получается хорошая траектория и пространство управления непрерывно=== Стохастические алгоритмы ===Существуют также [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>]]

Получается, мы каждый раз едем от нашего построенного дерева в случайную сторону и можем вершины в этом дереве делать в пространстве любой размерности, то есть в каждой вершине учитывать текущее направление машины, текущую скорость, ускорение, все углы, которые нам важны. А потом, когда мы возьмем новую точку, то возьмем и ближайшую к этой точке вершину. Проедем с помощью какой-то симуляции, например, 5 метров в сторону этой точки. Затем возьмем другую точку и проедем в ее сторону. Что нам это дает? Мы каждый раз исследуем пространство, но очень агрессивно. Мы не ищем оптимальные способы объехать препятствие. Мы просто ездим в разные стороны, но каждый раз делаем это из наиболее исследуемого участка нашего пространства к той, неизведанной стороне. === Стохастические алгоритмы ===[[Файл:RRTPath.png|right|thumb|200px|''Рис. 5.'' Один из путей, сгенерированных в процессе построения RRT<ref name="yandex-lecture"/>]] Самым распространенным стохастическим алгоритмом является построение быстро исследующего случайного дерева ([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> и прочие).

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

* Высокая вероятность того, что траектория движения будет сильно извилистой (зависит от выбора дерева; например, RRT* не обладает такой проблемойлишен этого недостатка).

[[Файл:LaneChangePaths.png|thumb|500px;left|''Рисунок 12.'' Построение и выбор плавной траектории смещения<ref name="yandex-lecture"/>]]В городе, нет абстрактных точек А и Б и неструктурированного окружения со случайными препятствиями. На такого рода подобных сценах все более-менее относительно понятно: есть конкретные полосы и движение машины почти всегда заключается в том, что автомобиль едет примерно по центру полосы, ; иногда смещается левее или правее, чтобы объехать препятствие, ; иногда перестраивается, чтобы по правилам дорожного движения повернуть туда, куда нужно. [[Файл:LaneChangePaths.png|center|thumb|400px|''Рисв нужном направлении. 6.'' Построение и выбор плавной траектории смещения<ref name="yandex-lecture"/>]]

Не В связи с этим не всегда есть необходимость в деревьях (хотя они все еще нужны хитрые деревья, чтобы парковаться например, во время парковки или делать сложные маневрысложных маневров). Когда автомобиль едет на полосе, ему достаточно построить более-менее сравнительно плавную траекторию, следующую к центру этой полосы или с каким-то смещением влево-/вправо. Это сделать гораздо проще, чем искать абстрактный путь в графе. Поэтому простым решением будет взять текущее положение машины, посмотреть на путь, по которому мы хотели хотелось бы ехать, и плавно свернуть на этот путь.<div style="clear:{{{1|both}}};"></div>

== Области применения решений проблемы планирования движения ==

* [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англ. ''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 Автоматизация процессов].