An exact geometry-based algorithm for path planning

Jafarzadeh, H. ; Fleming, C. H.

International Journal of Applied Mathematics and Computer Science, Tome 28 (2018) no. 3, pp. 493-504.

Résumé

A novel, exact algorithm is presented to solve the path planning problem that involves finding the shortest collision-free path from a start to a goal point in a two-dimensional environment containing convex and non-convex obstacles. The proposed algorithm, which is called the shortest possible path (SPP) algorithm, constructs a network of lines connecting the vertices of the obstacles and the locations of the start and goal points which is smaller than the network generated by the visibility graph. Then it finds the shortest path from start to goal point within this network. The SPP algorithm generates a safe, smooth and obstacle-free path that has a desired distance from each obstacle. This algorithm is designed for environments that are populated sparsely with convex and nonconvex polygonal obstacles. It has the capability of eliminating some of the polygons that do not play any role in constructing the optimal path. It is proven that the SPP algorithm can find the optimal path in O(nn^’2) time, where n is the number of vertices of all polygons and n’ is the number of vertices that are considered in constructing the path network (n’ ≤ n). The performance of the algorithm is evaluated relative to three major classes of algorithms: heuristic, probabilistic, and classic. Different benchmark scenarios are used to evaluate the performance of the algorithm relative to the first two classes of algorithms: GAMOPP (genetic algorithm for multi-objective path planning), a representative heuristic algorithm, as well as RRT (rapidly-exploring random tree) and PRM (probabilistic road map), two well-known probabilistic algorithms. Time complexity is known for classic algorithms, so the presented algorithm is compared analytically.

Détail

Keywords: shortest possible path algorithm, path planning, collision free path
Mots-clés : algorytm najkrótszej ścieżki, planowanie ścieżki, ścieżka bezkolizyjna

Bibliographie

[1] Akbaripour, H. and Masehian, E. (2017). Semi-lazy probabilistic roadmap: A parameter-tuned, resilient and robust path planning method for manipulator robots, International Journal of Advanced Manufacturing Technology 89(5–8): 1401–1430.

[2] Asano, T., Asano, T., Guibas, L., Hershberger, J. and Imai, H. (1986). Visibility of disjoint polygons, Algorithmica 1(1): 49–63.

[3] Bohlin, R. and Kavraki, L.E. (2000). Path planning using lazy PRM, Proceedings of the IEEE International Conference on Robotics and Automation, ICRA’00, San Francisco, CA, USA, Vol. 1, pp. 521–528.

[4] Choset, H.M. (2005). Principles of Robot Motion: Theory, Algorithms, and Implementation, MIT Press, Cambridge, MA.

[5] Coello, C.A.C., Pulido, G.T. and Lechuga, M.S. (2004). Handling multiple objectives with particle swarm optimization, IEEE Transactions on Evolutionary Computation 8(3): 256–279.

[6] Coello, C.C., Lamont, G.B. and Van Veldhuizen, D.A. (2007). Evolutionary Algorithms for Solving Multi-Objective Problems, Springer, New York, NY.

[7] Cormen, T.H. (2001). Introduction to Algorithms, MIT Press, Cambridge, MA, pp. 595–601.

[8] Davoodi,M., Panahi, F., Mohades, A. and Hashemi, S.N. (2015). Clear and smooth path planning, Applied Soft Computing 32: 568–579.

[9] De Berg, M., Cheong, O., Van Kreveld, M. and Overmars, M. (2008). Computational Geometry: Algorithms and Applications, Springer-Verlag TELOS, Santa Clara, CA.

[10] Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, New York, NY.

[11] Edelsbrunner, H., Guibas, L.J. and Stolfi, J. (1986). Optimal point location in a monotone subdivision, SIAM Journal on Computing 15(2): 317–340.

[12] Ge, S.S. and Cui, Y.J. (2000). New potential functions for mobile robot path planning, IEEE Transactions on Robotics and Automation 16(5): 615–620.

[13] Ghosh, S.K. and Mount, D.M. (1991). An output-sensitive algorithm for computing visibility graphs, SIAM Journal on Computing 20(5): 888–910.

[14] Jafarzadeh, H., Gholami, S. and Bashirzadeh, R. (2014). A new effective algorithm for on-line robot motion planning, Decision Science Letters 3(1): 121–130.

