Jak efektywnie podzielić drogę do celu. Algorytm AI Polaków wśród najlepszych na świecie

"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.

Publikacja zespołu polskich naukowców (z udziałem badacza z Kanady) o Adaptive Subgoal Search (dostępna w bazie arXiv oraz na stronie projektu) została doceniona na jednej z trzech najważniejszych konferencji informatycznych na świecie dot. sztucznej inteligencji - The International Conference on Learning Representations (ICLR). Pracę tę zakwalifikowano tam do najlepszych 5 proc. przyjętych prac (ang. notable-top-5 proc.). To w skali Polski wyjątkowe osiągnięcie.

BĄDŹ DZIELNY! DZIEL PROBLEMY

Nie zawsze zdajemy sobie z tego sprawę, ale przy wykonywaniu codziennych czynności stosujemy strategię dzielenia dużego zadania na mniejsze problemy.

"Kiedy chcemy pójść na pocztę, mamy po drodze do osiągnięcia ileś 'kamieni milowych'. Musimy ubrać się, znaleźć klucze i portfel, wyjść z domu, wybrać drogę, którą dojdziemy na pocztę, a potem tę drogę stopniowo pokonywać itd. Jedne z tych 'kamieni milowych' są łatwiejsze i szybsze do osiągnięcia, a czynności na tym odcinku wykonujemy niemal automatycznie, a inne wymagają więcej zaangażowania" - opisuje w rozmowie z PAP współautor pracy dr Łukasz Kuciński z Instytutu Matematycznego PAN.

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 IM PAN - kolejny współautor - podaje przykład podróży samochodem przez górzysty teren. Aby dotrzeć do celu, można wykonać serię bardzo wielu skomplikowanych manewrów, żeby przejechać wąskimi przesmykami omijając nierówności terenu. Albo też próbować wydostać się spośród wzniesień na wygodną, równą trasę i ominąć wszystkie przeszkody. Jeśli podzieli się te różne trasy na pojedyncze manewry, to na każdej z tych dróg kierowca musi inaczej rozłożyć swoje skupienie.

Badacze postanowili ten koncept wykorzystać do udoskonalenia algorytmu adaptatywnego poszukiwania podzadań (tzw. subgoali). Wyzwaniem jest to, by tak wyszukiwać kolejne podzadania, aby przemierzenie całej drogi było jak najłatwiejsze. A w praktyce: aby procesor do jego rozwiązania zużył jak najmniej energii.

Na razie badacze na warsztat wzięli kostkę Rubika, Sokoban i nierówności matematyczne. Jak wyliczają, ich algorytm jest w stanie rozwiązywać te zadania w mniejszej średniej ilości kroków niż najlepsze dotąd w tym zakresie algorytmy świata (kSubS i BestFS).

Dr Kuciński podaje przykład, że dla osób rozwiązujących kostkę Rubika takimi kolejnymi podzadaniami może być choćby ułożenie krzyża, bloków czy rogów odpowiedniego koloru. Czy jednak algorytm sztucznej inteligencji automatycznie znajdzie sobie takie same podzadania jak człowiek - nie wiadomo, można się tylko domyślać, że ma swoje bardziej efektywne sposoby.

Prof. Miłoś zdradza, że algorytm uczono układania kostki Rubika w dużej mierze na sekwencjach ruchów, które uzyskano z losowego mieszania rozwiązanej kostki. No bo przecież, gdy taką sekwencję odtworzymy wstecz - kostka z jakiegoś losowego układu zostanie efektywnie ułożona. Program analizował więc dziesiątki tysięcy takich łatwo uzyskanych trajektorii i miał sam automatycznie wyszukać sobie podzadania, które były na drodze do rozwiązania kostki.

"Małym 'cudem', który pokazaliśmy, jest to, że nawet tak 'tanie' dane - uzyskane prostym sposobem - są wystarczające, żeby algorytm był w stanie utworzyć sobie dobre subgoale" - komentuje prof. Miłoś.

PODZIELMY SIĘ ZADANIAMI Z ROBOTAMI

Naukowcy zapewniają, że łamigłówki i nierówności matematyczne to dopiero początek. "W którymś momencie algorytmu tego będzie można użyć do rozwiązywania problemów z prawdziwym impaktem. To może być automatyczne dowodzenie twierdzeń, pisanie programów, projektowanie algorytmów" - mówi dr Kuciński.

Warunkiem jest to, żeby dostarczyć odpowiedniej ilości danych, na których AdaSubS nauczy się rozwiązywania zadań - a po drodze - wyszukiwania sobie podzadań.

"Mamy hipotezę, że naszego algorytmu da się też użyć przy projektowaniu robotów" - uśmiecha się dr Kuciński. Opowiada, że być może niedługo będzie wystarczająco dużo danych uzyskanych przez roboty na całym świecie, aby trenować na nich kolejne roboty. Np. robot uczony będzie, jak wykonywać określone prace domowe w iluś wzorcowych kuchniach, a potem musi sobie poradzić z wykonaniem tych samych zadań w u docelowego użytkownika, w kuchni, która ma inny układ. "Jeśli ma się algorytmy, które potrafią rozwiązywać problemy generując podzadania - robot powinien poradzić sobie z nowym zadaniem" - zwraca uwagę matematyk.

Jeśli algorytm dotrze do prostego podzadania, płynnie dostosowuje się do tej trudności. A to akurat w przypadku robotów prowadziłoby do oszczędności energii.

"Dzięki temu algorytmowi jesteśmy w stanie być bardziej ekonomiczni względem obliczeń. Za tę samą stawkę jesteśmy w stanie więcej zrobić" - komentuje prof. Miłoś.

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

Autorami algorytmu są również doktoranci z Uniwersytetu Warszawskiego: Michał Zawalski, Michał Tyrolski, Konrad Czechowski, Piotr Piękos KAUST (praca napisana podczas pracy na Uniwersytecie Warszawskim), doktorant z Uniwersytetu Jagiellońskiego Damian Stachura, a także dr Tomasz Odrzygóźdź z IDEAS NCBR i dr Yuhuai Wu z Google Research.

Nauka w Polsce, Ludwika Tomala

lt/ agt/