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