Theta * - это алгоритм планирования пути под любым углом , основанный на алгоритме поиска A * . Он может находить почти оптимальные пути со временем работы, сопоставимым со временем работы A *. [1]
Описание
Для простейшей версии Theta * основной цикл почти такой же, как и у A *. Единственная разница в том, чтофункция. По сравнению с A *, родительский узел узла в Theta * не обязательно должен быть соседом узла, если между двумя узлами существует прямая видимость. [ необходима цитата ]
Псевдокод
Адаптированы из. [2]
function theta * ( start , goal ) // Этот основной цикл совпадает с A * gScore ( start ) : = 0 parent ( start ) : = start // Инициализирует открытые и закрытые наборы. Открытый набор инициализируется // начальным узлом и начальной стоимостью open : = {} open . insert ( start , gScore ( start ) + heuristic ( start )) // gScore (node) - текущее кратчайшее расстояние от начального узла до узла // эвристика (node) - это расчетное расстояние узла от целевого узла // там много вариантов эвристического такой как Евклид или Манхеттен закрыты : = {} , а открытым являются не пустым s : = открыты . pop (), если s = цель, вернуть реконструкцию_путь ( -ы ) закрыто . толчок ( ы ) для каждого соседа по с // Петли через каждый непосредственный сосед с , если соседом не в закрытом , если соседе не в открытых значениях // инициализирует для соседа , если он // уже не в открытом списке gScore ( сосед ) : = бесконечность родитель ( сосед ) : = Null update_vertex ( s , neighbour ) return Null function update_vertex ( s , neighbour ) // Эта часть алгоритма является основным различием между A * и Theta * if line_of_sight ( parent ( s ) , neighbour ) // Если есть линия прямой видимости между родителем (s) и сосед // затем игнорируйте s и используйте путь от родителя (ов) к соседу, если gScore ( parent ( s )) + c ( parent ( s ) , neighbour ) < gScore ( neighbour ) // c (s, сосед) является Евклидово расстояние от s до соседа gScore ( сосед ) : = gScore ( родитель ( и )) + c ( родитель ( и ) , сосед ) родитель ( сосед ) : = родитель ( и ), если сосед в открытом состоянии открыт . удалить ( сосед ) открыть . insert ( сосед , gScore ( сосед ) + эвристика ( сосед )) else // Если длина пути от начала до s и от s до // соседа короче, чем самое короткое известное в настоящее время расстояние // от начала до соседа, тогда обновить узел с новым расстоянием, если gScore ( s ) + c ( s , сосед ) < gScore ( сосед ) gScore ( сосед ) : = gScore ( s ) + c ( s , сосед ) родительский ( сосед ) : = s, если сосед в открытый открытый . удалить ( сосед ) открыть . вставить ( сосед , gScore ( сосед ) + эвристика ( сосед ))function reconstruct_path ( s ) total_path = {s} // Это рекурсивно реконструирует путь от целевого узла // до тех пор, пока не будет достигнут начальный узел, если родитель ( и ) ! = s total_path . push ( reconstruct_path ( parent ( s ))) else return total_path
Варианты
Существуют следующие варианты алгоритма: [ необходима цитата ]
- Lazy Theta * [3] - Расширения узлов задерживаются, что приводит к меньшему количеству проверок прямой видимости.
- Инкрементальный Phi * - модификация Theta *, которая позволяет динамическое планирование пути аналогично D *