Войти
D*(произносится как «D-звезда») - это любой из следующих трех связанных алгоритмов инкрементного поиска :
Все три алгоритма поиска решают одни и те же основанные на предположениях задачи планирования пути, включая планирование с допущением о свободном пространстве, когда робот должен перейти к заданным координатам цели на неизвестной местности. Он делает предположения о неизвестной части местности (например, что на ней нет препятствий) и находит кратчайший путь от ее текущих координат до координат цели при этих предположениях. Затем робот следует по пути. Когда он наблюдает новую информацию на карте (например, ранее неизвестные препятствия), он добавляет эту информацию на свою карту и, при необходимости, перепланировывает новый кратчайший путь из текущих координат в заданные координаты цели. Он повторяет процесс до тех пор, пока не достигнет координат цели или не определит, что координаты цели не могут быть достигнуты. При пересечении неизвестной местности могут часто обнаруживаться новые препятствия, поэтому такое перепланирование должно быть быстрым. Алгоритмы инкрементного (эвристического) поиска ускоряют поиск последовательностей схожих поисковых проблем, используя опыт решения предыдущих проблем для ускорения поиска текущей. Если предположить, что координаты цели не меняются, все три алгоритма поиска более эффективны, чем повторные поиски A *.
D * и его варианты широко использовались для мобильного робота и автономного транспортного средства навигации. Современные системы обычно основаны на D * Lite, а не на оригинальном D * или Focussed D *. Фактически, даже лаборатория Стенца в некоторых реализациях использует D * Lite, а не D *. Такие навигационные системы включают в себя прототип системы, испытанный на марсоходах Opportunity и Spirit, а также систему навигации победителя конкурса DARPA Urban Challenge, разработанные в Университет Карнеги-Меллона.
Оригинальный D * был представлен Энтони Стенцем в 1994 году. Название D * происходит от термина «Dynamic A *», потому что алгоритм ведет себя как A *, за исключением того, что стоимость дуги может изменяться как алгоритм работает.
Основная операция D * изложены ниже.
Подобно алгоритму Дейкстры и A *, D * поддерживает список узлов для оценки, известный как «OPEN list». Узлы помечаются как имеющие одно из нескольких состояний:
Алгоритм работает путем итеративного выбора узла из списка OPEN и его оценки. Затем он распространяет изменения узла на все соседние узлы и помещает их в список OPEN. Этот процесс распространения называется «расширением». В отличие от канонического A *, который следует по пути от начала до конца, D * начинает поиск в обратном направлении от целевого узла. Каждый расширенный узел имеет обратный указатель, который относится к следующему узлу, ведущему к цели, и каждый узел знает точную стоимость для цели. Когда начальный узел является следующим расширяемым узлом, алгоритм выполнен, и путь к цели можно найти, просто следуя обратным указателям.
Выполняется расширение. Финишный узел (желтый) находится в середине верхнего ряда точек, начальный узел находится в середине нижнего ряда. Красный цвет указывает на препятствие; черный / синий обозначает расширенные узлы (яркость обозначает стоимость). Зеленым обозначены узлы, которые расширяются.
Расширение завершено. Путь указан голубым цветом.
Когда препятствие обнаруживается на намеченной траектории, все затронутые точки снова помещаются в список ОТКРЫТЬ, на этот раз отмеченные ПОДЪЕМОМ. Однако перед увеличением стоимости узла RAISED алгоритм проверяет его соседей и проверяет, может ли он снизить стоимость узла. В противном случае состояние RAISE распространяется на все потомки узлов, то есть узлы, на которые есть обратные указатели. Затем эти узлы оцениваются, и состояние RAISE передается, формируя волну. Когда узел RAISED может быть уменьшен, его обратный указатель обновляется и передает состояние LOWER своим соседям. Эти волны состояний RAISE и LOWER являются сердцем D *.
К этому моменту волны не могут «коснуться» целого ряда других точек. Следовательно, алгоритм работал только с точками, на которые влияет изменение стоимости.
Было добавлено препятствие (красный) и узлы, отмеченные ПОДЪЕМ (желтый).
Выполняется расширение. Желтым цветом обозначены узлы с меткой RAISE, зеленым - узлы с меткой LOWER.
На этот раз тупик нельзя обойти так элегантно. Ни одна из точек не может найти новый маршрут через соседа к месту назначения. Поэтому они продолжают распространять свое повышение стоимости. Можно найти только точки за пределами канала, которые могут привести к месту назначения по жизнеспособному маршруту. Так развиваются две нижние волны, которые расширяются в виде точек, отмеченных как недостижимые с новой информацией о маршруте.
Канал заблокирован дополнительными препятствиями (красный)
Расширение идет (волна вверх желтым, волна внизу зеленым)
Найден новый путь (голубой)
while (! OpenList.isEmpty ()) {точка = openList.getFirst (); развернуть (точка); }void expand (currentPoint) {логическое isRaise = isRaise (currentPoint); двойная стоимость; для каждого (сосед в currentPoint.getNeighbors ()) {если (isRaise) {если (сосед.nextPoint == currentPoint) {сосед.setNextPointAndUpdateCost (currentPoint); openList.add (сосед); } else {стоимость = neighbour.calculateCostVia (currentPoint); if (cost < neighbor.getCost()) { currentPoint.setMinimumCostToCurrentCost(); openList.add(currentPoint); } } } else { cost = neighbor.calculateCostVia(currentPoint); if (cost < neighbor.getCost()) { neighbor.setNextPointAndUpdateCost(currentPoint); openList.add(neighbor); } } } }логического isRaise (point) {двойная стоимость; if (point.getCurrentCost ()>point.getMinimumCost ()) {для каждого (соседа в point.getNeighbors ()) {cost = point.calculateCostVia (neighbour); if (cost < point.getCurrentCost()) { point.setNextPointAndUpdateCost(neighbor); } } } return point.getCurrentCost()>point.getMinimumCost ();}Как следует из названия, Focused D * является расширением of D *, который использует эвристику для фокусировки распространения RAISE и LOWER к роботу. Таким образом, обновляются только важные состояния, так же как A * вычисляет затраты только для некоторых узлов.
D * Lite не основан на исходном D * или Focused D *, но реализует то же поведение. Его проще понять и его можно реализовать с помощью меньшего количества строк кода, поэтому название "D * Lite". По производительности оно не хуже Focused D *. D * Lite основан на Lifelong Planning A *, который был введен Кенигом и Лихачевым несколько лет назад ранее. D * Lite
Для D * важно различать текущие и минимальные затраты. Первый важен только во время сбора, а второй важен, потому что сортирует OpenList. Функция, которая возвращает минимальную стоимость, всегда является наименьшей стоимостью для текущей точки, поскольку это первая запись в OpenList.
