Persistent surveillance for unmanned aerial vehicles subject to charging and temporal logic constraints

Abstract

In this work, we present a novel method for automating persistent surveillance missions involving multiple vehicles. Automata-based techniques are used to generate collision-free motion plans for a team of vehicles to satisfy a temporal logic specification. Vector fields are created for use with a differential flatness-based controller, allowing vehicle flight and deployment to be fully automated according to the motion plans. The use of charging platforms with the vehicles allows for truly persistent missions. Experiments were performed with two quadrotors for two different missions over 50 runs each to validate the theoretical results.

Appendices

Appendix 1: Derivation of time bounds

The derivation for (6) follows the same structure as that of (5), which can be found in Aydin Gol and Belta (2013). That derivation involves finding the minimum velocity vector towards the exit facet, and solving a linear system to find the time taken to exit at that velocity. In our work, however, the minimum velocity towards the exit facet may be zero, and so an alternate method must be used to compute the time bound. For this derivation, we assume that positive x is the direction of the desired exit facet, as displayed in Fig. 13. In the event that the minimum magnitude of velocity towards the exit facet is zero, we restrict velocity in one of the other coordinates to be non-zero away from the other facets, which in this figure is the y direction, but holds also for the z direction. Following from (4),

$$\begin{aligned} \dot{x}=\frac{b_i-x}{b_i-a_i}s_{\bar{F}}+\left( 1-\frac{b_i-x}{b_i-a_i}\right) s_F, \end{aligned}$$

(28)

where $s_F$ and $s_{\bar{F}}$ are the vectors in the x direction away from the exit facet F and the opposite facet $\bar{F}$. But the magnitude of $\dot{x}$ depends on the y position through $s_F$ and $s_{\bar{F}}$.

Fig. 13

Vector field with zero-magnitude component for deriving time bounds

We separate the x and y directions in order to bound the time to exit the cube without needing to solve the coupled nonlinear equations of the vector field. First, we note that in (28),

$$\begin{aligned} s_F = \left( 1-\frac{b_j-y}{b_j-a_j}\right) h, \end{aligned}$$

(29)

where h is the magnitude of the vector at the corner of the cube in the y direction. We write the dynamics for the y direction as

$$\begin{aligned} \dot{y}=\frac{b_j-y}{b_j-a_j}h+\left( 1-\frac{b_i-y}{b_j-a_j}\right) \left( -h\right) , \end{aligned}$$

(30)

which rearranges to

$$\begin{aligned} \dot{y} = -\frac{2h}{b_j-a_j}y+h. \end{aligned}$$

(31)

This equation asymptotically approaches equilibrium at

$$\begin{aligned} y = \frac{b_j-a_j}{2} \end{aligned}$$

(32)

which means that getting a finite solution for time to equilibrium is not possible. However, we can solve for the time to some fraction of its equilibrium, $y^*=M\frac{b_j-a_j}{2}$, where $0<M<1$. The linear system in (31) can be solved explicitly for the time to reach $y^*$ as

$$\begin{aligned} t_y = \frac{b_j-a_j}{-2h}\ln \left( 1-M\right) . \end{aligned}$$

(33)

Then, we can substitute $M\frac{b_j-a_j}{2}$ for y in (29) to get

$$\begin{aligned} \dot{x} = \frac{\frac{M}{2}-1}{b_i-a_i}hx+h, \end{aligned}$$

(34)

which can be solved explicity for the time to reach $x = b_i$, yielding

$$\begin{aligned} t_x = \frac{b_i-a_i}{h\left( \frac{M}{2}-1\right) }\ln \left( \frac{M}{2}\right) . \end{aligned}$$

(35)

Adding (33) and (35) yields the time bound in (6).

To solve for the value of M that gives the tightest bound, we must take the derivative of (33) and (35). Starting with (33), we find

$$\begin{aligned} \frac{dt_y}{dM}=\left( \frac{b_j-a_j}{-2s_{\bar{F}}}\right) \left( \frac{1}{M-1}\right) . \end{aligned}$$

(36)

Similarly, taking the derivative of (35) yields

$$\begin{aligned} \frac{dt_x}{dM}= & {} \frac{1}{M}\left( \frac{b_i-a_i}{s_F\left( \frac{M}{2}-1\right) }\right) \nonumber \\&-2\ln \left( \frac{M}{2}\right) \left( \frac{b_i-a_i}{s_F}\right) \frac{1}{\left( M-2\right) ^2}. \end{aligned}$$

(37)

The quantities $b_i-a_i$, $b_j-a_j$, $s_F$, and $s_{\bar{F}}$ are all non-negative, and hence we can replace $\left( \frac{b_i-a_i}{s_{F}}\right)$ with A and $\left( \frac{b_j-a_j}{2s_{\bar{F}}}\right)$ with B and rearrange to get (7). Since (6) is convex, the solution to (7) corresponds to a value of M such that the time bound given by (6) is minimized.

Appendix 2: Analytical calculation of vector field derivatives

As with calculation of acceleration in (22), jerk j can be computed by applying the Jacobian to the acceleration as

$$\begin{aligned} j= & {} \dot{a}\left( v\left( p\left( t\right) \right) ,p\left( t\right) \right) =\frac{\partial a}{\partial p}\frac{dp}{dt}\nonumber \\= & {} \begin{bmatrix} \frac{\partial a_1}{\partial p_1}&\quad \frac{\partial a_1}{\partial p_2}&\quad \frac{\partial a_1}{\partial p_3} \\ \vdots&\quad \vdots&\quad \vdots \\ \frac{\partial a_3}{\partial p_1}&\quad \frac{\partial a_3}{\partial p_2}&\quad \frac{\partial a_3}{\partial p_3} \end{bmatrix} \begin{bmatrix} v_1 \\ v_2 \\ v_3 \end{bmatrix}. \end{aligned}$$

