Задача планирования движения — различия между версиями

Текущая версия на 19:37, 4 сентября 2022

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

Содержание

1 Постановка задачи
2 Этапы
3 Предсказание траекторий движения объектов
- 3.1 Стандартный подход
- 3.2 Применение машинного обучения
4 Решение задачи для беспилотных автомобилей (англ. Self-driving cars)
5 Области применения
6 См. также
7 Примечания
8 Источники информации

Постановка задачи

Пусть задано непустое множество препятствий [math]O \subset W[/math] в области евклидова пространства . Пусть также задано твердое тело [math]A \subset W[/math], либо кинематическая цепь [math]A \langle B, J \rangle[/math], где — множество твердотельных звеньев (элементов кинематической цепи), а [math]J = (J_1, J_2, \dots, J_k)[/math] — множество кинематических ограничений таких, что при корректной конфигурации цепи предикаты ограничений принимают истинное значение. Под конфигурацией [math]c \in C_A[/math] здесь понимается набор значений параметров, однозначно определяющий положение точек объекта [math]A[/math] в пространстве сцены. Обычно используется минимальный набор параметров, соответствующий количеству степеней свободы объекта и определяющий пространство состояний или конфигурационное пространство объекта [math]C_A[/math].

Определение:

Пространством допустимых состояний назовем множество всех конфигураций объекта , удовлетворяющих кинематическим ограничениям и исключающих столкновения с препятствиями сцены. для кинетической цепи; для простого твердого тела.

Тогда постановка задачи поиска пути может быть сформулирована следующим образом. Для пары заданных бесконфликтных конфигураций требуется найти непрерывный путь такой, что [math]p(0) = c_{init}[/math] и [math]p(1) = c_{goal}[/math], где [math]\tau[/math] — момент времени.

Рисунок 1. Конфигурационные пространства двумерного твердого тела^[1]

Рисунок 2. Конфигурационные пространства двухзвенного манипуляционного робота^[1]. Углы поворота верхнего и нижнего звена соответствуют углу поворота образующей окружности тора и угловой координате точки на этой окружности соответственно

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

Этапы

Рисунок 3. Доля машинного обучения в используемых на каждом этапе методах^[2]

Восприятие/анализ обстановки (англ. Perception)

Рисунок 4. Визуализация восприятия автомобилем изображения с камеры^[3]

Анализ данных об окружении, выделение объектов и препятствий, определение их размеров, скоростей, и расстояний до них. Зачастую осуществляется путем применения алгоритмов машинного обучения для распознавания объектов на изображениях и прочих массивах данных (таких как данные с датчиков).

Предсказание движения объектов (англ. Prediction)

Рисунок 5. Предсказание движения окружающих объектов^[4]

Анализ собранных за время наблюдения данных об окружающих объектах для последующего построение модели их движения и предсказания их траекторий. Этот этап будет подробно рассмотрен далее.

Принятие решения/планирование траектории движения (англ. Planning)

Рисунок 6. Планирование траектории движения^[5]

Построение потенциальных траекторий движения и выбор итоговой на основе собранных на предыдущих этапах данных. Как правило осуществляется с помощью дискретизации пространства и последующего применения алгоритмов на графах, например различных вариаций RRT алгоритмов, для поиска оптимальной траектории. В последнее время также становятся более актуальными решения с применением машинного обучения — в частности, подходы на основе имитационного обучения и обратного обучения с подкреплением^[6]^[7], обученные на большом количестве примеров, предоставленных человеком^[2].

Предсказание траекторий движения объектов

Поскольку в общем случае мы не можем определить, как будут двигаться объекты, для предсказания траекторий их движений необходимо строить модели на основе прошлых измерений. Эти модели могут представлять из себя как простые предсказания (например, “объект продолжит двигаться с неизменной скоростью/ускорением”), так и более сложные алгоритмы.

Стандартный подход

Рисунок 7. Точность IMM по сравнению с точностью одной модели (константной скорости) с высокой и низкой степенью доверия предсказанию^[8]

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

