# Thread: The Expanding Square Search Pattern Problem

1. ## The Expanding Square Search Pattern Problem

Hi All!

I am new to the MHF so greetings everybody. I am a Search and Rescue Mission Coordinator for the UK Coastguard but I am currently working with the British Antarctic Survey as a Boating Officer in the Antarctic. Part of my job is to implement a Search and Rescue framework for the maritime operations undertaken here and as part of this I am writing a Maritime Search Planning handbook. The purpose is to allow personnel with little experience plan a quantified "rapid response" search using the "Expanding Square" search pattern. The planner will calculate and plot a square area on a chart within which he or she will expect the missing person or craft to be drifting. The search and rescue unit will proceed to the exact centre of this square and begin navigating an expanding square pattern with an exact initial leg length and subsequent leg lengths and 90 degree alterations of course to the right or left. The Initial leg length is worked out using tables of existing data. The spacing between adjacent legs will be equal in distance to the length of the first leg and is called the Track Spacing. The pattern goes like this: Lifeboat proceeds North from the middle of the search area for 1 x track spacing, alters course right by 90 degrees, proceeds east for 1 x track spacing, alters course by 90 degrees right, proceeds South for 2 x track spacing, 90 degrees right, west for 2 x track spacing, 90 degrees right, North for 3 x track spacing and so on....... The result is an expanding square pattern with fills the entire square search area leaving no areas within the area further from the lifeboats track than the track spacing (known as a coverage factor of 1)

The problem I would like you guys to help with is this: Is there a formula which will tell you how many legs are required to complete the search area to a coverage factor of 1 having been given the Area of the Search Box and the track spacing (aka the initial track spacing)?

I have worked for weeks on this problem and in practice all my theories are marginally inaccurate or only work for certain size area and track spacings. My favoured theory was that the answer lays in the length of one side of the area divided by the track spacing, multiplied by the number of legs it takes to achieve one more advancement along the length of the side (which appears to be 4, except the first 360 degree rotation which takes 5 legs to complete) however this appears to simplistic as when I draw test areas to scale on graph paper the formula does not work and gives inaccurate answers.

Some common parameters would be:

Search Areas: 2nm2, 5nm2, 10nm2, 12nm2, 18nm2
Track Spacings: 0.1nm, 0.3nm, 0.5nm, 1nm, 1.25nm

Use the above figures in any combination as they are mutually exclusive and may be combined.

I am no Maths expert so, I am hoping this may be quite simple to someone with a good level of knowledge in Mathematics.

Kind Regards,

Matthew Kenney
KEP Research Station,
Antarctica.

2. A very interesting problem! Thanks for posting. I've done a few experiments of my own on graph paper. Here are some numbers (TS = Track Spacing, A = area in square units, and L = # legs):

$\begin{array}{rrr}
\text{TS} &\text{A} &\text{L}\\ \hline
1 &25 &9\\
1 &36 &9\\
1 &64 &13\\
1 &100 &17\\
1 &144 &21\\
1 &196 &25\\
1 &256 &29
\end{array}$

The pattern here is clear: adding two length units to the sides of the square increases the number of legs by 4, assuming the track spacing is constant.

Now, what happens when you keep the area constant but vary the track spacing? Here's some more data:

$\begin{array}{rrr}
\text{TS} &\text{A} &\text{L}\\ \hline
0.5 &256 &61\\
1.0 &256 &29\\
1.5 &256 &21\\
2.0 &256 &13\\
2.5 &256 &13\\
3.0 &256 &9\\
3.5 &256 &9\\
4.0 &256 &5\\
4.5 &256 &5\\
5.0 &256 &5\\
5.5 &256 &5\\
6.0 &256 &5\\
6.5 &256 &5\\
7.0 &256 &5\\
7.5 &256 &5\\
8.0 &256 &0
\end{array}$

The pattern here is a bit less clear. The sequence doesn't show up in the Online Encyclopedia of Integer Sequences. One thing I notice is that if you add three to all the Leg numbers, you get an interesting sequence:

$\begin{array}{rrrr}
\text{TS} &\text{A} &\text{L} &\text{L}+3\\ \hline
0.5 &256 &61 &64\\
1.0 &256 &29 &32\\
1.5 &256 &21 &24\\
2.0 &256 &13 &16\\
2.5 &256 &13 &16\\
3.0 &256 &9 &12\\
3.5 &256 &9 &12\\
4.0 &256 &5 &8\\
4.5 &256 &5 &8\\
5.0 &256 &5 &8\\
5.5 &256 &5 &8\\
6.0 &256 &5 &8\\
6.5 &256 &5 &8\\
7.0 &256 &5 &8\\
7.5 &256 &5 &8\\
8.0 &256 &0 &3
\end{array}$

