Deformed State Lattice Planning

Abstract

Search-based planning that uses a state lattice has been successfully applied in many applications but its utility is limited when confronted with complex problems represented by a lattice with many nodes and edges with high branching factor. However, in many seemingly complex problems, proper “form-fitting” can reduce the number of nodes and edges needed to represent the problems, provides a concise state lattice and therefore simplifies the computation. This paper proposes a planning framework which strikes to identify concise representations of problems, creates such “form-fitting” state lattice on which a more concise search can take place. In a sense, we take a conventional state lattice and map it onto a deformed space, and then the motion primitives and heuristics follow. Since the contribution of the paper is not the search approach but rather the means by which the lattice is deformed, any search-based planner can then be easily changed to a corresponding deformed version with no increase in time complexity. This paper demonstrate the benifits of the approach which includes 1) planned path can be followed with few changes in motion primitives and thus can provide global smoothness of planned path; 2) fewer states are expanded and thus shorter time to search solution in state space is required, and 3) fewer states are expanded and thus less memory is required to save the state lattice. We demonstrate the benefit of the proposed approach in illustrative toy examples, as well as robot experiments.