SPONSORED BY

. SAS
Leverage the untapped power of text analytics.
 Read the Seth Grimes research study.

NEW DIGITAL EDITION!

 

The current issue of ORMS Today is now available to INFORMS members in "digital magazine" format. Log in to the Digital Editions Archive and enjoy a new online reading experience.

Simulation Software Survey

  Biennial survey of simulation software...
more »

20th Conference of the International Federation of Operational Research Societies (IFORS)

 

Call for Papers

 

Conference organizers invite you to participate in the IFORS 2014 Conference (www.IFORS2014.com) and to submit an abstract. The IFORS 2014 Triennial Conference will be held in Barcelona, Spain, July 13-18, 2014. It will bring operational researchers from around the globe together.

 

Submit abstracts at: http://ifors2014.upc.edu/abstract

 

The Program Committee is preparing a high-quality and attractive scientific program. There are already nearly 200 streams distributed in 25 areas. Find the most appropriate stream for your presentations at: http://ifors2014.upc.edu/abstract

 

All attendees, including speakers and session chairs, must register and pay the registration fee. These fees have been announced at €500 for early bird (until Feb. 28) and €300 for students.
Register now at http://ifors2014.com/registration
Find more at www.IFORS2014.com

 

Important dates
Abstract submission deadline: Jan. 31, 2014
Notification of acceptance: Feb. 25, 2014
Early Registration: Ends Feb. 28, 2014
Regular Registration: March 1 - April 30, 2014
Late and on-site registration: May 1 - July 13, 2014

In Search of Air France Flight 447

Operations research helps locate underwater wreckage of doomed airliner.

By Lawrence D. Stone

Air France A330-200 F-GZCP, shown landing at Paris-Charles de Gaulle Airport, was later destroyed during Air France Flight 447 from Rio de Janeiro to Paris.

Air France A330-200 F-GZCP, shown landing at Paris-Charles de Gaulle Airport, was later destroyed during Air France Flight 447 from Rio de Janeiro to Paris.

In the early morning hours of June 1, 2009, Air France Flight AF 447, with 228 passengers and crew aboard, disappeared during stormy weather over the South Atlantic during a flight from Rio de Janeiro to Paris. On April 3, 2011, almost two years after the loss, the underwater wreckage was located on the ocean bottom some 14,000 feet below the surface. On April 8, 2011, the director of the French Bureau d’Enquêtes et d’Analyses (BEA) pour la sécurité de l’aviation, stated “This [Metron] study published on the BEA website on 20 January 2011, indicated a strong possibility for discovery of the wreckage near the center of the circle. It was in this area that it was in fact discovered after one week of exploration …” [1]. Subsequently the flight data recorder (FDR) (photo) and cockpit voice recorder (CVR) were found, recovered from the ocean bottom and flown to the BEA in Paris where the data in these recorders were recovered.

In July 2010, Metron was tasked by the BEA to review all information about the loss of AF 447 along with all previous search efforts in order to produce a probability map for the location of the underwater wreckage. The result of this effort was the Jan. 20, 2011 study published on the BEA website [2]. This article describes the process and results of producing the probability map that was used to guide the successful search. The success of this effort provides a powerful illustration of the value of this methodical, Bayesian approach to search planning.

The Loss of the Aircraft and Initial Search Efforts

The Aircraft Communications Addressing and Reporting System (ACARS) sends messages via satellite containing maintenance and logistic information about the aircraft. Every 10 minutes it sends a GPS position for the aircraft. The last reported position (last known position (LKP), 2.98°N latitude/30.59° W longitude) was sent at 02 hours, 10 minutes and 34 seconds UTC on June 1, 2009. Based on failure to receive any ACARS messages after 02 hours, 14 minutes and 26 seconds, the BEA estimated that the plane could not have stayed in the air longer than 280 seconds or traveled more than 40 nautical miles (NM) from the LKP before crashing into the ocean.

Upon receiving notification of the crash, the BEA organized an international search by aircraft and surface ships to look for signs of the plane and possible survivors. On the sixth day of this effort, the first debris and bodies were found 38 NM north of the LKP.

Air France A330-200 F-GZCP, shown landing at Paris-Charles de Gaulle Airport, was later destroyed during Air France Flight 447 from Rio de Janeiro to Paris.

Underwater Searches

After the surface search, four phases of underwater search took place.

Phase 1: Passive acoustic search for the underwater locator beacons

