How an algorithm protects us

It is regarded as one of the most significant algorithms of the past 50 years, a method of enabling estimation in the midst of uncertainty: the particle filter.

As Professor Peter Willett of the University of Connecticut writes, “Particle filters are now almost literally everywhere; every researcher in the field knows them and works with them. Their applications are ubiquitous, from predicting weather, to epidemiology, to extraction of missile threats from satellite data.”

In mathematical terms, the particle filter is a method for dealing with non-linear and non-Gaussian dynamic estimation problems. 

These are problems where typically the underlying dynamic processes do not follow a simple straight-line evolution and where the unknown variables feeding into the process are assumed not to follow a standard probability distribution.

When it comes to complex, non-linear, non-Gaussian problems, there would be few that rival the mystery of flight MH370, the Malaysia Airlines flight that went missing whilst en route from Kuala Lumpur to Beijing in 2014.

The aircraft disappeared from air traffic control radar screens minutes after its last communication, whilst flying over the South China Sea.

It was tracked by military radar for another hour, during which time it deviated from its planned flight path, eventually flying out of radar range 200 nautical miles northwest of Penang Island in north-western Peninsular Malaysia – its last known location.

Using maths to narrow the search

Dr Neil Gordon, a senior scientist with the Department of Defence in South Australia and widely recognised as one of the originators of the particle filter, led a Defence team that applied the particle filter to help define the search region for the missing aircraft.

“It’s all to do with estimation in dynamic systems,” Dr Gordon explains.

“You’ve got to capture the uncertainty in the right way. It’s impossible to do that with an analytic function which is why we’ve ended up with effectively a computer-driven approach, particle filters. They are a way of driving random samples and herding them around in the right way to end up with the probability distribution in the right place.”

“In the case of the MH370, we had an aircraft, presumed lost at sea. We had the last self-reported position early in the flight, we had data from radars, we had information about the wind and the weather and we had approximately once-an-hour metadata associated with Inmarsat satellite communication system handshakes with the aircraft.”

“Using the particle filter we were able to factor together all those uncertainties, and determine where best to focus the search effort.”

The work required great technical innovation because neither traditional sensor data nor self-reported location data from the aircraft were available for the majority of the flight.

The resulting search area was vast (larger than the size of England) and extremely challenging for a search operation, given its remoteness, the depths of the ocean and the ocean weather.

“In those situations, even if you’re searching in the most likely area, there is still no guarantee of locating the wreckage,” Dr Gordon explains.

MH370 has never been found.

Solving real-world problems

As the MH370 search demonstrates, real-world problems are rarely linear and often involve variables that do not fit neatly into a standard bell curve, what is termed a normal or Gaussian distribution.

“The physical world is full of uncertainties which other mathematical methods for dynamic estimation such as the Kalman filter are unable to represent,” Dr Gordon says.

“Particle filters provide a method for doing a rigorous calculation of the combination of all the contributions of uncertainty to give you an understanding of what’s going on.”

“Take the COVID pandemic. A particle filter, or a variation of it, can be used to model the possible infection scenarios, factoring in the different rates of transmission, levels of social distancing, whether people are wearing masks.”

“These models enable health experts to provide advice to governments on how best to prepare for and manage those possible outcomes.”

Surveillance powered by an algorithm

In Defence, the main application of the particle filter is in surveillance, processing data from radars and other sensors in order to extract meaningful intelligence.

“When it comes to surveillance it’s critical that we extract as much information from our sensors as possible to maximise situational awareness,” Dr Gordon explains.

“Using the particle filter, we take the received energy from a radar system, be it JORN or Wedgetail, and estimate how many targets there are, where they are, where they are going, what’s their intent.”

“Methods such as the particle filter allow us to do this in a more accurate way than using standard Kalman filter type approaches.”

As Dr Gordon points out, having accurate surveillance not only enables us to put in place appropriate defensive measures but it also acts as a very powerful deterrent.

“If the chances of detection are very high, that is more likely to deter any potential adversary,” he says.

The particle filter is an incredibly cost-effective way of improving detection capability. A few lines of maths can achieve improvements in detection sensitivity that would otherwise cost many millions of dollars in physical upgrades.

Defence is a proud participant in National Science Week, celebrating and acknowledging the contribution that our STEM workforce makes to the capabilities of our Defence Force and the security of the country. Check out #STEMsavinglives