Abstract
This paper deals with the problem of planning a path for a robot vehicle amidst obstacles. The kinematics of the vehicle being considered are of the unicycle or car-like type, i.e. are subject to nonholonomic constraints. Moreover, the trajectories of the robot are supposed not to exceed a given bound on curvature, that incorporates physical limitations of the allowable minimum turning radius for the vehicle. The method presented in this paper attempts at extending Reeds and Shepp's results on shortest paths of bounded curvature in absence of obstacles, to the case where obstacles are present in the workspace. The method does not require explicit construction of the configuration space, nor employs a preliminary phase of holonomic trajectory planning. Successfull outcomes of the proposed technique are paths consisting of a simple composition of Reeds/Shepp paths that solve the problem. For a particular vehicle shape, the path provided by the method, if regular, is also the shortest feasible path. In its original version, however, the method may fail to find a path, even though one may exist. Most such empasses can be overcome by use of a few simple heuristics, discussed in the paper. Applications to both unicycle and car-like (bicycle) mobile robots of general shape are described and their performance and practicality discussed.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Aicardi, M., Casalino, G., Balestrino, A., Bicchi, A.: 1994, Closed loop smooth steering of unicycle-like vehicles, in Proc. 33rd Conf. on Decision and Control, pp. 2455–2458.
Barraquand, J. and Latombe, J. C.: 1989, On nonholonomic mobile robots and optimal maneuvering, Proc. 4th Int. Symp. of Intelligent Control, Albany, NY.
Barraquand, J. and Latombe, J. C.: 1990, Controllability of mobile robots with kinematic constraints, Tech. Report No. STAN-CS-90-1317, Dept. of Computer Science, Stanford University.
Boissonnat, J. D., Cerezo, A. and Leblond, J.: 1992, Shortest paths of bounded curvature in the plane, in Proc. IEEE Int. Conf. on Robotics and Automation, pp. 2315–2320.
BrysonA. E. and HoY.: 1975, Applied Optimal Control, Hemisphere Washington, DC.
DubinsL. E.: 1957, On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents, Amer. J. Math. 79, 497–516.
Fortune, S. J. and Wilfong, G. T.: 1988, Planning constrained motion, in Proc. 4th ACM Symposium on Computational Geometry, pp. 445–459.
Jacobs, P. and Canny, J.: 1989, Planning smooth paths for mobile robots, IEEE Int. Conf. on Robotics and Automation, AZ 2–7.
JacobsP., LaumondJ. P., TaixM. and MurrayR.: 1990, Fast and exact trajectory planning for mobile robots and other systems with nonholonomic constraints, Tech. Report 90318, LAAS/CNRS, Toulouse, France.
LatombeJ-C.: 1990, Robot Motion Planning, Kluwer Academic Publishers, Dordrecht.
Laumond, J. P.: 1986, Feasible trajectories for mobile robots with kinematic and environment constraints, in Proc. Int. Conf. on Intelligent Autonomous Systems, Amsterdam, pp. 346–354.
Mirtich, B., Canny, J.: 1990, Using skeletons for nonholonomic path planning among obstacles, in IEEE Int. Conf. on Robotics and Automation, pp. 2533–2540.
Monaco, S. and Normand-Cyrot, D.: 1992, An introduction to motion planning under multirate digital control, Proc. Conf. on Decision and Control.
MurrayR. and SastryS. S.: 1993, Nonholonomic motion planning: Steering using sinusoids, IEEE Trans. Automatic Control 38(5), 700–716.
PontryaginL. S., BoltyanskiiV. G., GamkrelidzeR. V., and MishchenkoE. F.: 1962, The Mathematical Theory of Optimal Processes, Interscience, New York.
Reeds, J. A., Shepp, R. A.: 1990, Optimal paths for a car that goes both forward and backward, Pacific J. Math. 145(2).
Sussmann, H. J. and Tang, G.: 1991, Shortest paths for the reeds-shepp car: A worked out example of the use of geometric techniques in nonlinear optimal control, SYCON Report 91-10.
Author information
Authors and Affiliations
Additional information
The Authors are with the Centro “E. Plaggio” and Dipartimento di Sistemi Elettrici e Automazione, Università di Pisa, Italia. This work was supported in part by the C. N. R.-Progetto Finalizzato Robotica Grants 93.01079.PF67 and 93.00880.PF67.
Rights and permissions
About this article
Cite this article
Bicchi, A., Casalino, G. & Santilli, C. Planning shortest bounded-curvature paths for a class of nonholonomic vehicles among obstacles. J Intell Robot Syst 16, 387–405 (1996). https://doi.org/10.1007/BF00270450
Issue Date:
DOI: https://doi.org/10.1007/BF00270450