Improvements on the virtual obstacle method

Abstract

While the artificial potential field has been widely employed to design path planning algorithms, it is well-known that artificial potential field-based algorithms suffer a severe problem that a robot may sink into a local minimum point. To address such problems, a virtual obstacle method has been developed in the literature. However, a robot may be blocked by virtual obstacles generated during performing the virtual obstacle method if the environments are complex. In this article, an improved virtual obstacle method for local path planning is designed via proposing a new minimum criterion, a new switching condition, and a new exploration force. All the three new contributions allow to overcome the drawbacks of the artificial potential field-based algorithms and the virtual obstacle method. As a consequence, feasible collision-free paths can be found in complex environments, as illustrated by final numerical simulations.

Introduction

Performing missions for autonomous aerial and ground vehicles usually requires planning optimal collision-free paths in situ (or in real time) from its current position to a target point. It is well-known that the real-time path planning is challenging, especially when the environments are full of complex obstacles. To address this challenging issue, a large number of algorithms for path planning have been proposed or developed in the literature. ^{1 –5} In general, the algorithms for path planning can be classified into two categories, that is, calculus- and graph-based ones. Although the calculus-based path planning techniques can generate optimal paths, they usually suffer from high computational cost, which makes the calculus-based methods non-applicable for real-time missions. Although the graph-based path planning methods also have some disadvantages, such as suboptimality, sharp, and nonnegotiable corners due to the discretization of workspace, these disadvantages can be overcome by applying well-developed methods for flyable or movable trajectory generation.

According to available information of the environment, the graph-based path planning algorithms usually include two categories: (1) local path planning and (2) global path planning. The global path planning takes into account the overall environmental information, and the optimal path planning can be planned off-line. In fact, there are some well-developed global path planning algorithms, such as grid-based method (e.g. A* algorithm ⁶ ) and sampling-based method (e.g. the probabilistic roadmap method, ⁷ and the Rapidly-exploring Random Tree (RRT) method ^8,9 ).

Contrasting with the global path planning, the local path planning is usually employed if the global information of environment is not available due to the limited range of detection sensors. As the computational cost of local path planning is lower in comparison with the global path planning, it is more suitable for real-time applications. For this reason, extensive studies have been done on designing local path planning algorithms. Liu and Arimoto ¹⁰ introduced a method for path planning by computing the tangent graph of obstacles. Based on Monte Carlo method, a reactive randomized algorithm was proposed by Savkin and Hoy. ¹¹ Both the methods ^10,11 are computationally expensive in some special environments so that they may not be able to generate feasible paths in real time. By assuming that the target lies outside the convex hull of obstacles, an online planner was developed by Shiller. ¹² However, this online planner may not find a feasible path to the target if the detection range is smaller than the radii of obstacles. In addition to the three methods, there are two main kinds of algorithms for local path planning. The first kind is related to those based on the artificial potential field (APF) ^{13 –15} and the rest is of intelligent methods, like the genetic algorithm ¹⁶ and the swarm particle algorithm. ¹⁷

The core idea of the APF-based methods is to create some artificial potentials and to plan feasible paths from current location to the target according to the forces generated by the artificial potentials. ¹⁴ While the APF-based methods provide a good trade-off between the computational effort and the quality of the collision-free paths, it also has some inherent limitations. For instance, the APF may have many local minimum points where the overall force generated by the APF is zero so that the robot will be trapped at those points. Some improvements to the classical APF-based methods have been proposed in recent years. Chen et al. ¹⁵ and Sfeir et al. ¹⁸ redefined the potential function so that the distribution of the virtual force was improved to reduce the number of local minimum points. Instead of eliminating the local minimum points, virtual obstacles and virtual potentials ^19,20 were proposed to help a vehicle to escape from local minimum points. More recently, Zhu et al. ²¹ used some intelligent techniques, for example, “follow way” strategy, to escape from local minimum points.

Among the aforementioned improvements on the classical APF-based methods, the virtual obstacle method (VOM) ^19,20 is probably the most powerful algorithm to avoid local minimum points. However, it is found that when a robot moves to the corner of an L-shaped tunnel, the virtual obstacles of the VOM will block the way to the target. In addition, the criterion, defined in the VOM to estimate if or not a robot is trapped into a local minimum point, is not applicable in some special environments, as analyzed in the section of review on APF-based methods.