The aircraft was equipped with two “black boxes,” the flight data recorder (FDR) and the cockpit voice recorder (CVR). These ruggedized devices are designed to withstand the high impacts expected in a crash and are fitted with an underwater locator beacon (ULB) that activates when contact is made with water. The batteries on the ULBs are certified to last at least 30 days. The manufacturer of the ULBs fitted on the AF 447 aircraft stated that the expected duration of the transmissions from these beacons was of the order of 40 days.

The passive acoustic search for the FDR and CVR, which lasted 31 days and ended on July 10, 2009, primarily involved two tugs hired to assist in the search, Fairmount Glacier and Fairmount Expedition. The Fairmount ships’ search efforts overlaid the aircraft’s intended track. Both ships employed towed pinger locators (TPLs) supplied by the U.S. Navy. Personnel from Phoenix International operated the equipment. On-site tests indicated the equipment was functioning properly.

The TPL sensors were assessed to detect the ULBs at a lateral range of 1,730 meters with a detection probability of 0.90. This detection range accounted for the frequency of the ULBs’ emissions (37.5 kHz) and the assumed source level (160 dB). The TPLs were flying above the underwater terrain, so it was estimated that degradation due to terrain shadowing was minimal. Environmental calculations showed that deep water propagation in this area is basically direct path and the transmission loss and ambient noise are sufficiently low to provide detection probabilities of 0.90 or above, a number that believed to be conservative provided at least one of the ULBs was operating properly. The ships’ tracks, reconstructed from GPS data, are shown in Figure 2.

Figure 1: Approximate location of the AF 447 underwater wreckage. The red circle is the 40 NM circle about the LKP.

Figure 1: Approximate location of the AF 447 underwater wreckage. The red circle is the 40 NM circle about the LKP.

Figure 2: Fairmount Glacier (orange) and Fairmount Expedition (pink) search tracks. The blue circles are 20 NM and 40 NM circles about the LKP.

Figure 2: Fairmount Glacier (orange) and Fairmount Expedition (pink) search tracks. The blue circles are 20 NM and 40 NM circles about the LKP.

From Figures 1 and 2, one can see that the passive acoustic search passed over the location of the wreckage. The raises the question of why the ULBs were not detected. We shall return to this question later.

Phase 2: Side-looking sonar search by the Pourquoi Pas?

To continue the search after the pingers’ extinction, the BEA decided to use the IFREMER side-looking (active) sonar towed by the Pourquoi Pas?. The search took place in August 2009 in the eastern half of J24, all of K24 and L24 and the western half of M24 as shown in yellow in Figure 2. This region, which had not been searched in Phase 1 due to lack of time, was suitable for search by side-looking sonar and was given a 0.90 probability of detection.

Phase 3 searches

Phase 3 included two search efforts – the U.S. Navy/Phoenix International and the Woods Hole Oceanographic Institute (WHOI). Both efforts used side-scan sonar. The search area covered by these searches (see Figure 3) was, for the most part, determined by the search area recommendation made by the Drift Group in [3].

Figure 3. Search areas for ORION (orange) and REMUS/Triton (grey). The orange circle is the 40 NM circle about the LKP.

Figure 3. Search areas for ORION (orange) and REMUS/Triton (grey). The orange circle is the 40 NM circle about the LKP.

The US Navy/Phoenix International search was performed using the USN ORION-towed side-scan sonar system that covered the 1,900-square-kilometer area of orange swaths shown in Figure 3. The ORION was operated to cover a 2,400-meter swath. Adjacent lines were spaced no more than 2,000 meters apart. For the search in this area we used a detection probability of 0.90 with the exception of some small difficult to cover regions.

WHOI deployed to the search area with three REMUS 6000 AUVs and a Triton XLX 4000 ROV. The three REMUS vehicles covered the 4,375 km area shown in grey in Figure 3. Search legs were spaced a distance apart equal to the maximum range less 50 meters which produced double coverage almost everywhere within its search area. Most regions of steep terrain, such as ridges, were imaged from both sides and were thus well searched. Exceptions were regions that contained ridges that were not suitable for side-looking sonar coverage. The Triton ROV was deployed in some of these. We attributed a detection probability of 0.90 to the areas shown in grey in Figure 3 with exceptions in some small areas.

Phase 4 search

