Multi-robot energy autonomy with wind and constrained resources

Hassan Fouad and Giovanni Beltrame *This work was supported by the NSERC Discovery Grant 2019-05165.Hassan Fouad and Giovanni Beltrame are with Computer and Software Engineering department, Ecole polytechnique de Montreal hassan.fouad@polymtl.ca**The appendices of this paper can be found at https://mistlab.ca/papers/energy2020

Abstract

One aspect of the ever-growing need for long term autonomy of multi-robot systems, is ensuring energy sufficiency. In particular, in scenarios where charging facilities are limited, battery-powered robots need to coordinate to share access. In this work we extend previous results by considering robots that carry out a generic mission while sharing a single charging station, while being affected by air drag and wind fields. Our mission-agnostic framework based on control barrier functions (CBFs) ensures energy sufficiency (i.e., maintaining all robots above a certain voltage threshold) and proper coordination (i.e., ensuring mutually exclusive use of the available charging station). Moreover, we investigate the feasibility requirements of the system in relation to individual robots’ properties, as well as air drag and wind effects. We show simulation results that demonstrate the effectiveness of the proposed framework.

I Introduction

The continuous advances in multi-robot systems gave rise to many new applications like patrolling [12], coverage [4], exploration [3] and construction [11] to give a few examples. This has drawn many researchers’ attention in recent years to long term autonomy and resilience of multi-robot systems, with the aim of providing more practical and robust systems.

Energy autonomy, the ability of the robots in a multi-robot system to replenish their energy reserves, is particularly important to extend mission duration and general survivability.

Earlier interest in optimizing energy consumption in a multi-robot system can be traced back to energy aware path planning [14] and node scheduling in wireless sensor networks [13]. These ideas have been applied to multi-robot systems as in [8], where the mission tasks are divided among robots according to their energy content.

One option for tackling the issue of limited energy is through the introduction of stationary or mobile charging stations. Ding et al. [5] propose a method for planning routes of charging robots that deposit batteries along the trajectories of other robots carrying out a surveillance mission. Notomista et al. [10] use a control barrier function framework that allows each robot in a multi-robot system to recharge from a dedicated static charging station in a mission agnostic and minimally invasive manner.

In this work we extend [7], which is in turn inspired from [10], by considering a group of robots affected by air drag that perform a generic mission (e.g. coverage or patrolling) in a known wind field. These robots need to share a single charging station.

The contributions of this paper are: 1) We extend the results in [7] so that the CBF-based coordination framework proposed can account for the effect of air drag and winds, while ensuring mutually exclusive use of the charging station, and 2) we extend the sufficient feasibility conditions proposed in [7] to express the system’s capacity in case of wind and air drag effects and ensure the feasibility of coordination.

Ii Preliminaries

Ii-a Control Barrier Functions (CBF)

A control barrier function (CBF) [1] is a tool that is mainly used to ensure set invariance of control affine systems, having the form

˙ x = f (x) + g (x) u .

(1)

This is often used for ensuring system’s safety by enforcing forward invariance of a desired safe set.

The safe set is defined to be the superlevel set of a continuously differentiable function $h (x)$ such that [1]:

\begin{matrix} C & = {x \in R^{n} : h (x) \geq 0} \partial C & = {x \in R^{n} : h (x) = 0} I n t (C) & = {x \in R^{n} : h (x) > 0} \end{matrix}

(2)

where ensuring $h (x) > 0, \forall t \geq 0$ implies the safe set $C$ is positively invariant. For a control affine system, having a control action $u$ that achieves

L_{f} h (x) + L_{g} h (x) u      ˙ h (x) \geq - α (h (x))

(3)

where $α (h (x))$ is an extended type $K$ function, ensures positive invariance of $C$ .

One popular type of CBFs that we use in this paper is the zeroing control barrier function (ZCBF) [2], as they have favourable robustness and asymptotic stability properties [17].

Definition 1

[2] For a region $D \in C$ a continuously differentiable function $h (x)$ is called a ZCBF if there exists an extended class $K$ function $α (h (x))$ such that

sup u \in U (L_{f} h (x) + L_{g} h u + α (h (x)) \geq 0)

(4)

The set $K_{z c b f}$ [2] is defined as

K_{z c b f} = {u \in U : L_{f} h (x) + L_{g} h u + α (h (x)) \geq 0}

and it is the set that contains all the safe control inputs, thus choosing a Lipschitz continuous controller $u \in K_{z c b f}$ ensures forward invariance of $C$ and system’s safety.

To mix the safety control input with an arbitrary mission’s control input $u_{n o m}$ , we use a quadratic program: [10]

		$u^{*} = min u$		$\| \| u - u_{n o m} \| \|^{2}$		(5)
		$s.t.$		$L_{f} h (x) + L_{g} h (x) u \geq - α (h (x)) .$		(5)

Ii-B Higher order control barrier functions (HOCBF)

If $h (x)$ is of a higher relative degree (the control action $u$ doesn’t appear after differentiating once, i.e. $L_{g} h (x) = 0$ ), using (3) to find an appropriate control action becomes invalid. HOCBFs [16] are an effective solution of this problem. To define a HOCBF, we first need to define the following set of functions for an $m^{t h}$ order differentiable function $h (x)$

\begin{matrix} ψ_{0} (x) & = h (x) ψ_{1} (x) & = {˙ ψ}_{0} (x) + α_{1} (ψ_{0} (x)) ⋮ ψ_{m} (x) & = {˙ ψ}_{m - 1} (x) + α_{m} (ψ_{m - 1} (x)) \end{matrix}

(6)

where $α_{1}, \dots, α_{m - 1}$ are class $K$ functions. Also we define the following series of sets

C1\vcentcolon={x∈Rn:ψ0(x)≥0}⋮Cm\vcentcolon={x∈Rn:ψm(x)≥0}

(7)

Definition 2

[16] Let $C_{1}, C_{2}, \dots, C_{m}$ be defined by (7) and $ψ_{0} (x), ψ_{1} (x), \dots, ψ_{m} (x)$ be defined by (6). A function $h (x)$ is a HOCBF of relative degree $m$ for system (1) if there exists differentiable class $K$ functions $α_{1}, α_{2}, \dots, α_{m}$ such that

L_{f}^{m} h (x) + L_{g} L_{f}^{m - 1} h (x) + O (h (x)) + α_{m} (ψ_{m - 1} (x)) \geq 0

(8)

for all $x \in C_{1} \cap C_{2} \dots \cap C_{m}$ . Here $O (h (x))$ denotes the remaining Lie derivatives along $f$ with degrees less than or equal $m - 1$ .

Xiao et al. show in [16, Theorem 5] that choosing a control action that satisfies (8) renders the set $C_{1} \cap C_{2} \dots \cap C_{m}$ forward invariant for system (1).

Iii Problem formulation

We assume $n$ robots moving in a given wind field with the following dynamics:

