Алгоритм поиска D*

Алгоритм поиска D* (произносится как «Ди стар») — это любой из трёх связанных : * Оригинальный алгоритм D* Энтони Стенца — это информированный алгоритм инкрементного поиска. * Сфокусированный D* — это алгоритм инкрементного эвристического поиска, разработанный Энтони Стенцем, который сочетает в себе идеи A* и оригинального D*. Сфокусированный D* возник в результате дальнейшего развития оригинального D*. * Облегчённый D* — это алгоритм инкрементального эвристического поиска, созданный Свеном Кёнигом и Максимом Лихачёвым, который основан на LPA*, алгоритме инкрементального эвристического поиска, объединяющем идеи алгоритма поиска A* и динамического SWSF-FP. Все три алгоритма поиска решают одни и те же основанные на предположениях проблемы, включая планирование с предположением о свободном пространстве, когда робот должен перемещаться к заданным координатам цели на неизвестной местности. Он делает предположения о неизвестной части местности (например, что на ней нет препятствий) и находит кратчайший путь от её текущих координат до координат цели при этих предположениях. Затем робот следует по пути. Когда он наблюдает новую информацию на карте (например, ранее неизвестные препятствия), он добавляет эту информацию на свою карту и, при необходимости, перепланировывает новый кратчайший путь от текущих координат к заданным координатам цели. Он повторяет процесс до тех пор, пока не достигнет координат цели или не определит, что координаты цели не могут быть достигнуты. При пересечении неизвестной местности могут часто обнаруживаться новые препятствия, поэтому это перепланирование должно быть быстрым. Инкрементальные (эвристические) алгоритмы поиска ускоряют поиск последовательностей похожих поисковых задач, используя опыт решения предыдущих проблем для ускорения поиска текущей. Если предположить, что координаты цели не меняются, все три алгоритма поиска более эффективны, чем повторные поиски A*. D* и его варианты широко использовались для мобильного робота и автономного транспортного средства навигации. Современные системы обычно основаны на облегчённом, а не на оригинальном или сфокусированном D*. Фактически, даже лаборатория Стенца в некоторых реализациях использует облегчённый, а не оригинальный D*. Такие навигационные системы включают в себя прототип системы, испытанный на марсоходах Opportunity и Spirit, и навигационную систему победителя конкурса DARPA Urban Challenge, оба разработанные в Университете Карнеги — Меллона. Оригинальный D* был представлен Энтони Стенцем в 1994 году. Название D* происходит от термина «Dynamic A*» (рус. «Динамический A*»), потому что алгоритм ведёт себя как A*, за исключением того, что стоимость дуги может изменяться по мере выполнения алгоритма.