To guarantee an autonomous robot to find a collision-free path in complex environments, an improved VOM is developed in the article by proposing a new reliable criterion, a new switching condition, and a new potential force. This improved VOM allows to find collision-free paths in complex environments, as illustrated by the two final numerical simulations.

The remainder of this article is organized as follows: In the section of preliminaries, the general mathematical model for graph-based path planning problem is formulated, and the potential functions of APF-based methods are recalled. Then, after reviewing the drawbacks of the conventional APF method and the VOM, an improved VOM is developed. Finally, some numerical examples are simulated, illustrating the viability of the improved VOM in comparison with the conventional APF method and the VOM.

Preliminaries

In this section, the mathematical model for general graph-based path planning problems is established, and the potential functions, which will be used by the APF method and the VOM, are presented.

Mathematical model

Let X be the state space of the two-dimensional plane. Denote by $x_0\in X$ and $x_f\in X$ the initial point and the target point in X, respectively. Assume that there are n (n is a positive integer) obstacles. Let $x_i\in X$ and $X_i\subset X$ $\left(i=1,2,\dots ,n\right)$ be the center and the region of the ith obstacle, respectively. Then, the path planning problem is described as follows.

Problem 1

The path planning problem consists of finding a collision-free path $\gamma \in \mathcal{X}$ starting from x ₀ and finally reaching x_f such that $\gamma \cap X_i=\varnothing$ for $i=1,2,\dots ,n$ .

The APF-based methods, such as the conventional APF method ^13,14 and the VOM, ^19,20 are probably the most popular methods for addressing such path planning problems. As stated in the “Introduction” section, the conventional APF method and VOM may not find collision-free paths in complex environments. In this article, we will present an improved VOM in the framework of the APF method. Before proceeding to the improved VOM, we first present the potential functions in the next subsection, which are fundamental and necessary for the subsequent analyses.

Potential functions

The core idea of the APF-based methods is that some virtual repulsive and attractive potentials are defined in the field X so that a collision-free path from the initial point to the target can be found by following the forces generated by those virtual potentials. Note that the destination of the path planning problem is to reach the target. Hence, an attractive potential should be defined around the target. The attractive potential function at the target is commonly given by

$U_a(x)=k_a\parallel x-x_f{\parallel }^2,x\in X$

1

where $k_a>0$ is a proportional gain. Taking the negative gradient of the attractive potential function in equation (1), we have that the attractive force $F_{att}$ is given by

$F_{att}(x)=-\nabla U_a(x)=-2k_a(x-x_f),x\in X$

2

Meanwhile, a repulsive potential given by Kim and Khosla ²² to repel the robot from each obstacle is expressed as

