On the Application of the D* Search Algorithm to Time-Based Planning on Lattice Graphs
Martin Rufli, Roland Siegwart · Repository for Publications and Research Data (ETH Zurich) · 2009
In this paper we present a multi-resolution state lattice, which operates in four dimensions, namely 2D position, heading, and velocity.The generation of such a lattice is described, resulting in an efficient (in terms of branching factor) and feasible (i.e.directly executable) set of edges, which can be searched on using any standard graph based planner.Furthermore, we introduce a novel heuristic, the time-viable heuristic with horizon Tn, which exploits the limited (but nonetheless extremely large) number of feasible motion combinations in a state lattice of bounded time and stores them in a look-up table.This heuristic then enables recently developed incremental planning algorithms, which typically start node expansion at the goal state (such as the various D* variants [1]) to be employed in time-based search, where the time of arrival is generally unknown a priori.We show, that by employing this technique, on average a comparable number of expanded states are to be expected for a given initial planning problem as when using forward searching algorithms (such as A* and variants [2, 3]), thus speeding up re-planning by up to two orders of magnitude as reported in [4].