Interview with Vidal Alcázar – #AAAI20 award winner

Vidal Alcázar, Pat Riddle and Mike Barley received an honourable mention in the outstanding paper award category at AAAI-20 for their work “A Unifying View on Individual Bounds and Heuristic Inaccuracies in Bidirectional Search”. Here, Vidal Alcázar tells us more about the topic of heuristic searching, the main findings of their research, and plans for future work in the area.

What is the topic of the research that you presented at AAAI-20?

The topic is optimal Heuristic Search, that is, finding paths of lowest cost in graphs, often referred to as the shortest-path problem. A common example is the GPS navigator of a car: when you input the destination, the device usually spends some time calculating routes and then displays the best one. The time spent calculating is, for the most part, time spent executing heuristic search algorithms.

In particular, we focus on bidirectional search. This means running two algorithms at the same time, one from the set of initial states and another from the set of goal states. These algorithms interact with each other and meet somewhere in the middle, which allows reconstructing a solution from the meeting point. The main advantage is both reducing the depth of the search, which may yield up to exponential gains, and to share information between both algorithms in order to improve their performance.

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

For many decades, A* has been the state of the art in optimal Heuristic Search. A* was proposed back in 1968 and is taught in the vast majority of AI courses, and surprisingly it was arguably the to-go algorithm until 2016, in which a new family of bidirectional algorithms finally beat A* in common benchmarks.

Heuristic Search is at the core of both applications and other AI fields, like Constraint Satisfaction and Automated Planning. Hence, improving the state of the art and providing a more comprehensive theoretical framework will allow both implementing more efficient solutions and progressing in fields other than Heuristic Search itself.

Could you explain your methodology?

From 2016 to 2019, several very successful bidirectional algorithms pushed the state of the art. Along with them, a theoretical analysis allowed understanding the behavior of some of them and defining strong properties like near-optimality. However, the relationship between some of these algorithms was relatively unclear, and the theoretical analysis didn’t consider yet old approaches with a significant potential that exploited consistency and heuristic inaccuracies.

By trying to understand the common link between all these approaches, we realized that the main concept that they used is a lower bound on the cost of a solution path going through that node. Therefore, by defining individual lower bounds and integrating them together one can combine the main advantages of the algorithms within the same framework.

What were your main findings?

The main finding is the existence of a more general framework that seamlessly combines a very diverse set of algorithms. Even more, doing so is not only conceptually easy, but also synergistic. The resulting new family of algorithms is conceptually simple, yet it obtains significantly better results than the state of the art.

Additionally, this fills the gaps between the latest trends in bidirectional search and algorithms that remained hard to exploit for even decades despite their great potential.

What further work are you planning in this area?

A lot of work remains to be done. First, a sounder theory departing from this framework must be established. Second, the decisions that are made when designing algorithms under the new framework must be studied, particularly from an empirical point of view. Doing so will allow to popularize bidirectional search as an alternative to unidirectional search and to improve the efficiency of applications that were relying on A* as the main algorithm.

About the authors

Vidal Alcázar is a post-doctoral researcher in the Search and Parallel Computing Unit at Riken AIP. His main field of research is Automated Planning, with a focus on regression techniques and decomposition of problems. In particular, his aim is to create domain-independent solvers that can scale better as the size of the problems increases by reducing the depth of the different subproblems that compose the original one. Additionally, he works on bidirectional Heuristic Search as well, specifically finding solutions of optimal cost with bidirectional techniques.

Pat Riddle is a Senior Lecturer in the School of Computer Science at the University of Auckland. Her main research interests are in the AI areas of problem reformulation and machine learning and datamining. In particular, she is interested in various techniques for machine learning (such as ensemble approaches, techniques which overcome overfitting problems, and data-engineering as incorporating background knowledge) and their applications to real world problems.

Mike Barley is a Senior Lecturer in the School of Computer Science at the University of Auckland. His primary research focuses on adaptive problem solving. Specifically developing problem solvers that dynamically select the problem solving methods, problem representations, and search control knowledge that seem most likely to solve a given problem in the shortest amount of time. He is also interested in heuristic search in general, and more specifically bidirectional heuristic search.

Vidal Alcázar is a post-doctoral researcher in the Search and Parallel Computing Unit at Riken AIP

Vidal Alcázar is a post-doctoral researcher in the Search and Parallel Computing Unit at Riken AIP