Reactive Robot Navigation Utilizing Nonlinear Control

Abstract

In this paper, we propose a computationally efficient heuristic solution to choosing a path around obstacles in the face of limited sensor information. Specifically, we propose a navigation algorithm for a mobile robot that reaches a measured target position while avoiding obstacles, making decisions in real-time (without stopping) and relying strictly on information obtained from limited and noisy robot-mounted sensors to determine the location and severity of obstacles. The solution utilizes fuzzy processing to encode the environment – the fuzzy encoding is used both in deciding on an intermediate target direction and in a collision-avoidance strategy. A closed-loop nonlinear feedback control provides a smooth motion with stability guarantees. Simulation results in a corridor environment demonstrate expected collision-free trajectories.

1. Introduction

Unlike classic mathematical methods, heuristic algorithms often produce practical – although sub-optimal – solutions to mobile robot navigation problems in real-time. Masehian and Sedighizadeh's survey [9] shows that the proportion of heuristic methods to classic methods has been approaching unity for the past 30 years. However, even heuristic methods often rely on accurate sensor information and a large amount of computational power.

Different architectures for reactive mobile-robot navigation include fuzzy-logic, feedback control and BEAM (for Biology, Electronics, Aesthetics and Mechanics) strategies. The navigation system proposed here combines these three methods in a novel fashion, causing the robot to go around obstacles in a way that appears insect-like; it reacts to obstacles that it encounters along the way to the target rather than planning a global or optimal path. The fuzzy encoding of the environment includes the target, currently-faced obstacles and recently-passed obstacles. From this information, a fuzzy inference produces an intermediate target position. The closed-loop nonlinear feedback control, with a short-term memory element, uses the error between the current position and an intermediate target to produce commanded translational and rotational velocities. A BEAM-style control signal, referred to here as a ‘virtual force’, gets added directly to the commanded velocities as if it were a disturbance in the feedback loop. In this case, it is introduced as a deliberate and helpful disturbance. The virtual control serves as a collision-avoidance system to ensure that the robot does not brush against obstacles.

The very simplest control strategy stems from the concept of BEAM. Many hobbyists and students have followed this approach when building for fun or for robot games competitions, and the basic principles are outlined in [14]. Under this design approach, one connects the sensors directly to the actuators, which bypasses the need for processing the information and results in purely reactive motions. This strategy has proved very robust and reliable for simple movements, especially for avoiding imminent collisions. However, one normally desires more efficient and directed motions in real applications.

In order to avoid obstacles in an efficient – although sub-optimal – manner while seeking a target, a reactive control strategy appears to make the most sense. A reactive strategy does not rely on formal path planning algorithms requiring precise and/or global knowledge of the environment. Many researchers have designed fuzzy-rule bases for choosing paths based on obstacle distance/direction, which is a an approach that typically results in reasonable real-time decisions; for a recent example, see [1] where additional physical constraints are imposed on the fuzzy rules to reduce reliance on heuristics. An automatic algorithm modifies the fuzzy rules in real-time in response to the environment in [17]. A neural-network structure encodes the fuzzy rules in order to provide adaptation (or learning) for static obstacles in [12] and dynamic obstacles in [6]. In order to achieve more complex navigation behaviours, maze-navigation and/or extraction from dead-ends, the fuzzy rules must be augmented with a memory of the environment, for example [15]. However, heuristic fuzzy techniques lack mathematical guarantees of success and/or stability, which is an important issue to address in this field of research.

The theory of nonlinear feedback control holds the potential for mathematical guarantees in navigation problems in the face of uncertainty. Usually, nonlinear feedback controls simply track a pre-determined path or trajectory, as in [13, 16, 4] and [19]. The method of artificial potential fields is similar to feedback control and decides the path itself; modifications allow the use of only local sensor information to implement this popular technique in [8]. Given good knowledge of the environment and a series of pre-designed local feedback controls that funnel into each other in a hybrid control approach called ‘sequential composition’, it is possible to successfully steer the robot around obstacles, as in [3] and [5]. This is also the case for the similar-in-concept vector-field method, such as in [7] and [11]. Using only local sensor information, a Lyapunov-stable control for unicycle navigation in [2] uses a heuristic algorithm to switch between stable target-tracking and stable obstacle avoidance feedback modes. Similarly, a border-following feedback control law allows general obstacle avoidance, with straight movements towards the target otherwise, as in [10]. In [18], a direct connection between the output and control signal achieves BEAM-style obstacle avoidance, while a linear-filter memory element used inside a Lyapunov-stable backstepping scheme provides smooth, rounded motions around obstacles while guaranteeing target-reaching in the absence of obstacles.

Our work follows on from that proposed in [18] due its simplicity, mathematical stability analysis, robust characteristics in the face of sensor noise, and reliability in avoiding collisions with obstacles. However, we find the method insufficient to navigate some environments successfully. Rather than rely on the BEAM-style control to avoid obstacles, we modify it by adding some small amount of fuzzy processing and call it a virtual force, which slows the robot and chooses a logical turning direction only in the event of imminent collision. Rather than rely on the memory with Lyapunov backstepping control – with the target position as the only input – to choose the direction of travel, we introduce some fuzzy processing to pick an intermediate target for the nonlinear control that avoids the closest obstacles. The addition of these two fuzzy processing levels creates a new, novel control method which results in improved trajectories and obstacle avoidance compared to [18]. However, the scheme is still computationally simple and remains robust in the face of limited and noisy sensor data. The robot ends up behaving in an insect-like manner, in the sense that it simply heads for gaps between obstacles that are close to the direction of the target. The algorithm allows the robot to head directly towards a sensed obstacle; for example, it may head towards a further obstacle at the other end of a gap between two closer obstacles.

Simulation results demonstrate the expected behaviour of the system in a corridor environment relying on a noisy, sweeping proximity sensor. We also try the control of [18] in the simulations, whereby we find that it fails to navigate this environment. Moreover, simulations reveal that eliminating any one of the three elements in the proposed control (fuzzy motion-planning, nonlinear control or virtual force) results in a failure to navigate this environment.

2. Overview

The proposed navigation strategy uses fuzzy logic to decide on both an intermediate target location provided as a reference input to a closed-loop control as well as a virtual obstacle force provided as a disturbance to the closed-loop control (Figure 1). First, a fuzzy processing operation outputs an intermediate target position ${\eta }_i$ (a vector with a distance and a relative angle) that creates a logical heading for the robot to follow, taking into account the target position, measured obstacle positions and obstacle positions in the immediate past. The nonlinear control then takes this information and provides commanded translational and rotational velocities, in vector u, based on its current position ${\eta }_u$ (relative to the ultimate target) and ${\eta }_i$ . Another fuzzy logic operation decides on the virtual force term, ${\nu }_f$ added directly to u, that reacts quickly to obstacles that might cause a collision if forward motion continues in the same direction. Note that the addition of the control-system and virtual force outputs constitute the real commanded velocities of the robot. The resulting behaviour consists of:

Figure 1.

Navigation strategy

• heading for a gap between obstacles, or towards an obstacle that is relatively far away, in a direction that is close to the target direction,

• making wide turns around obstacles so as to avoid collisions,

• suddenly slowing and turning if a collision appears imminent.

2.1. Robot Dynamics

The robot makes angle measurements to the target, ${\theta }_u$ , and obstacles relative to its own heading (Figure 2). Note that the information ends up stored in the fuzzy encoding using an absolute coordinate system denoted by ϕ with $\varphi =0$ aligned to a Cartesian X coordinate. The robot also measures the distance to the ultimate target, $d_u$ , and the vector describing the target position becomes:

Figure 2.

Coordinates: Dashed lines indicate the scanning range of the proximity (obstacle) sensor, another sensor provides a relative target location ${\theta }_u$ , and fuzzy motion-planning decides on an intermediate target relative angle ${\theta }_t$

${\eta }_u={\left[\begin{array}{cc}{d}_u& {\theta }_u\end{array}\right]}^T\mathrm{.}$

(1)

The fuzzy logic system will pick a direction that avoids immediate obstacles (but possibly heading towards a distant obstacle) by choosing an intermediate target position defined by:

${\eta }_i={\left[\begin{array}{cc}{d}_i& {\theta }_i\end{array}\right]}^T\mathrm{.}$

(2)

The relative coordinate is thus:

$\eta ={\left[\begin{array}{cc}{d}_t& {\theta }_t\end{array}\right]}^T\mathrm{,}$

(3)

where $d_t=d_i$ and:

${\theta }_t={\theta }_u-{\theta }_i\mathrm{.}$

