Arrow Research search

Author name cluster

Sabine Storandt

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.

22 papers
2 author rows

Possible papers

22

IJCAI Conference 2024 Conference Paper

Scalable Landmark Hub Labeling for Optimal and Bounded Suboptimal Pathfinding

  • Sabine Storandt

Hub Labeling and A* are two well-established algorithms for shortest path computation in large graphs. Hub Labeling offers excellent query times for distance computation, but at the cost of a high space consumption for label storage. Landmark-based A* search requires less space but answers queries much slower. Recently, Landmark Hub Labeling (LHL) has been proposed, which combines both concepts and achieves a smaller space consumption than Hub Labeling and also much better query times than A*. However, the known algorithms for computing a LHL do not scale to large graphs, limiting its applicability. In this paper, we devise novel algorithms for LHL construction that work on graphs with millions of edges. We also further improve the LHL query answering algorithm and investigate how to reduce the space consumption of labeling techniques by performing bounded suboptimal pathfinding. In an extensive experimental study, we demonstrate the effectiveness of our methods and illuminate that sensible trade-offs between space consumption, query time, and path quality can be achieved with LHL.

PDF Details DOI

ICAPS Conference 2023 Conference Paper

Convexity Hierarchies in Grid Networks

  • Johannes Blum 0001
  • Ruoying Li 0001
  • Sabine Storandt

Several algorithms for path planning in grid networks rely on graph decomposition to reduce the search space size; either by constructing a search data structure on the components, or by using component information for A* guidance. The focus is usually on obtaining components of roughly equal size with few boundary nodes each. In this paper, we consider the problem of splitting a graph into convex components. A convex component is characterized by the property that for all pairs of its members, the shortest path between them is also contained in it. Thus, given a source node, a target node, and a (small) convex component that contains both of them, path planning can be restricted to this component without compromising optimality. We prove that it is NP-hard to find a balanced node separator that splits a given graph into convex components. However, we also present and evaluate heuristics for (hierarchical) convex decomposition of grid networks that perform well across various benchmarks. Moreover, we describe how existing path planning methods can benefit from the computation of convex components. As one main outcome, we show that contraction hierarchies become up to an order of magnitude faster on large grids when the contraction order is derived from a convex graph decomposition.

Details

IJCAI Conference 2021 Conference Paper

Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks (Extended Abstract)

  • Tenindra Abeywickrama
  • Muhammad Aamir Cheema
  • Sabine Storandt

A k nearest neighbors (kNN) query finds k closest points-of-interest (POIs) from an agent's location. In this paper, we study a natural extension of the kNN query for multiple agents, namely, the Aggregate k Nearest Neighbors (AkNN) query. An AkNN query retrieves k POIs with the smallest aggregate distances where the aggregate distance of a POI is obtained by aggregating its distances from the multiple agents (e. g. , sum of its distances from each agent). We propose a novel data structure COLT (Compacted Object-Landmark Tree) which enables efficient hierarchical graph traversal and utilize it to efficiently answer AkNN queries. Our experiments on real-world and synthetic data sets show that our techniques outperform existing approaches by more than an order of magnitude in almost all settings.

PDF Details DOI

ICAPS Conference 2020 Conference Paper

Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks

  • Tenindra Abeywickrama
  • Muhammad Aamir Cheema
  • Sabine Storandt

Location-based services rely heavily on efficient methods that search for relevant points-of-interest (POIs) close to a given location. A k nearest neighbors (kNN) query is one such example that finds k closest POIs from an agent's location. While most existing techniques focus on finding nearby POIs for a single agent, many applications require POIs that are close to multiple agents. In this paper, we study a natural extension of the kNN query for multiple agents, namely, the Aggregate k Nearest Neighbors (AkNN) query. An AkNN query retrieves k POIs with the smallest aggregate distances where the aggregate distance of a POI is obtained by aggregating its distances from the multiple agents (e. g. , sum of its distances from each agent). Existing search heuristics are designed for a single agent and do not work well for multiple agents. We propose a novel data structure COLT (Compacted Object-Landmark Tree) to address this gap by enabling efficient hierarchical graph traversal. We then utilize COLT for a wide range of aggregate functions to efficiently answer AkNN queries. In our experiments on real-world and synthetic data sets, our techniques significantly improve query performance, typically outperforming existing approaches by more than an order of magnitude in almost all settings.

Details

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

ICML Conference 2019 Conference Paper

Improved Dynamic Graph Learning through Fault-Tolerant Sparsification

  • Chun Jiang Zhu
  • Sabine Storandt
  • Kam-yiu Lam
  • Song Han 0002
  • Jinbo Bi

Graph sparsification has been used to improve the computational cost of learning over graphs, e. g. , Laplacian-regularized estimation and graph semi-supervised learning (SSL). However, when graphs vary over time, repeated sparsification requires polynomial order computational cost per update. We propose a new type of graph sparsification namely fault-tolerant (FT) sparsification to significantly reduce the cost to only a constant. Then the computational cost of subsequent graph learning tasks can be significantly improved with limited loss in their accuracy. In particular, we give theoretical analyze to upper bound the loss in the accuracy of the subsequent Laplacian-regularized estimation and graph SSL, due to the FT sparsification. In addition, FT spectral sparsification can be generalized to FT cut sparsification, for cut-based graph learning. Extensive experiments have confirmed the computational efficiencies and accuracies of the proposed methods for learning on dynamic graphs.

