Industry project: Scalable online machine learning algorithms for shortest path problems with stochastic weights (*)

Potential supervisors: 
Research groups/keywords: 
Description: 

Shortest path problems are present in many different domains, such as in-car navigation systems or computer network routing. When dealing with real-world networks, the costs associated with links in the network may be stochastic instead of fixed. If the cost distributions are known, it is possible to solve the shortest path algorithm using a standard shortest path algorithm with respect to, e.g., the mean costs of all links in the network. When they are not initially known, however, it may be desirable to continuously learn the distribution parameters by observing the costs incurred from tried paths. 

To use the resources available for this in an efficient way, the problem can be modelled as a sequential decision-making problem. Specifically, one can cast this as a combinatorial version of the classical multi-armed bandit problem. In order to collect enough data to find paths expected to minimize incurred costs, some exploration is often required. On the other hand, too much exploration incurs excessive costs. This trade-off has previously been addressed through variants of well-known bandit algorithms like Thompson Sampling and UCB1, adapted for online shortest path problems with both empirical and theoretical success [1]. 

However, these methods typically depend on applying standard shortest path algorithms on networks with link weights modified in various ways to encourage exploration. While they work well for small or moderately sized networks, they are not viable for large networks. Algorithms for real-world settings (e.g., navigation) often use computationally heavy initial pre-processing phases performed once, to enable faster real-time queries afterwards. The purpose of this project is to develop scalable online shortest path algorithms, usable on large-scale graphs.

References

[1] Åkerblom, N., Chen, Y., & Haghir Chehreghani, M. (2020). An Online Learning Framework for Energy-Efficient Navigation of Electric Vehicles. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20 (pp. 2051–2057). International Joint Conferences on Artificial Intelligence Organization. 

Requirements

  • Studies computer science, data science, engineering physics, mathematics, or similar
  • Courses in machine learning and AI, Algorithms and Statistics/Mathematics
  • Good programming skills (e.g., Java, C++)
  • Motivated, creative, focused and has problem-solving skills
  • Number of students: 1-2 (preferably two)

The thesis work is conducted in collaboration with Volvo. You will apply for the thesis work through a system at Volvo:   https://jobs.volvocars.com/job/Gothenburg-Thesis-Work-At-Safe-Vehicle-Automation-%28SVA%29/725971601/?locale=en_US

(*) This project is not available during November 2021 and October 2022.

Date range: 
September, 2021 to September, 2023