Optimization approaches for robot trajectory planning

Carlos Llopis-Albert, Francisco Rubio, Francisco Valero

Abstract

The development of optimal trajectory planning algorithms for autonomous robots is a key issue in order to efficiently perform the robot tasks. This problem is hampered by the complex environment regarding the kinematics and dynamics of robots with several arms and/or degrees of freedom (dof), the design of collision-free trajectories and the physical limitations of the robots. This paper presents a review about the existing robot motion planning techniques and discusses their pros and cons regarding completeness, optimality, efficiency, accuracy, smoothness, stability, safety and scalability.


Keywords

Algorithms; Optimal Trajectory; Kinematic and Dynamic constraints; Minimum time; Energy; Obstacle avoidance

Full Text:

PDF

References

J.C. Latombe, Robot motion planning. Kluwer Academic Publisher, Boston, 1991. https://doi.org/10.1007/978-1-4615-4022-9

S.M. LaValle, Planning Algorithms. Published by Cambridge University Press, 842p., 2006. https://doi.org/10.1017/CBO9780511546877

S.H. Tang, W. Khaksar, N.B. Ismail, and M.K.A. Ariffi, A Review on Robot Motion Planning Approaches. Pertanika Journal of Science & Technology 20(1), (2012) 15–29.

P. Raja, and S. Pugazhenthi, Optimal path planning of mobile robots: A review. International Journal of Physical Sciences 7(9) (2012) 1314-1320. DOI: 10.5897/IJPS11.1745. https://doi.org/10.5897/IJPS11.1745

Z. Shiller, Off-Line and On-Line Trajectory Planning. In Carbone, G., and Gomez-Bravo, F. (eds.), Motion and Operation Planning of Robotic Systems, Mechanisms and Mace Science 29 (2015), Springer, Cham. https://doi.org/10.1007/978-3-319-14705-5_2

V. Lumelsky and A. Stepanov, Path planning strategies for point mobile automaton moving amidst unknown obstacles of arbitrary shape. Algorithmica 2 (1987) 403–430. https://doi.org/10.1007/BF01840369

C.O. Dunlaing, and C.K. Yap, A retraction method for planning the motion of a disc. Journal of Algorithms 6 (1985) 104-111. https://doi.org/10.1016/0196-6774(85)90021-5

T. Osama and R.J. Schilling, Motion Planning in a Plane Using Generalized Voronoi Diagram. IEEE Transactions on Robotics and Automation 5(2) (1989) 143-150. https://doi.org/10.1109/70.88035

T. Lozano-Perez, and M.A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles. Communications ACM, 22(10) (1979) 560–570. https://doi.org/10.1145/359156.359164

T. Asano, L. Guibas, J. Hershberger, and H. Imai, Visibility-polygon search and Euclidean shortest paths. Paper presented at the Foundations of Computer Science, 26th Annual Symposium on, 21-23 October. Automation. ETFA '06. IEEE Conference on. (1985). https://doi.org/10.1109/SFCS.1985.65

L. Li, T. Ye, M. Tan, and X. Chen, Present state and future development of mobile robot technology research. Robot 24(5) (2002) 475-480.

R. Siegwart, and I.R. Nourbakhsh, Introduction to autonomous mobile robot. Massachusetts Institute of Technology press, Cambridge, U.S.A (2004).

Y.H. Liu, and S. Arimoto, Path planning using a tangent graph for mobile robots among polygonal and curved obstacles. International Journal of Robotics Research 11(4) (1992) 376–382. https://doi.org/10.1177/027836499201100409

T. Lozano-Perez, Spatial planning: A configuration approach. IEEE Transactions on Computers C-32(3) (1983) 108-120. https://doi.org/10.1109/TC.1983.1676196

R.A. Brooks, and T. Lozano-Perez, A subdivision algorithm in configuration space for find path with rotation. Proceedings of eighth International Joint Conference on Artificial Intelligence, Karlsruhe, Germany, pp. 799-806 (1983).

