Distributed Optimization of Multi-Robot Motion with Time-Energy Criterion

Abstract

This paper is an application of a special case of distributed optimization problem. It is applied on optimizing the motion of multiple robot systems. The problem is decomposed into L subproblems with L being the number of robot systems. This decomposition reduces the problem to solving a single robot problem. The optimization problem is solved via a distributed algorithm, utilizing subgradient method. A global objective function is set as the sum of individual robot objectives in time and energy. Constraints are divided into two sets, namely, robot-individual constraints and robots’ interactions (collision) constraints. The approach is applied for the case of wheeled mobile robots: we are able to generate in parallel for each robot an optimized control input trajectory and then illustrate it in simulation examples.

1. Introduction

Research in multi-robot systems is motivated by several notions; namely, some motivation can be put as [1]:

• It is complex for one single robot system to fulfill complex tasks. Instead, more than one system would simplify the solution.

• Tasks are generally distributed in nature.

• Multiple limited-resource robot systems are more efficient to deal with than a single powerful robot system.

• Speed of the task process increases through parallelism in multiple robot systems.

• Robustness increases as redundancy is introduced in multiple systems.

Until recently, the number of real-life implementations of multi-robot systems is relatively small. The reason is the complexity associated with the field. Also, the related technologies are relatively new. Emergence of autonomous driving vehicle technology and market can push the boundaries in the field. As technology develops, new venues for application will open for mainstream use rather than only in research and development labs. Due to its promising applicability, autonomous cars and vehicles (or various intelligent transportation systems in general) sit at the forefront [2, 3]. To name a few, benefits include reducing congestions [4], increasing road safety [5], and, of course, self-driving cars [6]. Another application in civil environments is related to safety and security like rescue missions of searching for missing people in areas hard for humans to operate in [7] or searching for dangerous materials or bombs [8] in an evacuated building. Also, another area of application of multi-robot systems is in military area; research was done heavily in the fields of unmanned aerial vehicles (UAVs) and unmanned ground vehicles (UGVs) [9, 10].

Many approaches are developed to tackle the issue of multiple robot systems. Under the inspiration of biological systems and the need of technologies, many problems are defined as cooperative motions. Cooperative motion is discussed in [11, 12, 13, 14, 15, 16]. Optimization in both time and energy has been tackled in the literature [17, 18, 19, 20]. There is an opportunity to incorporate concept of time/energy optimization into the paradigm of multi-robot systems.

This paper investigates the solution of a time-energy optimal control problem for multiple mobile robots; namely, the paper is to study the problem as a nonlinear programming (NLP) problem. The main idea of the solution used here is to utilize distributed optimization techniques to solve the overall optimization problem. Solving for optimal time and energy of more than one robot system adds more burden on the problem; robot interaction with each other is added to the problem. This paper will focus more on the distributed aspect of the problem; more details about the numerical optimal control problem formulation can be found in [21]. In [21], the problem of controlling the motion of a single mobile robot is solved using the direct method of numerical optimal control (see [22]); this showed great flexibility in incorporating physical constraints and nonlinear dynamics of the system.

The rest of this section will define the global problem formulation. Discussion about distributed optimization and associated algorithm is presented in Section 2. Section 3 will apply the method on the multi-robot problem. Application to wheeled mobile robots and simulation examples are discussed in Section 4 followed by the conclusion.

1.1 Global problem formulation

We can present the discrete time global optimization (numerical optimal control) problem for L robots as follows:

$$\begin{array}{l}\underset{{\left\{u^i,t_s^i\right\}}_{\forall k,\forall i}}{\mathit{min}}\sum _{\forall i}H\left(x^i\left(N\right)\right)+z^i\left(N\right)\\ \mathrm{s}.\mathrm{t}.\\ z^i\left(k+1\right)=z^i\left(k\right)+t_s^i\left(k\right)·\left\{L\left(x^i\left(k\right),u^i\left(k\right),t_s^i\left(k\right)\right)\right\}\\ x^i\left(k+1\right)=f_D\left(x^i\left(k\right),u^i\left(k\right),t_s^i\left(k\right)\right)\\ g\left(x^i\left(k\right),u^i\left(k\right),t_s^i\left(k\right)\right)\le 0\\ {\Omega }^i\left({\left\{x^i\left(k\right)\right\}}_{\forall i},{\left\{u^i\left(k\right)\right\}}_{\forall i},{\left\{t_s^i\left(k\right)\right\}}_{\forall i}\right)\le 0\\ \forall k,z^i\left(0\right)=0,x^i\left(0\right)=x_0^i,i=1,2,\dots ,L\end{array}$$E1