Также проблематичным является тот факт, что одной модели (особенно простой) как правило недостаточно для описания траектории движения объекта. В связи с этим существует алгоритм, использующий множество взаимодействующих моделей (англ. Interacting Multiple Model, IMM) — подход применения сразу нескольких моделей, для каждой из которых поддерживается актуальная (меняющаяся по мере прошествия времени и получения новых измерений) вероятность того, что объект двигается согласно этой модели. Таким образом, используя, например, модель для каждого возможного движения, такого как поворот или ускорение, мы можем делать более точные предположения о том, где объект будет находиться в будущем.

Рисунок 8. Диаграмма процесса работы IMM^[9]. На картинке KF означает фильтр Калмана (англ. Kalman filter) — один из возможных предсказательных алгоритмов

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

Применение машинного обучения

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

Они применяются как для улучшения производительности самого алгоритма IMM (например, для улучшения точности в пересчете вероятностей^[10]), так и для его замены (иногда применяя тот же самый принцип^[11]).

Существуют и другие алгоритмы, основанные на машинном обучении (в основном использующие сверточные нейронные сети), и не опирающиеся на принцип работы IMM, вместо этого по большей части использующие большие массивы данных, собранные на основе передвижений автомобилей, которые управлялись людьми вручную^[12]^[13]^[14].

Решение задачи для беспилотных автомобилей (англ. Self-driving cars)

Для организации управления беспилотным автомобилем можно воспользоваться классическим подходом из робототехники. Задача самостоятельного передвижения разбивается на четыре модуля.

Модуль локализации отвечает за определение положения автомобиля в пространстве.
Модуль распознавания — за анализ окружающей обстановки.
Модуль планирования — за планирование маршрута исходя из обстановки и цели.
Модуль управления — за определение траектории движения в выбранном направлении.

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

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

Алгоритмы на графах

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

Разбиение пространства на клетки и построение графа на них.
Построение графа из регулярных примитивов движения (например, дуг).
Другие, более специализированные подходы, основанные на особенностях конкретной системы.

Самым популярным и зачастую самым оптимальным является алгоритм А*.

Преимущества:

Гарантированно находит кратчайший (в дискретизированном пространстве) путь.

Недостатки:

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

Оптимизационные алгоритмы

Идея оптимизационных алгоритмов заключается в следующем: рассмотрим траекторию нашего положения во времени, [math]x[/math] и [math]y[/math] — координаты, зависящие от времени [math]t[/math], то есть поймем, в какой точке мы хотим оказаться в момент времени [math]t[/math]. Можно сказать, что оптимальной в этом случае будет траектория, которая минимизирует функционал [math]J[/math], являющийся интегралом некоторой функции от траектории по времени.

, где — траектория.

Функция от траектории [math]L[/math] здесь каким-либо образом нас штрафует за резкие повороты, резкие разгоны, нахождение близко к препятствиям. Тогда, если просуммировать вдоль траектории все необходимые штрафы и попытаться это минимизировать с помощью стандартного математического аппарата, никак не связанного с автомобилями в целом и беспилотными автомобилями в частности, это решит задачу в общем виде.

Что лучше рассмотреть в качестве штрафов? Например, можно сказать, что не нужно подъезжать близко к препятствиям, учитывать это с каким-то весом, или что скорость не должна быть гораздо выше или ниже заранее определенной скорости. Можно штрафовать за вторую производную, которая является ускорением, потому что машина не должна резко ускоряться или замедляться.

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

Большинство методов оптимизации предпочитают работать с хорошо дифференцируемыми функциями, в то время как автомобиль — объект довольно сложной формы, и препятствия, которые он объезжает, это тоже объекты непростых форм. Поэтому нужно производить какие-то упрощения. Например, можно сказать, что машина — не что-то сложное, а просто пять окружностей.

Рисунок 9. Для удобства вычисления расстояний представим автомобиль в виде набора окружностей^[15]

Рисунок 10. Для плавной функции расстояния до препятствий введем поле градиентов^[15]

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

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

Преимущества:

Пространство управления непрерывно.

