  We present a novel approach for motion planning in mobile robotics under
sensing and motion uncertainty based on state lattices with graduated fidelity.
The probability of collision is reliably estimated considering the robot shape,
and the fidelity adapts to the complexity of the environment, improving the
planning efficiency while maintaining the performance. Safe and optimal paths
are found with an informed search algorithm, for which a novel multi-resolution
heuristic is presented. Results for different scenarios and robot shapes are
given, showing the validity of the proposed methods.

Robotics;Artificial Intelligence