What is the AdaSubS algorithm and how it works
The Adaptive Subgoal Search algorithm allows machines to divide complex problems into sub-tasks which can be performed step by step. Thanks to this, reaching the solution requires less work, which also means less computing power and less energy needed to operate servers.
People work similarly – by dividing daily activities (such as preparing a meal) into small steps, relatively rare tasks (such as planning a holiday trip), and are able to apply this ability to completely new challenges (like a project at work that requires an innovative approach). In the case of computer programs, the further away from the routine scheme, the more difficult it is for them to take adequate action. However, artificial intelligence is able to learn how to independently break down its tasks into smaller steps.
“There are many pressing problems that are too difficult to solve accurately and quickly. Our innovative method, which is efficient and imitates the way we, humans, naturally think, may be useful,” commented Tomasz Odrzygóźdź, postdoc at IDEAS NCBR.
The Polish team trained the skill of their algorithm on the Rubik’s cube. By observing the effects of its mixing and analyzing thousands of possible combinations, the algorithm itself developed “milestones” on the way to solving the cube. Adaptive skills of AdaSubS were also tested on the Sokoban puzzle game and mathematical inequalities. It turned out that the Polish algorithm can solve these tasks in a smaller average number of steps than the best algorithms known so far in this area.
“We deliberately taught our algorithm not on the strategies of the Rubik’s cube masters but on the usual random spinning of the cube. The success lies in this, among other things, that it was enough. We have shown that even such “cheap” data obtained in a simple way is sufficient for the algorithm to be able to create good sub-tasks to achieve the goal,” commented Michał Zawalski, postgraduate student at the University of Warsaw.
Possible applications of the AdaSubS algorithm
Although robotics has been developed for decades, we are still far from fulfilling the futuristic visions of robots – assistants that have taken over the cooking and cleaning at home. This is precisely because these activities are, contrary to appearances, quite complicated. Employing machines for these tasks would require the creation of very complex software or artificial intelligence that would be able to learn how to move around the kitchen on its own, just like the AdaSubS algorithm learned to solve the Rubik’s cube.
Another place abounding in new and non-standard situations are the streets. The ability to learn on the fly would certainly help systems in controlling autonomous vehicles. The creators of the AdaSubS algorithm also see the potential application of their tool in a wide range of problems.
“AdaSubS is a general-purpose algorithm, which gives hope for scaling its use to important problems of science and everyday life. We plan to use the method for automatic theorem proving (ATP), robotics, automatic writing of programs (program synthesis), multiplayer games or retrosynthesis,” said Łukasz Kuciński, PhD from the Institute of Mathematics of the Polish Academy of Sciences.
The awarded work of the Polish scientists is available in the arXiv database and on a special stronie website. Its authors are postgraduate students from the University of Warsaw: Michał Zawalski, Michał Tyrolski, Konrad Czechowski, Piotr Piękos KAUS (work written while working at the University of Warsaw), postgraduate student from the Jagiellonian University Damian Stachura, Tomasz Odrzygóźdź, PhD from IDEAS NCBR, Yuhuai Wu from Google Research, Łukasz Kuciński, PhD from the Institute of Mathematics of the Polish Academy of Sciences and Professor Piotr Miłoś, leader of the research team at IDEAS NCBR, also associated with the Institute of Mathematics of the Polish Academy of Sciences.
ICLR 2023 will be held between May 1 and 5. Visit the websitge of the conferenc for more information.