{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T04:02:32Z","timestamp":1648612952458},"reference-count":73,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2011,10,12]],"date-time":"2011-10-12T00:00:00Z","timestamp":1318377600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AIEDAM"],"published-print":{"date-parts":[[2011,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The task of planning a path between two spatial configurations of an artifact moving among obstacles is an important problem in practically all geometrically intensive applications. Despite the ubiquity of the problem, the existing approaches make specific limiting assumptions about the geometry and mobility of the obstacles, or those of the environment in which the motion of the artifact takes place. We present a strategy to construct a family of paths, or roadmaps, for two- and three-dimensional solids moving in an evolving environment that can undergo drastic topological changes. Our approach is based on a potent paradigm for constructing geometric skeletons that relies on constructive representations of shapes with R-functions that operate on real-valued half-spaces as logic operations. We describe a family of skeletons that have the same homotopy as that of the environment and contains the medial axis as a special case. Of importance, our skeletons can be designed so that they are \u201cattracted to\u201d or \u201crepulsed by\u201d prescribed spatial sites of the environment. Moreover, the R-function formulation suggests the new concept of a medial zone, which can be thought of as a \u201cthick\u201d skeleton with significant applications for motion planning and other geometric reasoning applications. Our approach can handle problems in which the environment is not fully known a priori, and intrinsically supports local and parallel skeleton computations for domains with rigid or evolving boundaries. Furthermore, our path planning algorithm can be implemented in any commercial geometric kernel, and has attractive computational properties. The capability of the proposed technique are explored through several examples designed to simulate highly dynamic environments.<\/jats:p>","DOI":"10.1017\/s0890060411000229","type":"journal-article","created":{"date-parts":[[2011,10,12]],"date-time":"2011-10-12T14:19:10Z","timestamp":1318429150000},"page":"375-392","source":"Crossref","is-referenced-by-count":0,"title":["A family of skeletons for motion planning and geometric reasoning applications"],"prefix":"10.1017","volume":"25","author":[{"given":"Ata A.","family":"Eftekharian","sequence":"first","affiliation":[]},{"given":"Horea T.","family":"Ilie\u015f","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2011,10,12]]},"reference":[{"key":"S0890060411000229_ref19","doi-asserted-by":"crossref","unstructured":"Dey T.K. , Woo H. , & Zhao W. (2003). Approximate medial axis for CAD models. Proc. 8th ACM Symp. Solid Modeling and Applications: ISM \u201803, pp. 280\u2013285. New York: ACM.","DOI":"10.1145\/781606.781652"},{"key":"S0890060411000229_ref38","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4022-9"},{"key":"S0890060411000229_ref55","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.1273924"},{"key":"S0890060411000229_ref48","doi-asserted-by":"publisher","DOI":"10.1007\/s00366-004-0292-4"},{"key":"S0890060411000229_ref72","doi-asserted-by":"crossref","unstructured":"Wilmarth S.A. , Amato N.M. , & Stiller P.F. (1999). Motion planning for a rigid body using random networks on the medial axis of the free space. Proc. 15th Annual Symp. Computational Geometry: SCG \u201899, pp. 173\u2013180. New York: ACM.","DOI":"10.1145\/304893.304967"},{"key":"S0890060411000229_ref61","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4485(91)90095-E"},{"key":"S0890060411000229_ref35","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"S0890060411000229_ref27","doi-asserted-by":"crossref","unstructured":"Garber M. , & Lin M.C. (2002). Constraint-based motion planning for virtual prototyping. Proc. 7th ACM Symp. Solid Modeling and Applications: SMA \u201802, pp. 257\u2013264. New York: ACM.","DOI":"10.1145\/566282.566320"},{"key":"S0890060411000229_ref58","volume-title":"Theory of R-Functions and Applications: A Primer","author":"Shapiro","year":"1991"},{"key":"S0890060411000229_ref11","doi-asserted-by":"publisher","DOI":"10.1023\/B:JODS.0000024119.38784.ff"},{"key":"S0890060411000229_ref46","unstructured":"Neus M. , & Maouche S. (2005). Motion planning using the modified visibility graph. Proc. IEEE Int. Conf. Systems Man and Cybernetics, Vol. 4, pp. 651\u2013655."},{"key":"S0890060411000229_ref69","doi-asserted-by":"publisher","DOI":"10.1145\/357346.357348"},{"key":"S0890060411000229_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-005-4946-5"},{"key":"S0890060411000229_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1943"},{"key":"S0890060411000229_ref3","first-page":"362","article-title":"A transformation for extracting new descriptions of shape","author":"Blum","year":"1967","journal-title":"Proc. Models for the Perception of Speech and Visual Form"},{"key":"S0890060411000229_ref25","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2001.973336"},{"key":"S0890060411000229_ref17","volume-title":"Algorithms","author":"Dasgupta","year":"2008"},{"key":"S0890060411000229_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2009.05.006"},{"key":"S0890060411000229_ref29","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2007.09.013"},{"key":"S0890060411000229_ref68","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.08.008"},{"key":"S0890060411000229_ref34","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2004.1302410"},{"key":"S0890060411000229_ref41","doi-asserted-by":"publisher","DOI":"10.1145\/781606.781620"},{"key":"S0890060411000229_ref59","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195901000468"},{"key":"S0890060411000229_ref32","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.1991.174624"},{"key":"S0890060411000229_ref63","doi-asserted-by":"publisher","DOI":"10.1145\/218013.218059"},{"key":"S0890060411000229_ref70","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2005.851378"},{"key":"S0890060411000229_ref24","volume-title":"Medial zones: formulation, properties and applications","author":"Eftekharian","year":"2010"},{"key":"S0890060411000229_ref26","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.1993.583794"},{"key":"S0890060411000229_ref67","doi-asserted-by":"crossref","unstructured":"Suresh K. (2003). Automating the CAD\/CAE dimensional reduction process. Proc. 8th ACM Symp. Solid Modeling and Applications: SM \u201803, pp. 76\u201385. New York: ACM.","DOI":"10.1145\/781606.781621"},{"key":"S0890060411000229_ref73","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-006-0190-2"},{"key":"S0890060411000229_ref7","doi-asserted-by":"publisher","DOI":"10.1016\/1049-9660(92)90030-7"},{"key":"S0890060411000229_ref51","doi-asserted-by":"publisher","DOI":"10.1109\/70.163777"},{"key":"S0890060411000229_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(01)00017-7"},{"key":"S0890060411000229_ref39","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"S0890060411000229_ref2","volume-title":"Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration, Mathematics and Visualization","author":"Attali","year":"2008"},{"key":"S0890060411000229_ref37","doi-asserted-by":"publisher","DOI":"10.1006\/cviu.1995.1062"},{"key":"S0890060411000229_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(78)90025-0"},{"key":"S0890060411000229_ref65","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008102926703"},{"key":"S0890060411000229_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(79)90062-5"},{"key":"S0890060411000229_ref6","volume-title":"Handbook of Image and Video Processing (Communications, Networking and Multimedia)","author":"Bovik","year":"2005"},{"key":"S0890060411000229_ref8","doi-asserted-by":"crossref","unstructured":"Buchele S.F. , & Crawford R.H. (2003). Three-dimensional halfspace constructive solid geometry tree construction from implicit boundary representations. Proc. 8th ACM Symp. Solid Modeling and Applications, pp. 135\u2013144. New York: ACM Press.","DOI":"10.1145\/781606.781629"},{"key":"S0890060411000229_ref9","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/36.5.504"},{"key":"S0890060411000229_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2008.01.002"},{"key":"S0890060411000229_ref13","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1997.181.57"},{"key":"S0890060411000229_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2003.07.008"},{"key":"S0890060411000229_ref14","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008958800904"},{"key":"S0890060411000229_ref18","doi-asserted-by":"publisher","DOI":"10.1109\/3477.678654"},{"key":"S0890060411000229_ref21","doi-asserted-by":"crossref","unstructured":"Dobkin D. , Guibas L. , Hershberger J. , & Snoeyink J. (1988). An efficient algorithm for finding the CSG representation of a simple polygon. Proc. 15th Annual Conf. Computer Graphics and Interactive Techniques: SIGGRAPH \u201888, pp. 31\u201340. New York: ACM.","DOI":"10.1145\/54852.378472"},{"key":"S0890060411000229_ref22","first-page":"25","volume-title":"Proc. 9th ACM Symp. Solid Modeling and Applications: SM \u201804","author":"Du","year":"2004"},{"key":"S0890060411000229_ref28","doi-asserted-by":"publisher","DOI":"10.1177\/0278364907079280"},{"key":"S0890060411000229_ref31","unstructured":"Hoff K. III , Culver T. , Keyser J. , Lin M. , & Manocha D. (2000). Interactive motion planning using hardware-accelerated computation of generalized Voronoi diagrams. Proc. IEEE Int. Conf. Robotics and Automation, 2000: ICRA\u201900, Vol. 3."},{"key":"S0890060411000229_ref33","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008070923246"},{"key":"S0890060411000229_ref36","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36181-2_22"},{"key":"S0890060411000229_ref64","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016376116653"},{"key":"S0890060411000229_ref52","doi-asserted-by":"publisher","DOI":"10.1109\/38.788799"},{"key":"S0890060411000229_ref40","doi-asserted-by":"publisher","DOI":"10.1177\/0278364905053687"},{"key":"S0890060411000229_ref42","doi-asserted-by":"crossref","unstructured":"Lingelbach F. (2004). Path planning using probabilistic cell decomposition. Proc. IEEE Int. Conf. Robotics & Automation.","DOI":"10.1109\/ROBOT.2004.1307193"},{"key":"S0890060411000229_ref43","unstructured":"Liu T.-L. , Geiger D. , & Kohn R.V. (1998). Representation and self-similarity of shapes. Proc. 6th Int. Conf. Computer Vision: ICCV \u201898, pp. 1129. Washington, DC: IEEE Computer Society."},{"key":"S0890060411000229_ref30","doi-asserted-by":"publisher","DOI":"10.1006\/jvci.1999.0439"},{"key":"S0890060411000229_ref44","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2007.08.011"},{"key":"S0890060411000229_ref45","first-page":"20","article-title":"Robot motion planning in dynamic environments with moving obstacles and target","volume":"1","author":"Masehian","year":"2007","journal-title":"International Journal of Mechanical Systems Science and Engineering"},{"key":"S0890060411000229_ref47","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026135101267"},{"key":"S0890060411000229_ref71","doi-asserted-by":"crossref","unstructured":"van Eede M. , Macrini D. , Telea A. , Sminchisescu C. , & Dickinson S. (2006). Canonical skeletons for shape matching. Proc. 18th Int. Conf. Pattern Recognition ICPR 2006, Vol. 2, pp. 64\u201369.","DOI":"10.1109\/ICPR.2006.354"},{"key":"S0890060411000229_ref50","doi-asserted-by":"publisher","DOI":"10.1145\/356827.356833"},{"key":"S0890060411000229_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"S0890060411000229_ref49","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(98)00223-4"},{"key":"S0890060411000229_ref53","first-page":"21","article-title":"Semi-structured mesh generation based on medial axis","author":"Sampl","year":"2000","journal-title":"Proc. IMR"},{"key":"S0890060411000229_ref54","doi-asserted-by":"publisher","DOI":"10.1007\/s003660170004"},{"key":"S0890060411000229_ref56","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2004.10.007"},{"key":"S0890060411000229_ref57","unstructured":"Shaham A. , Shamir A. , & Cohen-Or D. (2004). Medial axis based solid representation. Proc. 9th ACM Symp. Solid Modeling and Applications."},{"key":"S0890060411000229_ref60","doi-asserted-by":"publisher","DOI":"10.1017\/S096249290631001X"},{"key":"S0890060411000229_ref62","doi-asserted-by":"publisher","DOI":"10.1145\/169728.169723"},{"key":"S0890060411000229_ref66","doi-asserted-by":"publisher","DOI":"10.1145\/1360612.1360614"}],"container-title":["Artificial Intelligence for Engineering Design, Analysis and Manufacturing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0890060411000229","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T03:55:03Z","timestamp":1556337303000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0890060411000229\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10,12]]},"references-count":73,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["S0890060411000229"],"URL":"https:\/\/doi.org\/10.1017\/s0890060411000229","relation":{},"ISSN":["0890-0604","1469-1760"],"issn-type":[{"value":"0890-0604","type":"print"},{"value":"1469-1760","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,10,12]]}}}