[15] Jafarzadeh, H., Moradinasab, N. and Elyasi, M. (2017). An enhanced genetic algorithm for the generalized traveling salesman problem, Engineering, Technology Applied Science Research 7(6): 2260–2265.

[16] Kala, R. (2014a). Code for robot path planning using probabilistic roadmap, Indian Institute of Information Technology, Allahabad, http://rkala.in/codes.php.

[17] Kala, R. (2014b). Code for robot path planning using rapidly-exploring random trees, Indian Institute of Information Technology, Allahabad, http://rkala.in/codes.php.

[18] Kavraki, L.E., Kolountzakis, M.N. and Latombe, J.-C. (1998). Analysis of probabilistic roadmaps for path planning, IEEE Transactions on Robotics and Automation 14(1): 166–171.

[19] Klaučo, M., Blažek, S. and Kvasnica, M. (2016). An optimal path planning problem for heterogeneous multi-vehicle systems, International Journal of Applied Mathematics and Computer Science 26(2): 297–308, DOI: 10.1515/amcs-2016-0021.

[20] Latombe, J.-C. (2012). Robot Motion Planning, Springer, New York, NY.

[21] LaValle, S.M. (1998). Rapidly-Exploring Random Trees: A New Tool for Path Planning, Iowa State University, Ames, IA.

[22] Liu, J., Yang, J., Liu, H., Tian, X. and Gao, M. (2017). An improved ant colony algorithm for robot path planning, Soft Computing 21(19): 5829–5839.

[23] Lozano-Pérez, T. and Wesley, M.A. (1979). An algorithm for planning collision-free paths among polyhedral obstacles, Communications of the ACM 22(10): 560–570.

[24] Mac, T.T., Copot, C., Tran, D.T. and De Keyser, R. (2016). Heuristic approaches in robot path planning: A survey, Robotics and Autonomous Systems 86: 13–28.

[25] Masehian, E. and Sedighizadeh, D. (2007). Classic and heuristic approaches in robot motion planning—a chronological review, World Academy of Science, Engineering and Technology 23(5): 101–106.

[26] Mohanta, J.C., Parhi, D.R. and Patel, S.K. (2011). Path planning strategy for autonomous mobile robot navigation using Petri-GA optimisation, Computers Electrical Engineering 37(6): 1058–1070.

[27] Ni, J., Wu, L., Shi, P. and Yang, S. X. (2017). A dynamic bioinspired neural network based real-time path planning method for autonomous underwater vehicles, Computational Intelligence and Neuroscience 2017, Article ID: 9269742.

[28] Purcaru, C., Precup, R.-E., Iercan, D., Fedorovici, L.-O. and David, R.-C. (2013). Hybrid PSO-GSA robot path planning algorithm in static environments with danger zones, Proceedings of the 17th International Conference System Theory, Control and Computing (ICSTCC), Sinaia, Romania, pp. 434–439.

[29] Qureshi, A.H. and Ayaz, Y. (2015). Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments, Robotics and Autonomous Systems 68(6): 1–11.

[30] Rohnert, H. (1986). Shortest paths in the plane with convex polygonal obstacles, Information Processing Letters 23(2): 71–76.

[31] Suzuki, Y., Thompson, S. and Kagami, S. (2009). Smooth path planning with pedestrian avoidance for wheeled robots: Implementation and evaluation, 4th International Conference on Autonomous Robots and Agents, ICARA 2009, Wellington, New Zealand, pp. 657–662.

[32] Tang, S., Khaksar, W., Ismail, N. and Ariffin, M. (2012). A review on robot motion planning approaches, Pertanika Journal of Science and Technology 20(1): 15–29.

[33] Urmson, C. and Simmons, R. (2003). Approaches for heuristically biasing RRT growth, Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003), Las Vegas, NV, USA, Vol. 2, pp. 1178–1183.

[34] Welzl, E. (1985). Constructing the visibility graph for n-line segments in O(n2) time, Information Processing Letters 20(4): 167–171.

[35] Zhang, Y., Gong, D.-W. and Zhang, J.-H. (2013). Robot path planning in uncertain environment using multi-objective particle swarm optimization, Neurocomputing 103: 172–185.

[36] Zitzler, E., Laumanns, M. and Thiele, L. (2001). SPEA2: Improving the strength Pareto evolutionary algorithm, Working paper, ETH Zürich, Zürich.