{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,18]],"date-time":"2025-12-18T13:48:55Z","timestamp":1766065735105,"version":"3.38.0"},"reference-count":26,"publisher":"SAGE Publications","issue":"8","license":[{"start":{"date-parts":[[1998,8,1]],"date-time":"1998-08-01T00:00:00Z","timestamp":901929600000},"content-version":"tdm","delay-in-days":0,"URL":"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":[[1998,8]]},"abstract":"<jats:p> We present a new and complete multilevel approachfor solving path- planning problems for nonholonomic robots. At the first level, a path is found that disrespects (some of) the nonholonomic constraints. At each of the next levels, a new path is generated by transformation of the path generated at the previous level. The transformation is such that more nonholonomic constraints are respected than at the previous level. At the final level, all nonholonomic constraints are respected. <\/jats:p><jats:p> We present two techniques for these transformations. The first, which we call the pick and link technique, repeatedly picks pieces from the given path, and tries to replace them by more feasible ones. The second technique restricts the free configuration space to a \"tube\" around the given path, and a road map that captures the free-space connectivity within this tube is constructed by the prob abilistic path planner. From this road map we retrieve a new, more feasible path. <\/jats:p><jats:p> In the intermediate levels, we plan paths for what we refer to as semiholonomic subsystems. Such systems are obtained by taking real (physical) systems, and removing some of their nonholonomic constraints. <\/jats:p><jats:p> In this paper, we apply the scheme to carlike robots pulling trail ers, that is, tractor-trailer robots. In this case, the real system is the tractor-trailer robot, and the ignored constraints in the semiholo nomic subsystems are the kinematic ones on the trailers. These are the constraints of rolling without slipping, on the trailer's wheels. <\/jats:p><jats:p> Experimental results are given that illustrate the time efficiency of the resulting planner. In particular, we show that using the multilevel scheme leads to significantly better performance (in computation time and path shape) than direct transformations to feasible paths. <\/jats:p>","DOI":"10.1177\/027836499801700803","type":"journal-article","created":{"date-parts":[[2007,3,11]],"date-time":"2007-03-11T07:05:13Z","timestamp":1173596713000},"page":"840-857","source":"Crossref","is-referenced-by-count":83,"title":["Multilevel Path Planning for Nonholonomic Robots Using Semiholonomic Subsystems"],"prefix":"10.1177","volume":"17","author":[{"given":"Sepanta","family":"Sekhavat","sequence":"first","affiliation":[{"name":"Laboratoire d'Analyse et d'Architecture des Syst\u00e8mes-Centre National de la Recherche Scientifique (LAAS-CNRS) 31077 Toulouse cedex, France"}]},{"given":"Petr","family":"Svestka","sequence":"additional","affiliation":[{"name":"Department of Computer Science Utrecht University 3508 Utrecht, The Netherlands"}]},{"given":"Jean-Paul","family":"Laumond","sequence":"additional","affiliation":[{"name":"Centre National de la Recherche Scientifique (LAAS\/CNRS) 31077 Toulouse cedex, France"}]},{"given":"Mark H.","family":"Overmars","sequence":"additional","affiliation":[{"name":"Department of Computer Science Utrecht University 3508 Utrecht, The Netherlands"}]}],"member":"179","published-online":{"date-parts":[[1998,8,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01891837"},{"volume-title":"Canonical nilpotent approximation of control systems: Application to nonholonomic motion planning. Proc. IEEE Conf. on Decision and Control","year":"1993","author":"Bella\u00efche, A.","key":"atypb2"},{"volume-title":"A method of progressive constraints for nonholonomic motion planning. Technical Report","year":"1995","author":"Ferbach, R.","key":"atypb3"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-3176-0_10"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1080\/00207179508921959"},{"volume-title":"PlaGeo\u2014A Library for Planar Geometry","year":"1993","author":"Giezeman, G.-J.","key":"atypb6"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"volume-title":"Motion planning for controllable systems without drift: A preliminary report. Technical Report SYSCON-90-04, Department of Mathematics","year":"1990","author":"Lafferriere, G.","key":"atypb8"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-3176-0_5"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/70.326564"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"Laumond, J.P., Sekhavat, S., and Vaisset, M. 1994 (Capri, Italy). Collision-free motion planning for a nonholonomic mobile robot with trailers. Proc. 4th IFAC Symp. on Robot Control . Ercolano, Italy: Cuen Editrice, pp. 171-177.","DOI":"10.1016\/S1474-6670(17)47311-3"},{"journal-title":"Proc. Int. Workshop on Adv. Motion Control","year":"1994","author":"Luzeaux, D.","key":"atypb12"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":". Mirtich, B., and Canny, J. 1992. Using skeletons for nonholonomic path planning. In Proc. IEEE Int. Conf. on Robotics and Automation, pp. 2533-2540, Nice, France.","DOI":"10.1109\/ROBOT.1992.220060"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"Murray, R., and Sastry, S. 1990 (Honolulu, HI). Steering nonholonomic systems using sinusoids. Proc. IEEE Conf. on Decision and Control. Los Alamitos, CA: IEEE, pp. 2097-2101.","DOI":"10.1109\/CDC.1990.203994"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1990.145.367"},{"key":"atypb16","first-page":"1518","author":"Rouchon, P.","year":"1993","journal-title":"Proc. European Control Conf."},{"volume-title":"An obstacle avoidance algorithm for a car pulling many trailers with kingpin hitching. Technical Report UCB\/ERL M94\/10","year":"1994","author":"Sahai, A.","key":"atypb17"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"Sekhavat, S., and Laumond, J.P. 1996 (Minneapolis, MN). Topological property of trajectories computed from sinusoidal inputs for nonholonomic chained form systems. Proc. IEEE Int. Conf. on Robot. and Automat. Madison, WI: Omnipress, pp. 3383-3388.","DOI":"10.1109\/ROBOT.1996.509227"},{"volume-title":"Probabilistic path planning for tractor-trailer robots. Technical Report 96007, LAAS\/CNRS","year":"1996","author":"Sekhavat, S.","key":"atypb19"},{"key":"atypb20","unstructured":"Sordalen, O.J. 1993 (Atlanta, GA). Conversion of a car with n trailers into a chained form. Proc. IEEE Int. Conf. on Robot. and Automat . Los Alamitos, CA: IEEE, pp. 1382-1387."},{"volume-title":"Limits of highly oscillatory controls and the approximation of general paths by admissible trajectories. Technical Report SYSCON-91-02, SYCON","year":"1991","author":"Sussmann, H.J.","key":"atypb21"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1177\/027836499701600201"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"\u0160vestka, P., and Vleugels, J. 1995 (Nagoya, Japan). Exact motion planning for tractor-trailer robots. Proc. IEEE Int. Conf. on Robot. and Automat. Los Alamitos, CA: IEEE, pp. 2445-2450.","DOI":"10.1109\/ROBOT.1995.525626"},{"key":"atypb24","series-title":"Proc. IEEE Int. Conf. on Robotics and Automation","volume-title":"Steering carlike systems with trailers using sinusoids","author":"Tilbury, D.","year":"1992"},{"volume-title":"Trajectory generation for the n-trailer problem using Goursat normal form. Proc. IEEE Int. Conf. on Decision and Control","year":"1993","author":"Tilbury, D.","key":"atypb25"},{"key":"atypb26","unstructured":"Vershik, A., and Gershkovich, V. 1988. Nonholonomic dynamical systems: Distribution geometry and variational problems. Modern Mathematics Problems, Dynamic Systems vol. 16. Moscow: Viniti, pp. 1518-1522. (English translation, 1990, available from Springer-Verlag.)"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836499801700803","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/027836499801700803","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T22:19:00Z","timestamp":1740867540000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/027836499801700803"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,8]]},"references-count":26,"journal-issue":{"issue":"8","published-print":{"date-parts":[[1998,8]]}},"alternative-id":["10.1177\/027836499801700803"],"URL":"https:\/\/doi.org\/10.1177\/027836499801700803","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"type":"print","value":"0278-3649"},{"type":"electronic","value":"1741-3176"}],"subject":[],"published":{"date-parts":[[1998,8]]}}}