That $-3$ kinda makes sense, because in all my drawings, if I started going north, I ended up going north on the last leg. That means all the numbers in the Leg column, except for 0, are always going to be congruent to 1 modulo 4 (That is, you always go north, east, south, west, north, east, south, west, ... , north, east, south, west, north.)

Breakthrough: focus on the number of times you go north. It's going to be

$\displaystyle\left\lceil\frac{\sqrt{A}/2}{TS}\right\rceil.$

So this formula is telling you that if you take the square root of the area, you get the length of one side, right? (You have squares). Take half of that, and you get half of the length of one side. That's the amount of space your "norths" have to cover. And if you divide again by the track spacing, and round up (that's what the funny little $\lceil x\rceil$ symbols mean), you get the number of times you go north. The rest of the formula goes like this:

$\displaystyle L=N+3(N-1)=4N-3=4\left\lceil\frac{\sqrt{A}}{2\,TS}\right\rceil-3.$

So that's your formula. It does not appear to work for the limiting case of $TS=\sqrt{A}/2.$ It should give zero, whereas the actual value coming out of the expression is 1. However, this is not, presumably, a worrisome thing, because this limiting case consists of someone just parking out in the middle of the square and looking! Most of the time, I would assume, the area to cover is too big to do that.

Hope this helps.

3. I should think another very practical consideration would be the total distance traveled for the boat. Let $N$ be the number of times the boat goes north. Let us consider all but the last leg; that is, the first $4N-4=4(N-1)$ legs. Now, for all-but-the-last legs, the number of different lengths traveled is equal to $(L-1)/2.$ So you have the expression

$\displaystyle d=\underbrace{TS+TS+2TS+2TS+3TS+3TS+\dots+\left(\f rac{L-1}{2}\right)TS+\left(\frac{L-1}{2}\right)TS}_{4(N-1)\;\text{times}}+\left(\frac{L-1}{2}\right)TS.$

The last term is the last leg going north, which only need be the same length as the second-to-last leg in order to cover the whole area. Simplifying yields

$\displaystyle d=2\left(TS+2TS+3TS+\dots+\left(\frac{L-1}{2}\right)TS\right)+\left(\frac{L-1}{2}\right)TS$

$\displaystyle =2TS\left(1+2+3+\dots+\left(\frac{L-1}{2}\right)\right)+\left(\frac{L-1}{2}\right)TS.$

Now it is a fairly well-known fact that the sum of the first $n$ numbers is $n(n+1)/2.$ To see this, pair up the first number, 1, with n. Pair up 2 with n-1. Pair up 3 with n-2, and so on. The sum of each of these pairings is n+1, and there are n/2 of them. This formula also works for n odd (check for yourself). So, our distance formula simplifies as follows:

$\displaystyle d=2TS\frac{\left(\frac{L-1}{2}\right)\left(\frac{L-1}{2}+1\right)}{2}+\left(\frac{L-1}{2}\right)TS$

$\displaystyle =TS\left(\frac{L-1}{2}\right)\left(\frac{L+1}{2}\right)+TS\left(\fr ac{L-1}{2}\right)$

$\displaystyle =TS\:\frac{L-1}{2}\left(\left(\frac{L+1}{2}\right)+1\right).$

The final expression is

$d=TS\left(\dfrac{L-1}{2}\right)\left(\dfrac{L+3}{2}\right),$

and, of course, you can plug in the value for $L$ determined in my previous post. I get

$\displaystyle d=4TS\left(\left\lceil\frac{\sqrt{A}}{2TS}\right\r ceil-1\right)\left\lceil\frac{\sqrt{A}}{2TS}\right\rcei l.$

So many thanks for your assistance with this. I am thrilled you have taken some of your precious time to help me! Now I am rather embarrassed to admit your level of maths is light years beyond mine (which stopped at high school) so I am having to work quite hard keeping up with the logic and symbology! However, I believe I have grasped the concept for finding the number of legs required. It will take me a little longer to understand your last post Im afraid, but I am enjoying the challenge!
There does seem to me to be a discrepancy when the areas are smaller. Take for instance an area of 16 Square Units (4x4), with an assigned track spacing of 1 unit. My doodle shows me the number of legs is 5 to complete the area, however the formula (providing I am using it correctly) gives me 13 legs as an answer. Similarly a 2x2 square with an assigned TS of 0.1 is 17 legs when drawn, but again I am getting 37 as an answer. Am I misunderstanding the solution?

