Multirobot energy autonomy with wind and constrained resources
Abstract
One aspect of the evergrowing need for long term autonomy of multirobot systems, is ensuring energy sufficiency. In particular, in scenarios where charging facilities are limited, batterypowered 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 missionagnostic 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 multirobot 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 multirobot systems, with the aim of providing more practical and robust systems.
Energy autonomy, the ability of the robots in a multirobot system to replenish their energy reserves, is particularly important to extend mission duration and general survivability.
Earlier interest in optimizing energy consumption in a multirobot 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 multirobot 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 multirobot 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 CBFbased 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
Iia 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
(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 such that [1]:
(2) 
where ensuring implies the safe set is positively invariant. For a control affine system, having a control action that achieves
(3) 
where is an extended type function, ensures positive invariance of .
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 a continuously differentiable function is called a ZCBF if there exists an extended class function such that
(4) 
The set [2] is defined as
and it is the set that contains all the safe control inputs, thus choosing a Lipschitz continuous controller ensures forward invariance of and system’s safety.
To mix the safety control input with an arbitrary mission’s control input , we use a quadratic program: [10]
(5)  
IiB Higher order control barrier functions (HOCBF)
If is of a higher relative degree (the control action doesn’t appear after differentiating once, i.e. ), 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 order differentiable function
(6) 
where are class functions. Also we define the following series of sets
(7) 
Definition 2
Iii Problem formulation
We assume robots moving in a given wind field with the following dynamics:
(9) 
where is the robot’s position, is its velocity, are coefficients of linear drag, recharge, static and dynamic discharge respectively. Also is the robot’s voltage, is the control input (no constraints on the control input), and is a known wind vector. Moreover we suppose that all the robots operate in a certain known operational range , where is a closed set, and the size of this operational range is described by the operational radius . The robots are carrying out a mission specified by and they have one charging station at a known location (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 .
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^{1}^{1}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 ) 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 . We take inspiration from [10], but we extend it to accommodate the system dynamics in (9). The candidate CBF is
(10) 
where ^{2}^{2}2The choice of is explained in the appendix. The first derivative of this function is
(11) 
so we need to differentiate twice for the control input to appear
(12) 
with the second and third expressions being . We can then create an inequality similar to (8) using and
(13) 
and and 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 , then is a HOCBF.
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 , they arrive to the charging station at different times. We propose a method for changing the values of to achieve the aforementioned coordination.
To get this expression, we integrate the voltage relation in (9) to get
(14) 
Supposing we have the average relative speed , the last integral can be replaced and the arrival time becomes
(15) 
We then replace in the last expression by to get an expression for that changes with time
(16) 
In this work, we use a moving average to estimate the average velocity relative to wind defined as
(17) 
where 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
(18) 
To be able to change to achieve coordination, we propose a simple single integrator model for as follows
(19) 
where is a control input to manipulate ,and is being the set of all possible values of . It is useful to point out that has a default value of unless modified by the proposed coordination framework.
Va Coordination CBF
We propose a CBF approach to change the values of to ensure mutually exclusive use of the charging station. We define a coordination CBF between robots and , as well as an associated pairwise safe set
(20) 
We use the same coordination CBF as in [7]
(21) 
and to get a constraint similar to (3)
(22) 
where
where . For decentralized implementation, we dropped out the term so the constraint equation is independent of , and provided both robots are adopting the constraint (22), each will try to stay in the safe set . 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.
VB Lower bound on
Since 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:
(24) 
where is the desired lower bound voltage and is a scaling gain. Differentiating and obtaining the QP constraint gives
(25) 
where for . It can be easily shown that is a ZCBF, since (no constraint on ) then there exists a control input that satisfies (25).
VC System capacity description
To successfully apply the coordination CBF in a pairwise manner, the value of the desired 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 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 as being an expression of the system’s capacity.
We propose a sufficient condition on the upper and lower limits of , in relation to properties like maximum and minimum battery voltages, discharge and recharge rates, and the number of robots in the system.
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 . Suppose we have a group of robots, each has its own 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 , which means
(26) 
Calculating and considering that , where being the actual value of of the neediest robot during the coordination, and being an additional increment of voltage to that is caused by the dependence of discharge rate on robot’s speed, we have:
(27) 
where . We can then calculate which is a uniform increment of between and to create the desired separation of arrival times
(28) 
What we want then is to have , meaning that the arrival times of the last two robots (or any two consecutive robots) to be at least
(29) 
and substituting 28 into the last equation we get
(30) 
then we obtain a critical value of at which the inequality becomes an equality
(31) 
One final requirement on is to be greater than half the time taken to recharge a battery from to
(32) 
The value of represents in this case an upper bound on the feasible that can be achieved by the system. To motivate the need for ^{3}^{3}3 More details on its derivation can be found in the appendix, we consider the critical case when , in which case the QP produces that renders (22) an equality, thus that reaches steady state in finite time (i.e. coordination achieved) at which . Considering the case where all robots have same (which we already supposed when deriving ) then from the LHS of (22) we have . So if decreases (robot going to recharge for example), increases and so resulting from the increase in . The value of can be estimated by approximating the integration of over the time it takes the robot to go back to the charging station. One approximation for is
(33) 
where , and is the magnitude of the mission’s nominal velocity w.r.t. the wind velocity vector\@footnotemark.
Lemma 2
For a group of robots that have distinct values of 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. , let be the number of recharges that one robot can have in one charging cycle, then the maximum number of recharges for any robot is . Moreover, .
Lemma 3
For a group of robots, if satisfies
(34) 
as well as equation (28), then there exists such that the difference in arrival times between any two robots is at least (i.e. the scheduling problem is feasible).
VD Feasibility of QP
In the proposed coordination framework so far , which is a 1D 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 . 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 over coordination. This way has to change to adapt one thing at a time and avoid potential infeasibility (see Algorithm 1).
Theorem 3
[7, Theorem 3] For a multi robot system of 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 , and we want to achieve . 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  

Value  0.005  0.015  0.2  14.8  12 
Via 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 .
Each robot applies a proportional control on the speed to produce a nominal control input , where is a nominal mission velocity and is a gain. The value of is the one that goes into the QP (35). To generate for patrolling, we specify a desired magnitude 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
(36) 
where , , and .
ViB Base scenario with wind
Here we add a constant wind field of and we have an upper bound . In this case for . Choosing to use 5 robots causes for some robots to go over 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 for . and are depicted in Figs. 1(b) and 1(e).
ViC Base scenario with wind and less
Vii Conclusions
In this paper we propose a CBF based framework for ensuring energy sufficiency of a multirobot 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] (2019) Control barrier functions: theory and applications. In 2019 18th European Control Conference (ECC), pp. 3420–3431. Cited by: §IIA, §IIA.
 [2] (2016) Control barrier function based quadratic programs for safety critical systems. IEEE Transactions on Automatic Control 62 (8), pp. 3861–3876. Cited by: §IIA, §IIA, Definition 1.
 [3] (2005) Coordinated multirobot exploration. IEEE Transactions on robotics 21 (3), pp. 376–386. Cited by: §I.
 [4] (2004) Coverage control for mobile sensing networks. IEEE Transactions on robotics and Automation 20 (2), pp. 243–255. Cited by: §I.
 [5] (2019) Decentralized multiple mobile depots route planning for replenishing persistent surveillance robots. In 2019 International Symposium on MultiRobot and MultiAgent Systems (MRS), pp. 23–29. Cited by: §I.
 [6] (2018) Robot ecology: constraintbased control design for long duration autonomy. Annual Reviews in Control 46, pp. 1–7. Cited by: §VD.
 [7] (2020) Energy autonomy for resourceconstrained multi robot missions. In International Conference on Intelligent Robots and Systems (IROS), Cited by: Appendix G, §I, §I, §VA, Theorem 2, Theorem 3.
 [8] (2007) Energybalancing cooperative strategies for sensor deployment. In 2007 46th IEEE Conference on Decision and Control, pp. 6136–6141. Cited by: §I.
 [9] (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, §VA.
 [10] (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, §IIA, §IV.
 [11] (2011) Termes: an autonomous robotic system for threedimensional collective construction. Robotics: science and systems VII. Cited by: §I.
 [12] (2011) A survey on multirobot patrolling algorithms. In Doctoral conference on computing, electrical and industrial systems, pp. 139–146. Cited by: §I.
 [13] (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] (2003) On energyminimizing 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] (2016) Multiobjective compositions for collisionfree connectivity maintenance in teams of mobile robots. In 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 2659–2664. Cited by: §VD.
 [16] (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: §IIB, §IIB, Definition 2.
 [17] (2015) Robustness of control barrier functions for safety critical control. IFACPapersOnLine 48 (27), pp. 54–61. Cited by: §IIA.
Appendix A Proof of theorem 1
{proof}Since then there should be a value of control input that satisfies (13) provided that . can be written as
(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 so that the least possible value of be greater than so , meaning .
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 in case doesn’t violate the constraints on the QP. Otherwise, the QP produces a value of 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 , then at some time the nominal control action will cause inequality (13) to be violated, in which case the QP produces a safe control input that follows the constraint in the sense of equality. Therefore the produced control input causes to vary in the following way
(38) 
for which the solution is
(39) 
where (the dominant mode),, and the constants and are determined from the initial conditions on and at the time .
When the robot arrives on the boundary of the charging station at time we have
(40) 
thus by properly choosing and we can gauge how closely the robot tracks on arrival to the charging station. We also point out to the fact that only at the boundary of the charging region, because if (which is the boundary of our safe set so to speak) we want this to be at , which happens if .
Since is a HOCBF, then any control input satisfying (13) renders the safe set forward invariant () so in case if and being on the boundary at the same time, then .
Appendix C A method for choosing
In this discussion we provide a heuristic to choose the value of in the definition of the energy sufficiency CBF. The third term in the definition of signifies the voltage change that a robot needs to go back to the charging station [10]. The basic idea of choosing 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. ). For more conservatism, we suppose that there is a headwind with a magnitude of 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 1D, and that the charging station is in the origin. In this case the system’s model will be
(41) 
which is a second order ordinary differential equation, the solution of which is ^{4}^{4}4The solution has been obtained using symbolic manipulation in Matlab.
(42) 
where , ,,. 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
(43) 
thus the time at which is
(44) 
then in order to consider the voltage change during this trip back to the charging station, we can integrate the voltage rate , 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 , which can be obtained by differentiating and getting the time at which the differential is equal to zero and use the velocity at this time, and we call it which is expressed as
(45) 
and the voltage change needed becomes
(46) 
however the current form of does not necessarily satisfy the condition that only on the boundary of the charging region, so we choose
(47) 
Appendix D Proof of Theorem 2
{proof}Since there exists a control action that satisfies (22)) (and keeps invariant), then to show that is a ZCBF, we need to ensure that .
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 applying (22)and without loss of generality suppose that robot arrives at the charging station, so the difference in arrival times is
(48) 
it suffices to show that by the end of the charging process which means that 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
(49) 
notice that we neglected the expression because it can be significantly less than for most cases of . An extreme case for (49) can be anticipated if we neglect alltogether and take