\begin{matrix} ˙ x & = v ˙ v & = u - C_{d} (v - v_{w}) ˙ E & = {\begin{matrix} - k_{e} - k_{v} | | v - v_{w} | |, if | | x - x_{c} | | > δ k_{c h}, Otherwise \end{matrix} \end{matrix}

(9)

where $x \in R^{2}$ is the robot’s position, $v \in R^{2}$ is its velocity, $C_{d} > 0, k_{c h} > 0, k_{e} > 0, k_{v} > 0$ are coefficients of linear drag, recharge, static and dynamic discharge respectively. Also $E > 0$ is the robot’s voltage, $u \in R^{2}$ is the control input (no constraints on the control input), and $v_{w}$ is a known wind vector. Moreover we suppose that all the robots operate in a certain known operational range $x \in R \subset R^{2}$ , where $R$ is a closed set, and the size of this operational range is described by the operational radius $R_{0}$ . The robots are carrying out a mission specified by $u_{n o m}$ and they have one charging station at a known location $x_{c}$ (in the origin without loss of generality), and this station can only serve one robot at a time, and has an effective charging range of $δ > 0$ .

We point out that in our model we use a linear drag term to account for the air drag effect, which is a reasonable approximation for bodies moving at low speeds. The main assumptions we are adopting in this work are: 1. all robots have the same properties 2. robots have a complete communication graph 3. robots start discharging from the maximum voltage 4. the charging rate is faster than the discharge rate¹¹1E.g. battery swapping or high power wireless charging. 5. An upper bound of the average relative velocity w.r.t. wind velocity(we call it $~ V$ ) of all robots is known at the beginning of the mission. We propose a CBF framework that:

Ensures no robot runs out of energy during the mission
Coordinates the times of arrival to the charging station so they are mutually exclusive.

Additionally, we describe the system’s capacity as the relationship between number of robots and robot properties with feasible separation in arrival times at the charging station.

It is worth mentioning that for the rest of the paper we are omitting the proofs due to space constraints, and putting them all in the appendix.

Iv Energy sufficiency

We provide a CBF that ensures that the voltage of all robots does not go below a certain desired minimum voltage $E_{m i n}$ . We take inspiration from [10], but we extend it to accommodate the system dynamics in (9). The candidate CBF is

h_{e} = E - E_{m i n} - k_{c} log \frac{D}{δ}

(10)

where $D = | | x - x_{c} | |$ ²²2The choice of $k_{c}$ is explained in the appendix. The first derivative of this function is

{˙ h}_{e} = - k_{e} - k_{v} | | v - v_{w} | | - \frac{k_{v}}{D^{2}} (x - x_{c})^{T} v

(11)

so we need to differentiate twice for the control input $u$ to appear

\begin{matrix} {¨ h}_{e} = L_{g} L_{f} h_{e} (x)      - [k v \frac{(v - v_{w})^{T}}{| | v - v_{w} | |} + k_{c} \frac{(x - x_{c})^{T}}{D^{2}}] u + k_{v} C_{d} | | v - v_{w} | | + \frac{k_{c}}{D^{2}} [\frac{2 ((x - x_{c})^{T} v)^{2}}{D^{2}} - v^{T} v + C_{d} x - x_{c})^{T} (v - v_{w})] \end{matrix}

(12)

with the second and third expressions being $L_{f}^{2} h_{e} (x)$ . We can then create an inequality similar to (8) using $α_{1} (h) = p_{1} h$ and $α_{2} (h) = p_{2} h$

L_{f}^{2} h_{e} (x) + L_{g} L_{f} h_{e} (x) u + (p_{1} + p_{2}) {˙ h}_{e} + p_{1} p_{2} h_{e} \geq 0

(13)

and $p_{1} >$ and $p_{2} >$ are chosen in such a way that lends the characteristic equation of the left side of (13) with distinct real roots.

Theorem 1

For a robot described by dynamics in (9), and provided that the robot is out of the charging region, and that $k_{c} > k_{v} R_{0}$ , then $h_{e}$ is a HOCBF.

Lemma 1

For a robot with dynamics described by (9) applying a QP as in (5) with (13) as being the constraint, then the quantity $E - E_{m i n}$ at the time of arrival to the charging station is upper bounded with a quantity exponentially decaying with a rate of $\frac{1}{2} (- (p_{1} + p_{2}) + | p_{1} - p_{2} |)$ and lower bounded by zero.

V Coordination

The second component in our framework ensures that the difference in arrival times of any two robots to the charging station is above a desired limit. The main idea is that if two robots have different values of $E_{m i n}$ , they arrive to the charging station at different times. We propose a method for changing the values of $E_{m i n}$ to achieve the aforementioned coordination.

To get this expression, we integrate the voltage relation in (9) to get

\begin{matrix} \int_{E_{m a x}}^{E_{m i n}} ˙ E d t & = - \int_{0}^{T_{L}} (k_{e} + k_{v} | | v - v_{w} | |) d t E_{m a x} - E_{m i n} & = k_{e} T_{L} + k_{v} \int_{0}^{T_{L}} | | v - v_{w} | | d t . \end{matrix}

(14)

Supposing we have the average relative speed $¯ z = \frac{1}{T_{L}} \int_{0}^{T_{L}} | | v - v_{w} | | d t$ , the last integral can be replaced and the arrival time becomes

T_{L} = \frac{E_{m a x} - E_{m i n}}{k_{e} + k_{v} ¯ z} .

(15)

We then replace $E_{m a x}$ in the last expression by $E (t)$ to get an expression for $T_{L} (t)$ that changes with time

T_{L} (t) = \frac{E (t) - E_{m i n}}{k_{e} + k_{v} ¯ z} .

(16)

In this work, we use a moving average $¯ V$ to estimate the average velocity relative to wind defined as

¯ V = \frac{1}{w} \int_{0}^{w} | | v - v_{w} | | d t

(17)

where $w > 0$ is the width of the integration window. The larger the window, the closer the estimate is to the true average. The approximate value of the arrival time is

T_{L} (t) \approx \frac{E (t) - E_{m i n}}{k_{e} + k_{v} ¯ V} .

(18)

To be able to change $E_{m i n}$ to achieve coordination, we propose a simple single integrator model for $E_{m i n}$ as follows

{˙ E}_{m i n} = η

(19)

where $η \in Θ \subset R$ is a control input to manipulate $E_{m i n}$ ,and $Θ$ is being the set of all possible values of $η$ . It is useful to point out that $η$ has a default value of $η_{n o m} = 0$ unless modified by the proposed coordination framework.

V-a Coordination CBF

We propose a CBF approach to change the values of $E_{m i n}$ to ensure mutually exclusive use of the charging station. We define a coordination CBF $h_{c_{i j}}$ between robots $i$ and $j$ , as well as an associated pairwise safe set $C_{i j}$

C_{i j} = {(E_{m i n_{i}}, E_{m i n_{j}}) \in R^{2} : h_{c_{i j}} \geq 0} .

(20)

We use the same coordination CBF as in [7]

h_{c_{i j}} = log \frac{| T_{L_{i}} - T_{L_{j}} |}{δ_{t}}

(21)

and to get a constraint similar to (3)

\frac{T_{L_{i}} - T_{L_{j}}}{| T_{L_{i}} - T_{L_{j}} |^{2}} (θ_{i} η_{i} + β_{i} - β_{j}) \geq α (h_{c_{i j}})

(22)

where

\begin{matrix} θ_{i} = - \frac{1}{k_{e} + k_{v} ¯ V} β_{i} = \frac{- k_{e} - k_{v} V}{k_{e} + k_{v} ¯ V} - \frac{k_{v}}{w} \frac{(E - E_{m i n}) (V (t) - V (t - w))}{k_{e} + k_{v} ¯ V} {˙ T}_{L_{i}} = θ_{i} η_{i} + β_{i} \end{matrix}

where $V = | | v - v_{w} | |$ . For decentralized implementation, we dropped out the term $θ_{j}$ so the constraint equation is independent of $η_{j}$ , and provided both robots are adopting the constraint (22), each will try to stay in the safe set $C_{i j}$ . For the right hand side of (22) we use the following

(23)

