Leader-Follower Formation for Nonholonomic Mobile Robots: Discrete-Time Approach

Abstract

This paper presents a novel solution for the classical leader-follower formation problem considering the case of nonholonomic mobile robots. A formation control strategy is proposed in a discrete-time context by considering the exact discrete-time discretization of the non-linear continuous-time kinematic model of the vehicle. The geometric formation of the robots allows us to derive an alternative model that describes the time evolution of the relative distance and angle between the robots. These variables are obtained in real-time by a vision-based localization system on board, in which the follower robot is equipped with a Kinect device, together with a recognition board mounted on the leader robot. The boundedness of the relative position error is formally proven by considering a feedback law that is delayed by one sampling period of time. Numerical simulations and real-time experiments are presented to verify the performance of the control strategy.

1. Introduction

The formation and cooperation of mobile robots are found in different fields: for example, in the aerial environment for navigation, exploration tasks, recognition of hostile terrain, aerial photography, terrain mapping or in the search and capture of ground targets [1, 2]. They are also considered for tracking and obstacle avoidance, patrolling an environment to prevent intruders in arbitrary topologies, 3D mapping, archaeological exploration and terrain recognition [3, 4]. In general, in order to perform such tasks, it is necessary to have a measuring device on board as in [5], where encoders and a compass on board are used to maintain the formation. In some cases, multiple devices are required to accomplish recognition of the environment: usually a laser system or a video camera [6, 7]. A special case is the detection of a leader robot or a particular pattern mounted on the robot [8].

The leader-follower formation problem has been analysed by considering several control strategies, mainly by means of the feedback linearization approach [9–13]. In [9], an on-board camera is used to estimate the orientation and the distance between the robots, and in [11], three different controllers are proposed and a camera is used for measuring the distance and angles between the vehicles, verifying the controller's performance by numerical simulation. Lyapunov-based control strategies have also been considered; for instance, in [14], two different controls are proposed using a camera fixed to the ceiling, while in [5, 15], the strategy is complemented by a receding horizon approach together with a single camera mounted on the ceiling. In addition, backstepping strategies have been implemented in the solution of the leader-follower problem; for example, in [16], the leader-follower formation is assured using Cartesian coordinates to avoid singularities that appear in polar coordinates. Backstepping and cascade system theory is used in [17] to control multiple robots and in [18], the method is complemented by a bioinspired dynamic to avoid impractical velocity jumps. The backstepping is merged with a fuzzy control strategy in [19] to perform an obstacle avoidance strategy. Game theory is used in [4] for terrain patrolling tasks, modelling the problem as a set of two players developing an optimal strategy for the solution of the problem. In [20], the leader-follower formation is analysed by measuring the relative distance between the vehicles from a mobile frame located on the follower robot, which is allowed to adopt a variable position under an input-constraints strategy.

One important aspect of the problem is the real-time implementation of the mentioned solutions. In this sense, there are two main approaches. The first one is based on a camera mounted on the ceiling of the working space as in [5] or [15], and the more general approach that considers an on-board camera used to estimate the orientation and the distance between the robots as in [9] and [21], in which observer-based solutions are proposed. In [22], the solution is based on an entropy segmentation that provides the relative-position estimation of the robots.

The objective of this paper is to analyse the leader-follower formation problem using a discrete-time approach: an approach that has not been considered in the literature. The consideration of a discrete-time strategy is based on the necessity of a practical implementation of the solution of the leader-follower problem stated in this work, which should be carried out, in general, by means of microprocessors or computer-based platforms. In addition, the discrete-time nature of the vision system seems to be more suitable for the approach proposed. In particular, a leader-follower formation based on relative distances between the robots is suitable for outdoor environments where an absolute localization system is difficult to implement. An exact discretization strategy based on direct integration, such as the one used in [23], is considered here.

The control of nonholonomic mobile robots of the type considered in this work is a challenging problem due to the fact that they do not satisfy the well-known Brocket's rank condition [24], which prevents the existence of a smooth time-invariant feedback for the solution of the stabilization problem. This problem is related to the control of the vehicle's posture. The standard formation problem is addressed in a discrete-time context assuming that the leader robot follows a free trajectory; it is intended that the follower robot tracks the leader within a specified distance using only a camera on board as a sensor. In this form, the solution does not depend on positions and velocities measurements, and only considers relative measurements between vehicles. To solve this problem, and following [16], a coordinate transformation is considered in which the relative time evolution of the position and angle between the robots is used.

Instead of a standard video camera, a Kinect device is used to estimate the relative distance and the angle between the leader and the follower robot. The solution of the problem is based on a non-standard discrete-time feedback that is retarded by one sampling period of time, which produces a closed-loop perturbed system. It is formally proven that the follower tracks the leader by using bounded tracking errors. The proposed formation strategy is evaluated by numerical simulation as well as real-time experiments by means of two differentially driven mobile robots.

The rest of the work is organized as follows. Section 2 describes the discretization procedure and the mathematical preliminaries that are used throughout the document. In Section 3, the leader-follower formation problem is geometrically stated and the control objective based on the relative errors is described. In Section 4, the solution to the leader-follower formation problem (the formation-error analysis and the main procedure to obtain the control law) is shown. The numerical and experimental evaluation of the proposed formation strategy is described in Section 5 and some conclusions are given in Section 6.

2. Discrete-time Model of the Mobile Robots

A differentially driven mobile robot (type (2.0)), such as the one depicted in Figure 1, is considered. The kinematic model of this robot is given by [25],

Figure 1.

Representation of a mobile robot (2,0) in the plane

$\begin{array}{l}\stackrel{·}{x}=V\text{cos}(\theta )\\ \stackrel{·}{y}=V\text{sin}(\theta )\\ \stackrel{·}{\theta }=W\end{array}$

(1)

where x and y are the positions along the axes X and Y, respectively, and θ corresponds to the orientation angle of the vehicle. V and W are the linear and angular velocities of the robot.

The kinematic evolution of the point α, located at the front of the robot along the longitudinal axis, can be described by considering the changes to the following coordinates,

$\begin{array}{l}{\alpha }_x=x+l\text{cos}(\theta )\\ {\alpha }_y=y+l\text{sin}(\theta )\\ {\alpha }_{\theta }=\theta \end{array}$