with $t$ being the time-independent variable, $k$ being the time index in discrete domain, $t_s^i$ being the sampling period, and $N$ being the number of time discrete instants across the time horizon, i.e., $k=0,1,\dots ,N$. The sampling period corresponds to the length of time the system input $u^i\left(t\right)$ is kept constant (zero-order hold): we assume the system input to be

$$u^i\left(t\right)=u^i\left(k\right),\text{for}{t}_k^i\le t<t_{k+1}^i,t_{k+1}^i=t_k^i+t_s^i\left(k\right),t_0^i=0,\forall i$$

System behavior is governed by the nonlinear dynamic system in $f_D\left(x^i\left(k\right),u^i\left(k\right),t_s^i\left(k\right)\right)$ with $x^i\left(k\right)$ as the robot $i$ states an initial condition of $x^i\left(0\right)=x_0^i$. The above optimal control problem has a final state objective of $H\left(x^i\left(N\right)\right)$ with the Lagrangian $L\left(x^i\left(k\right),u^i\left(k\right),t_s^i\left(k\right)\right)$ information being embedded into a dummy state variable $z^i\left(k\right)$.

The above optimization problem can be viewed as having two sets of control variables; the first set resembles the discretized system inputs, ${\left\{u^i\left(k\right)\right\}}_{\forall k}$, and the other set consists of the variable sampling period, ${\left\{t_s^i\left(k\right)\right\}}_{\forall k}$. Let us have the Lagrangian for the problem be

$$L=x^T\mathit{Qx}+u^T\mathit{Ru}+\beta ,$$

with $\beta$ being the scalar weight on time. The performance is restricted by a collection of inequality constraints of robot-specific constraints $g\left(.\right)\le 0$ and robot-interaction constraints of ${\Omega }^i\left(.\right)\le 0$. The objective function is just the summation of individual objectives. In this paper, as it will be explained later, we consider only collision avoidance as robot-interaction requirement; however, the above formulation can also meet other considerations. It can be shown that the objective function in (1) corresponds to objective function of the form

$$\mathit{min}\sum _{i=1}^L\left[H\left(x^i\left(t_f\right)\right)+{\int }_{t_0}^{t_f}x{\left(t\right)}^T\mathit{Qx}\left(t\right)+u{\left(t\right)}^T\mathit{Ru}\left(t\right)+\mathit{\beta dt}\right]$$

2. Distributed optimization

Here in this section, the concept of distributed optimization is explored. This area tackles optimization problems with distributed nature. Consider the following optimization problem:

$$\begin{array}{l}\underset{{\left\{u^i\right\}}_{\forall i}}{\mathit{min}}\sum _{i=1}^L{J}^i\left(u^i\right)\\ \mathrm{s}.\mathrm{t}.u^i\in {\Omega }^i,\text{for}i=1,\dots ,L\end{array}$$E2

with $J^i\left(u^i\right)$ as the objective function and ${\Omega }^i$ the set of constraints. We can easily separate the problem into its corresponding sub problems. An ith subproblem is easily put as

$$\begin{array}{c}\underset{u^i}{\mathit{min}}{J}^i\left(u^i\right)\\ \mathrm{s}.\mathrm{t}.u^i\in {\Omega }^i\end{array}$$E3

Observing the global problem in (2), we can see that it is just equivalent to the combination of all the subproblems; it is easy to see that solving for each subproblem (3) individually will result in the solution for the whole global problem. Now, however, consider the following problem:

$$\begin{array}{l}\underset{\left\{u^i\right\}}{\mathit{min}}\sum _{i=1}^L{J}^i\left(u^i\right)\\ \mathrm{s}.\mathrm{t}.g^i\left(u^1,u^2,\dots ,u^L\right)\le 0,\forall i\end{array}$$E4

You see clearly that the above problem cannot be trivially separated into some subproblems due to the constraint $g^i\left(u^1,u^2,\dots ,u^L\right)\le 0$. This can be called a complicating constraint or a coupling constraint. In the next subsection, we discuss an optimization method that will help us in solving this kind of problems.

