Polski algorytm AI wśród najlepszych na świecie. Potrafi efektywnie podzielić drogę do celu

Jeśli stoisz przed trudnym zadaniem i nie wiesz, jak się z nim zmierzyć, warto zastanowić się nad podzieleniem go na łatwiejsze podzadania. Polscy matematycy stworzyli algorytm, który pomaga w konstrukcji i wyszukiwaniu takich podzadań, aby rozwiązywać złożone problemy jak najbardziej efektywnie. Ta innowacja może być szczególnie użyteczna dla robotów.

„Nasz algorytm Adaptive Subgoal Search (AdaSubS) łączy uczenie maszynowe z klasyczną algorytmiką w celu rozwiązywania złożonych zadań kombinatorycznych, takich jak układanie kostki Rubika lub dowodzenie matematycznych nierówności. Algorytm wykorzystuje wyuczone wysokopoziomowe taktyki oraz adaptuje swoje działanie do stopnia trudności zadania w danej chwili” – opisują autorzy pracy.

Zespół polskich naukowców, wraz z badaczem z Kanady, opublikował pracę na temat Adaptive Subgoal Search, która została doceniona podczas międzynarodowej konferencji ICLR – jednej z trzech najważniejszych konferencji informatycznych na świecie dotyczących sztucznej inteligencji. Praca została zakwalifikowana do najlepszych 5% przyjętych prac (ang. notable-top-5 proc.), co stanowi wyjątkowe osiągnięcie w skali Polski. Publikacja jest dostępna w bazie arXiv oraz na stronie projektu.

Nie zawsze zdajemy sobie z tego sprawę, ale często korzystamy z strategii dzielenia dużego zadania na mniejsze problemy. Przykładem może być codzienna wizyta na poczcie – aby dotrzeć na miejsce, musimy wykonać wiele „kroków po drodze”, takich jak ubranie się, znalezienie kluczy i portfela, wyjście z domu, wybór trasy i stopniowe pokonywanie drogi. Niektóre z tych etapów są łatwiejsze i szybsze do wykonania, a inne wymagają większego wysiłku i zaangażowania. Dr Łukasz Kuciński z Instytutu Matematycznego PAN, jeden z autorów badania, podkreśla, że podobną strategię stosują roboty i sztuczna inteligencja, a ich algorytmy pozwalają na efektywne rozwiązywanie złożonych problemów poprzez konstruowanie i wyszukiwanie podproblemów.

Chodzi o to, że nie każdy kamień milowy osiąga się tym samym nakładem sił. I nie na każdą drogę do tego samego celu składa się jednakowa liczba kamieni milowych.

Prof. Piotr Miłoś z Instytutu Matematycznego PAN, współautor pracy, przytacza przykład podróży samochodem przez górzysty teren. Aby dotrzeć do celu, można wykonać skomplikowaną serię manewrów, aby przejechać wąskie przesmyki i pokonać nierówności terenu. Inne rozwiązanie to wydostać się z gór na wygodną, równą trasę i ominąć wszystkie przeszkody. Jeśli te różne trasy podzielimy na pojedyncze manewry, kierowca będzie musiał inaczej rozłożyć swoją uwagę na każdej z tych drogach.

Badacze zdecydowali się zastosować ten koncept do usprawnienia algorytmu adaptacyjnego wyszukiwania podzadań, zwanych subgoalami. Celem jest takie wyszukiwanie kolejnych podzadań, aby cała trasa była jak najłatwiejsza do przebycia. W praktyce oznacza to minimalizację zużycia energii przez procesor potrzebnego do rozwiązania problemu.

Badacze testowali swój algorytm na zadaniach takich jak kostka Rubika, gra Sokoban oraz nierówności matematyczne. Według wyliczeń, ich algorytm jest w stanie rozwiązywać te zadania w mniejszej średniej ilości kroków niż najlepsze dotąd algorytmy na świecie w tych dziedzinach (kSubS i BestFS).

Dr Kuciński sugeruje, że algorytm sztucznej inteligencji może mieć bardziej efektywne sposoby znajdowania podzadań niż człowiek. Jednakże nie jest to jeszcze do końca potwierdzone i badania nad tym tematem nadal trwają.

Profesor Miłoś wyjaśnia, że algorytm został nauczony rozwiązywania kostki Rubika, korzystając z sekwencji ruchów uzyskanych przez losowe mieszanie już ułożonej kostki. Dzięki temu, gdy sekwencję tych ruchów odtworzy się w odwrotnej kolejności, kostka zostanie ponownie ułożona. Program analizował dziesiątki tysięcy takich łatwych do uzyskania trajektorii i samodzielnie wyszukiwał podzadania, które umożliwiały rozwiązanie kostki Rubika.

— Niesamowitym osiągnięciem jest to, że algorytm potrafił wykorzystać tak proste dane do stworzenia skutecznych subzadań — podkreśla Profesor Miłoś.

Naukowcy uważają, że możliwości algorytmu są znacznie większe niż tylko rozwiązywanie łamigłówek. Ich zdaniem, w przyszłości można go wykorzystać do rozwiązywania problemów o dużym znaczeniu praktycznym, takich jak automatyczne dowodzenie twierdzeń, pisanie programów czy projektowanie algorytmów. Jednakże, aby to się stało, potrzebne jest dostarczenie odpowiedniej ilości danych, na których algorytm będzie mógł się uczyć rozwiązywania zadań i wyszukiwania odpowiednich podzadań.

Dr Kuciński uważa, że algorytm Adaptive Subgoal Search może być wykorzystany do projektowania robotów. Zdaniem naukowca, niedługo powinno być wystarczająco dużo danych zebranych przez roboty na całym świecie, aby uczyć na nich kolejne roboty. Przykładowo, robot uczony będzie, jak wykonywać określone prace domowe w wielu różnych kuchniach, a następnie będzie musiał poradzić sobie z wykonaniem tych samych zadań w kuchni użytkownika, która ma inny układ. Zwraca uwagę, że algorytmy, które potrafią rozwiązywać problemy poprzez generowanie podzadań, powinny umożliwić robotowi łatwe radzenie sobie z nowymi zadaniami.

Algorytm Adaptive Subgoal Search jest w stanie dostosować się do trudności prostych podzadań, co prowadziłoby do oszczędności energii w przypadku robotów.

Profesor Miłoś komentuje, że dzięki temu algorytmowi można być bardziej ekonomicznym w stosunku do obliczeń, co oznacza, że za tę samą stawkę jesteśmy w stanie zrobić więcej.

Dr Kuciński podsumowuje, że algorytm Adaptive Subgoal Search jest idealny do rozwiązywania trudnych problemów kombinatorycznych i pokazuje, jak dostosować się do sytuacji. Algorytm ten, inspirowany ludzkim zachowaniem, pokazuje, że duże zadania często warto podzielić na mniejsze podproblemy, na rozwiązanie których należy dopasować czas odpowiednio do ich złożoności.

Algorytm został opracowany przez dr Kucińskiego, doktorantów z Uniwersytetu Warszawskiego – Michała Zawalskiego, Michała Tyrolskiego i Konrada Czechowskiego, doktoranta z Uniwersytetu Jagiellońskiego – Damiana Stachurę, Piotra Piękos z KAUST (praca napisana podczas pracy na Uniwersytecie Warszawskim), dr Tomasza Odrzygóźdź z IDEAS NCBR oraz dr Yuhuai Wu z Google Research.