(2)

where $l>0$ is the constant distance between point P and α. In these coordinates, the kinematic model of the mobile robot takes the form,

$\begin{array}{l}{\stackrel{·}{\alpha }}_x=V\text{cos}({\alpha }_{\theta })-lW\text{sin}({\alpha }_{\theta })\\ {\stackrel{·}{\alpha }}_y=V\text{sin}({\alpha }_{\theta })+lW\text{cos}({\alpha }_{\theta })\\ {\stackrel{·}{\alpha }}_{\theta }=W.\end{array}$

(3)

The linear and angular velocities of each robot are related to the angular velocity of the right wheel, w_r, and the angular velocity of the left wheel, w_l, by means of the relation,

$\left[\begin{array}{c}{w}_r(t)\\ w_l(t)\end{array}\right]=\frac{1}{r}\left[\begin{array}{cc}1& m\\ 1& -m\end{array}\right]\left[\begin{array}{c}V(t)\\ W(t)\end{array}\right]$

(4)

where r is the wheel ratio and $2m$ is the distance between the wheels. This transformation is non-singular for all r, $m>0$ .

The control of nonholonomic mobile robots of the type considered in this work is a challenging problem due to the fact that they do not satisfy the well-known Brocket's rank condition [24], which prevents the existence of a smooth time-invariant feedback for the solution of the stabilization problem. The use of Lyapunov techniques has provided solutions for a single robot by means of discontinuous feedback [26] or by means of time-varying control laws [27, 28]. Instead of considering the posture of the vehicle, in this work, controlling the Cartesian coordinates of the point α was preferred, while obtaining simultaneously the boundedness of the orientation angle.

2.1. Exact discrete-time representation

Taking into account the discrete-time nature of a real time implementation, an exact discrete-time representation of the kinematic equations (3) is considered. The non-linear kinematic model (3) can be discretized in an exact manner by considering a sampling period $T>0$ , a time interval $t_k=\left\{t\in \left[kT\mathrm{,}kT+T\right)\right\}$ with $k=\mathrm{0,1,2,\dots }$ , and assuming that the control signals between the time intervals t_k are constant, this is, $v\left(t\right)=v\left(kT\right)$ , $w\left(t\right)=w\left(kT\right)$ , $\forall t\in \left[kT\mathrm{,}kT+T\right)$ . For the sake of simplicity, the compact notation ${\zeta }^{\pm n}=\zeta \left(kT\pm nT\right)$ , ${\zeta }^{\pm }=\zeta \left(kT\pm T\right)$ and ${\zeta }^0=\zeta$ for any positive integer n, is considered in all the subsequent developments.

Following [23], the time integration of the dynamics (3), with the initial condition evaluated at $t=kT$ and the final condition $t=kT+T$ , allows us to obtain the discrete-time representation for both the leader ( $i=L$ ) and follower ( $i=F$ ) robot in the form,

$\left[\begin{array}{c}{\alpha }_{xi}^{+}\\ {\alpha }_{yi}^{+}\\ {\alpha }_{\theta i}^{+}\end{array}\right]=\left[\begin{array}{c}{\alpha }_{xi}\\ {\alpha }_{yi}\\ {\alpha }_{\theta i}\end{array}\right]+T{\psi }_i(W_i)\left[\begin{array}{cc}\text{cos}({\gamma }_i)& -l\text{sin}({\gamma }_i)\\ \text{sin}({\gamma }_i)& l\text{cos}({\gamma }_i)\\ 0& \frac{1}{{\psi }_i(W_i)}\end{array}\right]\left[\begin{array}{c}{V}_i\\ W_i\end{array}\right]$

(5)

where ${\psi }_i(W_i)=\frac{\text{sin}\left(\frac{T}{2}{W}_i\right)}{\frac{T}{2}{W}_i}$ and ${\gamma }_i={\alpha }_{\theta i}+\frac{T}{2}{W}_i$ .

Remark 1 It should be noted that ${\psi }_i(W_i)$ is a well-defined function of W_i and, in particular, of ${{\displaystyle \text{lim}}}_{W_i\to 0}{\psi }_i(W_i)=1$ . In addition, note that model (5) depends directly on the sampling period T and, thus, the consideration of different values of this variable does not affect the properties of the model.

In addition to (5), the following output signals are considered:

$y_i=\left[\begin{array}{c}{y}_{i1}\\ y_{i2}\end{array}\right]=\left[\begin{array}{c}{\alpha }_{i1}\\ {\alpha }_{i2}\end{array}\right]\mathrm{.}$

(6)

Model (5)–(6) is used in the sequel to study a leader-follower formation problem.

3. Leader-follower Formation Problem

The configuration of a leader-follower formation is shown in Figure 2. The complexity of this formation is due to the difficulty of measuring the different relative positions and velocities that exist between the leader and the follower robot. The problem can be stated as follows.

Figure 2.

Representation of the leader-follower formation of mobile robots type (2,0) in the plane

Control objective Suppose that the leader robot follows a free path that is subject to the nonholonomic restrictions of the vehicle. The objective of the leader-follower formation is that the follower robot tracks the leader robot while maintaining a constant distance ${\bar{l}}_0$ . With respect to Figure 2, it is necessary to design a feedback law such that,

$\underset{k\to \infty }{{\displaystyle \text{lim}}}{l}_0(kT)={\bar{l}}_0\in R\mathrm{.}$

(7)

Remark 2 Model (5) considers the evolution of the frontal point α described by (2). In fact, since the leader robot has a free displacement in the working space; thus, it may not be necessary to consider model (5) in order to describe its dynamics (for example, a different discrete-time dynamic model obtained from (1) could be used). Here, model (5) is considered for the sake of simplicity of notation in the subsequent developments.

From Figure 2, it is possible to obtain the geometrical relationship between the leader and the follower robot. Note first that the distance l₀ between the points $({\alpha }_{x_F}\mathrm{,}{\alpha }_{y_F})$ and $({\alpha }_{x_L}\mathrm{,}{\alpha }_{y_L})$ can be decomposed on the local Cartesian components l_x, l_y that describe the position of the point $({\alpha }_{x_F}\mathrm{,}{\alpha }_{y_F})$ with respect to the moving frame $X^m-Y^m$ located at the point $({\alpha }_{x_L}\mathrm{,}{\alpha }_{y_L})$ of the leader robot. With respect to the fixed frame $X-Y$ , the distances l_x and l_y can be written as:

$\begin{array}{l}{l}_x=-({\alpha }_{x_L}-{\alpha }_{x_F})\text{cos}{\alpha }_{{\theta }_L}-({\alpha }_{y_L}-{\alpha }_{y_F})\text{sin}{\alpha }_{{\theta }_L}\\ l_y=({\alpha }_{x_L}-{\alpha }_{x_F})\text{sin}{\alpha }_{{\theta }_L}-({\alpha }_{y_L}-{\alpha }_{y_F})\text{cos}{\alpha }_{{\theta }_L}\mathrm{.}\end{array}$

(8)

It is clear that the control objective (7) can be rewritten in terms of the evolution of l_x and l_y. That is, it is required that, ${{\displaystyle \text{lim}}}_{k\to \infty }{l}_x(kT)={\bar{l}}_x$ , ${{\displaystyle \text{lim}}}_{k\to \infty }{l}_y(kT)={\bar{l}}_y$ , for ${\bar{l}}_x\mathrm{,}{\bar{l}}_y\in R$ , such that, ${\bar{l}}_x^2+{\bar{l}}_y^2={\bar{l}}_0^2$ .

The time evolution of l_x and l_y can be obtained by considering a direct forward shift of equation (8), this is:

$l_x^{+}=-\left[{\alpha }_{x_L}^{+}-{\alpha }_{x_F}^{+}\right]\text{cos}{\alpha }_{{\theta }_L}^{+}-\left[{\alpha }_{y_L}^{+}-{\alpha }_{y_F}^{+}\right]\text{sin}{\alpha }_{{\theta }_L}^{+}$

(9)

$l_y^{+}=\left[{\alpha }_{x_L}^{+}-{\alpha }_{x_F}^{+}\right]\text{sin}{\alpha }_{{\theta }_L}^{+}-\left[{\alpha }_{y_L}^{+}-{\alpha }_{y_F}^{+}\right]\text{cos}{\alpha }_{{\theta }_L}^{+}\mathrm{.}$

(10)

Substituting ${\alpha }_{x_L}^{+}$ , ${\alpha }_{x_F}^{+}$ , ${\alpha }_{y_L}^{+}$ , ${\alpha }_{y_F}^{+}$ and ${\alpha }_{{\theta }_L}^{+}$ from equation (5) into (9), leads to:

$\begin{array}{l}{l}_x^{+}=-[{\alpha }_{x_L}+T{V}_L{\psi }_L\text{cos}({\gamma }_L)-Tl{W}_L{\psi }_L\text{sin}({\gamma }_L)\\ -({\alpha }_{x_F}+T{V}_F{\psi }_F\text{cos}({\gamma }_F)-Tl{W}_F{\psi }_F\text{sin}({\gamma }_F))]\text{cos}({\alpha }_{{\theta }_L}+T{W}_L)\\ -[{\alpha }_{y_L}+T{V}_L{\psi }_L\text{sin}({\gamma }_L)+Tl{W}_L{\psi }_L\text{cos}({\gamma }_L)\\ -({\alpha }_{y_F}+T{V}_F{\psi }_F\text{sin}({\gamma }_F)+Tl{W}_F{\psi }_F\text{cos}({\gamma }_F))]\text{sin}({\alpha }_{{\theta }_L}+T{W}_L)\mathrm{.}\end{array}$

After a number of manipulations and substitutions of some trigonometric identities, one finds that the dynamics of l_x can be written as:

$\begin{array}{l}{l}_x^{+}=-({\alpha }_{x_L}-{\alpha }_{x_F})\text{cos}({\alpha }_{{\theta }_L})\text{cos}(T{W}_L)-({\alpha }_{y_L}-{\alpha }_{y_F})\text{sin}({\alpha }_{{\theta }_L})\text{cos}(T{W}_L)\\ +({\alpha }_{x_L}-{\alpha }_{x_F})\text{sin}({\alpha }_{{\theta }_L})\text{sin}(T{W}_L)\\ -({\alpha }_{y_L}-{\alpha }_{y_F})\text{cos}({\alpha }_{{\theta }_L})\text{sin}(T{W}_L)-T{V}_L{\psi }_L\text{cos}(\frac{T}{2}{W}_L)\\ -Tl{W}_L{\psi }_L\text{sin}(\frac{T}{2}{W}_L)+T{V}_F{\psi }_F\text{cos}(e_{\theta }+(\frac{W_F-2W_L}{2})T)\\ -Tl{W}_F{\psi }_F\text{sin}(e_{\theta }+(\frac{W_F-2W_L}{2})T)\end{array}$

(11)

where the orientation error between the vehicles e_θ, is defined as $e_{\theta }={\alpha }_{{\theta }_F}-{\alpha }_{{\theta }_L}$ .

Considering equation (8), it is possible to rewrite equation (11) in the form:

$\begin{array}{l}{l}_x^{+}=l_x\text{cos}(T{W}_L)+l_y\text{sin}(T{W}_L)-T{V}_L{\psi }_L\text{cos}(\frac{T}{2}{W}_L)\\ -Tl{W}_L{\psi }_L\text{sin}(\frac{T}{2}{W}_L)+T{V}_F{\psi }_F\text{cos}\left(\gamma \right)-Tl{W}_F{\psi }_F\text{sin}\left(\gamma \right)\end{array}$

(12)

where $\gamma =e_{\theta }+T\left(\frac{W_F-2W_L}{2}\right)$ .

Applying a similar procedure to $l_y^{+}$ in equation (10), one obtains the dynamics:

$\begin{array}{l}{l}_y^{+}=-l_x\text{sin}(T{W}_L)+l_y\text{cos}(T{W}_L)+T{V}_L{\psi }_L\text{sin}(\frac{T}{2}{W}_L)\\ -Tl{W}_L{\psi }_L\text{cos}(\frac{T}{2}{W}_L)+T{V}_F{\psi }_F\text{sin}\left(\gamma \right)+Tl{W}_F{\psi }_F\text{cos}\left(\gamma \right)\mathrm{.}\end{array}$

