Extending DTGOLOG with Options

1 Introduction

Recently Boutilier eta!. (2000) proposed the language DT­ �o~O� which combines explicit agent programming with decision theory. The motivation is that a user often has some idea about how to go about solving a particular problem yet at the same time does not want to or cannot commit in advance to an exact course of action. Instead, certain choices are left to the agent running the program and determining an optimal action selection policy involves solving a Markov Decision Process (MDP) [Puterman, 1994]. In a sense, a DTGOLOG program can be thought of as a factored representation of an MDP. ~san example, Boutilier eta!. consider a mail-delivery scen_ano where the task of delivering mail to a particular per­ son IS hand-coded and fixed, while the agent chooses the or­ der in which the various people are served according to some reward function. They note that this approach allows solving problems which are much larger than those solvable using the traditional dynamic-programming approach for MDPs.

Nevertheless, it is not very difficult to find examples where DTGOLOG also shows poor computational behavior. Roughly, the complexity is determined by the number of ~hoices the agent needs to consider when computing a pol­ Icy and the number of actions with uncertain outcomes (na­ ture's choices) that need to be considered along the way. To better control this potential blow-up we were inspired by work on so-called macro actions or options previously de­ veloped in the MDP framework [Hauskrecht et a!., 1998; Sutton et al., 1999]. The idea is that the policies forcer­ tain subtasks like leaving a room are pre-computed and then simply used when working on the global policy.

. Th.is is, roughly, what we propose: for a given domain Identify subtasks and compute local policies using standard MDP techniques like value iteration. From those local policies generate two representations: ( 1) a (deterministic) DTGOLOG program directly encoding the local policy in te?Jls of what action to take while the local policy is ap­ plicable and (2) so-called abstract stochastic actions which only address the expected outcome of a local policy. It turns out that, while both representations can be used to compute a glob~! policy, the ~se of abstract stochastic actions may result m an exponential speed-up.- In the next section we

·This work was partly supported by the German Science Foun­ dation (DFG), Grant No. LA 747/9-1, and a grant by the NRW Min­ istry of Education and Research (MSWF).

Extending DTGOLOG with Options*

A. Ferrein, Ch. Fritz, and G. Lakemeyer Department of Computer Science RWTHAachen

{ ferrein, fritz, gerhard}@cs.rwth-aachen.de

briefly introduce MDPs and DTGOLOG. Section 3 describes options in more detail and how to map them into DTGOLOG. We end with a discussion of experimental results.

2 Decision Theory and GOLOG

A fully observable MDP is represented as a tuple M = (S, A, Pr, R), where S is a finite set of states, A is a finite set of actions, Pr is a probability distribution Pr : S x A x S -t [0, 1] (~r(sJIA, si) denotes the probability of the agent end­ mg up m state Sj after performing action A in state si, and ??- : S -t lR. is a bounded reward function . The objective IS then to construct a policy 1r : S -t A that maximizes the expected total reward over some horizon. A simple algorithm for constructing optimal policies is value iteration ( cf. [Put­ erman, 1994]).

DTGOLOG [Boutilier et a!., 2000] can be thought of, roughly, as a programming language which allows a user to combi?e pre-defined primitive actions into complex pro­ gra~s usmg the usual constructs like sequence, if-then-else, wh1le, and recursive procedures. In addition there are nonde­ terministic actions to model that an agent can choose among alternatives. The semantics is based on the situation calcu­ lus and, in particular, the so-called basic action theories de­ s.cribed in [Reiter, 2001], which define when primitive ac­ twns ~re exe~utable and how they change and do not change ~hat IS true m the world. As a special form of primitive ac­ twn DTGOLOG allows so-called stochastic actions, which ha~e pro~abilistic outcomes, just as in MDPs. For example, 1t 1~ possible to define an action r (move to the right) , after :-vhich a robot has moved one step to the right with probabil­ Ity 0.9, but has moved to the left, up, or down with probability 0.1. M~P-style reward and cost functions are incorporated as well. G1ven a DTGOLOG program, the idea is then to com­ pute a policy in the sense that each nondeterministic choice !s resolve~ in a ?ecision theoretic manner, that is, by choos­ mg the actwn with maximal expected reward. Assuming that there are not too many nondeterministic or stochastic actions a poli~y can be c?mpu~ed even in cases where an MDP repre~ sentatwn seems mfeasible due to the size of the state space.

3 Mapping Options into DTGOLOG

As in [Sutton et a!., 1999], we define options as triples (J, 1r, /3), where I is the set of initial states, 1r is a policy, and ~ is the set of terminating states. To illustrate options con­ sider the example in Figure I from [Hauskrecht eta!., 1998].

The task is to find an optimal policy to get from position S to position G. Performing an action has cost I, the goal po­ sition has a high positive reward. The agent can perform the stochastic basic or primitive actions r, l, u, d succeeding with probability 0.9. With probability 0.1 it will be in any other ad­ jacent position. For each room options are defined to leave the room through a certain door (one for each room/door combi­ nation). The gray dots correspond to the termination positions of these options. For the left lower room in Figure I there are two options 0 E and 0 N (leave through the east or north door, respectively) with Ie = {(x , y) I 0 < x :S 3, 0 < y :S 3} and /3 E = { (2, 4), ( 4, 2)}, and similarly for 0 N. (In order to mark state (4,2) in f3e as success and (2,4) as failure, they are assigned positive and negative reward, respectively.)

Applying standard value iteration techniques, the follow­ ing can be computed for an option 0:

I . the optimal policy 1r, that is, the most appropriate action Ai for each Si E I;

2. for each Si E I and Sj E /3, the probability to terminate the option with the outcome Sj when starting in si.

These results can now be translated into a form suitable for DTGOLOG. Given I = { s1 , ... , sn}, suppose that each si can be uniquely characterized by a logical formula <iJi· (In our example, <iJi simply expresses the coordinates of the location of si-) Then the policy 1r can be translated in a straightfor­ ward fashion into the following DTGOLOG program:

senseState( 0); while ( rp 1 ) if 'Pl then A1 else if .. . else if 'Pn then An; senseState( 0); end while

where <p 1 = V <pi and senseState( 0) is a so-called sens­ ing action. Roughly, executing senseState( 0) establishes the truth values of the <pi so that they can be tested in the following while and if conditions. (The sensing actions are necessary to account for the MDP assumption of full observ­ ability.) All in all, the program simply prescribes that the optimal action (according to 1r) should be executed as long as the agent is in one of the initial states of 0.

Given (2.) above we can also generate for each Si E I an abstract stochastic action o(si)· For example, for the option 0 E and state s1 = (2, 2) we would define an ab­ stract stochastic action oe(si) with nature's choices o;(s1) and o~ ( si) for leaving through the east or north door, respec­ tively, together with the probabilities ofthese actually occur­ ring as computed in (2.) (Prob(o; (s1 ) I oe(si)) = 0.99898, Prob(o~(s!) I oe(si)) = 0.00102).

Just as options in the MDP framework can be treated like primitive actions in MDPs that use these options, the transla­ tion into abstract stochastic actions in the DTGOLOG frame­ work has the same effect, that is, we can now write DT­ GOLOG programs treating abstract stochastic actions just like any other primitive actions. A global policy computed by DT­ GOLOG for such a program usually mentions abstract actions. These are not readily executable (leaving a room through the east door is not a primitive action). Hence, in a final step we need to replace the abstract actions by the programs which we derived above .

4 Experimental results

Using our running example we conducted a number of exper­ iments, the goal being at different distances from the initial position (Fig.! shows the special case of distance 8). The re­ sults are given in Figure 2. The x-axis depicts the initial dis­ tance to the goal, the y-axis the running time. We compared three different approaches: (A) calculating the optimal policy in DTGOLOG nondeterministically choosing only from the primitive actions, (B) using a set of procedures like the one in the previous section for leaving each room towards a certain neighboring room, choosing from primitive actions only in the goal room, and (C) using options in the form of abstract stochastic actions, choosing from primitive actions only in the goal room.

Note that they-axis of the diagram has a logarithmic scale. The speed-up from (A) to (B) shows the benefit using DT­ GOLOG to constrain the search space by providing fixed pro­ grams for certain subtasks. Interestingly, (C), that is, using abstract actions, clearly outperforms (B). Roughly, this is be­ cause each abstract action has only two outcomes, whereas the corresponding program provides a very fine-grained view with a huge number of outcomes that need to be considered.

Taking the time of calculation of all options into account (here: 10.51 seconds) the use of options pays off at horizons greater than 5. Also, calculating options can be done off-line and can be neglected in case of frequent reuse.

We remark that while method (A) guarantees optimality, this is not necessarily so for (B) and (C), for essentially the same reasons as in [Hauskrecht eta/., 1998]. Certainly in the case of (C), this price seems worth the computational gain. Finally, while we currently assume options as given, Hauskrecht et a!. ( 1998) discuss ways of automatically generating options with good solution qualities, an issue we mtend to mvestigate in the future as well.