Hot Keywords

Intell Robot 2022;2:[Accepted].10.20517/ir.2022.21© The Author(s) 2022
Accepted Manuscript
Open AccessResearch Article

A node selection algorithm to graph-based multi-waypoint optimization navigation and mapping 

Correspondence Address: Prof. Chaomin Luo, Department of Electrical and Computer Engineering, Mississippi State University, 406 Hardy Road, Mississippi State, MS 39762, USA. E-mail:


© The Author(s) 2022. Open Access This article is licensed under a Creative Commons Attribution 4.0 International License (, which permits unrestricted use, sharing, adaptation, distribution and reproduction in any medium or format, for any purpose, even commercially, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.


Autonomous robot multi-waypoint navigation and mapping have been demanded in many real-world applications found in search and rescue (SAR), environmental exploration, and disaster response. Many solutions to this issue have been discovered via graph-based methods in need of switching the robots trajectory between the nodes and edges within the graph to create a trajectory for waypoint-to-waypoint navigation. However, studies of how waypoints are locally bridged to nodes or edges on the graphs have not been adequately undertaken. In this paper, an adjacent node selection (ANS) algorithm is developed to implement such a protocol to build up regional path from waypoints to nearest nodes or edges on the graph. We propose this node selection algorithm along with the generalized Voronoi diagram (GVD) and Improved Particle Swarm Optimization (IPSO) algorithm as well as a local navigator to solve the safety-aware concurrent graphbased multi-waypoint navigation and mapping problem. Firstly, GVD is used to form a Voronoi diagram in an obstacle populated environment to construct safety-aware routes. Secondly, the sequence of multiple waypoints is created by the IPSO algorithm to minimize the total travelling cost. Thirdly, while the robot attempts to visit multiple waypoints, it traverses along the edges of the GVD to plan a collision-free trajectory. The regional path from waypoints to the nearest nodes or edges needs to be created to join the trajectory by the proposed ANS algorithm. Finally, a sensor-based histogram local reactive navigator is adopted for moving obstacle avoidance while local maps are constructed as the robot moves. An improved B-spline curve-based smooth scheme is adopted that further refines the trajectory and enables the robot to be navigated smoothly. Simulation and comparison studies validate the effectiveness and robustness of the proposed model. 

Cite This Article

Sellers T, Lei T, Luo C, Jan GE, Ma J. A node selection algorithm to graph-based multi-waypoint optimization navigation and mapping. Intell Robot 2022;2:[Accept].

Article Access Statistics

  • Viewed: 22
  • Downloaded: 3
  • Cited: Crossref0

Share This Article

See Updates

© 2016-2022 OAE Publishing Inc., except certain content provided by third parties