Тета * - Theta*

Тета * является любой угол алгоритм планирования пути это основано на Алгоритм поиска A *. Он может найти почти оптимальные пути со временем работы, сопоставимым со временем работы A *.^[1]

Описание

Для простейшей версии Theta * основной цикл почти такой же, как и у A *. Единственная разница - это ${\displaystyle {\text{update}}\_{\text{vertex}}()}$функция. По сравнению с A *, родительский узел узла в Theta * не обязательно должен быть соседом узла, если между двумя узлами существует прямая видимость.^{[нужна цитата ]}

Псевдокод

Адаптирован из.^[2]

функция тета*(Начните, Цель)    // Этот основной цикл такой же, как A *    gScore(Начните) := 0    родитель(Начните) := Начните    // Инициализация открытых и закрытых наборов. Открытый набор инициализирован     // с начальным узлом и начальной стоимостью    открыто := {}    открыто.вставлять(Начните, gScore(Начните) + эвристический(Начните))    // gScore (узел) - текущее кратчайшее расстояние от начального узла до узла    // эвристика (узел) - расчетное расстояние узла от целевого узла    // есть много вариантов эвристики, например евклидова или манхэттенского     закрыто := {}    пока открыто является нет пустой        s := открыто.поп()        если s = Цель            возвращаться реконструировать_путь(s)        закрыто.толкать(s)        за каждый сосед из s        // Перебираем каждого ближайшего соседа s            если сосед нет в закрыто                если сосед нет в открыто                    // Инициализируем значения для соседа, если он                     // еще нет в открытом списке                    gScore(сосед) := бесконечность                    родитель(сосед) := Ноль                update_vertex(s, сосед)    возвращаться Ноль                функция update_vertex(s, сосед)    // Эта часть алгоритма является основным отличием A * от Theta *    если Поле зрения(родитель(s), сосед)        // Если есть прямая видимость между родителем (ями) и соседом        // затем игнорируем s и используем путь от родителя (ей) к соседу         если gScore(родитель(s)) + c(родитель(s), сосед) < gScore(сосед)            // c (s, сосед) - евклидово расстояние от s до соседа            gScore(сосед) := gScore(родитель(s)) + c(родитель(s), сосед)            родитель(сосед) := родитель(s)            если сосед в открыто                открыто.удалять(сосед)            открыто.вставлять(сосед, gScore(сосед) + эвристический(сосед))    еще        // Если длина пути от начала до s и от s до         // сосед короче самого короткого известного на данный момент расстояния        // от начала до соседа, затем обновляем узел с новым расстоянием        если gScore(s) + c(s, сосед) < gScore(сосед)            gScore(сосед) := gScore(s) + c(s, сосед)            родитель(сосед) := s            если сосед в открыто                открыто.удалять(сосед)            открыто.вставлять(сосед, gScore(сосед) + эвристический(сосед))функция реконструировать_путь(s)    total_path = {s}    // Это рекурсивно восстановит путь от целевого узла     // пока не будет достигнут начальный узел    если родитель(s) != s        total_path.толкать(реконструировать_путь(родитель(s)))    еще        возвращаться total_path

Варианты

Существуют следующие варианты алгоритма:^{[нужна цитата ]}

• Ленивая тета *^[3] - Расширение узлов откладывается, что приводит к меньшему количеству проверок прямой видимости
• Инкрементальный Phi * - модификация Theta *, которая позволяет динамическое планирование пути аналогично D *

Смотрите также

• Планирование траектории под любым углом
• А *

Рекомендации

1. Эмпирическое сравнение алгоритмов планирования пути под любым углом
2. Theta *: Планирование сетки под любым углом
3. http://idm-lab.org/bib/abstracts/papers/aaai10b.pdf