In July 2010, after the unsuccessful Phase 3 search, the BEA tasked Metron to review the search and to produce a posterior probability distribution function (PDF) or probability map for the location of the underwater wreckage. The resulting PDFs (see Figures 4 and 5) showed that the area near the center of the 40 NM circle remained a high probability area for the location of the wreckage. The Phase 4 search, performed by WHOI using REMUS 600 AUVs, began in this area and found the wreckage after one week of search effort. Figure 6 shows a side-scan sonar image of the wreckage.

Posterior PDF after Phase 3. Red cells indicate high probabilities. Decreasing probabilities are shown by orange to yellow to green to blue cells.

Figure 4: Posterior PDF after Phase 3. Red cells indicate high probabilities. Decreasing probabilities are shown by orange to yellow to green to blue cells.

Figure 5. Posterior PDF assuming pingers failed.

Figure 5. Posterior PDF assuming pingers failed.

Figure 6. Side-looking sonar image of wreckage.

Figure 6. Side-looking sonar image of wreckage.

Computing the Posterior PDF for the Location of the Underwater Wreckage

Metron’s previous work in search applications, detailed in references [4,5,6], includes searches for the U.S. nuclear submarine Scorpion, the SS Central America and Steve Fossett’s crash site. In addition, Metron played a key role in developing the U. S. Coast Guard’s Search and Rescue Optimal Planning System (SAROPS), which has been successfully employed since March 2007 to plan and execute searches for ships and personnel lost at sea [7].

Our approach to the AF 447 search is rooted in classical Bayesian inference, which allows the organization of available data with associated uncertainties and computation of the PDF for target location given these data. The first step in this approach was to gather the available information about the location of the impact site of the aircraft. We organized this material into consistent scenarios, quantified the uncertainties with probability distributions, weighted the relative likelihood of each scenario, and performed a simulation to produce a prior PDF for the location of the wreck. This is the same methodology that was pioneered in [4] and incorporated into SAROPS [7]. Metron used a specially modified version of SAROPS to compute the PDFs for the AF 447 search analysis.

Next we estimated the effect of the unsuccessful search efforts. These efforts included the air and surface searches for floating debris and the underwater searches in Phases 1, 2, and 3. The goal of the Phase 1 search was to detect signals from the flight recorders’ ULBs. The Phase 2 and 3 searches involved the use of side-looking sonar and cameras to detect the underwater debris field of the wreck of the AF 447 flight. For each search, we enlisted sensor experts and knowledge of the sea state, visibility, underwater geography and water column conditions to estimate sensor performance. The results of the search assessment, combined in a Bayesian fashion with the prior PDF of the impact site, yielded the posterior PDF for the impact location given the unsuccessful search efforts shown in Figures 4 and 5.

The Figure 7 chart summarizes the various steps of this approach. For the Phase 1 search, the blocks shown in green use the SAROPS environmental module that simulates effects of winds and currents in the search zone. The chart also shows the cumulative detection probability (CDP) at the end of each phase of the search.

Figure 7. Summary of PDF computation.

Figure 7. Summary of PDF computation.

Prior PDF for impact location

The prior (before surface search) PDF for impact location has two components: 1. flight dynamics, and 2. a reverse drift component.

The flight dynamics prior is a mixture of two distributions. The first is based on consideration of the maximum distance the aircraft could have traveled from the time of its last reported position (last known position (LKP)) at 35,000-foot altitude to the time when a scheduled response from the ACARS was not received. The BEA estimated this distance to be 40 NM, so we formed a uniform distribution over the disk of radius 40 NM centered at the LKP for the first distribution.

The second distribution is based on data from nine commercial aircraft accidents involving loss of control. This analysis was performed by the Russian Interstate Aviation Group and the BEA. It showed that all impact points (adjusted to a 35,000 foot altitude at the time the emergency situation began) were contained within a 20-NM radius circle from the point at which the emergency began. These results are represented by a circular normal distribution centered at the LKP with standard deviation 8 NM along both axes. For the flight dynamics (FD) prior, we chose a mixture weighted by 50 percent for the uniform over 40 NM distribution and 50 percent for the circular normal distribution truncated at 40 NM from the LKP. The resulting distribution is shown in Figure 8.

Figure 8: Flight dynamics prior.

Figure 8: Flight dynamics prior.

