Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.stsci.edu/institute/conference/iwpss/poster-a-frank.pdf Дата изменения: Tue Mar 20 17:47:28 2012 Дата индексирования: Tue Feb 5 07:08:08 2013 Кодировка: Поисковые слова: http astrokuban.info astrokuban

SOFIA's Challenge: Automated Scheduling of Airborne Astronomy Observations
Jeremy Frank NASA Ames Research Center Mail Stop N269-3 Moffett Field, CA 94035-1000 frank@email.arc.nasa.gov Abstract
The Stra tospheric Observatory for Infrared Astronom y (SOFIA) will requ ire scheduling flights in support of observations proposed b y many differen t investigators. Automa tion will b e cru cial to enable efficient and effective scheduling of SOFIA flights. We have designed an Automated Fligh t Planner (AFP) that accep ts as input a set of requested observa tions, designated flight days, weath er pred ictions and fuel lim ita tions, and searches automatically for highquality flight p lans that satisfy a ll relevant aircraft and astronomer specified constra ints. The AFP can generate one week's worth of flights in tens of m inutes of computa tion time, a feat beyond the capabilities o f human flight p lanners. The ra te a t which the AFP can generate fligh ts enables a sma ll staff to assess and analyze complex tradeoffs b etween fu el consumption, estimated scien ce quality and the p ercentage o f scheduled observations. observations must be grouped togeth er to make up single flights. Fligh t planning for the pr evious gen eration airborne observatory, th e Kuiper Airborne Observ atory (KAO), was done by hand; planners had to choose takeoff time, observations to p erform, and d ecide on setup-actions (called "dead- legs") to position the aircr aft prior to observing. This task frequen tly r equired b etw een 6-8 man hours to plan a single f light. The scope of th e flight p lanning problem w ith the anticipated flight r ate for SOFIA makes the manual approach for flight planning daunting. Howev er, au tomating the planning of flights con tains its own challenges. In this paper , we will summarize the technical ch allenges that hav e been met in order to bu ild an auto mated flight p lanner , and discuss fu ture challenges.

2. SOFIA's Operations Challenge
SOFIA's pred ecessor, the Kuip er Airborne Observatory (KAO), w as a Pr incip le Investigator (PI) driven facility . Scientists who developed instrumen ts had primary responsibility for developing flights in support of their own science. PI s had consider able latitude to choose indiv idual targets, observation duration, and groups of observations on flight days, even th e time of y ear during wh ich to observe. However, th is also forced PIs to have a flight planner on their staff. A variety of tools w ere d eveloped in order to support this mod e of oper ations. One of these, KNAV , was a command-lin e driven too l that accepted as input a specif ication of a flight leg, and calculated th e ground track of th e aircr aft and th e object elevation during the leg. The human flight planner had to choose the takeoff time, observ ations to perform, duration, and decid e on "dead-legs" to position the aircr aft pr ior to observing. The human planner also had to check th e details of each leg for elevation limit vio lations, Special Use Airsp ace (SUA) incursions, and estimate

1. Introduction
The Stratospher ic Observ atory for Infrared Astronomy (SOFIA) is NASA 's next gen eration airborne astronomical observatory. The facility consists of a 747-SP modified to accommod ate a 2.5 meter telescope. SOFIA is expected to fly an averag e of 140 science fligh ts per year over its 20 year lifetime. Depending on the n ature of th e instrument used during flight, 5-15 observations per f ligh t ar e expected . Th e SOFIA telescope is mounted aft of th e w ings on th e port sid e of the aircraf t and is ar ticulated through a range of 20 to 60 degrees of elevation. The telescope has minimal lateral flexib ility; thus, the air craf t must turn constan tly to main tain the telescope's focus on an object during observations. A significan t problem in SOFIA operations is that of sch eduling flights in support of observations. Investigators ar e expected to propose small number s of observ ations, and many


