Highly Reactive Decision Making: A Game with Time

1 Introduction

Monitoring and supervision deal with dynamic systems (or artefacts) , that evolve across time. A (human or au­ tomated) agent is in charge of observing (through sen­ sors) what happens, recognizing the typical behaviour, ~nd acting towards the artefact (through activators), for mstance to put it back into a normal state, or to process some safety procedure. This on-line process needs real­ time efficiency, and is reactive in the sense that actions are taken according to observations.

A model-based approach [Dvorak and Kuipers, 1989] has been introduced to deal with this problem, first com­ puting off-line faulty models of the artefact that are used on-line as associative models matched with incom­ ing observations. Next steps are predicted from the hy­ pothetical current situation, and incoming observations ~re ~h~cked to confirm the hypothesis. But time is only tmphett, through successive states in a dynamic decision tree, which is not expressive enough in realistic domains. Some approaches [Nejdl and Gamper, 1994] manage to attach a temporal qualification to behavioral modes us­ ing a rich set of temporal relations. More appealin~ are temporal chronicle recognition systems [Dousson et al.,

Thierry Vidal

LGP, ENIT

4 7 avenue d 'Azereix F-65016 Tarbes cedex, FRANCE

1993], where temporal constraint networks are used as associative models.

But all these approaches deal with systems in which an action is the consequence of a complete and fully rec­ ognized sequence of observed events. This paper deals with an explicit temporal framework in highly reactive domains, in which actions and observations continuously respond to each other. We extend the temporal chronicle formalism to mix events representing observations from the artefact and the agent actions, and equip them with goodness values expressing preferences among them. We also use a decision tree such as the one designed in [Coradeschi et al., 1996], but here only as a preprocessing step before decision making, to merely branch the cur­ rent static context onto a subset of relevant chronicles therefore restricting the number of candidate patterns. '

The agent has now a larger choice of decisions to take at any time. The goal is not to recognize a bad situation and put the system back into a good one, but to con­ tinuously take decisions that anticipate bad situations and push the system into better ones, which is basically a game playing process. For that we rely on the timed game automaton model [Asarin et al., 1995] that is best suited for continuously changing systems. Next transi­ tions are computed from the set of candidate patterns inheriting corresponding goodness values. Then our ne~ algorithm PLAY-AUTOMAT chooses a transition to select and a correct time to do so, using a least-commitment and opportunistic strategy, and following a formal deci­ sion policy based on a definition of the utility of each possible decision: we prove that our process is optimal in that it always takes thP. decision with highest utility.

Section 2 recalls the basic models and global archi­ tecture described in [Coradeschi and Vidal, 1998]. Our approach is illustrated through a specific example in the area of one-to-one aircraft combat in Section 3. Then Section 4 focuses on the very contribution of this paper, namely the new algorithm for on-line decision making.

2 Basic models and global process

2.1 The basic decision-tree approach

In [Coradeschi et al., 1996], the agent is equipped with a context (i.e. a set of propositions describing the current state of the world), and a decision tree. To each leaf of the tree is attached a decision (atomic action or sequence of actions). At each step of the simulation process the context is updated with new events received and inter­ preted. Then the decision tree is visited down, proposi­ tions in the context being matched with the conditions appearing at each node, until a leaf is reached. Each action has a priority value that changes dynamically, so that in the cases where multiple leaves are applicable and actions are mutually exclusive, the best one is selected. It is then sent to the simulator, which will update the context, and so forth.

This mechanism is highly reactive and efficient, and agent behaviours are easy to specify and test . It is how­ ever difficult to code in it reactions to sequences of tem­ porally related events.

2.2 Possible evolutions as chronicles

In the temporal system IxTeT [Dousson et al. , 1993] used for dynamic situation assessment, temporal evo­ lutions are taken into account in the shape of chroni­ cles, that are Temporal Constraint Networks [Schwalb and Dechter, 1997] on which classical constraint propa­ gation techniques can be run: time-points represent in­ stantaneous changes or begin/end points of intervals of time over which a fluent is true, and constraints between them are precedences labelled by arithmetic intervals of possible values, allowing to express dates of events and durations of fluents. Then chronicles are matched with incoming events, dynamically maintaining the set of can­ didates. As soon as a chronicle is fully recognized, an action written in the chronicle description is triggered.

