Page 30 - Read Online

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

Figure 2. Illustration of the ANS algorithm and the safety-aware model by creation of the GVD. (A) Depicts the equidistance property of
the nodes and edges in the GVD model. (B) illustrates how we remove extraneous edge distances, which are small edges within the graph
that reduce the search space or range in the ANS algorithm. (C) illustrates how the removal of those extraneous edges improves the range
and how an access node to the graph can be found.

(3) a GVD method is employed to plan safety-aware trajectories in an obstacle populated environment, while
the sequence of multiple waypoints is created by the IPSO algorithm to minimize the total distance cost; (4)
a sensor-based histogram robot reactive navigator coupled with map building is adopted for moving obstacle
avoidance and local mapping. An improved B-spline curve-based speed modulation module is adopted for
smoother navigation.

The structure of this paper is as follows. Section II presents the safety-aware model that constructs the safety-
conscious roads for robot traversal. Section III describes the proposed adjacent node selection algorithm to
find an access node into the graph-based map. Section IV, the improved PSO-based (IPSO) multi-waypoint
navigation model for waypoint sequencing is explained. Section V illustrates the reactive local navigator for
real-time workspace building and obstacle avoidance. Section VI depicts simulation results and comparative
analyses. Several important properties of the proposed framework are summarized in Section VII.

2. SAFETY-AWARE MODEL
Computational geometry has exceedingly studied the Voronoi diagrams (VD) model, which is an elemental
data structure used as a minimizing diagram of a finite set of continuous functions [28,35] . The minimized
function defines the distantance to an object within the workspace. The VD model decomposes the workspace
into several regions, each consisting of the points near a given object than the others. Let G = { 1 · · · , } be

a set of points of R to each associated with a specific Voronoi region ( ). This can be expressed by the
following equation [36,37] :

( ) = { ∈ R : k − k ≤ k − k, ∀ ≤ } (1)
The intersection of −1 half spaces can be denoted by the region ( ). Each half space holds a point along
with another point of G. The regions ( ) are convex polyhedrons due to the bisectors acting as hyperplanes
between each region. The generalized Voronoi diagram (GVD) is a modified version of the VD model defined
as the set of points Euclidean distance from two obstacles [37] . The workspace is represented as a graph by the
GVD model consisting of nodes, edges, and vertices [28] .

The proposed ANS algorithm utilizes nodes and edges obtained from the GVD illustrated in Figure 2A. The
nodes in the GVD act as junctions to connect waypoints, whereas the edges are used to determine the search
rangeinviewofwaypoints. Solelythenodesinthesearchrangearecalculated, otherthantheentireworkspace,
thus reducing the computational expense. Figure 2B reveals that the range of some edges fails to evaluate
how spare of the workspace is configurated. These edges with short lengths are distractors for evaluating and
computing the search range, thus need to be eliminated shown in Figure 2B. In our ANS algorithm, those