Изменения

Планирование движения== Постановка задачи ==Пусть задано непустое множество препятствий <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>.

Постановка задачиПусть задана сцена как непустое множество препятствий O W в областиевклидова пространства W EN N {2,3}. Пусть также задано твердое тело{Определениелибо кинематическая цепь A W либо кинематическая цепь A❰B,J❱, где В |definition = Пространством допустимых состояний <tex>C_{B1, B2, …, Bnfree} W — </tex> назовем множество твердотельных звеньеввсех конфигураций объекта <tex>c \in C_A</tex>, а J удовлетворяющих кинематическим ограничениям и исключающих столкновения с препятствиями сцены. <tex>C_{free} = \{c \in C_A | J_1(c) \wedge J_2(J1,J2, …Jkc) — множество кинематических ограничений таких, что при корректной конфигурации цепи предикаты ограничений J1\wedge \dots \wedge J_k(c),J2B_1(c)\cap O = \varnothing,…,JkB_n(c) принимают истинное значение.Под конфигурацией \cap O = \varnothing\}</tex> для кинетической цепи; <tex>C_{free} = \{c CA здесь понимается набор значений параметров,однозначно определяющий положение точек объекта \in C_A | A в пространстве сцены(c) \cap O = \varnothing\}</tex> для простого твердого тела.Обычно используется минимальный набор параметров, соответствующийколичеству степеней свободы объекта и определяющий пространствосостояний или конфигурационное пространство объекта CA.}}

РисТогда постановка задачи поиска пути может быть сформулирована следующим образом. Для пары заданных бесконфликтных конфигураций <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> {{---}} момент времени. Конфигурационные пространства двумерного твердого тела

