Path planning in practice; lazy evaluation on a multi-resolution grid

Abstract

We present a resolution complete path planner based on an implicit grid in the configuration space. The planner can be described as a two-level process in which a global planner restricts a local planner to certain subsets of the grid. The global planner starts by letting the local planner search in a coarse subset of the grid, and successively refines the grid until a solution is found. The local planner applies a scheme for lazy evaluation on each subgrid in order to minimize collision checking and thereby increase the performance. Experimental results in an industrial application show that lazy evaluation on a grid is very efficient in practice. The algorithm is particularly useful in high dimensional, relatively uncluttered configuration spaces, especially when collision checking is computationally expensive. Single queries are handled quickly since no preprocessing is required.