Differentially Constrained Motion Replanning using State Lattices with Graduated Fidelity

Mihail Pivtoraiko and Alonzo Kelly. Differentially Constrained Motion Replanning using State Lattices with Graduated Fidelity. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2611–2616, September 2008.

Download

[963.2kB pdf]  [ps.gz]  [ps]  [HTML] 

Abstract

This paper presents an approach to differentially constrained robot motion planning and efficient re-planning. Satisfaction of differential constraints is guaranteed by the state lattice, a 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 to modify 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. In this setting, we applied the planner successfully to the navigation of research prototype rovers in JPL Mars Yard.

BibTeX

@INPROCEEDINGS{pivtoraiko_kelly_iros08,
  author = {Mihail Pivtoraiko and Alonzo Kelly},
  title = {Differentially Constrained Motion Replanning using State Lattices
	with Graduated Fidelity},
  booktitle = {Proceedings of the IEEE/RSJ International Conference on Intelligent
	Robots and Systems},
  year = {2008},
  pages = {2611--2616},
  month = {September},
  abstract = {This paper presents an approach to differentially
                  constrained robot motion planning and efficient
                  re-planning.  Satisfaction of differential
                  constraints is guaranteed by the state lattice, a
                  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 to modify
                  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. In this setting, we applied the
                  planner successfully to the navigation of research
                  prototype rovers in JPL Mars Yard.},
  bib2html_pubtype = {Refereed Conference Papers},
  bib2html_rescat = {Kinodynamic Planning},
  doi = {10.1109/IROS.2008.4651220}
}