The reverse drift (RD) prior was computed using SAROPS and data on currents and winds to reverse the motion of recovered bodies back to the time of impact. The BEA commissioned a group of oceanographic experts to estimate the currents in the area of the crash. The results are reported in the Drift Group Report [3]. Because of the complexity of the currents in the area of crash and the lack of data, there is substantial uncertainty in these estimates. Metron used the current estimates produced by the Drift Group and wind estimates from the U. S. Navy’s NOGAPS model to perform the reverse drift. However, we have given the results based on these estimates a low weight (30 percent) because of the uncertainty in the estimates.

To produce the RD prior, Metron used the positions and recovery times of 33 bodies that were located from June 6-10, 2009 [8]. There are two components of drift: drift due to ocean current and drift due to wind, which is called leeway. We did not apply reverse drift to pieces of debris that were recovered during this time because we do not have good models for the effect of leeway on this type of debris. For a deceased person floating in the water, we used the leeway model developed in [9].

For each body a large number of initial positions were drawn from the distribution of the location of the body at the time of recovery. Each position became a particle that was drifted backward in time subject to winds and currents. At each time step, a draw is made for the value of the current and the wind from the distribution in the cell containing the particle. The leeway is calculated from the winds as described in section 2.5 of [7], and the negative of the vector sum of current drift plus leeway is applied to the particle motion until the next time step. Figure 9 shows the reverse drift distribution produced in this fashion and truncated at the 40 NM circle.

Figure 9: Reverse drift PDF.

Figure 9: Reverse drift PDF.

The prior distribution before surface search by aircraft and ships is a mixture of 70 percent of the FD prior given in Figure 8 and 30 percent of the RD prior given in Figure 9. The resulting distribution is shown in Figure 10.

Figure10: PDF for impact location prior to surface search.

Figure 10: PDF for impact location prior to surface search.

Accounting for Unsuccessful Search

SAROPS uses a large number N of simulated points or particles to represent the probability distribution on the path or location of a search object. The nth particle has weight Wn for n=1,K , N. Initially all weights are set equal. The weight is the probability that the particle represents the search object’s location or path. The SAROPS PDFs in Figure 4 and elsewhere were produced by adding the weights (probabilities) of the particles in each cell to obtain the probability that the impact point is in that cell. The cell probabilities are color coded and range from high to low as the color goes from red to orange to yellow to green to blue.

If an unsuccessful search takes place, SAROPS computes the probability p1d(n) that the search would have detected the search object if it were located where particle n is. SAROPS computes the posterior distribution on object location using Bayes’ rule as follows:

Air France Formula Update

where W1n is the posterior probability that particle represents the object’s location. If the particles are moving and the search sensor is moving, SAROPS accounts for both of these motions in calculating pd(n).

Searches for debris by Brazilian and French aircraft were conducted from June 1-26, 2009. These searches were unsuccessful until June 6 when debris and bodies from the aircraft were first recovered. Search paths for each sortie were entered into SAROPS, along with information on altitude, speed, aircraft type, meteorological visibility, sea state and expected sensor performance against a raft-sized target (specifically a four-man raft), which was taken as a surrogate for the detectability of a large piece of debris such as the galley.

We started with the surface search prior distribution given in Figure 10 and used SAROPS to “drift” these particles forward in time from the time of impact through June 6. In the process of doing this we accounted for the unsuccessful aircraft and ship search during that time. This produced a set of particles whose probabilities were updated to incorporate the unsuccessful air and ship search effort during those days.

We then pulled each particle back to its position at the time of impact, keeping its weight the same as it was at the end of unsuccessful surface search. This produced the surface search posterior.

To evaluate the underwater search, we formed a prior that is a mixture of 30 percent of the surface search posterior and 70 percent of the FD prior. This PDF is shown in Figure 11.

Figure 11: Underwater search prior.

Figure 11: Underwater search prior.

Underwater Acoustic Search

Starting with the underwater search prior in Figure 11, we accounted for the unsuccessful searches in phases 1, 2 and 3. Figure 12 shows the posterior PDF after the unsuccessful passive acoustic search for the ULBs. Even before the discovery of the wreckage in an area apparently well searched by the TPL effort, we had doubts as to whether the ULBs had functioned properly. Data from past crashes developed by the BEA showed that ULBs were highly reliable and the probability of both ULBs failing in a crash was very low.

Figure 12: Posterior PDF after Phase 1.

Figure 12: Posterior PDF after Phase 1.

