Алгоритм пошуку D*

D* - може відноситись до одного з трьох наступних алгоритмів пошуку:

Оригінальний D*, написаний Ентоні Стенцом, який є евристичним алгоритмом.
Цілеспрямований D* (en. Focused D*) - евристичний алгоритм розроблений Ентоні Стенцом. Він поєднує ідеї A* і оригінального D*. Алгоритм з'явився як результат подальшого розвитку оригінального D*.
Легкий D* (en. D* Lite) - розроблений Свеном Кьонігом та Максимом Ліхачовим евристичний алгоритм, який побудований на основі LPA* - алгоритмі, який поєднує ідеї А* та динамічного пошуку найкоротшого шляху з однієї вершини(en. Dynamic SWSF-FP).

Призначення ред.

Всі три алгоритми вирішують те ж саме завдання - планування шляху на основі припущення, включно з задачею, де роботу необхідно дістатися, до цілі з заданими координатами по невідомому ландшафту.

Принцип роботи ред.

Алгоритм виконує припущення щодо невідомої частини ландшафту (наприклад, що на ній не міститься жодних перешкод і знаходить найкоротший шлях від поточного місцезнаходження до цільових координат на основі цих припущень. Тоді робот слідує шляху. Коли він отримує нову інформацію про ландшафт(як наприклад про попередньо невідому перешкоду), то додає нову інформацію до карти і, якщо необхідно, прокладає новий шлях від поточного місцезнаходження до цілі. Він повторює даний процес поки не досягає цілі або поки не визначить, що добратись до неї неможливо. Оскільки при переміщенні по ландшафту, виявлення нових перешкод - доволі часте явище, то прокладання нового шляху мусить відбуватися швидко. Евристичний алгоритм пришвидшує пошук для послідовності подібних завдань, використовуючи досвід з попередніх для пришвидшення виконання даного. Припустимо координати пункту призначення не змінюються, тоді всі три вищезгадані алгоритми працюватимуть швидше ніж повторний А*.

Використання ред.

D* і його варіанти широко використовуються для мобільних ботів і автономної навігації в автомобілях. Поточні системи зазвичай засновані на легкому D*. Насправді, навіть у лабораторії Стенца для деяких завдань частіше використовують легкий D*, ніж оригінальну версію алгоритму. Для прикладу навігаційні системи прототипів марсоходів Opportunity і Spirit використовують даний алгоритм.

Операції ред.

Опис операцій виконуваних алгоритмом описаний нижче.

Як алгоритм Дейкстри чи A*, D* зберігає список вузлів, які слід оцінити (так званий відкритий список (en. Open list)). Кожен вузол може перебувати в одному з наступних станів:

Новий, тобто він ніколи не був вписаний у відкритий список.
Відкритий, тобто він зараз перебуває у відкритому списку.
Закритий, тобто він більше не перебуває у відкритому списку.
Підвищений, тобто його ціна(вага) більша ніж останній раз, коли він перебував у відкритому списку.
Понижений, тобто його ціна(вага) менша ніж останній раз, коли він перебував у відкритому списку.

Розширення ред.

Алгоритм працює шляхом ітеративного вибору вузла з відкритого списку та його оцінки. Потім він поширює зміни елементи вузла для всіх сусідніх вузлів і поміщає їх у відкритий список. Цей процес поширення називається "розширення". На відміну від A*, який йде по шляху від початку до кінця, D* починається з пошуку в зворотному напрямку від цільового(кінцевого) вузла. Кожен розширений вузол має зворотний вказівник, який посилається на наступний вузол, веде до мети, і кожен вузол знає точну вартість до мети. Коли початковий вузол є наступним вузлом, який буде розширено, тоді алгоритм виконав своє завдання і шлях до мети можна знайти просто дотримуючись зворотних вказівників.

Обробка перешкод ред.

Коли уздовж наміченого шляху виявляється перешкода, всі вузли, на які це впливає знову поміщаються у відкритому списку, проте позначаються як підвищені. Перед підняттям вузол збільшується у вартості, однак, алгоритм перевіряє сусідні вузли і розглядає, чи може він знизити вартість вузла. Якщо ні, то стан підйом поширюється на всі нащадки вузла, тобто вузли, які мають зворотних вказівник на нього. Ці вузли потім оцінюються, і стан ПІДЙОМ передається, формуючи хвилю. Коли піднятий вузол може бути зменшено, його зворотний вказівник оновлюється, і передає стан понижений для своїх сусідів. Ці хвилі підйому та опускання стану є основою D*.

Цілеспрямований D* ред.

Цей алгоритм є розширенням D*, яке використовує евристику для поширення хвиль підвищення і пониження станів у сторону робота(поточного положення). Проте у цьому випадку оновлюються лише ті вузли, які мають значення для знаходження шляху, аналогічно до того, як при виконанні А* обраховується ціна лише деяких вузлів.

Легкий D* ред.

Даний алгоритм не ґрунтується на оригінальному чи цілеспрямованому D*, але при виконанні має подібну поведінку. Легкий D* легше зрозуміти, алгоритм можна запрограмувати у мешній кількості коду, звідси і назва. Стосовно продуктивності, то він такий самий або кращий(залежно від конкретної задачі) за Цілеспрямований D*. Легкий D* ґрунтується на алгоритмі LPA* [Архівовано 18 травня 2014 у Wayback Machine.](Lifelong Planning A*), котрий був запропонований Кьонігом та Ліхачовим декілька років раніше.

D* Lite.

Див. також ред.

Джерела ред.

Stentz, Anthony (1994), "Optimal and Efficient Path Planning for Partially-Known Environments" [Архівовано 18 травня 2014 у Wayback Machine.]
Stentz, Anthony (1995), "The Focussed D* Algorithm for Real-Time Replanning [Архівовано 18 травня 2014 у Wayback Machine.]
P. Hart, N. Nilsson and B. Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Trans. Syst. Science and Cybernetics, SSC-4(2), 100–107, 1968.
S. Koenig and M. Likhachev. Fast Replanning for Navigation in Unknown Terrain. Transactions on Robotics, 21, (3), 354–363, 2005.
S. Koenig, M. Likhachev and D. Furcy. Lifelong Planning A*. Artificial Intelligence Journal, 155, (1–2), 93–146, 2004.
G. Ramalingam, T. Reps, An incremental algorithm for a generalization of the shortest-path problem, Journal of Algorithms 21 (1996) 267–305.
S. Koenig, Y. Smirnov and C. Tovey. Performance Bounds for Planning in Unknown Terrain. Artificial Intelligence Journal, 147, (1–2), 253–279, 2003.
D. Wooden, Graph-based Path Planning for Mobile Robots, Dissertation, Georgia Institute of Technology, 2006.