The Robotics Institute

Carnegie Mellon Robotics Institute

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Keywords

mobile robot, state lattice, motion planning, nonholonomic, vehicle model, path sampling

Notes

Associated Project(s): Very Rough Terrain Nonholonomic Trajectory Generation and Motion Planning for Rovers

Number of pages: 49

Text Reference

Mikhail Pivtoraiko, Ross Alan Knepper, and Alonzo Kelly, "Optimal, Smooth, Nonholonomic Mobile Robot Motion Planning in State Lattices," tech. report CMU-RI-TR-07-15, Robotics Institute, Carnegie Mellon University, May, 2007

BibTeX Reference

@techreport{Pivtoraiko_2007_5753,
   author = "Mikhail Pivtoraiko and Ross Alan Knepper and Alonzo Kelly",
   title = "Optimal, Smooth, Nonholonomic Mobile Robot Motion Planning in State Lattices",
   booktitle = "",
   institution = "Robotics Institute",
   month = "May",
   year = "2007",
   number= "CMU-RI-TR-07-15",
   address= "Pittsburgh, PA",
}

The Robotics Institute

Menu