which is inspired from [9] and leads to the favourable quality of converging to the safe set in a finite time, in case the initial condition is out of the safe set.

Theorem 2

[7, Theorem 2] For a pair of robots $(i, j)$ that belongs to a multi-robot system and satisfying $D_{i} > δ$ and $D_{j} > δ$ , and provided that $η \in Θ = R$ then $h_{c_{i j}}$ is a ZCBF. Moreover, if $(E_{m i n_{i}} (t_{0}), E_{m i n_{j}} (t_{0})) \notin C_{i j}$ , then the constraint (22) leads $(E_{m i n_{i}} (t), E_{m i n_{j}} (t))$ to converge to $\partial C_{i j}$ in finite time.

V-B Lower bound on $E_{m i n}$

Since $E_{m i n}$ is supposed to be the voltage at which the robot arrives to the charging station, then it is necessary to enforce a lower bound on its value to avoid any potential damage to the batteries or the loss of a robot with excessively low voltage. For this reason, we propose another CBF:

h_{L} = k_{s} (E_{m i n} - E_{l b})

(24)

where $E_{l b} > 0$ is the desired lower bound voltage and $k_{s} > 0$ is a scaling gain. Differentiating $h_{L}$ and obtaining the QP constraint gives

k_{s} η \geq - α (h_{L})

(25)

where $α (h_{L}) = p_{L} h_{L}$ for $p_{L} > 0$ . It can be easily shown that $h_{L}$ is a ZCBF, since $η \in Θ = R$ (no constraint on $η$ ) then there exists a control input $η$ that satisfies (25).

V-C System capacity description

To successfully apply the coordination CBF in a pairwise manner, the value of the desired $δ_{t}$ should be reasonable with respect to individual robot’s properties and the number of robots in the system (e.g. we can’t ask for $δ_{t}$ that is longer than the total discharge time of a battery). We consider the relation between the robots’ parameters, their number and the feasible limits on $δ_{t}$ as being an expression of the system’s capacity.

We propose a sufficient condition on the upper and lower limits of $δ_{t}$ , in relation to properties like maximum and minimum battery voltages, discharge and recharge rates, and the number of robots in the system.

Fig. 1: Schematic of a charging cycle with three robots. The red line represents the more needy robot, while the blue one is the least needy one, and it defines one recharging cycle.

For the sake of being conservative, we derive this capacity relation assuming that the system is pushed to its limits, meaning that all robots operate with the maximum average relative velocity w.r.t. wind $~ V$ . Suppose we have a group of $n$ robots, each has its own $E_{m i n}$ value, and one of them is the “neediest” robot that recharges first and most often, while another is the least needy one (represented in Figure 1 as the red and blue lines respectively). We want $t_{2} - t_{1} \geq δ_{t}$ , which means

\begin{matrix} t_{1} = \frac{E_{m a x} - E_{l b}}{k_{e} + k_{v} ~ V} t_{2} = \frac{E_{m a x} - {¯ E}_{M}}{k_{e} + k_{v} ~ V} + \frac{E_{m a x} - {¯ E}_{M}}{k_{c h}} + \frac{E_{m a x} - {¯ E}_{M}}{k_{e} + k_{v} ~ V} . \end{matrix}

(26)

Calculating $t_{2} - t_{1}$ and considering that ${¯ E}_{M} = E_{M} + ε$ , where $E_{M}$ being the actual value of $E_{m i n}$ of the neediest robot during the coordination, and $ε \geq 0$ being an additional increment of voltage to $E_{M}$ that is caused by the dependence of discharge rate on robot’s speed, we have:

E_{M} \leq \frac{(1 + \frac{k_{e} + k_{v} ~ V}{k_{c h}}) E_{m a x} + E_{l b} - δ_{t} (k_{e} + k_{v} ~ V) - κ ε}{κ}

(27)

where $κ = 2 + \frac{k_{e} + k_{v} ~ V}{k_{c h}}$ . We can then calculate $Δ E_{M} = \frac{E_{M} - E_{l b}}{n - 1}$ which is a uniform increment of $E_{m i n}$ between $E_{l b}$ and $E_{M}$ to create the desired separation of arrival times

Δ E_{M} = \frac{(1 + \frac{k_{e} + k_{v} ~ V}{k_{c h}}) (E_{m a x} - E_{l b}) - δ_{t} (k_{e} + k_{v} ~ V) - κ ε}{κ (n - 1)}

(28)

What we want then is to have $t_{1} - t_{3} \geq δ_{t}$ , meaning that the arrival times of the last two robots (or any two consecutive robots) to be at least $δ_{t}$

\frac{E_{m a x} - E_{l b}}{k_{e} + k_{v} ~ V} - \frac{E_{m a x} - (E_{l b} + Δ E_{M})}{k_{e} + k_{v} ~ V} \geq δ_{t}

(29)

and substituting 28 into the last equation we get

\begin{matrix} \frac{(1 + \frac{k_{e} + k_{v} ~ V}{k_{c h}}) (E_{m a x} - E_{l b}) - δ_{t} (k_{e} + k_{v} ~ V) - κ ε}{κ (n - 1)} - δ_{t} (k_{e} + k_{v} ~ V) \geq 0 \end{matrix}

(30)

then we obtain a critical value of $δ_{t}$ at which the inequality becomes an equality

δ_{t_{c r}} = \frac{(1 + \frac{k_{e} + k_{v} ~ V}{k_{c h}}) (E_{m a x} - E_{l b}) - κ ε}{(k_{e} + k_{v} ~ V) [1 + κ (n - 1)]} .

(31)

One final requirement on $δ_{t_{c r}}$ is to be greater than half the time taken to recharge a battery from $E_{l b}$ to $E_{m a x}$

δ_{t_{c r}} \geq \frac{E_{m a x} - E_{l b}}{2 k_{c h}}

(32)

The value of $δ_{t_{c r}}$ represents in this case an upper bound on the feasible $δ_{t}$ that can be achieved by the system. To motivate the need for $ε$ ³³3 More details on its derivation can be found in the appendix, we consider the critical case when $(E_{m i n_{i}}, E_{m i n_{j}}) \notin C_{i j}$ , in which case the QP produces $η_{i}$ that renders (22) an equality, thus ${˙ h}_{c_{i j}} = α (h_{c_{i j}})$ that reaches steady state in finite time (i.e. coordination achieved) at which ${˙ h}_{c_{i j}} = 0$ . Considering the case where all robots have same $¯ V = ~ V$ (which we already supposed when deriving $δ_{t_{c r}}$ ) then from the LHS of (22) we have $η_{i} = k_{v} (V_{j} - V_{i})$ . So if $V_{i}$ decreases (robot $i$ going to recharge for example), $η_{i}$ increases and so $ε = Δ E_{m i n_{i}}$ resulting from the increase in $η$ . The value of $ε$ can be estimated by approximating the integration of $η_{i}$ over the time it takes the robot to go back to the charging station. One approximation for $ε$ is

ε = \frac{k_{v} V_{n} ⎛ ⎜ ⎝ T_{e n d} - \frac{n (E_{m a x} - E_{l b}) - k_{c} log \frac{R_{0}}{δ} (1 + κ (n - 1))}{(k_{e} + k_{v} ~ V) (1 + κ (n - 1))} ⎞ ⎟ ⎠}{1 + \frac{k_{v} V_{n}}{k_{e} + k_{v} ~ V} (1 - \frac{1}{1 + κ (n - 1)})}

(33)

