Optimizations for sampling-based motion planning algorithms

Sampling-basedalgorithms solve the motion planning problem by successively solving several separate suproblems of reduced complexity. As a result, the efficiency of the sampling-based algorithm depends on the complexity of each of the algorithms used to solve the individual subproblems, namely the procedures GenerateSample, FindNearest, LocalPlan, CollisionFree, and AddToGraph. However, it is often the case that these subproblems are quite related, working on common components of the problem definition. Therefore, distinct algorithms and segregated data structures for solving these subproblems might be costing sampling-based algorithms more time than necessary. The thesis of this dissertation is the following: By taking advantage of the fact that these subproblems are solved repeatedly with similar inputs, and the relationships between data structures used to solve the subproblems, we may significantly reduce the practical complexity of sampling-based motion planning algorithms. Moreover, this reuse of information from components can be used to find a middle ground between exact motion planning algorithms which find an explicit representation ofthe collision-free space,and sampling-based algorithms which find no representation of the collision-free space, except for the zeromeasure paths between connected nodes in the roadmap.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Aeronautics and Astronautics.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2014

Author dc:creator

• Bialkowski, Joshua John

Advisor dc:contributor.advisor

• Emilio Frazzoli.

• Aeronautics and Astronautics.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/87475

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/87475