Planning and replanning for a constellation of agile Earth observation satellites

Romain Grasset-Bourdel?† and Gérard Verfaillie? Antoine Flipo†

? †
Onera - The French Aerospace Lab, Toulouse, France CNES, Toulouse, France
{[Link], [Link]}@[Link] [Link]@[Link]

Abstract zation of the management system we assume. Then, we de-

scribe the chronological forward search algorithm we devel-
In this paper, we present the problem of planning off-
line on the ground all the activities of a constellation of
oped to solve the planning problem. After that, we describe
next-generation agile Earth-observing satellites and the the replanning problem and how the planning algorithm can
specific algorithm that was developed to solve it. Then, be adapted to a replanning setting. Experimental results on
we present the replanning problem that arises when ur- real-size scenarios show the right behavior of the chosen ap-
gent observation requests are received during plan ex- proach.
ecution. We show how the planning algorithm can be
used in this replanning setting, with some modifications Satellite constellation
that limit computing time and favour plan stability and
optimality. The constellation we consider is made up of two identical
satellites1 moving on the same orbit (circular, low altitude,
quasi-polar, and heliosynchronous) with a phase shift of 180
Introduction degrees between the two satellites (see Figure 1).
The context of the work we present in this paper is the Eu-
z
ropean defence MUSIS project (Multinational Space-based
Imaging System for Surveillance, Reconnaissance, and Ob-
servation) and more precisely the management of the MU-
SIS agile satellites that are equipped with high-resolution
optical observation instruments.
As usual, such satellites are managed from the ground by
a mission planning system which receives user observation
requests, builds regularly satellite activity plans over a lim-
ited horizon ahead (typically one day), and receives plan ex- 180
o
y
ecution reports. These plans must meet all the physical con-
straints and satisfy as well as possible the user requests. x
However, such a management system is not very reactive.
Any observation request, arriving at any time during the day,
must wait for the next day to be taken into account. This led
project managers to consider a more reactive management
system that would take full advantage of the presence of sev-
eral ground control stations and of the numerous associated
satellite visibility windows that allow updated activity plans
to be uploaded. Figure 1: Two-satellite constellation.
In such a setting, replanning may be called before any
satellite visibility window. Replanning problem data is, on
the one hand, a current activity plan involving hundreds of Each satellite (see Figure 2) is equipped with thrusters
observations and, on the other hand, some urgent obser- which allow orbital manoeuvres to be performed in case of
vation requests (at most some tens). The goal is to build a too important drift with regard to the reference orbit and
quickly (efficiency) a new plan over the rest of the day that with gyroscopic actuators which allow very quick attitude
is of an as high as possible quality (optimality) and is as movements (agility) useful to perform observations and tran-
close as possible to the previous one (stability). sitions between observations.
In this paper, we present the physical system we have to 1
The planning algorithm we propose is able to manage any
manage, the physical constraints we must meet, the user re- number of satellites, possibly not identical: not the same param-
quests we must satisfy as well as possible, and the organi- eter values.
 tion, constant speed, and constant deceleration) performed
concurrently along each axis (roll, pitch, and yaw).

o1 o2 o1 o2

Figure 3: How the angular distance and thus the minimum

transition time between observations depends on the time at
which the first ends.

Observation Due to maximum observation angles, the ob-

servation of a given area on the ground must be performed
within one of its visibility windows. Its duration is fixed,
because it only depends on the required scanning speed on
the ground. The satellite attitude trajectory to be followed
during observation depends on the time at which it starts.
Figure 2: Artist view of a satellite.
Download The same way, due to maximum communica-
tion angles, a data download must be performed within one
of the visibility windows of one of the ground reception sta-
A telescope, with two focal planes, allows observations tions. However, this does not suffice because the satellite
to be performed in the visible and infra-red spectra, with attitude must be compatible with download (the target sta-
two images (visible and infra-red) within day periods (on tion must remain within the satellite antenna communication
the ground) and only one image (infra-red) within night peri- cone). The result is a set of effective communication win-
ods. A mass memory allows observation data to be recorded dows that depends on the satellite attitude trajectory. Obser-
and a high-rate large-aperture antenna allows it to be down- vation and download can be performed concurrently. Two
loaded towards ground reception stations. Solar panels al- images (visible and infra-red) resulting from the same ob-
low batteries to be recharged when the satellite is not in servation (within a day period) must be downloaded towards
eclipse. For the sake of agility, all these equipments are the same station and during the same station overflight.
body-mounted on the satellite.
Memory The amount of memory available on board for
Physical constraints observation data recording must be never exceeded.

