{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T13:49:28Z","timestamp":1762004968951,"version":"build-2065373602"},"reference-count":46,"publisher":"Cambridge University Press (CUP)","issue":"7","license":[{"start":{"date-parts":[[2018,2,27]],"date-time":"2018-02-27T00:00:00Z","timestamp":1519689600000},"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":[[2018,7]]},"abstract":"<jats:title>SUMMARY<\/jats:title><jats:p>This paper presents an approach that integrates the geometric notion of <jats:italic>clearance<\/jats:italic> (distance to the closest obstacle) into sampling-based motion planning to enable a robot to safely navigate in challenging environments. To reach the goal destination, the robot must obey geometric and differential constraints that arise from the underlying motion dynamics and the characteristics of the environment. To produce safe paths, the proposed approach expands a motion tree of collision-free and dynamically feasible motions while maintaining locally maximal clearance. In distinction from related work, rather than explicitly constructing the medial axis, the proposed approach imposes a grid or a triangular tessellation over the free space and uses the clearance information to construct a weighted graph where edges that connect regions with low clearance have high cost. Minimum-cost paths over this graph produce high-clearance routes that tend to follow the medial axis without requiring its explicit construction. A key aspect of the proposed approach is a route-following component which efficiently expands the motion tree to closely follow such high-clearance routes. When expansion along the current route becomes difficult, edges in the tessellation are penalized in order to promote motion-tree expansions along alternative high-clearance routes to the goal. Experiments using vehicle models with second-order dynamics demonstrate that the robot is able to successfully navigate in complex environments. Comparisons to the state-of-the-art show computational speedups of one or more orders of magnitude.<\/jats:p>","DOI":"10.1017\/s0263574718000164","type":"journal-article","created":{"date-parts":[[2018,2,27]],"date-time":"2018-02-27T07:08:53Z","timestamp":1519715333000},"page":"971-993","source":"Crossref","is-referenced-by-count":11,"title":["Clearance-driven motion planning for mobile robots with differential constraints"],"prefix":"10.1017","volume":"36","author":[{"given":"Evis","family":"Plaku","sequence":"first","affiliation":[]},{"given":"Erion","family":"Plaku","sequence":"additional","affiliation":[]},{"given":"Patricio","family":"Simari","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,2,27]]},"reference":[{"key":"S0263574718000164_ref7","doi-asserted-by":"publisher","DOI":"10.1037\/0033-2909.112.1.155"},{"key":"S0263574718000164_ref40","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00047-5"},{"key":"S0263574718000164_ref46","doi-asserted-by":"crossref","unstructured":"H. C. Yeh , J. Denny , A. Lindsey , S. L. Thomas and N. M. Amato , \u201cUMAPRM: Uniformly Sampling the Medial Axis,\u201d Proceedings of the International Conference on Robotics and Automation, Hong Kong, China (2014) pp. 5798\u20135803.","DOI":"10.1109\/ICRA.2014.6907711"},{"key":"S0263574718000164_ref11","doi-asserted-by":"crossref","unstructured":"J. Denny , E. Greco , S. Thomas and N. M. Amato , \u201cMARRT: Medial Axis Biased Rapidly-Exploring Random Trees,\u201d Proceedings of the IEEE International Conference on Robotics and Automation, Hong Kong, China (2014) pp. 90\u201397.","DOI":"10.1109\/ICRA.2014.6906594"},{"key":"S0263574718000164_ref31","doi-asserted-by":"crossref","unstructured":"M. Mukadam , X. Yan and B. Boots , \u201cGaussian Process Motion Planning,\u201d Proceedings of the IEEE International Conference on Robotics and Automation, Stockholm, Sweden (2016) pp. 9\u201315.","DOI":"10.1109\/ICRA.2016.7487091"},{"key":"S0263574718000164_ref20","doi-asserted-by":"crossref","unstructured":"J. Huh , B. Lee and D. D. Lee , \u201cAdaptive Motion Planning with High-Dimensional Mixture Models,\u201d Proceedings of the IEEE International Conference on Robotics and Automation, Singapore (2017) pp. 3740\u20133747.","DOI":"10.1109\/ICRA.2017.7989431"},{"key":"S0263574718000164_ref15","unstructured":"L. J. Guibas , C. Holleman and L. E. Kavraki , \u201cA Probabilistic Roadmap Planner for Flexible Objects with a Workspace Medial-Axis-Based Sampling Approach,\u201d Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, Kyongju, South Korea (1999) pp. 254\u2013260."},{"key":"S0263574718000164_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1049-y"},{"key":"S0263574718000164_ref22","unstructured":"S. Kiesel , E. Burns and W. Ruml , \u201cAbstraction-Guided Sampling for Motion Planning,\u201d Proceedings of the Symposium on Combinatorial Search Niagara Falls, Canada (2012) pp. 162\u2013163. Also as UNH CS Technical Report 12-01."},{"key":"S0263574718000164_ref30","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2014.2321376"},{"key":"S0263574718000164_ref14","doi-asserted-by":"crossref","unstructured":"M. Etzion and A. Rappoport , \u201cComputing the Voronoi Diagram of a 3-d Polyhedron by Separate Computation of its Symbolic and Geometric Parts,\u201d Proceedings of Symposium on Solid Modeling and Applications, New York, NY (1999) pp. 167\u2013178.","DOI":"10.1145\/304012.304029"},{"key":"S0263574718000164_ref39","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0014497"},{"key":"S0263574718000164_ref4","unstructured":"S. Brin , \u201cNear Neighbor Search in Large Metric Spaces,\u201d Proceedings of the 21th International Conference on Very Large Data Bases, Zurich, Switzerland (1995) pp. 574\u2013584."},{"key":"S0263574718000164_ref9","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2012.2205651"},{"key":"S0263574718000164_ref25","unstructured":"E. Larsen , S. Gottschalk , M. C. Lin and D. Manocha , Fast Proximity Queries with Swept Sphere Volumes. Technical Report (Department of Computer Science, University of North Carolina, Chapel Hill, NC, 1999)."},{"key":"S0263574718000164_ref43","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-22416-9_32"},{"key":"S0263574718000164_ref28","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"key":"S0263574718000164_ref38","first-page":"231","volume-title":"The Handbook of Research Synthesis","author":"Rosenthal","year":"1994"},{"key":"S0263574718000164_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"S0263574718000164_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2003.07.008"},{"key":"S0263574718000164_ref36","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2010.2047820"},{"key":"S0263574718000164_ref21","doi-asserted-by":"publisher","DOI":"10.1145\/2580947"},{"key":"S0263574718000164_ref33","doi-asserted-by":"crossref","unstructured":"L. Palmieri , T. Kucner , M. Magnusson , A. Lilienthal and K. Arras , \u201cKinodynamic Motion Planning on Gaussian Mixture Fields,\u201d Proceedings of the IEEE International Conference on Robotics and Automation, Singapore (2017) pp. 6176\u20136181.","DOI":"10.1109\/ICRA.2017.7989731"},{"key":"S0263574718000164_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00017-7"},{"key":"S0263574718000164_ref12","doi-asserted-by":"crossref","unstructured":"D. Devaurs , T. Simeon and J. Cort\u00e9s , \u201cEnhancing the Transition-Based RRT to Deal with Complex Cost Spaces,\u201d Proceedings of the IEEE International Conference on Robotics and Automation, Karlsruhe, Germany (2013) pp. 4120\u20134125.","DOI":"10.1109\/ICRA.2013.6631158"},{"key":"S0263574718000164_ref19","doi-asserted-by":"crossref","unstructured":"C. Holleman and L. E. Kavraki , \u201cA Framework for Using the Workspace Medial Axis in PRM Planners,\u201d Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, CA (2000) pp. 1408\u20131413.","DOI":"10.1109\/ROBOT.2000.844795"},{"key":"S0263574718000164_ref17","doi-asserted-by":"crossref","unstructured":"F. Hauer and P. Tsiotras , \u201cDeformable Rapidly-Exploring Random Trees,\u201d Proceedings of the Robotics: Science and Systems Conference, Boston, MA (2017) p. P08.","DOI":"10.15607\/RSS.2017.XIII.008"},{"key":"S0263574718000164_ref41","doi-asserted-by":"crossref","unstructured":"D. J. Tracy , S. R. Buss and B.M. Woods , \u201cEfficient Large-Scale Sweep and Prune Methods with AABB Insertion and Removal,\u201d Proceedings of the IEEE Conference on Virtual Reality, Lafayette, LA (2009) pp. 191\u2013198.","DOI":"10.1109\/VR.2009.4811022"},{"key":"S0263574718000164_ref5","unstructured":"Y. F. Chen , S. Y. Liu , M. Liu , J. Miller and J. P. How , \u201cMotion Planning with Diffusion Maps,\u201d Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, Deajeon, South Korea (2016) pp. 1423\u20131430."},{"key":"S0263574718000164_ref32","doi-asserted-by":"crossref","unstructured":"L. Palmieri , S. Koenig and K. O. Arras , \u201cRRT-Based Nonholonomic Motion Planning Using Any-Angle Path Biasing,\u201d Proceedings of the IEEE International Conference on Robotics and Automation, Stockholm, Sweden (2016) pp. 2775\u20132781.","DOI":"10.1109\/ICRA.2016.7487439"},{"key":"S0263574718000164_ref18","doi-asserted-by":"crossref","unstructured":"K. E. Hoff III , J. Keyser , M. Lin , D. Manocha and T. Culver , \u201cFast Computation Of Generalized Voronoi Diagrams Using Graphics Hardware,\u201d Proceedings of the Conference on Computer Graphics and Interactive Techniques, New York, NY (1999) pp. 277\u2013286.","DOI":"10.1145\/311535.311567"},{"key":"S0263574718000164_ref35","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2015.2424031"},{"key":"S0263574718000164_ref8","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2011.2160466"},{"key":"S0263574718000164_ref44","doi-asserted-by":"crossref","unstructured":"S. A. Wilmarth , N. M. Amato and P. F. Stiller , \u201cMAPRM: A Probabilistic Roadmap Planner with Sampling on the Medial Axis of the Free Space,\u201d Proceedings of the IEEE International Conference on Robotics and Automation, Detroit, MI (1999) pp. 1024\u20131031.","DOI":"10.1109\/ROBOT.1999.772448"},{"key":"S0263574718000164_ref27","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2011.940276"},{"key":"S0263574718000164_ref34","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2017.2651940"},{"key":"S0263574718000164_ref45","doi-asserted-by":"crossref","unstructured":"S. A. Wilmarth , N. M. Amato and P. F. Stiller , \u201cMotion Planning for a Rigid Body Using Random Networks on the Medial Axis of the Free Space,\u201d Proceedings of the Symposium on Computational Geometry, New York, NY (1999) pp. 173\u2013180.","DOI":"10.1145\/304893.304967"},{"key":"S0263574718000164_ref24","unstructured":"A. M. Ladd and L. E. Kavraki , \u201cMotion Planning in the Presence of Drift, Underactuation and Discrete System Changes,\u201d Proceedings of the Robotics: Science and Systems Conference, Boston, MA (2005) pp. 233\u2013241."},{"key":"S0263574718000164_ref29","unstructured":"J. M. Lien , S. L. Thomas and N. M. Amato , \u201cA General Framework for Sampling on the Medial Axis of the Free Space,\u201d Proceedings of the IEEE International Conference on Robotics and Automation, Taipei, Taiwan (2003) pp. 4439\u20134444."},{"key":"S0263574718000164_ref37","doi-asserted-by":"crossref","unstructured":"J. Reif , \u201cComplexity of the Mover's Problem and Generalizations,\u201d Proceedings of the IEEE Symposium on Foundations of Computer Science, San Juan, Puerto Rico (1979) pp. 421\u2013427.","DOI":"10.1109\/SFCS.1979.10"},{"volume-title":"Graph. Models Image Process","year":"1995","author":"Vleugels","key":"S0263574718000164_ref42"},{"key":"S0263574718000164_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00147-B"},{"volume-title":"Robust Statistics: The Approach Bon Influence Functions","year":"2011","author":"Hampel","key":"S0263574718000164_ref16"},{"volume-title":"Principles of Robot Motion: Theory, Algorithms, and Implementations","year":"2005","author":"Choset","key":"S0263574718000164_ref6"},{"key":"S0263574718000164_ref23","doi-asserted-by":"publisher","DOI":"10.1137\/0212002"},{"key":"S0263574718000164_ref26","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"}],"container-title":["Robotica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0263574718000164","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,14]],"date-time":"2019-04-14T19:07:04Z","timestamp":1555268824000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0263574718000164\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,27]]},"references-count":46,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["S0263574718000164"],"URL":"https:\/\/doi.org\/10.1017\/s0263574718000164","relation":{},"ISSN":["0263-5747","1469-8668"],"issn-type":[{"type":"print","value":"0263-5747"},{"type":"electronic","value":"1469-8668"}],"subject":[],"published":{"date-parts":[[2018,2,27]]}}}