Optimal Sampling In the Space of Paths: Preliminary Results

Colin Green and Alonzo Kelly
tech. report CMU-RI-TR-06-51, Robotics Institute, Carnegie Mellon University, November, 2006


Download
  • Adobe portable document format (pdf) (2MB)
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
While spatial sampling has received much attention in recent years, our understanding of sampling issues in the function space of trajectories remains limited. This paper presents a structured approach to the selection of a finite control set, derived from the infinite function space of possible controls, which is optimal in some useful sense. We show from first principles that the degree to which trajectories overlap spatially is directly related to the relative completeness that can be expected in sequential motion planning. We define relative completeness to mean the probability, taken over the population of all possible worlds, that at least one trajectory searched will not intersect an obstacle. Likewise, trajectories which are more separated from each other perform better in this regard than the alternatives. A suboptimal algorithm is presented which selects a control set from a dense sampling of the continuum of all possible paths. Results show that this algorithm produces control sets which perform significantly better than constant curvature arcs. The resulting control set has been deployed on an autonomous mobile robot operating in complex terrain in order to respond to situations when the robot is surrounded by a dense obstacle field.

Notes
Associated Project(s): UGCV PerceptOR Integrated
Number of pages: 16

Text Reference
Colin Green and Alonzo Kelly, "Optimal Sampling In the Space of Paths: Preliminary Results," tech. report CMU-RI-TR-06-51, Robotics Institute, Carnegie Mellon University, November, 2006

BibTeX Reference
@techreport{Green_2006_5587,
   author = "Colin Green and Alonzo Kelly",
   title = "Optimal Sampling In the Space of Paths: Preliminary Results",
   booktitle = "",
   institution = "Robotics Institute",
   month = "November",
   year = "2006",
   number= "CMU-RI-TR-06-51",
   address= "Pittsburgh, PA",
}