Graphics enhanced version of this site

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

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Adobe portable document format (pdf) [1713 KB]
Compressed postscript (ps.gz) [625 KB]

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.

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.

Associated center: NREC
Associated project: UGCV PerceptOR Integrated

Number of pages: 16

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

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