1. bookVolume 28 (2018): Issue 3 (September 2018)
Journal Details
License
Format
Journal
eISSN
2083-8492
First Published
05 Apr 2007
Publication timeframe
4 times per year
Languages
English
access type Open Access

An Exact Geometry–Based Algorithm for Path Planning

Published Online: 03 Oct 2018
Volume & Issue: Volume 28 (2018) - Issue 3 (September 2018)
Page range: 493 - 504
Received: 12 Jul 2017
Accepted: 09 Apr 2018
Journal Details
License
Format
Journal
eISSN
2083-8492
First Published
05 Apr 2007
Publication timeframe
4 times per year
Languages
English
Abstract

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(nnr2) 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.

Keywords

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.10.1007/s00170-016-9074-6Search in Google Scholar

Asano, T., Asano, T., Guibas, L., Hershberger, J. and Imai, H. (1986). Visibility of disjoint polygons, Algorithmica 1(1): 49-63.10.1007/BF01840436Search in Google Scholar

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.Search in Google Scholar

Choset, H.M. (2005). Principles of Robot Motion: Theory, Algorithms, and Implementation, MIT Press, Cambridge, MA.Search in Google Scholar

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.10.1109/TEVC.2004.826067Search in Google Scholar

Coello, C.C., Lamont, G.B. and Van Veldhuizen, D.A. (2007). Evolutionary Algorithms for Solving Multi- Objective Problems, Springer, New York, NY.Search in Google Scholar

Cormen, T.H. (2001). Introduction to Algorithms, MIT Press, Cambridge, MA, pp. 595-601.Search in Google Scholar

Davoodi,M., Panahi, F., Mohades, A. and Hashemi, S.N. (2015). Clear and smooth path planning, Applied Soft Computing 32: 568-579.10.1016/j.asoc.2015.04.017Search in Google Scholar

De Berg, M., Cheong, O., Van Kreveld, M. and Overmars, M. (2008). Computational Geometry: Algorithms and Applications, Springer-Verlag TELOS, Santa Clara, CA.10.1007/978-3-540-77974-2Search in Google Scholar

Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms, Wiley, New York, NY.Search in Google Scholar

Edelsbrunner, H., Guibas, L.J. and Stolfi, J. (1986). Optimal point location in a monotone subdivision, SIAM Journal on Computing 15(2): 317-340.10.1137/0215023Search in Google Scholar

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.10.1109/70.880813Search in Google Scholar

Ghosh, S.K. and Mount, D.M. (1991). An output-sensitive algorithm for computing visibility graphs, SIAM Journal on Computing 20(5): 888-910.10.1137/0220055Search in Google Scholar

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.10.5267/j.dsl.2013.07.004Search in Google Scholar

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.10.48084/etasr.1570Search in Google Scholar

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

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

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.10.1109/70.660866Search in Google Scholar

Klaučo, M., Blaˇzek, 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.10.1515/amcs-2016-0021Open DOISearch in Google Scholar

Latombe, J.-C. (2012). Robot Motion Planning, Springer, New York, NY.Search in Google Scholar

LaValle, S.M. (1998). Rapidly-Exploring Random Trees: A New Tool for Path Planning, Iowa State University, Ames, IA.Search in Google Scholar

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.10.1007/s00500-016-2161-7Search in Google Scholar

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.10.1145/359156.359164Search in Google Scholar

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.10.1016/j.robot.2016.08.001Search in Google Scholar

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.Search in Google Scholar

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.10.1016/j.compeleceng.2011.07.007Search in Google Scholar

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.10.1155/2017/9269742Search in Google Scholar

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.Search in Google Scholar

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.10.1016/j.robot.2015.02.007Search in Google Scholar

Rohnert, H. (1986). Shortest paths in the plane with convex polygonal obstacles, Information Processing Letters 23(2): 71-76.10.1016/0020-0190(86)90045-1Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

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.Search in Google Scholar

Welzl, E. (1985). Constructing the visibility graph for n-line segments in O(n2) time, Information Processing Letters 20(4): 167-171.10.1016/0020-0190(85)90044-4Search in Google Scholar

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.10.1016/j.neucom.2012.09.019Search in Google Scholar

Zitzler, E., Laumanns, M. and Thiele, L. (2001). SPEA2: Improving the strength Pareto evolutionary algorithm, Working paper, ETH Z¨urich, Z¨urich.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo