A novel directional sampling-based path planning algorithm for ambient intelligence navigation scheme in autonomous mobile robots

Abstract

Path planning algorithms determine the performance of the ambient intelligence navigation schemes in autonomous mobile robots. Sampling-based path planning algorithms are widely employed in autonomous mobile robot applications. RRT*, or Optimal Rapidly Exploring Random Trees, is a very effective sampling-based path planning algorithm. However, the RRT* solution converges slowly. This study proposes a directional random sampling-based RRT* path planning algorithm known as DR-RRT* to address the slow convergence issue. The novelty of the proposed method is that it reduces the search space by combining directional non-uniform sampling with uniform sampling. It employs a random selection approach to combine the non-uniform directional sampling method with uniform sampling. The proposed path planning algorithm is validated in three different environments with a map size of 384*384, and its performance is compared to two existing algorithms: RRT* and Informed RRT*. Validation is carried out utilizing a TurtleBot3 robot with the Gazebo Simulator and the Robotics Operating System (ROS) Melodic. The proposed DR-RRT* path planning algorithm is better than both RRT* and Informed RRT* in four performance measures: the number of nodes visited, the length of the path, the amount of time it takes, and the rate at which the path converges. The proposed DR-RRT* global path planning algorithm achieves a success rate of 100% in all three environments, and it is suited for use in all kinds of environments.

Keywords

Ambient intelligence navigation scheme directional sampling path planning algorithms rapidly exploring random trees autonomous mobile robot

1. Introduction

Autonomous mobile robots (AMR) are employed in a wide variety of applications, including agricultural [10], hazardous situations [34], medical [30], industrial automation [2], home automation [27,36], route guidance [1] and emergency management applications [5]. Recently, mobile robotics have been utilized to monitor patients’ fevers, disinfect floors with UV light, and transport medications and food to patients in hospitals during the coronavirus 2019 (COVID-19) pandemic to prevent disease spread [37]. These applications can be carried out with the assistance of these autonomous mobile robots, which are rising in popularity. Path planning is critical in AMR because it enables the robot to identify obstacles and follow the collision-free path from its starting place to its destination via a specified number of intermediate points [3]. Autonomous mobile robot path planning based on sampling techniques is the most significant improvement in the path planning segment [11]. The primary advantages of these algorithms are their low computational cost, their applicability to high-dimensional problems, and their increased success rate for advanced problems [23]. These algorithms are probabilistic complete, which indicates that they will find an answer if one exists given an unlimited run time. If there is enough time, these algorithms’ probabilistic completeness properties will eventually find a solution. The Probabilistic Roadmap (PRM) and the Rapidly Exploring Random Tree (RRT) are two of the most popular sampling-based path planning techniques. In this PRM [14], a roadmap is built by repeatedly sampling the configuration space (also known as C-space). The free-space samples are saved, but the obstacle-space samples are deleted from the roadmap. Since PRM and its variants are multi-query methods, they are incompatible with real-time applications that require preprocessing to develop a roadmap. For single-query concerns, RRT is faster than PRM [28]. RRT is a tree-type method that constructs a tree from the initial configuration to the final configuration [17]. It picks a random configuration from the C-space and tries to connect to the nearest vertex in the tree if it is in the free space. However, the solution provided by RRT is suboptimal. Asymptotically optimum solutions are found using RRT*, an RRT extension [13]. The major limitation of the RRT* algorithm is the slow convergence problem. Because of its popularity, there have been a lot of RRT * algorithms made to solve RRT *’s slow convergence problem and they are compiled in the review papers with their relevant applications [4,6,25,26]. Despite various extensions in RRT*, due to uniform sampling of the entire configuration space [20], the RRT* path planning algorithm suffers from slower convergence [21]. There are two ways to improve the slow convergence problem of the RRT* path planning algorithms: changing the sampling procedure [15] and improving the initial path [12,33]. Sampling-based path planning algorithms depend on a well-designed sampling technique, modification of the sampling procedure is considered in the research work out of these two methodologies. Sampling procedures in RRT* play an important role in exploring the search space. Uniform and non-uniform sampling or informed sampling, are two different kinds of sampling. RRT*’s convergence is improved by reducing the search space by using a non-uniform sampling approach. Non-uniform sampling is distinguished from uniform sampling by the fact that some points in the search space are given greater weight and have a larger likelihood of being sampled than others. The study of the impacts of non-uniform sampling in RRT* in comparison to uniform samples is a recent topic [22]. Investigation of non-uniform sampling in RRT* is reviewed by Veras, Medeiros and Guimaraes [31]. In general, two distinct strategies are used to accomplish the non-uniform sampling process in RRT*. The first strategy of the uniform sampling technique is referred to as biased sampling, in which RRT* expansion is skewed regionally to acquire samples in and surrounding regions of interest. Adaptive sampling is the second strategy that limits the RRT* search space during the sampling phase. A non-uniform distribution biases the sampling process in RRT* and decreases the number of samples necessary to find a path. These techniques can be used individually or in combination with uniform sampling. However, non-uniform sampling is frequently used in combination with a uniform sample to ensure success.

2. Related work

In standard RRT*, uniform random sampling is used to generate a tree. One option to improve the sampling technique in RRT* is to introduce bias [19]. For quick convergence, a P-RRT* based on an artificial potential function [24] is proposed. It employs a random gradient descent heuristic in which the sampling process is driven by an Artificial Potential Field (APF). The Artificial Potential Field (APF)-based methods that are used to bias the RRT* exploration use information about the links between the goal and the obstacle. Between the new sample and the goal, an attractive force converges the solution more quickly than the RRT* sampling process. Then, to further improve sampling efficiency, the artificial potential function-based RRT* is extended bidirectional operation, which is referred to as PB-RRT* [29]. Later on, BPIB-RRT* is proposed as a biased potentially guided intelligent bidirectional RRT* that incorporates biased sampling and artificial potential fields [35]. In more complex environments, artificial potential fields may become trapped at a local minimum solution. Additionally, because of the fixed attractive pole, the tree may grow in the wrong direction, resulting in undesired exploration and performance degradation. The primary issue with the biasing technique is that it becomes too greedy, resulting in a problem of local minima [18]. Another option to improve the sample operation in RRT* is to impose limitations on the sampling space. Through a simple hyper-ellipsoid and a direct bounded sampling method, informed RRT* [7] obtains samples from the configuration space. The Wrapping-based Informed RRT* (WIRRT*) [16] is a modified version of the Informed RRT* that incorporates a wrapping method to accelerate the decrease of the ellipsoidal region that constrains the sample space. Wrapping enhances the performance of a planned path by substituting for intermediate nodes that are wrapped around obstacles. However, informed RRT* base path planning algorithms determine the initial path using RRT*’s uniform sampling approach, so it traverses the whole configuration space to arrive at the optimal path. Hence, an alternative to RRT* path planning algorithms is required for quickly determining the initial path. A Directional RRT* (D-RRT*) path planning algorithm [8] is proposed to find the initial solution using an elliptic created between the start and goal configurations. Even though it outperforms RRT* and Informed RRT* in a cluttered environment, its success rate is very low in a maze and narrow passage environment since it is based only on non-uniform sampling. To address this issue, non-uniform D-RRT* is extended by combining it with uniform sampling known as DR-RRT*, a modified Directional Random-RRT* framework proposed in this paper. A random method is used to combine the non-uniform directional sampling method with uniform sampling [32].

The remainder of the paper is organized as follows. The problem statement is defined in detail in Section 3. Section 4 introduces the proposed DR-RRT* Algorithm. Section 5 covers the AMR simulation results and discussions in three different environments. The real-time implementation is discussed in Section 6. In Section 7, the conclusion and possible future research topics are presented.

3. Problem definition

Consider a configuration space (C-space) $C \subseteq R^{N}$ which includes all possible configurations of the AMR in N-dimensional space. A configuration $x \in C$ specifies the position and the volume occupied by the AMR. $C_{obs}$ denotes obstacle space, while $C_{free} = C ∖ C_{obs}$ denotes obstacle-free space. Let $x_{start} \in C_{free}$ be the start configuration and $x_{goal} \in C_{free}$ be the goal configuration, then $T : [0, 1] \to C$ is the path across the C-space. If $T (τ) \in C_{free} \forall τ \in [0, 1]$ , then the path is considered to be collision-free. The path planning problem refers to finding a collision-free path $T : [0, 1] \to C_{free}$ that start from $T (0) = x_{start}$ and reach $T (1) \in x_{goal}$ and $T (τ) \in C_{free} \forall τ \in [0, 1]$ . Consider Σ is the set of all paths over the configuration space C, and $Σ_{feasible}$ is the set of all feasible paths. Then optimal path planning is defined as finding a feasible path $T^{*}$ such that $(T^{*}) = min {cst (T) : T is feasible}$ . Where $cst : Σ \to R ⩾ 0$ denotes a cost function.

4. Directional Random – RRT*

In the proposed DR-RRT*, a non-uniform directional sampling method combines with uniform sampling using a simple random selection method. Section 4.1 explains the non-uniform directional sampling method and the proposed DR-RRT* framework is discussed in Section 4.2.

4.1. Directional sampling method

The main objective of the Directional Sample is to minimize the sample space by focusing on the direction of the starting configuration to the goal using a simple elliptical heuristic generated between $x_{start}$ and $x_{goal}$ , as illustrated in Fig. 1. This is accomplished through a simple elliptical heuristic between $x_{start}$ and $x_{goal}$ . The purpose of using an elliptical heuristic is to ensure that as little of the environment as possible is covered. To avoid collisions, the clearance length l between the beginning and target nodes is employed, where a is the major axis length and b is the minor axis length. In this scenario, the size of the ellipse is important. If the ellipse is too small, it may become trapped in the obstacles and fail to construct a path. Simultaneously, if the ellipse is too large, the coverage area may be expanded, i.e. the full area may be investigated. Here, the design, i.e., the size of the ellipse, is fully determined by the configuration of the start and goal locations. According to the study, the Euclidean distance between the start and goal configurations is used to calculate the major axis length a, and the minor axis length b is calculated as half of that, i.e. $b = a / 2$ .

Fig. 1.

Ellipse construction in directional sample method.

Algorithm 1 explains the pseudocode for the ‘ $directional sample$ ’ method. The ‘ $directional sample$ ’ method is supplied with the start and goal configurations as inputs and returns a random configuration based on an elliptical heuristic.

Primitive procedures for the ‘ $directional sample$ ’ procedure are described below.

$Findquadrant$ : It determines the quadrant in which the goal node $x_{goal}$ is present for each new node $x_{new}$ .

$Find_angle$ : Using the quadrant, it calculates the length of the ellipse’s major and minor axes, as well as the slope between two points, and then returns the angle between the two points.

$Get_Points_from_Ellipse$ : The random node $x_{r}$ is returned from the elliptical heuristic.

Algorithm 1

$directional sample$ procedure ( $x_{start}$ , $x_{goal}$ )

4.2. DR-RRT* framework

Even though standalone non-uniform directional sampling performance is good in cluttered environments, it fails to build the path in narrow and maze environments since it relies on the elliptical heuristic. So, the proposed DR-RRT* framework combines the non-uniform directional sampling approach with uniform sampling using a simple random selection method. The pseudocode that explains the DR-RRT* framework is given in Algorithm 2. A simple random selection condition $Rand () > 0.5$ is used for selecting the sampling procedure (Step3). A threshold of 0.5 was chosen based on the NRRT* path planning method [32] and our experimental study of various threshold levels. Based on the condition, the $uniform sample$ (Step 4) or $directional sample$ method (Step 6) is chosen (Step 3). The $directional sample$ method generates a random sample state $x_{rand}$ from the elliptical heuristic formed between $x_{start}$ and $x_{goal}$ , whereas the $uniform sample$ method traverses the entire C-space. After finding the sample, the ‘ $nearest$ ’ function determines the node $x_{nearest}$ between v and $x_{rand}$ (Step 7). The ‘ $steer$ ’ function directs along the path that results in $x_{new}$ at a distance δ from $x_{nearest}$ to $x_{rand}$ (Step 8). Determination of the path $T$ is in the obstacle-free region or not using the ‘ $obstaclefree$ ’ function (Step 9). If the node $x_{new}$ and an edge connecting it to the node $x_{nearest}$ are in the obstacle-free region, the ‘ $near_nodes$ ’ function returns the nearby nodes that are contained within a ball of volume $β ((log n) / n)$ surrounding $x_{near}$ , where β is constant (Step 10). The ‘ $updateParent$ ’ function selects a new node’s parent node from nearby nodes (Step 11). Then, using ‘ $add$ ’ function, the node vertex and edge are added to the tree $g (v, e)$ (Step 12). Moreover, the tree g is extended until the stopping criteria are met. Thus, the path between $x_{start}$ and $x_{goal}$ in the tree is determined, and the cost to the node is determined using the ‘ $rewire$ ’ function (Step 13).

Algorithm 2

DR-RRT* framework

Algorithm 3 details the proposed DR-RRT*’s ‘ $updateParent$ ’ procedure and it determines the optimal $x_{near}$ and the shortest path $T$ between $x_{start}$ and $x_{goal}$ .

Algorithm 3

$updateParent (x_{near}, x_{nearest}, x_{new}, T_{nearest})$

Algorithm 4 details the ‘ $rewire$ ’ procedure for the proposed DR-RRT*. Following the addition of $x_{new}$ to the tree g, the ‘ $rewire$ ’ method attempts to rewire the neighboring vertices to find the path $T$ with the lowest cost. If it discovers the path with the lowest cost, it uses the ‘ $addagain$ ’ function to add it to tree g. (Step 5).

Algorithm 4

$rewire (g, x_{new}, x_{near})$

Finally, the DR-RRT* creates a tree $g (v, e)$ from the collection of vertices v and edges e to establish an optimal path $T^{*}$ between the state space $x_{start}$ and $x_{goal}$ as illustrated in Fig. 2. The proposed DR-RRT* utilizes the $directional sample$ function to extract sample points from the smaller configuration space without wasting further samples. Simultaneously, it creates a few samples using the $Uniformsample$ function to avoid the problem of local minima and increase the success rate. Thus, the proposed DR-RRT* combines the advantages of non-uniform, and uniform sampling and it is suitable for all kinds of environments.

Fig. 2.

Tree pattern (a) RRT* and (b) DR-RRT* after 1000, 5000, and 10,000 iterations.

4.3. Probabilistic completeness

Theorem.
Probabilistic completeness is guaranteed by the proposed DR-RRT algorithm. For each given path planning problem* $(x_{start}, x_{goal}, C_{free})$ , there exist constants $u > 0$ and $t_{0} \in R$ , both of which depend only on $x_{goal}$ and $x_{start}$ such that $\begin{matrix} (1) & P ({v^{DRRRT } \cap x_{goal} \neq \emptyset}) > 1 - e^{- u t}, \forall t > t_{0} \end{matrix}$ Where* $v^{DRRRT }$ denotes the DR-RRT* vertices.*
Proof.
Since the DR-RRT* path planning algorithm returns a connected graph for all kinds of considered environments, it follows the RRT*’s probabilistic completeness. □
4.4. Complexity analysis

This section illustrates the proposed DR-RRT* algorithm’s space and time complexity using big O notation. The terms “space complexity” and “time complexity” refer to the amount of space and time required by the given path planning algorithm. Given two functions $f (t)$ and $h (t)$ , $f (t)$ is said to belong to $O (h (t))$ if $\begin{matrix} (2) & lim sup_{t \to \infty} | \frac{f (t)}{h (t)} | < \infty \end{matrix}$

4.4.1. Time complexity analysis

The time complexity of any procedure is defined by the number of procedure calls made to it.

Let the number of procedure calls made by the given path planning algorithm to the $obstaclefree$ procedure be denoted by $M_{n}^{ALG}$ in n iterations.

Lemma 1.
$M_{n}^{DRRRT } \in O (log n)$ .
Proof.
Let $C_{n}^{DRRRT }$ and $R_{n}^{DRRRT }$ represent the number of procedure calls to the $obstaclefree$ procedure in $updateParent$ and the $rewire$ procedure, respectively, then $\begin{matrix} (3) & M_{n}^{DRRRT } = C_{n}^{DRRRT } + R_{n}^{DRRRT } \end{matrix}$ DR-RRT* does not modify the $rewire$ and $updateParent$ procedurally, so the time complexity of $R_{n}^{DRRRT } \in O (log n)$ and $C_{n}^{DRRRT } \in O (log n)$ remains the same as RRT.

As a result, $M_{n}^{DRRRT } \in O (log n)$ . □

4.4.2. Space complexity analysis

The word “space complexity” relates to the path planning algorithm’s memory requirements. DR-RRT* generates a tree $g_{n} = (v_{n}, e_{n})$ , and the size of the tree $g_{n}$ determines the amount of memory used by DR-RRT*.

Lemma 2.
$| g_{n} | \in O (n)$ .
Proof.
For the proposed DR-RRT* path planning algorithm, the size of the tree $| g_{n} |$ is calculated as $| g_{n} | = | v_{n} | + | e_{n} |$ . If the tree $| g_{n} |$ visits n nodes, then $| v_{n} |$ equals n and $| e_{n} |$ equals $n - 1$ . As a result, the proposed DR-RRT* tree’s size is $| g_{n} | = | v_{n} | + | e_{n} | = 2 n - 1$ .

As a result, $| g_{n} | \in O (n)$ . □

5. Numerical simulation

The proposed DR-RRT* path planning algorithm is compared to the existing RRT* and Informed RRT* algorithms using a $384 \times 384$ -pixel 2D map of three different environments: narrow, cluttered, and maze. These three environmental maps are taken into account because they are widely used by robotics researchers in their research work [12,20,24,29,33]. To assess the performance of the various path planning algorithms, four metrics are used: the initial solution cost, i.e., path length, denoted as $c_{i}$ , the planning time, denoted as t, the number of nodes visited, defined as n, and the convergence rate denoted as $c_{r}$ . The experimental stopping criteria for the DR-RRT* tree extension are set at 10,000 samples based on an experimental study of convergence and success rate. The proposed research work experiments are carried out on an Intel i5-7500 CPU with 8 GB RAM and the Robot Operating System Melodic, which runs on Ubuntu 18.04. Because sampling-based algorithms are inherently random, all statistical data for the path-planning algorithm is derived from 100 distinct runs with varying mean and median values. Three different environments, namely, narrow, maze, and cluttered environments shown in Fig. 3, are used to validate the proposed DR-RRT* path planning algorithm.

Fig. 3.

Environments: narrow (a), maze (b), and cluttered (c).

Figure 4 illustrates the path generated by the proposed DR-RRT* using all three environments with a total of 10,000 samples. The samples generated by the proposed DR-RRT* path planning algorithm generate more samples directed toward the goal by visiting a few nodes.

Fig. 4.

Path generated by (a) RRT* and (b) DR-RRT* with 10,000 samples.

Statistical information about the performance measurement planning time t, the initial cost solution $c_{i}$ , and the number of nodes visited n in all three considered environments is presented in Tables 1, 2, and 3. The initial cost performance of the proposed DR-RRT* is improved over RRT* and Informed RRT*. However, Informed RRT* works well in a Maze environment than DR-RRT*. Due to the combination of the uniform and non-uniform, the planning time of the proposed DR-RRT* is larger in the maze and narrow. However, it takes less time than Informed RRT* in the considered cluttered environment. The number of nodes visited by the proposed DR-RRT* is less than RRT* by 3% and 15% less than Informed RRT* in the cluttered environment. The overall performance of the proposed DR-RRT* path planning algorithm is superior to the standard RRT* and Informed RRT* path planning algorithm. Even though the proposed DR-RRT* outperforms the standard RRT* and Informed RRT*, its performance is lesser than the Informed RRT* in the maze environment.

