Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-15T11:08:26.987Z Has data issue: false hasContentIssue false
  • English
  • Français

Local path planning for mobile robots based on intermediate objectives

Published online by Cambridge University Press:  01 April 2014

Yingchong Ma ,
Gang Zheng ,
Wilfrid Perruquetti  and
Zhaopeng Qiu
Yingchong Ma*
Affiliation:
LAGIS CNRS UMR 8219, Ecole Centrale de Lille, BP 48, 59651 Villeneuve d'Ascq, France
Gang Zheng
Affiliation:
Non-A Team, INRIA – Lille Nord Europe, 40 Avenue Halley, 59650 Villeneuve d'Ascq, France
Wilfrid Perruquetti
Affiliation:
LAGIS CNRS UMR 8219, Ecole Centrale de Lille, BP 48, 59651 Villeneuve d'Ascq, France Non-A Team, INRIA – Lille Nord Europe, 40 Avenue Halley, 59650 Villeneuve d'Ascq, France
Zhaopeng Qiu
Affiliation:
LAGIS CNRS UMR 8219, Ecole Centrale de Lille, BP 48, 59651 Villeneuve d'Ascq, France
*
*Corresponding author. E-mail: yingchong.ma@ec-lille.fr
Get access Rights & Permissions [Opens in a new window]

Summary

This paper presents a path planning algorithm for autonomous navigation of non-holonomic mobile robots in complex environments. The irregular contour of obstacles is represented by segments. The goal of the robot is to move towards a known target while avoiding obstacles. The velocity constraints, robot kinematic model and non-holonomic constraint are considered in the problem. The optimal path planning problem is formulated as a constrained receding horizon planning problem and the trajectory is obtained by solving an optimal control problem with constraints. Local minima are avoided by choosing intermediate objectives based on the real-time environment.

Keywords

