Optimal planning: Interview with Álvaro Torralba – #AAAI2022 award winner

Illustration of symbolic heuristic search. To the right, search space, where all states with the same initial-state distance (g) and estimated goal distance (h) are represented by a single binary decision diagram (to the left), and only those whose g+h <= solution cost need to be considered.

Daniel Fišer, Álvaro Torralba and Joerg Hoffmann won an outstanding paper runners-up award at AAAI 2022 for their paper Operator-potential heuristics for symbolic search. Here, Álvaro tells us more about the field of optical planning, their methodology, and how potential heuristics can be used in symbolic search with very positive results.

What is the topic of the research in your paper?

At a very general level, the research is on automated planning. This is a sub-area of AI where we try to answer the question: what is the best way to act given our knowledge of the world? We aim for general solvers that are domain-independent, so they can perform intelligence decision making in any situation.

In this case, we particularly deal with optimal planning, finding what is the best sequence of actions to achieve a set of goals (with guarantee of minimum cost). The key is that, in order to decide what to do now, you need to think in advance about what the outcome of your actions will be and how you will continue. We call this process search, where we search in the space of all possible alternative paths that you could follow. There are several ways of performing this search, and we present in this paper a new form to perform it in a very efficient way.

Could you tell us about the implications of your research and why it is an interesting area for study?

Research in AI planning has a very broad range of applications. In particular, it can be used in any application where one needs to optimize cost. For example, in logistics and distribution of goods, these tools can help to plan the delivery in an optimal way to optimize the cost for the company. It can also be very helpful in Industry 4.0, automatization of warehouses, etc. But it is also useful in very different kind of problems, that apparently are far away from the ones above. It has been used in security systems or natural language generation, just to give a couple of “non-classical” examples.

In all these applications, AI planning has many advantages due to having an explicit, symbolic, representation of the agent’s knowledge about the world. First, it is cheap, as you don’t need to design a program to solve the problem, but just use one of the existing tools. It is also very flexible. In a changing environment, we just need to introduce the new description of our knowledge, and we don’t need to modify the solver in any way. Furthermore, it is safe and explainable. For example, safety constraints can be easily introduced so the system will never perform unsafe actions.

What were your main findings?

In the last few years, there have been two main search techniques to look for the best possible plan: symbolic search and heuristic search.

• Heuristic search analyses the possibilities one at a time, exploring first those possibilities that are more “promising”, i.e., those that are closer to the goal according to a heuristic function that estimates the distance to the goal. The more accurate the heuristic is, the less search effort we need to find a successful plan.
• In symbolic search, we consider many possibilities at once by using efficient data-structures such as binary decision diagrams.

For years, several attempts had been made at combining these two ideas, and using heuristics in symbolic search, but they were not entirely successful. In fact, a recent publication (by David Speck et al.) showed that, somewhat counter-intuitively, having better estimations is not necessarily good in symbolic search. This led to thinking that these two ideas cannot be successfully combined.

But, in this paper we found out that, a particular class of heuristics (called potential heuristics) can be used in symbolic search with very positive results.

Could you explain your methodology?

Our methodology combines theory and practice. From the theoretical side, we ask about the properties of planning algorithms and models. In this case, we show that, under certain assumptions, potential heuristics can be expressed as a value for each action. This property is what allows us to efficiently compute them over sets of states.

From the practical side, in the planning community we have a standardized methodology to evaluate the performance of our proposal, including a standard benchmark set with around 2000 test cases. In this case, we use these benchmarks to evaluate how potential heuristics impact in symbolic search, but also we compare it with other state-of-the art algorithms, and analyze in how many cases each variant of the algorithm is superior.

We presented several variants of potential heuristics with symbolic search, and we have also performed a comparison among them, not only to determine which one is better, but also to understand which properties that have an impact on performance.

From the practical side, we ask how these heuristics impact on symbolic search. We evaluate our algorithms in a standard benchmark set with around 2000 test cases, and analyze in how many cases each variant of the algorithm is superior.

What further work are you planning in this area?

There is a lot to be done. This work has opened several theoretical questions, as it contradicts our previous intuitions on combining heuristics and symbolic search. Now, we know that this kind of heuristics can be helpful, and we have an intuitive understanding of why. A very interesting theoretical question is what exactly makes a heuristic good in symbolic search. We know that the metrics we use in traditional heuristic search are not adequate to answer this question. But now that we have an example of a good heuristic, we can try to formalize our intuitions, and that could lead to other useful heuristics in symbolic search.

In a more practical context, we will develop the use of potential heuristics in symbolic search to more complex algorithms, for example, extending it use to backward and bidirectional search (we have already started to work in this direction), to get more efficient algorithms.

You can read the paper in full here.

About Álvaro Torralba

Álvaro Torralba is currently an Associate Professor at the Department of Computer Science, Aalborg University in Denmark. His main research interest lies in AI planning, around the question of how to automate intelligent decision making in all kind of domains.

Lucy Smith is Senior Managing Editor for AIhub.

Lucy Smith is Senior Managing Editor for AIhub.