Differentially Constrained Motion Planning with State Lattice Motion Primitives

Mihail Pivtoraiko. Differentially Constrained Motion Planning with State Lattice Motion Primitives. Technical Report CMU-RI-TR-12-07, Robotics Institute, Carnegie Mellon University, 2012.

Download

[14.8MB pdf] 

Abstract

Robot motion planning with differential constraints has received a great deal of attention in the last few decades, yet it still remains a challenging problem. Among a number of reasons, three stand out. First, the differential constraints that most physical robots exhibit render the coupling between the control and state spaces quite complicated. Second, it is commonly accepted that robots must be able to operate in environments that are partially or entirely unknown; classical motion planning techniques that assume known structure of the world frequently encounter difficulties when applied in this setting. Third, such robots are typically expected to operate with speed that is commensurate with that of humans. This poses stringent limitations on available runtime and often hard real-time requirements on the motion planner. The impressive advances in computing capacity in recent years have been unable, by themselves, to meet the computational challenge of this problem. New algorithmic approaches to tackle its difficulties continue to be developed to this day. The approach advocated in this thesis is based on encapsulating some of the complexity of satisfying the differential constraints in pre-computed controls that serve as motion primitives, elementary motions that are combined to form the solution trajectory for the system. The contribution of this work is in developing a general approach to constructing such motion primitives, given a model of robot mobility. Moreover, the approach allows an unprecedented amount of pre-computation in this domain, which yields a dramatic increase in planning efficiency even for systems with complex kinematics and dynamics. Lastly, the proposed motion primitives are fully compatible with a wide range of planning algorithms and allow such useful techniques as incremental planning and multi-directional search to be used in the context of planning with differential constraints. These ideas are demonstrated and validated on a number of relevant systems, both in simulation and in real experiments. This work promises to enable capable and reliable motion planners with differential constraints, as encountered in many realistic robot systems with practical utility, operating efficiently in cluttered, partially known environments.

BibTeX

@TECHREPORT{pivtoraiko_tr12,
  author = {Mihail Pivtoraiko},
  title = {Differentially Constrained Motion Planning with State
                  Lattice Motion Primitives},
  institution = {Robotics Institute, Carnegie Mellon University},
  year = {2012},
  number = {CMU-RI-TR-12-07},
  abstract = { Robot motion planning with differential constraints has
                  received a great deal of attention in the last few
                  decades, yet it still remains a challenging
                  problem. Among a number of reasons, three stand
                  out. First, the differential constraints that most
                  physical robots exhibit render the coupling between
                  the control and state spaces quite
                  complicated. Second, it is commonly accepted that
                  robots must be able to operate in environments that
                  are partially or entirely unknown; classical motion
                  planning techniques that assume known structure of
                  the world frequently encounter difficulties when
                  applied in this setting. Third, such robots are
                  typically expected to operate with speed that is
                  commensurate with that of humans. This poses
                  stringent limitations on available runtime and often
                  hard real-time requirements on the motion
                  planner. The impressive advances in computing
                  capacity in recent years have been unable, by
                  themselves, to meet the computational challenge of
                  this problem. New algorithmic approaches to tackle
                  its difficulties continue to be developed to this
                  day.  The approach advocated in this thesis is based
                  on encapsulating some of the complexity of
                  satisfying the differential constraints in
                  pre-computed controls that serve as {motion
                  primitives}, elementary motions that are combined to
                  form the solution trajectory for the system. The
                  contribution of this work is in developing a
                  {general approach} to constructing such motion
                  primitives, given a model of robot
                  mobility. Moreover, the approach allows an
                  unprecedented amount of {pre-computation} in
                  this domain, which yields a dramatic increase in
                  planning efficiency even for systems with complex
                  kinematics and dynamics. Lastly, the proposed motion
                  primitives are fully compatible with a {wide
                  range} of planning algorithms and allow such useful
                  techniques as incremental planning and
                  multi-directional search to be used in the context
                  of planning with differential constraints.  These
                  ideas are demonstrated and validated on a number of
                  relevant systems, both in simulation and in real
                  experiments. This work promises to enable capable
                  and reliable motion planners with differential
                  constraints, as encountered in many realistic robot
                  systems with practical utility, operating
                  efficiently in cluttered, partially known
                  environments.  },
  bib2html_pubtype = {Tech Reports},
  bib2html_rescat = {Kinodynamic Planning}
}

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