J.M. Keil, and J.R. Sack, Minimum decomposition of polygonal objects. Machine Intelligence and Pattern Recognition 2 (1985) 197-216. https://doi.org/10.1016/B978-0-444-87806-9.50012-8

D.J. Zhu, and J.C. Latombe, New heuristic algorithms for efficient hierarchical path planning. Technical report STAN-CS-89-1279, Computer Science Department, Stanford University, USA (1989).

D.W. Payton, J.K. Rosenblatt, and D.M. Keirsey, Grid-based mapping for autonomous mobile robot. Robotics and Autonomous Systems 11(1) (1993) 13-21. https://doi.org/10.1016/0921-8890(93)90004-V

M. Likhachev, D. Ferguson, G. Gordon, A. Stentz, and S. Thrun, Anytime dynamic A*: An anytime, replanning algorithm. Proceedings of the International Conference on Automated Planning and Scheduling, pp. 262-271 (2005).

O. Hachour, The proposed genetic FPGA implementation for path planning of autonomous mobile robot. Circuits, Systems and Signal Processing 2(2) (2008) 151-167.

O. Hachour, Path planning of autonomous mobile robot. International journal of systems applications, engineering & development 4(2) (2008) 178-190.

J. Canny, and J. Reif, New lower bound techniques for robot motion planning problems. Proceedings of IEEE Symposium on the Foundations of Computer Science, Los Angeles, California, 49-60(1987). https://doi.org/10.1109/SFCS.1987.42

B. Faverjon, and P. Tournassoud, A local approach for path planning of manipulators with a high number of degrees of freedom. In Proceeding of IEEE International Conference on Robotics and Automation, 1152-1159 (1987). https://doi.org/10.1109/ROBOT.1987.1087982

J.J. Kuffner, and S.M. LaValle, RRT-connect: An efficient approach to single-query path planning. In IEEE International Conference on Robotics and Automation, 995–1001 (2000). https://doi.org/10.1109/ROBOT.2000.844730

Q.-C. Pham, and S. Caron, Y. Nakamura, Kinodynamic planning in the configuration space via velocity interval propagation, in Robotics: Science and System (2013).

O. Khatib, Real time obstacle avoidance for manipulators and mobile robots. International Journal of Robotics Research 5(1) (1986) 90-98. https://doi.org/10.1177/027836498600500106

L.E. Kavraki, P. Švestka, J.C. Latombe, and M.H. Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation 12(4) (1996) 566–580. https://doi.org/10.1109/70.508439

M. Overmars, and P. Svestka, A probabilistic learning approach to motion planning. In K. Goldberg, D. Halperin, J. C. Latombe, and R. Wilson (eds.). Algorithmic Foundations of Robotics (WAFR), 19–37, A. K. Peters, Ltd (1995).

L.E. Kavraki, J.C. Latombe, R. Motwani, and P. Raghavan, Randomized query processing in robot path planning. Journal of Computer and System Sciences 57(1) (1998) 50–60. https://doi.org/10.1006/jcss.1998.1578

D. Hsu, Randomized Single-Query Motion Planning In Expansive Spaces. PhD Thesis, Department of Computer Science, Stanford University (2000).

K. Sugihara, and J. Smith, Genetic algorithms for adaptive motion planning of an autonomous mobile robot. Proceedings of the IEEE International Symposium on Computational Intelligence in Robotics and Automation, Monterey, California, pp. 138-143 (1997). https://doi.org/10.1109/CIRA.1997.613850

M.M. Mohamad, N.K. Taylor, and M.W. Dunnigan, Articulated Robot Motion Planning Using Ant Colony Optimisation. Paper presented at the Intelligent Systems, 2006 3rd International IEEE Conference on (2006). https://doi.org/10.1109/IS.2006.348503

T. Guan-Zheng, H.E. Huan, and A. Sloman. Global optimal path planning for mobile robot based on improved Dijkstra algorithm and ant system algorithm. Journal of Central South University of Technology 13(1) (2006) 80-86. https://doi.org/10.1007/s11771-006-0111-8