Недостатки:

Сходится к локальным минимумам.
Ограничения должны быть заданы дифференцируемыми функциями.

Стохастические алгоритмы

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

Рисунок 11.. Анимация 10000 итераций работы алгоритма RRT^[16]

Самым распространенным стохастическим алгоритмом является построение быстро исследующего случайного дерева (Rapidly-exploring Random Tree, RRT) или деревьев на его основе (RRT*^[17] и прочие).

Принцип заключается в итеративном построении дерева. На каждой итерации происходят следующие действия:

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

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

Преимущества:

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

Недостатки:

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

Специализированные алгоритмы

Рисунок 12. Построение и выбор плавной траектории смещения^[15]

В городе нет абстрактных точек А и Б и неструктурированного окружения со случайными препятствиями. На подобных сценах все относительно понятно: есть конкретные полосы и движение машины почти всегда заключается в том, что автомобиль едет примерно по центру полосы; иногда смещается левее или правее, чтобы объехать препятствие; иногда перестраивается, чтобы по правилам дорожного движения повернуть в нужном направлении.

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

Области применения

Беспилотные автомобили (англ. Self-driving cars).

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

Компьютерная анимация — вид трехмерной анимации, создаваемый при помощи компьютерной графики. Процедурная анимация полностью или частично рассчитывается компьютером, например:
- Симуляция физического взаимодействия твёрдых тел.
- Имитация движения систем частиц, жидкостей и газов.
- Имитация взаимодействия мягких тел (ткани, волос).
- Расчёт движения иерархической структуры связей (скелета персонажа) под внешним воздействием.
- Имитация автономного движения персонажа.

Фолдинг белка — процесс спонтанного свертывания полипептидной цепи в уникальную пространственную структуру. Механизм сворачивания белков до конца не изучен, но аминокислотная последовательность белка обычно известна. Поэтому учёные пытаются использовать различные биофизические методы, чтобы предсказать пространственную структуру белка.

Архитектурный дизайн.

Автоматизация процессов.

См. также

Примечания

Источники информации

[motion-planning-overview-1] 1,0 ^1,1 Казаков К.А. и Семенов В.А. (2016) "Обзор современных методов планирования движения"

[lyft-ml-motion-planning-2] 2,0 ^2,1 Peter Ondruska, Sammy Omari (2020) "The Next Frontier in Self-Driving: Using Machine Learning to Solve Motion Planning"

[3] Christoph Hammerschmidt (2020) "Deep learning method improves environment perception of self-driving cars"

[4] Sacha Arnoud, Peter Ondruska (2020) "Fueling Self-Driving Research with Level 5’s Open Prediction Dataset"

[5] Robert Morgan, Mason Lee (2020) "Virtual Validation: A Scalable Solution to Test & Navigate the Autonomous Road Ahead"

[6] Alexandre Gonfalonieri (2018) "Inverse Reinforcement Learning — Introduction and Main Issues"

[7] Abbeel P., Ng A.Y. (2011) "Inverse Reinforcement Learning"

[8] "Tracking Maneuvering Targets", MathWorks

[9] Jongwon Park, Jaeho Choi, Kunsoo Huh (2019) "Interacting Multiple Model Filter for Multi-Sensor Data Fusion System"

[10] Lichuan Deng, Da Li and Ruifang Li (2020) "Improved IMM Algorithm based on RNNs"

[11] Stefan Becker, Ronny Hug, Wolfgang Hübner, and Michael Arens (2019) "An RNN-based IMM Filter Surrogate"

[12] 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"

[13] 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"

[14] Mustafa Ozan Tezcan (2017) "Motion Estimation Using Convolutional Neural Networks"

[yandex-lecture-15] 15,0 ^15,1 ^15,2 Клюев Л. (2017) "Алгоритмы построения пути для беспилотного автомобиля. Лекция Яндекса", Хабр

[RRT_wiki-16] Rapidly-exploring random tree

[17] Tim Chin (2019) "Robotic Path Planning: RRT and RRT*: Exploring the optimized version of a orthodox path planning algorithm"

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