fuel consumption. Former KAO flight plann ers indicated that one flight r equired 6-8 hours to p lan. By contrast, roughly half of SOFIA's flights w ill be driven by General Investigators (GIs), who will propose small numb ers of observations th at must b e assembled into f ligh ts by SOFIA operations staff. Fligh t planners will receive lists of proposals to perform observations w ith on e instrumen t. Each proposal will be ranked in importance by a Time Allo cations Committee ( TA C), and an instrumen t schedule will be developed using these proposals. An instrument w ill stay on the air craf t for a period of weeks; instrumen t ar e ch anged on week ends. Th e expected flight r ate is 2-3 f ligh ts a w eek . Fligh t planners will th en build f lights for each of these instrument blocks. The set of targets and th e (cumulative) durations of th e observ ations w ill b e fully specified, providing less latitude to flight p lanners. Furthermore, it is expected that th ere will be more observations than can be sch eduled, requiring tr adeoffs to optimize f ligh ts. Due to the expected number of flights and complexity of th e problem, scheduling flights by hand would r equire a larg e staff, with th e attendan t expense of tr ain ing and ov erhead costs.

astronomical observ ations for the Hubble Sp ace Telescope [6], Earth Observing Satellites [8] and Mars Exploration Rovers [1]. Howev er, successfu l automation of fligh t planning in troduces n ew challeng es not addressed by previously designed automated planning systems. SOFIA consists of a telescope carr ied abo ard a Boeing 747-SP air craf t. SO FIA can view objects between 20 and 60 degr ees of local elevation (from th e plane of flight). The elev ation of an object depends on the ob ject's coordinates, the air craf t's position and th e time, and th e co mbination of star ting position and star ting time of an observ ation limits th e amount of time an observation can be seen continuously . Checking th is constrain t requir es compu ting th e aircr aft's ground track throughout the course of th e observation. Figure 1 shows th e in ter action between the ob ject's coordinates, the aircraf t's position , the time, and the telescope elev ation. The Earth is shown as an oblate spheroid E. Let p be the air craft's curren t position, (latitude and longitude L) and be th e (Sidereal) time th at th e air craf t is at p. Let S be th e vector from the cen ter of E to p. Let T be th e vector to an astronomical object o at time and P be the plan e tangen t to E at p. Let TP be the projection of T onto P; this is the object azimuth at p. Let V be th e desired heading of the aircraf t. Th e observatory must track th e object inducing T subject to the constraint th at th e angle between V and TP is 270 degrees, because th e telescope po ints out the left-h and side of th e aircr aft. Let H be the elevation vector with respect to P. Most targets are sufficiently far from Earth th at we can assume H = T+S. Du e to the elevation limits imposed by the physical d esign of the telescope cavity, th e angle h b etw een H and TP must b e between 20 and 60 degrees throughout an observation. Solving for the ground track is necessary to compute h over the entire duration of the observation and check th e elevation constraints. The vector T traces a circle follows a latitude line around the Ear th in 24 (Sidereal) hours; th e latitud e is the same as th e observation declination . By contrast, the aircr aft w ill be fly ing at Mach .84, wh ich tr anslates to roughly constan t airspeed (depend ing on the ou tsid e air temp erature). Th e aircraf t ground speed will vary depending on the airspeed and local w ind conditions. Thus, th e direction of V is changing constan tly, and its rate of change dep ends on both the magnitud e of V (the ground speed) and the r ate at which T is chang ing. Finding th e ground track requ ires solving a differ ential equation induced by the coupled mo tion of T and V . The function describ ing the chang e in elevation h

3. The Automation Challenge: Constraints
Figure 1. Solv ing for target elevation and ground track. Automation w ill be critical in order to effectively plan fligh ts with a small staff. Automation will not replace hu man f light plann ers, bu t will provide human planners with tools they can use to plan flights more efficien tly , and more effectively, with smaller staff. This approach has been effectiv e in scheduling


June

