Arrow Research search

Author name cluster

Stefan Funke

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

20 papers
2 author rows

Possible papers

20

IJCAI Conference 2025 Conference Paper

Fast and Stronger Lower Bounds for Planar Euclidean Shortest Paths

  • Stefan Funke
  • Daniel Koch
  • Claudius Proissl
  • Christian Staib
  • Felix Weitbrecht

We consider the problem of quickly providing strong lower bounds for the planar Euclidean shortest path (ESP) problem. Such lower bounds are crucial for guiding the search in A* type approaches or for proving quality guarantees for algorithms that compute approximate solutions. Our contributions are two-fold: we show how to simplify ESP instances such that computing and storing a visibility graph becomes feasible while distances within the simplified instance are guaranteed to constitute lower bounds for the original problem instance. Furthermore we show how to precompute a space efficient data structure that allows to perform distance queries on visibility graphs within few microseconds with negligible space overhead.

PDF Details DOI

IJCAI Conference 2024 Conference Paper

Scalable Ultrafast Almost-optimal Euclidean Shortest Paths

  • Stefan Funke
  • Daniel Koch
  • Claudius Proissl
  • Axel Schneewind
  • Armin Weiß
  • Felix Weitbrecht

We consider the problem of computing high-quality Euclidean shortest paths amidst obstacles on a large scale. By transferring and adapting speed-up techniques from the road network setting, we are able to compute source target paths for problem instances with several million obstacle vertices within few milliseconds after moderate preprocessing. We show experimentally that for small instances where optimal solutions are easily available on average our computed paths are less than 0. 3% longer than the optimum. For large instances a new lower-bounding technique shows that on average our computed paths are less than 2% longer than the optimum paths. We compare our approach with the current state-of-the-art on problem instances derived from the OpenStreetMap project.

PDF Details DOI

SoCS Conference 2019 Conference Paper

Algorithms for Average Regret Minimization

  • Sabine Storandt
  • Stefan Funke

In this paper, we study a problem from the realm of multi-criteria decision making in which the goal is to select from a given set S of d-dimensional objects a minimum sized subset S

Details

AAAI Conference 2019 Conference Paper

Algorithms for Average Regret Minimization

  • Sabine Storandt
  • Stefan Funke

In this paper, we study a problem from the realm of multicriteria decision making in which the goal is to select from a given set S of d-dimensional objects a minimum sized subset S′ with bounded regret. Thereby, regret measures the unhappiness of users which would like to select their favorite object from set S but now can only select their favorite object from the subset S′. Previous work focused on bounding the maximum regret which is determined by the most unhappy user. We propose to consider the average regret instead which is determined by the sum of (un)happiness of all possible users. We show that this regret measure comes with desirable properties as supermodularity which allows to construct approximation algorithms. Furthermore, we introduce the regret minimizing permutation problem and discuss extensions of our algorithms to the recently proposed k-regret measure. Our theoretical results are accompanied with experiments on a variety of inputs with d up to 7.

PDF Details

AAAI Conference 2018 Conference Paper

Sublinear Search Spaces for Shortest Path Planning in Grid and Road Networks

  • Johannes Blum
  • Stefan Funke
  • Sabine Storandt

Shortest path planning is a fundamental building block in many applications. Hence developing efficient methods for computing shortest paths in e. g. road or grid networks is an important challenge. The most successful techniques for fast query answering rely on preprocessing. But for many of these techniques it is not fully understood why they perform so remarkably well and theoretical justification for the empirical results is missing. An attempt to explain the excellent practical performance of preprocessing based techniques on road networks (as transit nodes, hub labels, or contraction hierarchies) in a sound theoretical way are parametrized analyses, e. g. , considering the highway dimension or skeleton dimension of a graph. But these parameters tend to be large (order of Θ( √ n)) when the network contains grid-like substructures – which inarguably is the case for real-world road networks around the globe. In this paper, we use the very intuitive notion of bounded growth graphs to describe road networks and also grid graphs. We show that this model suffices to prove sublinear search spaces for the three above mentioned stateof-the-art shortest path planning techniques. For graphs with a large highway or skeleton dimension, our results turn out to be superior. Furthermore, our preprocessing methods are close to the ones used in practice and only require randomized polynomial time.

PDF Details

AAAI Conference 2017 Conference Paper

The Simultaneous Maze Solving Problem

  • Stefan Funke
  • Andre Nusser
  • Sabine Storandt

A grid maze is a binary matrix where fields containing a 0 are accessible while fields containing a 1 are blocked. A movement sequence consists of relative movements up, down, left, right – moving to a blocked field results in non-movement. The simultaneous maze solving problem asks for the shortest movement sequence starting in the upper left corner and visiting the lower right corner for all mazes of size n × m (for which a path from the upper left to the lower right corner exists at all). We present a theoretical problem analysis, including hardness results and a cubic upper bound on the sequence length. In addition, we describe several approaches to practically compute solving sequences and lower bounds despite the high combinatorial complexity of the problem.

PDF Details

SoCS Conference 2016 Conference Paper

Consistent Rounding of Edge Weights in Graphs

  • Stefan Funke
  • Sabine Storandt

