From: Daniel Jackson Date: Thu Mar 07, 2002 01:42:36 PM US/Eastern To: Heinz Erzberger , Michelle Eshow , "Russ Paielli Cc: tsafe@geyer.lcs.mit.edu, Michael Jackson Subject: TSAFE thoughts and questions Dear Heinz, Michelle, Russ, John and Tom, We're making some progress on TSAFE. We have an ETMS feed up and running, and a simple component that reads messages and displays aircraft positons. We are about to implement a flight plan parser. We're still trying to get a grip on the problem as a whole though. This week, Michael Jackson (who is now a consultant on a new HDCP project funded by NASA and CMU) was here at MIT to help us formulate some more rigorous requirements concepts. Some thoughts we've had are explained below. We'd welcome any comments, even quick reactions of the form "that's obvious", or "that's absurd". --Daniel 1. A problem without requirements. Of course, TSAFE has requirements in the sense that the developers of the software must have some goal in mind, and this goal can be articulated (eg, as in Heinz's papers, and in further documents one could develop) and the running system could be evaluated with respect to achievement of this goal. However, in a technical sense, from the point of view of software developers, the TSAFE problem doesn't have requirements. To have any cogent notion of requirements, you need to think of them as more than just another specification, at a "higher level", or "closer to the customer", or "more vague, and not yet fleshed out", etc. The only notion we know of that gives some rigorous meaning to the term "requirements", and distinguishes it from the term "specification", is the one developed in Michael Jackson's theory of problem frames. A _requirement_ is a constraint in the domain of the problem itself that the machine being built is intended to bring about or ensure. To achieve this, the software developer invents a _specification_, which is a constraint on the behaviour of the machine being built. The crucial difference is that the requirement is expressed in terms of phenomena of concern to the customer; the specification is expressed using phenomena at the interface of the machine and the problem domain. These sets of phenomena may be one and the same in very simple systems, but in an interesting system such as ATC, they are not and the distinction is crucial. Take a radiotherapy machine, for example. A requirement might be that a patient is never given a lethal dose. The specification of the machine doesn't talk about lethal doses at all -- or even of doses -- but rather of the settings of the parameters that control the devices that administer the radiation. A fundamental step in the development of a safety critical system is to argue that the specification (usually along with some domain properties that are being relied upon) implies the requirement. For example, the designer of the radiotherapy software must make assumptions about the domain (such as that sensors work, and that the dose adminstered to the patient is related in a particular way to the radiation generated, and so on), and use these to justify the specification in terms of the requirement. At first sight, TSAFE can be understood in this way. The requirement is that if two aircraft collide or violate separation, then there must have been a warning generated at least 3 minutes in advance. The domain properties that we rely on would be things like the physical constraints on aircraft motion, etc. Unfortunately, TSAFE doesn't seem to be like this. It won't be possible to make any such guarantees without generating far too many false alarms; two aircraft flying at different altitudes could suddenly turn towards each other, for example, and go from "no conflict predicted" to "conflict in 10 seconds" in a single analysis step. To avoid false alarms, you have to make reasonable assumptions of controller and pilot behaviour based on ATC experience. What this means is that the justification of the specification in terms of the requirements can no longer be conducted internally, within the software development, but becomes a judgment made in the social and economic context of ATC. Even as a final defence, TSAFE is thus a program whose behaviour cannot be simply explained, and which makes no simple guarantees. A perfect implementation of TSAFE, and the best requirements/specification work we could do, would still leave open the possibility of a disaster in which TSAFE does the "wrong thing". 2. A view of TSAFE as a composition of subproblems. Conflict warning is based on predictions of aircraft behaviour. There are several possible bases for prediction. The most conservative is to use only physical constraints: you figure out the envelope of reachable 4D positions, and if the envelopes of two aircraft don't intersect, you can be confident that they will not conflict. In practice, because of the density of aircraft in airspace, this is far too conservative and gives too many false alarms, rendering useless a system that used it exclusively. So some form of inference of the most likely behaviour is needed, by inferring the intent of the pilot, or the "intent" of the flight management system. Such intent can be inferred from historical data (to what extent the aircraft has conformed to previously issued instructions -- that is, the flight plan), from knowledge of standard operating procedures, of how pilots tend to fly to keep passengers comfortable and conserve fuel, etc. There are many different ways in which one could infer intent, and different kinds of intent that might be inferred using different sources of information. Clearly, it would be a mistake to hardwire the design of TSAFE to any particular scheme; moreover, we believe that it makes the development and justification of the software simpler if there is a clean separation between the choice of scheme used and the computations of the individual schemes. So one way to think of the system is that it comprises a set of processes that compute 4D volumes for aircraft. Each process computes on the basis of a different intent theory. There is an additional process that, based on observations of aircraft behaviour (such as conformance to a flight plan) and perhaps also on other sources of information (such as controller input that marks a pilot as less reliable, or an aircraft as handicapped), selects, for each aircraft, the intent theory most likely to hold. Finally, there is the conflict prediction process itself, which compares the 4D volumes that have been generated and selected appropriately. One might use several volumes for a given aircraft that have been generated by different processes, and use them to produce quantitative assessments, or at least rankings, of conflict risk. This point of view is close to Heinz's posited architecture in which first a deviation parameter value for an aircraft is obtained, which is then fed to the conflict probe to determine its possible conflicts. But it is a bit more general and abstract, and may be a more suitable basis for the design of an architecture in which intent theories can be "plugged in". 3. The nature of dead reckoning It's not obvious what it means to compute a dead reckoning (DR) trajectory. Presumably, DR means something like this: you assume the aircraft carries on doing what it's doing, and you predict accordingly. But what does "carry on" mean? If it's turning, does it continue to turn, or does it straighten out on the tangent? If it's climbing, does it continue to climb or level off at the next jet route altitude? If it's descending, do you really assume it will dive into the ground, or do you assume it will level off? These issues suggest that even in determining DR an element of intent must be included. There's also a question of what can be observed. To decide whether an aircraft continues to turn, if you know the bank angle, you know whether the aircraft can straighten up in a short period of time. And if you know the settings of the FMS, you can determine whether it's in a turning mode or not, etc. For the purposes of our prototype implementation, the current plan is to implement components for 3 levels of intent inference: i. the physical envelope; ii. a 4D volume around the flight plan; iii. a 4D volume around a straight line (tangent) DR. For (iii), what should we do about altitude in particular? Presumably, if a plane is level, we assume no change. But if it's climbing or descending, then what? ======================================================================== From: Heinz Erzberger Date: Thu Mar 07, 2002 07:39:31 pm US/Eastern To: Daniel Jackson Cc: Rpaielli@mail.arc.nasa.gov, Meshow@mail.arc.nasa.gov Subject: Re: TSAFE thoughts and questions Dear Daniel, I read your analysis with great interest. Your thought process and "differential diagnosis" concerning the proper formulation of a requirement was very educational. You have certainly put your finger on the weak state of our understanding of the TSAFE design requirement. In my experience, most of the research problems in ATC I have worked on in the past have had a similar level of uncertainty in the requirements. Somehow, after charging ahead for a while and going through a period of trial and error, we usually arrive at a level of understanding that gives us greater specificity in the definition of requirements. I initially thought that the relatively narrow functional capabilities envisioned for TSAFE would make it possible to infer the underlying requirements more easily and would allow a logical design and a corresponding software architecture to be developed in reasonable time. Perhaps I was too optimistic. Concerning your paragraph 2: You correctly point out the problem with false alerts if you do not account for reasonable intent. At any given time to a potential conflict there is a tradeoff between false alert and missed alert. At 5 minutes to a conflict, the tradeoff favors a low rate of false alert and a higher tolerance for missed alert. At 1 minute to a conflict the tradeoff is the reverse. This change in the tradeoff as time to a conflict approaches zero will influence the design of the TSAFE detection algorithm. Intent information ( flight plan) is the primary way to reduce the rate of false alerts. However, trust but verify. So we must monitor intent and have a way to detect violation of intent, especially if a violation would result in an immediate conflict. I called that type of intent violation "maneuver criticality" in my paper. Ranking of conflict risk is consistent with maneuver criticality. Concerning your paragraph 3: You correctly point out that the dead reckoning trajectory concept needs clarification. Here is how we are using the dead reckoning trajectory in climb or descent. We start with the measured vertical velocity of the aircraft. Then we create a 4D trajectory corresponding to that velocity vector for a 4 minute look-ahead time. We check if the trajectory penetrates an assigned altitude ( known from the flight plan) during that time. If it penetrates it, we add a level flight segment at the assigned altitude for the remainder of the 4 minute look-ahead time. If it does not violate any intent constraints, we use it as is. In addition, if it does penetrate the assigned altitude level, we use the unmodified dead reckoning trajectory to check for maneuver-critical conflicts, as I describe in the paper. A similar procedure applies to the horizontal plane. So, dead reckoning does need to be modified to incorporate intent information. I hope this will also help answer your questions near the end. Finally, Russ and I wanted to tell you that we are getting the specifications for the Conflict Alert function that is installed in the Center host computer and is used by controllers today. You might consider it the base line for TSAFE. Conflict Alert is written in the obscure language of the host computer, called JOVIAL. We are thinking about implementing it to run within the CTAS software. Such an implementation would be very useful for various reasons. Russ thought that perhaps you or one of your students might be interested in applying your software design methodology to this baseline requirement. I think it would be an excellent learning opportunity. Actually, if you reduced this requirement to a coded program, we would certainly like to make use of it, too. Finally, perhaps it is time for us to schedule another telecon. Heinz and Russ