requires th e ground track as input, and also depends on the r ate of change of T. Unlike ground-based and space-based telescopes, observing time for SOFIA is limited by flight time, which in turn is limited by the initial fu el load and th e rate of fuel consumption. Th e fuel consu mption of each engine depends on the air craft weight, mach number, outside air temper ature, initial altitude and final altitude. Since aircr aft weight changes as fuel consumed, calcu lating fuel consumption also requir es solving a diff eren tial equation. Pred icted or forecast wind and temp erature are in terpolated and used to calculate the fuel consu mption. Infrared signal is attenuated by atmospheric water vapor. Much of th e atmospher ic w ater vapor is below the stratosphere; the go al of SOFIA is to f ly above atmo spheric water v apor to enab le superior infr ared observing comp ared to ground-based telescopes. Observations may include constraints on line-of-sigh t water vapor (LOS WV). Atmospheric water vapor varies geographically , and is g enerally lower over th e poles; it also diminish es with in creased altitude. Th e altitude achievab le by th e aircr aft dep ends on outsid e air temp erature and aircr aft w eigh t; the h eavier th e aircr aft, the low er the operation al ceiling of the aircraf t due to the requ ired lift. It is also possible to reduce LOS WV by observing targets at high telescope elevation; th is can reduce LO S WV by a factor of 2-3. Atmospher ic conditions in the upper atmospher e during an observation are uncertain at observing time. Furthermore, the targ ets h ave uncertain properties that influen ce the signal received by th e instrumen t. To accoun t for th is, targets w ith w ell known properties ar e used to make calibration measurements. Calibrations must b e done p eriodically throughout a flight in order to ensure that, for any observation, data from a well characterized target was collected under similar conditions. This introduces new observ ation requests with o rdering constrain ts. For instance, an astronomer may request a calibration observation no more than 30 minutes b efore or after a science observation. Finally, Special Use A irspace (SUAs) constrain th e ground track of the aircr aft. SUAs encomp ass a geographic region, hav e a ceiling (and sometimes a floor). SUAs may also b e inactive on some days. SUAs constrain th e ground track of the aircraf t, and thus implicitly constr ain f ligh t plans.

Name

RA (J2000) 18:36:56.34 18:36:56.34 22:57:39.05 22:57:39.05 15:47:20.2 17:45:50.5 17:45:50.5 17:45:50.5 17:45:50.5 17:45:50.5 17:46:15.3 13:37:00.78 13:37:00.78 20:34:17.0 20:34:17.0 20:34:17.0 18:18:51.5 18:18:51.5 18:20:26 19:10:17 19:23:41 16:26 16:26

Dec

Total time hours 1.50 1.50 1.50 1.50 1.00 1.74 1.74 1.74 1.74 1.74 1.35 1.60 1.61 1.48 1.48 1.50 1.07 1.08 0.70 1.11 0.26 1.02 1.03

Rank

Alpha Lyr Alpha Lyr Fomalhaut Fomalhaut HD 141569 Sag A West, Arches, filaments Sag A West, Arches, filaments Sag A West, Arches, filaments Sag A West, Arches, filaments Sag A West, Arches, filaments "Pistol" star, Sickle region M83 M83 NGC 6946 NGC 6946 NGC 6946 M16 M16 M17 W49 A W51 IRS1/IRS2 Rho Oph Rho Oph

+38:47:01.3 +38:47:01.3 -29:37:20.1 -29:37:20.1 -03:46:12 -28:49:28 -28:49:28 -28:49:28 -28:49:28 -28:49:28 -28:50:04 -29:51:58.6 -29:51:58.6 60:08:58.0 60:08:58.0 60:08:58.0 -13:49:30 -13:49:30 -16:10:36 09:06:00 14:31:30 -24:20 -24:20

5 5 5 5 5 4 4 4 4 4 4 3 3 3 3 3 2 2 2 2 2 1 1

