Page 35 - Read Online

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

the PSO. This particle indicates a possible optimal solution to the multi-waypoint navigation issue and moves
to explore an optimal solution in a certain search space. In this paper, a weighted particle is introduced into
a swarm to suggest a more reasonable search direction for all the particles. As a result, the best position of
particle and neighbor guides the particle to move along the corrected direction for better covergence.

The multi-waypoint visiting sequence problem can be used to solve the transportation planning problem and
Covid-19 disinfection robot path planning in hospitals, in which agents (vehicles) need to be delivered as well
as the overall cost and time need to be minimized [14] . The algorithm of the improved PSO to finding multi-
waypoint visiting sequence is explained in Algorithm 1. The objective of the algorithm is to minimize the total
trajectory length of Cartesian coordinates ( , ) of waypoints given.

In the IPSO model the P represents the particle agent, which is denoted by the P : {P , P , N}. N holds
a group of particle agents which are predetermined as neighbors of P . The P are defined by the following
parameters.

(1) Each P requests each neighbor’s current personal best location.
(2) Each P returns its current personal best to neighbors.
(3) Obtains the center location of each surrounding cluster.
(4) Determines if the current position has been visited.
(5) Determines if current position is optimal if not record current position.

Every P obtainsasetofneighborsofpositionsduringtheinitialsetup. Utilizingavarietyoftopologiesonecan
create numerous properties of neighboring particle agents to obtain better performance. Within the proposed
model, we assume that each P has a static set of neighbors. Each P keeps track of its local best solution,
P , which is where a solution closest to the optimal solution is found in the problem space, while the global
best solution is recorded in the parameter P . During each iteration the P evaluates its current position and
determines if it needs to perform a fitness evaluation, while simultaneous checking if the termination criteria
has been met. If the termination criteria have not been met then it updates its P , obtains the neighbor’s P
and calculates the P , and marks the current position as visited.

4.2. Safety­aware IPSO multi­waypoint path planning
To ensure the robot safely reaches the waypoints via the planned visiting sequence, the safety-aware road is
selected to guide the autonomous robot. Nevertheless, there is a problem with the connection path from the
location of the waypoints to safety-aware roads. When we integrate the position information of a waypoint
in the workspace, it may be necessary to obtain the collision-free connection path length from the waypoint
to all nodes, which is computationally expensive. As shown in Figure 6A, with N nodes obtained in the
workspace, there are N possible connection paths from the waypoints to the nodes in the workspace. With
the initial N × N adjacent distance matrix obtained from GVD graph and the increasing M waypoints in the
workspace, the size of new distance matrix is expanded to (N + M) × (N + M). Since most of the connection
path computations are unnecessary, a new adjacent node selection (ANS) algorithm is proposed to reduce the
computational effort by restricting the search space in local regions rather than the entire working region.

The local regions are shown in Figure 6B, and the dark blue nodes, such as and nodes in the regions,
are potential adjacent nodes to connect. The radius R of the local area shall be determined by the potential
workspace, which determines the number of nodes in the search range. For instance, in an area with clustered
obstacles, there are many nodes in the environment; thus, the search radius may be small. However, In an area
with sparse obstacles, there are fewer nodes in the environment; thus, the search radius needs to be larger to
include all potential nodes.

Since the entire workspace is projected through the GVD graph, we can interpret the sparseness of the entire