Planning in Uncertain Temporal Domain

Planning in Uncertain Temporal Domain Nor Azlinayati Abdul Manaf 1, Mohammad Reza Beikzadeh 2 Multimedia University, 63100 Cyberjaya, Selangor, Malaysia {azlinayati.manaf, drbeik}@mmu.edu.my

ABSTRACT Planning is a fundamental aspect of human intelligence. Therefore it has become the fundamental problem in modelling intelligent behaviour within Artificial Intelligence. It is further complicated when the plan has to be done in uncertain temporal domain. This framework deals with linguistic fuzziness that often presents within temporal knowledge. An interval-based fuzzy membership representation is defined as an extension to the precise temporal interval. To deal with planning in this framework, a simple decision problem is shown. 1.

the proposed model followed by an application example in the following section. TABLE 1 13 POSSIBLE RELATIONS FOR ALLEN’S INTERVAL ALGEBRA Relations Symbol X before Y b x y Y after X bi X meets Y m x y Y met by X mi

INTRODUCTION

Planning is a necessary aspect in our everyday life. We plan for every action that we do everyday. Planning is a fundamental aspect of human intelligence. Therefore it has become a significant problem in modeling intelligent behaviour within Artificial Intelligence (AI). There is strongest interest in modeling planning system that can reason about realistic world [2]. However, many representation of temporal knowledge is weak in expressing uncertain temporal knowledge. The most influential work in representing and reasoning about temporal knowledge is the works by Allen [1]. He used time interval as the temporal notion in his work and defined thirteen possible simple relations between two intervals as shown in Table 1. These relations precisely characterize the relative starting and ending points of the intervals. In reality, there is only one of the thirteen possible mutual exclusive relations that may hold between two intervals. In this paper we proposed a framework that deals with linguistic fuzziness often presents within temporal knowledge and how it can be used to model planning system in real world. This model has been discussed in detail in [4] and the work described in this paper is an application example in planning domain of the proposed model. Next section briefly discussed the fundamental of

2.

X overlaps Y

o

Y overlapped by X

oi

X finishes Y

f

Y finished by X

fi

X during Y

d

Y during by X

di

X starts Y

s

Y started by X

si

X equals Y

eq

x

y x y x y x y x y

UNCERTAIN TEMPORAL KNOWLEDGE

As mentioned in the previous section, Allen’s intervalbased temporal logic is a powerful tool for reasoning about temporal knowledge especially in the application like scheduling and planning. However, this model only deals with precise time interval, whereas temporal information in practical is always pervaded with vagueness and uncertainty. In our model, we have introduced the element of uncertainty in the temporal information based on fuzzy linguistic expression. It can be represented using ‘fuzzy set’ [3] that are applied later to the temporal interval. Allen’s interval algebra will later be used to reason about the temporal problem. Each event is represented as an interval and the possible relations between each interval are defined.

2.1. The knowledge representation The representation of temporal intervals as fuzzy intervals plays very important role in reasoning about fuzzy temporal knowledge. However, temporal knowledge is often expressed in terms of linguistic fuzziness such as ‘a few seconds’ or in terms of temporal quantities with their modifiers such as ‘about 20 minutes’. This linguistic fuzziness can be represented using fuzzy set. Then, for each interval pervaded with the linguistic fuzziness, a series of fuzzified intervals that has been calculated with the fuzzy values was derived.

several fuzzy values at different point on x-axis of the original fuzzy membership function as shown in Fig. 1(b). It is very important when selecting these values, in order to at least maintain the shape of the original fuzzy membership function. The resulting fuzzy temporal membership function after selection process is shown in Fig. 1(c) and can be represented as a set of fuzzy values as follows: about_20minutes = { 0.2, 0.5, 0.9, 1.0, 0.9, 0.5, 0.2 }

Definition 2.1 (Fuzzy Temporal membership function) The fuzzy temporal membership function is defined as a set of fuzzy values selected from a fuzzy membership function with the values of the x-axis are omitted.

