43
правки
Изменения
м
→Решение задачи для беспилотных автомобилей (англ. Self-driving cars): Добавление ссылок
Тем не менее такая модель все еще имеет множество проблем, которые необходимо решить. Автомобиль обладает рядом довольно существенных ограничений. У автомобиля есть текущее направление, угол поворота колес, и он не может просто оказаться на два метра левее от текущего местоположения, это очень сложно. Он может ехать примерно вперед, поворачивая на какой-то угол, но тем не менее, перемещение очень сильно ограничено. И на траекторию движения влияют ограничениям, которые следуют из кинематики. Например, невозможно мгновенно разогнаться и мгновенно увеличить свое ускорение.
Для планирования дальнейшего движения автомобиля можно использовать нейросети[[Нейронные сети, перцептрон|нейронные сети]], передавая информацию со всех датчиков и камер в нейросетьсеть, предварительно ее обучив на человеческих перемещениях. Обучить, в каких ситуациях куда нужно крутить руль, увеличивать или снижать скорость и так далее. В теории такой подход представляется хорошим решением проблемы, но на практике выяснилось, что нужно слишком много данных и слишком большая нейросеть, чтобы успешно повторять все за человеком в различных ситуациях. В этом направлении ведется активная работа, и пока большинство успешных решений проблемы опирается на нейросети лишь частично, доверяя бо́льшую часть работы проверенным алгоритмам.
=== Алгоритмы на графах ===
Существует несколько [[:Категория:Кратчайшие пути в графах|алгоритмов на графах]], позволяющих решить проблему, но для их использования нужно понять, как построить граф по имеющейся информации. Для этого аналогично существует несколько подходов:
* Разбиение пространства на клетки и построение графа на них.
* Построение графа из регулярных примитивов движения (например, дуг).
=== Стохастические алгоритмы ===
Существуют также [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 стохастические ] алгоритмы, которые работают некоторым случайным образом, но зато позволяют нам построить какой-то приближенный маршрут достаточно быстро и удобно. Мы каждый раз исследуем пространство, но очень агрессивно. Мы не ищем оптимальные способы объехать препятствие, а просто направляемся в разные стороны, но каждый раз делая это из наиболее исследованного участка нашего пространства к наименее исследованному.
[[Файл:RRTPath.png|right|thumb|200px|''Рис. 5.'' Один из путей, сгенерированных в процессе построения RRT<ref name="yandex-lecture"/>]]
Самым распространенным стохастическим алгоритмом является построение быстро исследующего случайного дерева ([https://en.wikipedia.org/wiki/Rapidly-exploring_random_tree Rapidly-exploring Random Tree, RRT]) или деревьев на его основе (RRT* <ref>[https://theclassytim.medium.com/robotic-path-planning-rrt-and-rrt-212319121378 Tim Chin (2019) "Robotic Path Planning: RRT and RRT*Exploring the optimized version of a orthodox path planning algorithm"]</ref> и прочие).
Принцип заключается в итеративном построении дерева. На каждой итерации происходят следующие действия:
