{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,15]],"date-time":"2024-09-15T18:42:25Z","timestamp":1726425745093},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2013,1,25]],"date-time":"2013-01-25T00:00:00Z","timestamp":1359072000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Robotica"],"published-print":{"date-parts":[[2013,8]]},"abstract":"<jats:title>SUMMARY<\/jats:title><jats:p>It has been shown before that the Rapidly Exploring Random Tree (RRT) algorithm is probabilistically and resolution complete; and that the probability of finding a particular solution path can be related to the number of nodes. However, little analysis exists on the rate at which the tree covers the configuration space. In this paper, we present a stochastic difference equation which models how the tree covers the configuration space as a function of the number of nodes in the tree. Using two simplifying assumptions, appropriate for holonomic, kinematic systems in expansive configuration spaces, we derive closed-form solutions for the expected value and variance of configuration space coverage, which only depend on two easily computable parameters. Using a grid-based coverage measurement, we present experimental evidence supporting this model across a range of dimensions, obstacle densities, and parameter choices. Collecting data from 1000 RRTs, we provide evidence that configuration space coverage concentrates tightly around the expected coverage predicted by the model; and the results of the Chi-squared test suggest that the distribution of coverage across these runs is highly Gaussian. Together these results enable one to predict the expected coverage, along with a confidence interval, after a certain number of nodes have been added to the tree. We also applied the model to an example with extremely narrow passages and to a system with non-holonomic kinematics. The expected value prediction is still qualitatively accurate; but the rate constant is reduced and the variance is higher. Overall, in addition to its theoretical value, the model may find future application as an online measure of search-progress and problem difficulty, useful for adaptive variants of the basic RRT algorithm.<\/jats:p>","DOI":"10.1017\/s0263574712000690","type":"journal-article","created":{"date-parts":[[2013,1,25]],"date-time":"2013-01-25T08:35:53Z","timestamp":1359102953000},"page":"733-746","source":"Crossref","is-referenced-by-count":4,"title":["Conditional Density Growth (CDG) model: a simplified model of RRT coverage for kinematic systems"],"prefix":"10.1017","volume":"31","author":[{"given":"Joel M.","family":"Esposito","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2013,1,25]]},"reference":[{"key":"S0263574712000690_ref11","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1960.tb42846.x"},{"key":"S0263574712000690_ref3","first-page":"521","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Bohlin","year":"2000"},{"key":"S0263574712000690_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386213"},{"key":"S0263574712000690_ref8","doi-asserted-by":"publisher","DOI":"10.2514\/2.4856"},{"key":"S0263574712000690_ref25","first-page":"293","volume-title":"Algorithmic and Computational Robotics: New Directions","author":"LaValle","year":"2001"},{"key":"S0263574712000690_ref5","doi-asserted-by":"crossref","first-page":"3307","DOI":"10.1109\/ROBOT.2007.363983","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Burns","year":"2007"},{"key":"S0263574712000690_ref24","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"volume-title":"Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems","year":"2003","author":"Kim","key":"S0263574712000690_ref18"},{"key":"S0263574712000690_ref27","doi-asserted-by":"publisher","DOI":"10.1002\/rob.20256"},{"volume-title":"Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence","year":"2008","author":"Wedge","key":"S0263574712000690_ref28"},{"volume-title":"Introduction to the Theory of Coverage Processes","year":"1988","author":"Hall","key":"S0263574712000690_ref9"},{"key":"S0263574712000690_ref7","first-page":"267","volume-title":"Proceedings IEEE International Conference on Robotics and Automation","author":"Cheng","year":"2002"},{"volume-title":"The Complexity of Robot Motion Planning","year":"1988","author":"Canny","key":"S0263574712000690_ref6"},{"key":"S0263574712000690_ref23","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"S0263574712000690_ref17","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"S0263574712000690_ref2","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1996.503582"},{"key":"S0263574712000690_ref26","first-page":"3251","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Lindemann","year":"2004"},{"key":"S0263574712000690_ref12","unstructured":"D. Hsu , \u201cRandomized Single-Query Motion Planning in Expansive Spaces,\u201d Ph.D. thesis (Stanford University, California, 2000)."},{"key":"S0263574712000690_ref13","first-page":"141","volume-title":"Proceedings of the 3rd Workshop on the Algorithmic Foundations of Robotics (WAFR)","author":"Hsu","year":"1998"},{"volume-title":"International Syposium on Robotics Research","year":"2005","author":"Hsu","key":"S0263574712000690_ref14"},{"key":"S0263574712000690_ref20","doi-asserted-by":"publisher","DOI":"10.1109\/TRA.2004.824649"},{"key":"S0263574712000690_ref21","first-page":"297","volume-title":"Proceedings of the Workshop on the Algorithmic Foundations of Robotics","author":"Ladd","year":"2005"},{"key":"S0263574712000690_ref16","doi-asserted-by":"publisher","DOI":"10.1109\/70.660866"},{"key":"S0263574712000690_ref22","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045481"},{"key":"S0263574712000690_ref19","doi-asserted-by":"publisher","DOI":"10.1177\/0278364906072513"},{"key":"S0263574712000690_ref4","first-page":"1481","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Branicky","year":"2001"},{"key":"S0263574712000690_ref15","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"S0263574712000690_ref1","first-page":"3856","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Simeon","year":"2005"}],"container-title":["Robotica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0263574712000690","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,23]],"date-time":"2019-04-23T16:38:11Z","timestamp":1556037491000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0263574712000690\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,25]]},"references-count":28,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["S0263574712000690"],"URL":"https:\/\/doi.org\/10.1017\/s0263574712000690","relation":{},"ISSN":["0263-5747","1469-8668"],"issn-type":[{"type":"print","value":"0263-5747"},{"type":"electronic","value":"1469-8668"}],"subject":[],"published":{"date-parts":[[2013,1,25]]}}}