Задача планирования движения — различия между версиями

Текущая версия на 19:37, 4 сентября 2022

Содержание

Постановка задачи

Этапы

Восприятие/анализ обстановки (англ. Perception)

Предсказание движения объектов (англ. Prediction)

Принятие решения/планирование траектории движения (англ. Planning)

Предсказание траекторий движения объектов

Стандартный подход

Применение машинного обучения

Решение задачи для беспилотных автомобилей (англ. Self-driving cars)

Алгоритмы на графах

Оптимизационные алгоритмы

Стохастические алгоритмы

Специализированные алгоритмы

Области применения

См. также

Примечания

Источники информации

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты

@@ Строка 1: / Строка 1: @@
-{{В разработке}}
+Планирование движения (также известное как планирование пути и проблема навигации) — это вычислительная задача поиска последовательности допустимых конфигураций, которая перемещает объект от источника к месту назначения.
-Планирование движения, а также планирование пути (также известное как проблема навигации) — это вычислительная проблема для поиска последовательности допустимых конфигураций, которая перемещает объект от источника к месту назначения.
 == Постановка задачи ==
-{{Задача
+Пусть задано непустое множество препятствий <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>O \subset W</tex> в области евклидова пространства <tex>W \subset E^N,\ N \in \{2,3\}</tex>. Пусть также задано твердое тело либо кинематическая цепь <tex>A \subset W</tex> либо кинематическая цепь <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>.
-}}
-Рис. 1. Конфигурационные пространства двумерного твердого тела
 {{Определение
-|definition = Пространством допустимых состояний назовем множество всех конфигураций объекта <tex>c \in C_A</tex>, удовлетворяющих кинематическим ограничениям и исключающих столкновения с препятствиями сцены <tex>C_{free} = \{c \in C_A | J_1(c) \wedge J_2(c), \dots, \wedge J_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>
+|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_k(c), 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>, где <tex>\tau</tex> {{---}} момент времени.
-Рис. 1. Конфигурационные пространства двухзвенного манипуляционного робота
+{|align="center" cellpadding="0" cellspacing="0" style="margin: 0 auto;"
+ |[[Файл: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"/>. Углы поворота верхнего и нижнего звена соответствуют углу поворота образующей окружности тора и угловой координате точки на этой окружности соответственно]]
+ |}
 Поскольку планирование маршрута, как правило, допускает бесконечное
@@ Строка 22: / Строка 20: @@
 функцией, соответствующей минимальной длине маршрута или максимальной
 удаленности перемещаемого объекта от препятствий. На практике поиск пути даже в простых сценах с относительно небольшим количеством препятствий становится трудноразрешимой задачей, если перемещаемый объект имеет сложную геометрию или высокое число степеней свободы. В современных индустриальных приложениях часто требуется моделировать поведение сложных кинематических систем с шестью и более
-степенями свободы статическом или динамическом окружении,насчитывающим тысячи препятствий.
+степенями свободы в статическом или динамическом окружении, насчитывающим тысячи препятствий.
 == Этапы ==
+[[Файл: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>]]
 Построение потенциальных траекторий движения и выбор итоговой на основе собранных на предыдущих этапах данных.
-Как правило осуществляется с помощью дискретизации пространства и последующего применения алгоритмов на графах (таких как A*, RRT*, и прочих вариаций RRT, а также других) для поиска оптимальной траектории. В последнее время также становятся более актуальными решения с применением машинного обучения --- в частности, подходы на основе имитационного обучения и обратного обучения с подкреплением, обученные на большом количестве примеров, предоставленных человеком<ref>[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>.
+Как правило осуществляется с помощью дискретизации пространства и последующего применения алгоритмов на графах, например различных вариаций [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>, обученные на большом количестве примеров, предоставленных человеком<ref name="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) {{---}} подход применения сразу нескольких моделей, для каждой из которых поддерживается актуальная (меняющаяся по мере прошествия времени и получения новых измерений) вероятность того, что объект двигается согласно этой модели. Таким образом, используя, например, по модели для каждого возможного движения (поворот, ускорение, и так далее), мы можем делать более точные предположения о том, где объект будет находиться в будущем.
+Также проблематичным является тот факт, что одной модели (особенно простой) как правило недостаточно для описания траектории движения объекта. В связи с этим существует алгоритм, использующий множество взаимодействующих моделей (англ. ''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) также обладают своими недостатками как в точности (особенно при необходимости долговременного предсказания), так и в скорости, в связи с чем стали применяться и подходы, использующие машинное обучение, в частности {{---}} [[Рекуррентные нейронные сети|рекуррентные нейронные сети]].
-Они применяются как для улучшения производительности самого алгоритма 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://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>).
-так и для его замены
-<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
+Существуют и другие алгоритмы, основанные на машинном обучении (в основном использующие [[Сверточные нейронные сети|сверточные нейронные сети]]), и не опирающиеся на принцип работы 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>.
-<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) ==
+== Решение задачи для беспилотных автомобилей (англ. ''Self-driving cars'') ==
-Для организации управления беспилотным автомобилем можно воспользоваться классическим подходом из робототехники. Разобьем задачу самостоятельного передвижения на четыре модуля. Модуль локализации отвечает за то, чтобы машина понимала, где она находится. Модуль распознавания — за то, что находится вокруг машины. Модуль планирования обладает информацией о том, что находится вокруг, и зная, куда хочется приехать, строит маршрут. Модуль управления говорит, как же ехать по маршруту, чтобы приехать, выполнить эту траекторию. Но все же случай беспилотных автомобилей не так прост, как это может показаться в первом приближении.
+Для организации управления беспилотным автомобилем можно воспользоваться классическим подходом из робототехники. Задача самостоятельного передвижения разбивается на четыре модуля.
+*Модуль локализации отвечает за определение положения автомобиля в пространстве.
+*Модуль распознавания — за анализ окружающей обстановки.
+*Модуль планирования — за планирование маршрута исходя из обстановки и цели.
+*Модуль управления — за определение траектории движения в выбранном направлении.
-Автомобиль обладает рядом довольно существенных ограничений. Это не шар в пространстве, который может катиться в любую сторону и условно мгновенно останавливаться и замедляться. У автомобиля есть текущее направление, угол поворота колес, и он не может просто оказаться на два метра левее от текущего местоположения, это очень сложно. Он может ехать примерно вперед, поворачивая на какой-то угол, но тем не менее, перемещение очень сильно ограничено. И на траекторию движения влияют ограничениям, которые следуют из кинематики. Например, невозможно мгновенно разогнаться и мгновенно увеличить свое ускорение.
+Тем не менее такая модель все еще имеет множество проблем, которые необходимо решить. Автомобиль обладает рядом довольно существенных ограничений. У автомобиля есть текущее направление, угол поворота колес, и он не может просто оказаться на два метра левее от текущего местоположения, это очень сложно. Он может ехать примерно вперед, поворачивая на какой-то угол, но тем не менее, перемещение очень сильно ограничено. И на траекторию движения влияют ограничениям, которые следуют из кинематики. Например, невозможно мгновенно разогнаться и мгновенно увеличить свое ускорение.
-Для планирования дальнейшего движения автомобиля можно использовать нейросети, передавая информацию со всех датчиков и камер в нейросеть, предварительно ее обучив на каких-нибудь человеческих перемещениях. Обучить, в каких ситуациях куда нужно крутить руль, увеличивать или снижать скорость и т.д. В теории такой подход представляется хорошим решением проблемы, но на практике выяснилось, что нужно все-таки слишком много данных, нужна слишком большая нейросеть, чтобы за человеком все успешно повторять в различных ситуациях. В этом направлении ведется активная работа, и пока большинство успешных решений проблемы опирается на нейросети лишь частично, доверяя бо́льшую часть работы проверенным алгоритмам.
+Для планирования дальнейшего движения автомобиля можно использовать [[Нейронные сети, перцептрон|нейронные сети]], передавая информацию со всех датчиков и камер в сеть, предварительно ее обучив на человеческих перемещениях. Обучить, в каких ситуациях куда нужно крутить руль, увеличивать или снижать скорость. В теории такой подход представляется хорошим решением задачи, но на практике выяснилось, что нужно слишком много данных и слишком большая нейросеть, чтобы успешно повторять все за человеком в различных ситуациях. В этом направлении ведется активная работа, и пока большинство успешных решений задачи опирается на нейросети лишь частично, доверяя бо́льшую часть работы проверенным алгоритмам.
 === Алгоритмы на графах ===
-Существует несколько алгоритмов на графах, позволяющих решить проблему, но для их использования нужно понять, как построить граф по имеющейся информации. Для этого аналогично существует несколько подходов:
+Существует несколько [[:Категория:Кратчайшие пути в графах|алгоритмов на графах]], позволяющих решить задачу, но для их использования нужно понять, как построить граф по имеющейся информации. Для этого аналогично существует несколько подходов:
 * Разбиение пространства на клетки и построение графа на них.
 * Построение графа из регулярных примитивов движения (например, дуг).
-* И другие, более специализированные подходы, основанные на особенностях конкретной системы.
+* Другие, более специализированные подходы, основанные на особенностях конкретной системы.
 Самым популярным и зачастую самым оптимальным является [[Алгоритм A*|алгоритм А*]].
-Преимущества:
+'''Преимущества:'''
 * Гарантированно находит кратчайший (в дискретизированном пространстве) путь.
-Недостатки:
+'''Недостатки:'''
 * В пространствах малой размерности путь редко является кинематически выполнимым (зависит от метода построения графа).
-* В пространствах большой размерности время работы заметно ухудшается.
+* В пространствах большой размерности наблюдается заметное увеличение времени работы.
 === Оптимизационные алгоритмы ===
-Постановка задачи может быть такой: рассмотрим траекторию нашего положения во времени, <tex>x</tex> и <tex>y</tex>, зависящие от времени <tex>t</tex>, то есть поймем, в какой точке мы хотим оказаться в момент времени <tex>t</tex>. Мы можем определить угол касательной через арктангенс от производных, можем сказать, что оптимальной в этом случае будет траектория, которая минимизирует функционал, являющийся интегралом по времени вперед от какой-то функции от траектории. Функция от траектории здесь каким-либо образом нас штрафует за резкие повороты, резкие разгоны, нахождение близко к препятствиям и т. д. Тогда, если мы просуммируем вдоль нашей траектории все необходимые штрафы и попытаемся это минимизировать стандартным математическим аппаратом, никак не связанным с автомобилями в целом и беспилотными автомобилями в частности, то мы решим задачу в каком-то общем виде.
+Идея [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|''Рисунок 9.'' Для удобства вычисления расстояний представим автомобиль в виде набора окружностей<ref name="yandex-lecture">[https://habr.com/ru/company/yandex/blog/340674/ Клюев Л. (2017) "Алгоритмы построения пути для беспилотного автомобиля. Лекция Яндекса", Хабр]</ref>]]
+ |[[Файл:SpaceObstacleGradientField.png|thumb|400px|''Рисунок 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>]]
-Однако выход есть. Мы можем применить алгоритмы, которые работают некоторым случайным образом, но зато позволяют нам построить какой-то приближенный маршрут достаточно быстро и удобно. Например, мы будем строить наш граф, являющийся деревом, итеративным образом. Вначале ничего делить на клеточки не будем, никаких примитивов строить не будем. Мы просто возьмем симулятор нашей машины, который в целом умеет симулировать движение, максимально похожее на то, как машина едет по-настоящему. И возьмем стартовую точку. После этого итеративно выберем случайную точку в пространстве. И — найдем в текущем построенном дереве ближайший к ней узел. Построим ребро в сторону этой точки с помощью симуляции проезда в эту сторону.
+Самым распространенным стохастическим алгоритмом является построение быстро исследующего случайного дерева ([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> и прочие).
-Получается, мы каждый раз едем от нашего построенного дерева в случайную сторону и можем вершины в этом дереве делать в пространстве любой размерности, то есть в каждой вершине учитывать текущее направление машины, текущую скорость, ускорение, все углы, которые нам важны. А потом, когда мы возьмем новую точку, то возьмем и ближайшую к этой точке вершину. Проедем с помощью какой-то симуляции, например, 5 метров в сторону этой точки. Затем возьмем другую точку и проедем в ее сторону.
-Что нам это дает? Мы каждый раз исследуем пространство, но очень агрессивно. Мы не ищем оптимальные способы объехать препятствие. Мы просто ездим в разные стороны, но каждый раз делаем это из наиболее исследуемого участка нашего пространства к той, неизведанной стороне.
-=== Стохастические алгоритмы ===
-Самым распространенным стохастическим алгоритмом является построение быстро исследующего случайного дерева ([https://en.wikipedia.org/wiki/Rapidly-exploring_random_tree Rapidly-exploring Random Tree, RRT]) или деревьев на его основе (RRT* и прочие).
 Принцип заключается в итеративном построении дерева. На каждой итерации происходят следующие действия:
@@ Строка 126: / Строка 138: @@
 # Нахождения ближайшего к этой точке узла уже построенного дерева.
 # Построение ребра в сторону новой точки с помощью симуляции проезда нескольких метров.
-За счет этого мы довольно быстро получаем картину, где в разные стороны распространяются пути, которые как-то покрывают наше пространство. Возможно, неоптимально, но довольно быстро. Квадратик в углу {{---}} наша стартовая позиция. Потом мы можем получить какой-то путь к цели, который выглядит, возможно, не совсем оптимально, но зато получен достаточно быстрым способом.
-Преимущества:
+В результате достаточно быстро строится карта путей, которая некоторым (вероятнее всего, не оптимальным) образом покрывают пространство. Можно продолжать ее строить до тех пор, пока не найдется путь до искомой точки или пока не будет сочтено нужным остановиться.
-* Высокая скорость работы в пространствах большой размерности
-* Пути можно подавать практически напрямую в управляющий блок
+'''Преимущества:'''
+* Высокая скорость работы в пространствах большой размерности.
+* Пути можно подавать практически напрямую в управляющий блок.
-Недостатки:
+'''Недостатки:'''
-* Отсутствие гарантий на оптимальность
+* Отсутствие гарантий на оптимальность.
-* Высокая вероятность того, что траектория движения будет сильно извилистой (зависит от выбора дерева; например, RRT* не обладает такой проблемой)
+* Высокая вероятность того, что траектория движения будет сильно извилистой (зависит от выбора дерева; например, RRT* лишен этого недостатка).
 === Специализированные алгоритмы ===
-Когда машина ездит в городе, нет абстрактных точек А и Б и неструктурированного окружения со случайными препятствиями. В городе все более-менее понятно: есть конкретные полосы и движение нашей машины почти всегда заключается в том, что автомобиль едет примерно по центру полосы, иногда смещается левее или правее, чтобы объехать препятствие, иногда перестраивается, чтобы по правилам дорожного движения повернуть туда, куда нужно.
+[[Файл:LaneChangePaths.png|thumb|500px;left|''Рисунок 12.'' Построение и выбор плавной траектории смещения<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-driving cars)].
+* [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%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%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 Компьютерная анимация] {{---}} вид трехмерной анимации, создаваемый при помощи компьютерной графики. Процедурная анимация полностью или частично рассчитывается компьютером, например:
 ** Симуляция физического взаимодействия твёрдых тел.
 ** Имитация движения систем частиц, жидкостей и газов.
@@ Строка 153: / Строка 169: @@
 ** Имитация автономного движения персонажа.
-* [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://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://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 Автоматизация процессов]
+* [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'''
+* [[Сверточные нейронные сети]]
+* [[Рекуррентные нейронные сети]]
+* [[Алгоритм A*]]
+* [[Задача нахождения объектов на изображении]]
+* [[Анализ видео]]
 == Примечания ==