Table 1

Initial cost-performance comparison of the DR-RRT* with popular algorithms

Environment	Algorithm	Minimum (Units)	Median (Units)	Maximum (Units)	Mean (Units)
Narrow	RRT*	522	683	845	680.85
	DR-RRT*	513	672	886	676
	Informed RRT*	524	672	838	680.79
Maze	RRT*	730	887.5	1089	889.94
	DR-RRT*	743	878	1232	886.33
	Informed RRT*	716	862.5	1086	874.44
Cluttered	RRT*	503	593	820	595.89
	DR-RRT*	501	573.5	725	584.8
	Informed RRT*	495	588	699	586.94

Table 2

Time performance comparison of the DR-RRT* with popular algorithms

Environment	Algorithm	Minimum (Sec)	Median (Sec)	Maximum (Sec)	Mean (Sec)
Narrow	RRT*	0.59	1.12	1.56	1.15
	DR-RRT*	0.71	1.75	2.01	1.70
	Informed RRT*	0.99	1.71	2.12	1.69
Maze	RRT*	1.00	1.17	1.56	1.20
	DR-RRT*	1.33	1.67	2.56	1.72
	Informed RRT*	0.61	0.74	0.90	0.74
Cluttered	RRT*	0.99	1.09	1.45	1.11
	DR-RRT*	1.06	1.25	1.71	1.27
	Informed RRT*	2.26	2.68	3.69	2.72

Table 3

Nodes visit performance comparison of the DR-RRT* with popular algorithms

Environment	Algorithm	Minimum	Median	Maximum	Mean
Narrow	RRT*	5354	8114.5	8334	8029
	DR-RRT*	4130	7921	8097	7712.33
	Informed RRT*	5209	7210.5	7579	7044.44
Maze	RRT*	7278	7846	8111	7842.49
	DR-RRT*	7090	7609	7843	7568.96
	Informed RRT*	4606	4903.5	5142	4894.02
Cluttered	RRT*	7229	7443	7582	7446.36
	DR-RRT*	6857	7081.5	7221	7076.34
	Informed RRT*	7968	8370.5	8583	8349.85

The boxplot in Fig. 5 illustrates the initial cost solution performance of the proposed DR-RRT* in the three different environments. It improves the initial cost performance by about 1%. The boxplot in Fig. 6 illustrates the time performance of the proposed DR-RRT* in the three different environments. Due to the combination of uniform and non-uniform sampling techniques, the proposed DR-RRT* takes a longer planning time than RRT*. However, the proposed DR-RRT* time performance is faster than Informed RRT* by 53%.

Fig. 5.

Initial cost performance.

Fig. 6.

Time performance.

Fig. 7.

Number of nodes visited performance.

The boxplot in Fig. 7 illustrates the node visiting a performance of the proposed DR-RRT* in the three different environments. The proposed DR-RRT* visits lesser nodes than RRT*. However, the proposed DR-RRT* visits more nodes than Informed RRT*. Even though Informed RRT* visits fewer nodes than DR-RRT* in the maze and narrow environments. In the cluttered environment, it explores 18 % of the nodes more than the proposed DR-RRT* path planning algorithm. Moreover, the proposed DR-RRT* achieves a 100% success rate in all three different environments, whereas previous D-RRT* path planning algorithms cannot achieve the 100% result in maze and narrow environments.

The proposed DR-RRT* path planning algorithm is also evaluated using the convergence rate parameter. The convergence rate is defined as $\frac{cst (T_{i}) - cst (T^{*})}{t_{opt} - t_{i}}$ (Units/sec) [24]. Where $T_{i}$ represents the initial feasible path computed in time $t_{i}$ and $T^{*}$ represents the optimal path computed in time $t_{opt}$ , and $cst$ is the cost function. Table 4 shows the statistical convergence rate performance data of the proposed DR-RRT* path planning algorithm compared with popular algorithms in all three environments considered. Figure 8 shows how quickly the proposed DR-RRT* converges compared to RRT* and informed RRT*.

6. Validation in a real-time environment

6.1. Ambient intelligent navigation architecture

The proposed DR-RRT* path planning method is implemented as a global planner using an ambient Intelligent navigation architecture shown in Fig. 9. The ambient Intelligent navigation scheme moves the robot from the start point to the goal point on the map using the robot’s sensor data with directional information. The modules of the ambient Intelligent navigation architecture are outlined here. The perception module is responsible for sensing the robot’s status as well as its surroundings, which is performed by collecting raw data from sensors such as the 2D-LiDAR and Inertial Measurement Unit (IMU). The localization module uses a variety of approaches to detect where the robot is in the environment and what data it is receiving from the robot’s exteroceptive sensors. The path planning module is responsible for calculating a feasible path from the beginning location to the destination point while avoiding obstacles. The microcontroller, which sends control signals to the motors via drives, regulates the mobility of the mobile robot via the motion control module.

