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).
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.
We have proposed several different evaluation criteria to control roadmap construction. Some are general and others are application specific:
|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).|
|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.|
|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.
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.
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:
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.
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.
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
Parasol Home | Research | People | General info | Seminars | Resources
Parasol Lab, 301 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112
firstname.lastname@example.org Phone 979.458.0722 Fax 979.458.0718
Department of Computer Science and Engineering | Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science and Engineering Engineering TAMU
Web Accessibility Policy and Law - Web Accessibility and Usability Standards - Contact Webmaster