Page 29 - Read Online

Sellers et al. Intell Robot 2022;2(4):333­54 I http://dx.doi.org/10.20517/ir.2022.21 Page 335

Figure 1. Illustration of the proposed model framework.

filling forest method to solve the problem of finding collision-free trajectories while the sequence of waypoints
is formed by multiple trees [29] . However, the aforementioned approaches have not taken into account the
safety of the robot during navigation. In real-world applications, an autonomous vehicle has odometry er-
rors during operation. The safety-aware road model is developed utilizing the Generalized Voronoi diagram
(GVD) approach. Once the safety-aware roads are defined, a particle swarm optimization (PSO) algorithm-
based multi-waypoint path planning algorithm is proposed to visit each waypoint in an explicated sequence
while simultaneously avoiding obstacles. In this paper, the Adjacent Node Selection (ANS) algorithm is devel-
oped to select the closest nodes on the safety-aware roads to generate the final collision-free trajectories with
minimal distance. Furthermore, in our hybrid algorithm, we utilize a histogram-based reactive local navigator
to avoid dynamic and unknown obstacles within the workspace. Through all of these methods, an effective
and efficient safety-aware multiple waypoint navigation model was established, which has been validated by
both simulations and comparison studies.

This paper proposes an Adjacent Node Selection (ANS) algorithm for obtaining an optimal access node into
graph-based maps. To the best of our knowledge, there are no known similar algorithms that improve the
paths created from the waypoint to the graph. The ANS algorithm can be applied to any graph-based mapping
environment, which improves the various graph-based models used for autonomous robotic path planning
systems. In finding an access point into the graph utilizing one of the nodes in the system, the ANS algorithm
conducts point-to-point selection in dense obstacle field of environments to obtain a node to gain access to the
graph that forms a resumable path from a waypoint to the graph. The algorithm’s overall goal is to find a node
in a graph-based map and shorten the overall path length from each waypoint to waypoint, and the waypoint
to the graph.

One can see in Figure 1 the overall framework of our proposed model. Initially, the model is provided with
a global map of its environment and the location of each target waypoint. The GVD utilizes the global map
to construct the safety-aware roads, which are used to guide the robot throughout the environment. The tar-
geted waypoint locations are used as input to the improved PSO (IPSO) algorithm that act as our waypoint
sequencing module, which is utilized to find a near-optimal sequence to visit each waypoint. The ANS algo-
rithm utilizes the output from the previous stages. The ANS algorithm finds the best node for each waypoint
to use as an access point to the graph. If there is no direct path from one waypoint to a node in the graph, the
algorithm conduces point-to-point navigation with nodes within a specified range, which will be explained in
later sections of the paper. Once each waypoint has found its access point, the safety-aware path is constructed,
which is then applied to our path smoothing algorithm. Finally, we utilize a reactive local navigation system to
detect obstacles autonomously and simultaneously build a map of the environment along the generated path.

The main contributions of this paper with this framework of concurrent multi-waypoint navigation and map-
ping with collision avoidance as are summarized as follows: (1) An adjacent node selection (ANS) algorithm is
proposed to build up regional bridges from waypoints to nodes or edges on the graph in multi-waypoint navi-
gation and mapping; (2) a concurrent multi-waypoint navigation and mapping framework of an autonomous
robot is developed by the generalized Voronoi diagram (GVD) and IPSO algorithm as well as a local navigator;