6.2. Real-time implementation

The proposed path planning algorithm is implemented on the TurtleBot3 robot in a real-time laboratory environment shown in Fig. 10 using the ROS Melodic. Using sensor data, the Turtlebot3 robot goes from the starting place to the stated destination location on the map. The Simultaneous Localization and Mapping algorithm [9] is used to generate a 2D map using 2D LiDAR and odometry data. The size of the map, which measures 384 by 384 pixels with a resolution of 0.05 pixels/m, is utilized to validate the proposed algorithm. The proposed DR-RRT* path planning method is implemented as a global path planner, while a Dynamic-Window Approach is utilized as a local path planner to account for dynamic obstacles. The global path plan generated using the proposed DR-RRT* path planning algorithm is visualized using the Rviz tool as shown in Fig. 11. Table 5 shows statistical data for the proposed DR-RRT* performance measure in a real-time laboratory environment using popular algorithms. The proposed DR-RRT* path planning algorithm outperforms both RRT* and Informed RRT*.

Table 4
Convergence rate comparison of the DR-RRT* with popular algorithms

Environment Algorithm Mean (Units/Sec)

Narrow RRT* 0.21

DR-RRT* 0.35

Informed RRT* 0.35

Maze RRT* 0.21

DR-RRT* 0.14

Informed RRT* 0.3

Cluttered RRT* 0.11

DR-RRT* 0.16

Informed RRT* 0.09

Environment	Algorithm	Mean (Units/Sec)
Narrow	RRT*	0.21
DR-RRT*	0.35
Informed RRT*	0.35
Maze	RRT*	0.21
DR-RRT*	0.14
Informed RRT*	0.3
Cluttered	RRT*	0.11
DR-RRT*	0.16
Informed RRT*	0.09

Fig. 8.

Convergence rate performance.

Fig. 9.

Navigation architecture.

Fig. 10.

A real-time environment map.

Fig. 11.

TurtleBot3 navigation in Rviz.

Table 5

Performance comparison of the DR-RRT* with popular algorithms

Parameter	Algorithm	Mean
Cost (m)	RRT*	6.86
	DR-RRT*	6.58
	Informed RRT*	6.76
Time (s)	RRT*	12.4
	DR-RRT*	14
	Informed RRT*	13.9
Node visited	RRT*	1596
	DR-RRT*	1566
	Informed RRT*	1580

7. Conclusion and future work

RRT* is the optimal path-planning algorithm among sampling-based algorithms, but it suffers from a slow convergence problem. To overcome this issue, this article proposed a directional RRT* algorithm for autonomous mobile robots called DR-RRT*. The proposed DR-RRT* combines the advantages of non-uniform and uniform sampling in the RRT* path planning algorithm. The proposed DR-RRT* path planning algorithm is evaluated in the gazebo simulation using a TurtleBot3 robot with three different 2D maps namely, narrow, maze, and cluttered environments. Four different parameters such as the number of nodes visited, initial cost, time, and convergence rate are used to evaluate the proposed DR-RRT* path planning algorithm. The overall performance of the proposed DR-RRT* path planning algorithm is superior to the standard RRT* and Informed RRT* path planning algorithm in the cluttered environment. The proposed DR-RRT* path planning algorithm improves the initial cost performance by about 1% and it is 53% faster than Informed RRT* in the cluttered environment. In the cluttered environment, it explores 18 % of the nodes more than the proposed DR-RRT* path planning algorithm. Moreover, the proposed DR-RRT* achieves a 100% success rate in all three different environments, whereas previous D-RRT* path planning algorithms cannot achieve the 100% result in the maze and narrow environments. Thus, the proposed DR-RRT* path planning algorithm is suitable for all kinds of environments. The proposed research framework is also validated in a real-time laboratory environment using the TurtleBot3 robot as a global planner, and it can be extended as a local planner. The proposed DR-RRT* path planning algorithm can be used in any real-time autonomous mobile robot navigation application, such as warehouses for industrial material handling. In addition, the proposed research can be extended with path optimization methods to refine the generated path in real-time applications.

Conflict of interest

None to report.

References

Ayala,

Mandow,

Amor and

Fuentes, A mobile and interactive multiobjective urban tourist route planning system, J. Ambient Intell. Smart Environ. 9(1) (2017), 129–144. doi:10.3233/AIS-160413.

Beyer,

Jazdi,

Göhner and

Yousefifar, Knowledge-based planning and adaptation of industrial automation systems, in: IEEE International Conference on Emerging Technologies and Factory Automation, ETFA, Vol. 2015-Octob, 2015, pp. 1–4. doi:10.1109/ETFA.2015.7301635.

Colombo,

Fontanelli,

Legay,

Palopoli and

