Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

D * (произносится как «звезда D») - это любой из трех связанных алгоритмов инкрементного поиска :

  • Оригинальный алгоритм D *, [1] Энтони Стенца, представляет собой алгоритм инкрементного поиска с информацией.
  • Focused D * [2] - это алгоритм инкрементального эвристического поиска, разработанный Энтони Стенцем, который сочетает в себе идеи A * [3] и оригинального D *. Сфокусированный D * возник в результате дальнейшего развития оригинального D *.
  • D * Lite [4] инкрементный эвристический алгоритм поиска по Свена Кёнига и Максим Лихачев , который основывается на МПУ * , [5] инкрементный эвристический алгоритм поиска , который сочетает идеи A * и Dynamic SWSF-FP. [6]

Все три алгоритма поиска решают одни и те же задачи планирования пути на основе предположений , включая планирование с предположением о свободном пространстве, [7]где робот должен перейти к заданным координатам цели на неизвестной местности. Он делает предположения о неизвестной части местности (например, что на ней нет препятствий) и находит кратчайший путь от ее текущих координат до координат цели при этих предположениях. Затем робот следует по пути. Когда он наблюдает новую информацию на карте (например, ранее неизвестные препятствия), он добавляет эту информацию на свою карту и, при необходимости, перепланировывает новый кратчайший путь от текущих координат к заданным координатам цели. Он повторяет процесс до тех пор, пока не достигнет координат цели или не определит, что координаты цели не могут быть достигнуты. При пересечении неизвестной местности могут часто обнаруживаться новые препятствия, поэтому это перепланирование должно быть быстрым. Алгоритмы инкрементального (эвристического) поискаускорить поиск последовательностей похожих поисковых задач, используя опыт решения предыдущих задач, чтобы ускорить поиск текущей. Если предположить, что координаты цели не меняются, все три алгоритма поиска более эффективны, чем повторные поиски A *.

D * и его варианты широко используются для навигации мобильных роботов и автономных транспортных средств . Современные системы обычно основаны на D * Lite, а не на оригинальном D * или Focussed D *. Фактически, даже лаборатория Стенца в некоторых реализациях использует D * Lite, а не D *. [8] Такие навигационные системы включают прототип системы, испытанный на марсоходах Opportunity и Spirit, и навигационную систему победителя конкурса DARPA Urban Challenge , разработанные в Университете Карнеги-Меллона .

Оригинальный D * был представлен Энтони Стенцем в 1994 году. Название D * происходит от термина «Dynamic A *» [9], потому что алгоритм ведет себя как A *, за исключением того, что стоимость дуги может изменяться по мере выполнения алгоритма.

Операция [ править ]

Основная работа D * описана ниже.

Подобно алгоритму Дейкстры и A *, D * поддерживает список узлов для оценки, известный как «ОТКРЫТЫЙ список». Узлы помечаются как имеющие одно из нескольких состояний:

  • НОВИНКА, то есть никогда не помещалась в ОТКРЫТЫЙ список
  • ОТКРЫТЫЙ, то есть в настоящее время в списке ОТКРЫТО.
  • ЗАКРЫТО, то есть его больше нет в списке ОТКРЫТО.
  • ПОДНЯТЬ, указывая на то, что его стоимость выше, чем в последний раз, когда он был в списке ОТКРЫТО.
  • НИЖНИЙ, что указывает на то, что его стоимость ниже, чем в последний раз, когда он был в списке ОТКРЫТО.

Расширение [ править ]

Алгоритм работает путем итеративного выбора узла из списка OPEN и его оценки. Затем он распространяет изменения узла на все соседние узлы и помещает их в список OPEN. Этот процесс распространения называется «расширением». В отличие от канонического A *, который следует по пути от начала до конца, D * начинает поиск в обратном направлении от целевого узла. Каждый расширенный узел имеет обратный указатель, который относится к следующему узлу, ведущему к цели, и каждый узел знает точную стоимость для цели. Когда начальный узел является следующим расширяемым узлом, алгоритм выполнен, и путь к цели можно найти, просто следуя обратным указателям.

  • Расширение в процессе. Финишный узел (желтый) находится в середине верхнего ряда точек, начальный узел находится в середине нижнего ряда. Красный указывает на препятствие; черный / синий обозначает расширенные узлы (яркость обозначает стоимость). Зеленым обозначены узлы, которые расширяются.

  • Расширение завершено. Путь указан голубым цветом.

Преодоление препятствий [ править ]

Когда на заданном пути обнаруживается препятствие, все затронутые точки снова помещаются в список ОТКРЫТО, на этот раз с пометкой ПОДНЯТЬ. Однако перед увеличением стоимости узла RAISED алгоритм проверяет его соседей и проверяет, может ли он снизить стоимость узла. В противном случае состояние RAISE распространяется на все потомки узлов, то есть узлы, на которые есть обратные указатели. Затем эти узлы оцениваются, и состояние RAISE передается, формируя волну. Когда узел RAISED может быть уменьшен, его обратный указатель обновляется и передает состояние LOWER своим соседям. Эти волны состояний RAISE и LOWER являются сердцем D *.

К этому моменту волны не могут «коснуться» целого ряда других точек. Таким образом, алгоритм работал только с точками, на которые влияет изменение стоимости.

  • Было добавлено препятствие (красный) и узлы, отмеченные RAISE (желтый).

  • Расширение в процессе. Желтым цветом обозначены узлы, помеченные RAISE, зеленым - узлы, отмеченные LOWER.

