Home  | Publications | SFS19

Scaling the Dynamic Resource Routing Problem

MCML Authors

Link to Profile Matthias Schubert PI Matchmaking

Matthias Schubert

Prof. Dr.

Principal Investigator

Spatial Artificial Intelligence

Abstract

Routing to a resource (e.g. a parking spot or charging station) is a probabilistic search problem due to the uncertainty as to whether the resource is available at the time of arrival or not. In recent years, more and more real-time information about the current state of resources has become available in order to facilate this task. Therefore, we consider the case of a driver receiving online updates about the current situation. In this setting, the problem can be described as a fully observable Markov Decision Process (MDP) which can be used to compute an optimal policy minimizing the expected search time. However, current approaches do not scale beyond a dozen resources in a query. In this paper, we suggest to adapt common approximate solutions for solving MDPs. We propose a new re-planning and hindsight planning algorithm that redefine the state space and rely on novel cost estimations to find close to optimal results. Unlike exact solutions for computing MDPs, our approximate planers can scale up to hundreds of resources without prohibitive computational costs. We demonstrate the result quality and the scalability of our approaches on two settings describing the search for parking spots and charging stations in an urban environment.

inproceedings

SSTD 2019

16th International Symposium on Spatial and Temporal Databases. Vienna, Austria, Aug 19-21, 2019.

Authors

S. Schmoll • S. Friedl • M. Schubert

Links

DOI

Research Area

 A3 | Computational Models

BibTeXKey: SFS19

Back to Top