The physical constraints that must be met can be classified Instruments Concerning the three instruments (high-rate
into six classes : attitude trajectory, observation, download, antenna, visible and infra-red focal planes) a minimum pre-
memory, instruments, and energy. heating time must be met before use, as well as a maximum
total ON time and a maximum number of ON/OFF cycles
Attitude trajectory Thanks to gyroscopic actuators, the over the planning horizon, for the sake of reliability. Tem-
satellite is permanently moving around its gravity centre perature of the infra-red focal plane is automatically reg-
along the three axes (roll, pitch, and yaw). These attitude ulated by a cryothermic system, but temperatures of both
movements allow observations of areas on the ground to the visible focal plane and the antenna must remain below
be performed by scanning them. They also allow transi- a given level. Moreover, it must be checked that, at every
tions from the end of an observation to the beginning of the point on the satellite attitude trajectory, the focal planes are
following to be performed relatively quickly. These move- not dazzled and thus not damaged by the sunlight (minimum
ments are limited in terms of angular speed and acceleration, angle between the satellite axis and the Sun direction).
resulting in minimum times for moving from an attitude to
Energy On-board energy cannot exceed a maximum level
another. However, the attitude that is required to observe
due to battery limitations. For the sake of safety, it must
a given area on the ground depends on the orbital position
remain above a given level, particularly when the satellite
of the satellite and thus on the time at which the observa-
is in eclipse and solar panels produce nothing. When the
tion is performed. The result is a minimum time between
satellite is not in eclipse, the production of energy via the
the end of an observation and the beginning of the following
solar panels depends on the satellite attitude trajectory. On
that depends on the time at which the first ends (see Figure 3
the other hand, energy consumption depends on instrument
for a schematic 2D illustration). Moreover, computing this
activations.
minimum time requires solving a complex continuous opti-
mization problem (see (Beaumet, Verfaillie, and Charmeau
2007)). For solving it efficiently inside planning algorithms, User requests
dedicated approximate algorithms were developed at ON- With each user request, are associated a polygon which is
ERA, assuming three-phase movements (constant accelera- split into strips, a priority level, a weight, and a deadline.
Typically, three priority levels are available, from 3 (the • for the antenna and the visible focal plane, its temperature.
highest) to 1 (the lowest). It is assumed that any request
Six types of action are available for each satellite:
of priority p is preferred to any set of requests of priority
strictly less than p. Weights allow to express preferences be- 1. orbital manoeuvres which are mandatory and character-
tween requests of the same priority level and are assumed to ized by starting and ending times and attitudes and by an
be additive. In general, user requests exceed the constella- energy production (function of the attitude trajectory dur-
tion capacity and choices must be made using request prior- ing the manoeuvre);
ities and weights. 2. observations which are characterized by a strip, a visibil-
It is assumed that any strip can be observed using only one ity window, and a starting time;
strip overflight. With each strip, are associated a geograph-
ical definition, observation durations (day or night), image 3. data downloads which are characterized by an image, a
sizes (visible, day or night infra-red), a maximum observa- reception station, a communication window, and a starting
tion angle, and a set of triples hsatellite, visibility window, time;
weather forecasti. 4. heliocentric pointings (solar panels directed towards the
Sun in order to recharge batteries as fast as possible)
Management system which are characterized by starting and ending times;
User requests may arrive at any time and, each day, at a given 5. geocentric pointings (satellite axis directed towards the
time, a plan is built for the next day from all the requests Earth centre; default action when there is nothing else to
that are not out of date and not fully satisfied yet. This plan do) which are characterized by starting and ending times
is built on the ground and then uploaded to the satellites for too;
execution. Typically, up to ten minutes of computing are
available for planning. After plan execution, observation 6. instrument switchings which are characterized by an in-
data that has been downloaded to the ground is analyzed, strument and a time.
taking into account the actual cloud cover, and satisfied re- It must be observed that actions of all the types, but the
quests are removed. third and sixth (data downloads and instrument switchings),
In addition to these normal user requests, urgent ones may constrain the satellite attitude and are thus mutually exclu-
arrive at any time too. The latter must be taken into account sive. They must be performed in sequence. Only data down-
as soon as possible. To do that, before any visibility window loads and instrument switchings can be performed in paral-
between a ground control station and a constellation satel- lel, at any time for instrument switchings, but only within
lite, an updated plan is built for the rest of the day from all effective communication windows for data downloads. As a
the requests, either normal or urgent. Replanning is guided consequence, a plan has the form of a sequence of actions
by two objectives: on the one hand, to produce a new plan of any type, except the third and sixth, with attitude move-
of highest quality, as in planning, and, on the other hand, ments between consecutive actions and with data downloads
to maintain in the new plan the highest number of observa- and instrument switchings in parallel.
tions present in the previous one, because a plan is a kind Any plan must satisfy all the constraints described above
of commitment facing users. In order to be able, to take in Section Physical constraints.
into account urgent requests until the last minutes, we con- We define the criterion to be optimized as a vector of util-
sider that half of the computing time available for planning ities vp , one for each priority level p. Two vectors resulting
is available for replanning, that is up to five minutes. from two plans are lexicographically compared. For each
Differently from other studies that considered on-board priority level p, let Rp be the set of requests of priority p.
planning and replanning (Chien et al. 2004; Beaumet, Ver- For each request r, let wr be the utility associated with r
faillie, and Charmeau 2011), planning and replanning are defined as the weight of r weighted by four factors whose
here performed on the ground. This choice is justified by the value is between 0 and 1 and which represent (1) the per-
fact that the information used by planning and replanning centage of realization (observation and data download), (2)
(normal and urgent user requests) comes from the ground the mean percentage of cloud cover, (3) the mean observa-
and not from board. In such a setting, there would be no ad- tion angle, and (4) the mean data delivering delay, over all
vantage to plan on board. Limited computing resources on the strips of the polygon associated with r. At each
P priority
board would even make it disadvantageous. level p, we assume that utility is additive: vp = r∈Rp wr .
The result is a global hierarchical (lexicographic) criterion
Planning problem modeling and a local additive criterion at each priority level.
The planning problem can be modeled using for each satel-
lite the following state variables: Planning algorithm
• the current time and thus the orbital position; To solve this planning problem, we developed a specific
• the attitude position and speed along the three axes; chronological forward search algorithm with dedicated deci-
sion heuristics, constraint checking, limited lookahead, and
• the available memory and energy; backtrack in case of constraint violation, which guarantees
• for each instrument, its status (ON or OFF), the remaining the production of a plan that may be not optimal, but is really
ON time, and the remaining number of ON/OFF cycles; executable by the satellites.
Decreasing priorities First, the algorithm we developed At the second decision level, geo or heliocentric point-
works by decreasing priority levels from 3 (the highest) to ings are inserted between t and t0 when possible. Once in-
1 (the lowest). At each priority level p, the starting point sertions are decided, the satellite attitude trajectory is com-
is the plan Pl produced at the previous level p + 1, which pletely fixed from t to t00 . Hence, the production of energy
includes orbital manoeuvres, observations (of priority p + 1 and the effective communication windows can be computed
or more), pointings (geo or heliocentric), data downloads, and the absence of focal plane dazzle can be checked by
and instrument switchings. However, what is kept from Pl simulating trajectories.
is only the sequence Seq of orbital manoeuvres and obser- At the third decision level, data downloads are inserted
vations present in Pl , without their starting times. Other within the effective communication windows from t to t00
actions present in Pl , such as pointings, data downloads, or and memory constraints can be checked. This means that
instrument switchings are disregarded. At level p, observa- observations (first decision level) have priority over down-
tions of priority p will be inserted into Seq by moving start- loads (third level). This choice is justified by mission and
ing times when necessary. Other actions, such as pointings, algorithm considerations: on the one hand, observation is
data downloads, or instrument switchings will be added to the main system bottleneck and, on the other hand, it is nec-
build a consistent plan. At priority level 3, the starting point essary to know the effective communication windows and
is the set of orbital manoeuvres which are imposed on the thus observations and pointings before planning downloads.
mission planning system by the satellite control system and At the fourth decision level, instrument activations are in-
can be classed as observations of priority 4. serted in order to satisfy the requirements in terms of ob-
Such an approach is justified by the fact that any request servation (visible and infra-red focal planes) and download
of priority strictly greater than p is preferred to any set of (high-rate antenna). Energy and instrument constraints can
requests of priority p. This leads us to consider the sequence be checked.
of observations present in the plan produced at level p + 1 as Figure 5 shows an example of decisions at the four levels:
being mandatory when building a plan at level p. at level 1, observation o0 , starting at t0 , is chosen; at level
A forward chronological algorithm At each priority 2, a geocentric pointing followed by a heliocentric one are
level p, the algorithm builds a plan in a forward chrono- inserted before t0 ; at level 3, data downloads d1 and d2 , fol-
logical way, from the beginning Ts of the planning horizon lowed by d3 and d4 , are inserted between t and t00 ; at level
to the end Te. With any step of the algorithm, are asso- 4, the following decisions are made concerning instrument
ciated the current time t, the next observation o of priority activations: at time t, the visible focal plane was OFF and
p+1 or more to be included in the plan because it belongs to it is decided to switch it ON only before o0 ; on the contrary,
Seq, and the set Os of observations of priority p that can be the infra-red focal plane was ON and it is decided to main-
scheduled after t and before o. At the first step, t = Ts and tain it ON between t and t00 ; at time t, the antenna was OFF,
o is the first observation in Seq. The algorithm chooses an and it is decided to switch it ON before downloading d1 and
observation o0 in Os as the next observation to be included to maintain it ON until the end of d4 ’s download.
in the plan and a starting time t0 for o0 . If Os = ∅, then
o0
o0 = o (observation o is chosen and then a starting time for
t0 observations
it). At the next step of the algorithm, t is replaced by the t geo helio t00
ending time t00 of o0 and, if o0 = o, then o is replaced by pointings
the observation that follows it in Seq (empty when o is the d1 d2 d3 d4
last observation in Seq). Figure 4 illustrates two successive downloads
ON
steps of the algorithm. The algorithm stops when o and Os
visible focal plane
are both empty (no other observation to be included in the ON
plan). infra−red focal plane
ON
o0 o antenna

t t0 t00
o Figure 5: Example of decisions at the four levels: (1) obser-
vations, (2) pointings, (3) downloads, and (4) instruments.
t

Figure 4: Two successive steps of the forward chronological Once decisions are made at the four levels, a consistent
algorithm. plan is available from t to t00 , extending the plan that already
exists from Ts to t, and the planning process can continue
from t00 , starting from a completely known satellite state.
Decision levels This is the first decision level (1) of the This incremental process, which built incrementally a
algorithm (choice of the next observation to be included). complex system trajectory, is the main justification for us-
Once this choice is made, the algorithm makes other choices ing a forward chronological search.
over the temporal horizon from t to t00 at other decision lev- For the sake of simplicity, we present the algorithm by as-
els: (2) possible insertion of geo or heliocentric pointings, suming only one satellite. However the planning process is
(3) possible data downloads, and (4) instrument activations. in fact interleaved on the two satellites and the next planning
step is the earliest one over the two satellites. observation o0 is chosen, one chooses for it a starting time
t0 that maximizes the increase in the criterion resulting
Backtracks At any decision level, in case of constraint vi- from the insertion of o0 at time t0 (function of the obser-
olation, other choices are made. If no other choice is avail- vation angle; gain) minus the sum of the decreases in the
able, a hierarchical backtrack at the relevant decision level criterion resulting from this insertion (other observations
is triggered (see Figure 6). that would become impossible and whose quality would
degrade because of too large observation angles; cost);
current state at time t
2. at the second level, an expert rule aims at making eas-
ier energy production and data download; it systemati-
Observation
cally chooses a geocentric pointing when the satellite is
in eclipse; when it is not in eclipse, it gives priority to
remove observation o’ Pointings
a heliocentric pointing in order to recharge batteries, ex-
cept in case of visibility of a ground reception station, be-
cause a geocentric pointing always allows data download,
1 dazzle whereas a heliocentric one may prevent it;
remove observation o’
0
remove observation o’
3. at the third level, as in the knapsack problem, one chooses
an image of maximum priority that maximizes the ratio
remove the Downloads between the increase in the criterion resulting from its
last download
download (gain) and the duration of this download (cost);
memory
problem
1 4. at the fourth level, the choice is, for each instrument, at the
0 end of each mandatory activity period, between switching
it OFF and maintaining it ON; these choices have an im-
Instruments pact on four “resources”: energy, temperature, total ON
remove observation o’
time, and number of ON/OFF cycles; the result is a kind
of multi-criteria decision problem; for each resource and
0 1 energy or
no more download
to be removed antenna problem for each alternative a, it is possible to compute a ratio
1 0 between remaining and maximum quantity, if a is cho-
1
sen; finally, as usual in multi-criteria decision making,
focal plane
problem one chooses the alternative that maximizes the minimum
0
ratio over the four resources.
decision made over [t,t’’] horizon
The main difference between this algorithm and the one
presented in (Beaumet, Verfaillie, and Charmeau 2011)
Figure 6: Hierarchical backtracks between decision levels. is the use of backtrack mechanisms in case of con-
straint violation and of more sophisticated choice heuristics.
At the first level, if Os = ∅ and thus o is chosen, but in- In (Beaumet, Verfaillie, and Charmeau 2011), no backtrack
sertion of o is impossible, a chronological backtrack is trig- was allowed and heuristics were limited to randomized de-
gered to the previous insertion of an observation of priority cision rules.
p. However, in order to avoid as much as possible such sit-
uations, the latest observation ending times are propagated Replanning problem modeling
from the end to the beginning of Seq before planning. When replanning, the main question in terms of modeling
is how to manage the possibly contradictory two objectives:
Heuristics At all the decision levels, heuristics are nec-
(1) the intrinsic quality of the new plan which can be mea-
essary to make choices. These heuristics are crucial to the
sured using the same criterion as the one used when plan-
production of good quality plans because, for the sake of ef-
ning and (2) the plan stability which can be measured by the
ficiency, the algorithm backtracks only in case of constraint
difference between the new and the previous plan.
violation and never to try and improve on the current plan. It
The resulting two questions are: (1) how to define the dif-
may be important to stress the difference between the global
ference between two plans? and (2) how to combine quality
optimization criterion defined in Section Problem modeling
and stability objectives? These questions were discussed in
and the local heuristics described below which only aim at
planning (Fox et al. 2006; Cushing, Benton, and Kambham-
guiding the search towards good quality solutions.
pati 2008), in scheduling (Sakkout, Richards, and Wallace
The following heuristics were implemented at the various
1998), and in constraint satisfaction (Verfaillie and Jussien
decision levels:
2005).
1. at the first level, as in the knapsack problem, one chooses Our experience led us to consider that there is no generic
an observation o0 that maximizes the ratio between the in- answer to these questions. Answers depend on the problem
crease in the criterion resulting from the insertion of o0 at hand. In our problem, the quality of a plan is measured
(gain) and the time consumed by this insertion (t00 − t, by a vector of utilities vp , one for each priority level p. We
considering the earliest starting time for o0 ; cost); once an maintain this global hierarchical view when replanning. For
each priority level p, let Rp be the set of requests of priority We chose to develop a chronological forward search algo-
p. For each request
P r, let wr be the utility associated with r. rithm. On this basis, the idea is to use the same algorithm
We have: vp = r∈Rp wr . Let Ip ⊆ Rp be the set of re- for replanning with slightly different data.
quests r of priority p that are negatively impacted by replan- Let P be the set of observations that were considered
ning (at least one strip of the polygon associated with r was when planning, let S ⊆ P be the set of observations that
present in the previous plan, but does not appear in the new were selected by planning (present in the previous plan), and
one). We define the stability as the P sum over the impacted let U be the set of observations associated with urgent re-
requests of the loss in utility: sp = r∈Ip (wr0 − wr ) with quests.
wr0 (resp. wr ) the previous (resp. new) utility associated We consider four possible modes of replanning.
with r. sp is positive or null. The lower sp , the more stable 1. in the first mode, the set of candidate observations is
the plan. Then, we define the criterion to be optimized when S ∪ U ; however, we favour stability and consider that
replanning as a weighted combination of quality and stabil- all the observations in S are mandatory; for that, it suf-
ity: vs p = vp − α · sp , with α a positive parameter to be set fices to consider them as observations of priority 4; in this
by system users according to the importance they attach to mode, we try and insert the urgent observations in the pre-
stability with regard to intrinsic quality. vious plan without removing anything; however, starting
To take an example, let us consider two requests A and times of observations in S can be moved; the same way,
B of the same priority and of weights wA and wB , both pointing, download, and instrument activation plans can
reduced to one strip and thus to one observation. Let us be modified;
assume that A was previously planned, that B is a new ur- 2. in the second mode, the set of candidate observations is
gent request, but that A and B are in conflict (it is impos- the same: S ∪ U ; however, at each priority level, we con-
sible to satisfy both). The value of a new plan involving A sider that observations in S have priority over observa-
(no change) is wA , but the value of a new plan involving B tions in U ; for that, it suffices to add 0.5 to the priority
(change) is wB − α · wA . The second one is preferred only level of each observation in S; as a result, the number of
if wB − α · wA > wA , that is wB > wA · (1 + α). priority levels is multiplied by 2; in this mode, an observa-
The data of a replanning problem is very similar to the one tion in U of priority level 3 cannot remove an observation
of a planning one: same requests, state variables, actions, in S of the same priority level, but can remove an obser-
and constraints. The main difference is in the definition of vation in S of lower priority level (2 or 1);
the criterion to be optimized. Specific data is however:
3. in the third mode, the set of candidate observations re-
• the previous plan; mains the same: S ∪ U ; at each priority level, there is no
• a set of urgent requests to be taken into account; priority between observations in S and U ; all of them are
equally considered in terms of priority level;
• for each constellation satellite s, a replanning horizon
from the first time t at which a new plan can be received 4. finally, in the fourth mode, the set of candidate observa-
for execution by s to the end of the current day: before t, tions is P ∪ U (all observations); as in the previous mode,
the previous plan cannot be modified by replanning. at each priority level, there is no priority between obser-
vations in P and U ; all of them are equally considered in
Replanning algorithm terms of priority level.
When replanning, temporal pressure is generally higher than Roughly speaking, the search is less and less restrictive
when planning. This pressure takes generally the form of from the first to the fourth mode: less and less constraints
a deadline for plan production. In our problem, this dead- imposing previously planned observations, more and more
line is the beginning of the next visibility window between observations taken into account. It would be possible to run
a ground control station and a constellation satellite. these modes sequentially or concurrently and to get the best
Local search methods (Aarts and Lenstra 1997) are known result obtained by the deadline.
to be able to produce quickly good quality solutions on hard Modes 1 and 2 naturally favour stability. Modes 3 and 4
combinatorial optimization problems. One of their strengths do not so. To favour stability in the latter modes, it is sensi-
is that they can be used the same way, with the same local ble to modify the heuristics used at the first level (choice of
change operations, in a static setting (to solve a problem) the next observation to perform and of its starting date) by
and in a dynamic one (to solve a slightly modified problem, multiplying by (1 + α) the weight of a request r if one of its
using a previously computed solution). This is why they observations o was present in the previous plan (o ∈ S). The
are intensively used in a context of planning and replan- idea is to give these requests more importance when making
ning (Zweden et al. 1994; Chien, Knight, and Rabiddeau observation choices (see the example in the previous section
2000). for an intuitive justification).
To solve our problem, we did not choose to use local
search methods, mainly because of the high potential cost of Scenarios and experimental results
a local change: adding or removing an action in the middle Planning and replanning algorithms were implemented in
of a plan requires the complex system trajectory to be com- a tool, called PLANET for PLanner for Agile observatioN
puted and checked again from the adding/removing point to satElliTes, which was developed for this mission, on the ba-
the end of the planning horizon. sis of a previous tool (Beaumet, Verfaillie, and Charmeau
 first (easy) instance servations of priority 3 are more geographically conflicting
mode 1 mode 2 mode 3 mode 4 with each other.
CPU time (s) 130 275 225 232 In order to evaluate the four replanning modes, we con-
prio 3 0 0 1 0 sidered a scenario where 10 urgent requests of priority 3
# obs. removed prio 2 0 0 0 0 (the highest) arrive some minutes before uploading the daily
prio 1 0 1 5 4 plan. Such a scenario is one of the most stressing for re-
# urgent obs. added 10 10 8 8 planning because planning must be performed again over
prio 3 103.7 102.4 101.5 101.7 the whole one-day planning horizon. For the combination
criterion prio 2 115.2 114.8 114.8 114.8 of the quality and stability objectives, we set α = 0.5. Fol-
prio 1 96.9 95.4 93.7 94.3 lowing such a scenario, we built three replanning instances
second (medium) instance
of increasing difficulty:
mode 1 mode 2 mode 3 mode 4 1. in the first one, strips associated with urgent requests are
CPU time (s) 133 270 221 231 randomly generated on continents; the probability that
prio 3 0 0 1 0 these strips be in overloaded areas is low;
# obs. removed prio 2 0 4 1 1 2. in the second one, strips associated with urgent requests
prio 1 0 4 4 7 are manually generated on areas where many requests of
# urgent obs. added 2 10 9 9 priority 1 or 2 are present, but few of priority 3;
prio 3 101.9 104.6 103.1 103.3
3. in the third one, strips associated with urgent requests are
criterion prio 2 115.3 111.6 113.6 115.2
manually generated on areas where many requests of pri-
prio 1 96.9 93.4 93.0 92.7
ority 1, 2, or 3 are present.
third (hard) instance
Table 1 and Figure 7 show the results obtained by re-
mode 1 mode 2 mode 3 mode 4
planning in its four modes on these three instances: CPU
CPU time (s) 129 263 217 225
time, number of observations removed from the previous
prio 3 0 0 3 2
plan at the three priority levels, number or urgent observa-
# obs. removed prio 2 0 2 2 2
tions added in the new plan, value of the new plan at the three
prio 1 0 5 6 13
priority levels, taking into account quality and stability.
# urgent obs. added 0 7 8 8
On the first (easy) instance, Mode 1 is clearly the most
prio 3 100.8 103.0 102.7 103.2
efficient: all the urgent requests can be added without re-
criterion prio 2 115.3 112.3 113.2 114.0
moving anything; moreover this mode is the fastest in terms
prio 1 97.0 93.4 93.1 93.2
of CPU time.
On the second (medium) instance, Mode 2 produces the
Table 1: Results on the three instances using the four replan-
best results in terms of criterion value: all the urgent requests
ning modes
are added; no request of priority 3 is removed (it is anyway
forbidden in Mode 2); only requests of priority 1 and 2 are
2011). Algorithms were experimented on a real-size real- removed (fewer of priority 2 than of priority 1); however,
istic instance, built by CNES (French Space Agency) and this mode is the most costly in terms of CPU time.
whose characteristics are the following ones: On the third (hard) instance, things are more complex. No
urgent request can be added using Mode 1. 7 urgent requests
• a one-day planning horizon; can be added using Mode 2. One more (8) can be added
• 8 ground reception stations; using Modes 3 or 4. However, fewer requests of priority
• 3 priority levels; 3 are removed using Mode 4. Moreover, fewer requests of
priority 3 and 2 are removed than of priority 1 using this
• 1166 observation requests, all of them with polygons lim- mode. Mode 4 produces the best results in terms of criterion
ited to one strip and all of them of the same weight (1); value, closely followed by Mode 2.
among them, 377 of priority 3 (the highest), 419 of prior- In terms of CPU time, replanning modes 2, 3, and 4 re-
ity 2, and 370 of priority 1 (the smallest); quire nearly the same time as planning does. However, this
• meteorological forecast built from climatological data. time remains less than the maximum time specified in the
On this instance, planning takes 236 seconds (about 4 mission requirements (5 minutes). Replanning mode 1 re-
minutes), using a 3Ghz Intel processor with 2.5Go of RAM, quires only half the time used for planning. Moreover, most
running under Linux. In the resulting plan, 906 (78%) ob- of the time, replanning will be faster because it will be not
servations are performed and downloaded, 16 (1%) are per- performed over a one-day horizon, as in our scenario, but
formed, but not downloaded, and 244 (21%) not performed only on the remaining part of the day.
at all. Among the observations of priority 3, 280 (74%) are
performed. Results are 367 (88%) for priority 2 and 275 Conclusion
(74%) for priority 1. The fact that relatively more observa- In this paper, we showed that is it possible to use the same
tions of priority 2 are performed than observations of prior- chronological forward search algorithm for planning and re-
ity 3 can be explained by the fact that, in this instance, ob- planning, only by modifying request priorities and weights,
 100 100 Verfaillie, G.; and Charmeau, M. 2007. Estimation of

% observations maintained
the Minimal Duration of an Attitude Change for an Au-

% urgent obs. added

95 tonomous Agile Earth-observing Satellite. In Proc. of the
13th International Conference on Principles and Practice
90
of Constraint Programming (CP-07), 3–17.
99
85 [Beaumet, Verfaillie, and Charmeau 2011] Beaumet, G.;
Verfaillie, G.; and Charmeau, M. 2011. Feasibility
80 of Autonomous Decision Making on board an Agile
Earth-observing Satellite. Computational Intelligence
98 75
27(1):123–139.
mode 1 mode 2 mode 3 mode 4
[Chien et al. 2004] Chien, S.; Sherwood, R.; Tran, D.; Ci-
100 100 chy, B.; Rabideau, G.; Castano, R.; Davies, A.; Lee, R.;
% observations maintained

90 Mandl, D.; Frye, S.; Trout, B.; Hengemihle, J.; D’Agostino,

% urgent obs. added

80
99 J.; Shulman, S.; Ungar, S.; Brakke, T.; Boyer, D.; Van-
70
60
Gaasbeck, J.; Greeley, R.; Doggett, T.; Baker, V.; Dohm,
98 50
J.; and Ip, F. 2004. The EO-1 Autonomous Science Agent.
40 In Proc. of the 3rd Conference on Autonomous Agents and
30 Multi-Agent Systems (AAMAS-04), 420–427.
97
20
[Chien, Knight, and Rabiddeau 2000] Chien, S.; Knight, R.;
10
96 0
and Rabiddeau, G. 2000. An Empirical Evaluation of the
Effectiveness of Local Search for Replanning. In Proc. of
mode 1 mode 2 mode 3 mode 4
the ECAI-00 Workshop on "Local Search for Planning and
100 100 Scheduling".
% observations maintained

90
[Cushing, Benton, and Kambhampati 2008] Cushing, W.;
% urgent obs. added

99 80
70
Benton, J.; and Kambhampati, S. 2008. Replanning as
98 60 Deliberative Re-selection of Objectives. Technical report,
50 Arizona State University.
97 40
[Fox et al. 2006] Fox, M.; Gereveni, A.; Long, D.; and Se-
30
96 20
rina, I. 2006. Plan Stability: Replanning versus Plan Repair.
10 In Proc. of the 16th International Conference on Automated
95 0 Planning and Scheduling (ICAPS-06).
mode 1 mode 2 mode 3 mode 4 [Sakkout, Richards, and Wallace 1998] Sakkout, H. E.;
prio 3 prio 2 prio 1 urgent obs. added Richards, T.; and Wallace, M. 1998. Minimal Perturbation
in Dynamic Scheduling. In Proc. of the 13th European
Figure 7: Graphical view of the replanning results; top: first Conference on Artificial Intelligence (ECAI-98), 504–508.
(easy) instance; middle: second (medium) instance; bottom: [Verfaillie and Jussien 2005] Verfaillie, G., and Jussien, N.
third (hard) instance 2005. Constraint Solving in Uncertain and Dynamic En-
vironments: A Survey. Constraints 10(3):253–281.
[Zweden et al. 1994] Zweden, M.; Daun, B.; Davis, E.; and
as well as the set of candidate observations. We considered Deale, M. 1994. Scheduling and Rescheduling with Itera-
four more or less restrictive replanning modes. First experi- tive Repair. In Zweden, M., and Fox, M., eds., Intelligent
ments show that their efficiency in terms of quality, stability, Scheduling. Morgan Kaufmann. 241–256.
and computing time depends on the instance type.
Running these four replanning modes in parallel would be
an option. Another option would be to run them in sequence.
For that, the order according to which modes are called
could be determined for each replanning instance by per-
forming a quick analysis of the setting: urgent requests ei-
ther geographically spread, or concentrated on already over-
loaded areas.

References
[Aarts and Lenstra 1997] Aarts, E., and Lenstra, J., eds.
1997. Local Search in Combinatorial Optimization. John
Wiley & Sons.
[Beaumet, Verfaillie, and Charmeau 2007] Beaumet, G.;