Пошук шляху

Пошук шляху (англ. Pathfinding) — це побудова найкоротшого шляху між двома точками за допомогою комп'ютерної програми. Це практичніший варіант розв'язування лабіринтів. Ця галузь досліджень ґрунтується на алгоритмі Дейкстри для пошуку найкоротшого шляху на зваженому графі.

Однакові шляхи між A та B в 2D середовищі

Задача пошуку шляху тісно пов'язана з задачею про найкоротший шлях у рамках теорії графів, яка розглядає визначення шляху, що найкраще відповідає деяким критеріям (найкоротший, найдешевший, найшвидший і так далі) між двома точками у великій мережі.

Алгоритми

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

Двома основними задачами пошуку шляху є:

1. пошук шляху між двома вузлами на графі;
2. задача про найкоротший шлях — знайти оптимальний найкоротший шлях.

Основні алгоритми, такі як пошук у ширину і пошук у глибину, спрямовані на першу проблему, вичерпуючи всі можливості за допомогою грубого перебору; починаючи з даного вузла, вони ітераційно досліджують усі потенційні шляхи, доки не досягають цільового вузла. Ці алгоритми використовуються за час ${\displaystyle O\left(\left|V\right|+\left|E\right|\right)}$ або лінійний час, де V — кількість вершин, а E — кількість ребер між вершинами.

Більш складною проблемою є пошук оптимального шляху. Вичерпний підхід у даному випадку відомий як алгоритм Беллмана-Форда має часову складність ${\displaystyle O(|V||E|)}$, або квадратичний час. Однак не потрібно вивчати всі можливі шляхи, щоб знайти оптимальний. Алгоритми, такі як алгоритм A* та алгоритм Дейкстри стратегічно виключають шляхи, як за допомогою евристичного алгоритму, так і за допомогою динамічного програмування. Усунувши неможливі шляхи, ці алгоритми можуть досягати низької складності часу, як ${\displaystyle O(|E|\log(|V|))}$.

Наведені вище алгоритми є одними з найкращих загальних алгоритмів, які працюють на графу без попередньої обробки. Проте, в практичних системах маршрутизації шляхів, навіть найкращі за складністю часу, можна досягти за допомогою алгоритмів, які попередньо обробляють граф для досягнення кращої продуктивності. Одним з таких алгоритмів є ^[en].

Алгоритм Дейкстри 

Загальним прикладом алгоритму пошуку шляху базованого на графі є алгоритм Дейкстри. Цей алгоритм розпочинає роботу з початкового вузла й прямує до «відкритих вузлів» — кандидатів. На кожному наступному кроці обирається відкритий вузол з найменшою відстанню від початкового. Усі вузли, позначені як «закриті» та всі прилеглі до них вузли додаються до відкритого набору, якщо вони ще не були перевірені. Цей процес повторюється доки не буде знайдено шлях до потрібного вузла (пункту призначення). Оскільки найчастіше розглядаються вузли з найменшою відстанню, коли вперше буде знайдено пункт призначення — шлях до нього буде найкоротшим шляхом.

Алгоритм Дейкстри не працює з показниками від'ємної ваги. У гіпотетичній ситуації коли вузли А, В і С утворюють зв'язаний неорієнтований граф з ребрами  АВ = 3, АС = 4, та ВС = -2, оптимальний шлях від А до С коштує 1, а оптимальний шлях від A до B витратить 2. Алгоритм Дейкстри починає з А, а потім  спочатку розглядає  вузол B, оскільки він розташований найближче. Цей шлях буде коштувати  3  і буде позначений як «закритий», а значить, його вартість ніколи не буде переоцінена. Це i є причиною того, чому алгоритм Дейкстри не може оцінити показники від'ємної ваги. Проте, оскільки для багатьох практичних цілей ніколи не буде показників від'ємної ваги, алгоритм Дейкстера в значній мірі підходить для задач на пошук шляхів.

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

Алгоритм А* — це варіант алгоритму Дейкстри, який досить часто використовується в іграх. A* придає вагу кожному відкритому вузлу, вага якого дорівнює вазі ребра та додає приблизну відстань від ребра до фінішу. Ця приблизна відстань виявляється евристичною і являє собою мінімальну можливу відстань між цим вузлом і кінцем. Це дозволяє алгоритму усунути довші шляхи після виявлення початкового і працює наступним чином: якщо між початком і кінцем є шлях довжини X, а мінімальна відстань між вузлом і фінішем перевищує X, то цей вузол не потрібно перевіряти далі.

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

Алгоритм вибірки

