Sampling-based planning for discrete spaces

In this paper, we introduce several discrete space search algorithms based on continuous-space motion planning techniques such as rapidly exploring random trees (RRTs) and probabilistic roadmaps (PRMs). We describe methods for adapting these algorithms for discrete use by replacing distance metrics with cost-to-go heuristic estimates and substituting local planners for straight-line connectivity. Finally, we explore coverage and optimality properties of these algorithms in discrete spaces.