(4)

Since the desired value of $\eta$ must be ${[0\hspace{0.17em}0]}^T$ , the error becomes:

$\mathbf{e}=\mathbf{0}-(\eta -N(t))=-\eta +N(t)$

(5)

where N is the sensor noise from measurements of $\eta$ . The control system outputs the desired (commanded) translational velocity v and rotational velocity ω:

$u={\left[\begin{array}{cc}v& \omega \end{array}\right]}^T\mathrm{.}$

(6)

The final commanded velocities include the virtual force term ${\nu }_f$ , directly added to the control signal:

$\nu =u+{\nu }_f\mathrm{.}$

(7)

We assume that the internal motor controllers achieve the velocities in $\nu$ in sufficient time such that the errors between the commanded and actual velocities remain insignificant; they are ignored in the navigation/control scheme developed here. Thus, in the computer simulations the only dynamics consist of:

$\stackrel{.}{\eta }=T(\eta )\nu \mathrm{,}$

(8)

where $T(\nu )=\left[\begin{array}{cc}-\cos ({\theta }_t)& 0\\ \frac{\sin ({\theta }_t)}{d_t}& 1\end{array}\right]\mathrm{.}$

2.2. Nonlinear Control

In the nonlinear control strategy, we first define a linear filter memory element that has error for the input. The key to achieving smooth motions is in designing a desired error that will cause the filter states to gradually go to zero. This is done with a Lyapunov backstepping procedure where the desired error is a virtual control in the first step of backstepping. A second step of backstepping results in the design of the velocities (the controls) to move the error towards its virtual control desired value.

2.2.1. Linear filter memory element

In order to reject noise and to have the robot move in a wide, rounded path, we use a linear time-invariant low pass filter to deal with the state errors e as an analogue memory element.

Using standard state space-form for the filter gives:

$\stackrel{.}{\zeta }(t)=A\zeta (t)+{\rm B}e(t)$

(9)

where the vector $\zeta$ contains the states of the filter, with the first state being the output $y={\zeta }_1$ . The control achieves smooth and wide trajectories by trying to reduce filter states $\zeta$ to zero as opposed to trying to reduce $e(t)$ directly.

2.2.2. Lyapunov backstepping, step 1

Since the state equations appear in strict-feedback form:

$\stackrel{.}{\zeta }(t)=A\zeta (t)+B[-\eta (t)+N(t)]\mathrm{,}$

(10)

$\stackrel{.}{\eta }(t)=T(\eta )u\mathrm{,}$

(11)

the Lyapunov backstepping technique provides a suitable nonlinear control strategy. The first step of backstepping uses the positive-definite function:

$V_1={\zeta }^{T}P\zeta \mathrm{,}$

(12)

where $V_1$ is a scalar-valued function and P is a symmetric positive definite matrix which satisfies $A^{T}P+PA=-Q$ where Q is a positive-definite matrix. Taking the time-derivative results in:

${\stackrel{.}{V}}_1=-{\zeta }^{T}Q\zeta +2{\zeta }^{T}PB(-\eta +N)\mathrm{.}$

(13)

The backstepping error is:

$z=\eta -{\eta }_d\mathrm{,}$

(14)

where ${\eta }_d$ is the virtual control, a desired value of $\eta$ . Thus:

${\stackrel{.}{V}}_1=-{\zeta }^{T}Q\zeta +2{\zeta }^{T}PB(-z-{\eta }_d+N)\mathrm{,}$

(15)

leads to a choice of virtual control:

${\eta }_d=B^{T}P{K}_1\zeta +R\tanh (S{B}^{T}P\zeta )\mathrm{,}$

(16)

where $K_1$ , R and S are all diagonal matrices with positive constant terms on the diagonals (note $P^T=P$ ). The function $\tanh ()\in {ℛ}^2$ performs an element-by-element hyperbolic tangent operation and provides robustness to noise when choosing $R_{i\mathrm{,}i}>|N_i{|}_{\max }$ for $i=\mathrm{1,2}$ . Positive constants in S determine the steepness of the hyperbolic tangent, used in place of a discontinuous robust control so that the signal may be differentiated. Therefore, (15) becomes:

$\begin{array}{l}{\stackrel{.}{V}}_1=-{\zeta }^{T}Q\zeta -2{\zeta }^{T}PB{B}^{T}P{K}_1\zeta -2{\zeta }^{T}PBz\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+2{\zeta }^{T}PB\left[-R\tanh (S{B}^{T}P\zeta )+N\right]\mathrm{.}\end{array}$

(17)

2.2.3. Lyapunov backstepping, step 2

In the second step of backstepping, the control Lyapunov function becomes:

$V=V_1+z^{T}z\mathrm{.}$

(18)

Differentiating (18) with respect to time gives:

$\stackrel{.}{V}={\stackrel{.}{V}}_1+2z^T\stackrel{.}{z}$

(19)

$={\stackrel{.}{V}}_1+2{\mathbf{z}}^T(\stackrel{.}{\eta }-{\stackrel{.}{\eta }}_d)$

(20)

$={\stackrel{.}{V}}_1+2z^T(T(\eta )u-{\stackrel{.}{\eta }}_d)$

(21)

$\begin{array}{l}=-{\zeta }^{T}Q\zeta -2{\zeta }^{T}PB{B}^{T}P{K}_1\zeta -2{\zeta }^{T}PBz+\hfill \\ 2{\zeta }^{T}PB\left[-R\tanh (S{B}^{T}P\zeta )+N\right]+\hfill \\ 2z^T(T(\eta )u-{\stackrel{.}{\eta }}_d)\mathrm{.}\hfill \end{array}$

(22)

A nonlinear control that would ensure a negative-definite $\stackrel{.}{V}$ under noise-free conditions is:

$u=\left[\begin{array}{c}v\\ \omega \end{array}\right]=T{(\eta )}^{-1}(B^{T}P\zeta +{\stackrel{.}{\eta }}_d-K_{2}z)\mathrm{,}$

(23)

where $K_2$ has positive constant control gains on the diagonals. Note that ${\stackrel{.}{\eta }}_d$ must be calculated analytically:

${\stackrel{.}{\eta }}_d=\frac{\partial {\eta }_d}{\partial \zeta }\stackrel{.}{\zeta }$

(24)

$=g(K_1{B}^{T}P+RS{B}^{T}P[1-{\text{tanh}}^2(S{B}^{T}P\zeta )]g)\stackrel{.}{\zeta }\mathrm{.}$

(25)

Substituting (23) into (22), the derivative of the control Lyapunov function becomes:

$\begin{array}{l}\stackrel{.}{V}=-{\zeta }^{T}Q\zeta -2K_1{\zeta }^{T}PB{B}^{T}P{K}_1\zeta \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}2{\zeta }^{T}PB[-R\tanh (S{B}^{T}P\zeta )+N]-2z^T{K}_{2}z\mathrm{.}\end{array}$

(26)

To analyse stability, first bind the time derivative:

$\begin{array}{l}\stackrel{.}{V}\le -{\lambda }_{\min }(Q){\Vert \zeta \Vert }^2-2{\lambda }_{\min }(K_2){\Vert z\Vert }^2\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+2\Vert {\zeta }^{T}PB\Vert \left[-\Vert R\tanh (S{B}^{T}P\zeta )\Vert +\Vert N\Vert \right]\mathrm{,}\end{array}$

(27)

where ${\lambda }_{\min }()$ denotes the minimum eigenvalues of the symmetric matrices. Thus, $\stackrel{.}{V}<0$ when:

$|{\zeta }_i|>\frac{{\tanh }^{-1}(N_i/R_{i\mathrm{,}i})}{{(S{B}^{T}P)}_i}\text{for}\hspace{0.17em}\text{both}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}i=\mathrm{1,2,}$

(28)

and by standard arguments all signals are uniformly ultimately bounded. When there is no noise, $N(t)=0$ , the time derivative is negative definite and the origin is asymptotically stable ( $\zeta \to 0$ as $t\to \infty$ ).

2.3. Fuzzy Environment Encoding

