Virtual Mobile Robot-Based Modified for Path Planning and Smoothing of Evacuation Navigation Task in Accessible SAR Environment

2.1 Relate work

A comprehensive survey on path planning for AMRs categorizes methods into reactive computing, soft computing, configuration-space (c-space) search, and optimal control [25]. Path planning for evacuation and general exploration tasks can be divided into two main problems based on the availability of environmental information and the timing of path planning: online and offline path planning [25, 26]. Online path planning addresses exploration tasks without prior environmental data [27], whereas offline path planning occurs with some pre-existing environmental information [28-32].

In scenarios where prior environmental data is available, paths can be generated to avoid static obstacles efficiently [33]. However, these paths are often difficult for non-holonomic mobile robots to follow [34]. Sample-based algorithms from the c-space search category are suitable for high-dimensional path planning. The Probabilistic Road Map (PRM) algorithm, for instance, has been used for path planning in environments with static obstacles [28] and for global path planning with non-linear moving objects [29, 35]. Modifications to PRM have included replacing constant distances between nodes with functions based on several node samples [30].

Each PRM version connects the initial and target positions through several transitional waypoints [36, 37]. The resulting paths often contain sharp angles that need smoothing for non-holonomic mobile robots to follow easily [38]. Previous research on emergency evacuation without robotic assistance has focused on handling static obstacles [31, 39]. Studies involving differential-steering mobile robots in evacuation processes have not thoroughly addressed path planning [32]. This study to develop a path planning-and-smoothing method for supporting search-and-evacuate navigation tasks, it inspired by [31, 32]. Reviews on previous research in offline path planning of mobile robots are summarized in Table 1. Path planning method, path smoothing availability, the objective of the robot task, type of obstacle, and kinematics model of the mobile robot are used as parameters in comparing several works on offline path planning in a structured environment.

Table 1. Reviews of offline path planning

From previous research, no study investigates path planning for solving search-evacuate paths in supporting search-rescue exploration [40]. This study aims to develop a sample-based algorithm to solve search-evacuate routes connecting several victims' locations to the safe exit position. This paper proposes a modified rapidly-explored random tree (RRT) [41] that grows with each victim being found to answer the challenge of planning a search-evacuate path. This paper introduces a virtual non-holonomic mobile robot with an Ackermann-steering kinematics model for smoothing the search-evacuate path to generate a path that is easy to follow by a non-holonomic SAR mobile robot.

2.2 The problem of evacuation navigation tasks in a structured environment

Evacuation involves relocating people from a jeopardized zone to a more secure area in response to an emergency [42]. In most disaster occurrences, a total loss of lives happens because of inappropriate evacuation tasks. Evacuation plays an essential role in saving lives from troubles that could occur [43]. To execute the evacuation task flawlessly, it is necessary to plan the evacuation plan. The evacuation plan generates a sequential waypoint with characteristics in the shortest and safest evacuation path from each victim's location to the secure area [44]. This path should be planned before a disaster happens and must be updated [45, 46]. In this study, the evacuation navigation task consists of locating several victim objects and guiding them to a more stable environment.

Figure 1 illustrates a situation when a mobile robot operates in an indoor structured environment that has several rooms and contains some possible people to be victims. Environment with structured configuration is represented in a cartesian coordinate system $\left\{O_E, X_E, Y_E\right\}$. There are ten possible persons to be victims that spread in several rooms. Each victim and robot are labelled. The arrow of the robot indicates the trajectory that guides it to each victim.

1.jpg

Figure 1. A Search-and-Rescue (SAR) mobile robot and some victims in an indoor structured environment

The robot has to evacuate several victims with spread locations to a specific defined safe target exit position. To save some lives in such an environment with a structured configuration, the robot must be supported by the ability to plan the evacuation path. The path for the guiding robot from the entry point to each victim and the exit point must be calculated to define the shortest and smoothest path to be followed by the SAR robot.

2.3 Path planning and smoothing using a modified rapidly-explored random tree with a partial map

This research proposes a modified rapidly exploring random tree (RRT) based on the virtual non-holonomic mobile robot (VNMR). The design of the proposed method is presented in Figure 2. There are three subsystems in this proposed system, shown in Figure 2. These subsystems are path planning, path following, and virtual plant. The path planning subsystem creates the path connecting the robot's initial position to several victims and the exit point. This path is forced to comprise some sharp turns to connect these points within a short distance. To generate this guide path, this research modifies RRT to plan an entire route from the entry point to several victim positions and the exit location.

The next two subsystems are used for path smoothing. These subsystems involve path following and the kinematics model of the plant [47, 48]. The idea is to use a virtual non-holonomic mobile robot to follow the guidance path that still comprises the sharp turns. Path following function is implemented by using the Pure Pursuit algorithm. This method is applied to a selected virtual non-holonomic mobile robot kinematics model. Ackermann-steering [49] is chosen as the virtual non-holonomic mobile robot to transport heavy medical equipment in the real world [50].