where $T_{e n d} = \frac{E_{m a x} - \frac{E_{m a x} + E_{l b}}{2}}{k_{e} + k_{v} ~ V}$ , and $V_{n}$ is the magnitude of the mission’s nominal velocity w.r.t. the wind velocity vector\@footnotemark.

Lemma 2

For a group of $n$ robots that have distinct values of $E_{m i n}$ that satisfy (31), (32) and (28), and provided they all operate such that their average relative velocity (w.r.t. wind) is equal to its upper bound, i.e. $¯ V = ~ V$ , let $z_{i}$ be the number of recharges that one robot can have in one charging cycle, then the maximum number of recharges for any robot is ${¯ z}_{i} = 2$ . Moreover, ${¯ E}_{M} \leq \frac{E_{m a x} + E_{l b}}{2}$ .

Lemma 3

For a group of $n$ robots, if $δ_{t}$ satisfies

\frac{E_{m a x} - E_{l b}}{2 k_{c h}} \leq δ_{t} \leq δ_{t_{c r}}

(34)

as well as equation (28), then there exists $E_{m} = {E_{m i n_{1}}, \dots, E_{m i n_{n}}}$ such that the difference in arrival times between any two robots is at least $δ_{t}$ (i.e. the scheduling problem is feasible).

V-D Feasibility of QP

In the proposed coordination framework so far $E_{m i n}$ , which is a 1-D value, is being manipulated to vary the arrival times of robots to the charging station. However, this can potentially cause a QP infeasibility problem. For example, a robot might need to use a negative $η$ to evade a neighbour’s arrival time, but at the same time it may need $η$ to be positive so as not to go below $E_{l b}$ . Some methods have been proposed to deal with this issue as in [15] and [6], and we adapt the core idea of the latter. To avoid the infeasibility problem, each agent carries out coordination only with its neighbour with the closest arrival time. Moreover, it gives higher priority for maintaining $E_{m i n} \geq E_{l b}$ over coordination. This way $η$ has to change to adapt one thing at a time and avoid potential infeasibility (see Algorithm 1).

Input:

T_{L_{k}}, \forall k \in N_{i}

Result:

A_{c}

and

B_{c}

for QP constraints

h_{c_{m i n}} = h_{0}

h_{L_{i}} = E_{m i n_{i}} - E_{l b}

while j in $N_{i}$ do

h_{c_{i j}} = log \frac{T_{L_{i}} - T_{L_{j}}}{δ}

if $h_{c_{i j}} < h_{c_{m i n}}$ and $D_{j} > δ$ then

h_{c_{m i n}} = h_{c_{i j}}

end if

end while

if $h_{c_{m i n}} < h_{L_{i}}$ then

A_{c} = L_{g} h_{c_{m i n}}

B_{c} = - L_{f} h_{c_{m i n}} - α (h_{c_{m i n}})

…(eqn. 22)

else

A_{c} = L_{g} h_{L_{i}}

B_{c} = - L_{f} h_{L_{i}} - α (h_{L_{i}})

…(eqn. 25)

end if

Algorithm 1 Coordination algorithm

The final QP is

		$u^{*} = min u \in R^{3}$		$\| \| u - u_{n o m} \| \|^{2}$		(35)
		$s.t.$		$A u \geq B$		(35)

where

\begin{matrix} A & = [\begin{matrix} A_{e}^{T} A_{c}^{T} \end{matrix}] = [\begin{matrix} L_{g} L_{f} h_{e} & 0 0_{1 \times 2} & A_{c}^{T} \end{matrix}], B & = [\begin{matrix} B_{e} B_{c} \end{matrix}] = [\begin{matrix} - L_{f}^{2} h_{e} - (p_{1} + p_{2}) {˙ h}_{e} - p_{1} p_{2} h_{e} B_{c} \end{matrix}] \end{matrix}

while $A_{c}$ and $B_{c}$ are determined from Algorithm (1).

Theorem 3

[7, Theorem 3] For a multi robot system of $n$ robots, with dynamics defined in (9), and each robot applying energy sufficiency, coordination and lower bound constraints defined in (13), (22) and (25), and provided that the inequalities (27) and (34) are satisfied, then Algorithm (1) ensures mutual exclusive use of the charging station.

Vi Results

In this section we present Matlab simulation results of the proposed framework, aiming to highlight its effectiveness, as well as the utility of the capacity estimation we propose. We tackled three different scenarios of a simple patrolling mission for a group of robots spinning around the charging station at a certain distance with a desired nominal mission speed. In these scenarios we have $δ = 0.2 $ m $$ , $R_{0} = 9 $ m $$ and we want to achieve $δ_{t} = 35 $ s $$ . The results are depicted in Figure 2, and the main parameters used are presented in Table I. For all the cases discussed, the $ε$ is calculated using (33).

Parameter	$k_{e}$	$k_{v}$	$k_{c h}$	$E_{m a x}$	$E_{l b}$
Value	0.005 $V / s$	0.015 $V / m$	0.2 $V / s$	14.8 $V$	12 $V$

TABLE I: Values of parameters used in simulation

Vi-a Base scenario

In this scenario we have a group of five robots that revolve around the charging station, with an upper bound of average relative velocity $~ V = 0.15 $ m / s $$ .

Each robot applies a proportional control on the speed to produce a nominal control input $u_{n o m} = - k_{d} (v - v_{n})$ , where $v_{n}$ is a nominal mission velocity and $k_{d} > 0$ is a gain. The value of $u_{n o m}$ is the one that goes into the QP (35). To generate $v_{n}$ for patrolling, we specify a desired magnitude $V_{n} = | | v_{n} | |$ then we use potential flow theory to specify the direction. We calculate a potential function $ϕ$ of a source near the charging station, and of a vortex near the boundary