Возникает еще один тупик [ править ]

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

  • Канал заблокирован дополнительными препятствиями (красный)

  • Расширение в процессе (восходящая волна желтым цветом, нижняя волна зеленым)

  • Обнаружен новый путь (голубой)

Псевдокод [ править ]

в то время как  ( ! openList . isEmpty ())  {  point  =  openList . getFirst ();  развернуть ( точка ); }

Развернуть [ изменить ]

недействительное  расширение ( currentPoint )  {  булева  isRaise  =  isRaise ( currentPoint );  двойная  стоимость ;  для  каждого  ( соседа  в  currentPoint . getNeighbors ())  {  если  ( isRaise )  {  если  ( сосед . nextPoint  ==  currentPoint )  {  соседа . setNextPointAndUpdateCost ( currentPoint );  openList .добавить ( сосед );  }  else  {  стоимость  =  сосед . calculateCostVia ( currentPoint );  если  ( стоимость  <  сосед . getCost ())  {  currentPoint . setMinimumCostToCurrentCost ();  openList . добавить ( currentPoint );  }  }  }  еще  {  стоимость  =  сосед . calculateCostVia ( currentPoint );  если  (стоимость  <  сосед . getCost ())  {  сосед . setNextPointAndUpdateCost ( currentPoint );  openList . добавить ( сосед );  }  }  } }

Проверить на повышение [ править ]

логическое  isRaise ( точка )  {  двойная  стоимость ;  if  ( point . getCurrentCost ()  >  point . getMinimumCost ())  {  для  каждого ( соседа  в  точке . getNeighbors ())  {  cost  =  point . CalculCostVia ( сосед );  если  ( стоимость  <  точка . getCurrentCost ())  {  точка .setNextPointAndUpdateCost ( сосед );  }  }  }  точка возврата  . getCurrentCost () > точка . getMinimumCost (); }  

Варианты [ править ]

Сосредоточенный D * [ править ]

Как следует из названия, Focused D * является расширением D *, которое использует эвристику, чтобы сфокусировать распространение RAISE и LOWER в направлении робота. Таким образом, обновляются только важные состояния, так же как A * вычисляет затраты только для некоторых узлов.

D * Lite [ править ]

D * Lite не основан на исходном D * или Focused D *, но реализует то же поведение. Это проще для понимания и может быть реализовано меньшим количеством строк кода, отсюда и название «D * Lite». По производительности он не хуже Focused D *. D * Lite основан на пожизненном планировании A * , который был представлен Кенигом и Лихачевым несколькими годами ранее. D * Lite

Минимальная стоимость по сравнению с текущей стоимостью [ править ]

Для D * важно различать текущие и минимальные затраты. Первый важен только во время сбора, а второй важен, потому что сортирует OpenList. Функция, которая возвращает минимальную стоимость, всегда является самой низкой стоимостью для текущей точки, поскольку это первая запись в OpenList.

Ссылки [ править ]

  1. ^ Стенц, Энтони (1994), «Оптимальное и эффективное планирование пути для частично известных сред», Труды Международной конференции по робототехнике и автоматизации : 3310–3317, CiteSeerX  10.1.1.15.3683
  2. ^ Стенц, Энтони (1995), «Сфокусированный алгоритм D * для перепланирования в реальном времени», Труды Международной совместной конференции по искусственному интеллекту : 1652–1659, CiteSeerX 10.1.1.41.8257 
  3. ^ Hart, P .; Nilsson, N .; Рафаэль Б. (1968), «Формальная основа для эвристического определения путей с минимальной стоимостью», IEEE Trans. Syst. Наука и кибернетики , ССК-4 (2): 100-107, DOI : 10,1109 / TSSC.1968.300136
  4. ^ Koenig, S .; Лихачев, М. (2005), "Fast перепланировки для навигации в незнакомой местности", Операции по робототехнике , 21 (3): 354-363, CiteSeerX 10.1.1.65.5979 , DOI : 10.1109 / tro.2004.838026 
  5. ^ Koenig, S .; Лихачев, М .; Furcy, D. (2004), "Пожизненное планирования A *", Искусственный интеллект , 155 (1-2): 93-146, DOI : 10.1016 / j.artint.2003.12.001
  6. ^ Рамалингам, G .; Репс, Т. (1996), "инкрементный алгоритм обобщения задачи кратчайшего пути", журнал алгоритмов , 21 (2): 267-305, CiteSeerX 10.1.1.3.7926 , DOI : 10,1006 / jagm.1996.0046 
  7. ^ Koenig, S .; Смирнов, Ю .; Тови, C. (2003), "Производительность Bounds для планирования в незнакомой местности", Искусственный интеллект , 147 (1-2): 253-279, DOI : 10.1016 / s0004-3702 (03) 00062-6
  8. ^ Вуден, Д. (2006). Графическое планирование пути для мобильных роботов (дипломная работа). Технологический институт Джорджии.
  9. ^ Стенц, Энтони (1995), «Сфокусированный алгоритм D * для перепланирования в реальном времени», Труды Международной совместной конференции по искусственному интеллекту : 1652–1659, CiteSeerX 10.1.1.41.8257 

Внешние ссылки [ править ]

  • Веб-страница Свена Кенига
  • Веб-страница Энтони Стенца