5. Hmm, let me check. For your first example, you have TS = 1, A = 16. My computations:

$L=4\left\lceil\dfrac{\sqrt{A}}{2TS}\right\rceil-3=4\left\lceil\dfrac{\sqrt{16}}{2}\right\rceil-3=4\left\lceil\dfrac{4}{2}\right\rceil-3=4\left\lceil 2\right\rceil-3=4\cdot 2-3=8-3=5,$

as you got in your doodle. I would conclude from this that you're not computing the formula correctly.

For the second example, you have TS = 0.1, and A = 4. Again, my computations:

$L=4\left\lceil\dfrac{\sqrt{A}}{2TS}\right\rceil-3=4\left\lceil\dfrac{\sqrt{4}}{2(0.1)}\right\rceil-3=4\left\lceil\dfrac{2}{0.2}\right\rceil-3=4\left\lceil 10\right\rceil-3=4\cdot 10-3$

$=40-3=37.$

Here, it looks like you computed the formula correctly, but I'm not sure I buy your doodle figure of 17 legs. Could you please double-check that?

6. Doh! Yes indeed you are correct. I have doodled my 2 x 2 square out of scale and inadvertently used a track spacing of 0.2. Running this TS carefully through the formula gives me 17 legs! It appears I have made some foolish mistake on the calculation of the 4x4 square, as I have just run it again more carefully and have the correct answer. Thank you so much for helping me. I am about to have another look at your ideas for calculating the total distance as this will be invaluable in determining the Search Duration and ensuring the search craft has enough endurance to complete the whole area without refuelling. It will also be helpful to know if the search is likely to continue after dark. Im afraid the figures look a little daunting to me (which must make you chuckle!) I think its about time I undertake some Math study and bring myself back up to speed with Algebraic equations... Now where has that idiots guide gone??

7. Glad we're on the same page now.

Just a thought: you may want to give some consideration to where your base is relative to the center of the square. There's no reason you couldn't work from the outside in (just do the track in reverse). You might be able to optimize total voyage length, because then you could choose the corner you start in to be closer to base. Take that for what it's worth.

8. OK, I have looked at the distance calculation. The working is alittle beyond my level of mathematical understanding, however I have used the formula to work the 2 x 2 square with a TS of 0.1 and have concluded an answer of 36. Can you tell me if I appear to be using the formula correctly, and also tell me what unit that number relates to? Is it 36TS?

9. The answer is 36, with whatever units of length TS has (which should, incidentally, be the same as the units used to compute the area A, squared). So, for example, if your area is 2 km x 2 km, and TS = 0.1 km, then the distance calculation gives 36 km. So yes, it does appear you're plugging the numbers correctly into the formula - you just need to interpret the results correctly.

Query: I haven't checked the correctness of the distance calculation against doodles. Does it appear to match up?