This study improved the original RRT to have the ability to generate a path that interconnects some victim's positions from an entry point and to an exit point. The robot workspace based on the map of structured $\mathrm{I}_{x, y}$ is simplified through a partial map subsystem that utilizes the initial robot position $\left[x_i(k) \quad y_i(k)\right]^T$ and victim locations $\mathrm{L}_v(k)$. The partial map subsystem will divide the original structured map into several simpler map segments based on victim positions $\mathrm{L}_v(k)$. This is aimed at reducing the complexity of the RRT mapping, in order to enhancing the efficiency of RRT processing time. The map from partial results is subsequently utilized for executing path planning using a modified RRT. This early generated path of modified RRT still contained sharp turn $\left[\begin{array}{ll}x_{s t}(k) & y_{s t}(k)\end{array}\right]^T$ in each connected guided position. This sequence of positions that have a function to guide the robot is known as waypoints. The waypoints were used in Pure Pursuit of the following subsystem to generate linear and steering velocity commands $\left[\begin{array}{ll}v_{v n m r}(k) & \dot{\psi}_{v n m r}(k)\end{array}\right]^T$ to be executed by the virtual non-holonomic mobile robot. As a result of following the modified RRT path, this virtual robot left the trajectory $\left[\begin{array}{ll}x_{r e f}(k) & y_{r e f}(k)\end{array}\right]^T$ that forms the smooth path. This path was used for the real SAR mobile robot to guide evacuation navigation tasks in an accessible SAR environment.

2.jpg

Figure 2. The proposed path planning-smoothing based on a virtual non-holonomic mobile robot and partial map

2.4 Modified rapidly-explored random tree-based path planning

This research contributes by modifying RRT to construct the interconnection path to link some victim locations to entry/exit points with the shortest distance and no collision with static obstacles. The generated evacuation path results with respect to the objective function as follows:

$f(G)=g\left(P_e, P_v^1\right)+\sum_{i=2}^n g\left(P_v^{i-1}, P_v^i\right)$                   (1)

where, objective function $f(G)$ minimizes the sum of gap distance $g()$ between entry/exit point $\mathrm{P}_e$ and some number of victim position $\mathrm{P}_v^i$. The total gap distance of the complete path of the modified RRT from entry/exit point $\mathrm{P}_e$ to several victim positions $\mathrm{P}_v^i$ is depicted in Figure 3. In this illustration, there are four victims with arbitrary positions that were known to the robot before the evacuation path planning based on modified RRT is executed. This study differs from previous research in considering several targets represented as victims. Based on this illustration, four gap distances exist between four pairs of initial target points. The gap distance of each pair $g\left(\mathrm{P}_v^{i-1}, \mathrm{P}_v^i\right)$ is computed by using Euclidean distance regarding the following objective function:

$f(g)=\sum_{j=1}^m E\left(\mathrm{p}_v^{j-1}, \mathrm{p}_v^j\right)$               (2)

where, objective function $f(g)$ minimizes the path between interval point $\mathrm{p}_v^j$, each pair of initial-target positions is connected by a path consisting of some arbitrary interval points $\mathrm{p}_v^j$, as illustrated in Figure 4.

3.jpg

Figure 3. Objective function implementations of modified rapidly-explored random tree (RRT) for evacuation path planning with four victims

4.jpg

Figure 4. The first pair of initial target points in the enlarged view

2.5 Pure pursuit-based path following

To smooth the generated RRT path that still contains sharp turns $\left[x_{s t}(k) \quad y_{s t}(k)\right]^T$, this study proposes using a virtual non-holonomic mobile robot to follow the path using a pure pursuit path with the following algorithm. Some parameters must be defined before the pure pursuit algorithm processes the sharp turns-contained RRT path. Three parameters of the pure pursuit algorithm are the distance of the look-ahead, the preferred linear velocity, and the highest angular velocity. The results of the pure pursuit algorithm are linear and angular velocities $\left[v_{v n m r}(k) \quad \dot{\psi}_{v n m r}(k)\right]^T$. These velocities are used to reach the forward point based on the virtual non-holonomic mobile robot's location and orientation.

2.6 Virtual non-holonomic mobile robot

Using its kinematics model, the path-following algorithm guides the virtual non-holonomic mobile robot to move from the entry/exit point to each victim's location [51]. The Ackermann-steering mobile robot kinematics model is proposed in this study to navigate the evacuation task of several victims in an indoor, unstructured environment [52]. The kinematics configuration of the virtual Ackermann-steering mobile robot in the Cartesian coordinate system [53] is illustrated in Figure 5. The indoor structured environment is represented by an environment frame and symbolized with $\left\{O_E, X_E, Y_E\right\}$. The virtual non-holonomic mobile robot is depicted using the Ackermann-steering body frame [54] and denoted with $\left\{O_R, X_R, Y_R\right\}$.

5.jpg

Figure 5. The configuration of Ackermann-steering