M.A.P. Garcia, O. Montiel, O. Castillo, R. Sepulveda, and P. Melin, Path planning for autonomous mobile robot navigation with ant colony optimization and fuzzy cost evaluation. Applied Soft Computing 9 (2009) 1102-1110. https://doi.org/10.1016/j.asoc.2009.02.014

K. Manousakis, T. McAuley, R. Morera, and J. Baras, Using multi-objective domain optimization for routing in hierarchical networks. Proceedings of the International Conference on Wireless Networks, Communication and Mobile Computing, 1460-1465 (2005). https://doi.org/10.1109/WIRLES.2005.1549628

E. Masehian, and M.R. Amin-Naseri, Composite models for mobile robot offline path planning, Mobile robots: Perception and navigation. In Tech Publisher, Croatia (2007).

A. Zhu, and S.X. Yang, A Neural Network Approach to Dynamic Task Assignment of Multirobots. IEEE Transaction on Neural Networks 17(5) (2006) 1278-1287. https://doi.org/10.1109/TNN.2006.875994

J.H. Holland, Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, USA (1975).

D.E. Goldberg, Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Delhi, India (2000).

Z. Qingfu, S. Jianyong, X. Gaoxi, and E. Tsang, Evolutionary Algorithms Refining a Heuristic: A Hybrid Method for Shared-Path Protections in WDM Networks Under SRLG Constraints. Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, 37(1) (2007) 51-61.

J. Kennedy, and R.C. Eberhart, Particle swarm optimization. Proceedings of the IEEE International Conference on Neural Networks, Perth, Australia, 1942-1948 (1995). https://doi.org/10.1109/ICNN.1995.488968

Y.Q. Qin, D.B. Sun, N. Li, and Y.G. Cen, Path Planning for mobile robot using the particle swarm optimization with mutation operator. Proceedings of the IEEE International Conference on Machine Learning and Cybernetics, Shanghai, 2473-2478 (2004).

M. Saska, M. Macas, L. Preucil, and L. Lhotska, Robot Path Planning using Particle Swarm Optimization of Ferguson Splines. Emerging Technologies and Factory Automation, 2006. ETFA '06. IEEE Conference on. Prague, Czech Republic, 20-22 September. https://doi.org/10.1109/ETFA.2006.355416

J. Kuffner, S. Kagami, K. Nishiwaki, M. Inaba, and H. Inoue, Dynamically-stable motion planning for humanoid robots. Autonomous Robots 12(1) (2002) 105-118. https://doi.org/10.1023/A:1013219111657

A.Z. Nasrollahy, H.H.S. Javadi, Using particle swarm optimization for robot path planning in dynamic environments with moving obstacles and target. Third European Symposium on computer modeling and simulation, Athens, Greece, 60-65 (2009). https://doi.org/10.1109/EMS.2009.67

D.W. Gong, J.H. Zhang, and Y. Zhang, Multi-objective particle swarm optimization for robot path planning in environment with danger sources. Journal of Computers 6(8) (2011) 1554-1561. https://doi.org/10.4304/jcp.6.8.1554-1561

R.R. Cazangi, F.J. Von Zuben, and M.F. Figueiredo, Evolutionary Stigmergy in Multipurpose Navigation Systems. Evolutionary Computation, 2006. CEC 2006. IEEE Congress on. Vancouver, BC, Canada, 16-21 July. (2006).

https://doi.org/10.1109/CEC.2006.1688332

D.K. Pai, and L.M. Reissell, Multiresolution rough terrain motion planning. IEEE Transaction on Robotic and Automation, 14(1) (1998) 19- 33. https://doi.org/10.1109/70.660835

Q.R. Zhang, and G.C. Gu, Path planning based on improved binary particle swarm optimization algorithm. Proceedings of the IEEE International Conference on Robotics, Automation and Mechatronics, Chendu, China, 462-466 (2008).

