Path planning of a mobile robot using an improved mixed-method of potential field and wall following

Abstract

The existing Bug algorithms, which are the same as wall-following algorithms, offer good performance in solving local minimum problems caused by potential fields. However, because of the odometer drift that occurs in actual environments, the performance of the paths planned by these algorithms is significantly worse in actual environments than in simulated environments. To address this issue, this article proposes a new Bug algorithm. The proposed algorithm contains a potential field function that is based on the relative velocity, which enables the potential field method to be extended to dynamic scenarios. Using the cumulative changes in the internal and external angles and the reset point of the robot during the wall-following process, the condition for state switching has been redesigned. This improvement not only solves the problem of position estimation deviation caused by odometer noise but also enhances the decision-making ability of the robot. The simulation results demonstrate that the proposed algorithm is simpler and more efficient than existing wall-following algorithms and can realise path planning in an unknown dynamic environment. The experimental results for the Kobuki robot further validate the effectiveness of the proposed algorithm.

Introduction

Mobile robots must be capable of performing autonomous navigation in unknown environments. This requires the robot to plan its motion to reach destination points while avoiding obstacles. Several methods have been proposed to address this challenge. Based on whether global information is required, path planning algorithms can be divided into two categories—global and local path planning algorithms. ¹ The key precondition of global methods is the acquisition of complete and accurate prior knowledge about the environment. ² However, the dynamic complexity, unpredictability, and real-time performance of actual application scenarios pose challenges to global path planning and navigation. By contrast, the local method only uses the robot sensors to achieve obstacle-avoidant navigation in unknown scenarios. The main methods for implementing this approach include the artificial potential field (APF) method ³ and the Bug algorithm, which is the same as the wall-following algorithm. ⁴

The APF method is implemented using the superposition of the attractive field generated by the target point and the repulsive force field generated by the surrounding obstacles. Under the force of a superimposed potential field, the robot can only move along the negative gradient direction of the potential field. During the movement process, the robot is pulled by the attractive force of the target and pushed by the repulsive force of the surrounding obstacles, following an effective path between the starting point and the target point. The advantages of the APF approach are its low planning complexity, fast response, and effective obstacle avoidance. ⁵ Because conventional methods only contain location information, it is easy for them to fall into local minima, and therefore, they can only be applied to static environments. ⁶

To solve the local minimum problem, Bug algorithms are becoming increasingly popular for local path planning. Bug algorithms are also known as wall-following algorithms. A Bug algorithm only needs to know the target location and not the global environment information. ⁷ The basic concept underlying such algorithms is the design of conditions for switching between the wall-following mode and the target approach mode. ⁸ The algorithm must ensure that the robot switches from the wall-following mode to the target approach mode when its distance to the target is sufficiently short to guarantee global convergence.

A certain rule in a Bug algorithm is designed based on only the local information. When the robot touches a wall, it switches to wall-following mode to bypass the obstacle. The setting of these switching rules gives Bug algorithms wider applicability. Both Bug1 ⁹ and Bug2 ^10,11 firstly draw an imaginary line between the initial and target positions, called the M-line. When the robot touches a wall en route to the target, the path point is considered as the hit-point position. Then, the agent follows the border of the obstacle until it hits the same M-line on the other side of the obstacle. If that point is closer to the target than the hit-point position, then it departs from the obstacle. Zhang defined $l_{\text{rg}}$ as the line between the agent and the ending position and defined Map as the route map that is recorded by the robot in wall-following mode. ¹² If there are no intersections between $l_{\text{rg}}$ and Map, then the robot ends its wall-following motion and returns to the APF.

Although the aforementioned algorithms perform well, both the M-line and $l_{\text{rg}}$ require accurate measurement using an odometer. A recent study ¹³ compared the navigation performance of DistBug, ¹⁴ Rev2, ¹⁵ Alg2, ¹⁵ TangentBug, ¹⁶ Insert-bug, ¹⁷ and Com1 ¹⁸ with sensor noise. The experimental results showed that accurate location estimation was difficult to achieve because of odometer drift, which significantly decreased the performance of these algorithms. Additionally, there were considerable computational and memory overheads, even when the location estimation was accurate.

Zhu designed a new mode-switching condition. When the distance between the robot and the target began to decrease, the robot reverted to the target-approaching mode. ¹⁹ Borenstein ²⁰ and Sanchez ²¹ switched states when the angle between the robot and the target was below a certain threshold. However, when the shape of the obstacle becomes complex, these switching conditions may be too simple to complete the task.

To achieve efficient and real-time path planning in an unknown dynamic environment, this article proposes an improved Bug algorithm that addresses many of the limitations of the existing APF and Bug algorithms using accumulated angle information. Based on the optimised potential field function, this method can achieve path planning in a dynamic environment. In addition, we designed a new mode-switching condition based on the relative cumulative angle and reset point, which not only alleviates the sensor noise problem but also reduces the path length (PL) in a static environment compared with some classical Bug algorithms. The results of experimentation using the Kobuki robot ²² further validate the effectiveness of the proposed algorithm.

The rest of this article is organised as follows. In the second section, the improved APF method and the wall-following algorithm are described in detail, including the APF mode, mechanism of obstacle avoidance based on wall-following algorithm and the switching mechanism between the two states. The third section not only introduces the mathematical model of the mobile robot, the simulation results on the Webots platform and the application of the algorithm in the actual environment but also discusses the convergence and stability of the algorithm in detail. In addition, the third section also compares with several traditional methods (the minimum risk method, TangentBug and Bug2). Finally, the final section represents the conclusions and future work.

Algorithm description

The new method consists of two modes, namely APF mode and wall-following mode, similar to the multiple modes employed in previous studies. ¹¹ The two modes cyclically switch, as shown in Figure 1. The local minimum is the point at which the robot begins to swing or wander around in a cycle when the robot is in APF mode.

Figure 1.

Switching relationship between states.

The methods of realising the two modes, as well as their switching conditions, are described in the following subsections.

APF mode

• Function: When the robot is not trapped at a local minimum, an APF is used to avoid obstacles.

• Principle: The essence of the APF approach is to construct a virtual potential field by introducing a general potential field composed of the attractive potential field of the target and the repulsive field of the obstacles. The attractive potential field is proportional to the distance between the robot and the target. The repulsive potential field is inversely proportional to the distance between the robot and the obstacles. ²³

The most commonly used attractive and repulsive potentials take the following forms ²⁴

$U_{\text{att}}\left(x\right)=\frac{1}{2}{k}_{\text{att}}||x-x_{\text{g}}|{|}^m$

1

