In this paper we propose an extension of the action language GOLOG that integrates linguistic terms in non-deterministic argument choices and the reward function for decision-theoretic planning. It is often cumbersome to specify the set of values to pick from in the non-deterministic-choice-of-argument statement. Also, specifying a reward function is not always easy, even for domain experts. Instead of providing a finite domain for values in the non-deterministic-choice-of-argument statement in GOLOG, we now allow for stating the argument domain by simply providing a formula over linguistic terms and fuzzy fluents. In GOLOG's forwardsearch DT planning algorithm, these formulas are evaluated in order to find the agent's optimal policy. We illustrate this in the Diner Domain where the agent needs to calculate the optimal serving order.
The action language GOLOG [Levesque et al., 1997] has
proven useful for encoding the high-level behaviors of a robot
or agent
One of the features that we found particularly useful to define the behavior of an agent or robot in a flexible way was to use decision-theoretic planning. The programmer states the different action alternatives and a reward function in order to select preferred world situations; the optimal policy is then calculated and executed. Besides this non-deterministic choice of actions, GOLOG offers a non-deterministic-choiceof-argument statement. For a finite domain of arguments, an optimal policy is computed. This is in particular helpful when the agent faces incomplete knowledge and particular information has to be sensed at run-time. However, to specify the argument domain is often cumbersome. In this paper, we propose an extension to GOLOG that integrates linguistic terms in non-deterministic argument choices and the reward function for decision-theoretic planning. We demonstrate the extension in the Diner Domain, where a waitron agent has to serve coffee and dishes as hot as possible. The agent has to decide on which order to deliver first as the coffee and meals cool down over time. We show how linguistic terms as defined in the Fuzzy Logic extension of GOLOG [Ferrein et al., 2008; Schiffer et al., 2011] are formally integrated into the forwardsearch value iteration algorithm used in READYLOG.
The remainder of the paper is organized as follows. In the next section, we briefly introduce the Diner Domain. Then, in Section 3, we review the background of this work, namely READYLOG and our Fuzzy Logic extensions to the Situation Calculus. In Section 4, we bring together the linguistic terms and decision-theoretic planning and define the respective language constructs formally. We conclude with Section 5. 2
The example we use in this paper will be from the Diner Domain. In the Diner Domain, a waitron agent has to decide which of its assigned tables it should serve first in order to serve coffee and meals as hot as possible. Of course, the longer the distance for coffee and meals to be served, the cooler the dishes will be when served to the customer. In our example, the waitron was assigned to serve tables T1 and T9. The coffee is regarded as cold if its temperature lies between 0–50 centigrades, it is perceived as luke warm between 45 and 65 degrees, hot between 60 and 80 degrees; above 75 degrees we regard the coffee as veryhot. Despite a negative exponential cooling rate in reality, we assume a linear rate for the sake of simplicity in this example. For every 10 seconds we assume that coffee and meals cool down 1 degree. Traversing a square in the Diner Domain takes the waitron T3 T2 T1
T6 T5 T4 →
T9 T8
T7 ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ Counter
A
→ agent 5 seconds. Fig. 1 shows an example. The agent (A) needs 12 actions (r, r, u, u, u, u, u, u, u, u, u, r) to get to table T9. It takes the agent 60 seconds to reach that table. That means that a hot coffee at 65 centigrades will be lukewarm when served at table T9. The deliverCo ee action finally delivers the coffee to the customer, once the right table has been reached by the agent. 3
In this section we briefly introduce the Situation Calculus and READYLOG, showing the forward-search value iteration algorithm in greater detail. Then, we outline how Fuzzy sets can be formalized in the Situation Calculus. 3.1
The Situation Calculus is a second order language with equality which allows for reasoning about actions and their effects. The world evolves from an initial situation due to primitive actions. Possible world histories are represented by sequences of actions. The Situation Calculus distinguishes three different sorts: actions, situations, and domain objects. A special binary function symbol do : action situation ! situation exists, with do(a; s) denoting the situation which arises after performing action a in the situation s. The constant S0 denotes the initial situation, i.e. the situation where no actions have occurred yet. The state the world is in is characterized by functions and relations with a situation as their last argument. They are called functional and relational fluents, respectively. Actions in the Situation Calculus are characterized by unique names. For each action one has to specify a precondition axiom stating under which conditions it is possible to perform the respective action and an effect axiom formulating how the action changes the world in terms of the specified fluents. Finally, we need a so-called basic action theory, which consists of the successor state (a special form nil '? waitFor( ) [ 1; 2] if ' then 1 else 2 endif while ' do endwhile withCtrl ' do endwithCtrl
1 jj 2 withPol( 1; 2) prob(p; 1; 2) pproj(c; ) fproc P1(#~1) 1 endproc; solve(h; f; )
1 j 2 pickBest(h; ~x; ) conditional
loop guarded execution prioritized execution prioritized exec. of 2 probabilistic exec. of 1; 2
prob. projection of prog’s g procedures
initiate decision-theoretic optimization over up to a fixed
horizon h non-deterministic decision-theoretic
choice of prog’s non-deterministic decision-theoretic choice of arg’s empty program primitive action wait/test action event-interrupt sequence of effect axioms) and precondition axioms and states what is true in the initial situation. Some foundational axioms are also required. For details we refer to [Reiter, 2001].
READYLOG [Ferrein and Lakemeyer, 2008; Ferrein, 2010], our variant of GOLOG [Levesque et al., 1997], borrows ideas from [Levesque et al., 1997; De Giacomo et al., 2000; Grosskreutz, 2000; Grosskreutz and Lakemeyer, 2001; Boutilier et al., 2000] and features the constructs given in Fig. 2. Besides standard constructs, READYLOG also features non-standard constructs such as pproj, where a program is probabilistically projected into the future, or the nondeterministic decision-theoretic choices of programs or arguments (“j” and pickBest, respectively). These constructs are used inside a solve statement and leave choices open that are filled by the decision-theoretic forward search algorithm deployed in READYLOG which we will explain next. The other constructs of READYLOG are shown in Fig. 2.
As we are aiming at extending decision-theoretic planning (DTP) in GOLOG in this paper, we have a closer look at the forward-search DTP algorithm that was proposed by [Boutilier et al., 2000]. The search tree is expanded in a forward direction induced by the basic action theory. Fig. 3 shows the principle. The nodes in the search tree are expanded and the values are propagated back to the root. The path with the highest value represents the optimal policy. As the tree is constructed based on the basic action theory, it is particularly easy to restrict the search. Consider our waitron agent from the Diner Domain. To compute a path from the counter to table T9, it could simply use the program shown in Algorithm 1, assuming the robot has the following action set A = fgo right , go left , go up, go downg. Each of these actions takes the robot to the intended direction with a high probability, with a low probability it will end up in an adjacent location. The goal state, table T9, has a positive reward while each other field has a negative reward. READYLOG now computes the optimal policy (shortest path) from the Counter to T9 employing forward-search DTP. The forward-search DTP algorithm is implemented in terms of a number of BestDo predicates. For non-deterministic choices of actions, its formal definition following [Boutilier et al., 2000] is: BestDo((p1 j p2); p; s; h; ; v; pr ) d=ef 9 1; v1; pr 1:BestDo(p1; p; s; h; 1; v1; pr 1) ^ 9 2; v2; pr 2:BestDo(p2; p; s; h; 2; v2; pr 2) ^ ((v1; p1) (v2; p2) ^
= 1 ^ pr = pr 1 ^ v = v1) _ (v1; p1) < (v2; p2) ^
= 2 ^ pr = pr 2 ^ v = v2) The non-deterministic choice of action arguments is defined as:
BestDo(pickBest(x; ; p; p0); s; h; ; v; pr ) d=ef
j pjcxn ); p0; s; h; ; v; pr ) (1) Free variables x in the program p are bound to a finite domain ; for each “variable assignment” (denoted by pjcxi ) a new non-deterministic branch in the forward-search DTP is added. The policy is hence optimized for all possible variable assignments leading to the assignment which maximizes the reward function. 3.2
In [Ferrein et al., 2008; Schiffer et al., 2011] we introduced the notion of fuzzy fluents in GOLOG. Fuzzy fluents extend “ordinary” functional fluents in that they have a membership relation that defines, for a number of linguistic fuzzy terms the degree of membership for a particular function value.
In our Diner Domain, we want to serve hot coffee to our customers. The coffee, however, cools down quickly, depending on how long it takes to deliver the coffee. This, in turn, depends on the distance between the counter and the table where the coffee should be served. As an example for a fuzzy set defining the linguistic terms, we look at a distance relation. Distance in our diner example is understood as the Manhattan distance between two positions in the diner. We define distances between 0 and 3 blocks as close, between 3 1 proc navigate 2 solve(h; reward ; while loc 6= goal do 3 (go right j go left j go up j go down) 4 endwhile) 5 endproc
1: Decision-theoretic path planning in and 6 as medium, and above 6 as far. Formally,
F(distance; u; u) (distance = close
(0; 1:0) _ (1; 1:0) _ (2; 0:75) _ (3; 0:25) _ (13=12; 0:5)) ^ (distance = medium
(3; 0:25) _ (4; 0:75) _ (5; 0:75) _ (6; 0:25) _ (9=2; 0:5)) ^ (distance = far
(6; 0:25) _ (7; 0:75) _ (8; 1:0) _ (9; 1:0) _ (95=12; 0:5)); where we use (ui; ui ) as an abbreviation for u = ui ^ u = ui . The fuzzy set for the coffee temperature is shown in Fig. 4. Note that fuzzy categories can overlap. For instance, the coffee temperature 62 C belongs to the category luke as well as to the category hot. To query whether a value belongs to a certain category, one has to check if in the respective fuzzy set the value has a positive membership degree in that particular categorize. This is done with the predicate is real linguistic. It is defined as
is(f(~t; ); ) d=ef 9u; u:f(~t; ) = u ^ F( ; u; u) ^ u > 0; where f having the numeric value u is the fuzzy fluent to be queried, F is the respective fuzzy set and u is the degree of membership of value u in the fuzzy set F. In our distance example above, for instance, we have F(medium; 5; 0:75) to say that the numerical value 5 has a membership degree of 0.75 for the category medium. The predicate holds if the degree of membership is greater zero. For complex queries (logical formulas with fuzzy fluents), we have to define similar predicates is{ for the complement, is? for the conjunction, and is for the disjunction of fuzzy fluents. See [Ferrein et al., 2008; Schiffer et al., 2011] for the formal definitions. Further, we need to define a function to defuzzify a linguistic term to a numeric value. As a defuzzifying function, we use the center of gravity (cog) which we formally define in [Ferrein et al., 2008; Schiffer et al., 2011]. In our distance example, the center of gravity for the category close is 13=12. Note that we have to manually add the center of gravity for this respective category in our Situation Calculus fuzzy set formalization.
In the Diner Domain, we want to refer to positions in a room in a qualitative manner. This is why we introduce linguistic categories for the position in X and Y by the following membership functions:
F(posX; u; u) (posX = left (posX = center (posX = right (1; 1:0) _ (2; 1:0) _ (3; 1:0) ^
(4; 1:0) _ (5; 1:0) _ (6; 1:0) ^ (7; 1:0) _ (8; 1:0) _ (9; 1:0)): For the y-coordinate we introduce a fuzzy fluent posY and define the categories front, middle, back, referring to the tables whose ordinate have a distance of close, medium, and far from the Counter. In the next section, we propose an extension to DTP integrating those linguistic notions. One of the convenient features when specifying intelligent agents in GOLOG is that the agent designer can leave choices open that the agent then resolves on its own using an optimization theory. As already mentioned, the choices are the non-deterministic choice of action and the non-deterministic choice of argument. The latter is realized by means of the pickBest statement. It allows for specifying a set of possible values for a specific fluent for the program in the body of the statement. That program is evaluated with any of the values from the set. 4.1
We now propose to use, instead of a finite set of values, a fuzzy expression to specify the set of possible values for a fuzzy fluent. We introduce a new predicate pickBestF which takes a fuzzy expression instead of the regular set of the classical pickBest.
The idea is that instead of giving a finite set of variable or fluent values in the pickBest statement, the programmer now can state a formula specifying linguistic categories for a fuzzy fluent. For instance, if we want to optimize the coffee serving temperature, we could simply state to choose a coffee whose temperature is hot. What the pickBestF statement does is to translate this into a set of temperatures with positive membership values for the category hot. In our case shown in Fig. 4, this would be translated into the temperatures 60–80 centigrades. For each of the temperatures, the forward-search algorithm would try and optimize the respective program attached, say, serveCo ee(T9) (serve a coffee at table 9) with the pickBestF statement.
For a single linguistic category we define pickBestF as BestDo(pickBestF(f : ; p); p0; s; h; ; v; pr ) d=ef 9u1; : : : ; uk:
[f[s] = u ^ is(f[s] = u; )] ^ _ u2fu1;:::;ukg :9uj:(f[s] = uj ^ is(f[s]; ) ^
uj 6= u1 ^ : : : ^ uj 6= uk ^
j pjfuk ); p0; s; h; ; v; pr ) The intuitive meaning of the above definition is to collect all possible numerical values of a linguistic category as follows: First, we assume that the is predicate holds for k numerical values ui of the category . Then, we “check” if these k values are all values for which is( ; ) holds. Lastly, we call BestDo, replacing the fluent f in the program p with any such value (denoted by pjfui ).1 This is analogous to the definition of BestDo for pickBest (Eq. 1), where the fluent was replaced with any element of the set (cf. Section 3.1). We give the remaining definitions for the complement of a linguistic category and for conjunction and disjunction of several linguistic categories below.
If the expression is the complement of a linguistic category we have
BestDo(pickBestF(f : : ; p); p0; s; h; ; v; pr ) d=ef 9u1; : : : ; uk:
[f[s] = u ^ is{(f[s] = u; )] ^ _ u2fu1;:::;ukg :9uj:(f[s] = uj ^ is{(f[s]; ) ^
uj 6= u1 ^ : : : ^ uj 6= uk) ^
j pjfuk ); p0; s; h; ; v; pr ) For a conjunction of n linguistic categories we have BestDo(pickBestF(f : ?; p); p0; s; h; ; v; pr ) d=ef 9u1; : : : ; uk:
[f[s] = u ^ is?(f[s] = u; ?)] ^ _ u2fu1;:::;ukg :9uj:(f[s] = uj) ^ is?(f[s]; ?) ^
uj 6= u1 ^ : : : ^ uj 6= uk ^
j pjfuk ); p0; s; h; ; v; pr ) where ? is an abbreviation for ? d=ef 1 ^ disjunction of n linguistic categories we have BestDo(pickBestF(f : ; p); p0; s; h; ; v; pr ) d=ef
^ n. For the _ u2fu1;:::;ukg 9u1; : : : ; uk: [f[s] = u ^ is (f[s] = u; )] ^ :9uj:(f[s] = uj ^ is (f[s];
) ^ uj 6= u1 ^ : : : ^ uj 6= uk) ^ BestDo(pjfu1 j
j pjfuk ); p0; s; h; ; v; pr ) is an abbreviation for d=ef 1 _ _ n. By the above definitions we provide our new pickBestF allowing to specify the argument choice in terms of a fuzzy expressions for a single fuzzy fluent based on the existing BestDo statements for standard sets. The idea is to branch over all fluent values for which the fuzzy expression holds in the resulting non-deterministic choice of action statement having all occurrences of f replaced by the respective value from the respective fuzzy set. 4.2
As a second way to increase the naturalness of specifying programs for decision-theoretic planning we introduce a means 1Note that for readability we only use f to refer to a fuzzy fluent. f[s] denotes the fluent f with its situation argument being restored which we need to determine its value in a particular situation. to use fuzzy expression in the reward function. We propose a statement fcase that modifies the reward according to a fuzzy expression, i.e., a single fuzzy category, the complement of a single fuzzy category, the conjunction of several fuzzy categories and the disjunction of multiple categories (all for the same fuzzy fluent f).
The fcase statement distinguishes the four above cases and handles them according to the following definitions. For a single linguistic category For the complement of a single linguistic category def fcase(f; ; r) = reward = is(f[s]; ) ^ (reward = r) _ :is(f[s]; ) ^ (reward = 0)
def fcase(f; : ; r) = reward = is{(f[s]; ) ^ (reward = r) _ :is{(f[s]; ) ^ (reward = 0) For the conjunction of n linguistic categories For the disjunction of n linguistic categories def fcase(f; 1 ^ : : : n; r) = reward = is?(f[s]; 1; : : : ; n) ^ (reward = r) _ :is?(f[s]; 1; : : : ; n) ^ (reward = 0) def fcase(f; 1 _ : : : n; r) = reward = is (f[s]; 1; : : : ; n) ^ (reward = r) _ :is (f[s]; 1; : : : ; n) ^ (reward = 0) 4.3
To illustrate the extensions proposed above, consider the following example in our Diner Domain: The restaurant has several waitron robots and we need to specify the control program for one of them. Assume the robot is responsible for the tables located in the corners of the room. Let the position of the tables be composed of their x and y cell-coordinates. In terms of a linguistic description, we might then say that the robot needs to serve tables that are in the left or the right part of the room and that are in the front or the back part of the room. The robot can take orders for coffee or meals from any of the tables it needs to serve. Assume the robot has a (finite) list of orders in its world model, each with a number, the table it came from and the temperature the meal was served with. The individual properties of those orders can be retrieved via respective functions, where orderi is used to refer to the order number i. The serving temperature is zero for as long as an order has not been served.
Writing a program for such an agent includes letting the robot choose which table to serve in which order. Using decision-theoretic planning, we can specify an optimization theory by means of a reward function. With our newly introduced pickBestF statement we can write a control program in a very straight-forward manner as given in Alg. 2.
Let us assume that the reward is computed by giving a negative amount for any open order (i.e. any order that has not Algorithm 2: Decision-theoretic planning in READYLOG for serving a room with fuzzy argument choice 1 proc serve room 2 navigate(counter); 3 while haveOpenOrder(room) do 4 pickBestF(posX, left _ right ) f 5 pickBestF(posY, front _ back ) f 6 tableWithOpenOrder(table; posX; posY); pickBestF(mealTemp, luke _ hot ) f
mealWithTempReady(meal; mealTemp); 9 load meal(meal,tray); 10 bring meal(tray,table); 11 serve meal(tray,table); g g g 12 navigate(counter); 13 endwhile 14 endproc been served yet) and by giving a positive amount for food being served with a high temperature. We can use the newly introduced fcase statement to specify such a reward function with linguistic terms as follows. For simplicity, we limit ourselves to a list of only two orders.
def reward (s) = r = r = numOpenOrders(s) ( 100) + fcase(serveT emp(order1; s); hot; 100) + fcase(serveT emp(order2; s); hot; 100) + fcase(serveT emp(order1; s); luke; 10) + fcase(serveT emp(order2; s); luke; 10) The fuzzy fluent serveTemp returns the temperature at which a meal was served.
Let us assume, the robot has orders from tables T9 and T1. For simplicity we assume there is no coffee and only one meal to order hence both tables may be served with the same meal. The robot finds two meals M1 and M2 ready to serve on the counter with temperatures of 54 and 74 centigrades respectively. If the robot uses the above program it yields an execution trace as follows.
The first pickBestF statement has a disjunction as its fuzzy expression. Hence, we apply the corresponding BestDo definition. That is, by means of the existential quantifiers we collect those ui (and only those!) for which the predicate is (ui; left; right) is true. Using the F definition for the posX fuzzy fluent we find six values, namely 1; 2; 3; 7; 8; 9. Similarly for the second pickBestFstatement we collect possible y-coordinates 1; 2; 3; 7; 8; 9. Using the BestDo definition, we replace in the body of the pickBestF statement the variables posX and posY by any of the available values. For each combination we check whether there is a table with an open order at that position with the predicate tableWithOpenOrder. The only positions for which this is true are T1 and T9. For those two tables we continue with the program, i.e. we do another pickBestF, now for the fluent mealTemp. Again, using the BestDo definition for a disjunctive fuzzy expression (hot _ luke) we collect a set of values to replace the fluent mealTemp in the remaining program. In our example this is the set f45; : : : ; 80g as per our specification of the fuzzy sets F for luke and hot (cf. Sect. 2). Hence, we consider to execute the sequence inside the innermost pickBestF for any combination of existing table positions with open orders in the areas that our robot has to serve, each with any of the meals available with temperatures from the set f45; : : : ; 80g that we have from our BestDo definition. First we check whether a meal with a given temperature is ready on the counter by the predicate mealWithTempReady. Only if this is the case, we attempt to load the meal, bring it to a table and serve it. Starting from the initial situation as given above, from the sets constructed by our BestDo definitions for pickBestF by means of the two predicates tableWithOpenOrder and mealWithTempReady what remains for the innermost program part are for the position (8; 8) and (2; 2), each in combination with a meal of either 54 or 74 centigrades temperature.
Starting at the counter, we need 12 steps to reach table T9 and 6 steps to reach table T1. This means, a meal cools down by 12 5=10 = 6 centigrades when it is being delivered to T9 and 6 5=10 = 3 when it is being delivered to T1. With the two orders to serve and two meals to pick from for each we are left with four courses of action, shown with their reward in Tab. 1. The reward for the course of actions essentially depends on the temperature that each meal is being served at. For meals being served with luke temperature the agent receives a reward of 10, for those being served hot it is rewarded with 100. The most rewarding situation is reached with first serving table T1 with meal M1, and then delivering M2 to T9. This yields a total reward of 120. The policy returned for the agent to execute then is navigate(counter), tableWithOpenOrder(T9, 8, 8), mealWithTempReady(M1, 74), load meal(M1, tray), bring meal(tray, T9), serve meal(tray, T9), navigate(counter), tableWithOpenOrder(T1, 2, 2), mealWithTempReady(M2, 54), load meal(M2, tray), bring meal(tray, T1), serve meal(tray, T1), navigate(counter).
Our newly introduced constructs allow for a seamless integration of linguistic notions in decision-theoretic planning in agent programs. The agent designer can use fuzzy expressions both, to specify the set of values to pick from for the non-deterministic choice of argument and to specify portions of the reward function that is used as the underlying optimization theory in decision-theoretic planning.
In this paper we proposed an extension to READYLOG which combines fuzzy fluents and decision-theoretic planning. Fuzzy fluents are fluents that have a membership function attached. With this function, it can be checked whether or not a fluent value belongs to the linguistic category in question. In our previous work, we defined a predicate “is” to test this. With this predicate, we can handle negation, conjunction and, disjunction, respectively, of linguistic terms. The decision-theoretic extension of GOLOG implements a forward-search value iteration algorithm and allows to optimize non-deterministic choices of action or arguments w.r.t. a given reward function. The search for an optimal policy can be guided by a GOLOG program to restrict the search space. Our practical experiences with programming robots with READYLOG shows that, in particular, non-deterministic choices of actions and arguments are very useful when specifying the behavior of a robot or agent in a flexible way. For the non-deterministic choice of arguments, the programmer has to give a finite domain from which the program arguments for computing the optimal policy are evaluated. This can be a cumbersome process.
In this work, we extend the non-deterministic argument choice such that it can handle simple fuzzy fluent formulas. This facilitates the specification of the argument set in pickBest statements. To this end, we introduced and defined a statement pickBestF that translates the values for which the given fuzzy fluent formula holds as an argument set for the ordinary pickBest statement. Further, we introduced a statement fcase which allows to use simple fuzzy fluent formulas in the reward function of the forward-search value iteration algorithm. The programmer can make use of linguistic terms and fuzzy categories when assigning rewards to preferred world situations. We showed the use of the new constructs by an example from the Diner Domain, where a waitron agent has to find an optimal schedule to serve coffee or dishes to its customers.
Our further steps are as follows. So far, we did not allow arbitrary formulas over fuzzy fluents yet. Enabling such formulas is not as easy because, for example, in fuzzy logic the excluded middle does not always hold. We will look into possible realizations of more complex formulas. Furthermore, broadening the application of linguistic terms in planning to planning with preferences is on our agenda. Here we want to investigate how our work can be married with the work of [Fritz and McIlraith, 2006; Bienvenu et al., 2011] who compile modal logic preference formulas into GOLOG programs Similarly, we will have a look into [Finzi and Pirri, 2004; Cesta et al., 2011] who use temporal interval planning to solve scheduling problems.