Sedwards, Efficient customisable dynamic motion planning for assistive robots in complex human environments, J. Ambient Intell. Smart Environ. 7(5) (2015), 617–634. doi:10.3233/AIS-150338.

Elbanhawi and

Simic, Sampling-based robot motion planning: A review, IEEE Access 2 (2014), 56–77. doi:10.1109/ACCESS.2014.2302442.

Ermacora,

Rosa and

Toma, Fly4SmartCity: A cloud robotics service for smart city applications, J. Ambient Intell. Smart Environ. 8(3) (2016), 347–358. doi:10.3233/AIS-160374.

Galceran and

Carreras, A survey on coverage path planning for robotics, Rob. Auton. Syst. 61(12) (2013), 1258–1276. doi:10.1016/j.robot.2013.09.004.

J.D.

Gammell,

S.S.

Srinivasa and

T.D.

Barfoot, Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic, in: IEEE International Conference on Intelligent Robots and Systems, 2014, pp. 2997–3004. doi:10.1109/IROS.2014.6942976.

Ganesan,

S.K.

Natarajan and

Srinivasan, A global path planning algorithm for mobile robot in cluttered environments with an improved initial cost solution and convergence rate, Arab. J. Sci. Eng. (2022), 1–15. doi:10.1007/s13369-021-06452-3.

Grisetti,

Kümmerle,

Stachniss and

Burgard, A tutorial on graph-based SLAM, IEEE Intell. Transp. Syst. Mag. 2(4) (2010), 31–43. doi:10.1109/MITS.2010.939925.

10.

S.S.H.

Hajjaj and

K.S.M.

Sahari, Review of research in the area of agriculture mobile robots, in: Lecture Notes in Electrical Engineering, Vol. 291, LNEE, 2014, pp. 107–118. doi:10.1007/978-981-4585-42-2_13.

11.

X.A.

Jasmine and

S.R.

Shantha, Behavior architecture controller for an autonomous robot navigation in an unknown environment to perform a given task, Int. J. Phys. Sci. 10(5) (2015), 182–191. doi:10.5897/IJPS2014.4242.

12.

I.B.

Jeong,

S.J.

Lee and

J.H.

Kim, Quick-RRT*: Triangular inequality-based implementation of RRT* with improved initial solution and convergence rate, Expert Syst. Appl. 123 (2019), 82–90. doi:10.1016/j.eswa.2019.01.032.

13.

Karaman and

Frazzoli, Incremental sampling-based algorithms for optimal motion planning, Robot. Sci. Syst. 6 (2011), 267–274. doi:10.15607/rss.2010.vi.034.

14.

L.E.

Kavraki,

Švestka,

J.C.

Latombe and

M.H.

Overmars, Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE Trans. Robot. Autom. 12(4) (1996), 566–580. doi:10.1109/70.508439.

15.

Kim,

Lee and

S.E.

Yoon, Cloud RRT*: Sampling cloud based RRT*, in: Proceedings – IEEE International Conference on Robotics and Automation, 2014, pp. 2519–2526. doi:10.1109/ICRA.2014.6907211.

16.

M.C.

Kim and

J.B.

Song, Informed RRT* towards optimality by reducing size of hyperellipsoid, in: IEEE/ASME International Conference on Advanced Intelligent Mechatronics, AIM, Vol. 2015-Augus, 2015, pp. 244–248. doi:10.1109/AIM.2015.7222539.

17.

S.M.

LaValle, Rapidly-exploring random trees: A new tool for path planning, 1998, http://coitweb.uncc.edu/~xiao/itcs6151-8151/RRT.pdf.

18.

S.M.

LaValle,

J.J.

Kuffner,

B.R.

Donald et al., Rapidly-exploring random trees: Progress and prospects, Algorithmic Comput. Robot. New Dir. 5 (2001), 293–308.

19.

S.M.

LaValle and

J.J.

KuffnerJr., Randomized kinodynamic planning, Int. J. Rob. Res. 20(5) (2001), 378–400. doi:10.1177/02783640122067453.

20.

Li,

Wei,

Gao,

Wang and

Fan, PQ-RRT*: An improved path planning algorithm for mobile robots, Expert Syst. Appl. 152 (2020), 113425. doi:10.1016/j.eswa.2020.113425.

21.

Liao,

Wan,

Hua,

Ma,

Zhu and

Qing, F-RRT*: An improved path planning algorithm with improved initial solution and convergence rate, Expert Syst. Appl. 184 (2021), 115457. doi:10.1016/j.eswa.2021.115457.

22.

Noreen,

Khan and

Habib, Optimal path planning using RRT* based approaches: A survey and future directions, Int. J. Adv. Comput. Sci. Appl. 7(11) (2016), 97–107. doi:10.14569/ijacsa.2016.071114.

23.

Pérez-Hurtado,

M.Á.

Martínez-del-Amor,

Zhang,

Neri and

M.J.

Pérez-Jiménez, A membrane parallel rapidly-exploring random tree algorithm for robotic motion planning, Integr. Comput. Aided. Eng. 27(2) (2020), 121–138. doi:10.3233/ICA-190616.

