In their article, the researchers use machine learning to investigate classical planning problems, such as optimising deliveries. Photo credit Benjamin Haas/MostphotosSimon Ståhlberg, postdoc, and Jendrik Seipp, assistant professor, together with Guillem Francès at Universitat Pompeu Fabra in Barcelona, have been awarded the prize for an article they presented at the large International Joint Conferences on Artificial Intelligence Organization, IJCAI, conference.
“IJCAI is one of the two most important AI conferences in the world. 4,204 contributions were submitted for consideration, of which 587 were selected for presentation. Three of these were judged to be ‘distinguished papers’, and we’re happy that ours was one of them”, says Jendrik Seipp.
The article investigates what are known as classical planning problems.Jendrik Seipp. Photo credit Privat
“This type of problem considers an agent who can take decisions and perform actions. The agent is placed in a particular initial state. It knows which actions are possible in each state, and wants to find a sequence of actions that take it from the initial state to a state that satisfies its goals.”
Consider a logistics company as an example. You have several trucks that are to deliver packages, and you have information about the destinations of the packages. Initially, all trucks and packages are in the depot, and you must decide which truck is to be loaded with which package. You want to find the best sequence of actions, such that the cost of delivering all the packages is minimal.
“Normally, when starting to analyse such a problem, you create a space of all conceivable states. You must then find a path that takes you from the initial state, in which all trucks and packages are in the depot, to a state in which all packages have been delivered”, Jendrik Seipp explains.
Each state can be seen as a point in a coordinate system with many dimensions. When searching for a state in which all goals have been reached, it may be the case that you reach a state from which it is impossible to reach the goal.
“It’s desirable to realise that you are in such a state as early as possible, to eliminate the paths that lead to it. That’s what we show how to do in our article. In the example from logistics, such a state might be one in which a truck does not have sufficient fuel to reach its destination. When this arises, the goal cannot be reached.”
The researchers show that certain properties characterise such states. They use machine learning to find compact formulas that characterise unsolvable states, that is, states from which no goal state can be reached.
“What’s most interesting in our article, and I can imagine that this is why we won the prize, is that we combine machine learning and planning, and we do this in a way that can be explained. You can look at our formulas and say: ‘Yes, I can see that this formula makes sense’.”
Many machine learning approaches do not make it easy to interpret the learned models. It’s possible that you’ve found a model that works well, but you’re not able to grasp how the model makes its predictions. This is known as “black-box AI”.
“If you use machine learning to find answers, but don’t know why they are right, you can’t fully trust the answer. If you want to use a system in real life, you must understand why it makes certain decisions. It can be dangerous to use the system if you can’t explain its reasoning”, says Jendrik Seipp.
Within AI research, it has recently become more common to search for solutions that can be explained, an undertaking known as ”explainable AI”.
The research was supported by an ERC Advanced Grant (PI: Hector Geffner), the EU ICT-48 2020 project TAILOR, the Knut and Alice Wallenberg Foundation (WASP program) and the Swedish National Infrastructure for Computing (SNIC).
The article: “Learning Generalized Unsolvability Heuristics for Classical Planning”, Simon Ståhlberg, Guillem Francès, Jendrik Seipp, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, Main Track, pages 4175-4181
Translated by George Farrants