Д*
D* (произносится как «D звезда») — это любой из следующих трех связанных алгоритмов инкрементного поиска :
- Оригинальный Д*, [1] Энтони Стенц — это информированный алгоритм инкрементального поиска.
- Сосредоточенный Д* [2] — это информированный инкрементальный эвристический алгоритм поиска Энтони Стенца, который сочетает в себе идеи A* [3] и оригинальный D*. Сфокусированный D* стал результатом дальнейшего развития исходного D*.
- Д* Лайт [4] — это инкрементальный эвристический алгоритм поиска, разработанный Свеном Кенигом и Максимом Лихачевым, основанный на LPA* , [5] инкрементный эвристический алгоритм поиска, сочетающий в себе идеи A* и Dynamic SWSF-FP. [6]
на основе предположений Все три алгоритма поиска решают одни и те же проблемы планирования пути , включая планирование с предположением о свободном пространстве. [7] где робот должен перейти к заданным координатам цели на неизвестной местности. Он делает предположения о неизвестной части местности (например: что она не содержит препятствий) и находит кратчайший путь от своих текущих координат до координат цели при этих предположениях. Затем робот следует по пути. Когда он наблюдает новую информацию о карте (например, ранее неизвестные препятствия), он добавляет эту информацию на свою карту и, при необходимости, перепланирует новый кратчайший путь от своих текущих координат до заданных координат цели. Он повторяет процесс до тех пор, пока не достигнет целевых координат или не определит, что целевые координаты не могут быть достигнуты. При пересечении неизвестной местности часто могут обнаруживаться новые препятствия, поэтому перепланирование должно быть быстрым. Алгоритмы инкрементного (эвристического) поиска ускоряют поиск последовательностей похожих задач поиска, используя опыт решения предыдущих задач для ускорения поиска текущей. Если предположить, что координаты цели не меняются, все три алгоритма поиска более эффективны, чем повторные поиски A*.
D* и его варианты широко используются для мобильных роботов и автономных транспортных средств навигации . Текущие системы обычно основаны на D* Lite, а не на оригинальном D* или Focused D*. Фактически, даже лаборатория Стенца в некоторых реализациях использует D* Lite, а не D*. [8] К числу таких навигационных систем относятся прототип системы, испытанный на марсоходах Opportunity и Spirit, а также навигационная система победителя конкурса DARPA Urban Challenge , разработанные в Университете Карнеги-Меллон .
Оригинальный D* был представлен Энтони Стенцем в 1994 году. Название D* происходит от термина «Dynamic A*», [9] поскольку алгоритм ведет себя как A*, за исключением того, что стоимость дуги может меняться во время работы алгоритма.
Операция
[ редактировать ]Основные операции D* описаны ниже.
Подобно алгоритму Дейкстры и A*, D* поддерживает список узлов, подлежащих оценке, известный как «ОТКРЫТЫЙ список». Узлы помечаются как имеющие одно из нескольких состояний:
- НОВЫЙ, что означает, что он никогда не был помещен в список ОТКРЫТЫЙ.
- ОТКРЫТО, что означает, что в настоящее время оно находится в списке ОТКРЫТО.
- ЗАКРЫТО, то есть его больше нет в списке ОТКРЫТЫХ.
- ПОДНЯТЬ, указывая, что его стоимость выше, чем в прошлый раз, когда он был в списке ОТКРЫТЫЙ.
- НИЖЕ, что указывает на то, что его стоимость ниже, чем в прошлый раз, когда он был в ОТКРЫТОМ списке.
Расширение
[ редактировать ]Алгоритм работает путем итеративного выбора узла из списка OPEN и его оценки. Затем он распространяет изменения узла на все соседние узлы и помещает их в список OPEN. Этот процесс распространения называется «расширением». В отличие от канонического A*, который следует по пути от начала до конца, D* начинает с поиска назад от целевого узла. Это означает, что алгоритм фактически вычисляет оптимальный путь A* для каждого возможного начального узла. [10] Каждый расширенный узел имеет обратный указатель, который ссылается на следующий узел, ведущий к цели, и каждый узел знает точную стоимость достижения цели. Когда начальный узел является следующим узлом, который будет расширен, алгоритм завершен, и путь к цели можно найти, просто следуя обратным указателям.
Расширение в процессе. Финишный узел (желтый) находится в середине верхнего ряда точек, стартовый узел — в середине нижнего ряда. Красный указывает на препятствие; черный/синий указывает на расширенные узлы (яркость указывает на стоимость). Зеленый цвет указывает на узлы, которые расширяются.
Расширение завершено. Путь указан голубым цветом.
Обработка препятствий
[ редактировать ]При обнаружении препятствия на намеченном пути все затронутые точки снова помещаются в список ОТКРЫТЬ, на этот раз с пометкой ПОДНЯТЬ. Однако прежде чем стоимость узла RAISED увеличится, алгоритм проверяет его соседей и проверяет, может ли он снизить стоимость узла. В противном случае состояние RAISE распространяется на всех потомков узлов, то есть узлов, имеющих на него обратные указатели. Затем эти узлы оцениваются, и состояние RAISE передается дальше, образуя волну. Когда узел RAISED может быть уменьшен, его обратный указатель обновляется и передает состояние LOWER своим соседям. Эти волны состояний ПОДНЯТЬ и ПОНИЖИТЬ являются сердцем D*.
К этому моменту целый ряд других точек не может быть «затронут» волнами. Таким образом, алгоритм работал только с теми точками, на которые повлияло изменение стоимости.
Добавлено препятствие (красное), а узлы отмечены ПОДНИМАНИЕ (желтым).
Расширение в процессе. Желтый цвет обозначает узлы с пометкой ПОДНЯТЬ, зеленый — узлы с пометкой НИЖЕ.
Возникает очередной тупик
[ редактировать ]На этот раз тупик не удастся обойти столь элегантно. Ни одна из точек не может найти новый маршрут через соседа к пункту назначения. Поэтому они продолжают пропагандировать свое повышение стоимости. Можно найти только точки за пределами канала, которые могут привести к месту назначения по жизнеспособному маршруту. Так развиваются две Нижние волны, которые расширяются в виде точек, отмеченных как недостижимые с новой информацией о маршруте.
Канал заблокирован дополнительными препятствиями (красный)
Идет расширение (волна подъема выделена желтым цветом, волна понижения выделена зеленым цветом)
Найден новый путь (голубой)
Псевдокод
[ редактировать ]в то время как ( ! openList . isEmpty ()) { точка = openList . ПолучитьПервый (); расширить ( точку ); } Расширять
[ редактировать ]void расширить ( currentPoint ) { логическое значение isRaise = isRaise ( currentPoint ); двойная стоимость ; для каждого ( сосед в currentPoint . getNeighbors ()) { if ( isRaise ) { if ( сосед . nextPoint == currentPoint ) { neighborhood . setNextPointAndUpdateCost ( currentPoint ); открытый список . добавить ( сосед ); } Еще { стоимость = сосед . вычислитьCostVia ( currentPoint ); если ( стоимость < сосед . getCost ()) { currentPoint . setMinimumCostToCurrentCost (); открытый список . добавить ( currentPoint ); } } } Еще { стоимость = сосед . вычислитьCostVia ( currentPoint ); если ( стоимость < сосед . getCost ()) { сосед . setNextPointAndUpdateCost ( currentPoint ); открытый список . добавить ( сосед ); } } } } Проверить повышение
[ редактировать ]логическое значение isRaise ( point ) { двойная стоимость ; if ( point . getCurrentCost () > point . getMinimumCost ()) { для каждого ( соседа в point . getNeighbours ()) { cost = point . вычислитьCostVia ( сосед ); если ( стоимость < точка . getCurrentCost ()) { точка . setNextPointAndUpdateCost ( сосед ); } } } возврата точка . getCurrentCost () > точка . ПолучитьМинимальнуюСтоимость (); } Варианты
[ редактировать ]Сосредоточенный Д*
[ редактировать ]Как следует из названия, Focused D* является расширением D*, которое использует эвристику для фокусировки распространения команд RAISE и LOWER в сторону робота. Таким образом, обновляются только те состояния, которые имеют значение, точно так же, как A* вычисляет затраты только для некоторых узлов.
Д* Лайт
[ редактировать ]D* Lite не основан на исходном D* или Focused D*, но реализует то же поведение. Его проще понять и можно реализовать с помощью меньшего количества строк кода, отсюда и название «D* Lite». С точки зрения производительности он не уступает Focused D* или даже превосходит его. D* Lite основан на Lifelong Planning A* , который был представлен Кенигом и Лихачевым несколькими годами ранее. Д* Лайт
Минимальная стоимость по сравнению с текущей стоимостью
[ редактировать ]Для D* важно различать текущие и минимальные затраты. Первое важно только во время сбора, а второе критично, поскольку оно сортирует OpenList. Функция, возвращающая минимальную стоимость, всегда является самой низкой стоимостью для текущей точки, поскольку это первая запись в OpenList.
Ссылки
[ редактировать ]- ^ Стенц, Энтони (1994), «Оптимальное и эффективное планирование пути для частично известных сред», Материалы Международной конференции по робототехнике и автоматизации : 3310–3317, CiteSeerX 10.1.1.15.3683
- ^ Стенц, Энтони (1995), «Сфокусированный алгоритм D * для перепланирования в реальном времени», Труды Международной совместной конференции по искусственному интеллекту : 1652–1659, CiteSeerX 10.1.1.41.8257
- ^ Харт, П.; Нильссон, Н.; Рафаэль, Б. (1968), «Формальная основа эвристического определения путей с минимальной стоимостью», IEEE Transactions on Systems Science and Cybernetics , SSC-4 (2): 100–107, doi : 10.1109/TSSC.1968.300136
- ^ Кениг, С.; Лихачев, М. (2005), «Быстрое перепланирование навигации по неизвестной местности», IEEE Transactions on Robotics , 21 (3): 354–363, CiteSeerX 10.1.1.65.5979 , doi : 10.1109/tro.2004.838026 , S2CID 15664344
- ^ Кениг, С.; Лихачев М.; Фурси, Д. (2004), «Планирование на протяжении всей жизни A *», Искусственный интеллект , 155 (1–2): 93–146, doi : 10.1016/j.artint.2003.12.001
- ^ Рамалингам, Г.; Репс, Т. (1996), «Пошаговый алгоритм для обобщения задачи поиска кратчайшего пути», Journal of Algorithms , 21 (2): 267–305, CiteSeerX 10.1.1.3.7926 , doi : 10.1006/jagm.1996.0046
- ^ Кениг, С.; Смирнов Ю.; Тови, К. (2003), «Границы производительности планирования в неизвестной местности», Искусственный интеллект , 147 (1–2): 253–279, doi : 10.1016/s0004-3702(03)00062-6
- ^ Вуден, Д. (2006). Планирование пути для мобильных роботов на основе графов (Диссертация). Технологический институт Джорджии.
- ^ Стенц, Энтони (1995), «Сфокусированный алгоритм D * для перепланирования в реальном времени», Труды Международной совместной конференции по искусственному интеллекту : 1652–1659, CiteSeerX 10.1.1.41.8257
- ^ Мерфи, Робин Р. (2019). Введение в робототехнику искусственного интеллекта (2-е изд.). Брэдфорд Книги. Пункт 14.5.2. ISBN 978-0262038485 .