24.

A.H.

Qureshi and

Ayaz, Potential functions based sampling heuristic for optimal path planning, Auton. Robots 40(6) (2016), 1079–1093. doi:10.1007/s10514-015-9518-0.

25.

J.R.

Sánchez-Ibáñez,

C.J.

Pérez-Del-pulgar and

García-Cerezo, Path planning for autonomous mobile robots: A review, Sensors 21(23) (2021), 7898. doi:10.3390/s21237898.

26.

Short,

Pan,

Larkin and

Van Duin, Recent progress on sampling based dynamic motion planning algorithms, in: IEEE/ASME International Conference on Advanced Intelligent Mechatronics, AIM, Vol. 2016-Septe, 2016, pp. 1305–1311. doi:10.1109/AIM.2016.7576950.

27.

Sprute,

Tönnies and

König, Interactive restriction of a mobile robot’s workspace in a smart home environment, J. Ambient Intell. Smart Environ. 11(6) (2019), 475–494. doi:10.3233/AIS-190539.

28.

Svenstrup,

Bak and

H.J.

Andersen, Minimising computational complexity of the RRT algorithm a practical approach, in: Proceedings – IEEE International Conference on Robotics and Automation, 2011, pp. 5602–5607. doi:10.1109/ICRA.2011.5979540.

29.

Tahir,

A.H.

Qureshi,

Ayaz and

Nawaz, Potentially guided bidirectionalized RRT* for fast optimal path planning in cluttered environments, Rob. Auton. Syst. 108 (2018), 13–27. doi:10.1016/j.robot.2018.06.013.

30.

R.H.

Taylor,

Menciassi,

Fichtinger,

Fiorini and

Dario, Medical robotics and computer-integrated surgery, in: Springer Handbook of Robotics, Springer, 2016, pp. 1657–1683. doi:10.1007/978-3-319-32552-1_63.

31.

L.G.D.O.

Veras,

F.L.L.

Medeiros and

L.N.F.

Guimaraes, Systematic literature review of sampling process in rapidly-exploring random trees, IEEE Access 7 (2019), 50933–50953. doi:10.1109/ACCESS.2019.2908100.

32.

Wang,

Chi,

Li,

Wang and

M.Q.-H.

Meng, Neural RRT*: Learning-based optimal path planning, IEEE Trans. Autom. Sci. Eng. 17(4) (2020), 1748–1758. doi:10.1109/TASE.2020.2976560.

33.

Wang,

Li and

M.Q.H.

Meng, Kinematic constrained bi-directional RRT with efficient branch pruning for robot path planning, Expert Syst. Appl. 170 (2021), 114541. doi:10.1016/j.eswa.2020.114541.

34.

Wang,

Mizukami,

Tada and

Matsuno, Navigation of a mobile robot in a dynamic environment using a point cloud map, Artif. Life Robot. 26(1) (2021), 10–20. doi:10.1007/s10015-020-00617-3.

35.

Wu,

Xu,

Zhen and

Wu, Biased sampling potentially guided intelligent bidirectional RRT* algorithm for UAV path planning in 3D environment, Math. Probl. Eng. 2019 (2019). doi:10.1155/2019/5157403.

36.

M.A.

Yakoubi,

M.T.

Laskri and

M.N.

Zennir, The complete coverage for the vacuum cleaner robot using pulse-coupled neural network in dynamic environments, J. Ambient Intell. Smart Environ. 8(6) (2016), 603–617. doi:10.3233/AIS-160400.

37.

Yang

et al., Keep healthcare workers safe: Application of teleoperated robot in isolation ward for Covid-19 prevention and control, Chinese J. Mech. Eng. (English Ed.) 33(1) (2020), 1–4. doi:10.1186/s10033-020-00464-0.

A novel directional sampling-based path planning algorithm for ambient intelligence navigation scheme in autonomous mobile robots

Abstract

Keywords

1. Introduction

2. Related work

3. Problem definition

4. Directional Random – RRT*

4.1. Directional sampling method

4.4.1. Time complexity analysis

6.1. Ambient intelligent navigation architecture

6.2. Real-time implementation

Table 4 Convergence rate comparison of the DR-RRT* with popular algorithms Environment Algorithm Mean (Units/Sec) Narrow RRT* 0.21 DR-RRT* 0.35 Informed RRT* 0.35 Maze RRT* 0.21 DR-RRT* 0.14 Informed RRT* 0.3 Cluttered RRT* 0.11 DR-RRT* 0.16 Informed RRT* 0.09

Conflict of interest

References

Table 4
Convergence rate comparison of the DR-RRT* with popular algorithms

Environment Algorithm Mean (Units/Sec)

Narrow RRT* 0.21

DR-RRT* 0.35

Informed RRT* 0.35

Maze RRT* 0.21

DR-RRT* 0.14

Informed RRT* 0.3

Cluttered RRT* 0.11

DR-RRT* 0.16

Informed RRT* 0.09