Figure 2. A sample flight p lanning problem. Th e list of target coordinates, requested observation duration, and TAC rank ar e shown. Th ese targets ar e to be observed ov er fiv e days in June. A flight p lanning problem is posed as follows: a flight planner is presen ted with a list of a ten s to hundreds of observation r equests, and a per iod of weeks in wh ich to schedule the observations. Fligh t days are designated in advance, since most observations are p erformed with a par ticular instrument, and the instru ment schedule is planned by quarters or semesters. Observations are grouped in to proposals, each of which is given a TAC rank from 15; Rank 5 projects are most importan t. Th e task for the flight planner is to choose the observations to sch edule, group them on flight days, and construct a ser ies of flight p lans for those observations. These f ligh t plans must satisfy all of the constraints descr ibed above. Generally all rank 5 objects are expected to be scheduled; remaining time is allocated to rank 4 observations, and so on. Observations may either hav e constraints on permitted LOS WV ach ieved in a schedule, or th ere may simply be a desire to min imize LOS W V. A samp le problem is shown in Figure 2 . It is exp ected th at there w ill be too many objects to schedule, so a flight plann er must search for a subset of observations to schedu le. Further more, the order in which observations are schedu led in a flight w ill hav e an impact on both the number of observations observed, and f ligh t plan quality as measured by LOS WV for individual observations. Careful ordering is necessary to gen erate good quality f lights. Checking the constraints describ ed above is complex, but not computationally inten sive for a single flight. Unfortunately, so lving a flight planning

4. The Automation Challenge: Search


problem numbers shown in problem options.

may requir of flights. Figure 2. migh t lead

e sear ching Consider the Finding the to sear ching

over very large problem instance best plan for this over millions of

Scheduling fligh ts will also r equire choosing deadlegs to en able an observation. These migh t arise due to either SUAs that must be avoid ed, or to ensure th e aircr aft is at a p lace and time to satisfy the intersection of the observation duration constr aints and elevation limits. Finally, scheduling flights w ill require selecting a good takeoff time for each flight. Both dead-legs and takeoff time selection requ ire sear ching over continuous quantities, e.g. time and dead-leg headings. The number of schedu les for such problems is technically infinite, and th erefore it is practically impossible to search all sch edules.

telescope is allowed to move, the earliest and latest times w iden consider ably . Further , th ere is now th e problem of calculating the reach able positions of the aircr aft, which depends on a variety of factors su ch as wind and weather . Finally, th e upper elevation limit complicates the calculation of feasib le observation times. Figure 4 shows the set of positions on the planet from which an observation can be seen . A t any time, this set of positions is an annulus whose center is th e position at which the target is directly overhead. Th is annulus rotates around the Ear th; as descr ibed previously, the cen ter of the annulus follows th e latitude lin e at latitude , th e target d eclin ation. Furthermore, for some targ ets, th is geometry creates 2 visib ility windows. Overall, th e comp lexity of the constraints, looseness of the bounds, and computational co sts of generating th e bounds effectiv ely preclude the use of pruning techn iques.

5. Challenges for Previous Approaches
Automated p lanning and scheduling has a long history. A co mplete survey is beyond the scope of th is paper; how ever, w e rev iew some methods for automated plann ing and scheduling to see why they ar e unsuitab le for au tomatically scheduling SOFIA flights. A typical method of automatically solving planning and scheduling problems is to search the en tire sp ace of solutions, relying on a comb ination of heuristics to guide search towards good solu tions very early, and efficien t pruning techniques d esign ed to elimin ate infeasible or suboptimal so lutions quickly. As we hav e argued above, th e number of possible schedules ( even without the problem of choosing start times or deadlegs) mak es this approach unlikely to work. Many sch eduling problems assume that the ear liest and latest times at which observations can be scheduled ar e provided up-front to the solver ; these bounds can be adjusted to eff ectiv ely prune schedu les. These quantities may be calculated for astronomical targets observed when SO FIA is at a f ixed location quite easily. If the aircr aft is at position p =(,L), th e earliest and latest times at which the observation is visib le by SOFIA are given by th e so lutions to cos-1((sin(20) ­ (sin )(sin ))/((co s )(cos )))+L+ The sin(20) term arises from the fact that SOFIA 's lower elevation limit is 20 degrees. D epending on th e time of y ear, location of the telescope and th e target coordinates, some targets can be seen all nigh t, and some cannot be seen at all. Howev er, since th e