Often, the edge weights of graphs are given in implicitly infinite or overly high precision (think of Euclidean lengths) which leads to both theoretical as well as practical challenges. In this paper we investigate how to round edge weights of a given graph G(V, E, w) such that the rounded weights of paths satisfy certain consistency criteria. Natural consistency criteria are, for example, preserving optimality of paths, and bounding relative change in weight after the rounding procedure. Low precision edge weights allow for more space efficient implementations, faster arithmetic operations, and in general more stable and efficient algorithms. We present an ILP based rounding approach as well as a greedy rounding heuristic. We show experimentally for large road networks and grid graphs that our new rounding approaches are significantly better than common deterministic or randomized rounding schemes.

Details

ICAPS Conference 2016 Conference Paper

Placement of Loading Stations for Electric Vehicles: Allowing Small Detours

  • Stefan Funke
  • André Nusser
  • Sabine Storandt

We consider the problem of covering a street network with loading stations for electric vehicles (EVs) such that EVs can travel along shortest paths and only require small detours (e. g. , at most 3 km) to recharge along the route. We show that this problem can be formulated as a Hitting Set problem. Unfortunately, it turns out that even the explicit problem instance construction requires too much time and space to be practical. Therefore, we develop several approximation algorithms and heuristics to solve the problem. Our experiments show that even though small, the allowed detours lead to a considerable reduction in the number of required loading stations. Moreover, we devise an algorithm for planning high-quality EV-routes in a network with loading stations placed by our approach. We empirically show the usability of the routes by evaluating the number of reloading stops and the actually induced detour.

Details

JAIR Journal 2015 Journal Article

Placement of Loading Stations for Electric Vehicles: No Detours Necessary!

  • Stefan Funke
  • Andre Nusser
  • Sabine Storandt

Compared to conventional cars, electric vehicles (EVs) still suffer from considerably shorter cruising ranges. Combined with the sparsity of battery loading stations, the complete transition to E-mobility still seems a long way to go. In this paper, we consider the problem of placing as few loading stations as possible so that on any shortest path there are sufficiently many not to run out of energy. We show how to model this problem and introduce heuristics which provide close-to-optimal solutions even in large road networks.

PDF Details DOI

AAAI Conference 2014 Conference Paper

Placement of Loading Stations for Electric Vehicles: No Detours Necessary!

  • Stefan Funke
  • Andre Nusser
  • Sabine Storandt

Compared to conventional cars, electric vehicles still suffer from a considerably shorter cruising range. Combined with the sparsity of battery loading stations, the complete transition to E-mobility still seems a long way to go. In this paper, we consider the problem of placing as few loading stations as possible such that on any shortest path there are enough to guarantee sufficient energy supply. This means, that EV owners no longer have to plan their trips ahead incorporating loading station locations, and are no longer forced to accept long detours to reach their destinations. We show how to model this problem and introduce heuristics which provide close-to-optimal solutions even in large road networks.

PDF Details

SoCS Conference 2013 Conference Paper

Polynomial-Time Construction of Contraction Hierarchies for Multi-Criteria Objectives

  • Stefan Funke
  • Sabine Storandt

In this paper we consider a variant of the multi-criteria shortest path problem where the different criteria are combined in an arbitrary conic combination at query time. We show that contraction hierarchies (CH) — a very powerful speed-up technique originally developed for standard shortest path queries (Geisberger et al. 2008) — can be adapted to this scenario and lead - after moderate preprocessing effort - to query times that are orders of magnitudes faster than standard shortest path approaches. On the theory side we prove via some polyhedral considerations that the crucial node contraction operation during the CH construction can be performed in polynomial-time, while on the more practical side we complement our theoretical results with experiments on real-world data. Our approach extends previous results (Geisberger, Kobitzsch, and Sanders 2010) which only considered the bicriteria case. This is an extended abstract of the full paper published in (Funke and Storandt 2013).

Details

AAAI Conference 2012 Conference Paper

Cruising with a Battery-Powered Vehicle and Not Getting Stranded

  • Sabine Storandt
  • Stefan Funke

The main hindrance to a widespread market penetration of battery-powered electric vehicles (BEVs) has been their limited energy reservoir resulting in cruising ranges of few hundred kilometers unless one allows for recharging or switching of depleted batteries during a trip. Unfortunately, recharging typically takes several hours and battery switch stations providing fully recharged batteries are still quite rare – certainly not as widespread as ordinary gas stations. For not getting stranded with an empty battery, going on a BEV trip requires some planning ahead taking into account energy characteristics of the BEV as well as available battery switch stations. In this paper we consider very basic, yet fundamental problems for E-Mobility: Can I get from A to B and back with my BEV without recharging in between? Can I get from A to B when allowed to recharge? How can I minimize the number of battery switches when going from A to B? We provide efficient and mathematically sound algorithms for these problems that allow for the energy-aware planning of trips.

PDF Details

AAAI Conference 2011 Conference Paper

Optimal Route Planning for Electric Vehicles in Large Networks

  • Jochen Eisner
  • Stefan Funke
  • Sabine Storandt

We consider the problem of routing electric vehicles (EV) in the most energy-efficient way within a road network taking into account both their limited energy supply as well as their ability to recuperate energy. Employing a classical result by Johnson and an observation about Dijkstra under nonconstant edge costs we obtain O(n log n+m) query time after a O(nm) preprocessing phase for any road network graph whose edge costs represent energy consumption or recuperation. If the energy recuperation is height induced in a very natural way, the preprocessing phase can even be omitted. We then adapt a technique for speeding-up (unconstrained) shortest path queries to our scenario to achieve a speed-up of another factor of around 20. Our results drastically improve upon the recent results in (Artmeier et al. 2010) and allow for route planning of EVs in an instant even on large networks.

PDF Details