10. Ok, I have run the numbers 3 times and the actual distance is 36.1. When I run the calculation for a 2x2 area with TS = 0.2, then the formula gives the answer 16. When the sum of the legs is calculated manually the actual answer is 16.2.
Am I right in suspecting the minor discrepancy is due to the first 360 degree rotation out from centre is made of 5 legs not 4? In effect the first rotation requires 2 northerly legs. Would this be corrected by the addition of +TS to the end of the equation?
Thank you for clarifying the units. In reality they will be in Nautical Miles.
It is true that which ever direction you approach the search area you will have to navigate through it to get to the centre, and it may seem to be the case that if the exit of the search area lay closest to the origin of the lifeboat it would seem logical to reverse it, however this type of search is used for shorter drift elapsed times and when there is a higher degree of confidence in the "Datum Position" or the centre of the area. In effect what happens with manual search planning such as this is that you model your target from the time it began drifting (Drift Start Time or DST) taking into account Total Water Current (TWC) which includes tidal current, ocean currents and wind driven currents and Leeway. The model is run for the drift Elapsed Time (DET) which is up to the time the first search unit is expected to arrive at the datum position. In an ideal world you expect your missing object to be in that position awaiting your arrival. However an error circle is produced to encompass all the associated errors (Initial Position Error, Drift Error, and Plotting inaccuracies). So the search area is in fact circular around the datum. The area is boxed off to make navigating it simple. Incidentally, my preferred method of boxing off is North South as the lifeboat crew will appreciate simple courses. Some planners opt for boxing off perpendicular to the resultant drift vector (the result of all the above drift factors) concluding that having opposite corners placed along the vector, a slightly higher margin of error is achievable as a slightly higher amount of the vector is searched back along the track and to a point projected further along it. My argument is that the area of probability is within the circle, and if you are considering the location of the search object may be outside of this, then perhaps you should be increasing your error radii. As a lifeboatman of afew years experience I can say that having to calculate course changes of 90 degrees when your initial heading is given is 067 degrees at 3 am in 5m seas and driving rain and 40 knots of wind is really not an easy task, or for that matter easy to navigate via magnetic compass. Cardinal Points every time for me!
The point is the datum position is considered as having the highest likelyhood of success, therefore go straight for the prize, then when it isnt there (which is very likely) then search the error radius. I am sure by now you are seeing that search planning is not a science, but an art. I intend on expanding my work here and writing a book on the subject in due course in which I aim to discuss the problems with the current methodology, explore solutions and draw a picture of the future of search planning. The trend is heading toward Stocastic Modelling which is far more accurate, but completely impossible to calculate manually. The field becomes far more interesting with larger search areas and longer drift elapsed times when we must consider Divergence, but this is another discussion!

11. Some very nice additional information there. I can see this is a very practical problem, indeed.

I have a question for you. Are you doing the first or the second in this picture?

My formula assumes the second. That is, the last three legs of the journey have the same length. That's why, in my derivation of the distance formula, the last three terms are identical. If your doodles have the first picture, then it doesn't surprise me in the least that you would have my distance plus one track spacing, exactly.

In doing some more thinking about the problem, it seems to me that you do need to go the farther distance on the last leg, otherwise the far corner in which you end up will be $\sqrt{2}\cdot TS>TS$ distance units away from your final spot, which means the far corner will not be covered.

So, rederiving the formula using this assumption yields the following:

$d=TS+TS+2TS+2TS+\dots+\left(\dfrac{L-1}{2}\right)TS+\left(\dfrac{L-1}{2}\right)TS+\left(\dfrac{L+1}{2}\right)TS.$

The last term just carries through until you get to the fifth line of calculations, which changes to

$d=TS\left(\dfrac{L-1}{2}\right)\left(\dfrac{L+1}{2}\right)+TS\left(\d frac{L+1}{2}\right)$

$=TS\:\dfrac{L+1}{2}\left(\dfrac{L-1}{2}+1\right)$

$=TS\:\dfrac{L+1}{2}\left(\dfrac{L+1}{2}\right)$

$=TS\left(\dfrac{L+1}{2}\right)^{\!2}$

$=TS\left(\dfrac{4\lceil\sqrt{A}/(2TS)\rceil-3+1}{2}\right)^{\!2}$

$=TS\left(\dfrac{4\lceil\sqrt{A}/(2TS)\rceil-2}{2}\right)^{\!2}$

$=TS\left(2\left\lceil\dfrac{\sqrt{A}}{2TS}\right\r ceil-1\right)^{\!2}.$

So try evaluating the distance using the new and improved formula

$d=TS\left(2\left\lceil\dfrac{\sqrt{A}}{2TS}\right\ rceil-1\right)^{\!2},$

and see if that doesn't match your doodles (which are probably correct in this matter).

12. Some additional thoughts on optimizing total journey length:

1. I note you have a marked preference for the 4 points of the compass, which is entirely understandable.
2. I also note your comments concerning the higher probability of finding the target near the center of the square.
3. Hence, it seems to me that the thing to do is to go to the center of the square, and then pick your starting direction carefully. For example, if the southwest corner is the corner closest to base, then pick west as the starting direction. If the northwest corner is closest, start going north. If the northeast corner is closest, start going east. If the southeast corner is closest, start going south. Then you will end up in the corner closest to base.

Does that make sense?

Incidentally, you can compute the vector from the center of the square to the final stopping place if you know $L$. Let's say that you started going north, and that is the positive $y$-direction. Let's say that east is the positive $x$-direction. Also, let's put the origin at the starting point, the center of the square. Then the vector to the final stopping place is given by

$\mathbf{s}=TS\,\hat{\mathbf{j}}+\dfrac{TS(L-1)}{4}\,\left(\hat{\mathbf{j}}-\hat{\mathbf{i}}\right).$

