Определение направления пути в D*Lite

В настоящее время я работаю над реализацией алгоритма D*Lite от Свена Кенига. http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf . В основном я пытаюсь понять все детали, прежде чем приступить к реализации. Кажется, что алгоритм работает на ориентированных графах, так определяются функции Pred и Succ.

Как определить направление графиков и какие параметры определяют направление графиков. Должен ли я использовать значение некоторого параметра, такого как стоимость g (что не кажется хорошим выбором... так как стоимость g вместе со значением rhs обновляется алгоритмом) или эвристическую оценку расстояния?


algorithm path-finding directed-graph d-star
person Ned112    schedule 06.04.2012    source источник

Ответы (1)


arrow_upward
0
arrow_downward

D* и D*-lite будут работать как с ориентированными, так и с неориентированными графами.

Граф — это G = (V, E), где V — это список доступных конфигураций (или состояний). E — это список соединений между вершинами. В ориентированном графе E — это набор ребер, которые являются упорядоченными парами (u, v), где u и v являются вершинами. В неориентированном графе E — это набор неупорядоченных пар.

Планирование на неориентированном графе эквивалентно планированию на ориентированном графе с двунаправленным ребром. То есть, если (u,v) является ребром, (v, u) также будет ребром.

То, как вы строите графики, зависит от приложения и варьируется от простых сеток до гораздо более сложных стратегий, таких как приближение решетки к прямой кинематике.

person Andrew Walker    schedule 06.04.2012
comment
Да, хорошо, у меня совершенно ясная разница между ориентированным и неориентированным графом. Но мой вопрос был более конкретным: как мне определить направление графика на DLite для обычного планирования пути (то есть направление 8 ячеек)? Вы имеете в виду, что это решение зависит от меня и не подразумевается каким-то образом в самом алгоритме? Второй вопрос: действительно ли DLite работает даже на неориентированном графе, поэтому Succ=Pred?? Благодарю вас - person Ned112; 06.04.2012
comment
Да, вы правы, существует ли край, зависит от приложения. Например, в восьмисвязной сетке вы обычно знаете, где находится центр каждой ячейки сетки. Вы можете использовать векторную математику для расчета расстояния от каждой ячейки до каждой из pred или succ ячеек. Разрешить только ребра, которые не начинаются и не заканчиваются препятствием. Это помогает? - person Andrew Walker; 06.04.2012
comment
Да, succ может быть эквивалентно pred, и так происходит во многих простых графах (включая восемь связанных сеток). - person Andrew Walker; 06.04.2012
comment
Спасибо, это действительно очень помогает! - person Ned112; 06.04.2012