Алгоритм вибірки - це досить простий і зрозумілий алгоритм пошуку шляху для мап на основі черепиці. Щоб почати, у вас є карта, початкова координата та координата призначення. Карта буде виглядати так: X — це стінка, S — це початок, O — фініш, _ відкриті простори, цифри вздовж верхніх і правих країв — це номери стовпців та рядків:

 1 2 3 4 5 6 7 8 X X X X X X X X X X X _ _ _ X X _ X _ X 1 X _ X _ _ X _ _ _ X 2 X S X X _ _ _ X _ X 3 X _ X _ _ X _ _ _ X 4 X _ _ _ X X _ X _ X 5 X _ X _ _ X _ X _ X 6 X _ X X _ _ _ X _ X 7 X _ _ O _ X _ _ _ X 8 X X X X X X X X X X 

Спочатку створимо список координат, який ми будемо використовувати як чергу. Черга буде ініціалізована однією координатою, кінцевою координатою. Кожна координата також матиме змінній лічильник (мета цього скоро стане очевидною). Таким чином, черга починається з ((3,8,0)).

Потім переходимо до кожного елемента в черзі, включаючи елементи, додані до кінця по ходу алгоритму, і до кожного елемента, виконуємо наступне:

1. Створюємо список із чотирьох сусідніх комірок зі змінною лічильником змінної поточного елемента +1 (у нашому прикладі чотири комірки — це ((2,8,1), (3,7,1), (4,8,1), (3,9,1)))
2. Перевіряємо всі клітинки в кожному списку для наступних двох умов:
   1. Якщо клітина є стінкою, видаляємо її зі списку
   2. Якщо в головному списку є елемент з тією ж координатою та лічильник менший або рівний, видаляємо його з списку комірок
3. Додаємо всі інші комірки у список до кінця основного списку
4. Переходимо до наступного елемента списку

Таким чином, після першого повороту, список елементів буде таким: ((3,8,0),(2,8,1),(4,8,1))

• Після 2 поворотів: ((3,8,0), (2,8,1), (4,8,1), (1,8,2), (4,7,2))
• Після 3 поворотів: (… (1,7,3), (4,6,3), (5,7,3))
• Після 4 поворотів: (… (1,6,4), (3,6,4), (6,7,4))
• Після 5 поворотів: (… (1,5,5), (3,5,5), (6,6,5), (6,8,5))
• Після 6 витків: (… (1,4,6), (2,5,6), (3,4,6), (6,6,6), (7,8,6))
• Після 7 поворотів: ((1,3,7)) — задача розв'язана, закінчимо цей етап алгоритму — зверніть увагу, що якщо у вас є декілька одиниць, що переслідують ту саму ціль (як і в багатьох іграх — закінчення, щоб почати підхід алгоритму щоб зробити це простішим), ви можете продовжувати, доки не буде покрито всю карту, досягнуто всіх одиниць або досягнуто обмеження лічильника.

Тепер мапа лічильників виглядає так:

 1 2 3 4 5 6 7 8 X X X X X X X X X X X _ _ _ X X _ X _ X 1 X _ X _ _ X _ _ _ X 2 X S X X _ _ _ X _ X 3 X 6 X 6 _ X _ _ _ X 4 X 5 6 5 X X 6 X _ X 5 X 4 X 4 3 X 5 X _ X 6 X 3 X X 2 3 4 X _ X 7 X 2 1 0 1 X 5 6 _ X 8 X X X X X X X X X X 

Тепер почніть з S (7) і перейдіть до найближчої комірки з найменшим числом (неперевірені клітинки не можна перемістити). Простежується шлях (1,3,7) -> (1,4,6) -> (1,5,5) -> (1,6,4) -> (1,7,3) -> (1,8,2) -> (2,8,1) -> (3,8,0). У випадку, якщо два числа однаково низькі (наприклад, якщо S був на рівні (2,5)), виберіть випадковий напрямок — довжини однакові. Алгоритм завершено.

У відеоіграх

