Graduated Fidelity Motion Planning

Mihail Pivtoraiko and Alonzo Kelly. Graduated Fidelity Motion Planning. In Proceedings of the International Symposium on Combinatorial Search, 2011.

Download

(unavailable)

Abstract

This paper presents an approach to differentially constrained robot motion planning and efficient replanning. 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 replan rate on minimal computing hardware [2], while satisfying the car-like differential constraints.

BibTeX

@INPROCEEDINGS{pivtoraiko_kelly_socs11,
  author = {Mihail Pivtoraiko and Alonzo Kelly},
  title = {Graduated Fidelity Motion Planning},
  booktitle = {Proceedings of the International Symposium on Combinatorial Search},
  year = {2011},
  abstract = { This paper presents an approach to differentially
                  constrained robot motion planning and efficient
                  replanning. 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
                  replan rate on minimal computing hardware [2], while
                  satisfying the car-like differential constraints. },
  bib2html_pubtype = {Refereed Conference Papers},
  bib2html_rescat = {Kinodynamic Planning}
}