Details

ICAPS Conference 2019 Conference Paper

The Clustered Dial-a-Ride Problem

  • Fabian Feitsch
  • Sabine Storandt

We study a variant of the classical dial-a-ride problem, with an application to public transport planning in rural areas. In the classical dial-a-ride problem, n users each specify a pickup and a delivery location, and the aim is to plan the least cost route to cater all requests. This can be modeled as a traveling salesmen problem in a complete graph with precedence constraints (pick-ups need to happen before deliveries). In this paper, we consider the clustered dial-a-ride problem, where we do not operate on a complete graph but on a graph composed of serially numbered cliques where each clique is connected to the next one via a single edge. This setting is inspired by door-to-door transportation for people from remote villages who want to get to another village or the next city by a bus which operates on demand. We argue that in case the optimal route exhibits certain structural properties, it can be computed significantly faster. To make use of this observation, we devise a classification algorithm which can decide whether the optimal route exhibits these structural properties before computing it. Extensive experiments on artificial and real-world instances reveal that the majority of optimal routes indeed have the desired properties and that our classifier is an efficient tool to recognize the respective instances.

Details

ICAPS Conference 2018 Conference Paper

Scalability of Route Planning Techniques

  • Johannes Blum 0001
  • Sabine Storandt

In this paper, we thoroughly analyze the scaling behavior of several state-of-the-art route planning techniques for road networks, all of which rely on preprocessing. One goal is to determine which technique is most suitable to be used on huge networks. To be able to conduct scalability studies in a clean way, we first describe a new kind of road network generator that allows to produce road networks even larger than that of our planet with similar properties as real networks. We then carefully implement several preprocessing-based route planning techniques, as contraction hierarchies, hub labels and transit nodes, to study their space consumption as well as their search spaces in different sized networks. This allows to derive functions that describe their empirical scaling behavior for the first time. We also compare our functions to existing theoretical bounds. We show that several of our results can not be sufficiently explained by the theoretical investigations conducted so far. Hence our results encourage a further look for road network models that allow for better predictions.

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

AAAI Conference 2013 Conference Paper

Enabling E-Mobility: Facility Location for Battery Loading Stations

  • Sabine Storandt
  • Stefab Funke

The short cruising range due to the limited battery supply of current Electric Vehicles (EVs) is one of the main obstacles for a complete transition to E-mobility. Until batteries of higher energy storage density have been developed, it is of utmost importance to deliberately plan the locations of new loading stations for best possible coverage. Ideally the network of loading stations should allow driving from anywhere to anywhere (and back) without running out of energy. We show that minimizing the number of necessary loading stations to achieve this goal is NP-hard and even worse, we can rule out polynomial-time constant approximation algorithms. Hence algorithms with better approximation guarantees have to make use of the special structure of road networks (which is not obvious how to do it). On the positive side, we show with instance based lower bounds that our heuristic algorithms achieve provably good solutions on real-world problem instances.

PDF Details

SoCS Conference 2013 Conference Paper

Frequency Data Compression for Public Transportation Network Algorithms (Extended Abstract)

  • Hannah Bast
  • Sabine Storandt

Timetable information in public transportation networks exhibit a large degree of redundancy; e. g. consider a bus going from station A to station B at 6: 00, 6: 15, 6: 30, 6: 45, 7: 00, 7: 15, 7: 30, .. ., 20: 00, the very same data can be provided by a frequency-based representation as ’6: 00-20: 00, every 15 minutes’ in considerably less space. Nevertheless a common graph model for routing in public transportation networks is the time-expanded representation where for each arrival/departure event a single node is created. We will introduce a frequency-based graph model which allows for a significantly more compact representation of the network, resulting also in a speed-up for station-to-station queries. Moreover we will describe a new variant of Dijkstra’s algorithm, where also the labels are frequency-based. This approach allows for accelerating profile queries in public transportation networks.

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

SoCS Conference 2013 Conference Paper

The Hierarchy in Grid Graphs (Extended Abstract)

  • Sabine Storandt

Many speed-up techniques developed for accelerating the computation of shortest paths in road networks, like reach or contraction hierarchies, are based on the property that some streets are ’more important’ than others, e. g. on long routes the usage of an interstate is almost inevitable. In grids there is no obvious hierarchy among the edges, especially if the costs are uniform. Nevertheless we will show that contraction hierarchies can be applied to grid graphs as well. We will point out interesting connections to speed-up techniques shaped for routing on grids, like swamp hierarchies and jump points, and provide experimental results for game maps, mazes, random grids and rooms.

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

ICAPS Conference 2012 Conference Paper

Route Planning for Bicycles - Exact Constrained Shortest Paths Made Practical via Contraction Hierarchy

  • Sabine Storandt

We consider the problem of computing shortest paths subject to an additional resource constraint such as a hard limit on the (positive) height difference of the path. This is typically of interest in the context of bicycle route planning, or when energy consumption is to be limited. So far, the exact computation of such constrained shortest paths was not feasible on large networks; we show that state-of-the-art speed-up techniques for the shortest path problem, like contraction hierarchies, can be instrumented to solve this problem efficiently in practice despite the NP-hardness in general.

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