Mobile robotsMotion planningNavigationPath planningNon-holonomic robots
Type
Articles
Information
Robotica , Volume 33 , Issue 4 , May 2015 , pp. 1017 - 1031
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Pearsall, J., Concise Oxford Dictionary, 10th Revised ed. (Oxford University Press, Oxford, UK, 2001).Google Scholar
2. Brooks, R. and Lozano-Perez, T., “A subdivision algorithm in configuration space for findpath with rotation,” IEEE Trans. Syst. Man Cybern. SMC-15 (2), 224–233 (1985).CrossRefGoogle Scholar
3. Glavaški, D., Volf, M. and Bonkovic, M., “Robot Motion Planning Using Exact Cell Decomposition and Potential Field Methods,” Proceedings of the 9th WSEAS International Conference on Simulation, Modelling and Optimization (SMO'09) (2009) pp. 126–131.Google Scholar
4. Dudek, G. and Jenkin, M., Computational Principles of Mobile Robotics (Cambridge University Press, Cambridge, UK, 2010).CrossRefGoogle Scholar
5. Huang, H.-P. and Chung, S.-Y., “Dynamic Visibility Graph for Path Planning,” Proceedings of 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2004), vol. 3 (2004) pp. 2813–2818.Google Scholar
6. Bicchi, A., Casalino, G. and Santilli, C., “Planning shortest bounded-curvature paths for a class of non-holonomic vehicles among obstacles,” J. Intell. Robot. Syste. 16 (4), 387–405 (1996).CrossRefGoogle Scholar
7. 'Dnlaing, C. and Yap, C. K., “A “retraction” method for planning the motion of a disc,” J.Algorithms, 6 (1), 104–111 (1985).CrossRefGoogle Scholar
8. Dijkstra, E., “A note on two problems in connexion with graphs,” Numer. Mathe., 1 (1), 269–271 (1959).CrossRefGoogle Scholar
9. Hart, P., Nilsson, N. and Raphael, B., “A formal basis for the heuristic determination of minimum cost paths,” IEEE Trans. Syst. Sci. Cybern. 4 (2), 100–107 (1968).CrossRefGoogle Scholar
10. Nearchou, A. C., “Path planning of a mobile robot using genetic heuristics,” Robotica 16 (5), 575–588 (1998).CrossRefGoogle Scholar
11. Ismail, A.-T., Sheta, A. and Al-Weshah, M., “A mobile robot path planning using genetic algorithm in static environment,” J. Comput. Sci. 4 (4), 341–344 (2008).Google Scholar
12. Schwartz, J. T. and Sharir, M., “On the piano movers' problem (i) the case of a two-dimensional rigid polygonal body moving amidst polygonal barriers,” Commun. Pure Appl. Math. 36 (3), 345–398 (1983).CrossRefGoogle Scholar
13. Nilsson, N. J., Principles of Artificial Intelligence (Tioga, Grayson, TX, 1980).Google Scholar
14. Stentz, A., “Optimal and Efficient Path Planning for Partially-Known Environments,” Proceedings of the 1994 IEEE International Conference on Robotics and Automation (1994), pp. 3310–3317.Google Scholar
15. Choset, H. and Nagatani, K., “Topological simultaneous localization and mapping (slam): Toward exact localization without explicit localization,” IEEE Trans. Robot. Autom. 17, 125–137 (Apr. 2001).CrossRefGoogle Scholar
16. Goto, Y. and Stentz, A., “Mobile robot navigation: The CMU system,” IEEE Expert 2, 44–54 (1987).CrossRefGoogle Scholar
17. Lumelsky, V. J. and Stepanov, A. A., “Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape,” Algorithmica 2, 403–430 (1987).CrossRefGoogle Scholar
18. Khatib, O., “Real-Time Obstacle Avoidance for Manipulators and Mobile Robots,” Proceedings of the 1985 IEEE International Conference on Robotics and Automation, vol. 2 (1985) pp. 500–505.Google Scholar
19. Latombe, J.-C., Robot Motion Planning: Edition en anglais, Springer International Series in Engineering and Computer Science (Springer, Boston, MA, 1991).Google Scholar
20. Koren, Y. and Borenstein, J., “Potential Field Methods and Their Inherent Limitations for Mobile Robot Navigation,” Proceedings of the 1991 IEEE International Conference on Robotics and Automation, vol. 2 (1991) pp. 1398–1404.Google Scholar
21. Kolmanovsky, I. and McClamroch, N., “Developments in nonholonomic control problems,” IEEE Control Syst. 15 (6), 20–36 (1995).Google Scholar
22. Laumond, J., Robot Motion Planning and Control, Lecture Notes in Control and Information Sciences (Springer, Boston, MA, 1998).CrossRefGoogle Scholar
23. Guo, Y. and Tang, T., “Optimal Trajectory Generation for Nonholonomic Robots in Dynamic Environments,” Proceedings of the IEEE International Conference on Robotics and Automation (ICRA 2008) (May 2008) pp. 2552–2557.Google Scholar
24. Defoort, M., Palos, J., Kokosy, A., Floquet, T. and Perruquetti, W., “Performance-based reactive navigation for non-holonomic mobile robots,” Robotica 27 (2), 281–290 (Mar. 2009).CrossRefGoogle Scholar
25. Kokosy, A., Defaux, F.-O. and Perruquetti, W., “Autonomous Navigation of a Nonholonomic Mobile Robot in a Complex Environment,” Proceedings of the IEEE International Workshop on Safety, Security and Rescue Robotics (SSRR 2008) (2008) pp. 102–108.Google Scholar
26. Kamon, I., Rimon, E. and Rivlin, E., “A New Range-Sensor Based Globally Convergent Navigation Algorithm for Mobile Robots,” Proceedings of the 1996 IEEE International Conference on Robotics and Automation, vol. 1 (Apr. 1996) pp. 429–435.Google Scholar
27. Fliess, M., Lvine, J. and Rouchon, P., “Flatness and defect of nonlinear systems: Introductory theory and examples,” Int. J. Control 61, 1327–1361 (1995).Google Scholar
28. Mayne, D. and Michalska, H., “Receding horizon control of nonlinear systems,” IEEE Trans. Autom. Control 35 (7), 814–824 (1990).CrossRefGoogle Scholar
29. Lawrence, C., Zhou, J., and Tits, A., “User's Guide for CFSQP Version 2.5: AC Code for Solving (Large Scale) Constrained Nonlinear (Minimax) Optimization Problems, Generating Iterates Satisfying All Inequality Constraints,” Technical Report TR-94-16r1, Institute for Systems Research, University of Maryland (Aug. 1995).Google Scholar
30. Lawrence, C. T. and Tits, A. L., “A computationally efficient feasible sequential quadratic programming algorithm,” SIAM J. Optim. 11, 1092–1118 (2001).Google Scholar
31. Graham, R. L., “An efficient algorithm for determining the convex hull of a finite planar set,” Inf. Process. Lett. 1 (4) 132–133 (1972).CrossRefGoogle Scholar