🤖 Планувальник Шляхів Складських Роботів — A* Наживо

A* — це алгоритм пошуку в графі "найкращий-перший", що знаходить найкоротший шлях між двома вузлами, розширюючи вузол із найнижчим балом f = g + h, де g — точна пройдена вартість, а h — евристична оцінка залишкової вартості до цілі. На відміну від алгоритму Дейкстри, який досліджує рівномірно в усіх напрямках, A* спрямовується до цілі своєю евристикою, тож зазвичай досліджує набагато менше вузлів, при цьому все ще гарантуючи найкоротший шлях, коли евристика ніколи не перевищує справжню вартість. Складські роботи використовують точно цей компроміс: сіткове представлення проходів між стелажами, швидку евристику (манхеттенська відстань, оскільки рух обмежений чотирма напрямками) і чергу з пріоритетом, щоб завжди розширювати наступною найперспективнішу клітинку.

Ця симуляція множить евристику манхеттенської відстані на вагу ε перед додаванням до вартості шляху, тож f = g + ε·h. При ε = 1 евристика допустима (ніколи не перевищує) і A* гарантовано повертає найкоротший шлях. Підвищення ε понад 1 робить пошук "жадібнішим": він більше довіряє евристиці, досліджує драматично менше вузлів і знаходить шлях набагато швидше, але шлях більше не гарантовано оптимальний — це називається Зваженим A*, поширений практичний компроміс у робототехніці реального часу, де трохи довший шлях, знайдений миттєво, перемагає оптимальний шлях, знайдений занадто пізно.

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

Клацніть будь-яку відкриту клітинку проходу в 3D-сітці, або скористайтеся кнопкою «Заблокувати випадковий прохід», щоб позначити її непрохідною. Симуляція потім перевіряє поточний шлях кожного робота: якщо щойно заблокована клітинка лежить будь-де попереду на цьому шляху, негайно запускається цілком новий пошук A* від поточної клітинки робота до тієї самої цілі, уникаючи заблокованої клітинки разом з усіма стелажами. Це відображає реальні складські флоти, де впущений піддон чи інший робот, що займає клітинку, змушує до негайного повторного пошуку замість того, щоб робот заїжджав у глухий кут.

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

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