From the given example, it is known that Fred takes about 20 minutes to get to work. This means, the journey does not precisely take 20 minutes. The duration of the journey can be less or more than 20 minutes.

To show how we represent the fuzzy temporal membership function, let us consider the following statement.

Definition 2.2 (Conversion Functions) Two functions I −fv and I +fv used to convert the ideal case time interval to

“Fred takes about 20 minutes to get to work”

a set of intervals based on fuzzy values selected and is defined as

From the above statement, we can derive two important points which are:• Interval for Fred’s journey is 20 minutes. •

Fuzziness ‘about 20 minutes’ that might be represented as the following membership function as in Fig. 1(a). about 20 minutes

I −fv = I − ((1 − fv ) × X

)

(1)

I +fv = I + ((1 − fv ) × X

)

(2)

where I is the length of the ideal case time interval, fv is the selected fuzzy value and X is the factor that determine the distance from the peak value to the minimum or maximum value of the membership function (i.e. the relaxation of the membership function) on the x-axis. As we all know, for a normal fuzzy membership function, there must be only one maximum point or peak point in each function. Thus, we can easily separate the membership function into two parts, I −fv and I +fv where and I +fv represent the left side and right side of the function with respect to the peak point, respectively as shown in equations (1) and (2). I

20 minutes (a)

(b)

(c) Figure 1. (a) Fuzzy membership function, (b) Selected fuzzy values, and (c) Fuzzy temporal membership function

Consider the fuzzy membership function fuzziness ‘about 20 minutes’ in Fig. 1(a). In order to represent fuzzy temporal membership function, we first select

− fv

From the given example, assume the following values are used, I = 20 and X = 10 (i.e. the distance from the peak value to the minimum or maximum value of the membership function is 10). Applying the conversion function using the fuzzy values from the fuzzy temporal membership function define above results in the following set of fuzzified intervals shown in Fig. 2. Based on the set of intervals created, we can conclude that the conversion function is consistent since the intervals generated for the left side is less than the ideal time interval and the intervals generated for the right side is greater than the ideal time interval.

1.0

fv 0.9 0.5 0.2

the objects labeled 1 to 7 at their respective position within one hour. Assuming that all the objects to be arranged are located outside the room near the door, the lists of tasks that need to be performed by the robots are as follows:

20 min I

− fv

I

+ fv

19 min

21 min

15 min

25 min

12 min

T1: T2:

28 min

T3: L1: L2: L3: L4: L5: L6: L7:

Figure 2. Set of fuzzified intervals for Fred’s interval with fuzziness ‘about’

There is one assumption that can be defined from the fuzzified intervals in Fig. 2 which is for all fuzziness that is associated with a movement action, equations (1) and (2) might also represent ‘fast’ and ‘slow’ fuzziness, respectively. For example, if the person did the action fast, then, the interval will be shorter than the normal interval and vice versa.

5

0.9 0.5 0.2

19 minutes 15 minutes 12 minutes

1

7

6

4

DOOR R1

R2

Fig. 4 A room arrangement scene

slow 21 minutes 25 minutes 28 minutes

C1: T1 and T2 must start simultaneously, one each. C2: T3 has to be done after T1 by any robot. C3: L1 can be done after T3 finished by both robots. C4: L2 can be done after T1 finished by any robot. C5: L3 and L4 can be done by any robot after L1 finished. C6: L5, L6 and L7 can be done by any robot but must be done after L3 and L4 finished.

fvfast/slow 0.1 0.5 0.8

Figure 3. Corresponding “fast” and “slow” fuzzy values

3.

2

3

A few constraints that need to be followed in the arrangement tasks are:

20 minutes

fast

WINDOWS

