Machines are increasingly replacing processes or tasks carried out by humans and we can see such replacement more and more, both in industrial activities (logistics and distribution) and in more common activities of our daily lives, for example, the chatbots used in customer service applications, or the so-called conversational agents such as Alexa or Siri.

In Artificial Intelligence the term planning (PL for short) is applied to the area that seeks a sequence of actions that allow achieving a certain objective, for example, how to distribute the packages of a warehouse to the corresponding destinations. At the same time, generalized planning (GP) would no longer be a sequence but an algorithm or a program that allows solving a whole series of problems.

“An analogy that can be used to explain this is cooking”, explains Javier Segovia-Aguas, a researcher with the Artificial Intelligence and Machine Learning (AI & ML) group at the UPF Department of Information and Communication Technologies (DTIC). “Planning is like a recipe: to make it I need to know everything that is available and everything I can do in my kitchen, that is, all the actions I can carry out in the room. Generalized planning, meanwhile, would be like a catering service, in addition to learning the recipes you also need to solve the different problems that arise with customers. For example, what to do when a party arrives who are allergic to dairy products, what to do if a dish is a success and I have to direct resources to supply this particular dish, or someone asks for a very strange ingredient,... All this casuistry can be represented with a program like the ones we run on our computers and mobiles, so that the original problem ends up being converted to automatically finding the program that solves all the cases".

“Planning is like a recipe: to make it I need to know everything that is available and everything I can do in my kitchen, that is, all the actions I can carry out in the room. Generalized planning, meanwhile, would be like a catering service; in addition to learning the recipes you also need to solve the different problems that arise with customers”

So what Segovia-Aguas has done, together with Anders Jonsson, head of the AI & ML group, and Sergio Jiménez, at the Valencian Research Institute for Artificial Intelligence (VRAIN), is try to find solutions to a large number of possible problems with GP, since as the problems escalate, it is usually more difficult to find answers.

“We wanted to know if it was possible to find solutions to these increasingly bigger problems, of a size that could become infinite”, continues Segovia-Aguas. “In our study we show that they can be solved, and even if we have very big problems, we can find solutions to them”.

The study, published in the proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021), presents several very important results for the area of automatic planning. “First we develop a new representation of GP solutions that is independent of the size of the problems”, the researcher explains. “Second, we define heuristic and evaluation functions, which help us prioritize some solutions over others and inform how far I am from my goal. This is clear when I only have one goal, but not when we have several and these cases are what we are studying. Finally, we define a GP algorithm, called Best-First Generalized Planning (BFGP), which implements a solution space search guided by our evaluation/heuristic functions”.

“Heuristics means an estimate of how far I am from my goal. This is clear when I only have one goal, but not when we have several and these cases are what we are studying”, the researcher explains.

What they have done is a completely new search approach for generalized planning, with a search space, heuristic functions and a search algorithm, which had not been done before. Although it is just the first step, it is due to these results that the publication has been selected as one of the best in Artificial Intelligence in 2021, and for this reason they have been invited to the International Joint Conference on Artificial Intelligence (IJCAI), to attend the best publications session (Sister Conferences Best Papers of the IJCAI-ECAI 2022). “It is a very important distinction and says a lot about the level of research in AI that is conducted at UPF, a trajectory for which we already received the award for best IJCAI publication in 2016, and the best European thesis in Artificial Intelligence in 2018”.