Tuesday, May 29, 2012

Climb Every Mountain

In computer science there are sets of problems that have direct solutions, sorting a list of names for example. There are also sets of problems that don't have direct solutions and a solution is either found or approximated by an iterative series of steps, finding the Sin of an angle for example. Many of the techniques or algorithms used to solve the latter set of problems are drawn from mathematics, but some of the more interesting and useful ones are analogous to real world techniques. An algorithm is, after all, nothing more than a series of steps used to solve a problem. Understanding the computing science abstraction of the solution from the real world allows us to apply the algorithm as a technique back to the real world in new ways. One of these is the hill climbing algorithm. In simple terms the hill climbing algorithm may be described in this way:

Consider a blind hiker who, for reasons we won't pry into, wants to climb to the top of the highest hill in her neighbourhood, which has a number of hills, surrounded by miles of flat prairie. Let us assume that even though our hiker is very adept at navigating the town, she doesn't have any internal reference for the location of any of the hills. For the sighted person this is an easy task. Simply look for the highest terrain and walk towards it. For our blind hiker it is a bit more challenging, but she knows of the hill climbing algorithm, selects a starting point and sets off. She simply performs a scan of the area by walking around either in an organized search pattern, or by using a random walk, until she recognizes by feel that her steps are taking her uphill. At this point she changes to the hill climbing algorithm. As long as her steps take her up she continues in the same direction. If her steps begin to take her downhill, or level she goes back to her previous search pattern until her steps take her uphill again. When this search can no longer find a direction that takes her uphill, she is at the summit and her quest is complete. Or is it?

At this point, for a sighted person, this question is easily answered. A quick scan of the horizon will show if there are any higher hills. The example graph above shows this simple situation with a single summit (single maximum). For our ever intrepid blind hiker the problem is more difficult. She can not tell if she is on top of the highest hill, or even if there are any other hills around. If she wants to complete her quest she must continue, select a new starting point and search for another hill. Then once she climbs to the top of the new hill she must have a way to compare how high the current hill is in comparison to all the others. And she must continue until she can find no more hills. She can then quickly walk back to the highest hill she has found and be satisfied with a job well done. The graph below shows a case with two hills (two local maxima). Only one is the highest (global maximum). If our hiker had arrived on top of the lower hill first and decided she was done she would fail in her quest.


Computer scientists will also recognize a version of a classic example of computational complexity lurking in this problem. If our hiker wants to complete her search efficiently she will not want to climb the same hill twice, nor will she want to recover any ground when searching to see if there are any other hills. This is very similar to the travelling salesman problem, which is in the class of NP-complete problem in combinatorial optimization. Our hiker has a more difficult job than the salesman on one hand because she does not know where the hills are, or how many they are. On the other hand it is easier in that once she has visited all the hills her solution is evident.