This model is well-suited for dynamic applications with temporally expressive behaviours like nuclear plant or gas turbine monitoring [Milne et al., 1994], where su­ pervision is the key word. As an associative model, it provides high on-line efficiency; anyway, two shortcom­ ings compelled us to improve it somehow.

• Reactivity can be considered as being weak in Ix­ TeT, since an action only follows an ordered set of observations. Therefore we chose to extend the ini­ tial formalism to mix events representing both ob­ servations from the artefact and the agent actions , which in turn enforces a corresponding distinction between two types of constraints between events, as in [Vidal and Fargier, 1997]. A numerical constraint between e1 and e2 (with e1 before e2) will be said to be controllable iff e2 is an action, and contingent iff e2 is an observation.
• The second restriction is in the classical strict dis­ tinction between normal and abnormal behaviours: the agent here has a large choice of actions at any time that can push the system into various "more or less good" situations. Therefore we chose to extend the IxTeT approach by adding to each chronicle a goodness value in the range [-1,1], -1 meaning the worst possible case (e.g. breakdown) at the chroni­ cle completion, 1 a behaviour that fully entails the

system specifications, 0 a situation that keeps bal­ anced between eventual failure or success.

2.3 Timed game automata

The model we present here is inspired by recent advances [Asarin et al., 1995] on timed automata models [Alur and Dill, 1994], used for describing the dynamic behaviour of a system. It consists in equipping a finite-state au­ tomaton with time, allowing to consider cases in which a system can remain in a state during some time t be­ fore taking the next transition. This is made by adding continuous variables called clocks that are reset when some transitions are taken, then grow uniformly until they are checked on a later transition through some con­ dition (guard) that must be true for enabling it.

Such tools are well-suited for continuous real-time games : for each player, transitions are either activated or received, and some states are designated as winning ones. That extends the discrete game approach [Pearl, 1984], with the following pros: (1) there are no "turns" and the adversary need not wait for the player's next move, and (2) each player not only chooses a transition, but also the delay to wait before taking it.

This is especially relevant for controlling reactive sys­ tems in which one has to "play against Nature" , the goal being to synthesize a "safe" controller, i.e. add con­ ditions to compel the automaton to reach winning states for the agent. For our purpose we only need a restricted model: we do not need to build a complete automaton but we just compute the next states, transferring the goodness values from corresponding chronicles so as to compare them and choose the "best" one. That leads to the following restricted game automata definition.

Definition 2.1 (Short-term Game Automata)

• A= (Q, w, Z, ~, T, qo) is a game automaton where
• Q is the discrete set of states,
• qo E Q is the initial (current) state,
• w : Q -+ [ -1, 1] adds goodness values to states,
• Z = (~+)d is the clock space, H(Z) is the set of condition relations over clocks (see [Asarin et al., 1995} for details) , and R(Z) is the set of reset functions on clocks,
• ~ = ~b x ~ax {wait} is the input alphabet (b /a events plus the specific event wait, see 4.2),
• T = Tb x Ta ~ Q 2 x ~ x H(Z) x R(Z) is the set of

