Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Algorithms & Applications Group
Feature-Sensitive Motion Planning

Many motion planning techniques have been developed, but no one performs optimally in every problem instance. Rather, performance depends on the strengths and weaknesses of each planner and its suitability for each instance. Also, the problem environment may have vastly different regions, thus no single planner may be well suited for it.

We propose a feature-sensitive meta-planner that cooperatively applies more specialized planners to map an specific instance. It analizes a region to characterize it so to find the best-suited planning strategy for the region and to decide whether it needs to partition it and repeat the characterization until assigning a planning strategy to each distinct region in the planning space. Then, the meta-planner maps each region with the strategy assigned. Finally, regional maps are combined into a map for the overall problem.

Input: An instance of the motion planning problem. In the example a planar environment for a point robot with 2 degrees of freedom (red areas represent obstacles while the free space is in white).

Characterization: The region is analyzed to find a matching planning strategy. Descriptive features are extracted from the region. Machine learning is used to analize the features and to search for a matching planner.

Partitioning: If it is not possible to match the region to a good planner, the region is partitioned into subregions. Machine learning techniques are used to decide how to build subregions.

Mapping: Each region is mapped with the planning strategy found during its characterization. In the example we see how the free area on the right needs only a few samples to be well-mapped, while the area on the bottom is mapped with many samples around C-obstacles.

Combination: Specialized methods are used to combine regional solutions into an overall solution. Efficient methods for combination are needed to obtain good performance.

A non-homogeneous partition
Where no single planner would perform well
A cluttered partition
An obstacle-based sampling would perform well
A free partition
A basic probabilistic roadmap method would perform well
The resulting map
A combination of methods applied

Region Identification Methods for Efficient and Automated Motion Planning, Jory Denny, Anshul Agrawal, Evan Greco, Lydia Tapia, Nancy M. Amato, Technical Report, TR10-002, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, U.S.A., Sep 2010.
Technical Report(ps, pdf, abstract)

Intelligent Motion Planning and Analysis with Probabilistic Roadmap Methods for the Study of Complex and High-Dimensional Motions, Lydia Tapia, Ph.D. Thesis, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, Dec 2009.
Ph.D. Thesis(pdf, abstract)

Metrics for Sampling-Based Motion Planning, Marco Morales, Ph.D. Thesis, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, Dec 2007.
Ph.D. Thesis(pdf, abstract)

Metrics for Comparing C-space Roadmaps, Marco A. Morales A., Roger Pearce, Aimée Vargas E., Nancy M. Amato, Technical Report, TR05-012, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, U.S.A., Sep 2005.
Technical Report(ps, pdf, abstract)

C-Space Subdivision and Integration in Feature-Sensitive Motion Planning, Marco A. Morales A., Lydia Tapia, Roger Pearce, Samuel Rodriguez, Nancy M. Amato, Technical Report, TR04-004, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, U.S.A., Sep 2004.
Technical Report(ps, pdf, abstract)

A Machine Learning Approach for Feature-Sensitive Motion Planning, Marco Morales, Lydia Tapia, Roger Pearce, Samuel Rodriguez, Nancy M. Amato, In Proc. Int. Wkshp. on Alg. Found. of Rob. (WAFR), pp. 361-376, Utrecht/Zeist, The Netherlands, Jul 2004. Also, Technical Report, TR04-001, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, U.S.A., Feb 2004.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

Supported by NSF

Project Alumni:Anshul Agrawal,Evan Greco,Marco Morales,Roger Pearce,Lydia Tapia