From: "Gregory Dennis" To: "Heinz Erzberger" ; "Russ Paielli" Cc: Subject: TSAFE Algorithm Proposal Date: Thursday, June 27, 2002 11:23 AM Dear Heinz and Russ, We're at the point in the design of our prototype where we have to make some tentative decisions as to what algorithms we will use to perform TSAFE's various functions. Namely, we need to decide how we will carry out conformance monitoring, trajectory synthesis, critical maneuver detection, no transgression zone detection, and conflict detection. Drawing on your papers and our past conversations, I've made some algorithm proposals below for our first simple prototype. Conformance Monitoring We would like flight conformance to be boolean: either the flight is blundering or it is not blundering. Blundering we will define as too far from the assigned flight route (off track) and/or at a heading not aligned with the current flight route segment (off heading). Determining whether a flight is off track or off heading requires first finding the point on the route that will serve as the basis for comparison, i.e. where on the route the flight is supposed to be. I will call this the "snap-back point" - the location on the route the flight would be snapped back to if it were adhering perfectly to the assigned trajectory. To find this snap back point, I suggest simply searching for the closest point on the route to the flight. Note that this snap-back point will always be either a fix or a point located at the intersection of a route segment and a perpendicular that intersects the flight. Once the snap-back point is found, one must only measure the distance between the it and the aircraft to determine if the flight is off track; and measure the angle between the aircraft's heading and the heading of the snap-back point's route segment to find if the flight is off heading. Special consideration must be given to cases in which the snap-back point is a fix or near a fix, so as to allow for a more tolerable range of possible headings. This solution, though the simplest, has its drawbacks. Imagine a route shaped like a U, for instance. If a flight moving downward along the top-left hand segment makes an early turn, bringing it in line with the top right-hand segment, TSAFE could find the the flight as both on track and on heading, yet it should have been deemed bludering. One could concoct more of these "backtracking" route examples that would cause this method to fail, but I postulate that such routes do not exist. Can you verify that? A note about heading. To determine if a flight is on heading and to synthesize dead reckoning trajectories, we must of course know the flight' s heading. However, the ASDI feed does not give us the flight's heading or its ground track angle. To approximate this number, we will need to look at the line between the flights last position and its current position. To make matters worse, ETMS updates come only once every 60 seconds. Given this, do you feel our heading calculation would be worth anything? Trajectory Synthesis In the course of conflict detection, we propose synthesizing at most two trajectories: a dead reckoning trajectory and an assigned trajectory. If a flight is blundering, we will probe along its dead reckoning trajectory. The dead reckoning trajectory assumes the flight "stays on course." As you know, we've had extended discussion as to what this exactly means, but we seem to have concluded it is best represented by an extension of the velocity vector. We will assume atypical circumstances such as holding patterns, etc will be handled separately as special cases. For non-blundering aircraft, we will probe along the flights assigned trajectory. For the assigned trajectory synthesis, I propose snapping the flight back to its route (assume it is located at the snap-back point) and then following the flight route from the snap-back point forward. Note that the "snap back" approach is very different from the PFS_C trajectory that assumes the flight rejoins its flight path. Though probably less accurate, it is much simpler and hopefully adequate for our purposes. Critical Manuever Detection First, let's recognize that critical maneuver detection can only occur when the flight is not blundering. If it is blundering, and therefore significantly far from its assigned route, it won't be in a position to complete an assigned maneuver. In addition, because we lack adequate vertical intent information, we will only be looking for horizontal maneuvers. This narrows down the critical maneuvers we are interested in to the instances in which a non-blundering flight is approaching a fix in its route. To do critical maneuver detection in this case, as it turns out, is equivalent to snapping the flight to its route and probing along the dead reckoning trajectory. Thus, our dead reckoning probe can double as (1) conflict detection for blundering aircraft and (2) critical maneuver detection for non-blundering aircraft. Conflict Detection and No Trangression Zone Detection Daniel disagrees with me on this point, but I believe these two problems are effectively the same. To me, conflict detection and no transgression zone detection are both processes for determining whether two flights are, or will be, close to one another, except conflict detection uses a shorter separation distance in its definition of "close". Thus, for both conflict detection and no transgression zone detection, I believe we can use the same algorithm: draw 4-dimensional envelopes around the predicted trajectories of the aircraft and look for intersections between them. It would seem to greatly simplify TSAFE by allowing the 4D envelope intersection calculation to serve both purposes. Naturally, wider candidate envelopes with shorter time horizons would probably be used for no transgression zone detection, and we wouldn't try to detect a no transgression zone between two flights if they were already deemed to be in conflict. Daniel is concerned that the envelope intersection cannot be used to detect no transgression zones - that it is just a different problem. I feel that they can be done in the same manner, as long as we craft the envelopes appropriately. What are your thoughts on this? As you can tell, I've proposed a version of TSAFE that is algorithmically simple and largely heuristic-free. Moreover, I've tried to reuse logic to minimize the number of calculations TSAFE performs, as well as TSAFE's overall size. I invite your thoughts and reactions to these ideas and we look forward to hearing back from you. Greg ======================================================================== From: "Russ Paielli" To: "Gregory Dennis" Subject: Re: TSAFE Algorithm Proposal Date: Tuesday, July 02, 2002 5:35 PM Hi Greg, I just want you to know that I am working on a reply to your message. I hope to send it within a couple days. Russ Paielli Gregory Dennis wrote: > Dear Heinz and Russ, > > We're at the point in the design of our prototype where we have to make > some tentative decisions as to what algorithms we will use to perform > TSAFE's various functions. Namely, we need to decide how we will carry out > conformance monitoring, trajectory synthesis, critical maneuver detection, > no transgression zone detection, and conflict detection. Drawing on your > papers and our past conversations, I've made some algorithm proposals > below for our first simple prototype. ======================================================================== From: "Russ Paielli" To: "Gregory Dennis" Cc: "Heinz Erzberger" ; "TSAFE group at MIT" Subject: Re: TSAFE Algorithm Proposal Date: Thursday, July 11, 2002 1:29 PM Gregory Dennis wrote: > Dear Heinz and Russ, > > We're at the point in the design of our prototype where we have to make > some tentative decisions as to what algorithms we will use to perform > TSAFE's various functions. Namely, we need to decide how we will carry out > conformance monitoring, trajectory synthesis, critical maneuver detection, > no transgression zone detection, and conflict detection. Drawing on your > papers and our past conversations, I've made some algorithm proposals > below for our first simple prototype. > Sorry for the delay in replying. My comments are below. > > Conformance Monitoring > We would like flight conformance to be boolean: either the flight is > blundering or it is not blundering. Blundering we will define as too far > from the assigned flight route (off track) and/or at a heading not aligned > with the current flight route segment (off heading). Determining whether a > flight is off track or off heading requires first finding the point on the > route that will serve as the basis for comparison, i.e. where on the route > the flight is supposed to be. I will call this the "snap-back point" - the > location on the route the flight would be snapped back to if it were > adhering perfectly to the assigned trajectory. > First a comment on terminology. I'm not sure if "blundering" is a word we want to make heavy use of. Perhaps "off track" or "off course" are more appropriate. Those words each have slightly different connotations (track vs. course), but I mean them in a more or less generic sense. If that causes confusion, perhaps we could say "off plan" or something like that. By the way, I think the FAA uses the terms "free track" and "flat track" to basically mean radar tracks that are off the flight plan or on it (but I'm not sure about the exact definitions of those terms). As for making conformance a boolean state, I'm not sure about that either. I could easily see having an intermediate state, analogous to a yellow traffic light, to indicate marginal conformance or near non-conformance. I think we need to keep our options open on that. But perhaps this is mainly a matter of semantics. We could perhaps have a boolean state with substates within each category. For example, "off track" could be subdivided into "just a bit off track" and "way off track". I don't know the final solution, but I think we should be careful not to lock ourselves into a simple binary state just yet. > > To find this snap back point, I suggest simply searching for the closest > point on the route to the flight. Note that this snap-back point will > always be either a fix or a point located at the intersection of a route > segment and a perpendicular that intersects the flight. Once the snap-back > point is found, one must only measure the distance between the it and the > aircraft to determine if the flight is off track; and measure the angle > between the aircraft's heading and the heading of the snap-back point's > route segment to find if the flight is off heading. Special consideration > must be given to cases in which the snap-back point is a fix or near a fix, > so as to allow for a more tolerable range of possible headings. > That seems reasonable to me. You should certainly consult with Tom Reynolds on this if you haven't done so already. The important design consideration is to hide the details of this determination inside a function or class with a standard interface. The function should have as inputs the cross-track position error, the course (or heading), and perhaps the turn rate. The along-track position might be needed too in some cases or scenarios We should then be able to switch different conformance test functions in and out, at least in the development phase. > > This solution, though the simplest, has its drawbacks. Imagine a route > shaped like a U, for instance. If a flight moving downward along the > top-left hand segment makes an early turn, bringing it in line with the > top right-hand segment, TSAFE could find the the flight as both on track > and on heading, yet it should have been deemed bludering. One could > concoct more of these "backtracking" route examples that would cause this > method to fail, but I postulate that such routes do not exist. Can you > verify that? > In that case, you need some logic to decide when the airplane has legitimately crossed over to the other leg of the "U". If it just takes a short-cut over, that should not be considered satisfactory. This gets into the idea of 4-D trajectories. 4-D trajectory conformance takes into consideration along-track position as a function of time. Heinz doesn't think we need to worry about 4-D trajectories, however. > > A note about heading. To determine if a flight is on heading and to > synthesize dead reckoning trajectories, we must of course know the flight' > s heading. However, the ASDI feed does not give us the flight's heading or > its ground track angle. To approximate this number, we will need to look > at the line between the flights last position and its current position. To > make matters worse, ETMS updates come only once every 60 seconds. Given > this, do you feel our heading calculation would be worth anything? > Heading and speed estimation is a black art in the current system. The ARTCC host computers have an "alpha-beta" filter to estimate heading and speed from very noisy position measurements, but apparently it imposes a big lag during turns. I think CTAS now uses the raw radar information to provide better speed and heading estimates. When ADS-B with GPS becomes available, velocity accuracy will be greatly improved, of course, and that is important since we are considering a long-term solution here. The ETMS update rate of once per minute will really hamstring you, I think. Heinz has already contacted you regarding the possibility of using recorded radar-tracking data or CTAS "cm_sim" files. > > Trajectory Synthesis > In the course of conflict detection, we propose synthesizing at most two > trajectories: a dead reckoning trajectory and an assigned trajectory. If a > flight is blundering, we will probe along its dead reckoning trajectory. > The dead reckoning trajectory assumes the flight "stays on course." As you > know, we've had extended discussion as to what this exactly means, but we > seem to have concluded it is best represented by an extension of the > velocity vector. We will assume atypical circumstances such as holding > patterns, etc will be handled separately as special cases. > I don't think you necessarily want to restrict yourself to "at most" two trajectories. If the aircraft is far off track, you might need to "fan out" the possible turn angles back to course. When an aircraft is far off track, you are basically playing a guessing game, and you need to be conservative, especially in the current system. In the future, I think methods will need to be developed to communicate with the aircraft and determine its intent. Also, in the future I think it will be less common to have aircraft far off track, but we will still need methods to deal with it when it happens. > > For non-blundering aircraft, we will probe along the flights assigned > trajectory. For the assigned trajectory synthesis, I propose snapping the > flight back to its route (assume it is located at the snap-back point) and > then following the flight route from the snap-back point forward. Note > that the "snap back" approach is very different from the PFS_C trajectory > that assumes the flight rejoins its flight path. Though probably less > accurate, it is much simpler and hopefully adequate for our purposes. > I don't know if that will be sufficient or not, but my guess is that it won't be. > > Critical Manuever Detection > First, let's recognize that critical maneuver detection can only occur > when the flight is not blundering. If it is blundering, and therefore > significantly far from its assigned route, it won't be in a position to > complete an assigned maneuver. In addition, because we lack adequate > vertical intent information, we will only be looking for horizontal > maneuvers. This narrows down the critical maneuvers we are interested in > to the instances in which a non-blundering flight is approaching a fix in > its route. To do critical maneuver detection in this case, as it turns out, > is equivalent to snapping the flight to its route and probing along the > dead reckoning trajectory. Thus, our dead reckoning probe can double as (1) > conflict detection for blundering aircraft and (2) critical maneuver > detection for non-blundering aircraft. > Yes, I think that is basically correct, except for the part about "snapping the flight to its route". > > Conflict Detection and No Trangression Zone Detection > Daniel disagrees with me on this point, but I believe these two problems > are effectively the same. To me, conflict detection and no transgression > zone detection are both processes for determining whether two flights are, > or will be, close to one another, except conflict detection uses a > shorter separation distance in its definition of "close". > > Thus, for both conflict detection and no transgression zone detection, I > believe we can use the same algorithm: draw 4-dimensional envelopes > around the predicted trajectories of the aircraft and look for > intersections between them. It would seem to greatly simplify TSAFE by > allowing the 4D envelope intersection calculation to serve both purposes. > Naturally, wider candidate envelopes with shorter time horizons would > probably be used for no transgression zone detection, and we wouldn't try > to detect a no transgression zone between two flights if they were already > deemed to be in conflict. > Daniel is concerned that the envelope intersection cannot be used to > detect no transgression zones - that it is just a different problem. I > feel that they can be done in the same manner, as long as we craft the > envelopes appropriately. What are your thoughts on this? > You might be on to something here, but I'm not sure I "get it". I agree that you can think of the no-transgression zones as a special limit on the 4-D trajectory an aircraft is allowed to fly. Perhaps your idea would be clearer if you explained how it would work in specific cases. > > As you can tell, I've proposed a version of TSAFE that is algorithmically > simple and largely heuristic-free. Moreover, I've tried to reuse logic to > minimize the number of calculations TSAFE performs, as well as TSAFE's > overall size. I invite your thoughts and reactions to these ideas and we > look forward to hearing back from you. I've always believed in keeping things as simple as possible and avoiding unnecessary heuristics, so I certainly appreciate your approach. If any of my comments above are unclear or too terse, please don't hesitate to follow up with further discussion. Russ Paielli