Fredrik Präntare. Photo credit: Susanna Lönnqvist.

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.

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, WASP PhD student in the Department of Computer and Information Science at Linköping university, has developed an algorithm that determines who is to work with whom, in order to complete several specified tasks.

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 10 to the power of 1000 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).

Published: December 10th, 2018

Latest news

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners. View more
Cookies settings
Privacy & Cookie policy
Privacy & Cookies policy
Cookie name Active
The WASP website uses cookies. Cookies are small text files that are stored on a visitor’s computer and can be used to follow the visitor’s actions on the website. There are two types of cookie:
  • permanent cookies, which remain on a visitor’s computer for a certain, pre-determined duration,
  • session cookies, which are stored temporarily in the computer memory during the period under which a visitor views the website. Session cookies disappear when the visitor closes the web browser.
Permanent cookies are used to store any personal settings that are used. If you do not want cookies to be used, you can switch them off in the security settings of the web browser. It is also possible to set the security of the web browser such that the computer asks you each time a website wants to store a cookie on your computer. The web browser can also delete previously stored cookies: the help function for the web browser contains more information about this. The Swedish Post and Telecom Authority is the supervisory authority in this field. It provides further information about cookies on its website,
Save settings
Cookies settings