(q,q') E Q 2 , CJ E ~ , g E H(Z),r E R(Z) ,

• transitions of the form T = < q, q', CJ, g, r > whe_re

T ETa is activated iff CJ E ~a,

T E Tb is received iff CJ E ~b·

2.4 Global architecture

We have already presented [Coradeschi and Vidal, 1998] our associative model mixing a decision tree and chron­ icles, simply replacing actions in leaves by sets of chron­ icles, as a simple way to add context handling to the chronicle model. Then our global process will be to (1) determine the set of active candidate chronicles visit­ ing down the decision tree, (2) build the corresponding automaton, extracting from the chronicles the possible next states and transitions to them, and (3) select the best decision to make NOW by "playing" the automaton. This is illustrated through figure 1.

The global algorithm and its two first steps will not be reported here (see [Coradeschi and Vidal, 1998]), but the following example should give the reader an insight into it. Then we will focus on the decision-making step (3), namely the algorithm PLAY-AUTOMAT.

3 An example in the air-combat domain

The air-combat domain is a highly reactive domain where decisions are made under real-time constraints. An automated pilot should be able to predict his oppo­ nent's next moves and select the action that minimizes possible threats and maximizes chances of success. Pre­ dicting other agents behaviours is a hard task but some typical patterns have been developed by the military to help in identifying manoeuvres of the opponents.

We have built a simplified example of a one-to-one beyond visual range combat situation (the aircrafts can see each other just with board instrumentation). Fig­ ure 2 shows the chronicles corresponding to most plau­ sible typical patterns, where events labelled with a are the automated pilot own actions and the ones with b are the opponent observed actions. We start with a and b flying towards each other, and a sees b moving right . Two possible guesses for a are that b will continue es­ caping or turn back for an intercept. Then a can move left (evolution Q1), making b moving left as well. The resulting situation gives no special advantage for any of the pilots. Otherwise a may accelerate, then both pi­ lots turn left for an intercept (Q2 ), which would put a into a better situation as he can more easily attack on the side, or he may observe b escaping by moving right (Q3 ), which is even better. Q4 is also a good situation as a does not do anything and b escapes. But not do­ ing anything might as well be bad, if b moves left to intercept (Q5 ). Precise delays (here in seconds) are also added to the constraints.

Then figure 3 shows the result of step (2), the algo­ rithm Build-automat . One should notice the correspon­ dence between durations of controllable/contingent con­ straints in chronicles and guards on activated/received transitions in the automaton. Receiving the event bmr puts the pilot into a state in which there are four posible next events enext given by the five chronicle candidates of figure 2. For each one a new state is added together with the transition to this state, labeled with enext, comput­ ing the guard from the corresponding chronicle. Good­ ness values are transferred as well, with here the case where an event (aacc) belongs to two different chroni­ cles, so one keeps the min of the goodness values.

4 On-line decision making

4.1 Decision policy: basic definitions

Before presenting the algorithm that computes an accu­ rate decision from the built automaton, wes first define our decision policy, in the spirit of studies carried on in qualitative decision theory (see e.g. [Boutilier, 1994]) . Goodness values provide preferences over consequences of the decisions, but a decision might raise distinct con­ sequences. In this uncertain framework the utility of a decision must be defined as a function over the utilities (the goodness values) of all the possible consequences. For that we rely on a choice criterion similar to the clas­ sical pessimistic/cautious Wald criterion, that suits well our illustrative application area. Of course in other do­ mains less strict criteria balancing between the risk and the expected outcome may be preferred.

Definition 4.1 The utility of a decision U (8) is the lowest utility of all its possible consequences, i.e. the low­ est goodness value of all the possible states in which the system might get after the decision 8 is taken.

The decision strategy amounts to choose the decision with highest utility, which is consistent with min-max game strategies [Pearl, 1984). We will now give our al­ gorithm and prove that it obeys the given criterion, but before that we need some additional definitions.

Definition 4.2 A selected transition r is said to be en­ sured iff the system cannot take another one.

On the contrary, r is said to be threatened by r' (the threat) if the system might take r' instead of r ( obvi­ ously r' can only be a received transition).

We use the same terms for the corresponding decision 8 of selecting the transition r .

4.2 The game-based decision procedure

Our procedure has been inspired by classical controller synthesis algorithms [Asarin et al., 1995), but highly sim­ plified in our case of "one step ahead" automata with goodness values. One needs first sorting the next transi­ tions starting from the one with highest goodness value, and then consider them one by one.

1. If the current best transition r is a received one, the decision is to wait for its labelling event to occur. We watch out if there is a worse received transition r' possibly threatening T by occurring meanwhile (test lower (g ( T' ) ) :::; upper (g ( T))). Ensuring T amounts to deciding to wait only while r' cannot occur: r can hence be ensured iff lower (g ( T)) < lower (g ( T')). If not, this selection is forgotten and one tries next item in RANKED (Goto 0). Otherwise the waiting delay is set to lower (g ( r')), and a new transition is added, labelled by the special event wait, that will be taken for sure just before the delay has elapsed (the guard therefore exactly equals delay-, which means the atomic dura­ tion immediately lower than delay). Then there are two possibilities; in the worst case, nothing happens, the transition wait is taken after delay- has elapsed, and a new automaton accounting for this elapsed time is re­ computed in the next stage of the global algorithm; or in the lucky case where the event labelling r occurs before the delay has elapsed, then r is taken.

The algorithm has been slightly simplified for the sake of clarity: it should take into account cases with several threats: the delay to wait is actually the min of the corresponding delays.

Last, when there is no threat r', the decision is just to wait for r to be taken, but actually no more than MaxDelay, which corresponds to the time after which a better activated transition that had been put aside may become releasable, which is explained herebelow.

1. In the case where r is an activated transition, things get simpler, but r still needs to be ensured. If the action can be released now (lower (g ( r)) = 0), then it is released (<T(r) is the action label of r). If not, the test about a possible threat is now on the value lower (g ( r)) instead of upper (g ( r)) ( r being an activated transition it can be released as soon as lower(g(r)) has elapsed). Here again, if r cannot be ensured, then this selection is put aside and the next one tried. But in the case where the decision ends up being wait, as soon as the action <T( r) becomes releasable, it will not be threat­ ened anymore (lower(g(r)) equalling 0), and it should be reconsidered as a possible decision. For that we use MaxDelay that keeps track of the min of the times after which an action becomes releasable, so as to restart the algorithm at that time.

PLAY-AUTOMAT(A):

RANKED := set of next transitions ordered from the highest to the lowest goodness value MaxDelay := +oo 0: r := pop(RANKED) If r E Tb then I if 3r'E RANKED s.t. r' E Tb I and lower(g(r')) :S upper(g(r)) then I I delay:= lower(g(r')) I I if delay leq lower(g( r)) then Go to 0 I I else I I I add a new state Qwait I I I add a new transition: I I I Twait =<qo,Qwait,Wait,{delay},0> I I I DECISION := (wait, delay-) I else DECISION := (wait, MaxDelay) Else I if lower(g(r)) = 0 then DECISION:= (a(r), NOW) I else if 3r'E RANKED s.t. r' E Tb I and lower(g(r')) :S lower(g(r)) ~ I I MaxDelay := min(MaxDelay, lower(g(r)) I I Goto 0 I else DECISION:= (a(r), lower(g(r))) send DECISION to the execution manager.

This algorithm is illustrated through the example of figure 3. In the first iteration, q4 is the best transition (maximal goodness value 0. 7), but it is threatened by the transition to q5 . Ensuring the selected transition amounts to wait no longer than 1. The new wait tran­ sition added to the automaton appears in figure 4. We show there a possible improvement of the algorithm (not developped here for the sake of clarity) where one not only adds this transition, but at the same stage computes the next states from qwait, which should be the same as in q0 , with recomputed guards according to the delay. The two activated transitions from q0 are in dashed lines because they will not be taken at this stage, trying to opportunistically let bmr occur first. Next, falling into Qwait> the choice bmr would be forgotten since it can no longer be ensured, and the next best transition aacc would be selected since it can be released at once. This improvement, which amounts to consider two successive decision steps in one stage, would end up with an ex­ pressive decision sounding like wait no longer than one second, then accelerate, which of course could be can­ celled by the early fortunate occurrence of bmr·

4.3 Decision making algorithm properties

Our algorithm is a least commitment strategy: one al­ ways prefers waiting if this may lead to a better situation and is not threatened by a worse one. It is as well an opportunistic process: actions that were put aside be­ cause they could not be ensured are considered again when they become releasable, and waiting instead of re­ leasing a "rather good" action may allow to receive a better event, such as in our example. Last , our algo­ rithm is definite in the sense that a decision will always be taken (provided the automaton is not empty): even a wait decision ensures the system evolution either when a received event occurs, or when MaxDelay has elapsed and an action can then be released.

About algorithmic complexity, it gets low first thanks to our associative models (see [Coradeschi et al., 1996] and [Dousson et al., 1993]), but also in the algorithm PLAY-AUTOMAT: the automaton is bounded in depth (one never computes a complete automaton but only needs to consider the next step thanks to the goodness values), and also in breadth (the number of alternative transitions to consider is lower than the maximum num­ ber of chronicles in a given context, i.e. in a leaf of the decision tree). In fact the global complexity only de­ pends upon the size of the decision tree and the maxi­ mum number of chronicles in each leaf, i.e. the size of the expertise knowledge base, which is constant and known.

The key point is to prove the optimality, i.e. that one always gets the best decision according to the given pol­ icy (of course the decision taken will only be the best according to the given goodness values, hence it highly depends on how accurate and realistic the associative model built off-line is). For that purpose, we check that in each case the decision with highest utility is taken.

1. If the transition T with highest goodness value 1 is an activated one (the decision 6 will be an action):
2. (a) if 6 is not threatened: the action will necessarily be released and 6 has the highest utility.
3. (b) if 6 is threatened by Tt leading to a state with goodness value 1t: then U(6)=1t·
4. if there exists 6' not threatened leading to a state with goodness value 1' s.t. 1 > 1'> 1t: the algorithm will take the decision 6' with U(6')= 1' > U(o).
5. if there exists 6' threatened: the reasoning process can be recursively applied as in 1. (b).
6. if no other satisfactory decision is found: the algorithm only waits until some action becomes releasable (thanks to MaxDelay), hence all the other possibly better decisions remain available at the next stage.
7. If the transition T with highest goodness value 1 is a received one (the decision 6 will be to wait):
8. (a) if 6 is not threatened: it is ensured hence the corresponding state will be reached, and 6 has the highest utility.
9. (b) if 6 is threatened by an event that may occur after a certain delay: the system will wait for this delay, in an opportunistic way, which might hopefully lead the system into the state reached by T (which means highest utility), or put it into the following situation (c).
10. (c) if 6 is threatened by an event that may oc­ cur immediately: 6 has the same utility as the threat, and hence is not better and might be forgotten , as the algorithm does.

5 Discussion and conclusion

A main strength of our approach is to use different mod­ els that are best suited for each of the requirements of highly reactive monitoring: a decision-tree for the con­ text, chronicles for the temporal evolutions, and a game automaton for the predictive decision making process. It is straightforward to integrate those models and make them work together in a smooth way.

Our approach can be compared to [Tambe and Rosen­ bloom, 1996], where opponent actions are considered while making dynamic decisions. There a single interpre­ tation of actions and observations is used. Our approach is more general since actions and observations may be of any kind, making it fit the more general area of oper­ ator/artefact reactive loop. In the TIGER gas turbine monitoring project [Milne et al. , 1994], three models are mixed in a similar way as ours: decision trees are re­ placed by compiled rule bases, and a classical chroni­ cle recognition mechanism feeds a model-based diagnosis system. But we do more than mere supervision, getting a highly reactive decision making system processing hypo­ thetical reasoning on the future instead of comparative reasoning on the past. This compelled us to improve the chronicle structure to incorporate actions in it. In a re­ lated game-based military application [Katz and Butler, 1994], decision is also dynamically made, but thanks to a discrete game model. Besides, classical heuristic tech­ niques are used, exploring down the tree in a lookahead simulation, which we avoid by directly inheriting good­ ness values from our associative model.

One shortcoming of our approach is the classical ex­ pertise acquisition problem: uncompleteness of such an expertise is always to be feared. Anyway, our architec­ ture can be made robust to unexpected events as well , thanks to some additional features that have not been presented here (see [Coradeschi and Vidal, 1998]).

As a matter of conclusion, our approach is relevant in highly reactive real-time monitoring applications with complex temporal constraints. It brings out expressive and accurate dynamic decision making. We strongly be­ lieve that mixing symbolic models from the artificial in­ telligence community and control models built by theo­ retical computer scientists, as we did, might help making substantial advances in that field.

Acknowledgments

Thierry Vidal has been supported by the Excellence Cen­ ter for Computer Science and Systems Engineering (EC­ SEL) in Linkoping. Silvia Coradeschi has been sup­ ported by the Wallenberg Foundation project Informa­ tion Technology for Autonomous Aircraft. The authors are also grateful to Dan Stromberg (Swedish National Defense research center, Linkoping) and Goran Petter­ son (SAAB Military Aircraft, Linkoping) for useful com­ ments and discussions that inpired the simplified appli­ cation example used in the paper.