Page 31 - Read Online

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

edges with the shortest 10% are eliminated, while the rest of the edges are averaged to compute the radius of
the search range. One circumstance is exhibited in Figure 2C, in which some nodes fail to fall into the search
range once the excessively short edges are excluded. The original search space in solid circles and modified
search space in dashed circles based on the ANS algorithm are shown in Figure 2C. As may be seen, after
excessively short edges are effectively eliminated, an appropriate search range is achieved.

GVD nodes form the Euclidean distance between two or more obstacles, while the edges are the junction of
two nodes that depict the distance between each neighboring node to another. Vertices are the connection
points between three or more nodes. Using these features from the GVD model, an obstacle-free path with
our safety-aware model is effectively created. The safety-aware model is constructed by inputting an image and
extracting all significant features from the image, thus allowing the model to construct a map from the input
image. The safety-aware roads are the clearest path between obstacles that occupy the available space in the
map , which can be seen in Figure 2.

In this paper, in order to explain our proposed ANS algorithm, how the nodes are determined and constructed
with the GVD will be presented in some detail. We will introduce some definitions and notations. Lee and
Drysdale [36] derive four basic definitions for determining the optimal placement of edges and nodes within
the GVD graph.

DEFINITION 1. A closed line segment consists of two endpoints and . A straight line is denoted by
( , ), which is also known as an open segment. Elements within the derivation are referred to as points or
←→
segments. The straight line containing is denoted by . The same line directed from to is denoted by
.
®
←→
DEFINITION 2. The projection ( , ) of a point onto a closed segment , is the intersection of and
is perpendicular to and passing through .

DEFINITION 3. The distance between ( , ) is a point and a closed segment in the Euclidean metric
is defined as the distance ( , ( , )) between the point and its projection onto if ( , )) belongs to
and is min ( ( , ), ( , )) otherwise. In other words, ( , ) = min ∈ ( , ). The point of , which
is closest to , is called the image ( , ) of on .

DEFINITION 4. The bisector ( , ) of two elements and is the locus of points equidistant from and
. The bisector ( , ) of two sets of elements and is defined to be the locus of points equidistant from
and , where the distance ( , ) between a point and a set of elements is defined to be min ∈ ( , ).
The bisector ( , ) is said to be oriented if a direction is imposed upon it so that elements and lie to
the left and the right of it, respectively. An oriented bisector ( , ) is defined similarly.

Utilizingthesefourdefinitions, wecaneasilyestablishedgesamongspacesorobstacles, whichusestheequidis-
tant to create an optimal edge that lies directly between the two spaces. As seen in the above definitions, we
can also create edges between irregular-shaped spaces and obstacles.

To characterize the GVD, we expect the robot to be operated at a point within the workspace, a , which is
populated by convex obstacles 1 , ..., . Non-convex obstacles are displayed as the union of convex shapes.
The distance between a point and an obstacle is the minimal distance between the point and all points of the
obstacle. The distance function, and its “gradient” are represented as:

k − 0 k (2)
( ) = 0 ∈