ϕ = {\begin{matrix} m log D, if D < δ + Δ_{t o l} \frac{m}{2 π} θ_{p}, if D > R_{0} + Δ_{t o l} \end{matrix}

(36)

where $m > 0$ , $Δ_{t o l} > 0$ , $θ_{p} = ∠ (x - x_{c})$ and $v_{n} = V_{n} \frac{\nabla ϕ}{| | \nabla ϕ | |}$ .

The requirement is to have a $δ_{t} = 35 $ s $$ . The value of $δ_{t_{c r}}$ from (31) is $δ_{t_{c r}} = 36.39 $ s $$ for $ε = 0.24$ , and $\frac{E_{m a x} - E_{l b}}{2 k_{c h}} = 7 $ V $$ , thus (34) is satisfied. The evolution of voltages and $E_{m i n}$ values is depicted in figures 1(a) and 1(d).

Vi-B Base scenario with wind

Here we add a constant wind field of $v_{w} = (0.08, 0.08) $ m / s $$ and we have an upper bound $~ V = 0.2 $ m / s $$ . In this case $δ_{t_{c r}} = 31.9 $ s $ < δ_{t}$ for $ε = 0.28$ . Choosing to use 5 robots causes $E_{m i n}$ for some robots to go over $\frac{E_{m a x} + E_{l b}}{2}$ as shown in Figure 3 (when it should be less if it abides by the capacity condition (34), according to lemma 2), which is a sign of overloading the system. Reducing the robots to 4 gives $δ_{t_{c r}} = 41.1 $ s $ > δ_{t}$ for $ε = 0.27$ . $E (t)$ and $E_{m i n} (t)$ are depicted in Figs. 1(b) and 1(e).

Vi-C Base scenario with wind and less $k_{v}$

Here we consider the same previous scenario, but with robots having $k_{v} = 0.0045$ . Here for 5 robots $δ_{t_{c r}} = 48.3 $ s $$ for $ε = 0.14$ , which alludes to the possibility of adding a robot. Indeed, for 6 robots $δ_{t_{c r}} = 39.5 $ s $ > δ_{t}$ for $ε = 0.14$ . $E (t)$ and $E_{m i n} (t)$ are depicted in figures 1(c) and 1(f).

Fig. 3: Plot of $E_{m i n}$ when (34) is not satisfied, as described in the second scenario.

Vii Conclusions

In this paper we propose a CBF based framework for ensuring energy sufficiency of a multi-robot system while sharing one charging station in a mutually exclusive manner, given that the robots are affected by air drag and known constant wind fields.

As a future work we consider extending the current framework to allow for sharing multiple charging stations, as well as exploring the possibility of relaxing the assumption of having complete communication graph.

References

[1] A. D. Ames, S. Coogan, M. Egerstedt, G. Notomista, K. Sreenath, and P. Tabuada (2019) Control barrier functions: theory and applications. In 2019 18th European Control Conference (ECC), pp. 3420–3431. Cited by: §II-A, §II-A.
[2] A. D. Ames, X. Xu, J. W. Grizzle, and P. Tabuada (2016) Control barrier function based quadratic programs for safety critical systems. IEEE Transactions on Automatic Control 62 (8), pp. 3861–3876. Cited by: §II-A, §II-A, Definition 1.
[3] W. Burgard, M. Moors, C. Stachniss, and F. E. Schneider (2005) Coordinated multi-robot exploration. IEEE Transactions on robotics 21 (3), pp. 376–386. Cited by: §I.
[4] J. Cortes, S. Martinez, T. Karatas, and F. Bullo (2004) Coverage control for mobile sensing networks. IEEE Transactions on robotics and Automation 20 (2), pp. 243–255. Cited by: §I.
[5] Y. Ding, W. Luo, and K. Sycara (2019) Decentralized multiple mobile depots route planning for replenishing persistent surveillance robots. In 2019 International Symposium on Multi-Robot and Multi-Agent Systems (MRS), pp. 23–29. Cited by: §I.
[6] M. Egerstedt, J. N. Pauli, G. Notomista, and S. Hutchinson (2018) Robot ecology: constraint-based control design for long duration autonomy. Annual Reviews in Control 46, pp. 1–7. Cited by: §V-D.
[7] H. Fouad and G. Beltrame (2020) Energy autonomy for resource-constrained multi robot missions. In International Conference on Intelligent Robots and Systems (IROS), Cited by: Appendix G, §I, §I, §V-A, Theorem 2, Theorem 3.
[8] A. Kwok and S. Martinez (2007) Energy-balancing cooperative strategies for sensor deployment. In 2007 46th IEEE Conference on Decision and Control, pp. 6136–6141. Cited by: §I.
[9] A. Li, L. Wang, P. Pierpaoli, and M. Egerstedt (2018) Formally correct composition of coordinated behaviors using control barrier certificates. In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 3723–3729. Cited by: Appendix D, Appendix H, §V-A.
[10] G. Notomista, S. F. Ruf, and M. Egerstedt (2018) Persistification of robotic tasks using control barrier functions. IEEE Robotics and Automation Letters 3 (2), pp. 758–763. Cited by: Appendix C, §I, §I, §II-A, §IV.
[11] K. H. Petersen, R. Nagpal, and J. K. Werfel (2011) Termes: an autonomous robotic system for three-dimensional collective construction. Robotics: science and systems VII. Cited by: §I.
[12] D. Portugal and R. Rocha (2011) A survey on multi-robot patrolling algorithms. In Doctoral conference on computing, electrical and industrial systems, pp. 139–146. Cited by: §I.
[13] S. Slijepcevic and M. Potkonjak (2001) Power efficient organization of wireless sensor networks. In ICC 2001. IEEE International Conference on Communications. Conference Record (Cat. No. 01CH37240), Vol. 2, pp. 472–476. Cited by: §I.
[14] Z. Sun and J. Reif (2003) On energy-minimizing paths on terrains for a mobile robot. In 2003 IEEE International Conference on Robotics and Automation (Cat. No. 03CH37422), Vol. 3, pp. 3782–3788. Cited by: §I.
[15] L. Wang, A. D. Ames, and M. Egerstedt (2016) Multi-objective compositions for collision-free connectivity maintenance in teams of mobile robots. In 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 2659–2664. Cited by: §V-D.
[16] W. Xiao and C. Belta (2019) Control barrier functions for systems with high relative degree. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 474–479. Cited by: §II-B, §II-B, Definition 2.
[17] X. Xu, P. Tabuada, J. W. Grizzle, and A. D. Ames (2015) Robustness of control barrier functions for safety critical control. IFAC-PapersOnLine 48 (27), pp. 54–61. Cited by: §II-A.

Appendix A Proof of theorem 1

{proof}

Since $u \in R^{2}$ then there should be a value of control input that satisfies (13) provided that $L_{g} L_{f} h (x) \neq 0$ . $L_{g} L_{f} h (x)$ can be written as

L_{g} L_{f} h (x) = - k v \frac{(v - v_{w})^{T}}{| | v - v_{w} | |} - \frac{k_{c}}{D} \frac{(x - x_{c})^{T}}{D}

(37)

both expressions are basically unit vectors multiplied by an expression or a factor. If we want the second expression to dominate the first one (so even if both vectors are opposite, the summation will not be equal to zero), we pick $k_{c}$ so that the least possible value of $\frac{k_{c}}{D}$ be greater than $k_{v}$ so $\frac{k_{c}}{R_{0}} > k_{v} \Rightarrow k_{c} > R_{0} k_{v}$ , meaning $L_{g} L_{f} h (x) \neq 0$ .

Appendix B Proof of lemma 1

{proof}

To show this, it is useful to point out to the fact that the minimum value of the quadratic cost function of the QP (5) would be $u = u_{n o m}$ in case $u_{n o m}$ doesn’t violate the constraints on the QP. Otherwise, the QP produces a value of $u$ that abides with the constraint in the equality sense (produces a control input that renders the constraint as an equality).

Provided that the system starts in the safe set for $h_{e} > 0$ , then at some time $T_{b}$ the nominal control action will cause inequality (13) to be violated, in which case the QP produces a safe control input $u$ that follows the constraint in the sense of equality. Therefore the produced control input causes $h_{e}$ to vary in the following way

{¨ h}_{e} + (p_{1} + p_{2}) {˙ h}_{e} + p_{1} p_{2} h_{e} = 0

(38)

for which the solution is

h (t) = A e^{λ_{1} t} + B e^{λ_{2} t}

(39)

where $λ_{1} = \frac{1}{2} (- (p_{1} + p_{2}) + | p_{1} - p_{2} |)$ (the dominant mode), $λ_{2} = \frac{1}{2} (- (p_{1} + p_{2}) - | p_{1} - p_{2} |)$ , and the constants $A$ and $B$ are determined from the initial conditions on $h_{e}$ and ${˙ h}_{e}$ at the time $T_{b}$ .

When the robot arrives on the boundary of the charging station at time $t_{a}$ we have

h_{e} (t_{a}) = E (t_{a}) - E_{m i n} = A e^{λ_{1} t_{a}} + B e^{λ_{2} t_{a}}

(40)

thus by properly choosing $p_{1}$ and $p_{2}$ we can gauge how closely the robot tracks $E_{m i n}$ on arrival to the charging station. We also point out to the fact that $h_{e} = 0$ only at the boundary of the charging region, because if $E = E_{m i n}$ (which is the boundary of our safe set so to speak) we want this to be at $h_{e} = 0$ , which happens if $log \frac{D}{δ} = 0 \Rightarrow D = δ$ .

Since $h_{e}$ is a HOCBF, then any control input satisfying (13) renders the safe set forward invariant ( $h_{e} \geq 0$ ) so in case if $h_{e} = 0$ and being on the boundary at the same time, then $E - E_{m i n} = 0$ .

Appendix C A method for choosing $k_{c}$

In this discussion we provide a heuristic to choose the value of $k_{c}$ in the definition of the energy sufficiency CBF. The third term in the definition of $h_{e}$ signifies the voltage change that a robot needs to go back to the charging station [10]. The basic idea of choosing $k_{c}$ starts by supposing that a robot can use a PD controller to go back to the charging station, starting on the boundary of the operating range (i.e. $| | x_{0} | | = R_{0}$ ). For more conservatism, we suppose that there is a headwind with a magnitude of $| | v_{w} | |$ opposing the robot’s motion. Without loss of generality, we suppose that the robot is moving on a line so the robot’s motion is 1-D, and that the charging station is in the origin. In this case the system’s model will be

\begin{matrix} ˙ x & = v ˙ v & = - k_{p} x - k_{d} v - C_{d} (v - | | v_{w} | |) \end{matrix}

(41)

which is a second order ordinary differential equation, the solution of which is ⁴⁴4The solution has been obtained using symbolic manipulation in Matlab.

\begin{matrix} x (t) & = \frac{R_{0}}{G} [(L_{2} - c) e^{- L_{2} t} - (L_{1} - c) e^{- L_{1} t}] + \frac{C_{d} | | v_{w} | |}{G k_{p}} [L_{1} (e^{- L_{2} t} - 1) - L_{2} (e^{- L_{1} t} - 1)] v (t) & = \frac{C_{d} | | v_{w} | | - R_{0} k_{p}}{D} (e^{- L_{1} t} - e^{- L_{2} t}) \end{matrix}

(42)

where $c = k_{d} + C_{d}$ , $G = \sqrt{c^{2} - 4 k_{p}}$ , $L_{1} = \frac{c - G}{2}$ , $L_{2} = \frac{c + G}{2}$ . We then approximate the time needed to go from the initial position to a distance $δ$ from the center (arriving at the boundary of the charging region) by taking only the dominant terms in consideration, so the position equation will be

x (t) = (\frac{R_{0}}{G} (c - L_{1}) - \frac{C_{d} | | v_{w} | |}{G k_{p}} L_{2}) e^{- L_{1} t} + \frac{C_{d} | | v_{w} | |}{G k_{p}} L_{2}

(43)

thus the time at which $x (t) = δ$ is

Δ T = \frac{1}{L_{1}} log (\frac{- C_{d} | | v_{w} | | L_{2} + (c - L_{1}) k_{p} R_{0}}{- C_{d} | | v_{w} | | L_{2} + k_{p} G δ})

(44)

then in order to consider the voltage change during this trip back to the charging station, we can integrate the voltage rate $˙ E = - k_{e} - k_{v} | | v - v_{w} | |$ , however, to increase the conservatism in the estimate we choose to consider that the robot is moving on a constant speed equal to the maximum peak speed of $v (t)$ , which can be obtained by differentiating $v (t)$ and getting the time at which the differential is equal to zero and use the velocity at this time, and we call it $v^{*}$ which is expressed as

v^{*} = \frac{- R_{0} k_{p} + C_{d} | | v_{w} | |}{G} ⎛ ⎜ ⎝ {(\frac{L_{2}}{L_{1}})}^{\frac{- L_{2}}{L_{2} - L_{1}}} - {(\frac{L_{2}}{L_{1}})}^{\frac{- L_{1}}{L_{2} - L_{1}}} ⎞ ⎟ ⎠

(45)

and the voltage change needed becomes

\begin{matrix} Δ E = ˙ E Δ T = - \frac{k_{e} + k_{v} (| v^{*} | + | | v_{w} | |)}{L_{1}}      k_{c} log (\frac{- C_{d} | | v_{w} | | + (c - L_{1}) k_{p} G R_{0}}{- C_{d} | | v_{w} | | + k_{p} G δ}) \end{matrix}

(46)

however the current form of $Δ E$ does not necessarily satisfy the condition that $E = E_{m i n}$ only on the boundary of the charging region, so we choose

Δ E = - k_{c} log (\frac{D}{δ})

(47)

Appendix D Proof of Theorem 2

{proof}

Since $η \in Θ = R$ there exists a control action $η$ that satisfies (22)) (and keeps $C_{i j}$ invariant), then to show that $h_{c_{i j}}$ is a ZCBF, we need to ensure that $| T_{L_{i}} - T_{L_{j}} | \neq 0$ .

