43
правки
Изменения
Добавление изображений и ссылок на их источники, незначительные исправления форматирования
|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>.
}}
{{Определение
|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>
}}
{|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"/>]] |}
Поскольку планирование маршрута, как правило, допускает бесконечное
Зачастую осуществляется путем применения алгоритмов машинного обучения для распознавания объектов на изображениях и прочих массивах данных (таких как данные с датчиков).
=== Предсказание траекторий движения объектов ===
Анализ собранных за время наблюдения данных об окружающих объектов для последующего построение модели их движения и предсказания их траекторий.
=== Принятие решения/планирование траектории движения ===
Стандартные инженерные подходы (в том числе 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-driving cars) ==
Самым популярным и зачастую самым оптимальным является [[Алгоритм A*|алгоритм А*]].
'''Преимущества:'''
* Гарантированно находит кратчайший (в дискретизированном пространстве) путь.
'''Недостатки:'''
* В пространствах малой размерности путь редко является кинематически выполнимым (зависит от метода построения графа).
* В пространствах большой размерности время работы заметно ухудшается.
Отдельно хочется поговорить про вычисления расстояний, потому что в большинстве методов оптимизации очень любят работать с плавными функциями, которые хорошо дифференцируемые, гладкие. Тогда там все работает хорошо. А наша машина {{---}} объект довольно сложной формы, и препятствия, которые мы объезжаем, это тоже объекты хитрых форм. Поэтому тут нужно производить какое-то упрощение. Например, мы можем сказать, что машина {{---}} не что-то сложное, а просто пять окружностей.
{|align="center" cellpadding="0" cellspacing="0" style="margin: 0 auto;" |[[Файл:CarCircleRepresentation.png|thumb|400px|''Рис. … 3.'' Для удобства вычисления расстояний представим автомобиль в виде набора окружностей<ref name="yandex-lecture">[https://habr.com/ru/company/yandex/blog/340674/ Клюев Л. (2017) "Алгоритмы построения пути для беспилотного автомобиля. Лекция Яндекса", Хабр]</ref>]] |[[Файл:SpaceObstacleGradientField.png|thumb|400px|''Рис. … 4.'' Для плавной функции расстояния до препятствий введем поле градиентов<ref name="yandex-lecture"/>]] |}
От окружностей очень легко считать расстояния до чего угодно и очень легко проверять окружность на пересечения с остальными геометрическими примитивами. Если расстояние до центра меньше, чем радиус, то вот пересечение, иначе все хорошо.
Что нужно, чтобы плавно изменялось расстояние? Евклидово расстояние до невыпуклых многоугольников не обладает необходимыми нам свойствами и плохо дифференцируемо в местах, где возникает отсутствие выпуклости. Поэтому мы можем построить такое псевдо расстояние по градиентному полю до нашей ломаной, она здесь обозначена красным и представляет собой препятствие. Мы можем довольно несложно ввести поле расстояний от каждой точки до этой ломаной, которая направлена в сторону ломаной и обладает необходимыми свойствами дифференцируемости — пусть и не являясь строго кратчайшей. Если мы все это сделаем — сможем построить гладкую, красивую и аккуратную траекторию.
'''Преимущества:'''* Пространство управления непрерывно.
'''Недостатки:'''* Сходится к локальным минимумам.* Ограничения должны быть заданы дифференцируемыми функциями.
К преимуществам таких методов мы относим то, что получается хорошая траектория и пространство управления непрерывно. Мы можем по нему ехать, все ограничения в той или иной степени соблюдаются. Но к сожалению, большинство оптимизационных методов или даже почти все так или иначе страдают от локальных минимумов, где их попытки что-либо оптимизировать застревают и не находят достаточно хорошего решения. Очень сложно все формулировать в виде математических дифференцируемых функций, это тоже не всегда получается.
=== Стохастические алгоритмы ===
[[Файл: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* и прочие).
За счет этого мы довольно быстро получаем картину, где в разные стороны распространяются пути, которые как-то покрывают наше пространство. Возможно, неоптимально, но довольно быстро. Квадратик в углу {{---}} наша стартовая позиция. Потом мы можем получить какой-то путь к цели, который выглядит, возможно, не совсем оптимально, но зато получен достаточно быстрым способом.
'''Преимущества:'''* Высокая скорость работы в пространствах большой размерности.* Пути можно подавать практически напрямую в управляющий блок.
'''Недостатки:'''* Отсутствие гарантий на оптимальность.* Высокая вероятность того, что траектория движения будет сильно извилистой (зависит от выбора дерева; например, RRT* не обладает такой проблемой).
=== Специализированные алгоритмы ===
Когда машина ездит в городе, нет абстрактных точек А и Б и неструктурированного окружения со случайными препятствиями. В городе все более-менее понятно: есть конкретные полосы и движение нашей машины почти всегда заключается в том, что автомобиль едет примерно по центру полосы, иногда смещается левее или правее, чтобы объехать препятствие, иногда перестраивается, чтобы по правилам дорожного движения повернуть туда, куда нужно.
[[Файл:LaneChangePaths.png|center|thumb|400px|''Рис. 6.'' Построение и выбор плавной траектории смещения<ref name="yandex-lecture"/>]]
Не всегда нужны эти хитрые деревья, чтобы парковаться или делать сложные маневры. Когда автомобиль едет на полосе, ему достаточно построить более-менее плавную траекторию, следующую к центру этой полосы или с каким-то смещением влево-вправо. Это сделать гораздо проще, чем искать абстрактный путь в графе. Поэтому простым решением будет взять текущее положение машины, посмотреть на путь, по которому мы хотели бы ехать, и плавно свернуть на этот путь.