In the given example, if Fred takes only 12 minutes to arrive to work, most probably, he drives faster or if Fred takes 28 minutes to arrive to work, there might be a possibility that he drives slower than his normal speed. To represent the fuzzy values for these fast and slow fuzzy concepts, we use the inverse value (1 – fv) of the fuzzy values defined in the original fuzziness i.e., for fvabout_20minutes = 0.9, the corresponding fuzzy values for fast and slow are fvfast = fvslow = (1 – 0.9) = 0.1. The corresponding fuzzy values for fast and slow membership function are shown in Fig.3.

fvabout_20minutes

Sweeping the floor takes about 20 minutes. Cleaning up the windows takes about 15 minutes. Clearing the dustbin takes about 5 minutes. Moving object 1 takes about 10 minutes. Moving object 2 takes about 10 minutes. Moving object 3 takes about 8 minutes. Moving object 4 takes about 8 minutes. Moving object 5 takes about 6 minutes. Moving object 6 takes about 6 minutes. Moving object 7 takes about 6 minutes.

AN APPLICATION EXAMPLE

In this section, we give an example of using the knowledge representation scheme for modeling and planning activities in a room arrangement scene as shown in Fig. 1. The room is initially empty. Two robots, R1 and R2, are assigned to clean up the room and locate all

Form the given knowledge, a few queries can be post to the system not limited to the following: i.

Is it possible to generate a plan using the ideal time for each interval to finish all the tasks within the specified time?

ii.

What is the shortest duration to complete all the tasks?

iii. Is it possible for robot 1 do to finish sweeping the floor before robot 2 finish clean up the window? If yes, what should robot 1 do? (assuming robot 1 do T1 and robot 2 do T2 and ideal case for robot 2). For the first query, there are 5 possible plans than can be generated and the optimum solution for the plan is shown in Fig. 5. T1

R1

T2

R2

L2

L1

L3

L5

T3

L1

L4

L6

L6

The main applications that can benefit from this model are the applications involving scheduling and planning with uncertainty. In the future, we might extent this concept to point based representations to overcome those problems from temporal rich domains. References

0

20

30

60

Fig. 5 The optimum solution for case 1

Time taken to complete all the tasks is 60 minutes. For the second query, the shortest time taken to complete all the tasks assign is 33 minutes. This can be achieved by having both robots to move at their maximum speed. The sequence of action for both robots is shown in Fig. 6. T1

R1

T2

R2 0

12

L2

L1

L3

L5

T3

L1

L4

L6

19

L6

33

Fig. 6 The shortest possible time for case 2

For the third query, according to the fuzzified intervals generated, there are two intervals, 12 minutes (fv=0.2) and 14 minutes (fv=0.4), where the duration of the intervals are less than 15 minutes (the duration for task T2). Thus, it is possible for robot 1 to finish sweeping before robot 2 finished cleaning up the windows. The action that robot 1 should take is to move faster by at least fv=0.6. 4.

and quantitatively. The unified representation of fuzzy and temporal information and the planning utility that the model offers enable reasoning in planning and scheduling process. It also offers the straight forward view of the relations among intervals through the graphical representation.

CONCLUSION

The proposed model based on Allen’s interval algebra and fuzziness is used to present fuzzy temporal knowledge and reasoning process. This model has been developed using WIN-Prolog 4300 on Windows 2000. The major advantage of this model is the simplicity of the model and the straight forward computation. Furthermore, it can be used to reason both qualitatively

[1] J. F. Allen, “Maintaining Knowledge about Temporal Intervals”, Communications of the ACM, vol. 26, no.11, 1983, pp. 832-843. [2] J. F. Allen, “Planning as Temporal Reasoning”, In Proc., 2nd Principles of Knowledge Representation and Reasoning, Morgan Kaufmann, 1991. [3] L. A. Zadeh, “Fuzzy Sets”, Information and Control, vol. 8, 1965, pp. 338-353. [4] N. A. Abdul-Manaf and M. R. Beikzadeh, “Representation and Reasoning of Fuzzy Temporal Knowledge”, IEEE Int. Conferences on Cybernetics & Intelligent Systems and Robotics, Automation & Mechanics (CIS-RAM 2006), Bangkok, Thailand, June 2006.