Fast binary decision algorithms to enable real time diagnosis of in-flight faults in Unmanned Aerial Vehicles

Submitting Institution

Loughborough University

Unit of Assessment

Mathematical Sciences

Summary Impact Type


Research Subject Area(s)

Mathematical Sciences: Applied Mathematics
Information and Computing Sciences: Artificial Intelligence and Image Processing, Information Systems

Download original


Summary of the impact

Led by Professor Andrews, a computational method for real time mission planning, based on Binary Decision Diagrams (BDD), was developed in the Mathematical Sciences Department at Loughborough University (LU) from 1993-2003. This is fast and accurate and can be used to support decision-making on system utilisation in real-time operation, which has led to the ability to diagnose in flight faults for unmanned aerial vehicle (UAV) applications.

The research has changed the understanding and awareness of the advantages of BDD, resulting in integration into major industrial trials and proprietary software products, including at BAE Systems, one of the world's largest companies in an area of vital importance to UK security and economic development. The methodology has attracted significant research funding in collaborative programmes with industry.

Underpinning research

Fault Trees provide a diagrammatic description of the various causes of a specified system failure in terms of the failure of its components. Fault Tree Analysis (FTA) is used to predict the failure likelihood of complex engineering systems (safety critical systems) and is widely used in industry (Nuclear, Petro-Chemical, Aircraft, etc.). However, FTA is such a computationally intensive method that for large-scale systems approximations are required, i.e. FTA has to be truncated. The Binary Decision Diagrams (BDD) method, developed at Loughborough University overcomes this inherent weakness by performing the calculations exactly, and, being much quicker, offers considerable advantages in efficiency enabling the technique to be used in new contexts.

The development of the BDD system was undertaken at LU by Prof John Andrews, primarily whilst supervising five research students: Ros Sinnamon (PhD 1996), Lisa Bartlett (PhD 2000), Karen Reay (PhD 2002), Sally Beeson (PhD 2002), Rasa Remenyte-Prescott (PhD 2008). The four key aspects researched and reported in LU PhD theses were:

(1) Developing efficient BDD methodology. [3.1, 3.2]

(2) Structuring the logic to identify the critical components and produce an efficient ordering for BDD computation. [3.3]

(3) Modularising BDD for increased efficiency and extended applications. [3.4]

(4) Developing measures for non-coherent fault trees (i.e. where both the occurrence of an event or its non-occurrence may contribute to failure). [3.5, 3.6]

The fundamental research outcomes were published in the above PhD theses and in a number of high quality journal papers and conference proceedings, a number of which won awards. Some of these are listed in Section 3. Presentations at conferences were attended by academics and industrialists in about equal numbers.