^[en] в 1982 році описав, як він «витратив багато часу», намагаючись вирішити проблему з пошуком шляхів у Tanktics (комп'ютерна гра), в якій комп'ютерні танки потрапили в пастку на суші в U-образних озерах. «Після довгих витрачених зусиль я виявив краще рішення: видалити U-образні озера з карти», сказав він.

Ієрархічний пошук шляху

Дерево квадрантів можна використовувати для ієрархічного пошуку шляху

Ідея була вперше представлена в відеоігровій індустрії, що має потребує проєктування на великих картах при незначних витратах процесорного часу. Концепція використання абстракції та евристики є давнішою та вперше згадується під назвою ABSTRIPS (Abstraction-Based STRIPS), яка використовувалася для ефективного пошуку стану просторів логічних ігор. Подібною технікою є навігаційні сітки (navmesh), які використовуються для геометричного планування в відеоіграх і мультимодальному ^[en], яке використовується в задачах комівояжера з більш ніж одним транспортним засобом.

Мапа розділена на кластери. На верхньому рівні планується шлях між кластерами. Після того, як план знайдено, планується другий шлях у кластері на нижньому рівні. Це означає, що планування виконується у два етапи, тобто ^[en] у вихідному просторі. Перевагою є покращення виконуваного алгоритму за рахунок зменшення кількості вершин. Недоліком є те, що даний меанізм доволі важко реалізувати.

Приклад

Карта має розмір 3000x2000 вершин. Планування шляху на основі вершин займе дуже багато часу. Навіть ефективний алгоритм потребує обчислення багатьох можливих графіків. Причина в тому, що така карта міститиме 6 мільйонів вершин, а можливості для дослідження геометричного простору надзвичайно великі. Першим кроком для планування ієрархічного шляху є розділення карти на менші підкарти. Кожен кластер має розмір 300x200 вершин. Загальна кількість кластерів 10x10=100. У щойно створеному графі кількість вершин невелика і є можливість переміщатися між 100 кластерами, але не в межах детальної карти. Якщо в графі високого рівня знайдено дійсний шлях, наступним кроком є планування шляху в кожному кластері. Підкарта має 300x200 вершин, які можуть бути легко оброблені звичайним алгоритмом пошуку A*.

Алгоритми, які використовуються для пошуку шляхів

• Алгоритм пошуку A*
• Алгоритм Дейкстри, особливий випадок алгоритму A*
• Алгоритм пошуку D* сімейство ^[en] для проблем/задач, в яких обмеження змінюються з плином часу або невідомі, коли агент спочатку планує свій шлях
• ^[en] — це сім'я алгоритмів для планування шляхів, які не обмежуються рухатися уздовж країв у графічному пошуковому рядку, розроблені таким чином, щоб мати можливість приймати будь-який кут і таким чином знаходити більш короткі і прямі шляхи

Багатоагентний пошук шляху

Багатоагентний пошук шляху — це пошук шляху для декількох агентів з їх поточних розташувань до цільових місць, не стикаючись один з одним, одночасно оптимізуючи функцію витрат, таку як сума довжин шляху всіх агентів. Це узагальнення пошуку шляху. Багато алгоритмів мультиагентного пошуку шляхів генеровані від A* або базуються на скороченні до інших добре вивчених задач, таких як спрямоване лінійне програмування. Однак, такі алгоритми, як правило є неповні; Іншими словами, не доведено, що вони дають розв'язок протягом поліноміального часу. Інша категорія алгоритмів жертвує оптимальністю заради продуктивності за рахунок використання відомих навігаційних систем (таких як, потік трафіку) або топологією проблемного простору.

Див. також 

• Планування руху
• ^[en]

Список використаної літератури

1. http://lcm.csa.iisc.ernet.in/dsa/node162.html
2. Delling, D.; ; Schultes, D.; (2009). Engineering route planning algorithms. Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation. Springer. с. 117—139. doi:10.1007/978-3-642-02094-0_7.
3. http://students.ceid.upatras.gr/~papagel/project/kef5_7_1.htm
4. http://www.raywenderlich.com/4946/introduction-to-a-pathfinding
5. Crawford, Chris (December 1982). Design Techniques and Ideas for Computer Games. BYTE. с. 96. Процитовано 19 October 2013.
6. Sacerdoti, Earl D (1974). Planning in a hierarchy of abstraction spaces (PDF). Artificial Intelligence. doi:10.1016/0004-3702(74)90026-5.
7. Robert C. Holte; M.B. Perez; R.M. Zimmer; A.J. MacDonald (1995). Symposium on Abstraction, Reformulation, and Approximation.
8. Pelechano, Nuria; Fuentes, Carlos (2016). Hierarchical path-finding for Navigation Meshes (HNA⁎) (PDF) (вид. Computers & Graphics). с. 68—78. doi:10.1016/j.cag.2016.05.023.
9. Botea, Adi; Muller, Martin; Schaeffer, Jonathan (2004). Near optimal hierarchical path-finding (вид. Journal of Game Development). 10.1.1.479.4675.
10. Hang Ma, Sven Koenig, Nora Ayanian, Liron Cohen, Wolfgang Hoenig, T. K. Satish Kumar, Tansel Uras, Hong Xu, Craig Tovey, and Guni Sharon. Overview: generalizations of multi-agent path finding to real-world scenarios. [ 2021-07-15 у Wayback Machine.] In the 25th International Joint Conference on Artificial Intelligence (IJCAI) Workshop on Multi-Agent Path Finding. 2016.
11. Khorshid, Mokhtar (2011). . SOCS. Архів оригіналу за 2 грудня 2017. Процитовано 2 грудня 2017.

Посилання

• http://sourceforge.net/projects/argorha
• http://qiao.github.com/PathFinding.js/visual/
• StraightEdge Відкриття вихідного Java 2D шляху пошуку (використовуючи A *) та проектування освітлення. Включає демонстрацію аплетів.
• python-pathfinding Відкритий вихідний шлях Python 2D (використовуючи алгоритм Дейкстри) та проект освітлення.
• Daedalus Lib Відкрите джерело. Daedalus Lib керує повністю динамічним триангульованим моделюванням 2D середовища та розробкою шляхів через алгоритм A * алгоритми воронки.