Abstract
This paper proposes an Adaptive Surface Connectivity Path Planning (ASCPP) algorithm to solve the problem of robots and other autonomous navigation systems moving efficiently and safely through complex environments. The ASCPP algorithm addresses the limitations of existing methods by intelligently leveraging the connectivity of obstacle surfaces. The algorithm is designed to handle a wide range of obstacle shapes and applies to both two-dimensional and three-dimensional environments. The paper first proves that in a two-dimensional Euclidean space, if obstacles are surface-connected, the remaining space will remain connected. The authors also provide an algorithm to find an unobstructed path between any two points in the remaining space. Furthermore, the authors prove that even when surface-connected obstacles are attached to the boundary of a finitely connected Euclidean subspace, the remaining space will still be connected as long as the non-adhered parts of the obstacle's surface and other obstacles non-adhered surfaces remain connected. The ASCPP algorithm operates by adaptively connecting the vertices of obstacles to the start and goal positions, generating a graph representation of the environment. This graph representation allows for efficient exploration and path optimization using graph search techniques. The algorithm also takes into account the geometric properties of obstacles, such as convexity and concavity, to improve path selection and avoid potential collisions.
References
[1] Aggarwal, Shubhani, and Neeraj Kumar. "Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges." Computer Communications, 149 (2020): 270-299.
[2] Jiang, Jingchao, and Yongsheng Ma. "Path planning strategies to optimize accuracy, quality, build time and material use in additive manufacturing: a review." Micromachines, 11.7 (2020): 633.
[3] Ait Saadi, Amylia, et al. "UAV path planning using optimization approaches: A survey." Archives of Computational Methods in Engineering, 29.6 (2022): 4233-4284.
[4] Wang, Jiankun, et al. "Neural RRT*: Learning-based optimal path planning." IEEE Transactions on Automation Science and Engineering, 17.4 (2020): 1748-1758.
[5] Schmid, Lukas, et al. "An efficient sampling-based method for online informative path planning in unknown environments." IEEE Robotics and Automation Letters, 5.2 (2020): 1500-1507.
[6] Johnson, David S. "A theoretician's guide to the experimental analysis of algorithms." Data Structures, Near Neighbor Searches, and Methodology, 5 (1999): 215-250.
[7] Huang, Han-Pang, and Shu-Yun Chung. "Dynamic visibility graph for path planning." 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (IEEE Cat. No. 04CH37566). Vol. 3. IEEE, 2004.
[8] Kuffner, James J., and Steven M. LaValle. "RRT-connect: An efficient approach to single-query path planning." Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No. 00CH37065). Vol. 2. IEEE, 2000.
[9] Bohlin, Robert, and Lydia E. Kavraki. "Path planning using lazy PRM." Proceedings 2000 ICRA. Millennium conference. IEEE international conference on robotics and automation. Symposia proceedings (Cat. No. 00CH37065). Vol. 1. IEEE, 2000.
How to cite this paper
Adaptive Surface Connectivity Path Planning Algorithm for Autonomous Navigation
How to cite this paper: Xiangyu Zhou. (2023) Adaptive Surface Connectivity Path Planning Algorithm for Autonomous Navigation. Journal of Applied Mathematics and Computation, 7(3), 377-380.
DOI: http://dx.doi.org/10.26855/jamc.2023.09.007