$U_{\text{rep}}\left(x\right)=\{\begin{array}{l}\frac{1}{2}{k}_{\text{rep}}{\left(\frac{1}{\rho }-\frac{1}{{\rho }_0}\right)}^2||x-x_{\text{g}}|{|}^n,\rho <{\rho }_0\hfill \\ 0,\hspace{1em}\rho \ge {\rho }_0\hfill \end{array}$

2

where $x-x_{\text{g}}$ represents the distance between the robot $x$ and the target $x_{\text{g}}$ ; $U_{\text{att}}\left(x\right)$ and $U_{\text{rep}}\left(x\right)$ denote the attractive and repulsive potential energies, respectively; m, n, $k_{\text{att}}$ , $k_{\text{rep}}$ and ${\rho }_0$ are constant coefficients; and $\rho =||x_{\text{obs}}-x||$ is the distance between the robot and the obstacle. Because the conventional methods only contain location information, they work well in static environments but not in dynamic environments. The enhanced potential function improves the performance in dynamic scenarios by introducing the relative velocities of the target and obstacle

$U_{\text{att}}\left(x\right)=\frac{1}{2}{k}_{\text{att}}||x-x_{\text{g}}|{|}^m+k_{\text{att}\_v}||v_{\text{g}}-v|{|}^{m\_v}$

3

$U_{\text{rep}}\left(x\right)=\{\begin{array}{l}\frac{1}{2}{k}_{\text{rep}}{\left(\frac{1}{\rho }-\frac{1}{{\rho }_0}\right)}^2||x-x_{\text{g}}|{|}^n+\hfill \\ \hspace{1em}{k}_{\text{rep}\_v}{v}_{\text{or}}^{n\_v},\rho <{\rho }_0\text{and}{v}_{\text{or}}>0\hfill \\ 0,\hspace{1em}\rho \ge {\rho }_0\text{or}{v}_{\text{or}}\le 0\hfill \end{array}$

4

$v_{\text{or}}=\left(v_{\text{obs}}-v\right)\cdot e_{\text{or}}$

5

where $v$ is the velocity of the robot; $v_{\text{g}}$ is the velocity of the moving target; $v_{\text{obs}}$ is the velocity of the moving obstacle; $v_{\text{g}}-v$ is the relative velocity between the moving target and the robot; $v_{\text{obs}}-v$ is the relative velocity between the moving obstacle and robot; m_v and n_v are constant coefficients; $e_{\text{or}}$ is the unit vector from the obstacle to the robot and $v_{\text{or}}$ is the projection of the relative speed between the robot and the obstacle on the line between the robot and the obstacle (i.e. the inner product of vector $v_{\text{obs}}-v$ and unit vector $e_{\text{or}}$ ). For $v_{\text{or}}>0$ , the robot moves towards the obstacles and must avoid them, whereas for $v_{\text{or}}\le 0$ , the robot moves away from the obstacles and does not avoid them. Thus, the improved attractive force $F_{\text{att}}$ and repulsive force $F_{\text{rep}}$ are given by the negative gradient of the attractive and repulsive potential energies, as follows

$F_{\text{att}}=\frac{m}{2}{k}_{\text{att}}||x-x_{\text{g}}|{|}^{m-1}{e}_{\text{rg}}+m\_v\times k_{\text{att}\_v}||v_{\text{g}}-v|{|}^{m\_v-1}{e}_{\text{gr}\_v}$

6

$F_{\text{rep}}=\{\begin{array}{ll}{F}_{\text{rep}1}+F_{\text{rep}2}+F_{\text{rep}\_v},\hfill & \rho \ge {\rho }_0\hfill \\ 0,\hfill & \rho \ge {\rho }_0\hfill \end{array}$

7

$\{\begin{array}{l}{F}_{\text{rep}1}=k_{\text{rep}}\left(\frac{1}{\rho }-\frac{1}{{\rho }_0}\right)\frac{1}{{\rho }^2}||x-x_{\text{g}}|{|}^n{e}_{\text{or}}\hfill \\ \hspace{1em}\hspace{1em}\rho \le {\rho }_0\hfill \\ F_{\text{rep}2}=\frac{n}{2}\times k_{\text{rep}}{\left(\frac{1}{\rho }-\frac{1}{{\rho }_0}\right)}^2||x-x_{\text{g}}|{|}^{n-1}{e}_{\text{rg}}\hfill \\ \hspace{1em}\hspace{1em}\rho \le {\rho }_0\hfill \\ F_{\text{rep}\_v}=n\_v\times k_{\text{rep}\_v}{v}_{\text{or}}^{n\_v-1}{e}_{\text{or}\_v}\hfill \\ \hspace{1em}\hspace{1em}\rho \le {\rho }_0\hfill \end{array}$

8

where $e_{\text{rg}}$ is the unit vector from the robot to the target and $e_{\text{gr}\_v}$ is the unit vector in the direction of the relative velocity from the robot to the target. Because the component of $F_{\text{att}}$ including $e_{\text{gr}\_v}$ tends to maintain the same speed as the target, it can be used to track dynamic targets. $e_{\text{or}\_v}$ represents the unit vector in the direction of the relative velocity from the obstacle to the robot. $F_{\text{rep}\_v}$ strengthens the repulsive effect of obstacles on the robot. The relationships between the repulsive force and its three components are depicted in Figure 2, where T is the moving target.

Figure 2.

Relationships between unit vectors.

The total force applied to the robot is the sum of the attractive and repulsive forces

$F_{\text{sum}}=F_{\text{att}}+F_{\text{rep}}$

9

The enhanced potential function overcomes the poor performance of dynamic scenarios. However, the robot may stop moving or wander around the point at which the attractive force is equal to the repulsive force, which is known as the local minimum. The following switch conditions were set to identify the local minimum.

Switching condition: 1 | 2

Condition 1: $|F_{\text{att}}+F_{\text{rep}}|\le \epsilon$

Condition 2: $|{\theta }_{\text{att}}-{\theta }_0|\ge 90°$

In all reported end conditions, ‘&’ denotes logical ‘AND’ and ‘|’ denotes logical ‘OR’. Condition 1 means that the superposition force tends towards zero (ε is a very small positive number), which is a common condition for judging the local minimum. However, because the system is dynamic, the robot overshoots the equilibrium position and either oscillates or wanders around in a cycle. ²⁰ Therefore, local minima cannot be accurately identified by exclusively using condition 1 in actual environments. In condition 2, θ _att and θ ₀ represent the robot-to-target direction and actual instantaneous direction of travel, respectively. If the angle between the forward direction of the robot and the target direction exceeds 90°, that is, if the robot starts to move away from the target, it is likely to become trapped. Therefore, to avoid such a situation, the controller monitors condition 2. If condition 2 is satisfied, then the system switches to the recovery algorithm, as discussed in the subsequent subsections.

Wall-following mode

• Function: By moving along the edge of an obstacle, the robot can bypass the obstacle and escape the local minimum trap.

• Principle: As discussed previously, the limitations of the existing Bug methods are that the mode-switching conditions are imperfect and that a perfect global position estimate is difficult to achieve. This section introduces a new Bug method to address the local minimum problem of the APF by employing the relative cumulative angle.

As shown in Figure 3, the robot starts at S and moves directly to the target at T based on the total force of the potential field. When it encounters obstacles (such as that at A), the robot continues to move along the obstacles (at A–D) under the potential field. Because of the constant change in the resultant force direction during the movement process (i.e. the resultant force in segments A–C moves to the right, whereas the resultant force in segments C–D moves to the left), the robot can accelerate, decelerate or even move back and forth between B and D. This behaviour occurs because the attractive force is equal to the repulsive force at point C, which is the local minimum. The angle between the direction of the instantaneous velocity and the attractive force at the cut-off point at C is defined as θ, which is theoretically 90°. When the robot is at C, assuming that the obstacle has been removed, the repulsive force generated by the obstacle disappears, and the robot is only affected by the attractive force. The robot direction is deflected from the original forward direction to the direction of the wall by a certain angle θ. The new forward direction is close to the attractive direction and facing the target.

Figure 3.

Force model near local minimum. (The points A–F represent the path points, respectively. $F_{\text{att}}^{\text{A}-\text{B}}$ , $F_{\text{rep}}^{\text{A}-\text{B}}$ and $F_{\text{sum}}^{\text{A}-\text{B}}$ represent the attractive force, repulsive force and total force of the robot in segments A–B, respectively, and v is the instantaneous velocity direction of the robot.)

If the robot can continue following the wall to point F, then its direction is deflected at an angle of θ in the direction of attraction. This behaviour is similar to the deflection generated by the removal of the obstacle at C. Additionally, a wall gap is located at E, which means that there is no obstacle in the forward direction of the robot. The robot believes that the obstacle has been bypassed. According to this obstacle-avoidance process, changing θ is sufficient for the robot to reach the target position.

Switching conditions were designed according to the above assumptions and analysis.

Switching conditions: 1 & 2 & 3

Condition 1: ${\theta }_{\text{total}}\approx \theta$

Condition 2: $|{\theta }_{\text{inner}}|>\theta$

Condition 3: $D_{\text{latest}}>D_{\text{current}}$

The angle of rotation of the robot under the wall-following mode to the same side of the barrier is defined as the inner angle, ${\theta }_{\text{inner}}$ , and that to the opposite side of the obstacle is the outer angle, ${\theta }_{\text{outer}}$ . The outer angle is positive, and the inner angle is negative. Considering the complexity of the obstacles for the robot in motion, the relative accumulation of angle ${\theta }_{\text{total}}$ and reset point are introduced. As shown in Figure 3, the local minimum (at point C) is defined as the initial attitude ( ${\theta }_{\text{inner}}={\theta }_{\text{outer}}={\theta }_{\text{total}}=0$ ). The relative cumulative angle ${\theta }_{\text{total}}={\theta }_{\text{inner}}+{\theta }_{\text{outer}}$ describes the cumulative amount of course angle change by the robot during all periods under the wall-following mode, which represents the angular relationship between the current time and the initial time; the reset point can be expressed as ${\theta }_{\text{total}}=0$ , where the robot attitude is the same as the initial attitude (at point C).

Condition 1 introduces a reset point to help the robot decompose the complex environment into several simple environments. The reason for implementing this condition is that after resetting ${\theta }_{\text{inner}}={\theta }_{\text{outer}}={\theta }_{\text{total}}=0$ at the reset point, the robot replans the following environment as a new unknown environment. This cycle can be repeated until the robot bypasses the obstacle.

In the previous hypothesis, the deflection angle of the velocity direction at C towards the obstacle is the same as that of the inner angle ${\theta }_{\text{inner}}$ . Only at the gap in the wall can the robot deflect around the outer corner to the obstacle; therefore, the task of condition 2 is to find a position that is similar to point E in Figure 3.

As shown in condition 3, the vertical projection distance $D_{i|i=\text{A},\text{B},\text{C}\mathrm{...}}$ represents the projection of the Euclidean distance between the path point and the target on the line between the local minimum position (point A) and the target, which can be divided into $D_{\text{latest}}$ and $D_{\text{current}}$ . $D_{\text{latest}}$ represents the vertical projection distance between the last path point (which meets ${\theta }_{\text{inner}}$ and goes from 0° to −90°, or the reset point condition) and the target, and $D_{\text{current}}$ is the vertical projection distance between the current path point (which meets ${\theta }_{\text{inner}}$ and goes from 0° to −90°, or the reset point condition) and the target. The robot continues to approach the target using condition 3 to ensure global convergence during the obstacle-avoidance process.

An example is depicted in Figure 4. Influenced by the force field, the robot travels from S to T. According to the switching conditions of the potential field state, the robot enters the wall-following mode at A, sets the initial attitude ( ${\theta }_{\text{inner}}^{\text{A}}={\theta }_{\text{outer}}^{\text{A}}={\theta }_{\text{total}}^{\text{A}}=0$ ) and records the vertical projection distance $D_{\text{A}}$ between this point and the target simultaneously. It then proceeds to find the reset point or a path point that satisfies the switching condition. In the section from A to B, the robot deflects to the opposite side of the wall. When the robot is at B, its angle parameters are ${\theta }_{\text{outer}}^{\text{B}}=+90°$ , ${\theta }_{\text{inner}}^{\text{B}}=0°$ and ${\theta }_{\text{total}}^{\text{B}}=+90°$ ; similarly, at C, ${\theta }_{\text{outer}}^{\text{C}}=+180°$ , ${\theta }_{\text{inner}}^{\text{C}}=0°$ and ${\theta }_{\text{total}}^{\text{C}}=+180°$ ; at D, ${\theta }_{\text{outer}}^{\text{D}}=+180°$ , ${\theta }_{\text{inner}}^{\text{D}}=-90°$ and ${\theta }_{\text{total}}^{\text{D}}=+90°$ , and the agent calculates the vertical projection distance $D_{\text{D}}$ between itself and the target. The robot remains in wall-following mode because $D_{\text{D}}>D_{\text{A}}$ . At E, the controller sets the angle parameters as ${\theta }_{\text{outer}}^{\text{E}}=+180°$ , ${\theta }_{\text{inner}}^{\text{E}}=-180°$ and ${\theta }_{\text{total}}^{\text{E}}=0°$ , which satisfy the conditions of the reset point and are presented to the same initial attitude as that at A ( ${\theta }_{\text{inner}}^{\text{A}}={\theta }_{\text{outer}}^{\text{A}}={\theta }_{\text{total}}^{\text{A}}=0°$ ). The agent records the vertical projection distance $D_{\text{E}}$ between this point and the target and replans the environment as a new, unknown environment. The robot deflects to the same side of the wall in sections E and F ( ${\theta }_{\text{outer}}^{\text{F}}=0°$ , ${\theta }_{\text{inner}}^{\text{F}}=-90°$ and ${\theta }_{\text{total}}^{\text{F}}=-90°$ ) and calculates the vertical projection distance $D_{\text{F}}$ between itself and the target at F. Because $D_{\text{F}}<D_{\text{E}}$ , the condition for exiting wall-following mode is satisfied, and the robot returns to path planning according to the potential field at F until it reaches T.

Figure 4.

Ideal path planning in a sample environment. (The state from A to F is the same, and the state is the same in these intervals. For segment ab in the figure, the angle state within this range is the same as that of point A. In this article, we use point A to represent segment ab. The other B–F all represent the state in the corresponding line segment.)

Simulation and experimental results

Simulation model

The experimental study consisted of simulations based on Webots (Cyberbotics Ltd, Switzerland) and experiments on actual Kobuki robots. The laser sensor Rplidar A1M8 (Slamted Ltd, China) was used as the range sensor. The position of the obstacle in the Lidar coordinates can be calculated at sampling times t1 and t2. The difference between the two positions is the relative displacement between the obstacle and the robot, $\left(\left(v_{\text{obs}}-v\right)\times \left(t2-t1\right)\right)$ . The target velocity $v$ can be obtained from the motor encoder, so the obstacle velocity $v_{\text{obs}}$ can be calculated. $v$ and $v_{\text{obs}}$ are indicated in Figure 2. The coordinate system shown in Figure 5 was defined as the principal coordinate system. During the simulation, the principal coordinate system at the initial moment was used as the global coordinate system for path planning.

Figure 5.

Force map for wall-following mode.

Algorithm realisation

In APF mode, at each sampling moment, the linear velocity v, angular velocity $\omega$ and expected motion direction ${\theta }_{\text{exp}}$ of the robot are as follows

$v=\{\begin{array}{ll}{v}_{\text{max}}\left(1-|\text{cos}\left({\theta }_{\text{rep}}-{\theta }_0\right)|\right),\hfill & F_{\text{rep}}>0\hfill \\ v_{\text{max}},\hfill & F_{\text{rep}}=0\hfill \end{array}$

10

$\omega ={\omega }_{\text{max}}\left({\theta }_{\text{res}}-{\theta }_0\right)$

11

${\theta }_{\text{exp}}={\theta }_{\text{res}}$

12

where $v_{\text{max}}$ is the maximum linear velocity of the robot, ${\omega }_{\text{max}}$ is the maximum angular velocity of the robot, ${\theta }_{\text{rep}}-{\theta }_0$ is the angle between the resultant direction and the moving direction of the robot and ${\theta }_{\text{res}}-{\theta }_0$ is the desired direction of motion of the robot.

In wall-following mode, v, $\omega$ and ${\theta }_{\text{exp}}$ at each sampling moment are as follows

$v=v_{\text{max}}\left(1-|\text{cos}\left({\theta }_{\text{rep}}-{\theta }_0\right)|\right)$

13

$\omega ={\omega }_{\text{max}}\left({\theta }_{\text{res}}-{\theta }_0\right)+{\omega }_{\text{d}}\left(d_0-d_{\text{s}}\right)$

14

${\theta }_{\text{exp}}={\theta }_{\text{rep}}-\alpha$

15

where $d_0-d_{\text{s}}$ is the difference between the measured distance between the robot and the wall and the preset distance between the robot and the wall, the modified values ${\omega }_{\text{d}}\left(d_0-d_{\text{s}}\right)$ maintain the distance between the robot and the wall at a preset value and α is the deflection angle (the theoretical value is 90°). After approaching the obstacle at a speed of v and entering wall-following mode with the expected direction of motion ${\theta }_{\text{exp}}$ as a reference (as expressed in equation (15)), the robot moves along the wall and adjusts its posture to be parallel to the wall, as depicted in Figure 5.

The cumulative angle is measured by a gyroscope and calculated using the following expression, where $\theta \left(t\right)$ is the forward direction of the robot at time t

${\theta }_{\text{total}}={\displaystyle \sum \left[\theta \left(t\right)-\theta \left(t-1\right)\right]}$

16

Parameter adjustment

Parameter α affects the smoothness of the robot trajectory in wall-following mode. Considering practical application environments, the relationship between the trajectory and ${\theta }_{\text{exp}}$ is analysed for α = 88°, 90° and 92°. As illustrated in Figure 6(a), section I is the adjustment region in which the robot changes mode from APF mode to wall-following mode. In section II, the robot is in wall-following mode. When the robot is in section II, it moves forward only in the expected direction of motion. The expected direction of motion of sampling area II at equal time intervals is plotted as a box plot in Figure 6(b). Section III is the region in which the robot changes mode from wall-following mode to APF mode.

Figure 6.

Parameter influence on (a) motion trajectories and (b) expected motion angle.

The results indicate that the expected direction of motion is more inclined to the obstacle at α = 92° than at α = 90°, which leads to a trajectory that is close to the wall. Therefore, the robot needs to adjust ${\theta }_{\text{exp}}$ continuously in section II to avoid collision with the wall. Similarly, it is in a state of constant attitude adjustment during section II when $\alpha =88°$ . However, when $\alpha =90°$ , the change in the expected direction of motion is minimised, and the trajectory is the smoothest in section II. In the subsequent simulation, $k_{\text{att}}=30$ , $k_{\text{rep}}=0.2$ and α = 90°.

Simulation studies

The reset point can decompose a complex environment into a collection of simple environments. Figure 7(a) to (f) presents the six typical simple environments that were used to verify the effectiveness of the algorithm. Figure 7(a) to (d) shows an obstacle with a rectangular border, and Figure 7(e) and (f) illustrates an obstacle with an arbitrary bending angle. The experimental results indicate that a robot using the proposed algorithm can successfully plan paths in various obstacle-strewn environments with different characteristics. Therefore, path planning for any environment can be conducted by using the reset point.

Figure 7.

Path planning in different simple environments: (a) to (d) an obstacle with a rectangular border and (e) and (f) an obstacle with an arbitrary bending angle.

Figure 8(a) depicts a complex static environment composed of typical simple environments. The robot successfully reaches the target point, which proves the validity of the reset point. There are both static and moving obstacles in the environment in Figure 8(b). After avoiding the moving obstacle, the agent starts to follow the boundary of the U-shaped obstacle and successfully reaches the static target. Spaces with moving obstacles and targets are shown in Figure 8(c) to (f). In the simulation experiment, we set the target to move for 10s at a linear velocity of 0.5 m/s and then stop. The robot moves at the linear velocity of 0.5 m/s until the moving target is reached. The starting positions of the robot and the target are the same in the scenarios depicted in Figure 8(c) and (e), but the obstacle speeds are different. In the situations illustrated in Figure 8(e) and (f), the starting position is changed without changing the environment, and consequently, the obstacle speed is different. The proposed method performed well under these conditions.

Figure 8.

Path planning in different complex environments. (a) Environment with only static obstacles. (b) Environment with static and moving obstacles ( $v_{\text{max}}=0.5\text{ m/s}$ , $v_{\text{obs}}=0.4\text{ m/s}$ ). (c) to (f) Environments with moving obstacles and targets. The red line with an arrow indicates the target trajectory: (c) $v_{\text{max}} =0.5\text{ m/s}$ , $v_{\text{obs}}=0.4\text{ m/s}$ ; (d) $v_{\text{max}}=0.5\text{ m/s}$ , $v_{\text{obs}}=0.6\text{ m/s}$ ; (e) $v_{\text{max}}=0.5\text{ m/s}$ , $v_{\text{obs}}=0.4\text{ m/s}$ ; (f) $v_{\text{max}}=0.5\text{ m/s}$ , $v_{\text{obs}}=0.6\text{ m/s}$ .

Stability and convergence of the algorithm

The stability of the controller is given by the Lyapunov ²⁵ stability formula $V_{i|i=1,2,3}$ , where V ₁, V ₂ and V ₃ denote the potential field obstacle-avoidance state, dynamic obstacle-avoidance state and wall-following state, respectively. The convergence of the algorithm is represented by the Euclidean distance between the robot and the target point. Figure 9(a) and (b) depicts stability and convergence, according to the algorithm in a static scene (Figure 8(a)). Figure 9(c) and (d) illustrates the algorithm in a dynamic scene (Figure 8(d)). The value of the correlation function gradually decreases to the equilibrium point, proving that the controller is stable and reliable.

$\{\begin{array}{l}{V}_1=\frac{1}{2}||x-x_{\text{g}}|{|}^2\hfill \\ V_2=\frac{1}{2}||v_{\text{g}}-v|{|}^2\hfill \\ V_3=\frac{1}{2}{\left({\theta }_{\text{rep}}-\alpha -{\theta }_0\right)}^2\hfill \end{array}$

17

$d=\sqrt{||x-x_{\text{g}}|{|}^2}$

18

Figure 9.

Stability and convergence of the algorithm in static and dynamic environments. (a) Stability and (b) convergence of the algorithm in a static scene. (c) Stability and (d) convergence of the algorithm in a dynamic scene.

Comparison with the minimum risk method, TangentBug and Bug2

The simulation results presented in Figure 10 illustrate the performance of the proposed method compared with those of the minimum risk method, ²⁶ TangentBug ¹⁶ and Bug2. ¹¹ Table 1 presents PL measurements traced by the minimum risk method, TangentBug, Bug2 and the proposed method in scenarios 1, 2 and 3, which correspond to the three scenarios in Figure 10. Wang proposed a minimum risk method based on a memory grid that records the trajectory traversed by the robot. After encountering obstacles, the robot uses the memory grid to address the local minimum problem faced by a goal-oriented robot navigating in unknown indoor environments. However, when trapped in a local minimum, the robot uses ‘trial-and-return’ behaviour to arrive at the nearest exit. Although the trial-and-return behaviour appears to be reliable in some environment, it is time consuming in U-shaped environments, as shown in Figure 10(a). The proposed method is more efficient because it uses the cumulative angle and reset point design in the switching conditions. The results of the proposed method are presented in Figure 10(b).

Table 1.

Path length measurements traced by the minimum risk method, TangentBug, Bug2 and the proposed method in scenarios 1, 2 and 3.

Scenario	Minimum risk	Tangent Bug	Bug2	Proposed method
Scenario 1	52	/	/	9
Scenario 2	/	74	/	23
Scenario 3	/	/	164	65

Figure 10.

Comparison of the proposed method with some existing methods. (a) Minimum risk method in environment 1. (b) Proposed algorithm in environment 1. (c) TangentBug in environment 2. (d) Proposed algorithm in environment 2. (e) Bug2 in environment 3. (f) Proposed algorithm in environment 3.

TangentBug constructs a local tangent graph within the maximum range of the robot sensor. The agent records the distance from the local minimum to the obstacle and adds the remaining distance from that obstacle to the target. This distance is represented by $d_{\text{min}}$ . After the robot senses a point on the boundary of the obstacle that is smaller than $d_{\text{min}}$ , it triggers switch in conditions and, if possible, moves directly to the target. The proposed method not only substitutes the vertical distance for a straight distance but also uses angle information to exit wall-following mode earlier, generating a shorter PL than TangentBug. The results of TangentBug and the proposed method are depicted in Figure 10(c) and (d), respectively.

Bug2 draws an imaginary line between the beginning and end positions, called the M-line. When it touches a wall on the way to the target, the robot records the distance $d_{\text{min}}$ between itself and the target. The robot then follows the border of the obstacle until it hits the same M-line on the other side of the obstacle. If the robot meets the M-line at a point whose goal distance is shorter than $d_{\text{min}}$ , then Bug2 stops following the boundary and departs from the obstacle. The proposed method uses the cumulative change in the advance angle recorded by the gyroscope to replace the M-line, which not only alleviates the sensor noise problem but also reduces the number of calculations required. Figure 10(c) and (d) presents the results of Bug2 and the proposed method, respectively.

Experiments on an actual robot

The proposed method was also been tested on an actual Kobuki robot (shown in Figure 11), and experiments were conducted in an indoor environment populated by various boxes. The experimental scenario is illustrated in Figure 12. Each obstacle consisted of a square box.

Figure 11.

Kobuki robot used in the experiments.

Figure 12.

Experimental results in an actual environment. Robot reaches the goal in: (a) a static environment and (b) an actual environment with static and dynamic obstacles.

Figure 12(a) depicts the static obstacle used in the experiment. The robot started to move from S and avoided the static obstacle by switching into wall-following mode twice (starting at A and C). At D, the robot switched back into APF mode. Finally, it reached T due to the attractive force of the target. Figure 12(b) depicts the scene containing the dynamic obstacles. The speed of both the robot and the moving obstacle was 0.3 m/s. The robot started to move from S. After avoiding moving obstacles at A, the robot started to follow the boundary of the static obstacle at B and switched from wall-following mode at C. The robot finally reached the target.

From the actual planned trajectory, it can be observed that the robot successfully bypassed obstacles in an actual complex environment and completed the path from the starting point to the target point. Comparison of the experimental results with the corresponding simulation results reveals that the two sets of results are consistent, which further verifies the feasibility of the algorithm.

Conclusion

In this study, an improved Bug method was developed to implement path planning in unknown dynamic environments, using a relative velocity to construct a new potential field function. In addition, the relative cumulative angle was recorded for the wall-following status and represented the change in the advance angle between the current attitude of the robot and its initial attitude, improving the capability of the robot to understand unknown environments. Further, a reset point was defined as the position with the same angular relationship as the initial position and was used to reset the state to the initial state to simplify the environment. By utilising the relative cumulative angle and the reset point of the new switching conditions, the robot approached the target gradually in wall-following mode under global convergence. Compared with the existing methods, which experience odometry drift, the proposed method is straightforward to implement in actual environments, making it more suitable for implementation in such environments.

The simulation results demonstrate that the proposed method can solve the local minimum problem of the potential field method by switching conditions in various environments, and it performs well in dynamic environments. Compared with the existing algorithms (minimum risk method, TangentBug and Bug2), the proposed method has a shorter PL and higher efficiency. Experiments on actual robots further verified the feasibility and applicability of the proposed algorithm.

However, this algorithm also has some limitations. First, the control structure based on condition switching makes the robot have a fast response ability and reduces the instability caused by inaccurate perception of the environment. However, direct behaviour switching makes coordination between behaviours more difficult, and occasionally unexpected situations occur. In addition, the hyperparameters set in this study were universal values applicable to most scenes. In some environments, problems such as excessive turning radii and uneven planning lines will still exist. In the future, more reasonable methods will be used to dynamically adjust the hyperparameters according to the environment.