72
правки
Изменения
Отмена правки 80465, сделанной NikolayPlyusnin (обсуждение)
== Постановка задачи ==
{{Определение
|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>
Тогда постановка задачи поиска пути может быть сформулирована следующим образом. Для пары заданных бесконфликтных конфигураций <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> {{---}} момент времени.
Поскольку планирование маршрута, как правило, допускает бесконечное
функцией, соответствующей минимальной длине маршрута или максимальной
удаленности перемещаемого объекта от препятствий. На практике поиск пути даже в простых сценах с относительно небольшим количеством препятствий становится трудноразрешимой задачей, если перемещаемый объект имеет сложную геометрию или высокое число степеней свободы. В современных индустриальных приложениях часто требуется моделировать поведение сложных кинематических систем с шестью и более
степенями свободы в статическом или динамическом окружении,насчитывающим тысячи препятствий.
== Этапы ==
[[Файл: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*, и прочих например различных вариаций [https://en.wikipedia.org/wiki/Rapidly-exploring_random_tree RRTалгоритмов], а также других) для поиска оптимальной траектории. В последнее время также становятся более актуальными решения с применением машинного обучения {{--- }} в частности, подходы на основе имитационного обучения и обратного [[Обучение с подкреплением|обучения с подкреплением]]<ref>[https://towardsdatascience.com/inverse-reinforcement-learning-6453b7cdc90d Alexandre Gonfalonieri (2018) "Inverse Reinforcement Learning {{---}} Introduction and Main Issues"]</ref><ref>[https://link.springer.com/referenceworkentry/10.1007%2F978-0-387-30164-8_417 Abbeel P., Ng A.Y. (2011) "Inverse Reinforcement Learning"]</ref>, обученные на большом количестве примеров, предоставленных человеком<refname="lyft-ml-motion-planning">[https://medium.com/lyftself-driving/the-next-frontier-in-self-driving-using-machine-learning-to-solve-motion-planning-a259b814e9ad Peter Ondruska and , Sammy Omari (2020) "The Next Frontier in Self-Driving: Using Machine Learning to Solve Motion Planning"]</ref>. <div style="clear:{{{1|both}}};"></div>
== Предсказание траекторий движения объектов ==
Поскольку в общем случае мы не можем однозначно знатьопределить, как будут двигаться объекты, для предсказания траекторий их движений необходимо строить модели на основе прошлых измерений. Эти модели могут представлять из себя как простые предсказания (например, “объект продолжит двигаться с неизменной скоростью/ускорением”), так и более сложные алгоритмы.
=== Стандартный подход ===
[[Файл:IMMPrecision.png|right|thumb|400px|''Рисунок 7.'' Точность IMM по сравнению с точностью одной модели (константной скорости) с высокой и низкой степенью доверия предсказанию<ref>[https://www.mathworks.com/help/fusion/ug/tracking-maneuvering-targets.html "Tracking Maneuvering Targets", MathWorks]</ref>]]
Одна из основных сложностей в предсказании траекторий движения объектов заключается в неопределенности, которая появляется из-за погрешностей в измерениях сенсоров и невозможности однозначно предсказать действия объектов. Для смягчения этой проблемы применяются фильтры, которые приближают текущую позицию исходя из измерений сенсоров и наших предсказаний, а также степени уверенности в результатах обоих.
Также проблематичным является тот факт, что одной модели (особенно простой) как правило недостаточно для описания траектории движения объекта. В связи с этим существует алгоритм множества , использующий множество взаимодействующих моделей (англ. ''Interacting Multiple Model, IMM'') {{---}} подход применения сразу нескольких моделей, для каждой из которых поддерживается актуальная (меняющаяся по мере прошествия времени и получения новых измерений) вероятность того, что объект двигается согласно этой модели. Таким образом, используя, например, по модели модель для каждого возможного движения (, такого как поворот, или ускорение, и так далее), мы можем делать более точные предположения о том, где объект будет находиться в будущем. [[Файл:IMMDiagram.png|left|thumb|750px|''Рисунок 8.'' Диаграмма процесса работы IMM<ref>[https://www.ksae.org/func/download_journal.php?path=L2hvbWUvdmlydHVhbC9rc2FlL2h0ZG9jcy91cGxvYWQvam91cm5hbC8yMDE5MTIyODE5MzI1OS44MDUxLjMuMS5wZGY=&filename=MTlBS1NBRV9EMDYyLnBkZg==&bsid=46256 Jongwon Park, Jaeho Choi, Kunsoo Huh (2019) "Interacting Multiple Model Filter for Multi-Sensor Data Fusion System"]</ref>. На картинке KF означает [https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%BB%D1%8C%D1%82%D1%80_%D0%9A%D0%B0%D0%BB%D0%BC%D0%B0%D0%BD%D0%B0 фильтр Калмана] (англ. ''Kalman filter'') {{---}} один из возможных предсказательных алгоритмов]]<div style="clear:{{{1|both}}};"></div>
Существуют и другие, более специализированные, подходы, опирающиеся на ряд заранее заданных правил, моделей и предположений об используемом пространстве.
=== Применение машинного обучения ===
Стандартные инженерные подходы (в том числе 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'') ==
Для организации управления беспилотным автомобилем можно воспользоваться классическим подходом из робототехники. Разобьем задачу Задача самостоятельного передвижения разбивается на четыре модуля. *Модуль локализации отвечает за то, чтобы машина понимала, где она находитсяопределение положения автомобиля в пространстве. *Модуль распознавания — за то, что находится вокруг машиныанализ окружающей обстановки. *Модуль планирования обладает информацией о том, что находится вокруг, — за планирование маршрута исходя из обстановки и зная, куда хочется приехать, строит маршрутцели. *Модуль управления говорит, как же ехать по маршруту, чтобы приехать, выполнить эту траекторию. Но все же случай беспилотных автомобилей не так прост, как это может показаться — за определение траектории движения в первом приближениивыбранном направлении.
Тем не менее такая модель все еще имеет множество проблем, которые необходимо решить. Автомобиль обладает рядом довольно существенных ограничений. Это не шар в пространстве, который может катиться в любую сторону и условно мгновенно останавливаться и замедляться. У автомобиля есть текущее направление, угол поворота колес, и он не может просто оказаться на два метра левее от текущего местоположения, это очень сложно. Он может ехать примерно вперед, поворачивая на какой-то угол, но тем не менее, перемещение очень сильно ограничено. И на траекторию движения влияют ограничениям, которые следуют из кинематики. Например, невозможно мгновенно разогнаться и мгновенно увеличить свое ускорение.
Для планирования дальнейшего движения автомобиля можно использовать нейросети[[Нейронные сети, перцептрон|нейронные сети]], передавая информацию со всех датчиков и камер в нейросетьсеть, предварительно ее обучив на каких-нибудь человеческих перемещениях. Обучить, в каких ситуациях куда нужно крутить руль, увеличивать или снижать скорость и т.д. В теории такой подход представляется хорошим решением проблемызадачи, но на практике выяснилось, что нужно все-таки слишком много данных, нужна и слишком большая нейросеть, чтобы успешно повторять все за человеком все успешно повторять в различных ситуациях. В этом направлении ведется активная работа, и пока большинство успешных решений проблемы задачи опирается на нейросети лишь частично, доверяя бо́льшую часть работы проверенным алгоритмам.
=== Алгоритмы на графах ===
Существует несколько [[:Категория:Кратчайшие пути в графах|алгоритмов на графах]], позволяющих решить проблемузадачу, но для их использования нужно понять, как построить граф по имеющейся информации. Для этого аналогично существует несколько подходов:
* Разбиение пространства на клетки и построение графа на них.
* Построение графа из регулярных примитивов движения (например, дуг).
* И другиеДругие, более специализированные подходы, основанные на особенностях конкретной системы.
Самым популярным и зачастую самым оптимальным является [[Алгоритм A*|алгоритм А*]].
'''Преимущества:'''
* Гарантированно находит кратчайший (в дискретизированном пространстве) путь.
'''Недостатки:'''
* В пространствах малой размерности путь редко является кинематически выполнимым (зависит от метода построения графа).
* В пространствах большой размерности время наблюдается заметное увеличение времени работы заметно ухудшается.
=== Оптимизационные алгоритмы ===
Можно рассмотреть третью производную, которая является рывком, то есть не нужно, чтобы ускорение тоже менялось достаточно резко, поскольку это может сказаться на состоянии пассажиров. Если ускорение фиксированное и машина просто все время разгоняется, то, как показывают исследования, людей не укачивает. Также можно избегать крутых поворотов, ограничивая угол. Есть дополнительные ограничения, которые говорят, что машина физически не может разгоняться быстрее какого-то ускорения. Если все это учтется, то можно решить задачу с помощью абстрактного алгоритма минимизации функции и получить некий результат.
{|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"/>]]
|}
Принцип заключается в итеративном построении дерева. На каждой итерации происходят следующие действия:
# Нахождения ближайшего к этой точке узла уже построенного дерева.
# Построение ребра в сторону новой точки с помощью симуляции проезда нескольких метров.
В результате достаточно быстро строится карта путей, которая некоторым (вероятнее всего, не оптимальным) образом покрывают пространство. Можно продолжать ее строить до тех пор, пока не найдется путь до искомой точки или пока не будет сочтено нужным остановиться. '''Преимущества:'''* Высокая скорость работы в пространствах большой размерности.* Пути можно подавать практически напрямую в управляющий блок.
'''Недостатки:'''* Отсутствие гарантий на оптимальность.* Высокая вероятность того, что траектория движения будет сильно извилистой (зависит от выбора дерева; например, RRT* не обладает такой проблемойлишен этого недостатка).
=== Специализированные алгоритмы ===
== Области применения решений проблемы планирования движения ==
* [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 Автоматизация процессов].
== См. также ==
== Примечания ==