Abstract
This paper deals with autonomous navigation of unmanned ground vehicles (UGV). The UGV has to reach its assigned final configuration in a structured environments (e.g. a warehouse or an urban environment), and to avoid colliding neither with the route boundaries nor any obstructing obstacles. In this paper, vehicle planning/set-points definition is addressed. A new efficient and flexible methodology for vehicle navigation throughout optimal and discrete selected waypoints is proposed. Combining multi-criteria optimization and expanding tree allows safe, smooth and fast vehicle overall navigation. This navigation through way-points permits to avoid any path/trajectory planning which could be time consuming and complex, mainly in cluttered and dynamic environment. To evaluate the flexibility and the efficiency of the proposed methodology based on expanding tree (taking into account the vehicle model and uncertainties), an important part of this paper is dedicated to give an accurate comparison with another proposed optimization based on the commonly used grid map. A set of simulations, comparison with other methods and experiments, using an urban electric vehicle, are presented and demonstrate the reliability of our proposals.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Abbadi, A., Matousek, R., Petr Minar, P.S.: RRTs review and options. In: Proceedings of the International Conference on Energy, Environment, Economics, Devices, Systems, Communications, Computers (2011)
Adouane, L., Benzerrouk, A., Martinet, P.: Mobile robot navigation in cluttered environment using reactive elliptic trajectories. In: Proceedings of the 18th IFAC World Congress (2011)
Aicardi, M., Casalino, G., Bicchi, A., Balestrino, A.: Closed loop steering of unicycle like vehicles via lyapunov techniques. J. Math. Mech. IEEE 2(1), 27–35 (1995)
Bellman, R.: A markovian decision process. J. Math. Mech. 6, 679–684 (1957)
Bertsekas, D.P.: Dynamic Programming and Optimal Control, vol. I. Athena Scientific (1995)
Bonfè, M., Secchi, C., Scioni, E.: Online trajectory generation for mobile robots with kinodynamic constraints and embedded control systems. In: Proceedings of the 10th International IFAC Symposium on Robot Control. Croatia (2012)
Choset, H., Lynch, K.M., Hutchinson, S., Kantor, G., Burgard, W., Kavraki, L.E., Thrun, S.: Principles of Robot Motion: Theory, Algorithms, and Implementation. MIT Press (2005)
Connors, J., Elkaim, G.H.: Manipulating b-spline based paths for obstacle avoidance in autonomous ground vehicles. In: Proceedings of the ION National Technical Meeting, ION NTM 2007 San Diego (2007)
Consolini, L., Morbidi, F., Prattichizzo, D., Tosques, M.: Leader-follower formation control of nonholonomic mobile robots with input constraints. Automatica 44(5), 1343–1349 (2008)
Gu, T., Dolan, J.M.: On-road motion planning for autonomous vehicles. In: Su, C.Y., Rakheja, S., Liu, H. (eds.) Intelligent Robotics and Applications, vol. 7508. Springer Berlin Heidelberg (2012)
Horst, J., Barbera, A.: Trajectory generation for an on-road autonomous vehicle. Proceedings of the SPIE, Unmanned Systems Technology VIII (2006)
The Institut Pascal Data Sets. http://ipds.univ-bpclermont.fr (2013)
Jazar, R.N.: Vehicle Dynamics: Theory and Application, Chapter 7. Springer-Verlag (2014)
Kallem, V., Komoroski, A., Kumar, V.: Sequential composition for navigating a nonholonomic cart in the presence of obstacles. IEEE Trans. Robot. 27(6), 1152–1159 (2011)
Karaman, S., Frazzoli, E.: Sampling-based Algorithms for Optimal Motion Planning. Int. J. Robot. Res. 30(7), 846–894 (2011)
Khalil, H.K.: Nonlinear Systems. Prentice Hall (2002). (1986)
Khatib, O.: Real-time obstacle avoidance for manipulators and mobile robots. Int. J. Robot. Res. 5, 90–99 (1986)
Kuwata, Y., Fiore, G.A., Teo, J., Frazzoli, E., How, J.P.: Motion planning for urban driving using rrt. In: International Conference on Intelligent Robots and Systems, pp. 1681–1686 (2008)
Labakhua, L., Nunes, U., Rodrigues, R., Leite, F.: Smooth trajectory planning for fully automated passengers vehicles: Spline and clothoid based methods and its simulation. In: Cetto, J., Ferrier, J.L., Costa dias Pereira, J.M., Filipe, J. (eds.) Informatics in Control Automation and Robotics, Lecture Notes Electrical Engineering, vol. 15, pp. 169–182. Springer Berlin Heidelberg (2008)
Latombe, J.C.: Robot Motion Planning. Kluwer Academic Publishers, Boston (1991)
LaValle, S. M.: Planning Algorithms. Cambridge University Press (2006)
Lee, J.W., Litkouhi, B.: A unified framework of the automated lane centering/changing control for motion smoothness adaptation. In: Proceedings of the 15th International IEEE Conference on Intelligent Transportation Systems (ITSC), pp. 282–287 (2012)
Luca, A.D., Oriolo, G., Samson, C.: Feedback control of a nonholonomic car-like robot. In: Laumond, J.P. (ed.) Proceedings of the Robot Motion Planning and Control, pp. 171–253. Springer-Verlag, Berlin (1998)
Maalouf, E., Saad, M., Saliah, H.: A higher level path tracking controller for a four-wheel differentially steered mobile robot. Robot. Auton. Syst. 54, 23–33 (2006)
Martins, M.M., Santos, C.P., Frizera-Neto, A., Ceres, R.: Assistive mobility devices focusing on smart walkers: Classification and review. Robot. Auton. Syst. 60(4), 548–562 (2012)
Rucco, A., Notarstefano, G., Hauser, J.: Computing minimum lap-time trajectories for a single-track car with load transfer. In: Decision and Control (CDC), 2012 IEEE 51st Annual Conference on, pp. 6321–6326 (2012)
Sezen, B.: Modeling automated guided vehicle systems in material handling. Otomatiklestirilmi Rehberli Arac Sistemlerinin Transport Tekniginde Modellemesi. Dou Universitesi Dergisi 4(2), 207–216 (2011)
Sharma, S., Taylor, M.E.: Autonomous waypoint selection for navigation and path planning: A navigation framework for multiple planning algorithms. Tech. Rep. (2012)
Siciliano, B., Khatib, O. (eds.): Springer Handbook of Robotics, Part E-34. Springer (2008)
Stoeter, S.A., Rybski, P.E., Stubbs, K.N., McMillen, C.P., Gini, M., Hougen, D.F., Papanikolopoulos, N.: A robot team for surveillance tasks: Design and architecture. Robot. Auton. Syst. 40(2-3), 173–183 (2002)
Szczerba, R., Galkowski, P., Glicktein, I., Ternullo, N.: Robust algorithm for real-time route planning. IEEE Trans. Aerosp. Electron. Syst. 36(3), 869–878 (2000)
Vaz, D.A., Inoue, R.S., Grassi Jr. V.: Kinodynamic motion planning of a skid-steering mobile robot using rrts. In: Proceedings of the 2010 Latin American Robotics Symposium and Intelligent Robotics Meeting, LARS ’10, pp. 73–78. IEEE Computer Society (2010)
Vilca, J., Adouane, L., Mezouar, Y., Lébraly, P.: An overall control strategy based on target reaching for the navigation of an urban electric vehicle. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’13). Tokyo (2013)
Ziegler, J., Werling, M., Schroeder, J.: Navigating car-like robots in unstructured environment using an obstacle sensitive cost function. In: Proceedings of the IEEE Intelligent Vehicle Sympsium (IV), pp. 787–791. Netherlands (2008)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Vilca, J., Adouane, L. & Mezouar, Y. Optimal Multi-Criteria Waypoint Selection for Autonomous Vehicle Navigation in Structured Environment. J Intell Robot Syst 82, 301–324 (2016). https://doi.org/10.1007/s10846-015-0223-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-015-0223-1