The origin of the robot frame $O_R$ coincides with the middle of the rear wheel axis and overlaps with the center of mass $G$. The origin position of the robot frame relative to the environment frame describes the coordinate of the robot $\left[\begin{array}{ll}x_R & y_R\end{array}\right]^T$. The length of the wheelbase is represented by $l_R$. The virtual non-holonomic mobile robot moves with linear and steering wheel velocity $\left[v_R(k) \quad \omega_R(k)\right]^T$. The orientation and the steering angle of the virtual non-holonomic mobile robot are represented by $\phi_R$ and $\psi_R$, respectively.

The steering angle $\psi_R$ is used to turn its body with respect to the instantaneous center of rotation (ICR) [55]. The pose and its first derivatives of the virtual non-holonomic mobile robot are respectively expressed as follows:

$\mathrm{P}_R=\left[\begin{array}{llll}x_R & y_R & \phi_R & \psi_R\end{array}\right]^T$,                (3)

$\dot{\mathrm{P}_R}=\left[\begin{array}{llll}\dot{x}_R & \dot{y}_R & \dot{\phi}_R & \dot{\psi}_R\end{array}\right]^T$                    (4)

The rear-wheel driving Ackermann-steering [56] as the virtual non-holonomic mobile robot has a kinematics model as follows:

$\left[\begin{array}{c}\dot{x}_R \\ \dot{y}_R \\ \dot{\phi}_R \\ \dot{\psi}_R\end{array}\right]=\left[\begin{array}{cc}\cos \phi_R & 0 \\ \sin \phi_R & 0 \\ \tan \psi_R / l_R & 0 \\ 0 & 1\end{array}\right]\left[\begin{array}{c}v_R \\ \omega_R\end{array}\right]$                 (5)

The next robot poses is $\mathrm{P}_R(k+1)$ determined by using the current pose $\mathrm{P}_R(k)$ and the velocities $\left[v_R(k) \quad \omega_R(k)\right]^T$ such as described as follows:

$\left[\begin{array}{l}x_R(k+1) \\ y_R(k+1) \\ \phi_R(k+1) \\ \psi_R(k+1)\end{array}\right]=\left[\begin{array}{l}x_R(k) \\ y_R(k) \\ \phi_R(k) \\ \psi_R(k)\end{array}\right]+k T\left[\begin{array}{c}v_R(k) \cos \phi_R \\ v_R(k) \sin \phi_{\quad R} \\ v_R(k) \tan \psi_R / l_R \\ \omega_R(k)\end{array}\right]$                   (6)

2.7 Algorithm description, convergence analysis, and complexity

This process begins with the input structured environmental map data and known victim positions, then simplifying the map using a partial map strategy. This simplification aims to limit the search space so that path planning can be carried out more efficiently. Subsequently, a modified RRT algorithm as described in Section 2.6 is employed as global path planning by generating collision-free paths connecting the robot's entry point, victim locations, and the exit point. One of the characteristics of RRT is that the resulting global planning path still contains sharp turns, so it is smoothed using the Pure Pursuit algorithm implemented on a virtual non-holonomic robot. This process produces a smoother and kinematically feasible path, which is then used as the reference trajectory for victim evacuation.

In terms of convergence, the proposed method inherits the probabilistic completeness property of the RRT algorithm. With an increasing number of samples, the probability of finding a collision-free evacuation path will also increase. The modifications made in this study do not change the basic convergence property because they focus on the construction of the evacuation path.

Regarding computational complexity, the main computational load comes from the global path planning stage using RRT. The overall complexity is dominated by the sampling and tree expansion processes, while the path smoothing process using the Pure Pursuit algorithm only adds linear computational load. Therefore, this computational process does not have a significant effect on the overall complexity of the method.

Based on several simulations using the modified RRT algorithm on partial map and PRM algorithm, as in Figure 8 to Figure 15 for RRT and Figure 17 to Figure 24 for PRM. Based on this comparison, it can be seen that in carrying out the navigation task of some victim’s evacuation in a structured room, the modified RRT algorithm on partial map shows better performance compared to the PRM algorithm. It can be validated in Figure 16 for RRT and Figure 24 for PRM, with the results that the movement in Figure 16 looks smooth and does not experience collisions with static obstacles during victim evacuation in a structured room. On the other hand, in Figure 24 it can be seen that the movement of the mobile robot with the PRM algorithm often touches obstacles, which can affect the performance of the mobile robot. These results show that the modified RRT algorithm provides advantages in the context of casualty evacuation, with more efficient and safe movement in structured spaces. This validation is supported by the visualization of simulation results in Figure 16 and Figure 24. Although the proposed method has been validated through simulations, further validation on real robotic platforms and standardised benchmark environments will be considered for future work to strengthen its applicability in real-world SAR scenarios. Quantitative evaluation confirms that the proposed modified RRT outperforms the PRM approach for evacuation navigation tasks. Compared to PRM, the proposed method reduced path length by 22.1%, decreased curvature variation by 63.1%, shortened computation time by 25.7%, and completely eliminated obstacle collisions.

Future work will include quantitative comparison with other RRT variants and optimization-based smoothing methods to further validate the generality of the proposed approach.