Differentially Constrained Mobile Robot Motion Planning in State Lattices

Mihail Pivtoraiko, Ross A. Knepper, and Alonzo Kelly. Differentially Constrained Mobile Robot Motion Planning in State Lattices. Journal of Field Robotics, 26(3):308–333, John Wiley and Sons Ltd., Chichester, UK, 2009.

Download

[5.0MB pdf]  [ps.gz]  [ps]  [HTML] 

Abstract

We present an approach to the problem of differentially constrained mobile robot motion planning in arbitrary cost fields. The approach is based on deterministic search in a specially discretized state space. We compute a set of elementary motions that connects each discrete state value to a set of its reachable neighbors via feasible motions. Thus, this set of motions induces a connected search graph. The motions are carefully designed to terminate at discrete states, whose dimensions include relevant state variables (e.g., position, heading, curvature, and velocity). The discrete states, and thus the motions, repeat at regular intervals, forming a lattice. We ensure that all paths in the graph encode feasible motions via the imposition of continuity constraints on state variables at graph vertices and compliance of the graph edges with a differential equation comprising the vehicle model. The resulting state lattice permits fast full configuration space cost evaluation and collision detection. Experimental results with research prototype rovers demonstrate that the planner allows us to exploit the entire envelope of vehicle maneuverability in rough terrain, while featuring real-time performance. © 2009 Wiley Periodicals, Inc.

BibTeX

@ARTICLE{pivtoraiko_knepper_kelly_jfr09,
  author = {Mihail Pivtoraiko and Ross A. Knepper and Alonzo Kelly},
  title = {Differentially Constrained Mobile Robot Motion Planning in State
	Lattices},
  journal = {Journal of Field Robotics},
  year = {2009},
  volume = {26},
  pages = {308--333},
  number = {3},
  abstract = {We present an approach to the problem of differentially
                  constrained mobile robot motion planning in
                  arbitrary cost fields. The approach is based on
                  deterministic search in a specially discretized
                  state space. We compute a set of elementary motions
                  that connects each discrete state value to a set of
                  its reachable neighbors via feasible motions. Thus,
                  this set of motions induces a connected search
                  graph.  The motions are carefully designed to
                  terminate at discrete states, whose dimensions
                  include relevant state variables (e.g., position,
                  heading, curvature, and velocity). The discrete
                  states, and thus the motions, repeat at regular
                  intervals, forming a lattice. We ensure that all
                  paths in the graph encode feasible motions via the
                  imposition of continuity constraints on state
                  variables at graph vertices and compliance of the
                  graph edges with a differential equation comprising
                  the vehicle model. The resulting state lattice
                  permits fast full configuration space cost
                  evaluation and collision detection. Experimental
                  results with research prototype rovers demonstrate
                  that the planner allows us to exploit the entire
                  envelope of vehicle maneuverability in rough
                  terrain, while featuring real-time
                  performance. © 2009 Wiley Periodicals, Inc.},
  address = {Chichester, UK},
  bib2html_pubtype = {Journal Papers},
  bib2html_rescat = {Kinodynamic Planning},
  doi = {10.1002/rob.v26:3},
  issn = {1556-4959},
  publisher = {John Wiley and Sons Ltd.}
}