When I explained to Langley Muir, Anne Barr and Mike Casey that their off tuning and Cardinal Pass techniques were hill climbing techniques and presented a problem of NP-complete complexity the reply I received from Dr Muir was puzzling:
In fact, the aural null procedure, as defined in the CASARA handbook (pages 2-3 - 2.5) is entirely based on the premise that the radiation pattern of the transmitter is circular. It has nothing at all to do with searches for global or local maxima or minima and has definitely got nothing at all to do with NP-Complete problems in any practical sense. If the radiation pattern is not circular, then the CASARA method will not lead to a solution at all in general but, in practice, will get you pretty close. There will be an "aural null" iff the monopole antenna is nearly vertical and you happen to pass almost directly over top of it. I think would be difficult to use any "hill-climbing" techniques (ie following a track which crosses the flux lines at 90 degrees) with simply a radio receiver and a fairly un-nimble aircraft.
It is true that the CASARA handbook and training manual claim that the Aural Null technique is base on a circular radiation pattern, but that is simple parroting of statements made by others for which I have never seen any scientific, engineering or technical justification; and are not true. It is also true that the approved procedures have nothing to do with searches for global or local maxima, but the off-tuning technique they proposed and used does because it uses a hill climbing algorithm or technique, as I will show a little later. The aural null he is referring to is the one that exists in line with the element of the monopole, which does not have to be vertical, or even nearly so. The aural null will exist regardless of the antenna orientation. You do need to fly through it to detect it, but that has nothing to do with the aural null homing technique. The phrase aural null is used to represent may different instances of when "nothing is heard" in radio communications, including (but not limited to) the aural null used in some radio direction finding systems. There is no need to follow a track that crosses "flux lines" at 90°, and in fact no way to determine which direction the "flux lines" go, and no need to be nimble. He goes on to say:
Using off-tuning simply reduces the amplitude of the received power so that the circle you are using to estimate the transmitter position is smaller in diameter than it would be if you kept working on the original transmitted frequency. As a matter of fact, you can make the off-tuning much more finely adjustable if you fiddle with both the frequency and the signal amplification (ie the volume) at the same time. However, doing two things at once is a good way to get entirely confused in practice and I am not recommending it - simply doing the off-tuning works well enough.
So in other words it is a hill climbing algorithm where the goal is to maximize the off-tuning, or minimize the diameter of a circle, apparently simply performed with a radio receiver and a fairly un-nimble aircraft. (The statement about making the procedure more sensitive by using the volume control is just more proof, if any was needed, that Dr Muir doesn't understand how radios receivers work.) Quoting Dr Muir again:
... If you have already found a "global" maximum by using the off-tuning method, I find it difficult to believe that you are going to be led very far astray by other "local" maxima.
So the goal is definitely to find a global maximum, certainly seems to be a hill climbing algorithm. Of course the problem, as we saw above with our hiker, isn't being lead astray after one has found the global maximum, but being led astray to a local maximum and thinking you have found the global maximum. This has happened but I will get to that in a little bit. Dr Muir also says:
You could theoretically make the problem NP-complete, but we do, in fact, live in the real world and have neither potentially infinite numbers of receivers nor reflectors to worry about.
The travelling salesman problem is a real world problem, and does not require an infinite number of anything to be NP-complete. Multiple local maxima in a radio signal field is a real world problem. But one must understand radio technology to know that. One must also understand how the theories apply to the problem of finding an ELT using off tuning to appreciate the danger it presents to the people you are looking for.

When I was still a member of CASARA I flew a training mission with a navigator that used this off tuning technique. We ended up homing to a local maximum that was nearly 10 nautical miles from the actual location of the ELT. When I relayed this story to Anne she accused me of attacking a valuable member of the unit (the navigator). I was not attacking any members. If I was attacking anything it was only the validity and safety of the technique. But to accept that the technique was flawed and dangerous would also force her to accept a number of other facts that she did not want to.

I suppose I can forgive a Ph.D in Physical Oceanography (Dr Muir) for not understanding radio technology, computational complexity theory or mathematical optimization of local search. I can't really forgive him for not educating himself in these subjects before making inaccurate statements about them. I can not understand how a professional programmer (Anne Barr) providing support to the Advanced Cognitive Engineering Lab at Carleton University can not be very familiar with computational complexity theory and mathematical optimization of local search.

In summary, off tuning is a hill climbing algorithm seeking to find the global maximum of ELT signal strength, using equipment that is ill suited for that purpose, and sets the crew up to be confused by what they hear. If the ELT presents more than one local maximum, then the search crew can be seduced (in the Electronic Warfare sense) away from the actual location, especially if they have been told that either there will be no other maxima, or that the technique will always take them to the global maximum. The probability of seduction increases with each additional local maxima. Identifying the global maximum from the set is an a problem of NP-complete complexity. This is further complicated by the crude mechanism used to measure signal strength. We have seen that one can not accurately compare signal strength moment by moment as one flies past an ELT. How then, can one expect to be able to compare the strength of one local maximum with one encountered many minutes previously? It does not matter how many times the technique has been successfully used in training. Without a statistical model that shows beacon placement in training is a representative sample of actual emergency ELT activations, all that proves is that their training beacon placement does not cause multiple local maxima. It is not proof that the technique will be effective and not subject to seduction in all actual searches. The continued use of this technique is not only contrary to instructions from the national air search authority, but poses a danger to people awaiting rescue.

No comments:

Post a Comment