2023-07-01, Blum, Johannes, Li, Ruoying, Storandt, Sabine

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.

2021, Li, Ruoying, Storandt, Sabine, Müller, Uli, Weber, David

We present a holistic approach for pedestrian routing that allows computing shortest paths that may have indoor and outdoor sections. Such routes arise, for example, when the destination is not just an address but a specific store in a large mall, or when one needs to get to a certain track at a large train station. Currently, map services as Google Maps or OSRM do not offer such functionality. We identify and overcome three main challenges for answering such complex route planning queries: (i) Pedestrian routing requires fine-grained data, as the location of stairs and elevators, building dventrances, building footprints, and elevation/level information. A single missing staircase can change the length of the computed path severely. (ii) Indoor routing has to be integrated carefully into classical path planning to allow the computation of sensible routes that may enter and exit buildings. (iii) Given the large amount of data to be considered in a query, acceleration techniques need to be applied in order to achieve interactive query times. Retrieving barrier-free routes for wheelchairs is also our important use case.

2020, Blum, Johannes, Li, Ruoying, Storandt, Sabine

Given an undirected graph, a balanced node separator is a set of nodes whose removal splits the graph into connected components of limited size. Balanced node separators are used for graph partitioning, for the construction of graph data structures, and for measuring network reliability. It is NP-hard to decide whether a graph has a balanced node separator of size at most k. Therefore, practical algorithms typically try to find small separators in a heuristic fashion. In this paper, we present a branching algorithm that for a given value k either outputs a balanced node separator of size at most k or certifies that k is a valid lower bound. Using this algorithm iteratively for growing values of k allows us to find a minimum balanced node separator. To make this algorithm scalable to real-world (road) networks of considerable size, we first describe pruning rules to reduce the graph size without affecting the minimum balanced separator size. In addition, we prove several structural properties of minimum balanced node separators which are then used to reduce the branching factor and search depth of our algorithm. We experimentally demonstrate the applicability of our algorithm to graphs with thousands of nodes and edges. Finally, we showcase the usefulness of having minimum balanced separators for judging the quality of existing heuristics, for improving preprocessing-based route planning techniques on road networks, and for lower bounding important graph parameters.