In spite of this evidence we thought that calculation of the probability of detection for the TPL search must account for the possibility that the ULBs were destroyed or disabled in the crash. After conferring with the BEA, we assumed a probability of 0.8 that a single ULB survived the crash. We decided to use a weighted average of 0.25 for independent survival probabilities and 0.75 for the dependent probabilities yielding a 0.77 detection probability for the TPL sensor.

Figure 4 shows the posterior after the unsuccessful Phase 2 and Phase 3 searches. Even though Figure 4 allows for the possibility that the ULBs did not work, the doubts we had about the ULBs compelled us to produce the alternate posterior PDF shown in Figure 5, which assumes the ULBs did not function. In retrospect, this PDF seems remarkably accurate and raises the question of why the ULBs were not detected. Were they not functioning? Were they obstructed somehow or did the TPLs simply fail to detect them? The BEA recovered one data recorder with the ULB attached. Perhaps the BEA will be able to determine whether it functioned properly. At the moment, this remains a perplexing question.

Conclusions

Figure 5 shows the wreckage is located in a high probability area assuming the ULBs failed to operate properly. Since the wreckage is located in an area thoroughly covered by the TPL search (see Figure 2), these results suggest it is likely that either both ULBs failed or failed to be detected for some reason. This failure resulted in a long and difficult search.

Our approach used careful and methodical consideration of all data available, with associated uncertainties, to form an analytic assessment of the highest likelihood areas for future search efforts. The weighted scenario approach allowed inconsistent information to be combined with subjective weights that capture the confidence in each piece of data. The analysis of the detection effectiveness of each component of the search, which produced the Bayesian posterior distributions shown in Figures 4 and 5 formed a solid basis for planning the next increment of search. In fact the Phase 4 search commenced in the center of the distribution and quickly found the wreckage.

The success of this effort provides a powerful illustration of the value of this methodical, Bayesian approach to search planning. The full report [2] of this work is available on the BEA website.

Lawrence D. Stone (stone@metsci.com) is chief scientist of Metron Inc. He is a member of the National Academy of Engineering and an INFORMS Fellow. In 1975, his text “Theory of Optimal Search” was awarded the Lanchester Prize. In 1986, he produced the probability maps used to locate the S.S. Central America that sank in 1857. The team for the AF447 analysis included Colleen M. Keller and Thomas M. Kratzke of Metron and Johan Strumpfer of Partners for Change in South Africa. This article is a based on “Search for the Underwater Wreckage of Air France Flight 447” in Proceedings of 14th International Conference on Information Fusion, July 5-8, 2011, Chicago.

References

  1. 1. Troadec, Jean-Paul, “Undersea search operations to find the wreckage of the A 330, flight AF 447: the culmination of extensive searches,” note from BEA director, April 8, 2011, on the BEA website at www.bea.aero/en/enquetes/flight.af.447/note.from.bea.director.end.phase4.pdf .
  2. Lawrence D. Stone, C M. Keller, T. M. Kratzke, and J. P. Strumpfer, “Search Analysis for the Location of the AF447 Underwater Wreckage,” report to BEA, Jan. 20, 2011.
  3. “Estimating the Wreckage Location of the Rio-Paris AF447,” report from Drift Group to BEA, June 30, 2010.
  4. Henry R. Richardson and L. D. Stone, “Operations Analysis During the Underwater Search for Scorpion,” Naval Research Logistics Quarterly, Vol. 18, June 1971.
  5. Lawrence D. Stone, “Search for the SS Central America: Mathematical Treasure Hunting,” Interfaces, Vol. 22: January-February 1992.
  6. Colleen M. Keller and M. A. Anderson, “Applying Optimal Search Theory to Inland SAR: Steve Fossett Case Study,” October 2008.
  7. Thomas M. Kratzke, L. D. Stone and J. R. Frost, “Search and Rescue Optimal Planning System,” Proceedings of the 13th International Conference on Information Fusion, Edinburgh Scotland, July 26-29, 2010.
  8. “Interim Report n°2 on the accident on 1st June 2009 to Airbus A330-203 registered F-GZCP operated by Air France, flight AF 447 Rio de Janeiro-Paris” by Bureau d’Enquêtes et d’Analyses, Dec. 17, 2009 (see http://www.bea.aero/en/enquetes/flight.af.447/flight.af.447.php).
  9. Ø. Breivik, A. Allen, C. Maisondieu, and J-C Roth, “Wind-induced drift of objects at sea: The leeway field method,” Applied Ocean Research 2011 doi: 10.1016/j.apor.2011.01.005