The only chance that this difference can be equal to zero is when one of the robots enters to the charging region. To show this, consider having two robots $(i, j)$ applying (22)and without loss of generality suppose that robot $j$ arrives at the charging station, so the difference in arrival times is

Δ T_{L_{i j}} = \frac{E_{i} - E_{m i n_{i}}}{k_{e} + k_{v} {¯ V}_{i}} - \frac{E_{j} - E_{m i n_{j}}}{k_{e} + k_{v} {¯ V}_{j}} > 0

(48)

it suffices to show that by the end of the charging process $Δ T_{i j} < 0$ which means that $Δ T_{i j} = 0$ at some point. To show this, we first point out that when the QP manipulates $η$ for coordination, then (22) becomes an equality, and due to the choice of $γ$ in (23), the right hand side will be equal to zero. Thus

η_{i} \approx - (k_{e} + k_{v} {¯ V}_{i}) (- \frac{k_{e} + k_{v} V_{j}}{k_{e} + k_{v} {¯ V}_{j}} + \frac{k_{e} + k_{v} V_{i}}{k_{e} + k_{v} {¯ V}_{i}})

(49)

notice that we neglected the expression $\frac{k_{v}}{w} \frac{(E - E_{m i n}) (V (t) - V (t - w))}{k_{e} + k_{v} ¯ V}$ because it can be significantly less than $\frac{k_{e} + k_{v} V_{i}}{k_{e} + k_{v} {¯ V}_{i}}$ for most cases of $w$ . An extreme case for (49) can be anticipated if we neglect $\frac{k_{e} + k_{v} V_{j}}{k_{e} + k_{v} {¯ V}_{j}}$ alltogether and take $V_{i} = max (V_{n}, ~ V)$ , so an extreme case for $η_{i}$ can be

η_{i} \approx - (k_{e} + k_{v} max {V_{n}, ~ V})

(50)

however if $| η_{i} |$ is less than $k_{c h}$ (by assumption) it means that $E_{j}$ increases faster than $E_{m i n}$ changes for both robots $(i, j)$ (noticing that for $η_{j}$ the bracket in (49) will be of reversed sign). Without loss of generality, for cases where $k_{c h} ≫ (k_{e} + k_{v} max {V_{n}, ~ V})$ we can consider the change in $E_{m i n}$ values is sufficiently slow that they can be considered constant, so from (48) the value of $T_{L_{j}}$ is increasing in a faster rate than $T_{L_{i}}$ is decreasing, and at some point $T_{L_{j}} = \frac{E_{m a x} - E_{m i n_{j}}}{k_{e} + k_{v} {¯ V}_{j}} > \frac{E_{i} - E m i n_{i}}{k_{e} + k_{v} {¯ V}_{i}} = T_{L_{i}}$ , which means that $Δ T_{L_{i j}} = 0$ at some point during the recharge.

