A research team from the University of Warsaw and Jagiellonian University as well as IDEAS NCBR research and development centre and Polish Academy of Sciences Institute of Mathematics has created an algorithm which will help artificial intelligence to independently plan subsequent steps in designing solutions to complex problems. This will allow engineers to, for instance, build robots that will be better in performing difficult tasks.
The Adaptive Subgoal Search algorithm (AdaSubS) will allow machines to divide complex and complicated problems into subgoals that can be carried out on a ‘step by step’ basis. Because of that, arriving at a solution requires less work and therefore less computing power and less energy to power the servers. This is similar to how humans act, dividing both everyday chores (e.g. cooking a meal) and more rare activities (e.g. planning vacation) into simpler stages and thus managing to overcome new challenges. In the case of computer programmes, the further from routine, the more difficult it is for AIs to chose an appropriate behaviour. However, it is able to learn how to independently divide its tasks into simpler subgoals.
The team from the University of Warsaw and Jagiellonian University as well as IDEAS NCBR research and development centre and Polish Academy of Sciences Institute of Mathematics investigated how the algorithm they had written learned to solve the Rubik’s Cube. By observing attempts and analysing thousands of possible combinations, the algorithm independently identify the milestones on the path to solving the Cube. Its adaptation skills were also tested in the puzzle video game Sokoban and mathematical equations. It turned out that it is able to solve problems in a lower average number of steps that other similar algorithms.
‘We intentionally chose to feed the algorithm a set of random turns instead of a list of moves by masters of the Rubik’s Cube. In fact, one of the most important aspects of our success is the fact that it proved to be enough. We have shown that even "cheap" data acquired in a simple way are sufficient for the algorithm to design effective subgoals in order to achieve its goal’, said Michał Zawalski, a PhD student at the University of Warsaw.
According to the designers of the algorithm, although robotics has been in development for decades, we are still far away from the futuristic concept of robot assistants that cook and clean for us. This is because, despite appearances, these activities are actually quite complex. To make machines perform them for us, we would have to either write an elaborate code or create an AI that would be able to learn how to move around the kitchen in the same way as the AdaSubS algorithm learned to solve the Rubik’s Cube. The solution provided by Polish scientists could also be implemented on the streets. The ability to learn in real time would certainly be of use in self-driving car systems.
The algorithm will be showcased in May at the International Conference on Learning Representations in Kigali, Rwanda. It is one of the most important events for researchers and institutions involved in the development of AI. Its participants will discuss subjects such as machine learning, deep learning and data science. The publication describing the invention of Polish researchers is amongst the accepted five percent of the total number of applications. It can be accessed via the arXiv database and a dedicated website.
The paper was written by Prof. Piotr Miłoś, leader of the IDEAS NCBR research team who also works closely with the Polish Academy of Sciences Institute of Mathematics, Dr Łukasz Kuciński from the Polish Academy of Sciences Institute of Mathematics, PhD students from the University of Warsaw: Michał Zawalski, Michał Tyrolski and Konrad Czechowski, Piotr Pieńkos (King Abdullah University of Science and Technology), PhD student from the Jagiellonian University Damian Stachura as well as Dr Tomasz Odrzygóźdź (postdoc at IDEAS NCBR) and Dr Yunhuai Wu from Google Research.
