Feature-Sensitive Motion Planning | Algorithms & Applications Group

Algorithms & Applications Group
Feature-Sensitive Motion Planning

A framework for motion planning
supported by NSF
Bryan Boyd, Marco A. Morales A., Roger Pearce, Samuel Rodriguez, Lydia Tapia, Shawna Thomas, Nancy M. Amato

Project Alumni: Terra Horton

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.

Example with rigid body robot

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

Presentations

WAFR 2004 Presentation (PDF)

ICRA 2005 Presentation (PDF)

Papers

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(abstract)

The Role of Spatial-Temporal Adaptation in Motion Planning, Lydia Tapia, Shawna Thomas, Bryan Boyd, Nancy M. Amato, Technical Report, TR07-005, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, U.S.A., Oct 2007.
Technical Report(ps, pdf, abstract)

Analysis of the Evolution of C-Space Models built through Incremental Exploration, Marco Morales, Roger Pearce, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 1029-1034, Rome, Italy, Apr 2007. Also, Technical Report, TR06-013, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, Texas, U.S.A., Sep 2006.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

Metrics for Analyzing the Evolution of C-Space Models, Marco A. Morales A., Roger Pearce, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 1268-1273, Orlando, Florida, U.S.A., May 2006.
Proceedings(ps, 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)

Department of Computer Science | Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science Engineering TAMU

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