Decomposition in mathematics is the concept of breaking a mathematical problem into smaller subproblems that can be solved independently while not violating the original problem. Primary works of [23, 24] discuss multiple aspects of optimization in general while exploring specific classes as well; these works are excellent resources for reading and understanding. Viewing the applications of distributed optimization will convey the impression that they, however different, are all mostly very similar theoretically. Terms of networked, distributed, decentralized, cooperative, and the like are becoming all corresponding to somewhat similar problems. Other works related to this area and the area of multi-agent systems can be found in [25, 26, 27, 28, 29].

2.1 Subgradient method

Before going further, we discuss a method used in solving distributed optimization problem which will help us in solving the problem of this paper. This method is called subgradient methods [30]. These methods are similar to the popular optimization algorithms using gradient descent. However, they are extended to escape function differentiation. The works [31, 32, 33] also explore the method in the perspective of multi-agent systems.

Consider the typical problem:

$$\underset{u}{\mathit{min}}J\left(u\right)$$E5

This typical problem can be solved using any gradient descent method. At iteration $m$ of an algorithm, a solver, or an optimizer, can be constructed as

$$u_{\left(m+1\right)}=u_{\left(m\right)}-{\alpha }_{\left(m\right)}{d}_{\left(m\right)}$$E6

with ${\alpha }_{\left(m\right)}$ as a predefined step size. For a standard gradient method, the vector $d_{\left(m\right)}$ contains the gradient information of the problem. The simplest definition is to have

$$d_{\left(m\right)}=\nabla J\left(u_{\left(m\right)}\right)$$E7

However, for the subgradient method [33], we will have a definition of

$$d_{\left(m\right)}=p_{\left(m\right)}$$E8

with $p_{\left(m\right)}$, called subgradient of $J\left(u\right)$, being any vector that satisfies the following:

$$J\left(x\right)-J\left(u_{\left(m\right)}\right)\ge {p_{\left(m\right)}}^T\left[x-u_{\left(m\right)}\right],\forall x$$E9

The subgradient method is a simple first-order algorithm to minimize a possibly nondifferentiable function. The above definition escapes the requirement of a differentiated objective function. It is defined as finding any vector that makes the optimization algorithm go to better value in a first-order optimality sense. Of course, when a gradient $\nabla J\left(u_{\left(m\right)}\right)$ exists, we can compute the subgradient as the gradient. As it is a first-order method, it could have a lower performance than other second-order approaches. However, the advantage here is that it does not require differentiation. Also, and perhaps more importantly, it gives us flexibility to solve problems in a distributed manner as will be seen later.

Now observe the following constrained optimization problem:

$$\begin{array}{c}\underset{u}{\mathit{min}}J\left(u\right)\\ s.t.g\left(u\right)\le 0\end{array}$$E10

Let $g\left(u\right)$ be a vector of $M$ constraints. Then, we can define the dual problem. Let us define the dual function of $\lambda$ and $u$ as

$$q\left(\lambda ,u\right)=J\left(u\right)+{\lambda }^{T}g\left(u\right)$$E11

The vector $\lambda$ of size $M$ corresponds to the multipliers associated with each constraint. The dual problem relaxes the constraints of the original primal problem in (10) and solves for $\lambda$ to maximize the dual function:

$$\begin{array}{c}\underset{\lambda }{\mathit{max}}q\left(\lambda ,u\right)\\ s.t.\lambda \ge 0\end{array}$$E12

The dual optimization problem is the pair of two optimization problems, namely, a maximization in $\lambda$ as in (12) and a minimization in $u$. The pair resembles a maximization-minimization problem. You can visualize the solution of the problem as attacking the effect of constraint violation while solving for the original minimization problem concurrently.

Now, an algorithm for solving the dual problem utilizing subgradient method is discussed. Let us define

$$u\left(\lambda \right)=\mathit{arg}\underset{u}{\mathit{min}}\left\{J\left(u\right)+{\lambda }^{T}g\left(u\right)\right\}$$E13

The above definition is to clarify the minimum attained at any value of $\lambda$. So, with the above definition, at iteration $m$, with also denoting $u_{\left(m\right)}=u\left({\lambda }_{\left(m\right)}\right)$, we can safely have

$$q\left(\lambda ,u_{\left(m\right)}\right)=J\left(u_{\left(m\right)}\right)+{\lambda }^{T}g\left(u_{\left(m\right)}\right)=\underset{u}{\mathit{min}}\left\{J\left(u\right)+{\lambda }^{T}g\left(u\right)\right\}$$E14

Now, it is obvious from (14) that at iteration $m$, a subgradient of the dual function in (14) as function of $\lambda$ can be computed as $p_{\left(m\right)}=g\left(u_{\left(m\right)}\right)$. At iteration $m$ of the algorithm, an update for the multipliers is constructed as