(13)

The leader-follower formation problem can be alternatively described in terms of relative position errors, defined as $e_{l_x}=l_x^d-l_x$ , $e_{l_y}=l_y^d-l_y$ , where $l_x^d$ and $l_y^d$ are the desired relative distances between the vehicles. From Figure 2, it is easy to see that $l_x^d$ and $l_y^d$ can be expressed as:

$l_x^d={\bar{l}}_0\text{cos}\left({\phi }^d\left(kT\right)\right)\text{,}{l}_y^d={\bar{l}}_0\text{sin}\left({\phi }^d\left(kT\right)\right)$

(14)

for a desired time-varying angle ${\phi }^d$ . Note that equation (14) satisfies the relation ${\left(l_x^d\right)}^2+{\left(l_y^d\right)}^2={\bar{l}}_0^2$ .

The time evolution of $e_{l_x}$ can be obtained by considering, again, a direct forward shift; this is:

$\begin{array}{l}{e}_{l_x}^{+}=l_x^{d+}-\left(l_x\text{cos}(T{W}_L\right)+l_y\text{sin}\left(T{W}_L\right)\\ -T{V}_L{\psi }_L\text{cos}\left(W_L\frac{T}{2}\right)-Tl{W}_L{\psi }_L\text{sin}\left(W_L\frac{T}{2}\right)\\ +T{V}_F{\psi }_F\text{cos}\left(\gamma \right)-Tl{W}_F{\psi }_F\text{sin}\left(\gamma \right))\mathrm{.}\end{array}$

which can be rewritten in the form:

$\begin{array}{l}{e}_{l_x}^{+}=l_x^{d+}+e_{l_x}\text{cos}\left(T{W}_L\right)+e_{l_y}\text{sin}\left(T{W}_L\right)\\ +T{V}_L{\psi }_L\text{cos}\left(\frac{T}{2}{W}_L\right)+Tl{W}_L{\psi }_L\text{sin}\left(\frac{T}{2}{W}_L\right)\\ -T{V}_F{\psi }_F\text{cos}\left(\gamma \right)+Tl{W}_F{\psi }_F\text{sin}\left(\gamma \right)\\ -l_x^d\text{cos}\left(T{W}_L\right)-l_y^d\text{sin}\left(T{W}_L\right)\mathrm{.}\end{array}$

(15)

Following a similar procedure for $e_{l_y}$ , one obtains the dynamics:

$\begin{array}{l}{e}_{l_y}^{+}=l_y^{d+}-e_{l_x}\text{sin}\left(T{W}_L\right)\\ +e_{l_y}\text{cos}\left(T{W}_L\right)-T{V}_L{\psi }_L\text{sin}\left(\frac{T}{2}{W}_L\right)\\ +Tl{W}_L{\psi }_L\text{cos}\left(\frac{T}{2}{W}_L\right)\\ -T{V}_F{\psi }_F\text{sin}\left(\gamma \right)-Tl{W}_F{\psi }_F\text{cos}\left(\gamma \right)\\ +l_x^d\text{sin}\left(T{W}_L\right)-l_y^d\text{cos}\left(T{W}_L\right)\mathrm{.}\end{array}$

(16)

4. Delayed Feedback Solution to the Leader-follower Problem

According to the definition of the leader-follower problem as stated in Section 3, the follower robot must be able to follow any path described by the leader robot while maintaining a constant distance with respect to it. Therefore, the design of the control strategy should be based on the follower's control signals V_F, W_F. In order to simplify the developments of the required feedback, equations (15) and (16) can be rewritten in the compact form:

$\begin{array}{l}\left[\begin{array}{c}{e}_{l_x}^{+}\\ e_{l_y}^{+}\end{array}\right]=A_1(W_L)\left[\begin{array}{c}{e}_{l_x}-l_x^d\\ e_{l_y}-l_y^d\end{array}\right]+T{\psi }_L{A}_2(W_L)\left[\begin{array}{c}{V}_L\\ W_L\end{array}\right]\\ +T{\psi }_F{A}_3(\gamma )\left[\begin{array}{c}{V}_F\\ W_F\end{array}\right]+\left[\begin{array}{c}{l}_x^{d+}\\ l_y^{d+}\end{array}\right]\end{array}$

(17)

where,

$\begin{array}{l}{A}_1(W_L)=\left[\begin{array}{cc}\text{cos}(T{W}_L)& \text{sin}(T{W}_L)\\ -\text{sin}(T{W}_L)& \text{cos}(T{W}_L)\end{array}\right]\text{,}\\ A_2(W_L)=\left[\begin{array}{cc}\text{cos}(\frac{T}{2}{W}_L)& l\text{sin}(\frac{T}{2}{W}_L)\\ -\text{sin}(\frac{T}{2}{W}_L)& l\text{cos}(\frac{T}{2}{W}_L)\end{array}\right]\text{,}\\ A_3(\gamma )=\left[\begin{array}{cc}-\text{cos}\left(\gamma \right)& l\text{sin}\left(\gamma \right)\\ -\text{sin}\left(\gamma \right)& -l\text{cos}\left(\gamma \right)\end{array}\right]\mathrm{.}\end{array}$

To obtain a solution to the leader-follower problem, the virtual control signals, ${\xi }_1=T{\psi }_F{V}_F$ and ${\xi }_2=T{\psi }_F{W}_F$ are considered. Note also that, by defining $e_l={\left[e_{l_x}\mathrm{,}{e}_{l_y}\right]}^T$ , $l^d={\left[l_x^d\mathrm{,}{l}_y^d\right]}^T$ , $\xi ={\left[{\xi }_1\mathrm{,}{\xi }_2\right]}^T$ and $u_L={\left[V_L\mathrm{,}{W}_L\right]}^T$ , equation (17) can be rewritten as:

$\begin{array}{l}{e}_l^{+}=A_1(W_L)e_l-A_1(W_L)l^d\\ +T{\psi }_L{A}_2(W_L)u_L+A_3(\gamma )\xi +l^{d+}\mathrm{.}\end{array}$

(18)

A feedback law can now be synthesized based on the virtual controls ξ as:

$\begin{array}{l}\xi =A_3{\left(\bar{\gamma }\right)}^{-1}[v-A_1\left(W_L\right)e_l+A_1\left(W_L\right)l^d\\ -T{\psi }_L{A}_2\left(W_L\right)u_L-l^{d+}]\end{array}$

(19)

where the new input signal v is selected as:

$v=K{e}_l=\left[\begin{array}{cc}{k}_1& 0\\ 0& k_2\end{array}\right]\left[\begin{array}{c}{e}_{l_x}\\ e_{l_y}\end{array}\right]$

(20)

where $k_1\mathrm{,}{k}_2\in R$ , with $\left|k_1\right|<1$ , $\left|k_2\right|<1$ and $\bar{\gamma }=e_{\theta }+\frac{T}{2}(W_F^{-}-2W_L)$ .

The original control signals V_F, W_F can be derived from ξ₁ and ξ₂, more precisely:

$V_F=\frac{{\xi }_1}{T\psi (W_F)}\text{,}{W}_F=\frac{2}{T}{{\displaystyle \text{sin}}}^{-1}\left(\frac{{\xi }_2}{2}\right)\mathrm{.}$

(21)

Remark 3 It should be pointed out that control signals V_F, W_F cannot be synthesized directly from equation (17) due to the dependence of the matrix $A_3(\gamma )$ on the signal W_F, since $\gamma =e_{\theta }+T\left(\frac{W_F-2W_L}{2}\right)$ . For this reason, equation (19) is defined in terms of the delayed function $\bar{\gamma }$ that allows us to synthesize the virtual control signal ξ as a function of $W_F^{-}=W_F(kT-T)$ .

Let us now consider the formation error dynamics (18), together with the feedback (19); this is:

$\begin{array}{l}{e}_l^{+}=A_l\left(W_L\right)e_l-A_l\left(W_L\right)l^d+T{\mathrm{\Psi }}_L{A}_2\left(W_L\right)u_L\\ +A_3\left(\gamma \right)A_3{\left(\bar{\gamma }\right)}^{-1}[v-A_1\left(W_L\right)e_l+A_1\left(W_L\right)l^d-T{\mathrm{\Psi }}_L{A}_2\left(W_L\right)u_L-l^{d+}]+l^{d+}.\end{array}$

(22)

Note first that,

$A_3(\gamma )A_3{(\bar{\gamma })}^{-1}=\left[\begin{array}{cc}\text{cos}\left(\gamma -\bar{\gamma }\right)& -\text{sin}\left(\gamma -\bar{\gamma }\right)\\ \text{sin}\left(\gamma -\bar{\gamma }\right)& \text{cos}\left(\gamma -\bar{\gamma }\right)\end{array}\right]$

where $\gamma -\bar{\gamma }=\frac{T}{2}(W_F-W_F^{-})$ . Since $\text{cos}(x)=1-2{{\displaystyle \text{sin}}}^2(\frac{x}{2})$ , it is possible to write:

$A_3(\gamma )A_3{(\bar{\gamma })}^{-1}=I-\mathrm{\Delta }(\gamma -\bar{\gamma })=I-\left[\begin{array}{cc}{\partial }_1(\gamma -\bar{\gamma })& \partial (\gamma -\bar{\gamma })\\ -\partial (\gamma -\bar{\gamma })& {\partial }_1(\gamma -\bar{\gamma })\end{array}\right]$

(23)

where $I\in R^2$ is an identity matrix and $\partial (\gamma -\bar{\gamma })=\text{sin}(\gamma -\bar{\gamma })$ , ${\partial }_1(\gamma -\bar{\gamma })=2{{\displaystyle \text{sin}}}^2(\gamma -\bar{\gamma })$ . Hence, equation (22) takes the form:

$e_l^{+}=K{e}_l-\mathrm{\Gamma }$

(24)

with $\mathrm{\Gamma }={\left[\begin{array}{cc}{\mathrm{\Gamma }}_x& {\mathrm{\Gamma }}_y\end{array}\right]}^T$ being a non-linear term of the form:

$\mathrm{\Gamma }=h_1+h_2$

(25)

where

$h_1=\mathrm{\Delta }K-A_1\left(W_L\right)\left[e_l\right]\text{,}{h}_2=\mathrm{\Delta }{A}_1\left(W_L\right)l^d-T\psi \left(W_L\right)A_2\left(W_L\right)u_L-l^{d+}\mathrm{.}$

It is possible to show that the terms h₁ and h₂ are appropriated bounded functions. The term h₁ can be majored as:

$\Vert h_1\Vert =\Vert \mathrm{\Delta }K-A_1(W_L)e_l\Vert \le \Vert \mathrm{\Delta }\Vert [\Vert K-A_1(W_L)\Vert ]\Vert e_l\Vert \mathrm{.}$

Then, due to the boundedness of matrices Δ, K and $A_1(W_L)$ , there exists a non-zero real positive C₁, such that:

$\Vert h_1\Vert \le C_1\Vert e_l\Vert \mathrm{.}$

(26)

The term h₂ can be majored as:

$\Vert h_2\Vert \le \Vert \mathrm{\Delta }\Vert \left[\Vert A_1(W_L)l^d-T{\psi }_L{A}_2(W_L)u_L-l^{d+}\Vert \right]\le \Vert \mathrm{\Delta }\Vert \left[\Vert A_1(W_L)\Vert \Vert l^d\Vert +T\Vert {\psi }_L\Vert \Vert A_2(W_L)\Vert \Vert u_L\Vert +\Vert l^{d+}\Vert \right]\mathrm{.}$

Since $u_L={\left[\begin{array}{cc}{V}_L& W_L\end{array}\right]}^T$ , $l^d$ and $l^{d+}$ are bounded by design, it is possible to proof that the function ψ_L and matrices Δ, $A_1(W_L)$ and $A_2(W_L)$ are also bounded. Then, it is possible to write:

$\Vert h_2\Vert \le C_2$

(27)

for a non-zero positive constant C₂. Hence, from (26) and (27), it is obtained that:

$\Vert \mathrm{\Gamma }\Vert \le C_1\Vert e_l\Vert +C_2\mathrm{.}$

(28)

4.1. Formation error analysis

Based on the previous developments, it is now possible to state the main result on the evolution of the formation error, as follows.

