Изменения

Что нужно, чтобы плавно изменялось расстояние? Евклидово расстояние до невыпуклых многоугольников не обладает необходимыми нам свойствами и плохо дифференцируемо в местах, где возникает отсутствие выпуклости. Поэтому мы можем можно построить такое псевдо расстояние псевдорасстояние по градиентному полю до нашей ломаной, она здесь которая обозначена на ''Рис. 4'' красным и представляет собой препятствие. Мы можем довольно несложно ввести Введем поле расстояний от каждой точки до этой ломаной, которая направлена которое направлено в сторону ломаной и обладает необходимыми свойствами дифференцируемости — пусть и не являясь строго кратчайшейкратчайшим. Если мы все это сделаем — сможем Это позволит построить гладкую, красивую и аккуратную траекторию.

К преимуществам таких методов мы относим то, что получается хорошая траектория и пространство управления непрерывно. Мы можем по нему ехать, все ограничения в той или иной степени соблюдаются. Но к сожалению, большинство оптимизационных методов или даже почти все так или иначе страдают от локальных минимумов, где их попытки что-либо оптимизировать застревают и не находят достаточно хорошего решения. Очень сложно все формулировать в виде математических дифференцируемых функций, это тоже не всегда получается.=== Стохастические алгоритмы === Однако выход есть. Мы можем применить Существуют также стохастические алгоритмы, которые работают некоторым случайным образом, но зато позволяют нам построить какой-то приближенный маршрут достаточно быстро и удобно. Например, мы будем строить наш граф, являющийся деревом, итеративным образом. Вначале ничего делить на клеточки не будем, никаких примитивов строить не будем. Мы просто возьмем симулятор нашей машины, который в целом умеет симулировать движение, максимально похожее на то, как машина едет по-настоящему. И возьмем стартовую точку. После этого итеративно выберем случайную точку в пространстве. И — найдем в текущем построенном дереве ближайший к ней узел. Построим ребро в сторону этой точки с помощью симуляции проезда в эту сторону. Получается, мы каждый раз едем от нашего построенного дерева в случайную сторону и можем вершины в этом дереве делать в пространстве любой размерности, то есть в каждой вершине учитывать текущее направление машины, текущую скорость, ускорение, все углы, которые нам важны. А потом, когда мы возьмем новую точку, то возьмем и ближайшую к этой точке вершину. Проедем с помощью какой-то симуляции, например, 5 метров в сторону этой точки. Затем возьмем другую точку и проедем в ее сторону. Что нам это дает? Мы каждый раз исследуем пространство, но очень агрессивно. Мы не ищем оптимальные способы объехать препятствие. Мы , а просто ездим направляемся в разные стороны, но каждый раз делаем делая это из наиболее исследуемого исследованного участка нашего пространства к той, неизведанной стороненаименее исследованному.

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

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

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