Определение (сюда бы сноску на учебник твой мфтишный вставить). Пространством допустимых состояний назовем множество всех конфигураций объекта c CA, удовлетворяющих кинематическим ограничениям и исключающих столкновения с препятствиями сцены Cfree = { c CA | J1(c) J2(c), …, JK(c) B1(c) align="center" cellpadding="0 " cellspacing= ∅,…, Bn(c) "0 " style= ∅}. Для простого твердого тела свободное множество определяется как Cfree = {c CA | A(c)"margin: 0 = ∅}auto;"Тогда постановка задачи поиска пути может быть сформулирована следующимобразом. Для пары заданных бесконфликтных конфигураций cinit, cgoal Cfreeтребуется найти непрерывный путь 𝒑(𝛕)|[[Файл: [0,ConfigurationSpaceSolidBody.jpg|thumb|400px|''Рисунок 1] → Cfree такой, что 𝒑(0) .'' Конфигурационные пространства двумерного твердого тела<ref name= cinit "motion-planning-overview">[https://cyberleninka.ru/article/n/obzor-sovremennyh-metodov-planirovaniya-dvizheniya Казаков К.А. и𝒑Семенов В.А. (12016) = cgoal "Обзор современных методов планирования движения"]</ref>]] Рис |[[Файл:ConfigurationSpaceRobot. 1jpg|thumb|400px|''Рисунок 2. '' Конфигурационные пространства двухзвенного манипуляционного робота<ref name="motion-planning-overview"/>. Углы поворота верхнего и нижнего звена соответствуют углу поворота образующей окружности тора и угловой координате точки на этой окружности соответственно]] |}

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

== Этапы==[[Файл: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>]]

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

=== Предсказание движения объектов (англ. ''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>, обученные на большом количестве примеров, предоставленных человеком (<ref name="lyft-ml-motion-planning">[https://medium.com/lyftself-driving/the-next-frontier-in-self-driving-using-machine-learning-to-solve-motion-planning-a259b814e9adPeter 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'') {{--- }} подход применения сразу нескольких моделей, для каждой из которых поддерживается актуальная (меняющаяся по мере прошествия времени и получения новых измерений) вероятность того, что объект двигается согласно этой модели. Таким образом, используя, например, по модели модель для каждого возможного движения (, такого как поворот, или ускорение, и так далее), мы можем делать более точные предположения о том, где объект будет находиться в будущем (. [[Файл:IMMDiagram.png|left|thumb|750px|''Рисунок 8.'' Диаграмма процесса работы IMM<ref>[https://www.youtubeksae.comorg/watchfunc/download_journal.php?vpath=L2hvbWUvdmlydHVhbC9rc2FlL2h0ZG9jcy91cGxvYWQvam91cm5hbC8yMDE5MTIyODE5MzI1OS44MDUxLjMuMS5wZGY=&filename=MTlBS1NBRV9EMDYyLnBkZg==hJG08iWlres&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-surrogateStefan 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.pdfMustafa Ozan Tezcan (2017) "Motion Estimation Using Convolutional Neural Networks"]</ref>. == Решение задачи для беспилотных автомобилей (англ. ''Self-driving cars'') == Для организации управления беспилотным автомобилем можно воспользоваться классическим подходом из робототехники. Задача самостоятельного передвижения разбивается на четыре модуля. *Модуль локализации отвечает за определение положения автомобиля в пространстве. *Модуль распознавания — за анализ окружающей обстановки. *Модуль планирования — за планирование маршрута исходя из обстановки и цели. *Модуль управления — за определение траектории движения в выбранном направлении. Тем не менее такая модель все еще имеет множество проблем, которые необходимо решить. Автомобиль обладает рядом довольно существенных ограничений. У автомобиля есть текущее направление, угол поворота колес, и он не может просто оказаться на два метра левее от текущего местоположения, это очень сложно. Он может ехать примерно вперед, поворачивая на какой-то угол, но тем не менее, перемещение очень сильно ограничено. И на траекторию движения влияют ограничениям, которые следуют из кинематики. Например, невозможно мгновенно разогнаться и мгновенно увеличить свое ускорение. Для планирования дальнейшего движения автомобиля можно использовать [[Нейронные сети, перцептрон|нейронные сети]], передавая информацию со всех датчиков и камер в сеть, предварительно ее обучив на человеческих перемещениях. Обучить, в каких ситуациях куда нужно крутить руль, увеличивать или снижать скорость. В теории такой подход представляется хорошим решением задачи, но на практике выяснилось, что нужно слишком много данных и слишком большая нейросеть, чтобы успешно повторять все за человеком в различных ситуациях. В этом направлении ведется активная работа, и пока большинство успешных решений задачи опирается на нейросети лишь частично, доверяя бо́льшую часть работы проверенным алгоритмам. === Алгоритмы на графах ===Существует несколько [[:Категория:Кратчайшие пути в графах|алгоритмов на графах]], позволяющих решить задачу, но для их использования нужно понять, как построить граф по имеющейся информации. Для этого аналогично существует несколько подходов:* Разбиение пространства на клетки и построение графа на них.* Построение графа из регулярных примитивов движения (например, дуг).* Другие, более специализированные подходы, основанные на особенностях конкретной системы. Самым популярным и зачастую самым оптимальным является [[Алгоритм A*|алгоритм А*]].

Решение проблемы для беспилотных автомобилей Идея [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_(self%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> {{---driving cars)}} координаты, зависящие от времени <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> {{-то угол, но тем не менее, перемещение очень сильно ограничено. И на траекторию движения влияют ограничениям, которые следуют из кинематики. Например, невозможно мгновенно разогнаться и мгновенно увеличить свое ускорение.Для планирования дальнейшего движения автомобиля можно использовать нейросети, передавая информацию со всех датчиков и камер в нейросеть, предварительно ее обучив на каких-нибудь человеческих перемещениях. Обучить, в каких ситуациях куда нужно крутить руль, увеличивать или снижать скорость и т.д. В теории такой подход представляется хорошим решением проблемы, но на практике выяснилось, что нужно все-таки слишком много данных, нужна слишком большая нейросеть, чтобы за человеком все успешно повторять в различных ситуациях. В этом направлении ведется активная работа, и пока большинство успешных решений проблемы опирается на нейросети лишь частично, доверяя бо́льшую часть работы проверенным алгоритмам}} траектория.

Алгоритмы на графахСуществует несколько алгоритмов на графахЧто лучше рассмотреть в качестве штрафов? Например, позволяющих решить проблемуможно сказать, но для их использования что не нужно понятьподъезжать близко к препятствиям, учитывать это с каким-то весом, как построить граф по имеющейся информацииили что скорость не должна быть гораздо выше или ниже заранее определенной скорости. Для этого аналогично существует несколько подходов:Разбиение пространства на клетки и построение графа на нихПостроение графа из регулярных примитивов движения (напримерМожно штрафовать за вторую производную, дуг)И другиекоторая является ускорением, более специализированные подходы, основанные на особенностях конкретной системы Самым популярным и зачастую самым оптимальным является алгоритм А* http://neercпотому что машина не должна резко ускоряться или замедляться.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_A*Преимущества: Гарантированно находит кратчайший (в дискретизированном пространстве) путьНедостатки: В пространствах малой размерности путь редко является кинематически выполнимым (зависит от метода построения графа) В пространствах большой размерности время работы заметно ухудшается

Постановка задачи может быть такой: рассмотрим траекторию нашего положения во времениБольшинство методов оптимизации предпочитают работать с хорошо дифференцируемыми функциями, в то время как автомобиль {{---}} объект довольно сложной формы, x и yпрепятствия, зависящие от времени tкоторые он объезжает, это тоже объекты непростых форм. Поэтому нужно производить какие-то есть поймем, в какой точке мы хотим оказаться в момент времени tупрощения. Мы можем определить угол касательной через арктангенс от производныхНапример, можем можно сказать, что оптимальной в этом случае будет траектория, которая минимизирует функционал, являющийся интегралом по времени вперед от какоймашина {{--то функции от траектории. Функция от траектории здесь каким-либо образом нас штрафует за резкие повороты, резкие разгоны, нахождение близко к препятствиям и т. д. Тогда, если мы просуммируем вдоль нашей траектории все необходимые штрафы и попытаемся это минимизировать стандартным математическим аппаратом, никак }} не связанным с автомобилями в целом и беспилотными автомобилями в частности, то мы решим задачу в какомчто-то общем видесложное, а просто пять окружностей.

Что лучше рассмотреть {|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'' красным и представляет собой препятствие. А наша машина — объект довольно сложной формыВведем поле расстояний от каждой точки до этой ломаной, которое направлено в сторону ломаной и препятствия, которые мы объезжаем, это тоже объекты хитрых форм. Поэтому тут нужно производить какое-то упрощение. Например, мы можем сказать, что машина обладает необходимыми свойствами дифференцируемости — пусть и не что-то сложное, а просто пять окружностейявляясь строго кратчайшим. Это позволит построить гладкую и аккуратную траекторию.

Рис'''Недостатки:'''* Сходится к локальным минимумам.* Ограничения должны быть заданы дифференцируемыми функциями. … Для удобства вычисления расстояний представим автомобиль в виде набора окружностей

Рис[[Файл: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 метров в сторону этой точки. Затем возьмем другую точку и проедем * Пути можно подавать практически напрямую в ее сторонууправляющий блок.

Что нам это дает? Мы каждый раз исследуем пространство, но очень агрессивно. Мы не ищем оптимальные способы объехать препятствие'''Недостатки:'''* Отсутствие гарантий на оптимальность. Мы просто ездим в разные стороны* Высокая вероятность того, но каждый раз делаем это из наиболее исследуемого участка нашего пространства к тойчто траектория движения будет сильно извилистой (зависит от выбора дерева; например, неизведанной сторонеRRT* лишен этого недостатка).

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

Самым распространенным стохастическим алгоритмом является построение быстро исследующего случайного дерева В связи с этим не всегда есть необходимость в деревьях (Rapidly-exploring Random Treeхотя они все еще нужны, например, RRT https://en.wikipedia.org/wiki/Rapidly-exploring_random_tree) во время парковки или деревьев на его основе (RRT* и прочиесложных маневров). Принцип заключается в итеративном построении дерева. На каждой итерации происходят следующие действия:Выбор случайной точки пространстваНахождения ближайшего Когда автомобиль едет на полосе, ему достаточно построить сравнительно плавную траекторию, следующую к центру этой точке узла уже построенного дереваПостроение ребра в сторону новой точки полосы или с помощью симуляции проезда нескольких метров.За счет этого мы довольно быстро получаем картину, где в разные стороны распространяются пути, которые каккаким-то покрывают наше пространствосмещением влево/вправо. ВозможноЭто сделать гораздо проще, неоптимально, но довольно быстро. Квадратик чем искать путь в углу — наша стартовая позицияграфе. Потом мы можем получить какой-то Поэтому простым решением будет взять текущее положение машины, посмотреть на путь к цели, который выглядитпо которому хотелось бы ехать, возможно, не совсем оптимально, но зато получен достаточно быстрым способоми плавно свернуть на этот путь.Преимущества<div style="clear: Высокая скорость работы в пространствах большой размерности Пути можно подавать практически напрямую в управляющий блокНедостатки: Отсутствие гарантий на оптимальность Высокая вероятность того, что траектория движения будет сильно извилистой (зависит от выбора дерева{{{1|both}}}; например, RRT* не обладает такой проблемой)"></div>

Области применения решений проблемы планирования * [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 Компьютерная анимация] {{---}} вид трехмерной анимации, создаваемый при помощи компьютерной графики. Процедурная анимация полностью или частично рассчитывается компьютером, например:** Симуляция физического взаимодействия твёрдых тел.** Имитация движениясистем частиц, жидкостей и газов.** Имитация взаимодействия мягких тел (ткани, волос).** Расчёт движения иерархической структуры связей (скелета персонажа) под внешним воздействием.** Имитация автономного движения персонажа.

Беспилотные автомобили (self* [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 Фолдинг белка] {{-driving cars)--}} процесс спонтанного свертывания полипептидной цепи в уникальную пространственную структуру. Механизм сворачивания белков до конца не изучен, но аминокислотная последовательность белка обычно известна. Поэтому учёные пытаются использовать различные биофизические методы, чтобы предсказать пространственную структуру белка.

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

Фолдинг белка — процесс спонтанного свертывания полипептидной цепи в уникальную нативную пространственную структуру. Механизм сворачивания белков до конца не изучен, но аминокислотная последовательность белка обычно известна. Поэтому учёные пытаются использовать различные биофизические методы, чтобы предсказать пространственную структуру белка== См.также ==* [[Сверточные нейронные сети]]* [[Рекуррентные нейронные сети]]* [[Алгоритм A*]]* [[Задача нахождения объектов на изображении]]* [[Анализ видео]]