The underlying work led to an EPSRC funded project, with BAE Systems as Project Partners, called NECTISE (Network Enabled Capability Through Innovative Systems Engineering) worth £8.4 million (1/11/2005-30/4/2009). Its aims were `to investigate through-life systems management for defence capability' (i.e. to enable defence suppliers such as BAE to develop systems capable of responding to changing requirements in complex dynamically connected networks of supplier-customer organisations). This project involved 11 Universities and BAE Systems. Three of the twelve Investigators and four of the sixteen RAs were based at LU. Prof Andrews was the instigator and principal investigator of this project.

The recognised importance of the BDD method led to its inclusion in the highly significant ASTRAEA (Autonomous Systems Technology Related Airborne Evaluation & Assessment) project (2006-2013). ASTRAEA I (2006-2008) focussed on the technologies, systems, facilities, procedures and regulations to allow unmanned aerial vehicles (UAVs) to operate safely and routinely in civil airspace over the United Kingdom. Following thorough evaluation, BDD has continued to feature in ASTRAEA II (2009-2013).

ASTRAEA I and II have been funded by the public sector (DTI then TSB, CAA and others) and industry (BAE, QinetiQ, Rolls Royce and others) with total funding reported to be £62 million. [Ref: Flight Global 26 April 2010, Ref: July 2012]. In July 2012 the ASTREA project had reached its first goal of combining all the associated research into the design of a UAV which had its maiden flight, see [Ref.]. For all the partners involved in the ASTRAEA project see: [Ref.]

The principle researcher Prof J D Andrews (LU Maths. 1988-2003, LU Systems and Aeronautical and Automotive Engineering 2003-2009) moved to Nottingham University in 2009 to take up the post of Royal Academy of Engineering and Network Rail Professor of Infrastructure Asset Management. This resulted in widening the impact of the BDD method, for rail applications.

Indicators of the significance and reach of papers [3.5] and [3.6] are the two prestigious awards for conference presentations based on the research's application to UAVs, as follows:

(a) Best paper award at the 26th International System Safety Conference, Vancouver, Canada, August 2008, Remenyte-Prescott, R., Andrews, J.D., Downes, C.G., Reliability Analysis in Responsive Mission Planning for Autonomous Vehicles.

(b) The Donald Julius Groen Prize 2009 by the Institution of Mechanical Engineers for a paper: Remenyte-Prescott, R. and Andrews, J.D., (2008), Analysis of Non-coherent Fault Trees Using Ternary Decision Diagrams, Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability, 222, 27-138, DOI: 10.1243/1748006XJRR154.

Following Prof Andrews' move to Nottingham, utilising BDD has continued at Loughborough University in the School of Aeronautical & Automotive Engineering directed by senior lecturer Dr Lisa Jackson (née Bartlett) employed in Mathematical Sciences at LU from 2001-2003 and lecturer Dr Sarah Dunnett employed in Mathematical Sciences at LU from 1996-2003. Furthermore, the impact of BDD is now seen in that BDD features as a tool, which is heavily used in collaborative work with BAE who have continued to support this research at Loughborough University through Case Study awards [5.1, 5.2].

References to the research

3.1. Sinnamon, R.M. and Andrews, J.D., (1996), Fault Tree Analysis and Binary Decision Diagrams, Proc. IEEE Reliability and Maintainability Symposium, 215-222, DOI: 10.1109/RAMS.1996.500665


3.2. Sinnamon, R.M. and Andrews, J.D., (1997), New Approaches to Evaluating Fault Trees, Journal of Reliability Engineering and System Safety, 58, 89-96, DOI: 10.1016/S0951-8320(96)00036-1


3.3. Bartlett, L.M. and Andrews, J.D., (2001), An Ordering Heuristic to Develop the Binary Decision Diagram Based on Structural Importance, Reliability Engineering and System Safety, 72, 31-38, DOI: 10.1016/S0951-8320(00)00103-4


3.4. Reay, K. and Andrews, J.D., (2002), A Fault Tree Analysis Strategy Using Binary Decision Diagrams, Reliability Engineering and System Safety, 78, 45-56, DOI: 10.1016/S0951-8320(02)00107-2


3.5. Andrews, J.D. and Beeson, S., (2003), Birnbaum's measure of component importance for non-coherent systems, IEEE Transactions on Reliability, 52, 213-219, DOI: 10.1109/TR.2003.809656


3.6. Beeson, S. and Andrews, J.D., (2003), Importance measures for non-coherent-system analysis, IEEE Transactions on Reliability, 52, 301-310, DOI: 10.1109/TR.2003.816397



EP/D505461/1, A Research Proposal in Systems Engineering Addressing the Question: Are you prepared for NEC? £8,397,350, 01/11/05-30/04/09. This was co-ordinated by Prof. Andrews who was also PI before moving to Nottingham

ASTRAEA I consisted of 16 Projects [Ref], value £32 million. ASTRAEA II which followed consisted of 6 Projects, value £30 million. Total funding for ASTRAEA £62 million.

[Ref:]. The projects involved 7 major companies and 5 universities and about 12 SME's and subcontractors and was led at Loughborough University by Prof. Paul Chung (now Dean of Science at LU).

The research quality of the work, in terms of originality, rigour and significance is evidenced by the above papers and the large amount of external funding obtained, including industrial funding, in addition to the prizes referred to in Section 2 above.

Details of the impact

We now present evidence to show that the research cited in §2 and §3 above has changed the understanding and awareness of major industrial companies of the advantages of BDD and has resulted in its integration into major industrial trials and proprietary software products.

BDD is now routinely used as an analysis tool for certification of engineering designs, i.e. before implementation. Much more significantly, BDD can also be used to support decision-making on system utilisation in real-time operation. For example, as component faults are reported or environmental conditions change fast BDD calculations can be performed to update the prediction of the probability of mission failure; when this reaches some preset critical threshold appropriate action can be taken. BDD is a major development with wide and significant applications. In particular, recognising BDD's value, BAE Systems have adopted it for use in unmanned aerial vehicles (UAVs).

BDD's are used for many different aerospace applications such as by NASA ( and by the group of Antoine Rauzy at the Ecole Polytechnique in Paris [5.5].

Example 1

The development of BDD led to a large collaborative project with BAE Systems as Project Partners, called NECTISE (Network Enabled Capability Through Innovative Systems Engineering). It was also supported by EPSRC and worth £8.4 million (1/11/2005-30/4/2009) with about half being industrial funding. The research involved ten universities, led by Loughborough University. Prof John Andrews was the principle investigator of the submission, and Prof Michael Henshaw (Loughborough University) later led the programme. The impact of BDD on this work and its outcome for BAE can be verified by [5.1]. The key aspect being that the BDD decision-making capability in the area of real-time diagnostics was fundamental to a number of BAE Systems research themes and changed the understanding and awareness as to the operational advantages conferred by BDD. In particular the work led to the integration of BDD's into major industrial research programmes: Autonomous Systems and Integrated Vehicle Health Management (IVHM).

Example 2

The development of BDD at Loughborough University led to it being thoroughly tested and its viability demonstrated for an entirely different application, firstly in BAE Systems-led projects ASTRAEA I (2006-8) and then in ASTRAEA II (2009-2013) concerning UAVs. It is predicted that following the Tornado, no future UK/European military aircraft will have onboard pilots, and for such aircraft UAVs will be the norm. BAE's Advanced Technical Centres have carried out experimental trials and BAE's Military Air & Information Group is (in 2012-13) undertaking UAV flight trials. BDD is an essential part of this work and the impact of this research will be felt wherever UAVs are deployed — such as earth observation, monitoring of pipelines and power lines, detecting and controlling forest fires, law enforcement, border control and coastguarding. The UAV must have the ability to respond to changing conditions. Such changes can occur due to component failures causing loss of functionality or reduced redundancy, changing weather conditions, or the emergence of a threat such as another aircraft in the locality. When these conditions are reported the mission success likelihood is re-evaluated using the BDD approach, accounting for the new conditions.

Mission failures can be considered in two ways: catastrophic failure where the vehicle will be lost, and mission failure where the mission objectives are not accomplished but the vehicle lands safely. When the predicted likelihood that the vehicle will successfully perform its intended task becomes unacceptably low, action is required to mitigate this situation. This action takes the form of mission reconfiguration. Mission reconfiguration for a UAV selects a new route, new mission objectives, or can be implemented to abort the mission and make an emergency landing. It is this mission reconfiguration process through the use of BDD's which provides the main impact in UAV design.

Within the ASTRAEA project there have been a number of projects (or themes). Specifically, ASTRAEA's Theme T7 `Health Management System Design' addressed the issue of `maintaining real-time system awareness of the UAV'. This was a collaborative project between BAE Systems, LU and Aberystwyth University. According to a BAE Systems member, `BDD was an essential underpinning methodology' [5.1].

The significance of ASTRAEA I's Theme 7 (referred to above) led to its being selected as a finalist (one of three) in the 2009 Institution of Engineering and Technology Innovation Awards, a further indicator of the impact of the BDD method [5.2, 5.3].

The research has therefore been integrated into experimental trials in one of the world's largest manufacturing companies in an area of vital importance to the future of UK security and economic development.

A further indicator of the impact of BDD comes from the fact that commercial software companies such as ISOGRAPH, ARALIA and ITEM SOFTWARE now incorporate BDD in their proprietary packages for Fault Tree Analysis [5.4]. The research therefore changed the awareness of another industry leading to new products and services.

Sources to corroborate the impact

The following sources of corroboration can be made available at request:

5.1. Email from Control Systems Design — Trent 1000, Aero Engine Controls — Rolls-Royce plc Group Sin C-6, PO Box 31, Derby, DE24 8BJ

5.2. Email from BAE — Warton — Military Air & Information

5.3. The Institution of Engineering and Technology (IET FINALIST) — Highly commended award made 25 November 2009.

5.4. ARALIA — "Seminal work on the use of BDD to assess importance factors has been done by J. Andrews and his students ...." A quotation taken from a chapter entitled BDD for Reliability Studies in K.B. Misra ed., Handbook of Performability Engineering. Elsevier. pp 381-396, 2008. Available as PDF at: