Graduated Fidelity Motion Planning

Abstract

This paper presents an approach to differentially constrained robot motion planning and efficient re-planning. Satisfaction of differential constraints is guaranteed by the search space which consists of motions that satisfy the constraints by construction. Any systematic replanning algorithm, e.g. D*, can be utilized to search the state lattice to find a motion plan that satisfies the differential constraints, and to repair it efficiently in the event of a change in the environment. Further efficiency is obtained by varying the fidelity of representation of the planning problem. High fidelity is utilized where it matters most, while it is lowered in the areas that do not affect the quality of the plan significantly. The paper presents a method of modifying the fidelity between replans, thereby enabling dynamic flexibility of the search space, while maintaining its compatibility with replanning algorithms. The approach is especially suited for mobile robotics applications in unknown challenging environments. We successfully applied the motion planner on a real robot: the planner featured 10Hz average replan rate on minimal computing hardware, while satisfying the car-like differential constraints.