Back A single program that solves multiple problems automatically

A single program that solves multiple problems automatically

This is the field of research chosen by Javier Segovia Aguas, whose doctoral thesis was distinguished by the European Association for Artificial Intelligence as the best European thesis on Artificial Intelligence 2018 at the international meeting held in Macau (China), on 14 August.

27.09.2019

Imatge inicial

Program Synthesis for Generalized Planning was the doctoral thesis title which Javier Segovia Aguas, supervised by Anders Jonsson, a member of the Artificial Intelligence and Machine Learning research group at the UPF Department of Information and Communication Technologies (DTIC), defended at Pompeu Fabra University in October 2018.

“The thesis deals with different mechanisms whose purpose consists of solving multiple problems using a single program automatically”, asserts Segovia. The study was recognized as Best European thesis on Artificial Intelligence 2018 by the European Association for Artificial Intelligence (EURAI), at the international meeting of the IJCAI held in Macau (China), on 14 August.

The research combines two essential issues in the field of artificial intelligence

The thesis combines two areas in the field of artificial intelligence. First, it investigates the synthesis of programs, or how to get machines to program code, and secondly it refers to the field of generalized planning, with “planning” being understood as the sequence of steps that lead to a goal or target, and “generalized” as being the solution to a problem that may serve to solve other similar problems.

The main goal of this research was to make classic planning techniques capable of programming code automatically and to solve more complex problems

The main aim of this research was to make classic planning techniques capable of programming code automatically and to validate that the solutions found could also be used to solve more complex problems in such a way that the classic techniques could not be solved without help. Another aim was to establish solid theoretical bases on the complexity and the correctness of the formalized mechanisms (whether they solve the computational problem for which they were designed).

As Segovia explains, “on the one hand we have a set of problems we wish to solve. For example, to visit all of the cells in a table, or to put a set of random numbers in ascending order. Also, these problems establish what the solutions or final programs must be like (deterministic, recursive,...) so that they solve not one but multiple problems”.

“These characteristics are of the type: a) “must the program always have a single option (Deterministic program) or can it have situations in which it must choose? (Non-deterministic program); b) can prior knowledge be used? (partial solutions for the problem); c) does it require an additional observation? For example, to know whether one number is bigger than another, etc.”, Segovia adds.

“Once we establish the context, we can now translate an entire language understood by the classic systems of planning such as PDDL (Planning Domain Definition Language). Having all the problems in PDDL makes them independent from the techniques used to solve them, in such a way that we have been able to use free tools from other universities and research centres around the world without problems”, the author comments.

The solution provided by these systems is known as flat, and here is where the author has found the final program that solves the original problem and other problems of the same kind. And to validate that the programs are correct solutions, the system was forced to run these programs and verify that the sequence of steps leads to the desired goal for each of the problems.

The experiments have shown the capacity of classic planning techniques to solve highly complex problems through program synthesis

The experiments conducted in this research have shown the capacity of classic planning techniques to solve highly complex problems through program synthesis.

In addition, program generation and validation have been integrated under one same problem, since until now they were construed as being different problems.

It has also been shown that programming is flexible, since it can provide partial programs and leave the system to generate the remaining code, and can re-use the solutions to other problems to solve new, more complex problems.

The theoretical bases have been established that show the complexity of each mechanism implemented, and the correctness of the solutions found.

Finally, the same procedures were able to be easily applied to other areas. For example, learning a grammar from a text, which proves the enormous adaptability of the proposed approach.

Future application or extension of the research

As Javier Segovia states, this research can be applied in a great many areas. In the field of robotics “where we are applying similar techniques to program robots naturally”, he affirms. But also, to justify how and why artificial intelligence is taking a concrete decision; to generate a code automatically with little effort; in cybersecurity, to quickly detect attacks and halt them. “Or even in theoretical biology, where we are interested in finding out how a system evolves in time, similarly to what we call the game of life”.

Reference work:

Javier  Segovia Aguas (2018), Program Synthesis for Generalized Planning, tesi doctoral, Universitat Pompeu Fabra, 5 October. Director: Anders Jonsson. Best European thesis on Artificial Intelligence 2018 by the European Association for Artificial Intelligence (EURAI).

Multimedia

Categories:

SDG - Sustainable Development Goals:

Els ODS a la UPF

Contact

For more information

News published by:

Communication Office