The proof of the second part is the same as that of proposition III.1 in [9] and is omitted for brevity.

Remark 1

To demonstrate the fact that $k_{c h}$ is sufficiently big, a minimum threshold on $k_{c h}$ can be obtained by equating $δ_{t_{c r}}$ with $\frac{E_{m a x} - E_{l b}}{2}$ in (34). In other words, by doing so we can get a minimum acceptable value of $k_{c h}$ so that the capacity constraint (34) is technically satisfied. Doing so we get

k_{c h} = (k_{e} + k_{v} ~ V) [\frac{(2 (n - 1) Δ E + ε) \pm \sqrt{} (2 (n - 1) Δ E + ε)^{2} + 4 (n - 1) (Δ E - 2 ε) Δ E}{2 (Δ E - 2 ε)}]

(51)

where $Δ E = E_{m a x} - E_{l b}$ . If we set $ε = 0$ for simplicity, and for $n = 2$ we get $k_{c h} = (1 + \sqrt{2}) (k_{e} + k_{v} ~ V)$ . In practice, the value of $δ_{t_{c r}}$ is usually significantly larger than $\frac{E_{m a x} - E_{l b}}{2 k_{c h}}$ . Moreover the value of $n$ is bigger than two, which means that $k_{c h}$ is in practice significantly larger than $(k_{e} + k_{v} ~ V)$ .

Appendix E Proof of lemma 2

{proof}

We start by showing that

{¯ E}_{M} \leq \frac{E_{m a x} + E_{l b}}{2}

To do this, we calculate the difference

\begin{matrix} \frac{E_{m a x} + E_{l b}}{2} - {¯ E}_{M} = \frac{E_{m a x} + E_{l b}}{2} - \frac{(1 + \frac{k_{e} + k_{v} ~ V}{k_{c h}}) E_{m a x} + E_{l b} - δ_{t} (k_{e} + k_{v} ~ V)}{κ} \end{matrix}

(52)

where $κ = 2 + \frac{k_{e} + k_{v} ~ V}{k_{c h}}$ . This gives

\frac{E_{m a x} + E_{l b}}{2} - {¯ E}_{M} = \frac{(k_{e} + k_{v} ~ V)}{2 κ} (2 δ_{t} - \frac{E_{m a x} - E_{m i n}}{k_{c h}})

(53)

but due to the choice (32) then $\frac{E_{m a x} + E_{l b}}{2} - {¯ E}_{M} \geq 0$ This sets an upper bound on the value of $E_{m i n}$ of the most needy agent (with which it arrives to the charging station). Now the number of arrivals of a robot in a cycle is

ζ_{i} = 1 + ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ \frac{\frac{(E_{m a x} - E_{l b}) (1 + \frac{k_{e} + k_{v} ~ V}{k_{c h}})}{k_{e} + k_{v} ~ V}}{\frac{(E_{m a x} - {¯ E}_{M}) (1 + \frac{k_{e} + k_{v} ~ V}{k_{c h}})}{k_{e} + k_{v} ~ V}} ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦

(54)

where $⌊ . ⌋$ is the floor operator. Here the numerator represents the time the least needy robot (that defines the cycle) takes to discharge and recharge once, while the denominator expresses the same thing for the most needy robot. The ratio represents how many whole sections to which a cycle can be divided, or in other words, how many small cycles can we fit in the large one (i.e. how many visits the most needy robot can do in a cycle). Since we are considering the case where $¯ V = ~ V$ for all robots to be more conservative, then $ζ_{i}$ can be reduced to

ζ_{i} = 1 + ⌊ \frac{E_{m a x} - E_{l b}}{E_{m a x} - {¯ E}_{M}} ⌋

(55)

substituting the upper bound of ${¯ E}_{M}$ in the last equation

\begin{matrix} ζ_{i} & = 1 + ⎢ ⎢ ⎢ ⎢ ⎣ \frac{E_{m a x} - E_{l b}}{E_{m a x} - \frac{E_{m a x} + E_{l b}}{2}} ⎥ ⎥ ⎥ ⎥ ⎦ = 1 + ⌊ \frac{E_{m a x} - E_{l b}}{E_{m a x} - E_{l b}} ⌋ = 2 \end{matrix}

(56)

since this has been considered for the most needy robot, this means that all other robots, which have less $E_{m i n}$ values, visit the charging station at most two times per cycle. Notice that in this proof we used the more critical value of ${¯ E}_{M}$ at which the robot arrives to the charging station.

Appendix F Proof of lemma 3

{proof}

Since from lemma 2 we know that for any robot the maximum number of visits to the charging station is at most two, then the maximum number of total visits to the charging station within one cycle is $2 (n - 1)$ . Moreover, the total number of spaces between these visits (taking the start and end of the cycle into account) is $M = 2 (n - 1) + 1 = 2 n - 1$ . We then calculate the amount of available time between visits $δ_{a v}$ by dividing the cycle length (while still assuming that all robots operate such that $¯ V = ~ V$ ) and compare this quantity to $δ_{t_{c r}}$

δ_{a v} = \frac{(E_{m a x} - E_{l b}) (1 + \frac{k_{e} + k_{v} ~ V}{k_{c h}})}{(2 n - 1) (k_{e} + k_{v} ~ V)}

(57)

To check that $δ_{a v} > δ_{t_{c r}}$ we calculate the difference

\begin{matrix} δ_{a v} - δ_{t_{c r}} & = \frac{(E_{m a x} - E_{l b}) (1 + \frac{k_{e} + k_{v} ~ V}{k_{c h}})}{(k_{e} + k_{v} ~ V)} (\frac{1}{(2 n - 1)} - \frac{1}{1 + κ (n - 1)}) + \frac{κ ε}{k_{e} + k_{v} ~ V} \end{matrix}

(58)

but since $1 + 1 + κ (n - 1) = 2 n - 1 + \frac{k_{e} + k_{v} ~ V}{k_{c h}} (n - 1) > 2 n - 1$ , and that $κ ε > 0$ , then $δ_{a v} - δ_{t_{c r}} > 0$ , meaning that the available time is bigger than $δ_{t_{c r}}$ , which means a $δ_{t}$ satisfying (34) can be accommodated(since $δ_{t_{c r}}$ can be accommodated).

Appendix G Proof of Theorem 3

{proof}

[7, Theorem 3] From Algorithm (1), each robot is either applying the coordination CBF $h_{c_{i j}}$ or the lower bound CBF $h_{L}$ . For the robots which don’t apply $h_{L}$ , the value of the control input $η_{i}$ that respects (22) leads $E_{m i n_{i}}$ into safe set $C_{i j}$ with respect to its neighbour with the closest landing time (by virtue of theorem 2). Each robot applies this to its neighbour with the closest landing time ${(i, j) | j \in N_{i} and h_{c_{i j}} = {min}_{k \in N_{i}} h_{c_{i k}}}$ , eventually leading to $E_{m i n_{i}} \in C = ⋂ \forall i \neq j C_{i j}, \forall i$ . Moreover, since we have established the feasibility of the scheduling problem in Lemma (3), then we know that the sets $C_{i j}$ are nonempty and that a solution exists.

If a robot $i$ is applying the lower bound $h_{L}$ , then it can’t push its arrival time any further. In this case The nearest robot $j$ that applies the coordination CBF will have a control action $η_{j}$ that will lead $E_{m i n_{j}}$ to $C_{i j}$ (noticing that $C_{i j}$ is non empty), and then all other robots applying coordination CBF will coordinate in a pairwise fashion based on the neighbour of closest landing time as discussed in the previous point. If we add to the previous points the ability of each robot to arrive at the charging station at almost $E_{m i n}$ (by virtue of lemma 1), then mutual exclusive use of the charging station is satisfied.

