Path Planning for Indoor UAV Using A* and Late Acceptance Hill Climbing Algorithms Utilizing Probabilistic Roadmap

  • Authors

    • Jacob Hopkins
    • Forrest Joy
    • Alaa Sheta Texas A&M University-corpus Christi, TX, USA
    • Hamza Turabieh
    • Dulal Kar
    2020-10-23
    https://doi.org/10.14419/ijet.v9i4.31033
  • UAV, Probabilistic Road Mapping, A*, Late Acceptance Hill-Climbing.

  • Abstract

    The main objective of an unmanned aerial vehicle (UAV) path planning is to generate a flight path that links a start point to an endpoint in an indoor space avoiding obstacles.  Path planning is essential for many real-life applications such as an autonomous car, surveillance mission, farming robots, unmanned aerial vehicles package delivery, space exploration, and many others. To create an optimal path, we need to adopt a specific criterion to minimize the distance the UAV must travel such as the Euclidean distance. In this paper, we provide our initial idea of creating an optimal path for indoor UAV using both A* and the Late Acceptance Hill Climbing (LAHC) algorithms. We are adopting an indoor search environment with various complexity and utilize the Probabilistic Roadmap algorithm (PRM) as a search space for both algorithms. The basic idea following PRM is to generate random sample points in the space and search these points for an optimal path. The developed results show that the LAHC algorithm outperforms the A* algorithm.

  • References

      1. T. Goetzendorf-Grabowski and M. Rodzewicz, “Design of UAV for photogrammetric mission in antarctic area,†Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, vol. 231, no. 9, pp. 1660–1675, 2017.
      2. J. Kim, S. Kim, C. Ju, and H. I. Son, “Unmanned aerial vehicles in agriculture: A review of perspective of platform, control, and applications,†IEEE Access, vol. 7, pp. 105 100–105 115, 2019.
      3. P. Radoglou-Grammatikis, P. Sarigiannidis, T. Lagkas, and I. Moscholios, “A compilation of UAV applications for precision agriculture,†Computer Networks, vol. 172, p. 107148, 2020.
      4. H. T. Berie and I. Burud, “Application of unmanned aerial vehicles in earth resources monitoring: focus on evaluating potentials for forest monitoring in ethiopia,†European Journal of Remote Sensing, vol. 51, no. 1, pp. 326–335, 2018.
      5. R. Koslowski and M. Schulzke, “Drones along borders: Border security uavs in the united states and the european union,†International Studies Perspectives, vol. 19, July 2017.
      6. G. Sylvester, G. Rambaldi, D. Guerin, A. Wisniewski, N. Khan, J. Veale, and M. Xiao, “E-agriculture in action: drones for agriculture. food and agriculture organization of the united nations and international telecommunication union, bangkok, thailand,†Bangkok: Food and Agriculture Organization of the United Nations and International Telecommunication Union. Retrieved July, vol. 19, p. 2018, 2018.
      7. Ruijie He, S. Prentice, and N. Roy, “Planning in information space for a quadrotor helicopter in a gps-denied environment,†in 2008 IEEE International Conference on Robotics and Automation, 2008, pp. 1814–1820.
      8. C. Huang, Y. Lan, Y. Liu, W. Zhou, H. Pei, L. Yang, Y. Cheng, Y. Hao, and Y. Peng, “A new dynamic path planning approach for unmanned aerial vehicles,†Complexity, vol. 2018, pp. 1–17, November 2018.
      9. D. R. Maddi, A. Sheta, A. Mahdy, and H. Turabieh, “Multiple waypoint mobile robot path planning using neighborhood search genetic algorithms,†in Proceedings of the 2019 International Conference on Artificial Intelligence, Robotics and Control, ser. AIRC ’19. New York, NY, USA: Association for Computing Machinery, 2019, p. 14–22.

      10. R. M. Santiago, A. L. De Ocampo, A. Ubando, A. Bandala, and E. Dadios, “Path planning for mobile robots using genetic algorithm and probabilistic roadmap,†December 2017, pp. 1–5.

      11. Y. Chen, F. Su, and L.-C. Shen, “Improved ant colony algorithm based on PRM for uav route planning,†vol. 21, pp. 1658–1666, March 2009.

      1. 12. D. Zhao and J. Yi, “Robot planning with artificial potential field guided ant colony optimization algorithm,†in Advances in Natural Computation, L. Jiao, L.Wang, X. Gao, J. Liu, and F. Wu, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 222–231.

      13. E. Krell, A. Sheta, A. P. R. Balasubramanian, and S. A. King, “Collision-free autonomous robot navigation in unknown environments utilizing PSO for path planning,†Journal of Artificial Intelligence and Soft Computing Research, vol. 9, no. 4, pp. 267 – 282, 01 Oct. 2019.

      14. L. Kavraki, P. Svestka, J. Latombe, and M. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,†Robotics and Automation, IEEE Transactions on, vol. 12, pp. 566–580, September 1996.

      15. M. Xue, “Optimal path selection of vehicle route scheduling under bad weather factors,†Computer Simulation, vol. 32, no. 2, pp. 210–212, 2015.

      16. R. Sotnezov, “Genetic algorithms for problems of logical data analysis in discrete optimization and image recognition,†Pattern Recognition and Image Analysis, vol. 19, no. 3, pp. 469–477, 2009.

      17. B. Yan, T. Chen, X. Zhu, Y. Yue, B. Xu, and K. Shi, “A comprehensive survey and analysis on path planning algorithms and heuristic functions,†in Science and Information Conference. Springer, 2020, pp. 581–598.

      18. W. Qiuping, S. Rong, and Z. Qi, “Optimal path selection of slow traffic based on GIS network analysis,†Journal of Xi’an University of Architecture & Technology, vol. 45, no. 5, pp. 668–674, 2013.

      19. T. T. Mac, C. Copot, D. T. Tran, and R. De Keyser, “Heuristic approaches in robot path planning: A survey,†Robotics and Autonomous Systems, vol. 86, pp. 13–28, 2016.

      20. F. Duchon, A. Babinec, M. Kajan, P. Beno, M. Florek, T. Fico, and L. Jurišica, “Path planning with modified a star algorithm for a mobile robot,†Procedia Engineering, vol. 96, pp. 59–69, 2014.

      21. S. Behnke, “Local multiresolution path planning,†in Robot Soccer World Cup. Springer, 2003, pp. 332–343.

      22. C. M. Dellin and S. S. Srinivasa, “A unifying formalism for shortest path problems with expensive edge evaluations via lazy best-first search over paths with edge selectors,†ser. ICAPS’16. AAAI Press, 2016, p. 459–467.

      23. Q. Zhu, Y. Yan, and Z. Xing, “Robot path planning based on artificial potential field approach with simulated annealing,†in Sixth International Conference on Intelligent Systems Design and Applications, vol. 2. IEEE, 2006, pp. 622–627.

      24. W. Khaksar, T. S. Hong, M. Khaksar, and O. R. E. Motlagh, “Sampling-based Tabu search approach for online path planning,†Advanced Robotics, vol. 26, no. 8-9, pp. 1013–1034, 2012.

      25. E. Akar, H. R. Topcuoglu, and M. Ermis, “Hyper-heuristics for online UAV path planning under imperfect information,†in European Conference on the Applications of Evolutionary Computation. Springer, 2014, pp. 741–752.

      26. U. F. Siddiqi, Y. Shiraishi, and S. M. Sait, “Multi-objective optimal path selection in electric vehicles,†Artificial Life and Robotics, vol. 17, no. 1, pp. 113–122, 2012.

      27. J. E. Doran and D. Michie, “Experiments with the graph traverser program,†in Proceedings of the Royal Society of London, Series A. Mathematical and Physical Sciences, vol. 294, no. 1437, September 1966.

      28. N. J. Nilsson, The Quest for Artificial Intelligence. Cambridge University Press, 2009.

      29. P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,†SIGART Bull., no. 37, pp. 28–29, Dec. 1972.

      30. M. Korkmaz and A. Durdu, “Comparison of optimal path planning algorithms,†in 2018 14th International Conference on Advanced Trends in Radioelecrtronics, Telecommunications and Computer Engineering (TCSET), February 2018, pp. 255–258.

      31. V. Kunchev, L. Jain, V. Ivancevic, and A. Finn, “Path planning and obstacle avoidance for autonomous mobile robots: A review,†in Knowledge-Based Intelligent Information and Engineering Systems, B. Gabrys, R. J. Howlett, and L. C. Jain, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 537–544.

      32. O. Hachour, “Path planning of autonomous mobile robot,†International journal of systems applications, engineering & development, vol. 2, no. 4, pp. 178–190, 2008.

      33. M. Radovnikovich, K. C. Cheok, and P. Vempaty, “Comparison of optimal path planning algorithms for an autonomous mobile robot,†in 2011 IEEE Conference on Technologies for Practical Robot Applications, April 2011, pp. 35–39.

      34. P. Raja and S. Pugazhenthi, “Optimal path planning of mobile robots: A review,†International Journal of Physical Sciences, vol. 7, no. 9, pp. 1314 – 1320, 2012.

      35. F. Duchon, D. Hunady, M. Dekan, and A. Babinec, “Optimal navigation for mobile robot in known environment,†in Robotics in Theory and Practice, ser. Applied Mechanics and Materials, vol. 282. Trans Tech Publications Ltd, March 2013, pp. 33–38.

      36. A. Hussein, H. Mostafa, M. Badrel-din, O. Sultan, and A. Khamis, “Metaheuristic optimization approach to mobile robot path planning,†in 2012 International Conference on Engineering and Technology (ICET), October 2012, pp. 1–6.

      37. A. Ismail, A. Sheta, and M. Al-Weshah, “A mobile robot path planning using genetic algorithm in static environment,†Journal of Computer Science, vol. 4, no. 4, pp. 341–344, 2008.

      38. S. C. Yun, V. Ganapathy, and L. O. Chong, “Improved genetic algorithms based optimum path planning for mobile robot,†in 2010 11th International Conference on Control Automation Robotics Vision, Dec 2010, pp. 1565–1570.

      39. R. M. C. Santiago, A. L. D. Ocampo, A. T. Ubando, A. A. Bandala, and E. P. Dadios, “Path planning for mobile robots using genetic algorithm and probabilistic roadmap,†in 2017 IEEE 9th International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment and Management (HNICEM), Dec 2017, pp. 1–5.

      40. M. Wu, E. Chen, Q. Shi, L. Zhou, Z. Chen, and M. Li, “Path planning of mobile robot based on improved genetic algorithm,†in 2017 Chinese Automation Congress (CAC), Oct 2017, pp. 6696–6700.

      41. Y. Liang, F. Hong, Q. Lin, S. Bi, and L. Feng, “Optimization of robot path planning parameters based on genetic algorithm,†in 2017 IEEE International Conference on Real-time Computing and Robotics (RCAR), July 2017, pp. 529–534.

      42. J. Chen, F. Ye, and T. Jiang, “Path planning under obstacle avoidance constraints based on ant colony optimization algorithm,†in 2017 IEEE 17th International Conference on Communication Technology (ICCT), October 2017, pp. 1434–1438.

      43. N. Alpkiray, Y. Torun, and O. Kaynar, “Probabilistic roadmap and artificial bee colony algorithm cooperation for path planning,†in 2018 International Conference on Artificial Intelligence and Data Processing (IDAP), Sep. 2018, pp. 1–6.

      44. D.-W. Gong, J.-H. Zhang, and Y. Zhang, “Multi-objective particle swarm optimization for robot path planning in environment with danger sources,†JCP, vol. 6, pp. 1554–1561, August 2011.

      45. R. Grandi, “Coordination and control of autonomous mobile robot swarms by using particle swarm optimization algorithm and consensus theory,†Master’s thesis, Alma Mater Studiorum - Universita di Bologna, May 2013.

      46. M. S. Alam, M. U. Rafique, and M. U. Khan, “Mobile robot path planning in static environments using particle swarm optimization,†International journal of computer science and electronics engineering (IJCSEE), vol. 3, pp. 253–257, 2015.

      47. P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,†IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, July 1968.

      48. E. K. Burke and Y. Bykov, “The late acceptance hill-climbing heuristic,†European Journal of Operational Research, vol. 258, no. 1, pp. 70 – 78, 2017.

      49. A. Goerler, F. Schulte, and S. Voß, “An application of late acceptance hill-climbing to the traveling purchaser problem,†in Computational Logistics. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013, pp. 173–183.

  • Downloads

  • How to Cite

    Hopkins, J., Joy, F., Sheta, A., Turabieh, H., & Kar, D. (2020). Path Planning for Indoor UAV Using A* and Late Acceptance Hill Climbing Algorithms Utilizing Probabilistic Roadmap. International Journal of Engineering & Technology, 9(4), 857-862. https://doi.org/10.14419/ijet.v9i4.31033

    Received date: 2020-07-23

    Accepted date: 2020-09-04

    Published date: 2020-10-23