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