$${\lambda }_{\left(m+1\right)}=P_{\lambda \ge 0}\left\{{\lambda }_{\left(m\right)}+{\alpha }_{\left(m\right)}g\left(u_{\left(m\right)}\right)\right\}$$E15

The projection operator $P_{\lambda \ge 0}\left\{.\right\}$ is to ensure that the value of the update ${\lambda }_{\left(m\right)}+{\alpha }_{\left(m\right)}{p}_{\left(m\right)}$ is positive or enforced to zero. Also, observe the ascent update with the “+” sign rather than a descent update as it is a maximization. We can assume an initial ${\lambda }_{\left(0\right)}=0$ or any other positive value. An optimal solution to the original problem in (10) will be attained as $m\to \infty$, with the optimal solution value of $u_{\left(m\right)}$.

2.2 The distributed algorithm

Recall the problem of combination of $L$ subproblems in (2). Now, let us have the following global problem:

$$\begin{array}{c}\underset{\left\{u^i\right\}}{\mathit{min}}\sum _{i=1}^L{J}^i\left(u^i\right)\\ \mathrm{s}.\mathrm{t}. u^i\in {\Omega }^i,\forall i\\ g^i\left(u^1,u^2,\dots ,u^L\right)\le 0,\forall i\end{array}$$E16

As mentioned, the constraints $g^i\left(u^1,u^2,\dots ,u^L\right)\le 0$ are the complicating (or coupling) constraints. We can formulate the dual pair problems to be

$$\begin{array}{c}\underset{\left\{{\lambda }^i\right\}}{\mathit{max}}q\left(\left\{{\lambda }^i\right\}\right)\\ s.t. {\lambda }^i\ge 0,\forall i\end{array}$$E17

Put in mind that $\left\{{\lambda }^i\right\}=\left\{{\lambda }^1,{\lambda }^2,\cdots ,{\lambda }^L\right\}$. If we define the notations of

$$u={\left[\begin{array}{cccc}{u}^1& u^2& \dots & u^L\end{array}\right]}^T,\lambda ={\left[\begin{array}{cccc}{\lambda }^1& {\lambda }^2& \dots & {\lambda }^L\end{array}\right]}^T,$$

then we can apply the primal-dual update from (13) and (15) at an iteration $m$ as

$$\begin{array}{cc}{\mathit{u}}_{\left(m,+,1\right)}^{*}& =\mathit{arg}\underset{\left\{u^i\right\}\in {\Omega }^i}{\mathit{min}}\left\{\sum _{i=1}^L\left\{J^i\left(u^i\right)+{\left[{\lambda }_{\left(m\right)}^i\right]}^T{g}^i\left(\mathit{u}\right)\right\}\right\}\\ {\mathit{\lambda }}_{\left(m+1\right)}& ={\mathcal{P}}_{\lambda \ge 0}\left\{{\mathit{\lambda }}_{\left(m\right)}+{\alpha }_{\left(m\right)}·{\left[g^1,\left({\mathit{u}}_{\left(m\right)}^{*}\right),g^2,\left({\mathit{u}}_{\left(m\right)}^{*}\right),\dots ,g^L,\left({\mathit{u}}_{\left(m\right)}^{*}\right)\right]}^T\right\}\end{array}$$E18

We can see that the above pair of updates can easily be distributed; after the relaxing of the constraints, the primal problem can be separated. The facility of subgradients lets us propose that any iteration $m$ for subproblem $i$ has

$$\begin{array}{cc}{u}_{\left(m+1\right)}^i& ={\mathit{\phi }}_{\mathit{min}}\left(J^i\left(u_{\left(m\right)}^i\right)+{\left[{\lambda }_{\left(m\right)}^i\right]}^T{g}^i\left(u_{\left(m\right)}^1,u_{\left(m\right)}^2,\dots ,u_{\left(m\right)}^L\right)\right)\\ {\lambda }_{\left(m+1\right)}^i& ={\mathcal{P}}_{{\lambda }^i\ge 0}\left\{{\lambda }_{\left(m\right)}^i+\alpha g^i\left(u_{\left(m\right)}^1,u_{\left(m\right)}^2,\dots ,u_{\left(m\right)}^L\right)\right\}\end{array}$$E19