The magnitude of this vector is

$s=|\mathbf{s}|=\dfrac{TS\sqrt{L^{2}+2L+5}}{2\sqrt{ 2}}.$

13. The pattern continues until the coverage factor is one. I.e - there are no empty spaces within the search area greater than the track spacing. Now I have never closely considered the last leg. I have drawn a few more scenarios and combinations of area and TS and I cannot see a necessity for the last leg to be any longer than the 2 previous. The space on the outside of the last 3 legs should be at maximum the distance of the track spacing. If it is greater then more legs are required right? Furthermore, take for instance 4 x 4 area with a TS of 1.1. 5 legs are required. It appears in fact that the last leg need only be 2.0nm long and area will still be covered to a coverage factor of 1. The sequence of leg lengths required is 1.1, 1.1, 2.2, 2.2, 2. Im not sure what the significance of this is, and as the distance fundamentally required of the last leg will vary between each model, it may be best to keep the last leg the same distance as the previous two for simplicity? It will always achieve a coverage factor of 1 this way.
The argument for choosing the course of the first leg is a fair point, however it is not as simplistic as it first appears. This type of search is not referenced to the sea bed. It is a fluid "through the water" search. This means the craft navigating the pattern is steering a compass course at a constant "log speed" or with reference to the crafts Speed through the water, and is making his course changes with reference to time. For instance, the search speed is 10 knots and the track spacing assigned is 0.5nm. He will commence his first leg and time 3 minutes, alter course, time 3 minutes, alter course time 6 minutes and so forth. This is what mariners call navigating by Dead reckoning (DR). What this means is the vessel is drifting with the elements and is making no alterations to counteract this. What you end up with is an expanding spiral drifting off with the wind and tide. It is still true to say that if you start by heading on the course closest to the return to base course, then you will end up closer to it than you otherwise would. In reality this is of little concern to the lifeboat crew as this type of search is really only used for smaller areas so wherever they end up it wont be to far. Plus the fact that every lifeboat crew wishes to find survivors and execute a rescue, therefore thinking about finishing the search pattern and returning home is not done. In practice once the target is located, it is often the case that the lifeboat will take them somewhere other than the lifeboat station (although this is also very common) for example an agreed casualty transfer jetty, or perhaps even into open water to facilitate an at sea transfer to a Coastguard helicopter for evac to hospital.
Perhaps you have spotted another problem with this system. As you are searching, the target is progressing further with the elements. The search area is also increasing in size as the errors build with the extra drift distance. The idea that the search unit is also drifting with the elements is fine for tidal current as the movement of water will affect all objects regardless of size, displacement and underwater form in exactly the same manner. This is not true for leeway however. A person in the water, wearing a lifejacket is thought to drift due to leeway at a rate of 2% of the wind speed in a downwind direction or upto 45 degrees either side of it. The figure for an inshore lifeboat will be more like 4%. This difference is further complicated by the fact that there is no data on how the vessels motion will effect its leeway. The lifeboat is travelling at 10 knots, therefore if there was absolutely no wind, it would now be experiencing 10 kntos of apparent wind from directly ahead. When you consider the wind acting on the vessel it will interact with this apparent wind and change the leeway experienced by it. There is also no data that I am aware of for how hydrodynamics might affect the vessel when it is moving through the water at speed. The variables are mind boggling. This is one of the seemingly insurmountable problems with search and rescue at sea in its current form. The solution is that expanding square searches are used for short drift elapsed times where there isnt a great wind strength, and the difference in leeway between the target and search vessel is overlooked as it cannot be accurately planned for. It is likely this has been considered in the drift error factor which is currently 30% of the drift distance. Once again this is turning into a good note making session for the book, sorry for the ramblings!

14. I cannot see a necessity for the last leg to be any longer than the 2 previous.
Here's the necessity. Let's take the case where $TS$ goes evenly into $\sqrt{A},$ the length of one of the sides. Then you'll have a situation somewhat like the following picture:

You can see that the horizontal distance from the last leg to the left-hand edge of the square is $TS.$ But the distance from $A$ to $B$ is $\sqrt{2}\,TS>TS.$ Hence, point $B$ is not covered. Now, if you extended the last (north-bound) leg all the way to the top of the square, you can see that point $B$ would be covered, as needed. I would also point out that point $C$ is also not covered by the last short leg, but would be covered by a long last leg.

Does that help clarify matters?