Изменения

Существуют также [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 стохастические] алгоритмы, которые работают некоторым случайным образом, но зато позволяют нам построить какой-то приближенный маршрут достаточно быстро и удобно. Мы каждый раз исследуем пространство, но очень агрессивно. Мы не ищем оптимальные способы объехать препятствие, а просто направляемся в разные стороны, но каждый раз делая это из наиболее исследованного участка нашего пространства к наименее исследованному.

Самым распространенным стохастическим алгоритмом является построение быстро исследующего случайного дерева ([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*

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

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