$$\newcommand{\vect}[1]{\underline{#1}} % vector \newcommand{\mat}[1]{\mathbf{#1}} % matrices \newcommand{\est}[1]{\hat{#1}} % estimate \newcommand{\err}[1]{\tilde{#1}} % error \newcommand{\esterr}[1]{\tilde{#1}} % error \newcommand{\pd}[2]{\frac{\partial{#1}}{\partial{#2}}} % partial derivatives \newcommand{\transp}[1]{#1^{T}} % transpose \newcommand{\inv}[1]{#1^{-1}} % invert \newcommand{\norm}[1]{|{#1}|} % norm \newcommand{\esp}[1]{\mathbb{E}\left[{#1}\right]} % expectation \newcommand{\identity}[0]{\mathbb{I}} % identity \newcommand{\jac}[3]{\frac{\partial{#1}}{\partial{#2}}|_{#3}} % Jacobian$$

1: Introduction

We consider a drone and a set of targets in an euclidian planar environment. The targets are moving in a uniform rectilinear motion. The drone is moving at a constant forward velocity with a piecewise constant heading. Our goal is to compute the optimal trajectory for the drone, i.e. the trajectory leading to the fastest interception of all targets as depicted on figure 0.

Fig0. - Drone target interception thingy principle. Let's play sheepdog

2: Single target

2.1: Derivation

2.2: implementation

The above computation is implemented as follow

code

This first test runs our computation on a set of harcoded examples and displays the results as shown on figure 1. It additionally measures that my circa 2014 laptop is able to run this function at 10kHz.

Fig1. - Interception examples.

3: Multiple targets

3.1: Implementation

When considering our initial problem, a set of targets, all that is left to do is to decide the sequence in which the interceptions will proceed. With this information in hand, we apply our previous computation iteratively to the sequence of targets as follows:

We start feeling the need of a way to store and describe scenarios, which we quench in the following way:

Click for details

scenario_2.yaml

We create a 6 targets scenari with increasing headings and intercept them in order. This leads to the spiral like trajectory depicted on figure 2

Fig2. - Interception examples with 6 targets.

3.2: Exhaustive search

For scenario with small number of targets, sequences of targets can be exhaustively searched for the optimal.

We create a scenari with two targets and test the two possible sequences as depicted on figure 3, one leading to a total time of \(3.08 s\) and the other \(4.86 s\)

Fig3. - Interception examples with 2 targets.

We create a scenari with three targets and test the six possible sequences as depicted on figure 4. Total times vary between \(8.25s\) and \(25.08s\)

Fig4. - All sequences on a 3 targets example.

On random scenario with increasing number of targets, we measure the time for an exhaustive search:

Fig5. - Exhaustive search time versus number of targets.

It becomes increasingly clear that we will not be able to brute-force our way into this problem and that an exhaustive search becomes intractable for number of targets above 8.

3.3: Naïve heuristic

We create a naïve heuristic by selecting the target that is closest to the drone at each decision time.

We test our heuristic on a 30 targets scenario (for which we are curently unable to compute the optimal)

Fig6. - Heuristics on 30 targets.

As it seems to perform moderatly well on the large 30 targets example we throw at it, we seek to gain a quantitative evalution of its performances. We define a set of 7 targets scenarios and perform an exhaustive search on each of them. Results are summarized in fig 7

Fig7. - histograms of 7 targets scenarios.

We use our heuristic to improve the exhaustive search by throwing away solutions that are worse than our heuristic. (The improvement is less dramatic than I had hoped for, might be due to the implementation using python exceptions…)

Fig8. - Improved exhaustive search.

3.4: Local refinement

In order to try and improve the solution given by out heuristic, we implement a local search :

We apply the local search to a 7 targets scenario, in which the optimal is dicovered.

Click for details

loading scenario from file: scenario_7_2.yaml
heuristic closest target
 23.36 ['1', '2', '3', '4', '5', '6', '7']
local search
 23.19 ['1', '2', '4', '5', '6', '3', '7']
 21.66 ['7', '1', '2', '4', '5', '6', '3']
 20.93 ['7', '1', '2', '4', '5', '3', '6']
 20.84 ['7', '1', '2', '5', '4', '3', '6']
 20.12 ['6', '7', '1', '2', '5', '4', '3']
 19.10 ['6', '7', '1', '2', '5', '3', '4']
 18.78 ['6', '7', '1', '2', '4', '5', '3']
 18.75 ['6', '7', '1', '2', '3', '4', '5']
 18.51 ['6', '7', '1', '2', '4', '3', '5']
optimal
 18.51 ['6', '7', '1', '2', '4', '3', '5']

We apply the local search to a 10 targets scenario. We improve the heuristic solution but fail to discover the optimal. Flight time is reduced from 78.55s to 50.11s

Click for details

loading scenario from file: scenario_10_1.yaml
heuristic closest target
 78.55 ['10', '2', '7', '9', '1', '4', '5', '6', '3', '8']
local search
 74.42 ['10', '7', '9', '1', '4', '5', '6', '3', '8', '2']
 70.35 ['10', '7', '9', '4', '1', '5', '6', '3', '8', '2']
 66.97 ['10', '7', '9', '4', '1', '5', '3', '6', '8', '2']
 63.44 ['2', '10', '7', '9', '4', '1', '5', '3', '6', '8']
 58.58 ['2', '10', '9', '4', '1', '7', '5', '3', '6', '8']
optimal
 50.11 ['2', '10', '9', '5', '8', '6', '3', '7', '1', '4']

We apply the local search to a 30 targets scenario (unknown optimal). Flight time is reduced from 169.86s to 97.06s

Click for details

loading scenario from file: scenario_30_1.yaml
heuristic closest target
169.86 ['2', '3', '4', '5', '29', '7', '6', '9', '11', '13', '8', '16', '10', '22', '12', '21', '1', '27', '26', '28', '24', '20', '19', '18', '17', '15', '14', '23', '25', '30']
local search
168.21 ['2', '3', '4', '5', '29', '7', '6', '9', '11', '13', '8', '16', '22', '12', '21', '1', '27', '10', '26', '28', '24', '20', '19', '18', '17', '15', '14', '23', '25', '30']
163.72 ['2', '3', '4', '5', '29', '7', '6', '9', '11', '13', '8', '16', '22', '12', '1', '27', '10', '26', '28', '24', '20', '19', '18', '17', '15', '14', '23', '25', '30', '21']
163.09 ['2', '3', '4', '5', '29', '7', '6', '9', '11', '13', '8', '22', '12', '1', '27', '10', '26', '28', '24', '20', '19', '18', '17', '15', '14', '16', '23', '25', '30', '21']
160.90 ['3', '4', '5', '29', '7', '6', '9', '11', '13', '8', '22', '12', '1', '27', '10', '26', '28', '24', '20', '2', '19', '18', '17', '15', '14', '16', '23', '25', '30', '21']
159.35 ['3', '4', '5', '29', '7', '6', '9', '11', '13', '8', '22', '12', '1', '27', '10', '26', '28', '24', '20', '19', '2', '18', '17', '15', '14', '16', '23', '25', '30', '21']
141.62 ['3', '4', '5', '29', '7', '6', '9', '11', '13', '8', '22', '12', '1', '27', '10', '28', '24', '20', '19', '2', '18', '17', '15', '14', '16', '23', '25', '30', '21', '26']
137.54 ['3', '4', '5', '29', '7', '11', '6', '9', '13', '8', '22', '12', '1', '27', '10', '28', '24', '20', '19', '2', '18', '17', '15', '14', '16', '23', '25', '30', '21', '26']
131.35 ['3', '4', '5', '29', '7', '11', '6', '9', '13', '8', '22', '27', '12', '1', '10', '28', '24', '20', '19', '2', '18', '17', '15', '14', '16', '23', '25', '30', '21', '26']
130.22 ['3', '4', '5', '29', '7', '11', '6', '9', '8', '13', '22', '27', '12', '1', '10', '28', '24', '20', '19', '2', '18', '17', '15', '14', '16', '23', '25', '30', '21', '26']
129.93 ['3', '4', '5', '29', '7', '11', '6', '9', '8', '13', '22', '27', '12', '1', '10', '28', '24', '20', '19', '2', '18', '17', '14', '15', '16', '23', '25', '30', '21', '26']
129.73 ['3', '4', '5', '29', '7', '11', '6', '9', '8', '13', '22', '27', '12', '1', '10', '28', '24', '20', '19', '2', '18', '17', '14', '15', '16', '23', '25', '21', '26', '30']
127.89 ['30', '3', '4', '5', '29', '7', '11', '6', '9', '8', '13', '22', '27', '12', '1', '10', '28', '24', '20', '19', '2', '18', '17', '14', '15', '16', '23', '25', '21', '26']
119.82 ['30', '3', '4', '5', '29', '7', '11', '9', '8', '6', '13', '22', '27', '12', '1', '10', '28', '24', '20', '19', '2', '18', '17', '14', '15', '16', '23', '25', '21', '26']
118.13 ['30', '3', '4', '5', '29', '7', '11', '9', '6', '13', '8', '22', '27', '12', '1', '10', '28', '24', '20', '19', '2', '18', '17', '14', '15', '16', '23', '25', '21', '26']
118.11 ['30', '3', '4', '5', '7', '29', '11', '9', '6', '13', '8', '22', '27', '12', '1', '10', '28', '24', '20', '19', '2', '18', '17', '14', '15', '16', '23', '25', '21', '26']
116.94 ['30', '3', '4', '5', '7', '29', '11', '9', '6', '13', '8', '16', '22', '27', '12', '1', '10', '28', '24', '20', '19', '2', '18', '17', '14', '15', '23', '25', '21', '26']
114.82 ['30', '3', '4', '5', '7', '29', '11', '9', '6', '13', '8', '16', '22', '27', '12', '1', '10', '28', '20', '19', '2', '18', '17', '14', '15', '23', '25', '24', '21', '26']
114.75 ['30', '4', '5', '7', '29', '11', '9', '6', '13', '8', '16', '22', '27', '12', '1', '10', '28', '3', '20', '19', '2', '18', '17', '14', '15', '23', '25', '24', '21', '26']
107.58 ['30', '4', '5', '7', '29', '11', '9', '6', '13', '8', '16', '22', '27', '12', '1', '10', '28', '3', '20', '19', '2', '18', '14', '15', '17', '23', '25', '24', '21', '26']
107.42 ['30', '4', '5', '7', '29', '11', '9', '6', '8', '13', '16', '22', '27', '12', '1', '10', '28', '3', '20', '19', '2', '18', '14', '15', '17', '23', '25', '24', '21', '26']
105.82 ['30', '4', '5', '7', '29', '11', '9', '6', '8', '16', '22', '27', '12', '1', '10', '28', '3', '20', '19', '2', '18', '14', '15', '13', '17', '23', '25', '24', '21', '26']
105.53 ['1', '30', '4', '5', '7', '29', '11', '9', '6', '8', '16', '22', '27', '12', '10', '28', '3', '20', '19', '2', '18', '14', '15', '13', '17', '23', '25', '24', '21', '26']
105.27 ['1', '30', '4', '5', '7', '29', '11', '9', '6', '8', '22', '27', '12', '10', '28', '3', '20', '19', '2', '18', '14', '15', '13', '17', '16', '23', '25', '24', '21', '26']
105.06 ['1', '30', '4', '5', '7', '29', '11', '9', '6', '8', '22', '27', '12', '10', '28', '3', '20', '19', '2', '18', '15', '14', '13', '17', '16', '23', '25', '24', '21', '26']
103.11 ['1', '30', '4', '5', '7', '29', '11', '9', '6', '8', '22', '12', '27', '10', '28', '3', '20', '19', '2', '18', '15', '14', '13', '17', '16', '23', '25', '24', '21', '26']
 97.80 ['1', '30', '4', '5', '7', '29', '11', '9', '6', '8', '10', '22', '12', '27', '28', '3', '20', '19', '2', '18', '15', '14', '13', '17', '16', '23', '25', '24', '21', '26']
 97.15 ['1', '30', '3', '4', '5', '7', '29', '11', '9', '6', '8', '10', '22', '12', '27', '28', '20', '19', '2', '18', '15', '14', '13', '17', '16', '23', '25', '24', '21', '26']
 97.06 ['1', '30', '3', '4', '5', '7', '29', '11', '9', '6', '8', '10', '22', '12', '27', '28', '20', '19', '18', '2', '15', '14', '13', '17', '16', '23', '25', '24', '21', '26']