Lemma 4 Let us consider a pair of differentially driven mobile robots, each of which is described by (5), together with the discrete-time feedback (19)–(21) where the real parameters k₁ and k₂ are such that $\left|k_i\right|<1$ for $i=\mathrm{1,2}$ . Then, if the condition:

$\Vert K\Vert +C_1<1$

(29)

is satisfied, then the formation error $e_l={\left[\begin{array}{cc}{e}_{l_x}& e_{l_y}\end{array}\right]}^T$ is ultimately bounded.

Proof. The time evolution of the closed-loop formation error e can be determined by considering the solution of equation (24); this is:

$e_l(n)=K^n{e}_l(0)-{\displaystyle \sum _{m=0}^{n-1}}{K}^{(n-1-m)}\mathrm{\Gamma }(m)$

(30)

which can be majored by using bound (28) as follows:

$\Vert e_l(n)\Vert \le {\Vert K\Vert }^n\Vert e_l(0)\Vert +{\displaystyle \sum _{m=0}^{n-1}}{\Vert K\Vert }^{(n-1-m)}\{C_1\Vert e_l(m)\Vert +C_2\}\mathrm{.}$

(31)

Since the eigenvalues of the matrix K are all within the unit circle, one finds that:

$\underset{n\to \infty }{{\displaystyle \text{lim}}}({\Vert K\Vert }^n)=0\text{and}\underset{n\to \infty }{{\displaystyle \text{lim}}}\left({\displaystyle \sum _{m=0}^{n-1}}{\Vert K\Vert }^{(n-1-m)}\right)=\frac{1}{1-\Vert K\Vert }\mathrm{.}$

Therefore, from equation (31), the ultimate bound can be obtained as:

$\underset{n\to \infty }{{\displaystyle \text{lim}}}\Vert e_l(n)\Vert \le \frac{C_2}{1-\Vert K\Vert -C_1}\mathrm{.}$

(32)

Then, if condition (29) holds, the formation error $e_l={\left[\begin{array}{cc}{e}_{l_x}& e_{l_y}\end{array}\right]}^T$ is ultimately bounded.

Remark 5 If the approximation of the angular acceleration as a function of the angular velocity W_F is considered, this is $a_{W_F}\approx \frac{(W_F-W_F^{-})}{T}$ , then $\gamma -\bar{\gamma }\approx \frac{T^2}{2}{a}_{W_F}$ . Therefore, consideration of a low angular acceleration, together with a sufficiently small sampling period, allows us to ensure that $\gamma -\bar{\gamma }\approx 0$ .

Remark 6 Note that the magnitudes of constants C₁, C₂ in the ultimate bound (32) directly depend on the norm of matrix Δ in equation (23). It is clear that when $\Vert \mathrm{\Delta }\Vert \to 0$ , one has $C_1\mathrm{,}{C}_2\to 0$ , ensuring in this way that ${{\displaystyle \text{lim}}}_{n\to \infty }\Vert e(n)\Vert =0$ . Since the magnitude of $\Vert \mathrm{\Delta }\Vert$ depends on $\gamma -\bar{\gamma }$ , a small ultimate bound is obtained in terms of Remark 5.

Remark 7 Note that in the special case in which the angular velocity is constant, as it is in the case of a straight or a circular path, the perturbation term Γ becomes a vanishing perturbation. In this case, the closed-loop formation error asymptotically converges to zero.

The result stated in Lemma 4 assures the boundedness of the formation error but it cannot determine the evolution of the orientation of the follower robot. This is an important issue since the control of the follower vehicle is carried out by considering the point ${\alpha }_F=({\alpha }_{x_F}\mathrm{,}{\alpha }_{y_F})$ , which is located at the front of the longitudinal axis of the vehicle. A good reference for the orientation of the follower vehicle is the orientation of the leader vehicle; that is, the error $e_{\theta }={\alpha }_{{\theta }_F}-{\alpha }_{{\theta }_L}$ , which has a time evolution that can be obtained by considering its corresponding forward shift, more precisely:

$e_{\theta }^{+}=e_{\theta }+T\left(W_F-W_L\right)\mathrm{.}$

(33)

Since W_L is an input to the leader robot that generates the tracking trajectory, it can be assumed to be bounded. Also, from (21) it is clear that W_F is also a bounded function. Therefore, the evolution of the formation error is bounded. The evolution of ${\alpha }_{{\theta }_L}$ is determined by the trajectory described by the leader robot. To determine the evolution of ${\alpha }_{{\theta }_F}$ , the first two equations of the discrete time model (5) are considered in order to obtain:

$\left({\alpha }_{x_F}^{+}-{\alpha }_{x_F}\right)\text{sin}({\gamma }_F)-\left({\alpha }_{y_F}^{+}-{\alpha }_{y_F}\right)\text{cos}({\gamma }_F)+l{\psi }_{F}T{W}_F=0.$

Then, by considering the last equation in (5) and the definition of γ_F, one obtains:

$\begin{array}{l}\left({\alpha }_{x_F}^{+}-{\alpha }_{x_F}\right)\text{sin}(\frac{{\alpha }_{{\theta }_F}^{+}+{\alpha }_{{\theta }_F}}{2})-\left({\alpha }_{y_F}^{+}-{\alpha }_{y_F}\right)\text{cos}(\frac{{\alpha }_{{\theta }_F}^{+}+{\alpha }_{{\theta }_F}}{2})\\ +2l\text{sin}\left(\frac{{\alpha }_{{\theta }_F}^{+}-{\alpha }_{{\theta }_F}}{2}\right)=0.\end{array}$

(34)

Equation (34) is the discrete-time counterpart of the continuous time nonholonomic restriction:

${\stackrel{·}{\alpha }}_x\text{sin}\theta -{\stackrel{·}{\alpha }}_y\text{cos}\theta +l\stackrel{·}{\theta }=0$

associated with the original system (3). The importance of equation (34) is that since the proposed leader-follower control strategy determines the evolution of the point $({\alpha }_{x_F}\mathrm{,}{\alpha }_{y_F})$ , the evolution of the orientation of the follower robot ${\alpha }_{{\theta }_F}$ must satisfy restriction (34). This fact shows the boundedness of ${\alpha }_{{\theta }_F}$ .

