EFFICIENT CONSTRAINED PATH PLANNING VIA SEARCH IN STATE LATTICES

摘要

We propose a novel approach to constrained path planningrnthat is based on a special search space which effi-rnciently encodes feasible paths. The paths are encodedrnimplicitly as connections between states, but only feasiblernand local connections are included. Once this searchrnspace is developed, we systematically generate a nearminimalrnset of spatially distinct path primitives. This setrnexpresses the local connectivity of constrained motionsrnand also eliminates redundancies. The set of primitives isrnused to define heuristic search, and thereby create a veryrnefficient path planner at the chosen resolution. We alsorndiscuss a wide variety of space and terrestrial roboticsrnapplications where this motion planner can be especiallyrnuseful.