{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T21:41:15Z","timestamp":1779313275098,"version":"3.51.4"},"reference-count":53,"publisher":"SAGE Publications","issue":"12","license":[{"start":{"date-parts":[[2006,12,1]],"date-time":"2006-12-01T00:00:00Z","timestamp":1164931200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2006,12]]},"abstract":"<jats:p>The problem of testing complex reactive control systems and validating the effectiveness of multi-agent controllers is addressed. Testing and validation involve searching for conditions that lead to system failure by exploring all adversarial inputs and disturbances for errant trajectories. This problem of testing is related to motion planning. In both cases, there is a goal or specification set consisting of a set of points in state space that is of interest, either for finding a plan, demonstrating failure or for validation. Unlike motion planning problems, the problem of testing generally involves systems that are not controllable with respect to disturbances or adversarial inputs and therefore, the reachable set of states is a small subset of the entire state space. In this work, sampling-based algorithms based on the Rapidly-exploring Random Trees (RRT) algorithm are applied to the testing and validation problem. First, some of the factors that govern the exploration rate of the RRT algorithm are analysed, this analysis serving to motivate some enhancements. Then, three modifications to the original RRT algorithm are proposed, suited for use on uncontrollable systems. First, a new distance function is introduced which incorporates information about the system\u2019s dynamics to select nodes for extension. Second, a weighting is introduced to penalize nodes which are repeatedly selected but fail to extend.Third, a scheme for adaptively modifying the sampling probability distribution is proposed, based on tree growth. Application of the algorithm is demonstrated using several examples, and computational statistics are provided to illustrate the effect of each modification. The final algorithm is demonstrated on a 25 state example and results in nearly an order of magnitude reduction in computation time when compared with the traditional RRT. The proposed algorithms are also applicable to motion planning for systems that are not small time locally controllable.<\/jats:p>","DOI":"10.1177\/0278364906072513","type":"journal-article","created":{"date-parts":[[2006,11,13]],"date-time":"2006-11-13T14:29:33Z","timestamp":1163428173000},"page":"1257-1272","source":"Crossref","is-referenced-by-count":18,"title":["Sampling-based Algorithm for Testing and Validating Robot Controllers"],"prefix":"10.1177","volume":"25","author":[{"given":"Jongwoo","family":"Kim","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joel M.","family":"Esposito","sequence":"additional","affiliation":[{"name":"US Naval Academy, Annapolis, MD,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vijay","family":"Kumar","sequence":"additional","affiliation":[{"name":"University of Pennsylvania Philadelphia, PA,"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2006,12,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1109\/32.489079"},{"key":"atypb2","first-page":"113","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Amato, N."},{"key":"atypb3","volume-title":"5th IFAC Symposium on Nonlinear Control Systems","author":"Asarin, E."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1177\/0278364905050359"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24743-2_10"},{"key":"atypb6","first-page":"521","volume":"1","author":"Bohlin, R.","year":"2000","journal-title":"Proceedings of the International Conference on Robotics and Automation"},{"key":"atypb7","first-page":"1018","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Boor, V."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46430-1_10"},{"key":"atypb9","volume-title":"IEEE Conference on Decision and Control","author":"Branicky, M. S."},{"key":"atypb10","volume-title":"Proceedings of Robotics: Science and Systems","author":"Burns, B."},{"key":"atypb11","volume-title":"IEEE International Conference on Robotics and Automation","author":"Chaimowicz, L."},{"key":"atypb12","volume-title":"Proceedings of 38th Annual Allerton Conference on Communication, Control, and Computing","author":"Cheng, P."},{"key":"atypb13","first-page":"43","volume-title":"Proceedings of IEEE\/RSJ International Conference on Intelligent Robots and Systems","author":"Cheng, P."},{"issue":"3","key":"atypb14","first-page":"167","volume":"11","author":"Cheng, P.","year":"2001","journal-title":"Archives of Control Sciences"},{"key":"atypb15","unstructured":"Cheng, P. 2005.\n                      Sampling-based Motion Planning with Differential                 Constraints\n                      . PhD thesis, University of Illinois, Urbana, IL."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48983-5_10"},{"key":"atypb17","volume-title":"Proceedings of the 37th International Conference on Decision and Control","author":"Chutinan, A."},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2002.806655"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-64358-3_34"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1145\/174147.174150"},{"key":"atypb21","volume-title":"International Workshop on the Algorithmic Foundations of Robotics","author":"Esposito, J. M."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.2514\/6.2000-4056"},{"key":"atypb23","first-page":"225","volume-title":"Proceedings of the 7th International Conference on Computer Aided Verification","author":"Henzinger, T. A."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/s100090050008"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844795"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1177\/027836402320556421"},{"key":"atypb27","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Hsu, D."},{"key":"atypb28","volume-title":"Proceedings of the International Symposium on Robotics Research","author":"Hsu, D."},{"key":"atypb29","first-page":"2138","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Kavraki, L. E."},{"key":"atypb30","unstructured":"Kavraki, L. E. 1995.\n                      Random Networks in Configuration Space for Fast Path                 Planning\n                      . PhD thesus, Stanford University."},{"key":"atypb31","first-page":"353","volume-title":"Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC)","author":"Kavraki, L. E."},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"atypb33","volume-title":"IEEE International Conference on Robotics and Automation","author":"Kim, J."},{"key":"atypb34","volume-title":"IEEE\/RSJ International Conference on Intelligent Robots and Systems","author":"Kim, J."},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46430-1_19"},{"key":"atypb36","volume-title":"International Workshop on the Algorithmic Foundations of Robotics","author":"Ladd, A. M."},{"key":"atypb37","volume-title":"Proceedings of Robotics: Science and Systems","author":"Ladd, A. M."},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.2001.0472"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"key":"atypb40","first-page":"293","volume-title":"Algorithmic and Computational Robotics: New Directions","author":"LaValle, S. M.","year":"2001"},{"key":"atypb41","volume-title":"Proceedings of the Workshop on the Algorithmic Foundations of Robotics","author":"LaValle, S. M."},{"key":"atypb42","unstructured":"Levine, J. A. 2003.\n                      Sampling-based Planning for Hybrid Systems\n                      .                 Master\u2019s thesis, Case Western Reserve University, September."},{"key":"atypb43","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Lindermann, S. R."},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46430-1_27"},{"key":"atypb45","unstructured":"Mitchell, I. 2002.\n                      Application of Level Set Methods to Control and                     Reachability Problems in Continuous and Hybrid Systems\n                      . PhD thesis.                 Stanford University."},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24743-2_32"},{"key":"atypb47","first-page":"421","volume-title":"20th IEEE Symposium on Foundation of Computer Science","author":"Reif, J. H."},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-3108-8"},{"key":"atypb49","volume-title":"Proceedings of the IEEE International Conference on Intelligent Robotics and Systems","author":"Simeon, T."},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2003.814621"},{"key":"atypb51","author":"Urmson, C.","year":"2003","journal-title":"IEEE\/RSJ IROS 2003"},{"key":"atypb52","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Yang, Y."},{"key":"atypb53","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Yershova, A."}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364906072513","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364906072513","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:15:39Z","timestamp":1777457739000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/journals.sagepub.com\/doi\/10.1177\/0278364906072513"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,12]]},"references-count":53,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["10.1177\/0278364906072513"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1177\/0278364906072513","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,12]]}}}