According to the mathematicians: “Our Adaptive Subgoal Search (AdaSubS) algorithm combines machine learning and classical algorithms to solve complex combinatorial tasks such as solving Rubik's Cube or proving mathematical inequalities. The algorithm uses learned high-level tactics and adapts its operation to the difficulty of the task at hand.”

The publication by a team of Polish scientists (with the participation of a researcher from Canada) about Adaptive Subgoal Search (available in the arXiv database and on the project website) was appreciated at one of the three most important IT conferences in the world on artificial intelligence - The International Conference on Learning Representations (ICLR) . This paper was classified in the notable-top-5 percent. This is a unique achievement in Poland.

BE BRAVE! DIVIDE PROBLEMS

The study’s co-author Dr. Łukasz Kuciński from the Institute of Mathematics of the Polish Academy of Sciences told PAP: “When we want to go to the post office, we have a number of 'milestones' on the way. We have to get dressed, find keys and a wallet, leave the house, choose a route to get to the post office, then gradually take this route, etc. Some of these 'milestones' are easier and faster to achieve, activities in these sections are performed almost automatically, while others require more commitment.”

The point is that not every milestone is reached with the same amount of effort. And not every road to the same goal consists of the same number of milestones.

Professor Piotr Miłoś from the Institute of Mathematics PAS - another co-author - gives an example of travelling by car through a mountainous area. 

To reach the destination, you can perform a series of very complex manoeuvres to drive through narrow passages, avoiding uneven terrain. Or you can try to get out of the hills onto a comfortable, level road and avoid all obstacles. If you divide these different routes into individual manoeuvres, then on each of these roads the driver must spread his focus differently.

The researchers decided to use this concept to improve the algorithm of the adaptive search for subtasks (so-called subgoals). The challenge is to search for subtasks in such a way that travelling the entire route is as easy as possible. And in practice: so that the processor consumes as little energy as possible to solve it.

For now, researchers have focused on the Rubik's cube, Sokoban and mathematical inequalities. They claim that their algorithm is able to solve these tasks in a smaller average number of steps than the world's best algorithms so far (kSubS and BestFS).

Dr. Kuciński gives an example that for people solving the Rubik's cube, such subsequent subtasks may be, for example, arranging a cross, blocks or corners of the appropriate colour. However, whether the AI algorithm will automatically find the same subtasks as a human - it is not known, one can only guess that it has its more efficient ways.

Professor Miłoś said that the algorithm was trained to solve the Rubik's cube largely on sequences of moves obtained from randomly mixing a solved cube. After all, when such a sequence is reversed, the cube will effectively be solved. So the programme analysed tens of thousands of such easily obtained trajectories and was supposed to automatically search for subtasks leading to solving the cube. 

Professor Piotr Miłoś said: “A little +miracle+ we showed was that even such +cheap+ data - obtained in a simple way - were enough for the algorithm to be able to create good subgoals.”

SHARE TASKS WITH ROBOTS

Dr. Kuciński added: “At some point, this algorithm can be used to solve problems that have a real impact. It can be automatic theorem proving, writing programmes, designing algorithms.”

The condition is to provide the right amount of data, on which AdaSubS will learn to solve tasks - and find subtasks on the way.

“We hypothesise that our algorithm can also be used to design robots,” said Dr. Kuciński, adding that perhaps there will soon be enough data obtained by robots around the world to train more robots on them. 

For example, a robot will be taught how to perform certain household chores in a number of model kitchens, and then it will have to handle the same tasks in the target user's kitchen that has a different layout. “If you have algorithms that can solve problems by generating subtasks - the robot should be able to handle the new task,” Kuciński said.

If the algorithm reaches a simple subtask, it smoothly adapts to that difficulty. In the case of robots, this would lead to energy savings.

Kuciński added: “Adaptive Subgoal Search is great at solving difficult combinatorial problems and shows how to adapt to the situation. The algorithm, which is inspired by human behaviour, shows that large tasks are often worth breaking down into smaller subproblems, the time for the solution of which should be adjusted to their complexity.”

The authors of the algorithm also include doctoral candidates from the University of Warsaw: Michał Zawalski, Michał Tyrolski, Konrad Czechowski, Piotr Piękos (KAUST, dissertation written while working at the University of Warsaw), Damian Stachura (a doctoral candidate at the Jagiellonian University), as well as Dr Tomasz Odrzygóźdź from IDEAS NCBR and Dr. Yuhuai Wu from Google Research.

PAP - Science in Poland, Ludwika Tomala

lt/ agt/ kap/

tr. RL