Appendix H Estimation of $ε$ parameter

To motivate the need for $ε$ , let’s consider a pair of consecutive robots in the charging schedule which are manipulating $η_{i}$ so that their values of $E_{m i n}$ stay inside $C_{i j}$ or on its boundary. We are interested in the critical case when (22) is violated (when both $E_{m i n}$ values start outside $C_{i j}$ or approach to the boundary from the inside), in which case the QP produces values of $η$ that renders (22) an equality, hence ${˙ h}_{c_{i j}} = - α (h_{c_{i j}})$ , which reaches a steady state in finite time [9], i.e. ${˙ h}_{c_{i j}} = 0$ . Thus $η$ in (22) changes such that ${˙ h}_{c_{i j}} = 0$ after reaching the steady state. Supposing that both robots operate on the maximum nominal speed of the mission $V_{n}$ (relative w.r.t. wind) such that they have an equal average relative speed w.r.t. wind ${¯ V}_{i} = {¯ V}_{j}$ , then as ${˙ h}_{c_{i j}} = 0$ , from LHS of (22) we have $η_{i} = k_{v} (V_{j} - V_{i})$ . Suppose that robot $i$ goes back to the charging station and that its speed decreases exponentially from $V_{n}$ to $V_{f} ≪ V_{n}$ with a rate $a$ , then

{˙ E}_{m i n} = η = k_{v} V_{n} (1 - e^{- a t})

(59)

which means that as the exponential term decreases, $η$ increases and thus $E_{m i n}$ increases. In order to be able to estimate this increase, we need to integrate (59) from the time the robot starts moving towards the charging station till it arrives.

Considering the most needy robot as this robot $i$ ⁵⁵5Since we considered ${¯ E}_{M} = E_{M} + ε$ for the most needy agent and defined $δ_{t_{c r}}$ based on that, then we can say that the arrival time $T_{e n d}$ in the most critical case is

T_{e n d} = \frac{E_{m a x} - {¯ E}_{M}}{k_{e} + k_{v} ~ V} = \frac{E_{m a x} - \frac{E_{m a x} + E_{m i n}}{2}}{k_{e} + k_{v} ~ V}

(60)

notice here that for agent $i$ in the above equation, the average speed expression may include the mission segment (at which the robot operates at a speed equal to $V_{n}$ ), and the approach where the speed decreases, so for conservativeness we suppose that ${¯ V}_{i} = ~ V$ , which is the same thing we did on deriving $δ_{t_{c r}}$ . An example demonstration for the aforementioned velocities is in Figure 4.

Fig. 4: Demonstration of the maximum average relative velocity w.r.t. wind $~ V$ , the average velocity $¯ V$ and the nominal mission velocity $V_{n}$ for a robot revolving around the charging station.

To estimate the time at which the neediest robot starts approaching the charging station $T_{s t a r t}$ , we can approximate it as being the time at which $h_{e} = 0$ for this robot, while supposing it is operating at the boundary of the operating range $R$ ⁶⁶6This approximation is based on the idea that the safe control input described by the constraints of the QP start taking over when the states of the system are close to the boundary of the safe set ( $h_{e} = ϵ$ , where $ϵ ≪$ ).. This means

E (T_{s t a r t}) - E_{m i n} (T_{s t a r t}) - k_{c} log \frac{R_{0}}{δ} = 0

(61)

we can take $E (t) = E_{m a x} - (k_{e} + k_{v} ~ V) (t - t_{0})$ where $t_{0} = 0$ (considering the first cycle) and we can take $E_{m i n} (T_{s t a r t}) = E_{M}$ . Substituting in the last equation we get

T_{s t a r t} = \frac{E_{m a x} - E_{M} - k_{c} log \frac{R_{0}}{δ}}{k_{e} + k_{v} ~ V}

(62)

substituting (27) in the last equation we get

\begin{matrix} T_{s t a r t} & = \frac{ε}{k_{e} + k_{v} ~ V} (1 - \frac{1}{1 + κ (n - 1)}) + \frac{n (E_{m a x} - E_{l b}) - k_{c} (1 + κ (n - 1)) log \frac{R_{0}}{δ}}{(1 + κ (n - 1)) (k_{e} + k_{v} ~ V)} \end{matrix}

(63)

Supposing that the robot decreases its velocity from $V_{n}$ to $v_{f}$ in an amount of time equal to $T_{e n d} - T_{s t a r t}$ , then

\begin{matrix} v_{f} = V_{n} e^{- a (T_{e n d} - T_{s t a r t})} \end{matrix}

(64)

and

a = - \frac{1}{T_{e n d} - T_{s t a r t}} log \frac{v_{f}}{V_{n}}

(65)

Now in order to calculate the increase in $E_{m i n}$

\begin{matrix} ε & = k_{v} V_{n} \int_{0}^{T_{e n d} - T_{s t a r t}} (1 - e^{- a t}) d t = k_{v} V_{n} {[t + \frac{1}{a} e^{- a t}]}_{0}^{- a t} = k_{v} V_{n} [T_{e n d} - T_{s t a r t} + \frac{1}{a} (\frac{v_{f}}{} V_{n} - 1)] = k_{v} V_{n} ⎡ ⎢ ⎣ 1 + \frac{1}{log \frac{V_{n}}{v_{f}}} (\frac{v_{f}}{V_{n}} - 1) ⎤ ⎥ ⎦      Γ (T_{e n d} - T_{s t a r t}) \end{matrix}

(66)

the smaller the choice of $v_{f}$ , the closer $Γ$ approaches one, and the more conservative the estimate of $ε$ will be. Substituting (60) and (63) in the above equation we get

ε = \frac{Γ k_{v} V_{n} ⎛ ⎜ ⎝ T_{e n d} - \frac{n (E_{m a x} - E_{l b}) - k_{c} (1 + κ (n - 1) log \frac{R_{0}}{δ}}{(k_{e} + k_{v} ~ V) (1 + κ (n - 1)} ⎞ ⎟ ⎠}{1 + \frac{Γ k_{v} V_{n}}{k_{e} + k_{v} ~ V} (1 - \frac{1}{1 + κ (n - 1)})}

(67)

Multi-robot energy autonomy with wind and constrained resources

Abstract

I Introduction

Ii Preliminaries

Ii-a Control Barrier Functions (CBF)

Definition 1

Ii-B Higher order control barrier functions (HOCBF)

Definition 2

Iii Problem formulation

Iv Energy sufficiency

Theorem 1

Lemma 1

V Coordination

V-a Coordination CBF

Theorem 2

V-B Lower bound on Emin

V-C System capacity description

Lemma 2

Lemma 3

V-D Feasibility of QP

Theorem 3

Vi Results

Vi-a Base scenario

Vi-B Base scenario with wind

Vi-C Base scenario with wind and less kv

Vii Conclusions

References

Appendix A Proof of theorem 1

Appendix B Proof of lemma 1

Appendix C A method for choosing kc

Appendix D Proof of Theorem 2

Remark 1

Appendix E Proof of lemma 2

Appendix F Proof of lemma 3

Appendix G Proof of Theorem 3

Appendix H Estimation of ε parameter

V-B Lower bound on $E_{m i n}$

Vi-C Base scenario with wind and less $k_{v}$

Appendix C A method for choosing $k_{c}$

Appendix H Estimation of $ε$ parameter