🤖 Planer trasy robota magazynowego — algorytm A* na żywo

A* to algorytm przeszukiwania grafu typu best-first, który znajduje najkrótszą ścieżkę między dwoma węzłami, rozwijając węzeł o najniższym wyniku f = g + h, gdzie g to dokładny dotychczasowy koszt podróży, a h to heurystyczna estymata pozostałego kosztu do celu. W przeciwieństwie do algorytmu Dijkstry, który przeszukuje jednostajnie we wszystkich kierunkach, A* jest kierowany ku celowi przez swoją heurystykę, więc zazwyczaj przeszukuje znacznie mniej węzłów, wciąż gwarantując najkrótszą ścieżkę, gdy heurystyka nigdy nie przeszacowuje prawdziwego kosztu. Roboty magazynowe wykorzystują dokładnie ten kompromis: siatkową reprezentację alejek regałowych, szybką heurystykę (odległość Manhattan, ponieważ ruch jest ograniczony do czterech kierunków) oraz kolejkę priorytetową, by zawsze rozwijać najbardziej obiecującą komórkę jako następną.

Ta symulacja mnoży heurystykę odległości Manhattan przez wagę ε przed dodaniem jej do kosztu ścieżki, więc f = g + ε·h. Przy ε = 1 heurystyka jest dopuszczalna (nigdy nie przeszacowuje), a A* gwarantuje zwrócenie najkrótszej ścieżki. Podniesienie ε powyżej 1 czyni przeszukiwanie bardziej „zachłannym”: bardziej ufa heurystyce, przeszukuje dramatycznie mniej węzłów i znajduje ścieżkę znacznie szybciej, ale ścieżka nie jest już gwarantowana jako optymalna — nazywa się to Ważonym A*, powszechnym praktycznym kompromisem w robotyce czasu rzeczywistego, gdzie nieco dłuższa ścieżka znaleziona natychmiast bije optymalną ścieżkę znalezioną zbyt późno.

Każdy zapalający się kafelek to komórka, którą algorytm faktycznie zdjął ze swojego zbioru otwartego i rozwinął — prawdziwy front przeszukiwania, a nie dekoracyjna animacja. Kolor koduje koszt f tej komórki w chwili jej rozwinięcia, od niebieskiego (niski koszt, blisko startu) przez żółty do czerwonego (wysoki koszt, daleko od startu lub heurystycznie odległy od celu). Obserwowanie rosnącego kolorowego obszaru pokazuje, jak A* rozchodzi się w przybliżeniu ku celowi, zamiast zalewać całą siatkę tak, jak zrobiłoby to nieinformowane przeszukiwanie w rodzaju przeszukiwania wszerz czy algorytmu Dijkstry.

Kliknij dowolną otwartą komórkę alejki w siatce 3D lub użyj przycisku Zablokuj losową alejkę, by oznaczyć ją jako nieprzejezdną. Symulacja następnie sprawdza bieżącą ścieżkę każdego robota: jeśli nowo zablokowana komórka leży gdziekolwiek dalej na tej ścieżce, natychmiast uruchamiane jest zupełnie nowe przeszukiwanie A* z bieżącej komórki robota do tego samego celu, omijając zablokowaną komórkę wraz z każdym regałem. Odzwierciedla to prawdziwe floty magazynowe, gdzie upuszczona paleta lub inny robot zajmujący komórkę wymusza przeszukiwanie w locie zamiast wjazdu robota w ślepy zaułek.

Dekompozycja siatkowa zamienia planowanie trasy w dobrze poznany, tani problem przeszukiwania grafu: każda komórka to węzeł, każdy otwarty sąsiad to krawędź o koszcie 1, a klasyczne algorytmy takie jak A*, algorytm Dijkstry czy przeszukiwanie wszerz mają zastosowanie wprost. Prawdziwe zautomatyzowane magazyny używają bardzo podobnych siatek zajętości wyrównanych do regałów, ponieważ regały są już rozmieszczone w regularnym rozstawie, a roboty fizycznie muszą pozostawać w alejkach — siatka jest naturalnym, wydajnym dopasowaniem, a nie tylko uproszczeniem do celów demonstracyjnych.

Algorytm Dijkstry to A* z heurystyką h wymuszoną na zero: rozwija węzły wyłącznie na podstawie zakumulowanego kosztu g, gwarantując najkrótszą ścieżkę, ale przeszukując na zewnątrz jednakowo we wszystkich kierunkach, co marnuje czas w otwartych magazynach. A* dodaje wyraz heurystyczny, więc przeszukiwanie jest ukierunkowane ku celowi, zwykle odwiedzając niewielki ułamek węzłów, które odwiedziłby algorytm Dijkstry przy tej samej gwarancji optymalności, dopóki heurystyka jest dopuszczalna. Ustawienie suwaka wagi heurystyki w tej symulacji na 0 skutecznie odtworzyłoby wzorzec eksploracji węzłów algorytmu Dijkstry.