The function ${\mathit{\phi }}_{\mathit{min}}\left(.\right)$ is any algorithm minimizer for the primal problem constrained by $u^i\in {\Omega }^i,\forall i$. Observe that the primal update for each subproblem needs only the latest values of the other subproblem updates. During the computations of an iteration, computation of $u_{\left(m+1\right)}^i$ and ${\lambda }_{\left(m+1\right)}^i$ is done independent of each other; the updates above can be computed in parallel for each subproblem. The only information shared after each iteration is $u_{\left(m\right)}^1,u_{\left(m\right)}^2,\dots ,u_{\left(m\right)}^L$ among all.

3. Distributed algorithm for multi-robot system

3.1 Problem formulation

Now, in this section we can apply the previous discussion into the problem of optimizing the motion of multiple robots. Recall the global optimization problem of motion of $L$ mobile robots from (1)

$$\begin{array}{l}\underset{{\left\{{\mathit{u}}^i,t_s^i\right\}}_{\forall k,\forall i}}{\mathit{min}}\sum _{i=1}^{L}H\left({\mathit{x}}^i\left(N\right)\right)+z^i\left(N\right)\\ \mathrm{s}.\mathrm{t}.\\ z^i\left(k+1\right)=z^i\left(k\right)+t_s^i\left(k\right)·\left\{\mathcal{L}\left({\mathit{x}}^i\left(k\right),{\mathit{u}}^i\left(k\right),t_s^i\left(k\right)\right)\right\}\\ {\mathit{x}}^i\left(k+1\right)=f_D\left({\mathit{x}}^i\left(k\right),{\mathit{u}}^i\left(k\right),t_s^i\left(k\right)\right)\\ {\mathit{g}}^i\left(x^i\left(k\right),{\mathit{u}}^i\left(k\right),t_s^i\left(k\right)\right)\le 0\\ {\mathit{\Omega }}^i\left({\left\{{\mathit{x}}^i\left(k\right)\right\}}_{\forall i},{\left\{{\mathit{u}}^i\left(k\right)\right\}}_{\forall i},{\left\{t_s^i\left(k\right)\right\}}_{\forall i}\right)\le 0\\ k=0,1,\dots ,N,i=1,\dots ,L,z^i\left(0\right)=0,{\mathit{x}}^i\left(0\right)={\mathit{x}}_0^i\end{array}$$E20

You can see that the problem above is just the combination of $L$ subproblems with superscript $i$ corresponding to each robot. The objective function is just the summation of individual objectives. The coupling constraint of ${\Omega }^i\left({\left\{x^i\left(k\right)\right\}}_{\forall i},{\left\{u^i\left(k\right)\right\}}_{\forall i},{\left\{t_s^i\left(k\right)\right\}}_{\forall i}\right)\le 0,\forall k$ is the only difference to the single robot problem. To simplify the notations, let us define

$${\overline{u}}^i={\left\{u^i\left(k\right),t_s^i\left(k\right)\right\}}_{k=0}^N$$

The above definition is just to reduce the notation of robot input sequence. If we have, for example, two robot inputs $u^i={\left[\begin{array}{cc}{u}_1^i& u_2^i\end{array}\right]}^T$ (e.g., wheel torques), then we have a total of $3\times L\times N$ control variables of the optimization problem. We can condense notation of the global problem of multi-robot system without loss of generality to be

$$\begin{array}{c}\underset{{\left\{{\overline{\mathit{u}}}^i\right\}}_{\forall i}}{\mathit{min}}\sum _{i=1}^L{J}^i\left({\overline{\mathit{u}}}^i\right)\\ \mathrm{s}.\mathrm{t}.{\overline{\mathit{u}}}^i\in {\Xi }^i\\ {\mathit{\Omega }}^i\left({\overline{\mathit{u}}}^1,{\overline{\mathit{u}}}^2,\dots ,{\overline{\mathit{u}}}^L\right)\le 0,\forall i\end{array}$$E21

with objectives

$$J^i\left({\overline{u}}^i\right)=H\left(x^i\left(N\right)\right)+z^i\left(N\right)$$E22

which are subject to the set of individual robot $i$ constraints of

