Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Algorithms & Applications Group
IMG: Incremental Map Generation

Project Personnel:Shawna Thomas,Nancy Amato

Probabilistic roadmap methods (PRMs) have been highly successful in solving many high degree of freedom motion planning problems arising in diverse application domains such as traditional robotics, computer-aided design, and computational biology and chemistry. One important practical issue is that PRMs do not provide an automated stopping mechanism to determine how large a roadmap is needed for a given problem. Ideally, planning should stop when the planner is no longer learning, when it is no longer adding useful information to the roadmap. This work addresses this issue with a new framework called Incremental Map Generation (IMG).

IMG iterates over the following phases: roadmap construction/expansion and roadmap evaluation.

Our strategy is to break the map generation into several processes, each of which generates samples and connections, and to continue adding the next increment of samples and connections to the evolving roadmap. The process continues until the planning strategy is no longer improving the roadmap as determined by a set of evaluation criteria.

For example, consider how the roadmap below evolves over time. After 500 nodes there are 3 connected components, 2 connected components after 750 nodes, and 1 single connected component after 1000 nodes. The success rate is the percentage of queries the roadmap can solve.

500 nodes.
Success rate: 33.7%.
750 nodes.
Success rate: 52.4%.
1000 nodes.
Success rate: 98.0%.
Evolution of a roadmap in the IMG framework.

We have proposed several different evaluation criteria to control roadmap construction. Some are general and others are application specific:

Evaluation Criteria
Roadmap Progress Evaluation This evaluator monitors roadmap coverage and connectivity. We classify new samples as they are insterted into the roadmap. We use changes in connected component diameters to approximate changes in roadmap coverage and connectivity. We stop roadmap construction when the rate of change of the maximum component diameter and the sum of component diameters over a certain period of time (k) falls below a threshold (tau).
Query Evaluation
(Application Specific)
This evaluator simply determines whether a roadmap can solve a set of user specified queries. This is useful when the user knows the set of test problems they want to solve a priori or to develop a single query application.
Max-flow Evaluation
(Application Specific)
Some applications not only require a single path between two configurations but many paths between them. To study how a protein changes from one target configuration to another for example, we can examine the probable paths between them in the roadmap. We can define this as a maximum flow problem on a network: if a roadmap edge weight, w(e), reflects the likelihood that the protein will move from one configuration to the next, then we can define edge capacity c(e) as 1/w(e). The evaluator returns success if the max-flow between the two configurations is above some threshold f.

Here we examine how the window size, k, effects roadmap progress evaluation performance. We keep all other parameters fixed. In the plots below, we show how component diameter changes over time for both graphs and trees for various sampling methods. The circle markers indicate where IMG would stop roadmap construction for various k.

Hook Environment
(Rigid Body)
Uniform Sampling
Bridge Test Sampling
Gaussian Sampling
OBPRM Sampling
Component diameter evolution for various samplers in the Hook environment where k varies and tau remains fixed. The witness query from one end of the environment to the other was solved after Uniform Sampling: never, Bridge Test Sampling: 550 samples, Gaussian Sampling: 3600 samples, OBPRM Sampling: 500 samples.

For each sampling method, the roadmap grows rapiduly in the beginning and then experiences a long refinement period before stabilizing. Also, increasing k cause the planner to stop later because larger k values allow IMG to capture changes over longer time windows.

Here we examine how the variability threshold, tau, effects roadmap progress evaluation performance. We keep all other parameters fixed. In the plots below, we show how component diameter changes over time for both graphs and trees for various environements. For these experiments we use OBPRM sampling. The circle markers indicate where IMG would stop roadmap construction for various tau.

Hook Environment
(Manipulator)
Maze Environment
(Rigid Body)
U-Tunnel Environment
(Rigid Body)
Component diameter evolution for environments using OBPRM sampling where tau varies and k remains fixed. The witness query from one end of the environment to the other was solved after Hook: 500 samples, Hook Manipulator: never, Maze: 3750 samples, U-Tunnel: 2850 samples.

Overall, decreasing tau requires the planner to run longer because smaller tau values signify a smaller tolerance for diameter variability. Again, we see distinct planning phases: "quick learning", "model enhancement", and "learning decay".

We can combine the IMG framework with Hybrid PRM in two ways:

  • use Hybrid PRM as the sampling method in the IMG framework, and
  • partition each IMG iteration in two parts: a "learning window" and a "sampling window" where we use Hybrid PRM in the "learning window" to determing a sampling distribution to apply to the "sampling window".

Here we show where IMG would stop Hybrid PRM sampling for various k and tau. This shows similar trends for k and tau as seen previously.

Hook Environment
(Rigid Body)
Using Hybrid PRM as the sampling method in the IMG framework.

Here we compare the two ways for combining Hybrid PRM and IMG. For each combination, we show how the number of samples produced, the selection probability, and the percentage of oversamples for each component sampler over time.

Combination 1: IMG as a stopping mechanism for Hybrid PRM
# Samples per Sampler
Sampling Probability and % Oversamples
Combination 2: Hybrid PRM in a learning window
# Samples per Sampler
Sampling Probability and % Oversamples

Our results confirm the treds found in the Hybrid PRM research: uniform sampling is selected early on but dies out quickly as other, more powerful and expensive samplers are selected. In the end, combination 1 vacillates between Gauss and Bridge Test sampling, while combination 2 does not select a dominant sampler after solving the witness query. We believe this is a more accurate assessment because all samplers are equally "bad": more than 80% of all nodes created at this point are oversample nodes.

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)

Incremental Map Generation (IMG), Dawen Xie, Marco Morales, Roger Pearce, Shawna Thomas, Jyh-Ming Lien, Nancy M. Amato, In Proc. Int. Wkshp. on Alg. Found. of Rob. (WAFR), New York City, NY, Jul 2006. Also, Technical Report, TR06-005, Department of Computer Science and Engineering, Texas A&M University, Mar 2006.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

Supported by NSF

Project Alumni:Jyh-Ming Lien,Marco Morales,Roger Pearce,Dawen Xie