5. Experimental Evaluation

The solution proposed for the leader-follower formation problem (21) is initially evaluated by numerical simulations and by real-time experiments carried out using a pair of differentially driven wheeled mobile robots of the type Pioneer 3-DX from MobileRobots Inc.

5.1. Numerical results

A numerical experiment (NE) was carried out by considering that the leader robot follows a circular path with a radius of $1.8m$ centred at $(x\mathrm{,}y)=(3m\mathrm{,3}m)$ . The trajectory described by the leader robot is generated by considering a linear velocity $V_L=1m/s$ and an angular velocity $W_L=0.5rad/s$ . It is considered that the follower robot remains at a constant distance of one metre behind the leader robot, this is ${\bar{l}}_0=1m$ and ${\phi }^d=0rad$ (equivalently, $l_x^d=1m$ and $l_y^d=0m$ ). The initial conditions considered in the experiment are $x_L(0)=3m$ , $y_L(0)=1m$ , ${\theta }_L(0)=0rad$ and $x_F(0)=2.5m$ , $y_L(0)=2.5m$ , ${\theta }_L(0)=0rad$ . A sampling period of $T=0.1s$ was used, together with gains $k_1=0.4$ and $k_2=0.4$ .

Figure 3 depicts the evolution of the leader-follower formation on the Cartesian plane. It can be observed that the trajectory tracked by the follower robot is different from the one developed by the leader robot. This is a consequence of the control strategy that considers the control of the relative distance between the robots and not a specific path.

Figure 3.

NE. Time formation evolution on the Cartesian plane.

The tracking errors $e_{l_x}$ and $e_{l_y}$ , associated with the desired relative distance ${\bar{l}}_0$ , are shown in Figure 4 where it can be observed that $e_{l_x}$ and $e_{l_y}$ converge to the origin due to the constant angular velocity considered in the experiment (see Remark 7).

Figure 4.

NE. Cartesian relative errors $e_{lx}$ , $e_{ly}$ .

5.2. Experimental platform

As mentioned above, two differentially driven mobile robots of the type Pioneer 3-DX that support loads of up to $21kg$ were used. For these robots, $l=0.1m$ in equation (2), and $r=0.0973m$ , $m=0.34m$ in equation (4). To carry out the experiment, the leader robot carries a recognition graphical pattern placed at the midpoint of the wheel's axis. The pattern consists of three white rectangles within a black rectangle (see Figure 6). The follower robot has a Kinect device positioned at the midpoint of the wheel's axis and an on-board laptop in which image processing and calculations of the control law programmed in C++ are performed. An RGB camera in the Kinect device captures images that are smoothed and then binarized. Then, a program in the laptop searches the recognition pattern and detects the centroids of each of the three rectangular contours within a larger rectangular contour.

Figure 6.

Relative distance and orientation recognition using the graphical pattern and Kinect device

5.2.1. Vision-based localization system

This section provides an overview of the major steps of our method for detecting the leader robot from the visual information provided by the Kinect device that is on-board the follower robot for feedback purposes. The Microsoft Kinect device contains a depth sensor, an RGB camera and a four-microphone array. The Kinect device has the capabilities to perform 3D motion capture, and face and voice recognition [29]. The depth sensor consists of an infrared projector to differentiate depth by infrared vision. The infrared projector and a monochrome CMOS sensor in the Kinect device is combined to capture video data in 3D under any ambient light conditions. The vision sensor provides a maximum of 30 frames per second with a resolution of $640\times 480$ pixels for each camera. Due to its limitations, the depth sensor can be used for indoor navigation only.

The Kinect depth sensor can detect the distance of an object so that an autonomous robot can navigate while avoiding obstacles in an indoor environment [30]. The three-dimensional space is reconstructed by merging the two images obtained by the RGB and the depth camera. The RGB camera obtains the image of the environment while the depth camera obtains the depth information of each pixel in the image. A detailed analysis of the accuracy and resolution of the Kinect can be found in [31].

Before its use, the Kinect has to be calibrated to merge the data of the images obtained by the cameras and to process the raw data of the depth sensor. This calibration was done as in [32], following the procedure developed in [33]. The depth information obtained is linearly perpendicular to the longitudinal axis sensor. Thus, all the objects that are over the same line will have the same depth value, regardless of whether they are at the edge or at the centre of the image; this distance is denoted as $l_{xr}$ .

Figure 5 shows how the distance between the centre of the image and a centroid of the recognition pattern board is calculated; first by obtaining the depth information of the central point of the image and then by determining the number of pixels that exist between these two points at the same depth. The distance covered by each pixel is obtained experimentally using the approximate relation $cmppixel=0.169\ast depth+0.016$ obtained for a distance between $0.9m$ and $3.5m$ , where the first constant depends on the standard geometric characteristics of the cameras and the free constant term is a correction factor. See [32, 33] for more information.

Figure 5.

Distances between the centre of the image to the centroid of the recognition pattern

Knowing the number of pixels $NP$ between the centre of the image and a centroid of the recognition pattern, the length $l_{yr}$ is obtained as $l_{yr}=NP\ast cmppixel$ . If the centroid is on the right of the image this length will be positive, and negative if it is on the left.

Figure 6 shows how the recognition pattern on the leader robot is used to obtain the orientation error e_θ. Once the distance of the three centroids are determined from the Kinect information, the distances A and B (see Figure 6) are used to compute the relative orientation angle, e_θ, between the robots. This error is calculated using basic trigonometry; since the distance between the external centroids on the graphical pattern ( $C=11.5cm$ ) is known, and the distances A and B are known, it is a simple matter to obtain the orientation error as $e_{\theta }={{\displaystyle \text{sin}}}^{-1}\frac{C}{A-B}$ . The tracking distances l_x, l_y and the orientation error e_θ are calculated in real-time at each iteration of the control.

From the geometric relation between the robots, as shown in Figure 7, it is clear that the relative distances l_x, l_y used to obtain the solution to the formation problem can be obtained as: $l_x=l_{xr}+l_{x\alpha }$ , $l_y=l_{yr}+l_{y\alpha }$ where $l_{x\alpha }=l\text{cos}(e_{\theta })$ , $l_{y\alpha }=l\text{sin}(e_{\theta })$ .

Figure 7.

Geometrical representation of the alpha point and the middle point of each robot

5.3. Real-time results

Two real-time experiments were carried out in order to evaluate the proposed solution. The first one considered the tracking of a straight path by the leader robot, and a sinusoidal path for the second experiment. In both cases, the follower robot must track the leader vehicle at a constant distance of one metre ${\bar{l}}_0=1m$ with an angle ${\phi }^d=0rad$ (that is, $l_x^d=1m$ and $l_y^d=0m$ ). A sampling time of $T=0.05s$ was considered for the control loop. The Kinect device obtained the image and the depth data of all the pixels. Then, using the software OpenCV, the image was smoothed and binarized so it was possible to recognize the pattern board on the leader. The centroids of each rectangle were obtained knowing the pixels of the centroids, and the linear distances were obtained from the depth data; in this way, the measurement of the relative distances l_x, l_y were obtained, so that it was possible to compute l₀ and angle φ Then, the control variables were calculated and sent to the follower robot every $0.3s$ . It is important to point out that even when the control loop was carried out with a faster sampling time, the new control signal in the follower robot changed until a new relative distance measurement was obtained. For the real-time experiments, it is not considered to be a local absolute localization system and, therefore, it is not possible to show the evolution of the formation on the Cartesian plane.

5.3.1. Straight path experiment (StPE)

Even when, in the presented solution to the problem, internal or external disturbances have not been considered, a disturbance was introduced on the straight path experiment as a practical evaluation of the robustness of the discrete-time strategy. At approximately $t=11s$ , the follower robot was manually shifted from its current position, thus introducing instantaneous tracking errors and causing the vision system to lose the tracking reference pattern; incorrect estimations of the relative distances and angles between the robots thus appeared. The straight line was generated by considering $V_L=1m/s$ and $W_L=0rad/s$ . As an initial condition, the follower robot was placed at $l_0(0)=1.5m$ and $\phi (0)=3.3685rad$ (that is, $l_x(0)=-1.438m$ and $l_y(0)=-0.425m$ ) from the leader robot.

The evolution of the relative errors $e_{l_x}$ , $e_{l_y}$ is depicted in Figure 8, which shows their convergence to a neighbourhood of the origin until the mentioned disturbance appeared. After the new relative position was measured, the convergence of $e_{l_x}$ , $e_{l_y}$ was recovered. The evolution of the non-controlled error signal e_θ is shown in Figure 9, where it can be appreciated that it remained constant for the period that the disturbance was not affecting the experiment. Finally, Figure 10 shows the time evolution of the control signals.

Figure 8.

StPE. Behaviour of the relative errors $e_{lx}$ , $e_{ly}$ .

Figure 9.

StPE. Evolution of the non-controlled error e_θ.

Figure 10.

StPE. Control signals V_F, W_F.

Note that the effects of the external disturbance are more evident in Figure 9, where e_θ becomes an unbounded signal and, because of the physical characteristics of the experiment, this signal should have a magnitude between $\pm \pi$ rad. The control signal W_F is shown in Figure 10. It should be pointed out that during the interval of time when the disturbance was acting, the control signal (based on measured distances) was not acting on the mobile robot.

5.3.2. Sinusoidal path experiment (SiPE)

The sinusoidal path described by the leader robot was obtained by considering: $V_L=0.16m/s$ and $W_L=-0.647\text{sin}(kT)rad/s$ for $k=\mathrm{0,1,2,3,\dots }$ and $T=0.1s$ . The initial conditions of the experiment were set to $l_0(0)=0.8m$ and $\phi (0)=\pi rad$ .

The relative errors $e_{l_x}$ , $e_{l_y}$ are shown in Figure 11; it can be noted that they converge to a neighbourhood of the origin, evolving in a gap of $\pm 5cm$ for $e_{l_x}$ and $\pm 8cm$ for $e_{l_y}$ . Note that this gap depends on the constant associated with the norm of the perturbation term Γ, as well as on the magnitude of the relative error e_l. The main disadvantage in our experiment is the low refresh rate of the vision system, which induces an increment on the relative error e_l and consequently on the magnitude of the neighbourhood's convergence. The evolution of the non-controlled signal e_θ is shown in Figure 12 and it is bounded, as expected, from equation (34), oscillating in a gap of $\pm 0.3rad$ . The time evolution of the control signals is shown in Figure 13.

Figure 11.

SiPE. Behaviour of the errors $e_{lx}$ , $e_{ly}$ .

Figure 12.

SiPE. Evolution of the non-controlled error e_θ.

Figure 13.

SiPE. Control signals V_F, W_F.

Finally, the disturbance terms ${\mathrm{\Gamma }}_x$ and ${\mathrm{\Gamma }}_y$ , in equations (24)–(25) are depicted in Figure 14, where it can be seen that they are appropriated bounded, as it is required in order to obtain a small ultimate bound for the relative errors $e_{l_x}$ and $e_{l_y}$ .

Figure 14.

SiPE. Perturbation signals evolution ${\mathrm{\Gamma }}_x$ , ${\mathrm{\Gamma }}_y$ .

6. Conclusions

The leader-follower formation problem for nonholonomic differentially driven mobile robots is addressed in this work by considering the discrete-time representation of the kinematic models of the robots. To deal with the associated kinematics constraints, a control located at the front of the robot is considered. A solution to the problem is obtained by considering a single sampling time delayed feedback, based on relative distances and angles between the robots that are measured by an on-board camera mounted on the follower robot, together with a graphical pattern mounted on the leader robot.

It is formally proven that the relative Cartesian errors with respect to a desired relative distance between the robots are ultimately bounded. The main advantage of the proposed discrete-time strategy lies in its ease of implementation on microprocessors or computer-based platforms, and the consideration of the vision system that is of a discrete nature. The main disadvantage of the solution proposed is the closed-loop practical stability property of the convergence errors, since they converge to the origin only for constant angular velocities. The proposed strategy was evaluated via numerical and real-time experiments in a laboratory environment, using a low-cost measurement device. The use of relative distances between the leader and the follower robot has been previously used in the literature in a continuous time context; it is shown in this work that a discrete-time approach can also be exploited in the solution to the problem.