$U_{r-i}(x)=\left\{\begin{array}{ll}\frac{1}{2}{k}_{r-i}{\left(\frac{1}{{\rho }_i(x)}-\frac{1}{R_i}\right)}^2\hfill & {\rho }_i(x)\le R_i\hfill \\ 0\hfill & {\rho }_i(x)>R_i\hfill \end{array}\right.$

3

where $k_{r-i}>0$ is a proportional scaling factor of the repulsive potential, ${\rho }_i(x)=\text{min}\{\parallel x-x_i\parallel :x_i\in X_i\}$ is the shortest Euclidean distance from the current state x to the center of the ith obstacle, and $R_i>0$ is the largest distance of the region, which is influenced by the repulsive potential. To this end, the repulsive force around the ith obstacle can be readily obtained by taking the negative gradient of the repulsive potential function in equation (3), that is

$F_{r-i}(x)=\left\{\begin{array}{ll}{k}_{r-i}\left(\frac{1}{{\rho }_i(x)}-\frac{1}{R_i}\right)\frac{1}{{\rho }_i{(x)}^2}\frac{\partial {\rho }_i(x)}{\partial x}\hfill & {\rho }_i(x)\le R_i\hfill \\ 0\hfill & {\rho }_i(x)>R_i\hfill \end{array}\right.$

4

where

$\frac{\partial {\rho }_i(x)}{\partial x}=\frac{x-x_i}{\parallel x-x_i\parallel }$

The total repulsive force then can be expressed as

$F_{r-total}(x)={\displaystyle \sum _{i=1}^n}{F}_{r-i}(x)$

5

In addition to the attractive force in equation (2) and the repulsive force in equation (5), another kind of force, namely, rotational force, is usually employed by APF-based methods. ²³ The main role of the rotational force is to make sure the path around each obstacle to be parallel with its surface so that the trajectory around each obstacle is smoother. In general, the rotational force is generated by a rotational vector field. Around the ith obstacle, the rotational force is commonly given by

$F_{rot-i}(x)=\left\{\begin{array}{ll}{k}_i^{rot}\frac{r_{rot}^i-{\rho }_i(x)}{{\rho }_i(x)}\frac{{\lambda }_i\times \left({\sigma }_i\times {\lambda }_i\right)}{‖{\lambda }_i\times \left({\sigma }_i\times {\lambda }_i\right)‖}\hfill & {\rho }_i(x)\le R_i^{rot}\hfill \\ 0\hfill & {\rho }_i(x)>R_i^{rot}\hfill \end{array}\right.$

6

where $k_i^{rot}>0$ is a scaling factor of the rotational vector field and $R_i^{rot}>0$ is the maximal radius of the circle that is influenced by the rotational vector field around X_i . In addition, the two unit vectors ${\sigma }_i$ and ${\lambda }_i$ are defined by

${\sigma }_i=\frac{x_f-{\overline{x}}_i}{‖x_f-{\overline{x}}_i‖}$

${\lambda }_i=\frac{x-{\overline{x}}_i}{‖x-{\overline{x}}_i‖}$

where ${\overline{x}}_i\in X_i$ is the closest point in the ith obstacle to the current state x. Then, because the number of obstacles in the plane X is assumed to ben, it follows that the total rotational force is given by

$F_{rot-total}(x)={\displaystyle \sum _{i=1}^n}{F}_{rot-i}(x)$

7

To this end, by summing up all the potential forces in equations (2), (5), and (7), the overall potential field force in the state space X are expressed as

$F_{APF}(x)=F_{att}(x)+F_{rep-total}(x)+F_{rot-total}(x)$

8

where $x\in X$ This overall potential force has been widely used in the literature for APF-based methods to generate collision-free paths.

Review on typical APF-based methods

Given the overall potential force in equation (8), two typical APF-based methods, including the conventional APF method ⁸ and the VOM, ²⁰ will be reviewed in this section.

The conventional APF method

As a matter of fact, the conventional APF method is a straightforward application of the overall potential force, ⁸ as shown in Algorithm 1.

Algorithm 1

Conventional APF method.

Once each obstacle has a convex-like shape and far away from others, the conventional APF method performs well in finding collision-free paths. However, the conventional APF method may not find a feasible path to the target if there are some concave-shaped obstacles, as illustrated in Figure 1. Note that at point A in Figure 1, the overall potential force in equation (8) generated by the concave-shaped obstacle and the target can be zero. In such a case, the conventional APF method in Algorithm 1 will be trapped at point A instead of making a step forward (see line 5 in Algorithm 1). Therefore, the conventional APF method may fail to find collision-free paths once there are local minimum points where the overall potential force is zero.

Figure 1.

The existence of a local minimum point (where the overall potential force is zero) in an environment with a concave-shaped obstacle.

Virtual obstacle method

To address the local minimum point issue encountered by the conventional APF method, a virtual obstacle concept has been proposed. ²⁰ The core idea of the virtual obstacle concept is first to introduce a criterion to determine if or not a robot is trapped into a local minimum point. The criterion is given by

$\parallel x_k-x_{k-\lambda }\parallel \le S_a$

9

where $\lambda <k$ is a positive integer and $S_a>0$ is a positive threshold. Once the criterion in equation (9) is met, then a virtual obstacle X_v with an extra potential is added to the overall potential field, as shown by lines 5 and 6 in Algorithm 2.

Algorithm 2

VOM.

Although the VOM performs better than the conventional APF method, as it is seen by comparing Figures 1 and 2, it should be noticed that the criterion in equation (9) may lead a robot to make a wrong decision. Taking the scenario in Figure 3 as an example, the robot will be trapped if P ₁ and P ₂ are too close so that equation (9) is met. In addition, for some specific obstacles, such as the one presented in Figure 4, the virtual obstacle will block the only way to the target. All in all, the VOM may still fail to find a feasible collision-free path even though it has been improved in comparison with the conventional APF method.

Figure 2.

A collision-free path generated by the VOM. VOM: virtual obstacle method.

Figure 3.

The robot is blocked at P ₁ if P ₁ and P ₂ are close enough.

Figure 4.

The way to the target is blocked by a virtual obstacle.

Improved VOM

To address the aforementioned issues of the VOM, an improved VOM will be established in this section, by defining a new local minima criterion, a new exploration force, and a new switching condition.

Local minima criterion

Since the local minima criterion in equation (9) may make a wrong decision, we design a new local minima criterion

$R_k<\text{R}$

10

where $R_k>0$ is the radius of the smallest circle that contains the previous k waypoints and $R>0$ is a threshold which depends on the environment.

Exploration force

To solve the blocking issue of the VOM, some attractive potentials should be added around those states that have never been reached within the range of measurement, defined as $X_{new}$ . In this article, we assume that the state can be added in $X_{new}$ only if the distance between state and robot is smaller than the maximum range of detector d ₁ and greater than the reachable range d ₂, as shown in Figure 5. We call this new added attractive potential field as the exploration potential field. Let $x_i^{new}\in X_{new}$ ( $i=1,\dots ,M$ and M is a positive integer) be a sampled state that has never been reached by the robot. Then, the force generated by the exploration potential field around $x_i^{new}$ can be represented as

$F_{exp-i}(x)=\left\{\begin{array}{ll}{k}_{exp-i}\frac{{\rho }_i(x)}{d_1-{\rho }_i(x)}\frac{x-x_i^{new}}{{\rho }_i(x)}\hfill & d_2<{\rho }_i(x)<d_1\hfill \\ 0\hfill & {\rho }_i(x)\ge d_1\hfill \end{array}\right.$

11

Figure 5.

The range of the sensor and $X_{new}$ .

where $k_{exp-i}>0$ is a scaling factor of the exploration force and ${\rho }_i(x)=\parallel x-x_i^{new}\parallel$ . It is clear that the overall exploration force can be expressed by

$F_{exp-total}\left(x\right)={\displaystyle \sum _{i=1}^M}{F}_{exp-i}\left(x\right)$

12

Then, the improved global potential force, denoted by $F_{APF}^{new}(x)$ , can be calculated by summing up $F_{APF}\left(x\right)$ and $F_{exp-total}\left(x\right)$ , that is

$F_{APF}^{new}\left(x\right)=F_{APF}\left(x\right)+F_{exp-total}\left(x\right)$

13

This new overall potential force will be used to generate feasible collision-free path later.

Switching condition

Based on the development in the previous subsection, an improved VOM consists of two modes: the conventional mode and the exploration mode. While only the VOM is used to generate path in the conventional mode, both the exploration force and the VOM will be combined in the exploration mode. The switching condition between the two modes will be designed in this subsection.

In principle, the switching condition consists of three criteria. The first criterion is the one defined in equation (10), which determines whether or not the robot is sank into a local minimum point. The second criterion is defined by

$\left\{\begin{array}{l}\parallel x_{k-j}-x_i^{new}\parallel \ge d_2\hfill \\ X_i\cap \{\lambda x_k+(1-\lambda )x_i^{new}:\lambda \in [0,1]\}=\varnothing \hfill \end{array}\right)$

14

where $i=1,2,\dots ,n$ and $j=0,1,\dots ,k$ . Note that the satisfaction of equation (14) indicates that the state $x_i^{new}$ within the detection range has not yet been visited and that the straight line between $x_i^{new}$ and x_k does not intersect with X_i ’s. Therefore, if both equations (10) and (14) are true, then the algorithm switches from the conventional mode to the exploration mode. In the exploration mode, once the criterion in equation (14) is violated, the algorithm switches to the conventional mode.

According to the above developments, the improved VOM is described in Algorithm 3. It is worth mentioning here that the efficiency of the improved VOM is comparable to the conventional VOM because computing the new defined conditions is not time-consuming. In the next section, the new algorithm will be tested by two complex environments.

Algorithm 3

Improved VOM.

Numerical simulations

In this section, we consider two maze-like environments, as shown in Figures 6 and 7, to illustrate the improved VOM by comparing with the conventional APF method, the VOM, A* algorithm, and RRT* algorithm. The parameters of the example are given as follows:

1. the range of sensor is 1.2 m, indicating that the robot can detect obstacles up to only 1.2 m from itself;

2. the obstacles in the environment have three types of shape: (1) concave-shaped obstacle, (2) bar-shaped obstacle, and (3) cylindrical-shaped obstacle;

3. the reachable range is 1.0 m which means that only the state within 1.0 m around the robot will be marked as reachable state.

Figure 6.

Case A.

Figure 7.

Case B.

Case A

As for the environment of Figure 6, the path generated by the conventional APF method in Algorithm 1 is shown in Figure 8. It is clear from Figure 8 that the conventional APF method cannot find a feasible path from the initial point to the target. The reason is that the overall potential force at the end of the generated path is zero.

Figure 8.

Case A: the path generated by the conventional APF with a local minimum point. APF: artificial potential field.

The conventional VOM in Algorithm 2 is also used to generate path, which is presented in Figure 9. Although the VOM tries to escape from local minimum points by employing virtual obstacles, the virtual obstacles blocked the way to the target, as shown by the solid circles in Figure 9. Finally, the improved VOM (Algorithm 3) developed in the article is used, and a feasible collision-free path is found, which is depicted in Figure 10.

Figure 9.

Case A: the path generated by the conventional VOM with blocking Issue. VOM: virtual obstacle method.

Figure 10.

Case A: the path generated by the improved VOM. VOM: virtual obstacle method.

Case B

Analogously, the conventional APF method, the VOM, and the improved VOM are all employed to generate collision-free paths in the environment of Figure 7. The path generated by the conventional APF method is shown in Figure 11, illustrating that the robot is trapped in a local minimum point. Figure 12 shows the path generated by the conventional VOM, indicating that the robot cannot find the way to the target because the virtual obstacles blocked the way to the target. Finally, the path generated by the improved VOM is shown in Figure 13.

Figure 11.

Case B: the path generated by the conventional APF. APF: artificial potential field.

Figure 12.

Case B: the path generated by the conventional VOM. VOM: virtual obstacle method.

Figure 13.

Case B: the path generated by the improved VOM. VOM: virtual obstacle method

To show the efficiency of the improved VOM, it is also compared with two typical path planning algorithms: A* algorithm and RRT* algorithm. The average time to find the paths for case A and case B by each algorithm is listed in Table 1. It is clearly seen from Table 1 that the improved VOM consumes just around 16% computational time of A* algorithm. However, both the conventional VOM and RRT* algorithm cannot find feasible paths for case A and case B due to the blocking issue and the local minimum points.

Table 1.

Average time to find the path.

Case	IVOM	VOM	A*	RRT*
Case A	18.2 s	Blocking issue	112.5 s	Local minimum
Case B	17.6 s	Blocking issue	196.5 s	Local minimum

VOM: virtual obstacle method; IVOM: Improved virtual obstacle method.

All in all, it is concluded from the above simulations that the improved VOM, by addressing the blocking issues that are encountered by the VOM, can find feasible collision-free paths in complex environments and it is more efficient than A* algorithm.

Conclusions

As the APF-based methods, including the conventional APF method and VOM, may not generate feasible collision-free paths in complex environments, an improved VOM is proposed in the article. Once the robot is trapped in a local minimum point, a new potential force is added to the APF to help the robot bypass the local minimum point, addressing the blocking issue. As the conventional local minima criterion may lead to a wrong decision, a new local minima criterion is designed. Since an exploration force is added to address the issue that the path may be blocked by virtual obstacles, the improved VOM has two modes: the exploration mode and the conventional mode. In the article, a switching condition for the switching between the two modes is devised. All these contributions allow the improved VOM to generate feasible collision-free path in complex environments, as shown by the final numerical simulations. Future work will consider to extend the improved VOM so that it can tackle more practical scenarios, such as large-scale and dynamic environments.