Figure 4. The set of positions on Earth from which an observation can be viewed at a fix ed time. A further complication arises because of the constraint that th e aircr aft tak es off and lands at designated locations. Typically, th e tak eoff and landing airport ar e th e same. The time and position at which an observation is performed influen ce th e direction th e aircr aft flies. Observing a target while it is rising carr ies the aircr aft South, since targ ets rise in th e East and the telescope poin ts out the left-hand side of the aircraf t. Similar ly, observing a target while it is setting carries the aircraf t North. If the target declination is high er than the air craf t's latitude, th e aircr aft w ill be carried East; otherw ise, the aircr aft w ill be carr ied W est. Car eful scheduling is n eeded to


ensure th e aircraf t lands at its destination while still ensuring th at flights ar e of high quality .

flight; th ird, it turns out that the sear ch for the shortest dead-leg can be solv ed very f ast; for details, see [2]. As previously discussed, complete sear ch is unlikely to solv e this problem. Prev iously w e developed an approach b ased on constructing a f ligh t from beginning to end. The approach es uses gr eedy sear ch and sampling to decide which observation to add next. Th is approach, called ForwardPlanner , is describ ed fully in [2,3]. U ltimately, this approach failed to p erform well as more constraints w ere added to the problem; var ian ts of this approach w ere f ast, or produced high quality plans, but no approach did both . We chose instead to use a form of algor ithm known as lo cal search. Briefly , these algorithms g enerate a candid ate so lution that migh t be eith er inf easible or have poor quality. Th e algorithms then gener ate modifications of the schedu le in an effort to either reduce the number of v iolated constraints or improve the quality, and chooses one of these modif ications as the n ew schedule. While un able to find the best solution, these methods often find h igh quality solutions very f ast. We designed the A FP based on a local sear ch algorith m called Squeaky Wh eel Optimization (SWO) [7]. SWO tak es as input a permutation of tasks to sch edule, and schedu les each task in the order specified by the permu tation. Our version of SWO discards tasks if they can' t be scheduled without violating constr ain ts. Th e permutation and its resu lting schedule ar e then analy zed to construct a new permutation that migh t schedule tasks th at w ere prev iously rejected. The cy cle repeats until all tasks are sch eduled or for a fixed number of iter ations. In Figure 5 we provide a sketch of SWO specialized to solve the f light planning problem. The f irst step is to gen erate a reasonable order for observations in the flight, th en to d ecide on a takeoff time. Observ ations are th en evaluated in order to see if th ey can be sch eduled . If an observation is not trivially visible for the requested duration at the curren t position and time, the shor test dead- leg is found. If SUAs can be avoid ed, and sufficien t fuel remains to return to th e landing airport af ter th e observation leg is completed, th e observation is added to the sch edule, otherwise it is rejected. All observations are processed in order; rejected observ ations ar e r ecorded. Once th is process is completed, SWO attempts to shoehorn the rejected observ ations in to th e ex isting schedule. This is done by considering each location and time at which an observation is p erformed in th e schedule, and trying to sch edule a rejected observation at th at time and position. Generally, this may delay subsequent observations, causing them to be r ejected .

6. Designing an Automated Flight Planner
In this section we d iscuss an approach to automated flight planning that addresses the challenges descr ibed in the prev ious sections. We beg in with a serv er that provides an API for bo th au tomated and manual f ligh t planning. The API makes use of a climatology model or weather pred iction to provide w ind, temper ature and water vapor data. Th is API provides functionality to represen t a f light p lann ing problem, including th e candid ate set of observations and flight days; insert and remove observations from a fligh t, and calculate th e implications; retr iev e details from each leg such as target elevation, LOS WV, SUA incursions, fuel, outside air temperature, w inds, and altitude. We made the follow ing assumptions for problem specifications: Targ et durations may not exceed 2 h o u r s. A maximu m takeoff fuel weight must b e provided as part of th e problem sp ecification. Th e flight dates must be sp ecified in advance, and th e takeoff and landing airports must be designated for each flight d ate. The problem may specify calibration observations, and precedence constraints between observations and calibrations. We made the fo llow ing assu mptions on solution methodology wh ich limit the set of flight plans w e can generate: The automated f light planner attempts to find a sch edule max imizing the su m of TA C ranks of scheduled. An observation is eith er sch eduled su ch that all relevan t constrain ts ar e satisfied, or not sch eduled ; the au tomated fligh t planner does not attempt to divid e observations into smaller pieces. Observations ar e guaranteed to be observed at a time at which the sun is below th e horizon. Takeoff times are no earlier than half an hour before darkness at the takeoff airport, and landing times ar e no more than half an hour after sunrise at th e landing airport. If a scheduled observation has a calibration, th e calibr ation is scheduled on the same f light. Ev ery fligh t obeys all relev ant constr ain ts on observation duration, telescope elevation limits, fuel consump tion, and SUAs. A 20,000 lb fuel reserve is guaran teed for each f light. We chose a policy for constructing dead- legs that limits the set of f lights w e consider. If th e air craft must enable an observation by f lying a dead-leg, w e alw ays choose th e shortest dead-leg . Th is choice has three benefits: first, w e do not hav e to search over an infin ite number of possibilities; second, th is leaves th e maximum amount of time to observe targets later in th e