$${\Xi }^i:\left\{\begin{array}{l}{z}^i\left(k+1\right)=z^i\left(k\right)+t_s^i\left(k\right)·\left\{L\left(x^i\left(k\right),u^i\left(k\right),t_s^i\left(k\right)\right)\right\}\\ x^i\left(k+1\right)=f_D\left(x^i\left(k\right),u^i\left(k\right),t_s^i\left(k\right)\right)\\ g^i\left(x^i\left(k\right),u^i\left(k\right),t_s^i\left(k\right)\right)\le 0\\ \forall k,z^i\left(0\right)=0,x^i\left(0\right)=x_0^i\end{array}\right.$$E23

3.2 Distributed algorithm

Returning back to the primal-dual problem pair in Section 2, we can establish the algorithm updates according to the defined updates in (19). At each iteration $m$, we update each robot inputs and multipliers according to

$$\begin{array}{cc}{\overline{\mathit{u}}}_{\left(m+1\right)}^i& ={\mathit{\phi }}_{\mathit{min}}\left(J^i\left({\overline{\mathit{u}}}_{\left(m\right)}^i\right)+{\left[{\lambda }_{\left(m\right)}^i\right]}^T\left[{\mathit{\Omega }}_{\left(m\right)}^i\right]\right)\\ {\lambda }_{\left(m+1\right)}^i& ={\mathcal{P}}_{{\lambda }^i\ge 0}\left\{{\lambda }_{\left(m\right)}^i+\alpha {\mathit{\Omega }}_{\left(m\right)}^i\right\}\end{array}$$E24

The minimizer update ${\mathit{\phi }}_{\mathit{min}}\left(.\right)$ is responsible to solve the single robot optimization (primal) problem according to the objective defined in (22) and subject to constraints in (23). In this paper, the minimizer update ${\mathit{\phi }}_{\mathit{min}}\left(.\right)$ is selected to be any state-of-the-art nonlinear programming (NLP) algorithm. Let us have the step size $\alpha$ for the dual update to be constant. This is sufficient for converging to a solution of the original problem [33]. You can read the algorithm updates in (24) at iteration $m$ as each robot independently optimizes its whole motion throughout the whole time horizon $k=0,1,\dots ,N$ while at the same time puts in mind the extra cost of cooperation/interaction with others introduced by the term ${\left[{\lambda }_{\left(m\right)}^i\right]}^T\left[{\Omega }_{\left(m\right)}^i\right]$ and so on.

3.3 Algorithm convergence

In this brief section, elaboration is put forth about how to practically use the algorithm. The ultimate goal is to optimize primal problem with no collision violation, i.e., reaching optimal dual (maximum) solution. At each global iteration, we only need to improve the primal problem values for the updated extra cost of the interaction constraint, ${\left[{\lambda }^i\right]}^T\left[{\Omega }^i\right]$. In this paper, a perfect solution is to optimize while maintaining ${\left[{\Omega }^i\right]}_{\forall k}\le 0$. A logical property is to monitor the M-element vector of constraints for positive values, i.e., violations. So, a stopping criterion for the algorithm can be chosen to be some minimum change $\text{TolJ}$ in the primal problem value:

$$\left|J_{\left(m+1\right)}-J_{\left(m\right)}\right|\le \text{TolJ with}{J}_{\left(m\right)}={\sum }_{i=1}^{L}J\left({\overline{u}}_{\left(m\right)}^i\right)$$E25

We can also distribute the stopping decision to individual robots by observing the change in individual objective values.

With condition (25) on its own, we cannot always be satisfying the collision requirement. So, this condition can be accompanied by a condition on the collision constraint violation. For all robots, elements of the complete constraint vector ${\left[{\Omega }^i\right]}_{\forall k}$ should be less than a relatively small positive value $\mathrm{Tol}\Omega$. So, for each robot, an extra stopping criterion along with criteria in (25) is to have

$$\mathit{max}\left({\left[{\Omega }_{\left(m\right)}^i\right]}_{\forall k}\right)\le \text{TolΩ}$$E26

Specific values of $\text{TolΩ}$ and $\text{TolJ}$ depend on the nonlinear programming algorithm and/or the global desired requirements. Note that the behavior of the two tolerance parameters could be competitive with each other.

4. Application to wheeled mobile robots

4.1 System description

Figure 1 shows the individual robot system considered here. Robot state includes $x^i={\left[\begin{array}{ccccccc}x& y& \varphi & {\theta }_R& {\theta }_L& v_R& v_L\end{array}\right]}^T$ with both position $\left(x,y\right)$ and orientation $\varphi$ and $\left({\theta }_R,{\theta }_L,v_R,v_L\right)$ as the right and left wheel angular positions and velocities, respectively. Robot input includes the respective wheel torques $u^i={\left[\begin{array}{cc}{\tau }_R& {\tau }_L\end{array}\right]}^T$. You can have the details of the applied nonlinear dynamic model $f_D\left(x^i\left(k\right),u^i\left(k\right),t_s^i\left(k\right)\right)$ based on the system model developed in [34, 35]. Details of discretization and choice of parameters of the robot model can be found in [21]. As mentioned before, for choices of $Q,R$ in Section 1, the Lagrangian for the problem is chosen to include the cost for energy spent by the torques of the wheels, the cost for kinetic energy spent by robot body, and the weight on time. Individual robot constraints include final desired configuration tolerance, torque limits, and the ensurance of zero final velocities (see more details in [36]).

Figure 1.

Wheeled mobile robot.

4.2 Collision avoidance

Here, we will discuss the formulation and the structure of the coupling constraints. The robots can be designed to perform any cooperative strategy in their motion. Here, we only consider the global goal of optimizing the motion of each robot in time and energy while avoiding colliding with each other during the motion. Let us define the coupling constraint vector across the discrete time indexes as

$${\Omega }^i\left(k\right)={\Omega }^i\left({\left\{x^i\left(k\right)\right\}}_{\forall i},{\left\{u^i\left(k\right)\right\}}_{\forall i},{\left\{t_s^i\left(k\right)\right\}}_{\forall i}\right).$$

For the ith robot, it tries to avoid colliding with the rest of $L-1$ robots at each of its time indexes $k$. Let us label elements of the constraint vector as $\left[{\Omega }^{\mathit{ij}}\left(k\right)\right]$. Each element is corresponding to a definition of constraint at time index $k$ for all other robots, $j\ne i$. So, for each robot, the constraint vector $\left[{\Omega }^i\right]$ is of size $M=\left(L-1\right)\times N$; of course, the multiplier vector ${\lambda }^i$ in (24) is of the same size.

We define the collision avoidance by constraining motion of other robots to be outside a safety circle region around each $i$ robot at the position $\left(x^i,y^i\right)$ in the 2D plane:

$${\left(x^i\left(k\right)-{\widehat{x}}^j\left(k\right)\right)}^2+{\left(y^i\left(k\right)-{\widehat{y}}^j\left(k\right)\right)}^2\ge p^2.$$

So, we can define each element of the constraint vector as

$${\Omega }^{\mathit{ij}}\left(k\right)=p^2-{\left(x^i\left(k\right)-{\widehat{x}}^j\left(k\right)\right)}^2+{\left(y^i\left(k\right)-{\widehat{y}}^j\left(k\right)\right)}^2$$E27

The radius of the safety region is chosen as $p$. Because of the definition of the sampling period variable, at each of discrete time step $k,$ the actual time variable does not necessarily imply $t^i\left(k\right)=t^j\left(k\right)$ for all the other $L-1$ robots. That is why you see that the x- and y- coordinates in (23) of the $j\mathrm{th}$ robot are noted as $\left({\widehat{x}}^j,{\widehat{y}}^j\right)$ which are chosen to be calculated as linear interpolation of positions according to available actual times of $t^i\left(k\right) \text{and} t^j\left(k\right)$.

4.3 Simulation examples

You can follow the whole distributed algorithm for the time-energy optimization of multi-robot system with collision avoidance in the flowchart in Figure 2. View the flowchart as the process for each individual robot (subproblem). We implement the algorithm in Figure 2. For the primal minimizer update in (24), the nonlinear programming (NLP) function of fmincon in MATLAB is used. We solved the problem for motion of $L=3$ mobile robots. Utilizing the parallel capability in MATLAB, the distributed steps are solved independently utilizing three parallel processors. We choose number of instants $N=40$; so, we are going to optimize 120 control variables for each robot. More details can be found in [36].

Figure 2.

Distributed algorithm flowchart to optimize multi-robot motion.

Example 1. In this example, exploration of the behavior of the algorithm is shown. The problem has the following desired values of initial and final positions and orientations for the three robots:

$$\left(x_0^1,y_0^1,{\varphi }_0^1\right)=\left(0,-8,\frac{\pi }{2}\right),\left(x_f^1,y_f^1,{\varphi }_f^1\right)=\left(0,5,\pi \right)$$

$$\left(x_0^2,y_0^2,{\varphi }_0^2\right)=\left(-10,-1,0\right),\left(x_f^2,y_f^2,{\varphi }_f^2\right)=\left(8,5,\frac{\pi }{2}\right)$$

$$\left(x_0^3,y_0^3,{\varphi }_0^3\right)=\left(5,0,\pi \right),\left(x_f^3,y_f^3,{\varphi }_f^3\right)=\left(-8,-1,\frac{\pi }{2}\right)$$

Here, robot 1 has equal objective weights of 5 on both time and energy, robot 2 has weights of 10 on energy and 1 on time, and robot 3 has 10 on time and 1 on energy. The maximum number of internal NLP iterations (primal update) is set to only 10. The step size is set to $\alpha =0.1$. Maximum global iterations are allowed for 100 iterations. The safety circle radius is chosen to be $p=2$.

Figure 3 contains the objective (time-energy) value evolution throughout iterations. You can see the stable convergence as the algorithm progresses. Figure 4 shows each of the robots’ safety clearances during the optimized motion. In Figure 5, snapshots of motion of the three robots at different time instants are depicted. This illustrates the collision avoidance attained throughout the optimized motion. Observe also how different are the speeds of each robot because of objective weights; note from Figure 4 that each robot has a different final time for their motion. The algorithm has shown good performance at eliminating collision constraint violations. Figures 4 and 5 show an instant (around t = 12) where robots 1 and 3 violate collision distance with very small value, but no collision occurs. This is because the maximum number of iterations of the algorithm is exhausted. This indicates the possibility for the motion to be optimized even more if collision constraints were relaxed or if more algorithm iterations were allowed. Initialization of the algorithm also plays a role in algorithm evolution.

Figure 3.

The time-energy objective values throughout global iterations (Example 1).

Figure 4.

Collision avoidance (Example 1).

Figure 5.

Snapshots of optimized motions at different instants (Example 1).

Example 2. This example illustrates more the satisfaction of the objectives. In this example the safety circle radius is put as $p=3$. Here we choose the following initial and final positions and orientations for the three robots:

$$\left(x_0^1,y_0^1,{\varphi }_0^1\right)=\left(-8,0,\frac{\pi }{2}\right),\left(x_f^1,y_f^1,{\varphi }_f^1\right)=\left(8,0,\frac{\pi }{2}\right)$$

$$\left(x_0^2,y_0^2,{\varphi }_0^2\right)=\left(0,8,0\right),\left(x_f^2,y_f^2,{\varphi }_f^2\right)=\left(0,-8,0\right)$$

$$\left(x_0^3,y_0^3,{\varphi }_0^3\right)=\left(8,0,-\frac{\pi }{2}\right),\left(x_f^3,y_f^3,{\varphi }_f^3\right)=\left(-8,0,-\frac{\pi }{2}\right)$$

After applying our approach, you can see the resulting optimized motions in Figure 6. In Figure 6, errors in x- and y-coordinates and orientation of each robot are shown with respect to time. It is clear that errors of zero are achieved. In Figure 7 for each robot, constraint evaluations, i.e., safety clearance, are displayed for the other two robots throughout time. You can see that robots come close to each other sometimes but without violating the safety distance. This result is attained maybe because of special structure of initial and final positions and orientations. That could have given flexibility for the algorithm.

Figure 6.

Optimized trajectories of the three robots: each row of plots shows x-coordinate error, y-coordinate error, and orientation error, respectively; each column of plots show robots 1, 2, and 3 errors, respectively (Example 2).

Figure 7.

Collision avoidance (Example 2).

5. Conclusion

The paper investigated the time-energy minimization onto the multi-robot case. A global objective function is formulated as the sum of individual robot objectives in time and energy. Constraints are divided into two sets, namely, robot-individual constraints and robots’ interaction constraints. The problem is decomposed into L subproblems with L being the number of robot systems. The subproblems are coupled with each other by the collision avoidance information. Applying a distributed algorithm solved the problem iteratively. The overall output gives optimized motions for all robots in time and energy while adhering and not colliding with each other. We applied our approach to the case of three wheeled mobile robots: we generated in parallel for each robot an optimized control input trajectory.

An extension to this study is to generate optimized motion trajectories and apply them experimentally. A possible area for experimentation is full-scale autonomous vehicles. Issues related to communication and distributing information during the parallel algorithm will need to be incorporated and investigated. Also, aspects of state estimation and localization of the robot system will come into the place which were not considered in this work. A possible other investigation is to distribute the problem further onto the time variable $k$; this will lead the problem to the domain of distributed model predictive control. This will, possibly, pave the way to faster deployment into autonomous vehicles.

Acknowledgments

The authors would like to thank King Fahd University of Petroleum and Minerals supporting this work.