Zdaniem matematyków: „Nasz algorytm Adaptive Subgoal Search (AdaSubS) łączy uczenie maszynowe i klasyczne algorytmy w celu rozwiązywania złożonych zadań kombinatorycznych, takich jak układanie kostki Rubika lub dowodzenie nierówności matematycznych. Algorytm wykorzystuje wyuczoną taktykę wysokiego poziomu i dostosowuje swoje działanie do trudności danego zadania”.

Publikacja zespołu polskich naukowców (z udziałem naukowca z Kanady) na temat Adaptive Subgoal Search (dostępna w bazie arXiv oraz na stronie projektu) została doceniona na jednej z trzech najważniejszych na świecie konferencji informatycznych poświęconych sztucznym inteligencja – Międzynarodowa konferencja na temat reprezentacji uczenia się (ICLR). Artykuł ten został sklasyfikowany w notowanych w czołówce 5 proc. To ewenement w skali Polski.

BYĆ ODWAŻNYM! PODZIEL PROBLEMY

Jak powiedział PAP współautor badań dr hab. Łukasz Kuciński z Instytutu Matematyki Polskiej Akademii Nauk: „Kiedy chcemy iść na pocztę, mamy po drodze kilka „kamieni milowych”. Musimy się ubrać, znaleźć klucze i portfel, wyjść z domu, wybrać trasę na pocztę, potem stopniowo tą trasą iść itp. Niektóre z tych „kamieni milowych” są łatwiejsze i szybsze do osiągnięcia, czynności w tych sekcje wykonywane są niemal automatycznie, inne wymagają większego zaangażowania.”

Chodzi o to, że nie każdy kamień milowy jest osiągany przy takim samym wysiłku. I nie każda droga do tego samego celu składa się z tej samej liczby kamieni milowych.

Prof. Piotr Miłoś z Instytutu Matematyki PAN – kolejny współautor – podaje przykład przejazdu samochodem przez teren górski. 

Aby dotrzeć do celu, możesz wykonać szereg bardzo skomplikowanych manewrów, aby przejechać przez wąskie przejścia, omijając nierówny teren. Lub możesz spróbować wydostać się ze wzgórz na wygodną, ​​równą drogę i ominąć wszelkie przeszkody. Jeśli podzielić te różne trasy na poszczególne manewry, to na każdej z tych dróg kierowca musi inaczej rozłożyć swoją uwagę.

Badacze postanowili wykorzystać tę koncepcję do udoskonalenia algorytmu adaptacyjnego wyszukiwania podzadań (tzw. celów cząstkowych). Wyzwanie polega na wyszukiwaniu podzadań w taki sposób, aby pokonanie całej trasy było jak najłatwiejsze. A w praktyce: tak, aby procesor zużywał jak najmniej energii na jego rozwiązanie.

Na razie badacze skupili się na kostce Rubika, Sokobanie i nierównościach matematycznych. Twierdzą, że ich algorytm jest w stanie rozwiązać te zadania w mniejszej średniej liczbie kroków niż najlepsze dotychczas algorytmy na świecie (kSubS i BestFS).

Dr Kuciński podaje przykład, że dla osób układających kostkę Rubika takimi kolejnymi podzadaniami może być np. ułożenie krzyżyka, klocków czy rogów odpowiedniego koloru. Jednak czy algorytm AI automatycznie znajdzie te same podzadania co człowiek – nie wiadomo, można się tylko domyślać, że ma swoje skuteczniejsze sposoby.

Profesor Miłoś powiedział, że algorytm został wytrenowany do układania kostki Rubika w dużej mierze na sekwencjach ruchów uzyskanych z losowego wymieszania ułożonej kostki. Wszakże gdy taka kolejność zostanie odwrócona, sześcian zostanie skutecznie ułożony. Program przeanalizował więc dziesiątki tysięcy tak łatwo uzyskanych trajektorii i miał automatycznie wyszukać podzadania prowadzące do ułożenia kostki. 

Profesor Piotr Miłoś powiedział: „Mały +cud+, który pokazaliśmy, polegał na tym, że nawet takie +tanie+ dane – pozyskane w prosty sposób – wystarczyły, aby algorytm mógł tworzyć dobre cele cząstkowe”.

DZIEL SIĘ ZADANIAMI Z ROBOTAMI

Dr Kuciński dodaje: „W pewnym momencie ten algorytm może zostać wykorzystany do rozwiązania problemów, które mają realny wpływ. Może to być automatyczne dowodzenie twierdzeń, pisanie programów, projektowanie algorytmów”.

Warunkiem jest dostarczenie odpowiedniej ilości danych, na których AdaSubS nauczy się rozwiązywać zadania – i znajdować po drodze podzadania.

– Stawiamy hipotezę, że nasz algorytm da się też wykorzystać do projektowania robotów – mówi dr Kuciński, dodając, że być może wkrótce będzie wystarczająco dużo danych pozyskiwanych przez roboty na całym świecie, by trenować na nich więcej robotów. 

Na przykład robot zostanie nauczony wykonywania pewnych prac domowych w kilku modelowych kuchniach, a następnie będzie musiał wykonać te same zadania w kuchni docelowego użytkownika, która ma inny układ. „Jeśli masz algorytmy, które potrafią rozwiązywać problemy poprzez generowanie podzadań – robot powinien sobie poradzić z nowym zadaniem” – powiedział Kuciński.

Jeśli algorytm osiągnie proste podzadanie, płynnie dostosowuje się do tej trudności. W przypadku robotów prowadziłoby to do oszczędności energii.

Kuciński dodał: „Adaptive Subgoal Search świetnie rozwiązuje trudne problemy kombinatoryczne i pokazuje, jak dostosować się do sytuacji. Inspirowany ludzkim zachowaniem algorytm pokazuje, że często duże zadania warto rozbić na mniejsze podproblemy, których czas rozwiązania należy dostosować do ich złożoności”.

Wśród autorów algorytmu są także doktoranci z UW: Michał Zawalski, Michał Tyrolski, Konrad Czechowski, Piotr Piękos (KAUST, praca pisana w czasie pracy na UW), Damian Stachura (doktorant na Uniwersytecie Jagiellońskim ), a także dr Tomasz Odrzygóźdź z IDEAS NCBR i dr Yuhuai Wu z Google Research.