10 December 2018

How can units collaborate to complete a task in the best possible manner? Fredrik Präntare has been awarded the Lilla Polhemspris for his degree project that answers this question and solves an optimisation problem that has engaged engineers for years.

Fredrik Präntare
Fredrik Präntare. Photo credit: Susanna Lönnqvist.
The problem can be expressed in general terms: How should a team or workgroup be formed and collaborate in order to solve a problem in the most efficient manner? This optimisation problem is particularly familiar to researchers working in artificial intelligence, AI. Fredrik Präntare, doctoral student in the Department of Computer and Information Science, has developed an algorithm that determines who is to work with whom, in order to complete several specified tasks. 

“The algorithm has been developed for what are known as ‘multi-agent system’, which, as the name implies, are systems that are composed of different agents or units. The agents may be humans or robots, and no assumptions are made about whether the agents work with or against each other, or whether there are mixed groups of humans and robots”, Fredrik Präntare explains.

The algorithm coordinates the units and optimises the use of resources, in order to complete the tasks as efficiently as possible. An example of a task is to provide care for patients in a hospital. The doctors and nurses are agents who can carry out different work, and the problem that is to be solved is how the workgroups are to be composed in order to provide the best and most efficient care for the patients. 

In his degree project, Fredrik Präntare has applied the algorithm to a strategy-based game. The game involves players controlling armies on a map, and attempting to outmanoeuvre enemies. Fredrik Präntare’s newly developed algorithm was pitted against the currently used optimisation techniques used in the game, and an artificial intelligence was included as one of the players, coordinating its armies with the aid of the algorithm in real-time. 

“In real-time strategy games, you have to take decisions all the time: you can’t delay a decision in an ongoing game or in a process that has started. This means that the algorithm can also be applied to real-life problems: it doesn’t just work in a theoretical environment”, says Fredrik Präntare. 

Testing the algorithm on the toughest problems

Another way to determine the power of an algorithm is to benchmark it with synthetic problem sets. These are extremely difficult to solve and have several different solutions. 
 
“If you have a doctor who is a specialist in cancer at the hospital, you know that you should probably put that doctor into a workgroup that is to provide care for cancer patients. This is a simplification of the problem. The idea of using synthetic datasets is that they do not allow any such simplifications, and the problem becomes as difficult as possible for the algorithm to solve”, says Fredrik Präntare. 

When compared to other algorithms, Fredrik Präntare’s algorithm is the most efficient in solving the optimisation problem. The next step in development will be to use machine learning to be able to arrive at solutions to problems that are too complex for currently used algorithms. A problem with ten tasks and 1000 agents has 101000 possible solutions, and none of the current algorithms can solve this in a reasonable time.

“We also want to continue to investigate how the algorithm can be applied to real-life problems: a specialist nurse, for example, may be a member of two workgroups at the same time, as a worker in one of them and supervisor in the other. Including such descriptions in the problems would increase the area of application of the algorithm and are interesting to examine more closely”, says Fredrik Präntare. 


The award

The “Lilla Polhemspris” is awarded annually by the Swedish Association of Graduate Engineers to the best master’s degree project carried out at a Swedish university or Swedish university college. The prize was awarded on 19 November at an annual ceremony honouring Swedish inventor and engineer Christopher Polhem (1661-1751). 

Translated by George Farrants

Thesis

Read the award-winning thesis

Latest news from LiU

Two men in white lab coats with a computer in a lab.

Improving Alphafold to predict very large proteins

The AI tool Alphafold has been improved so that it can now predict the shape of very large and complex protein structures. Linköping University researchers have also succeeded in integrating experimental data into the tool.

Rinata Kazak looking down at her jacket.

LiU researcher ahead of UN climate summit - "I’m optimistic"

Azerbaijan will host the International Climate Summit this year. Although the country is heavily dependent on its oil production, holding the meeting there could actually be an advantage, according to Rinata Kazak, who will represent LiU.

Two women at a table talking.

Working together for a less biased world

In what ways does modern technology risk giving us a distorted picture of the world? Seeking answers, researchers at Tema Genus are working with colleagues in computer science.