Page 27 - Read Online

Sellers et al. Intell Robot 2022;2(4):333­54 Intelligence & Robotics
DOI: 10.20517/ir.2022.21

Research Article Open Access

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

2
1
1
1
Timothy Sellers , Tingjun Lei , Chaomin Luo , Gene Eu Jan , Junfeng Ma 3
1 Department of Electrical and Computer Engineering, Mississippi State University, Mississippi State, MS 39759, USA.
2 Department of Electrical Engineering, National Taipei University and Tainan National University of the Arts, Taipei 72045, Taiwan.
3 Department of Industrial and Systems Engineering, Mississippi State University, Mississippi State, MS 39759, USA.
Correspondence to: Prof. Chaomin Luo, Department of Electrical and Computer Engineering, Mississippi State University, 406
Hardy Road, Mississippi State, MS 39762, USA. E-mail: Chaomin.Luo@ece.msstate.edu; ORCID: 0000-0002-7578-3631
Howtocitethis 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(4):333-54. http://dx.doi.org/10.20517/ir.2022.21
Received: 20 Jul 2022 First Decision: 12 Aug 2022 Revised: 18 Aug 2022 Accepted: 25 Aug 2022 Published: 12 Oct 2022

Academic Editor: Simon X. Yang Copy Editor: Jia-Xin Zhang Production Editor: Jia-Xin Zhang

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 robot’s 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.

© The Author(s) 2022. Open Access This article is licensed under a Creative Commons Attribution 4.0
International License (https://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, shar­
ing, 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.

www.intellrobot.com