Optimal, Smooth, Nonholonomic Mobile Robot Motion Planning in State Lattices

Mihail Pivtoraiko, Ross A. Knepper, and Alonzo Kelly. Optimal, Smooth, Nonholonomic Mobile Robot Motion Planning in State Lattices. Technical Report CMU-RI-TR-07-15, Robotics Institute, Carnegie Mellon University, 2007.

Download

[2.4MB pdf] 

Abstract

We present an approach to the problem of mobile robot motion planning in arbitrary cost fields subject to differential constraints. Given a model of vehicle maneuverability, a trajectory generator solves the two point boundary value problem of connecting two points in state space with a feasible motion. We use this capacity to compute a control set which connects any state to its reachable neighbors in a limited neighborhood. Equivalence classes of paths are used to implement a path sampling policy which preserves expressiveness while eliminating redundancy. The implicit repetition of the resulting minimal control set throughout state space produces a reachability graph that encodes all feasible motions consistent with this sampling policy. The graph encodes only feasible motions by construction and, by appropriate choice of state space dimension, can permit full configuration space collision detection while imposing heading and curvature continuity constraints at nodes. Nonholonomic constraints are satisfied by construction in the trajectory generator. We also use the trajectory generator to compute an ideal admissible heuristic and significantly improve planning efficiency. Comparisons to classical grid search and nonholonomic motion planners show the planner provides better plans or provides them faster or both. Applications to planetary rovers and terrestrial unmanned ground vehicles are illustrated.

BibTeX

@TECHREPORT{pivtoraiko_knepper_kelly_tr07,
  author = {Mihail Pivtoraiko and Ross A. Knepper and Alonzo Kelly},
  title = {Optimal, Smooth, Nonholonomic Mobile Robot Motion Planning in State
	Lattices},
  institution = {Robotics Institute, Carnegie Mellon University},
  year = {2007},
  number = {CMU-RI-TR-07-15},
  abstract = {We present an approach to the problem of mobile robot
                  motion planning in arbitrary cost fields subject to
                  differential constraints. Given a model of vehicle
                  maneuverability, a trajectory generator solves the
                  two point boundary value problem of connecting two
                  points in state space with a feasible motion. We use
                  this capacity to compute a control set which
                  connects any state to its reachable neighbors in a
                  limited neighborhood.  Equivalence classes of paths
                  are used to implement a path sampling policy which
                  preserves expressiveness while eliminating
                  redundancy. The implicit repetition of the resulting
                  minimal control set throughout state space produces
                  a reachability graph that encodes all feasible
                  motions consistent with this sampling policy.  The
                  graph encodes only feasible motions by construction
                  and, by appropriate choice of state space dimension,
                  can permit full configuration space collision
                  detection while imposing heading and curvature
                  continuity constraints at nodes. Nonholonomic
                  constraints are satisfied by construction in the
                  trajectory generator. We also use the trajectory
                  generator to compute an ideal admissible heuristic
                  and significantly improve planning efficiency.
                  Comparisons to classical grid search and
                  nonholonomic motion planners show the planner
                  provides better plans or provides them faster or
                  both. Applications to planetary rovers and
                  terrestrial unmanned ground vehicles are
                  illustrated.},
  bib2html_pubtype = {Tech Reports},
  bib2html_rescat = {Kinodynamic Planning},
  owner = {mihail},
  timestamp = {2010.08.07}
}

Generated by bib2html.pl (written by Patrick Riley ) on Wed May 15, 2013 18:16:05