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

Publications

2024

Fredrik Präntare (2024) Dividing the Indivisible: Algorithms, Empirical Advances, and Complexity Results for Value-Maximizing Combinatorial Assignment Problems

2021

Fredrik Präntare, Herman Appelgren, Fredrik Heintz (2021) Anytime Heuristic and Monte Carlo Methods for Large-Scale Simultaneous Coalition Structure Generation and Assignment THIRTY-FIFTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THIRTY-THIRD CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE AND THE ELEVENTH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, p. 11317-11324 Continue to DOI
Fredrik Präntare, Fredrik Heintz (2021) Hybrid Dynamic Programming for Simultaneous Coalition Structure Generation and Assignment PRIMA 2020: Principles and Practice of Multi-Agent Systems: 23rd International Conference, Nagoya, Japan, November 18–20, 2020, Proceedings, p. 19-33 Continue to DOI

2020

Fredrik Präntare, Mattias Tiger, David Bergström, Herman Appelgren, Fredrik Heintz (2020) Towards Utilitarian Combinatorial Assignment with Deep Neural Networks and Heuristic Algorithms
Veronika Domova, Erik Gärtner, Fredrik Präntare, Martin Pallin, Johan Källström, Nikita Korzhitskii (2020) Improving Usability of Search and Rescue Decision Support Systems: WARA-PS Case Study In proceedings of the 2020 25th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA), p. 1251-1254 Continue to DOI
Fredrik Präntare, Fredrik Heintz (2020) An anytime algorithm for optimal simultaneous coalition structure generation and assignment Autonomous Agents and Multi-Agent Systems, Vol. 34, Article 29 Continue to DOI

2018

Fredrik Präntare, Fredrik Heintz (2018) An Anytime Algorithm for Simultaneous Coalition Structure Generation and Assignment PRIMA 2018: Principles and Practice of Multi-Agent Systems: 21st International Conference, Tokyo, Japan, October 29-November 2, 2018, Proceedings, p. 158-174 Continue to DOI

2017

Fredrik Präntare, Ingemar Ragnemalm, Fredrik Heintz (2017) An Algorithm for Simultaneous Coalition Structure Generation and Task Assignment PRIMA 2017: Principles and Practice of Multi-Agent Systems 20th International Conference, Nice, France, October 30 – November 3, 2017, Proceedings, p. 514-522 Continue to DOI

Contact

Latest news from LiU

Female PhD student lectures to master's students in the lab.

From sketches to a robot with artificial intelligence

How do you develop a product with as little human involvement as possible? LiU students built a robot using generative artificial intelligence.

Iontronic pump in thin blood vessels.

More effective cancer treatment with iontronic pump

When low doses of cancer drugs are administered continuously near malignant brain tumours using so-called iontronic technology, cancer cell growth drastically decreases. This is demonstrated in experiments with bird embryos.

Electronic medicine – at the intersection of technology and medicine

Swedish researchers have developed a gel that can form a soft electrode capable of conducting electricity. In the long term, they aim to connect electronics to biological tissue, such as the brain.