The fuzzy encoding of the environment utilizes an absolute polar coordinate system, requiring conversion of the relative angle and distance measurements from the sensors. The proximity sensor outputs (after coordinate transformation) M equally-spaced angles ${\varphi }_i\mathrm{,}\hspace{0.17em}i=1\dots M$ in the current sweeping arc of the sensor between ${\varphi }_{\min }(t)$ and ${\varphi }_{\max }(t)$ , each with a distance reading $d_i({\varphi }_i)$ (or equivalently ${\eta }_i=[d_i\hspace{0.17em}{\varphi }_i{]}^T$ ). We provide the fuzzy encoding system with a normalized distance ${\bar{d}}_i=d_i/d_{\max }$ , where $d_{\max }$ is the maximum sensor range, interpreting each ${\bar{d}}_i$ as a fuzzy truth-value of FAR=“The obstacle is far”. When no obstacle is detected at ${\varphi }_i$ , then ${\bar{d}}_i=1$ . Obtaining a continuous, filtered output defining FAR for all angles between 0 and ${360}^{\circ }$ , we encode the information using m weighted Gaussian fuzzy membership functions of the form:

Figure 3.

Inner structure of the control system: first is a linear filter used as memory, followed by nonlinear backstepping control

${\mathrm{\Gamma }}_j({\varphi }_i)=\exp ((-{\varphi }_i-c_j{)}^2/{\sigma }^2)\hspace{0.17em}\hspace{0.17em}\text{for}\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}j=1\dots m$

(29)

where σ is a positive constant. The centres are evenly distributed with $c_j=360j/m$ . Expressing the truth-value of “The obstacle is far” as a function of an input ${\varphi }_i$ , we write:

$\mathrm{F}\mathrm{A}\mathrm{R}={\displaystyle \sum _{j=1}^m}{w}_j{\mathrm{\Gamma }}_j({\varphi }_i)\mathrm{.}$

(30)

The algorithm continuously updates, in real-time, each weighting $w_j$ by sweeping ϕ from 0 to ${360}^{\circ }$ in M steps, and at each step applying the update $w_j=w_j+\mathrm{\Delta }{w}_j$ where:

$\mathrm{\Delta }{w}_j=\{\begin{array}{cc}\beta ({\bar{d}}_i-\mathrm{F}\mathrm{A}\mathrm{R})& \text{if}\hspace{0.17em}{\varphi }_{\min }(t)<{\varphi }_i<{\varphi }_{\max }(t)\mathrm{,}\\ -\gamma w_j& \text{otherwise}\mathrm{,}\end{array}$

(31)

and where β is a positive learning rate and γ is a positive forgetting factor. Inside the sensor range, the Gaussian functions serve to filter the proximity-sensor data. Obstacles previously in sensor range remain in memory for some time in order that they can be taken into account in the motion planning algorithm. Once enough time has passed, these disappear from the memory such that γ should depend upon the speed of the robot.

The fuzzy encoding of the target heading utilizes a Gaussian function, with a value of 1 where the sensors locate the target at a given moment and a value approaching 0 at $\pm {360}^{\circ }$ .

2.4. Decision on the Intermediate Target

The choice of desired heading depends, first, on the peaks (maxima) of the fuzzy obstacle encoding, FAR, being identified. The peaks then represent possible headings for the robot, i.e., the angular component of possible intermediate targets. A value greater than 1 at the peak (FAR $>1$ ) means that no obstacle is within sensor range in that direction, while FAR $<1$ indicates the relative distance to the obstacle in that direction. FAR $=0$ would imply contact with the obstacle. Note that even though all values less than 1 represent possible obstacles, the choice of heading does not directly take obstacles into account (although these obstacles will be used in producing virtual forces). Possible headings might be in the same direction as obstacles but directed towards an obstacle relatively far away compared to other obstacles. The choice of intermediate target direction utilizes the fuzzy rule:

• If the possible heading is CLOSE to the target direction AND an obstacle in that direction is FAR, then in it is DESIRED

which is computed at the k th peak of FAR as:

${\text{DESIRED}}_k=|{\varphi }_k-{\varphi }_{\text{target}}|\times \text{FAR}({\varphi }_k)\mathrm{.}$

(32)

The new desired heading becomes the one with the largest value of DESIRED. Note that the intermediate target depends upon time for both the angle and the distance. The angle changes continuously with the robot's motion as obstacles are perceived at different angles, and the angle may change discontinuously at any time if a different peak moves closer to the target. The distance to the intermediate target simply becomes the maximum sensor range when no obstacles are detected that way or else a fraction of the way to the obstacle given an obstacle in that direction. Specifically, in the simulations, when FAR $<1$ in the direction of the desired heading, the vehicle is commanded to go 80% of the way to the obstacle.

2.5. Producing Virtual Force

The virtual force term directly augments the commanded velocities from the control, appearing as a disturbance in the feedback control loop. In this way, the robot reacts directly to an impending obstacle analogous to the way in which BEAM strategies manoeuvre The fuzzy encoding of the environment provides a convenient way to instantly decide whether the robot should move left or right, and by how much, in order to avoid the obstacle. It also decides how much it should slow down. The fuzzy rules for producing the virtual force in the direction are made by looking at the value of FAR. The algorithm looks to the left and right of the current heading in FAR and identifies the nearest obstacle (where FAR $<1$ ) to both the left and the right. The fuzzy rule base is:

1. If an obstacle is NEAR, then the translational velocity moves SLOWER,

2. If an obstacle is to the LEFT AND NEAR, then the angular velocity moves NEGATIVE,

3. If an obstacle is to the RIGHT AND NEAR, then the angular velocity moves POSITIVE,

where:

$\mathrm{N}\mathrm{E}\mathrm{A}\mathrm{R}=\{\begin{array}{ll}1-\mathrm{F}\mathrm{A}\mathrm{R}\hfill & \text{if}\hspace{0.17em}\text{FAR}<1\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$

(33)

The fuzzy logic utilizes constants s and c to determine SLOWER, NEGATIVE and POSITIVE, calculated by:

${\nu }_f=\left[\begin{array}{c}\mathrm{\Delta }v\\ \mathrm{\Delta }\omega \end{array}\right]=\left[\begin{array}{ccc}-s& 0& 0\\ 0& -c& c\end{array}\right]\left[\begin{array}{c}\text{NEAR}\\ |{\varphi }_h-{\varphi }_{\text{left}}|\times \text{NEAR}\\ |{\varphi }_h-{\varphi }_{\text{right}}|\times \text{NEAR}\end{array}\right]$

(34)

where ${\varphi }_h$ is the current heading and ${\varphi }_{\mathrm{l}eft}\mathrm{,}{\varphi }_{\mathrm{r}ight}$ are the closest angles, in positive and negative angle directions, respectively, where FAR $<1$ .

3. Simulation Results

In the simulation, the robot attempts to traverse a 200 cm by 200 cm environment with corridors starting in the bottom-right corner with the ultimate target at the top left (Figure 4). The robot knows where the target is in relation to its heading and has a (noisy) view of obstacles $\pm {90}^{\circ }$ from its heading up to a range of 25 cm in the Cartesian coordinates. The nominal (maximum) speed of the robot is 7 cm/s (1 unit/s in the graphs). The thick dashes on the Cartesian environment plot represent the position and orientation of the robot at each second.

Figure 4.

Cartesian path and robot orientation for 19 seconds. The red circles indicate current and past obstacle-sensor readings (the sensor range can be inferred.

Noise appears in both the obstacle (proximity) sensor and target sensor signals. The fuzzy encoding memory filters the proximity sensor noise while the linear filter and the robust nonlinear control handle the target sensor noise. The obstacle sensor model obtains a distance to the obstacle, $d_{\text{measured}}$ [at angle $\varphi (t)$ ], which is a random number for a certain proportion of the time and the correct reading for other times. Formally:

$d_{\text{measured}}(\varphi (t))=(\begin{array}{ll}{d}_{\text{max}}(\varphi (t))(1-\mathrm{rand}(1))\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}\text{rand}(1)<r\hfill \\ d_{\text{actual}}(\varphi (t))\hfill & \text{otherwise}\mathrm{,}\hfill \end{array}$

(35)

where $d_{\max }$ is the maximum sensor range and function rand(1) produces a random number between 0 and 1, and where a positive constant r between 0 and 1 determines the noise level. For the simulations, we use a nominal value of $r=0.2$ . The target sensor output displays significant noise, giving angle readings within $\pm {40}^{\circ }$ of the real target angle:

${\theta }_{u\mathrm{,}\text{measured}}={\theta }_{u\mathrm{,}\text{actual}}+80\cdot [0.5-\text{rand}(1)]\hspace{0.17em}\hspace{0.17em}\text{[deg]}\mathrm{.}$

(36)

We assume that the maximum orientation error is known and use $N_{\max }{=40}^{\circ }$ in the robust control, choosing the following parameters:

$\begin{array}{c}Q=\text{diag}(\mathrm{1,1})\mathrm{,}\\ K_1=\text{diag}(\mathrm{0.65,5})\mathrm{,}\hspace{0.17em}\hspace{0.17em}{K}_2=\text{diag}(\mathrm{0.65,5})\mathrm{,}\\ R=\text{diag}(\mathrm{0.1,50})\mathrm{,}\hspace{0.17em}\hspace{0.17em}S=\text{diag}(\mathrm{1,1})\mathrm{.}\end{array}$

Note that as the noise appears in the angle measurement only, it is only the second diagonal element of R that provides robustness to noise. In our work, we found $c=500$ deg/s and $s=2$ m/s to be suitable values in (34). For the linear filter memory, we use a simple low pass filter:

$\frac{{\zeta }_1(s)}{e(s)}=\frac{{\omega }_f}{s^2+2{\zeta }_f{\omega }_{f}s+{\omega }_f^2}$

(37)

with ${\omega }_f=1.6$ Hz and ${\zeta }_f=0.7$ .

The robot starts out at an initial heading of $0^{\circ }$ , directly facing the right-hand wall and facing away from the target. For the first two seconds, the robot turns back and forth as it attempts to find an obstacle-free heading (Figure 4 bottom right). Inspecting the simulation 19 seconds after the start (Figure 5) reveals typical robot decision-making during the manoeuvre. At this point in time, the robot faces ${90}^{\circ }$ in absolute coordinates (Figure 5 bottom graph, green line), while the ultimate target appears at ${155}^{\circ }$ absolute angle (Figure 5 top graph), thus making the relative target heading (error) ${65}^{\circ }$ . The range-finder sensor sweeps ${90}^{\circ }$ to either side of the heading, $0^{\circ }$ to ${180}^{\circ }$ in absolute coordinates, with noise clearly visible in the sensor readings (Figure 5 middle graph).

Figure 5.

Encoding and decision-making at $t=19$ – made when the robot heading is $\varphi {=90}^{\circ }$

At 19 seconds, the robot also senses the wall directly ahead of it and makes a decision to put the intermediate target at ${140}^{\circ }$ (Figure 5 bottom graph, red line), thus making a left turn of $+{50}^{\circ }$ from the current heading. Even though the robot sees an obstacle-free direction to its right between ${85}^{\circ }$ to ${35}^{\circ }$ in absolute coordinates (Figure 5 bottom graph, solid curve), it chooses a heading to its left since the obstacle remains relatively far away and this heading appears closer to the ultimate target position.

In another simulation, the random noise affects decision-making and results in a slightly different path (Figure 6a). However, at approximately the same point in space where the previous simulation ended, it makes the same decision – in this case, to turn left.

Figure 6.

Complete simulations

Figure 7.

Other controls: Green (on left) Control 1, Red (crashes into wall) Control 2, Black (on right) Control 3

Tracking the commanded velocities from the motion-planning and the velocities from the virtual force term (Figure 6b) reveals that at the 17 second mark, when faced with a similar decision as in Figure 4, the virtual force command for a negative angular velocity (a right turn) was “overruled” by the motion-planning. The virtual force slows the robot and tries to direct the robot to the obstacle-free direction (to the right), but the fuzzy motion planning has a stronger command with a larger commanded positive angular velocity (to the left), thereby seeing a possible heading more aligned with the ultimate target direction.

In a third simulation, when faced with a similar decision, the robot – this time – moved to the right (Figure 6c). The effects of random sensor noise on the system have slightly altered the particular circumstances compared to the previous occasion. This time, the robot virtual force term slightly outweighs the fuzzy motion planning at the 19 second mark (Figure 6d) and the robot turns to the right. After turning, the fuzzy motion-planning identifies a new possible heading and does not try to turn around. The virtual force term again interferes in the motion at the 27 second mark, slowing and turning the robot away from the wall on the right when the motion planning appears to command a turn towards the wall.

In a fourth simulation, the robot starts at a slightly different location – to the left – and it ends up taking a completely different path (Figure 6e). In this simulation, the virtual force term helps the robot avoid a corner at the 24 second mark (Figure 6f). It causes the robot to turn to the right to avoid the corner, even though the motion planning commands a left turn. In a real robot, this type of behaviour should eliminate the chance that the machine would try to move too close to a corner and thus make contact with the extrusion due to the robot's width.

Table 1.

Summary of results

Sim.	Min. Distance (cm)	Time (s)	Min. Curvature (cm)
2nd	5.4	43	4.3
3rd	4.2	45	6.4
4th	4.4	38	5.3

In all cases, the nonlinear control provides a smooth motion except for when the virtual force terms affect the system and provide quick responses. Table 2 summarizes the results in terms of the minimum distance to a wall, the total time and the minimum radius of the curvature of the trajectory. Note that the nonlinear control provides most of the changes in heading; for example, as seen in Figure 6f, between nine and 13 seconds. Here, the intermediate target position does not change significantly, remaining at approximately ${140}^{\circ }$ , yet the nonlinear control causes a smooth, rounded right-turn around the corner to the right (Figure 6e first corner), with no input from the virtual force term needed.

Table 2.

Robustness to noise

r	<0.5	0.5	0.55	>0.55
Success rate	100%	75%	25%	0%

To show the necessity of the each component in each of the controls, we test three different alternative methods:

1. Using the same virtual force and backstepping control, but no motion planning – only aiming for the ultimate target which reflects the control proposed in [18] (green dash, nearly hitting wall on left, Figure 7),

2. Using the same motion planning and memory/backstepping control, but without any virtual force term (red dash, hitting wall, Figure 7),

3. Using the same motion planning and virtual force, but without memory/backstepping control – instead using $u=T^{-1}(\eta )(-e)$ (black dash, nearly hitting wall on right, Figure 7.)

Although the virtual force term keeps the system from actually touching the wall in Controls 1 and 3, the robot does come very close and ends up having to reverse direction. The previous method proposed in the literature – Control 1, which uses just the ultimate target without planning any intermediate targets – relies too heavily on the BEAM-like virtual force to make an effective navigation strategy. Control 2, without virtual force, ends up driving directly into a wall. Control 3, without backstepping, does not give the corner enough room to get by safely.

In order to test the necessity of the robust virtual control term [with $\tanh ()$ ], another control, Control 4, eliminates the robust term (as the only change):

${\eta }_d=K_1{B}^{T}P\zeta \mathrm{.}$

(38)

This affects only the angle-control in the simulation, since the robust term accounts only for noisy ${\theta }_t$ (not noise-free $d_t$ ). The results show that the robot is easily confused by obstacles and cannot always find the obstacle-free path (Figure 8 top right), and also that it tends to wander back and forth in its movements when it should be following a nearly-straight line in a long corridor.

Figure 8.

Control without $\tanh ()$ as the robust control term (Control 4)

Finally, we test the robustness to noise by varying the noise-level parameter r from (35). The simulation was attempted eight times at each level of r, and r was changed by 0.05 each time. The simulations had 100% success rate, as defined in terms of reaching the target without hitting a wall, when using a noise level below $r<0.5$ . The results appear in Table 2.

4. Conclusion

This paper proposes a reactive-navigation strategy for a mobile robot, suitable for implementation on a robot with limited computational power. The strategy relies on knowledge of the ultimate target location and local knowledge of obstacles provided by a sweeping, forward-looking proximity sensor. A fuzzy motion-planning algorithm plans an intermediate target between obstacles for the control system to track. A Gaussian fuzzy-encoding of the environment serves to filter sensor noise and provide a basis for choosing a heading. A nonlinear Lyapunov backstepping control system with a linear filter element provides robustness to noise in the control system itself, resulting in a wide path around obstacles. A collision avoidance strategy, implemented with a BEAM-style virtual force term, directly augments the commanded velocities in order to react immediately to any impending obstacles – both slowing and turning in a logical direction. The advantages over computationally-complex approaches, include suitability for small mobile robots, immediate decision-making, continuous motion in a complex environment, reasonable choices in the face of environmental uncertainty from limited sensors, smooth motion in the face of noisy sensors, and immediate reactions in the face of imminent collisions. Unlike as with computationally simple BEAM control, the robot follows a smooth path when possible and can immediately head for a space between sensed obstacles.

To evaluate the performance of the control system, computer simulations in a corridor environment were conducted with noisy sensor data. The results show that the control system provides robustness to noise and can successfully give obstacles/walls a wide clearance while maintaining a reasonable speed. The robot navigates an unknown static environment (lacking dead-ends, traps and moving obstacles) while avoiding obstacles/walls and arriving at the desired location successfully.