T.L. Lee, and C.J. Wu, Fuzzy Motion Planning of Mobile Robots in Unknown Environments. Journal of Intelligent and Robotic Systems 37(2) (2003) 177-191. https://doi.org/10.1023/A:1024145608826

P.S. Maybeck, The Kalman Filter: An Introduction to Concepts. In: Cox I.J., Wilfong G.T. (eds) Autonomous Robot Vehicles. Springer, New York, NY (1990). https://doi.org/10.1007/978-1-4613-8997-2_15

M. Fakoor, A. Kosari, and M. Jafarzadeh, Humanoid robot path planning with fuzzy Markov decision processes. Journal of Applied Research and Technology 14(5) (2016) 300-310. https://doi.org/10.1016/j.jart.2016.06.006

H. Choset, K.M. Lynch, and S. Hutchinson, Principles of Robot Motion: Theory, Algorithms, and Implementations. MIT Press. ISBN: 9780262033275. (2005).

L. Yang, J. Qi, D. Song, J. Xiao, J. Han, and Y. Xia, Survey of Robot 3D Path Planning Algorithms. Journal of Control Science and Engineering (2016) pp. 22. https://doi.org/10.1155/2016/7426913

F. Rubio, C. Llopis-Albert, F. Valero, and J.L. Su-er, Assembly line productivity assessment by comparing optimization-simulation algorithms of trajectory planning for industrial robots. Mathematical Problems in Engineering (2015). https://doi.org/10.1155/2015/931048

F. Rubio, C. Llopis-Albert, and F. Valero, J.L. Su-er, Industrial robot efficient trajectory generation without collision through the evolution of the optimal trajectory. Robotics and Autonomous Systems 86 (2016) 106–112. https://doi.org/10.1016/j.robot.2016.09.008

C. Llopis-Albert, F. Rubio, and F. Valero. Improving productivity using a multi-objective optimization of robotic trajectory planning. Journal of Business Research 68(7) (2015) 1429-1431. https://doi.org/10.1016/j.jbusres.2015.01.027

C. Llopis-Albert, and D. Palacios-Marqués, Applied Mathematical Problems in Engineering. Multidisciplinary Journal for Education, Social and Technological Sciences 3(2) (2016) 1-14. https://doi.org/10.4995/muse.2016.6679

W. Xing, J. Zhang, W. Lu, and P. Bao, An Improved Potential Field Based Method for Crowd Simulation. International Journal of Software Engineering and Knowledge Engineering 25(03) (2015) 427-451. https://doi.org/10.1142/S021819401540015X

J. Sobecki, Comparison of Selected Swarm Intelligence Algorithms in Student Courses Recommendation Application. International Journal of Software Engineering and Knowledge Engineering 24(1) (2014) 91-109. https://doi.org/10.1142/S0218194014500041

A. Saeed, S.H.A. Hamid, and A.A. Sani, Cost and Effectiveness of Search-Based Techniques for Model-Based Testing: An Empirical Analysis. International Journal of Software Engineering and Knowledge Engineering 27(04) (2017) 601-622. https://doi.org/10.1142/S021819401750022X

Abstract Views

1278
Metrics Loading ...

Metrics powered by PLOS ALM


 

Cited-By (articles included in Crossref)

This journal is a Crossref Cited-by Linking member. This list shows the references that citing the article automatically, if there are. For more information about the system please visit Crossref site

1. Optimal Reconfiguration of a Parallel Robot for Forward Singularities Avoidance in Rehabilitation Therapies. A Comparison via Different Optimization Methods
Carlos Llopis-Albert, Francisco Valero, Vicente Mata, José L. Pulloquinga, Pau Zamora-Ortiz, Rafael J. Escarabajal
Sustainability  vol: 12  issue: 14  first page: 5803  year: 2020  
doi: 10.3390/su12145803




This journal is distributed under a Creative Commons Attribution-NonCommercial-NonDerivs 4.0 Internacional License.

Universitat Politècnica de València

e-ISSN: 2341-2593   https://dx.doi.org/10.4995/muse