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

Abstract

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 robotos 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 graph-based 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.

Keywords

Adjacent node selection (ANS) algorithm / safety-aware roads / path planning / multiple-waypoint optimization / navigation and mapping