(38)

The partial derivatives of acceleration can be solved by differentiating the terms for acceleration to get

$$\begin{aligned} \frac{\partial a_i}{\partial p_j}= \begin{bmatrix} \frac{\partial J_{i1}}{\partial p_j}&\quad \frac{\partial J_{i2}}{\partial p_j}&\quad \frac{\partial J_{i3}}{\partial p_j} \end{bmatrix} \begin{bmatrix} v_1 \\ v_2 \\ v_3 \end{bmatrix}+ \begin{bmatrix} J_{i1}&\quad J_{i2}&\quad J_{i3} \end{bmatrix} \begin{bmatrix} J_{1j} \\ J_{2j} \\ J_{3j} \end{bmatrix},\nonumber \\ \end{aligned}$$

(39)

where $J_{ij}$ is the Jacobian as defined in (23). These partial derivatives can be solved as

$$\begin{aligned} \frac{\partial J_{ij}}{\partial p_k}= \begin{bmatrix} \frac{\partial ^2c_1}{\partial p_j\partial p_k}&\quad \cdots&\quad \frac{\partial ^2c_8}{\partial p_j\partial p_k} \end{bmatrix} \begin{bmatrix} h_{1i} \\ \vdots \\ h_{8i} \end{bmatrix}. \end{aligned}$$

(40)

In this equation, $h_{ij}$ is the $p_j{th}$ component of the vector at the ith vertex, and the $c_i$’s are the coefficients calculated in (21).

The same process is used to calculate snap:

$$\begin{aligned} \frac{\partial j}{\partial p}\frac{dp}{dt}= \begin{bmatrix} \frac{\partial j_1}{\partial p_1}&\quad \frac{\partial j_1}{\partial p_2}&\quad \frac{\partial j_1}{\partial p_3} \\ \vdots&\vdots&\vdots \\ \frac{\partial j_3}{\partial p_1}&\frac{\partial j_3}{\partial p_2}&\frac{\partial j_3}{\partial p_3} \end{bmatrix} \begin{bmatrix} v_1 \\ v_2\\ v_3 \end{bmatrix} \end{aligned}$$

(41)

$$\begin{aligned} \frac{\partial j_i}{\partial p_j}= & {} \begin{bmatrix} \frac{\partial ^2 a_i}{\partial p_1 \partial p_j}&\frac{\partial ^2 a_i}{\partial p_2 \partial p_j}&\frac{\partial ^2 a_i}{\partial p_3 \partial p_j} \end{bmatrix}\begin{bmatrix} v_1 \\ v_2 \\ v_3 \end{bmatrix}+ \begin{bmatrix} \frac{\partial a_i}{\partial p_1}&\quad \frac{\partial a_i}{\partial p_2}&\quad \frac{\partial a_i}{\partial p_3} \end{bmatrix} \nonumber \\&\times \begin{bmatrix} J_{1j} \\ J_{2j} \\ J_{3j} \end{bmatrix} \end{aligned}$$

(42)

All of the terms in (42) have been calculated previously in (4), (23), and (39), except the second partial derivatives of acceleration, which can be expressed as

$$\begin{aligned} \frac{\partial ^2 a_i}{\partial p_j \partial p_k}&= \begin{bmatrix} \frac{\partial ^2 J_{i1}}{\partial p_j \partial p_k}&\quad \frac{\partial ^2 J_{i2}}{\partial p_j \partial p_k}&\quad \frac{\partial ^2 J_{i3}}{\partial p_j \partial p_k} \end{bmatrix} \begin{bmatrix} v_1 \\ v_2 \\ v_3 \end{bmatrix} \nonumber \\&\quad + \begin{bmatrix} \frac{\partial J_{i1}}{\partial p_j \partial p_k}&\quad \frac{\partial J_{i2}}{\partial p_j \partial p_k}&\quad \frac{\partial J_{i3}}{\partial p_j \partial p_k} \end{bmatrix} \begin{bmatrix} J_{1j}\\ J_{2j}\\ J_{3j} \end{bmatrix} \nonumber \\&\quad + \begin{bmatrix} \frac{\partial J_{i1}}{\partial p_k}&\quad \frac{\partial J_{i2}}{\partial p_k}&\quad \frac{\partial J_{i3}}{\partial p_k} \end{bmatrix} \begin{bmatrix} J_{1j}\\ J_{2j}\\ J_{3j} \end{bmatrix} \nonumber \\&\quad + \begin{bmatrix} J_{i1}&\quad J_{i2}&\quad J_{i3} \end{bmatrix} \begin{bmatrix} \frac{\partial J_{1j}}{\partial p_k}\\ \frac{\partial J_{2j}}{\partial p_k}\\ \frac{\partial J_{3j}}{\partial p_k} \end{bmatrix}. \end{aligned}$$

(43)

Again, each of these terms is known except the second partial derivatives of the elements of the Jacobian matrix, which are written as

$$\begin{aligned} \frac{\partial ^2 J_{ij}}{\partial p_k \partial p_l}= \begin{bmatrix} \frac{\partial ^2 c_1}{\partial p_j \partial p_k \partial p_l}&\quad \cdots&\quad \frac{\partial ^2 c_8}{\partial p_j \partial p_k \partial p_l} \end{bmatrix} \begin{bmatrix} h_{1i}\\ \vdots \\ h_{8i} \end{bmatrix}. \end{aligned}$$

(44)

Thus all elements are known, and acceleration, jerk and snap can be expressed as functions of position, velocity, and partial derivatives of the coefficients calculated in (21). Analytical computation in these forms allows for efficient online computation of the parameters needed for the vector field based controller used in the experiments.