Department of Computer Science

How to Find the Optimal Actions Faster

How to Find the Optimal Actions Faster

Together with his two co-authors, Álvaro Torralba, Associate Professor at the Department of Computer Science, Aalborg University, has received honourable mention at the AAAI-22 conference for the paper “Operator-Potential Heuristics for Symbolic Search”. The paper demonstrates that heuristic and symbolic search can be combined to enhance speed when searching for the optimal actions to perform.

The Association for the Advancement of Artificial Intelligence organizes some of biggest and most important conferences within the field of AI. The AAAI-22, held as a virtual conference from February 22 through March 1, was no exception. 9,251 papers were submitted, 9,020 were reviewed and through a thorough and rigorous process, 1,349 papers were accepted. Being among the very few that actually get an award is therefore an extraordinary accomplishment.

- You could, jokingly of course, refer to “honourable mention” as a kind of second place. However, given the number of submissions and the quality of the papers submitted, we are extremely proud to have received this award, says Álvaro Torralba.

heuristic and symbolic search combined

The paper “Operator-Potential Heuristics for Symbolic Search” is co-written with Daniel Fišer, Saarland University and Czech Technical University in Prague, and Jörg Hoffmann, Saarland University. The paper demonstrates that two previously competing algorithms can actually be used in combination and provide faster search results. In this context, the aim of the performed search is to identify the optimal set of actions to perform to achieve a certain result as fast as possible.   

- I think that the main reason for giving us the award was that we challenged a belief that you cannot be sure to enhance the speed of standard symbolic search by combining it with heuristic search. In some cases, combining symbolic search with heuristic search could actually end up jeopardizing performance. A number of attempts to combine the two algorithms have been made, but so far, nobody had succeeded, Álvaro Torralba explains.

In heuristic search, the options are ranked in order to enhance speed, whereas in symbolic search, multiple options are considered all at once, which makes it diffcult to rank them.

- How can the rankings from heuristics be used effectively within symbolic search, was the question. A key insight in our paper is that introducing “potential heuristics”, a specific subtype of heuristic search, for symbolic search makes it possible to anticipate how applying certain actions will affect these rankings, before the actions are actually performed. This is what allows using them in symbolic search in a way that speeds up the search, says Álvaro Torralba.

Álvaro Torralba describes the paper as basic research presenting findings that may be used in a number of diverse situations and applications.

- Our paper describes a method to optimize search performance. It is not targeted at a specific application, but may be adapted and applied to a number of different situations, he says

The poster used during the virtual poster session at the AAAI-22 conference.

_________________________________________________________________________________________

FURTHER INFORMATION

CONTACT

Álvaro Torralba
Associate Professor
Department of Computer Science,
Aalborg University
Mail: alto@cs.aau.dk

Stig Andersen
Communications Offcer
Department of Computer Science,
Aalborg University
Mail: stan@cs.aau.dk
Phone: +45 4019 7682

Department of Computer Science, Aalborg University

Selma Lagerlöfs Vej 300  ・ 9220 Aalborg East, Denmark 
Telephone: +45 9940 9940  ・ Mail: info@cs.aau.dk

Contact department management