The prospects for rejection of future observ ations and the relative TA C ranks of the observations involved ar e estimated and u sed to ev alu ate the n et b enef it of any reordering. Th is, in turn, is used to decid e how to revise th e ordering . Random sampling is used to ensure all rejects are giv en a fair ch ance in the nex t schedule. The best schedule of all g enerated is saved. SWO( MaxFlights) Generate observation order P for MaxFligh ts Select the takeoff time for observ ation o in P if o can b e performed at p, (possibly w ith a dead leg) and the aircr aft can land af terw ards Add o to the flight F Update p, else add o to reject list R Update th e best flight B Modify(P,R,F) end Modify(P,R,F) for observation o in R, each observation s in F ps is th e position th e aircr aft before performing s s the time th e air craft beg ins s if o can b e performed at ps,s and the aircr aft can land af terw ards v(o,s) is the net ben efit of order ing o before s Add (o,s,(v(o,s)) to U Randomly choose a reorder ing from U using P(o before s) = v(o,s) / ( w(o,s) inU w(o,s)) Modify and return P Figure 5. Th e Automated Flight Plann er algor ithm, based on Squeaky Wheel Op timization (SWO). Local sear ch algorithms lik e SWO hav e th e property that the more time they are allowed to run, th e better quality results they provide. However, th ere is a "law of diminish ing returns" th at dictates how extr a time leads to increased quality ; performance tuning is necessary to get th e best results. Furthermor e, th e entir e process can also be repeated using a differen t initial order ing. W e note that th e algorithm sk etched shows how to build a single flight; the gener alization to series of flights is str aigh tforward. For a set of represen tativ e problems, SW O can gen erate high quality flights quick ly, providing a good comb ination of speed and quality . A comparison of SWO with ForwardPlann er is shown in Figure 6.

Figure 6. Quality (top) and time (bottom) p erformance of SWO on a small set of fligh t planning problems compared to pr evious approach. Further details of the algorithm and compar ison with previous approaches can be found in [4,5].

7. A New Challenge: Preferences
The automated f light planner descr ibed above was designed primarily to sch edule as many high ranked observations as possib le. However, th ere are o ther objectiv es that h ave arisen during the design of th e planner; handling these objectives will requir e modifying the A FP to meet n ew challenges. As stated above, a primary objective of SOFIA is to minimize th e LOS WV achieved during observations. In [4] we describe a method for minimizing the LOS WV for an individual observation by forcing the observation to occur at the maximum telescope elevation. This can r educe LO S WV by a factor of 2-3, and dead- legs max imizing the telescope elevation can still be found quite efficiently. However, th e optimization is " local" in the sense th at each observation can be optimized alone, but may lead to


poor choices for subsequent observations in the flight; in [4] we report th at this approach leads to a tr adeoff between achiev ing low LOS WV and scheduling more observations. Further work in th is area is possible, by exploiting geographic variation in water vapor, as w ell as achieving aggressive altitude change by manipu lating the in itial fuel load . Anecdotal eviden ce from astronomers who worked with KAO indicates that fligh t planners strove to ensure there w ere no dead-legs at high altitudes or near the end of f light plans. Th e automated f light planner cannot op timize flight p lans th is w ay. Some of th e design decisions of the automated fligh t planner may even contr ibute to plan s with dead-legs, especially at the end of the f ligh t. Ob serving as early as possible may leave no suitable observation at the end of a flight, simp ly because all observations have b een sch eduled . As discussed in a previous section, observ ing targets while they ar e rising carries th e air craf t south; the bias to observe targ ets as ear ly as possib le may lead th e aircr aft to fly south throughout most of the flight. With no impetu s to observe targ ets wh ile th ey are setting, the f light plann er may b e unab le to delay observations and fly north. Finally , th e flight planner is built in such a way that sch eduled observ ations have a high likelihood of staying sch eduled ; scheduled observations are nev er re-ordered, and candid ate reorderings of rejected observations that may "bump" scheduled observations are avoid ed. Searching for good flights will requir e r elaxing these assump tions.

schedule; howev er, sometimes this is not possib le. There are comp lex tr adeoffs betw een the takeoff fuel weight, flight duration, percentage of requested observations that can be performed , and aver age LOS WV for a flight. During flight, air craf t altitude is limited by aircr aft weight. The more fuel carr ied, th e longer the f ligh t, but also the more limited th e aircr aft's initial oper ating altitude. Fuel is costly (JPA costing $3.00 a gallon in April of 2005, and ev en more today) so using it wisely is important. Fur thermore, repositioning the aircraf t to seek drier air or max imize telescope elev ation will gener ally require longer deadlegs; this will reduce time for observing . The constraints governing legal f ligh ts are complex enough that it is no t possible to an aly ze the tr adeoffs up front; one has to generate fligh t plans and compar e them to see the tr adeoffs manif ested. Fur thermore, th e tradeoffs cannot be analyzed just once. The tr ade sp ace will look differen t for differ ent sets of observations, due to the co mplex nature of th e aircr aft's ground track . The trade space will also look diff erent at d ifferen t times of year; temperature and water vapor ch ange throughout the year , affecting fuel consump tion and LOS WV. Finally, the price of fuel is not constan t, so operators' propensity to tr ade science for oper ations costs will also chang e. These trad eoffs are mad e even more complex because th e quantities th at ar e traded ar e usually in compar able. Low ering oper ations costs is valuab le, but it is hard to put a dollar valu e on the science output of the entire observ atory. Similarly, it is not possible (or at least quite diff icult) to determin e whether it is wor thwhile to sacrif ice one observation for lower LOS WV on another observation. We demonstrate these tr adeoffs in a study performed on the observations shown in Figure 2. All flights or iginate and terminate at Moffett Field, CA . Figure 7 shows the p ercentage of scheduled requests, fuel load and LOS WV of the sch edules found by th e AFP. We d esir e flights w ith low LOS WV and many scheduled observations, i.e. those in th e upper lef t corner of Figure 7. We see that th ere ar e significan t tradeoffs between tak eoff fuel load, per cen tage of requested observ ations scheduled, and LOS WV. An extensive ver sion of this analysis w as origin ally published in [4]. In addition to desir ing low LOS WV , astronomers may wish to impose constr ain ts on LOS WV for sensitiv e observations. Th e au tomated planner describ ed in [4] iter atively constr ains the telescope elevation to redu ce LOS WV ; th is is a promising way of manag ing th ese constraints.

8. A New Challenge: Complex Tradeoffs
A highly auto mated flight p lanner will en able SOFIA flight planners to evalu ate comp lex tr adeoffs efficien tly using less staff than w as possible for KAO . In this section w e describ e some of these tradeoffs, and provide a d emonstration of how the auto mated f ligh t planner can help SOFIA meet th ese ch allenges. If we return to the problem of scheduling flights with no dead-leg time, as describ ed above, one way of doing this is to allow choice in the duration of observations, and express a preference function over the value of an observation of any particular dur ation. The au tomated f light p lanner can then search for flights w ith a quality measure that comb ines th e TA C rank, scheduled observation duration, and dead-leg time. How ever , this would requir e astronomers to provide meaningful time-quality tr adeoffs. The approach outlin ed above assumes th at a single quality measure can be assign ed to a proposed


We acknow ledge the contr ibutions of Elif Kurklu Michael A . K. Gross, W illiam V acca, Gor an Sandell, Jacquelin e Davidson, and Sean Casey over the years to this work.

11. References
[1] J. B resin a and A. Jonsson and P. Morris and K. Rajan, "Activity Planning for the Mars Exploration Rovers", Proceedings of th e 15th International Conference on Automated Planning and Scheduling, Kluwer Acad emic Publishing, Monterey, CA, 2005, pp. 40-49. [2] J. Frank and M. A. K. Gross and E. Kurklu, "SOFIA's Choice: An AI Approach for S cheduling Airborn e Astronomy Observations", P roceedings of th e 16th Innovative Application s of Artificial Intellig ence, AAAI Press, San Jo se, CA, 2 0 0 4 , p p . 8 2 8 - 8 3 5 . [3] J. Frank and Observations for the 13th Internat and Scheduling, 235. E. Kurklu, "SOFIA's Choice: Scheduling an A irborn e Observato ry", Pro ceedings of ional Conferen ce on Automated P lanning AAAI Press, Trento, IT, 2003, pp. 226 and Dry : Trading Water e fo r Airborne In frared the 25th International Symposium, IEEE Press,

Figure 7. Tradeoff b etw een tak eoff fuel load, LOS WV and fraction of requested observ ations scheduled for June flight ser ies.

9. SOFIA's Challenges: Planning Ahead
Automation can address many more of SOFIA's challeng es. As men tioned , the automated f light planner assumes th at requ ests specific to diff erent instrumen ts have been allocated to times of year before detailed planning of instrument blo cks commences. A llocation of instrumen t blocks is presently done by hand, but the automated flight planner can poten tially be used to allocate instrumen t blocks. A brute-force method of doing so is to try building schedules for each month of the year, initially trying to schedu le every requ ested observation. A lternativ es involve expand ing on th e basic SWO approach outlined for detailed f ligh t scheduling. A more aggressive challenge, both computationally and op erationally , is to use the AFP to mitigate operational uncer tainty, e.g. due to weather . One str ategy is to move auto mated f ligh t planning onboard the air craf t in order to r efine plans in f light. The oper ational ch allenge is to defin e the set of possible flight p lan changes per mitted by th e observatory, astronomers, pilo ts, and the FAA. Th is challeng e includes limitations of the onboard fligh t hardware and co mmunications link to en able weather condition updates. The challenge is to formulate algorithms that w ill solve th e appropriate rescheduling problems in order to pr eserv e later observations.

[4] J. Frank and E. Kurklu , "High Vapor, Fuel and Observing Tim Astronomy", Pro ceedings of Geoscience and Remote Sen sing Seoul, South Korea, 2005.

[5] J. Frank and E. Kurklu, "Mix ed Discrete and Continuous Algorithm s for S cheduling Airborne A stronomy Observations", P roceeding s of the 2nd In ternational Conference on Constraint P rogramming, A rtificial Intelligence, and Operations Research, Springer V erlag, Prague, C zech R epublic, 2005, pp. 183 - 200. [6] M. Johnston and Scheduling of the Hubble Scheduling M. Zweben and Publishers, San Francisco, 1 G.Miller, "SPIKE : Intellig ent Space Telescope", In Intellig ent M. Fox, eds, Mo rgan K auffmann 994, pp. 257 - 290.

[7] D. Joslin and D. Clem ents, "Squeaky Wh eel Optimization", Journal of Artificial Intelligence Research v 10, AAAI P ress, 1999, pp. 353-373. [8] J. W. Potter and Scheduling LANDS Proceedings of th e Mission Operations Jap an, 1998. J. G asch, "A AT 7 Mis International and Ground Photo Album of Earth: sion Daily Activies", Symposium on Space Data System s, Tokyo,

10. Acknowledgements