Home

31295019600575

1. obs P 0 0 3 14 for defining the initial values of processes A fluent remains constant throughout the duration of a step This is expressed by the axiom 3 15 val Y P T I val Y P 0 J 3 15 process P fluent in T I Axiom 3 16 says that no process can have more than one value at the same time val Y1 P T I val Y2 P T J 3 16 neq Y1 2 27 3 4 EXAMPLE TRANSLATIONS Now let us refer back to Examples 2 1 and 2 2 and sec how the corresponding causal laws will be translated In Example 2 1 the dynamic causal law drop causes holding is translated as val false holding 0 I 1 o drop T I catch causes holding is translated as val true holding 0 I 1 o catch T I Next we look at the executability conditions impossible drop if holding is translated as o drop T I val false holding T I impossible drop if height end 0 is translated as 28 o drop T I val 0 height T 1 impossible catch if holding is translated as o catch T I val true holding T I Next we look at state constraints height fo T if height 0 Y holding is translated as function f0 val f0 Y T height T I val Y height 0 I val true holding T 1 in T I range height Y The function fO is a user defined function that is linked to Iparse Such functions 29 are meant to be
2. drop causes holding 1 3 which says that performing the action drop at time end in a state s causes holding to be false in the successor state of s This explains the change in the value of holding from so to s The executabilty conditions will have the form impossible drop if holding 1 4 which says that the ball cannot be dropped at time end in a state s if holding the ball is false Therefore the action drop cannot be performed in the state s1 impossible drop if height end 0 1 5 says that the ball cannot be dropped at time end in a state s if it is on the ground at end height end is a special fluent corresponding to the continuous process height that denotes the height at the end of a state The effects of the action catch are given by the causal law catch causes holding 1 6 1 6 explains why there is a change in the value of holding from s to s2 The executablity conditions will have the form impossible catch if holding 1 7 1 7 explains why the action catch cannot be performed in the states sy and ss height is defined by the following statements height fo Y T if height 0 Y 1 8 holding From Figure 1 3 it is obvious that the value of height is determined depending on whether holding is true or not Statement 1 8 requires that in any state in which holding is true height does not change with time hcight 0 is a special fluent corresponding to continuous process height t
3. Range of processes 86 range open true range open false range inflow_rate 0 range inflow_rate 3 values 0 60 Suppose that the maximum volume of the tank whose length is 4 m breadth is 3 m and height is 5 m is 60 cubic meter range volume Y values Y The maximum value of outflow rate is 10 range outflow_rate Y values Y lt 10 Domain independent axioms A process cannot have two values at the same time val Y 2 PN T D vallY1 PN T 1 neg Y2 Y1 process P N PT range PN Y1 range PN Y 2 Axioms for defining end of a state 87 end T D o ANT D action ANAT If no action occurs during a step then the step will end at the last possible time unit end m I 1 No state can have more than one end end T1 J end T2 1 neq T1 T2 Every state must end ends I end T D not ends I Axioms that define in and out out T I end T1 To T1 in T 1 not out T I The value of fluent does not change with time 88 val Y PN T D val PN 0 1 in T J process PN fluent range PN Y Inertia axiom Things normally stay as they are val PN O0 I 1 vall PN T I end T I not val PN 0 1 1 process PN PT range PN Y Reality Check obs Val Process T I s obs Y PN T I not val PN T 1 process P N PT range PN
4. 5 1 which says that performing the action start V at time end in a state s causes velocity to be V in any successor state of s The executability condition will have the form impossible start V if velocity 0 5 2 which says that in any state s it is not possible to perform start V at time end if the velocity is not zero In other words the car cannot be started if it is already moving The effects of the action stop will be given by the causal law stop causes velocity 0 5 3 43 which says that performing the action stop at time end in a state s causes the velocity of the car to be 0 in any successor state of s The execntability condition will have the form impossible stop if velocity 0 5 4 which says that in any state s it is not possible to slop the car at time end if the velocity is 0 In other words the car cannot be stopped if it is not moving position is defined by the state constraint position fQ V T if position 0 Yo 5 5 velocity V which says that position is defined by Newtonian equations in any state We will now consider the program a 4D3 obtained by translating the statements of AD The actions and processes of the domain will be declared as action start V agent range velocity V V gt Q action stop agent process velocity fluent process position continuous Statement 5 1 will be translated as val V velocity 0 1 1 o start V T
5. Example of such a process would be the function height of a freely falling object Suppose that a ball 50 meters above the ground is dropped The height of the ball at any time is determined by Newton s laws of motion The height varies continuously with time until someone catches the ball before it reaches the ground Suppose that the ball was caught after 2 seconds Assume that there is only one arm that drops and catches the ball The corresponding transition diagram will contain transitions of the form So 8 holding height fo 50 T sholding height f 50 T holding drop catch height fo 30 T 0 5 0 0 0 2 where fp and f are defincd as REDEY AV T Ag Figure 1 2 Transitions caused by drop and catch Notice that states of this diagram are represented by mapping of values to the symbols holding and height over corresponding intervals of time For example in state s holding is mapped to false and height is defined by the function f1 50 7 where T ranges over the interval 0 2 Intuitively the time interval of a state s denotes the time lapse between oc currences of actions The lower bound of the interval denotes start time of s which is the time at which an action initiates s The upper bound denotes the end time of s which is the time at which an action teminates s We assume that actions are instantaneous that is the actual duration is negligible with respect to the dura
6. J range velocity V 44 Statement 5 2 will be translated as o starl V T val VO veloeity T VO 0 rangelvclocity V rangelvclocity VO Statement 5 3 will be translated as val 0 velocity 0 I 1 o stop T I Statement 5 4 will be translated as o stop T I val 0 velocity T I Statement 5 5 will be translated as function f5 val f5 Y 0 V T position T I val Y 0 position 0 1 val V velocity T I in T I range position Y0 range velocity V 45 Now consider the recorded history T obs 0 velocity 0 0 obs 0 position 0 0 These observations say that initially the car is not moving and positioned at 0 The program a ADs Di is obtained by adding T to a ADs Now suppose that the goal of an agent acting in this domain is to drive to a certain position on the X axis and stop there We will use the rule goal T I val 8 position T 1 5 6 val 0 velocity T I to say that the goal is to reach position 8 and stop there To achieve this goal the values of I and T must satisfy the rule success goal T I 5 7 Failure is not an option Therefore we write not success 5 8 The rules 5 6 5 7 and 5 8 will be added to the program a AD3 T1 We know that I takes integer values from some interval 0 n This means that we can look for plans of no more than n consecutive steps Candidate plans will
7. i e for any process p of T contains obs v p 0 0 then M is a model of I iff M is defined by some answer set of a D A proof of the above hypothesis will not be presented in this thesis If proven it means that our translations are indeed correct In the next chapter we will look at a complex example and some experimental results 32 CHAPTER 4 EXAMPLE DOMAIN In this chapter we will look at an example domain and show how our language can be used to model it First we will understand the physics of the system and then construct an action description describing the system Later we will translate the statements of the action description into rules of A prolog Finally we will look at some sample scenarios and experimental results Example 4 1 Consider a rectangular water tank with a faucet on the top and a drain at the bottom The faucet is the source of water to the tank and the drain is an outlet The faucet can be opened and closed We are interested in predicting the volume of water in the tank Let us first understand the physics of the system Assume that the velocity at which the water flows out of the faucet into the tank called inflow rate is approximately 3 m sec when the faucet is open and 0 when it is closed The volume of water flowing into the tank per second denoted by Vin is determined by the following equation Vin inflow rate cf 4 1 where cf is the cross section area of the faucet opening
8. C iff there is an answer set Q of conf C U DAL such that E o A T I action A ex A o A T 1 E QA hpd A T I Q Let us introduce some faults in Example 4 1 of the water tank and see how a diagnosis is done when the agent s predictions do not match with reality First we introduce the exogenous action break which causes the faucet to malfunction By malfunction we mean that the faucet will be unable to output any water even when it is open We will introduce the boolean fluent broken to denote that the faucet is broken We extend the signature D2 in Example 4 1 to include the exogenous action break and fluent broken A few additions and modifications will be made to the action description AD of Example 4 1 The effects of the action break will be given by the 50 causal law break causes broken 5 9 which says that the exogenous action break causes the faucet to be broken The executability condition is of the form impossible break if broken 5 10 which says that the faucet cannot break if it is already broken Statements 5 9 and 5 10 are now part of AD The statements 4 9 and 4 10 will be modified to accomodate the effects of break inflow rate 3 if open 5 11 broken inflow rate 0 if open 5 12 broken Let us now look at the translations of the above statements First we must declare the exogenous action break and the fluent broken action break ex process broken
9. I maps a fluent f to a value v dom f Given that 1 n are executable in a state s a function s 1 f1 n tn where ty lt t2 lt tn lt t expresses the state of the world after t units of time from the time to corresponding to s assuming that the actions a1 an were started at relative to 80 to times f respectively Note that is a number gt 0 If the effects of the actions terminate at a time t such that lt then the values of fluents during will be defined by inertia In ADC all notions of time are relative In sitcalc time is the actual occurrence time of an action In our approach time is local But it is possible to predict global values of processes by mapping local time into global time The version of ADC presented in 4 does not allow conditional effects and temporal preconditions Examples such as 2 2 in which the effects of actions depend on the value of some fluents temporally and conditionally cannot be modeled using this version of ADC It does not contain state constraints and therefore will be unable to model examples such as 4 1 The authors of 4 are planning to enhance ADC by adding new features such as those for expressing temporal preconditions conditional effects or state constraints They use a Java planner to implement their action theories Results are satisfactory 81 CIHLAPTER 7 CONCLUSIONS AND FUTURE WORK In this thesis
10. We will use the features of SMODELS to reason about such effects Let us look at the following example Example 6 3 Consider the actions deposit and withdraw that effect the balance of a bank account Now suppose that multiple deposits and withdrawals were made from the same account at the same time The resulting balance can be computed by adding all the deposits to the existing balance and subtracting all the withdrawals from it We will now see how to do this using weight rules of SMODELS Let us construct an action description AD of H describing the above domain The corresponding signature 4 contains the actions deposit A and withdraw A X which denote depositing X dollars into account A and withdrawing X dollars from account A respectively and the flucnts increase A decrease A and balance A increase A and decrease A are numerical fluents that denote the increase and de crease in account A respectively The range balance A range increase A and range decrease A is the set of real numbers The effects of the action deposit A X will be given by the causal law deposit A X causes increase A X 72 which says that depositing N dollars into account cl at time end in a state s Canses an increase of N dollars in account in any successor state of s It is translated as val X inerease A O I 1 o deposit AX T 2 account A range balance A X The effects of the action withdraw will be giv
11. describes a transition diagram TD AD whose nodes represent possible states of the world and whose arcs are labeled by actions Whenever possible the parameter AD will be omitted Definition 2 2 An interpretation 1 of H is a mapping that assigns properly typed values to the processes of H such that for every continuous process c c end I c I end and I c 0 J c 0 A mapping Jp below is an example of an interpretation of action language of Exam ple 2 1 Ip end 0 Ip holding T Io height 0 50 13 Ip height end 50 Io height fo 50 T Definition 2 3 An atom p v is true in interpretation I symbolically J p v if I p v Similarly I p v if I p v An interpretation J is closed under the state constraints of AD if for any state con straint 2 1 of AD IE l for every i 1 lt i lt n then JE lo Definition 2 4 A state s of a TD AD is an interpretation closed under the state constraints of AD It is easy to see that interpretation Jy corresponds to the state sy in Figure 1 2 Whenever convenient a state s will be represented by a set l s H l of literals For example in Figure 1 2 the state sy will be the set So end 0 holding height 0 50 height end 50 height fo 50 T Please note that only atoms are shown here sy also contains the literals holding 1 height 0 4 10 height 0 20 and so on Definition 2 5 Action a is exe
12. g height end 0 will be translated as val 0 height T S val V p T T if l is of the form p v other than c 0 v val V p T I is read as V is not the value of process p at time T of step I ao l 0 1 1 will be replaced by val V p 0 1 if l is of the form p v val V p 0 1 1 if l is of the form pF v Note that when translating the f atom end y we will not follow the above conventions Instead we translate it as end T J where T denotes the end of step I Observations of the form obs v p t i and hpd a t i are translated as facts of A Prolog programs Before we look at some examples we will discuss domain inde pendent axioms 24 3 3 DOMAIN INDEPENDENT AXIOMS Domain independent axioms define properties that are common to every do main We will denote such a collection of axioms by II Given a domain description D and a D that maps D into rules of A prolog we will construct a D that adds I to aal D Therefore a D IU ag D Let us look at the axioms constituting I END OF STATE AXIOMS These axioms will define the end of every state s The end of a state is the local time at which an action terminates s When it comes to implementation we talk about the end of a step instead of state Therefore we write end T 1 o A T D 3 4 If no action occurs during a step then end will be the maximum time point allowed for that step This is accomplished by using the choice rule end m
13. is a discrepancy it sends a message to the agent that in flow_rate was observed to be 0 at time 3 of step 0 This will be represented by the fact error 0 in flow rate 3 0 5 13 Now we write the general rule obs Y P 0 I 1 error Y P T I 5 14 which states that since an error was detected at time T of step I it must be true that an exogenous action must have occurred at this time and therefore Y will be the observed value of process P at time 0 of the next step I 1 We also need the rule end T I error Y P T I 5 15 to make sure that the step ends at time T when the discrepancy was detected The maximum number of steps is incremented by one and the rules 5 13 5 14 5 15 are added to the program a AD gt 2 I The resulting program is inconsistent 58 Therefore we augment it with the diagnostic module DM to restore consistency o A T I action Ad co error P T 1 5 16 I lt n The answer set of the resulting program contains o break 3 0 which is indeed the correct explanation The average run time for this program was 4 9 seconds of which SMODELS took 2 1 secs and Lparse and SMODELS together took 4 6 seconds 59 CHAPTER 6 RELATED WORK In this chapter we will compare language H with two other languages used for similar purposes The first language is called situation calculus 13 14 and the second one is called ADC 4 which stands for Actions with Delayed and Continuo
14. we introduced the action language H for modeling hybrid do mains We looked at many examples and showed how they are modeled in this language The syntax and semantics of the language were defined We implemented action theories of H using A Prolog Some examples involved planning and diagnosis We were able to show that language H overcomes many of the limitations of sitcalc and ADC It provides almost all the functionalities of sitcalc and ADC and can model domains that cannot be modeled by the other two Using local time not only improves efficiency but also allows us to represent different kinds of time units For instance given a transition diagram TD the local time of a state s TD could represent time in the order of seconds while the local time of an other state could represent minutes or hours For example consider the action set_timer X that sets the timer on a mi crowave to N time units The local time of a state resulting from performing this action represents either minutes or seconds depending on whether N is minutes or seconds Now let us look at some future work prospects One area for future research is delayed grounding By delayed grounding we mean that functional values and 82 times are grounded if and only when needed This could reduce the program size and improve efficiency Another area for future research is developing mechanisms for efficient planning and diagnosis In chapter 5 there were some scenario
15. will use the fluent holding We will define the relation act_poss that defines the possible time t at which hit_ground can occur as follows function f act_poss hit_ground f H I val H height 0 1 H gt 0 val false holding 0 I f is a user defined function that is linked to Iparse that returns the value y2 H g The following rule says that the action hit ground will occur at time t of step i if t 69 is the time at which it is supposed to occur and 1 is a time point during step o hit ground T 1 act_poss hit_ground T 1 in T I An other approach to modeling natural worlds is to get rid of natural actions and just have processes The effects of actions will then be captured by process definitions This may probably lead to complex process definitions but it gives us another approach to compare with Example 6 2 Let us revisit the Example 2 2 from chapter 2 We will model this example again but with a different approach We will get rid of the natural action bounce The action description AD that we constructed previously will be modified Let us call this modified version as AD Please note that velocity will be treated as a continuous process now The corresponding signature PA contains the continuous processes position and velocity and fluents position 0 position end velocity 0 velocity end G contains the functions Yo ifT 0 fo Yo Vo T fo Yo Vo T 1 filo vT
16. 1 fT gt 0 70 le ifTs0 Yo if fo lo bo T wp and fi vo Yo T fo Yo o T wp and T gt 0 o otherwise where Y rangelposition Vo range velocity and wp wpz are constants de noting the position of the walls w and wz respectively The process position will be defined by the state constraint position folYo Vo T if position 0 Yo velocity 0 Vo which says that position will be defined by Newtonian equations in any state velocity is defined by the state constraint velocity f Vo Yo T if velocity 0 Vo position 0 Yo which says that the direction of velocity will change only when the position of the ball is the same as the position of a wall This is of course when velocity is not zero The effects of the action bounce are captured by the function fi When we look at Examples 6 2 and 2 2 and the way they are modeled in H there is not much difference The advantage of Example 6 2 is that when we implement it using A Prolog the answer set solver need not compute occurrence times of bounce 71 When we implement Example 2 2 we have to write extra rules that will com pute the occurrence times of bounce These computations cost us time The approach suggested by Example 6 2 is just one way of improving efficiency Let us discuss some of the limitations of H Language H is not capable of representing the effects of several concurrently exccuting actions on a process
17. I 1 3 5 The consequence of the rule 3 5 is that the number of end m 1 that will be true is either 0 or 1 A step cannot have more than one end This is expressed by 3 6 end T1 J 3 6 end T2 I neq T1 T2 25 Every sfep must end Therefore we write ends 1 end T 1 3 7 nol ends I 3 8 Every step i is associated with an interval 0 e where 0 denotes the start time and e denotes the end time of i We will use the relation out to define the time points t 0 e and in to define the time points t 0 el out T I end T1 J 3 9 F gt TA in T I not out T 1 3 10 By using these relations in our rules we can avoid computing process values at time points t 0 e INERTIA AXIOM The inertia axiom states that things normally stay as they are It has the following form val Y P 0 I 1 val Y P T I 3 11 end T I not val Y P 0 I 1 Intuitively rule 3 11 says that actions are instantaneous In example 2 1 height at global time O is 50 when the instantaneous action drop occurs at 0 REALITY CHECK AXIOM This axiom guarantees that the agent s predictions match with his observations obs P T 1 8 12 wal Py Pd OTHER AXIOMS The axiom o A T I hpd A T I 3 13 says that if action A was observed to have happened at time T of step I then it must have occurred at time T of step I And we have val Y P 0 0
18. MODELING HYBRID DOMAINS USING PROCESS DESCRIPTION LANGUAGE by SANDEEP CHINTABATHINA B S A THESIS IN COMPUTER SCIENCE Submitted to the Graduate Faculty of Texas Tech University in Partial Fulfillment of the Requirements for the Degree of MASTER OF SCIENCE Approved Chairperson of the Committee Accepted Dean of the Graduate School December 2004 ACKNOWLEDGEMENTS I would like to thank my parents and my sister for their support and good wishes They have always been my reason to do well Mother and Father I would like to express to vou my gratitude in your support as pursue my college education And Akka I have learned a lot of things from you over the years Thank you for everything I would like to thank Dr Gelfond and Dr Watson for making this thesis possible You guys are good at what you do and also nice to work with You have constantly pushed me and got the best out of me Thank you for your guidance and support Dr Gelfond working with you is an unforgettable experience I am amazed by your ability to concentrate Your work ethic and moral values will always inspire me I have learned so much from you You always make time for me even when you are so busy You worked almost everyday with me to finish this thesis I really appreciate it Thank you for all your suggestions and comments Dr Watson you are a very open minded and down to earth person You hired me as a research assistant at a time when I despe
19. Now we will define the outflow rate which is the velocity at which the water flows out of the drain We 33 apply Bernoulli s equation of law of conservation of energy to an open tank under atmospheric pressure to derive oul flow rale 2 g h 4 2 where g is acceleration due to gravity and h is the height of the water level in the tank Now we can define the volume of water flowing out of the tank per second denoted by Vi as follows Vou out flow rate cd 4 3 where cd is the cross section area of the drain opening If V is the volume of the tank at current time t then Vesa Vi Vin Vout 4 4 Now let us construct an action description AD describing the above system Sig nature U2 contains the actions turn open and turn close for opening and clos ing the faucet continuous processes volume and outflow_rate and fluents open in flow rate volume 0 volume end out flow rate 0 and out flow rate end The range volume and range outflow_rate is the set of non negative real numbers open is a boolean fluent range inflow contains 0 and 3 Let G2 contain functions Y if T 0 BONT BOUNT DIN se fiY N T l cd if T gt 0 falY N T 2 9 BO NTD U b 34 where Y range volume N range inflow rate and the constants cf cd 9 l and b denote the cross section arca of the faucet cross section area of the drain acceleration due to gravity length and breadth of the tank respecti
20. O A pair ESE will be often referred to as systems configuration If new observations are consistent with the agent s view of the world ie if C is consistent then O simply becomes part of recorded history In other words 4 C Otherwise the agent has to start seeking the explanation s of the mismatch Let conf C a AD T UO C is consistent iff conf C has an answer set Definition 5 2 The configuration C is a symptom of system s malfunctioning iff the program con f C has no answer set An explanation of the symptom can be found by discovering some unobserved past occurrences of exogenous actions Let denote a set of elementary exogenous actions corresponding to D Definition 5 3 An explanation E of symptom C is a collection of statements E hpd a t i 0 lt i lt nandae E such that T U O U E is consistent 49 Answer set programming provides a wav of computing explanations for inconsistency of C Such a computation cau be viewed as planning in the past We construct a program called diagnostic module DM that computes explanations The simplest diagnostic module DA is defined by the choice rule of SMODELS o A T 1 action A er 0 lt I lt n where ex stands for exogenous action Finding diagnoses of the symptom C is reduced to finding answer sets of the program conf C U DM A set E of occurrences of exogenous actions is a possible explanation of inconsistency of
21. PLE DOMAIN PLANNING AND DIAGNOSIS 5 1 PLANNING oh a AM aa Ar 5 2 DIAGNOSIS RELATED WORK 6 1 SITUATION CALCULUS 62 LANGUAGE ADC 3 iv vi vii 13 16 19 19 22 25 28 33 7 CONCLUSIONS AND FUTURE WORK REFERENCES vy eo a lt 4 APPENDIX A ABSTRACT Researchers in the field of knowledge representation and logic programming are constantly trying to come up with better ways to represent knowledge One of the recent attempts is to model dynamic domains A dynamic domain consists of actions that are capable of changing the properties of objects in the domain for exainple the blocks world domain Such domains can be modeled by action theories collection of statements in so called action languages spccifically designed for this purpose In this thesis we extend this work to allow for continuous processes properties of objects that change continuously with time For example the height of a freely falling object In order to do this we adopt an action language logic programming approach A new action language called process description language is introduced that will be useful to model systems that exhibit both continuous and discrete behavior also called hybrid systems An example of a hybrid domain is the domain consisting of a freely falling object A freely falling object is in the state of falling which is a discrete property that can be changed only by actions also c
22. Y o AN T 1 hpd AN T 1 action AN AT Axiom for defining initial state 89 val Y PN 0 0 obs Y PN 0 0 process PN PT range PN Y Process definitions 1 open Dynamic causal law describing effects of turn open val true open 0 1 1 o turn open T T Executability conditions for turn open o turn open T 1 val true open T I Dynamic causal law describing effects of turn close val false open 0 1 1 o turn close T I Executability conditions for turn close o turn close T I val false open T I 2 inflow_rate State constraints defining inflow_rate If the faucet is open inflow is 3 val 3 inflow rate T I val true open T 1 90 If the faucet is closed inflow is 0 val 0 inflow rate T 1 val false open T I 3 outflow_rate State constraints defining outflow_rate outflow rate is a function of the water level of the tank function f4 val fY Y outflow rate T val volume T J range volume Y 4 volume State constraints defining volume function f3 val f3 Y0 N volume T 1 1 val Y0 volume T I val N inflow rate T T in T 1 1 range volume Y 0 range in flow rate N 91 History obs 25 volume 0 0 obs false open 0 0 hpd turn open 0 0 hpd turn close 3 1 Defining some relations to ge
23. alculus and H For this we will model the Example 2 1 from chapter 2 in situation calculus In that example we had actions drop and catch and processes holding and height The continuous process height will be treated as a functional fluent holding will be treated as a relational fluent To reason about the effects of actions situation calculus uses three kinds of axioms namely action precondition axioms successor state axioms and unique names axiom for actions Action precondition axioms specify conditions that must be satisfied in order for an action to be executed in any situation They can be considered as counterparts of executability conditions of language H They are more powerful than executability conditions in the sense that they can be used to determine the occurrence times of natural actions The following example demonstrates how to use action precondition axioms to predict the occurrence times of a natural action such as bounce 65 Example 6 1 poss bounce t s isFalling s A height s vel s t start s sel start s 0 Note that in situation calculus lower case letter are used to denote variables and upper case letters are used to denote constants height s and vel s are the height and velocity of the ball at start of situation s poss bouncelt s means that bounce is physically possible at time t during situation s The action precondition axioms for drop and catch from Example 2 2 will be po
24. alled fluent while its height is a continuous process The syntax semantics and translation of the statements of the language into rules of a logic program will be discussed Examples of domains that can represented in this language will be given In addition some planning and diagnostic problems will be discussed Finally the language will be compared with other languages used for similar purposes vi LIST OF FIGURES Transitions caused by flip Transitions caused by drop and catch Mapping between local and global time Architecture of an agent in a hybrid domain vil CHAPTER 1 INTRODUCTION Designing an intelligent agent capable of reasoning planning and acting in a changing environment is one of the important research areas in the field of AI Such an agent should have knowledge about the domain in which it is intended to act and its capabilities and goals In this thesis we are interested in agents which view the world as a dynamical system represented by a transition diagram whose nodes correspond to possible physical states of the world and whose arcs are labeled by actions A link so a s1 of a diagram indicates that action a is executable in so and that after the execution of a in sy the system may move to state s Various approaches to representation of such diagrams 3 6 9 can be classified by languages used for their description In this thesis we will adopt the approach in which the diagrams are represented
25. ample from 4 Example 6 6 Suppose that driving a car with velocity v for 10 units of time consumes c v units of gasoline per unit time This is expressed as driveoo v contributes c v t to gas intank from 0 to 10 And suppose that filling gas for 10 units of time will increase the amount of gasoline 79 by 2x This is expressed as fill gasoag contributes 2x4 to gas in lauk from 0 to 10 Let us assume that while driving we can refill and that initially the gas in lank was 20 Suppose that action drivei10 3 starts its execution at time 0 and full_gaso 10 starts it execution at time 0 Let c 3 1 5 The net value of gas in tank at time 1 will be 20 1 5 1 21 which is 20 5 Similarly at time 2 gas in tank 21 and so on As mentioned earlier language H and sitcalc depend on the implementation to represent the effects of several concurrently executing actions Note that properties of objects that change continuously with time are still referred to as fluents in the language of ADC We will now discuss the semantics for action theories in ADC In the presence of time and delayed effects the effects of an action might not happen immediately or might last over a time interval Therefore a state encodes not only the fluent values but also obligations due to delayed effects of recent actions and actions under execution A state is a pair J Q where I is an interpretation and Q is a set of future effects An interpretation
26. and has an answer set that con tains o break 0 0 which is the possible explanation for the inconsistency of con f C The average run time for this program was 4 9 seconds of which SMODELS took 2 1 seconds and Lparse and SMODELS together took 4 7 seconds Example 5 3 Let us look at another scenario where answer set programming alone may not be enough to find explanations Consider the history I hpd turn close 3 0 obs true open 0 0 obs 25 volume 0 0 obs 3 inflow rate 0 0 obs false broken 0 0 93 and the new observation Ol fobs 17 volume 0 1 The program con C a 1D2 P U O is found to be inconsistent So it is augmented with the diagnostic module D o The resulting program is still inconsistent The diagnostic module DA will compute only those explanations in which the unobserved exogenous actions occur in parallel with agent s action In Example 5 3 Ty predicts val 33 volume 0 1 which contradicts the ob servation obs 17 volume 0 1 Therefore we add DAI to find explanations DM will look for an exogenous action that occurs at the same time as the agent action turn close But fails to find one In reality an unobserved exogenous event must have happened before the agent action was executed A possible explanation for the unexpected observation obs 17 volume 0 1 is the unobserved occurrence of break at time 1 of step 0 Similarly there may arise situations in which break coul
27. be generated by the choice rule P Mo o A T I action A agent I lt n 46 For any value of I ranging from 0 to n 1 if the goal is not satisfied PAo will select a candidate action Po is also called the planning module Answer sets of the program a AD T1 U PAL will encode candidate plans i e possible sequences of actions that satisfy success In our example I and T take integer valucs from the intervals 0 2 and 0 6 re spectively A total of 21 different candidate plans were generated and the average run time was 4 6 seconds of which SMODELS took 2 75 secs and Lparse and SMODELS together took 4 4 seconds One of the candidate plans o start 2 4 0 o stop 4 1 is to start driving with a velocity of 2 at time point 4 of step 0 and then stop at time point 4 of step 1 at which point the car is positioned at 8 5 2 DIAGNOSIS In this section we are interested in the agent s ability to diagnose Diagnosis involves finding possible explanations for discrepancies between agent s predictions and system s actual behavior The algorithms used in 1 3 to perform diagnostic tasks are based on encoding agent s knowledge in A prolog and reducing the agent s task to computing answer sets of logic programs We will use a similar approach to do diagnosis in hybrid domains 47 The first step of an observe think act loop of an intelligent agent is to observe the world explain observations and update t
28. by action theories collections of statement in so called action languages specifically designed for this purpose This approach allows for useful classification of dynamical systems and for the methodology of design and implementation of deliberative agents based on answer set programming Most of this work with the notable exception of 4 14 deals with discrete dynamical systems A state of such a system consists of a set of fluents properties of the domain whose values can only be changed by actions An example of a fluent would be the position of an electrical switch The position of the switch can be changed only when an external force causes it to change Once changed it stays in that position until it is changed yet again The corresponding transitions in the diagram are shown in Figure 1 1 So 8 Lip n o on a on flip gt Figure 1 1 Transitions caused by flip Action languages will describe the diagram in Figure 1 1 by so called dynamic causal laws of the form flip causes on if on 1 1 flip causes on if von 1 2 1 1 says that performing the action flip causes the position of the switch to be of f if it was on 1 2 says that performing the action flip causes the position of the switch to be on if it was of f In this thesis we focus on the design of action languages capable of describing dynamical systems which allow continuous processes properties of an object whose values change continuously with time
29. called directly from logic programs Note that the function has to be declared before it appears in any rule For more information on how to use them refer to the Iparse user manual height BUY T if height 0 y sholding is translated as function fl val f1 T height T I val Y height 0 T val false holding T 1 in T I range height Y where f1 is also a user defined function that is linked to lparse The value returned by the function f1 given Y and T will determine the value of height at T Now let us look at the translations for the causal laws in Example 2 2 The dynamic causal law bounce W causes velocity V if velocity V is translated as 30 val V1 velocily 0 1 41 o bounce W T 1 val V velocity T 1 Vl 1 V wall W rangelvelocity V range velocity V1 And the state constraint position fo lo T if vosition 0 Y velocity V is translated as val f2 Y0 V T position T I val Y0 position 0 I val V velocity T J in T I range position Y 0 range velocity V where f2 is a user defined function The following hypothesis establishes the rela tionship between the theory of actions in H and logic programming 31 HYPOTHESIS Given a domain description D AD Ina where AD is an action description of H gG A and T is the recorded history upto moment n if the initial situation of Pn is complete
30. crease to the existing balance and then subtracting the total decrease from it The rule that we used to define balance is called a weight rule An other approach to implementing Example 6 3 is to use ASET Prolog 16 which is an extension of A Prolog by sets and aggregates Functions such as sum of elements of a set and cardinality of a set are implemented in this language The answer sets of ASET Prolog programs are computed by an inference engine called the ASET solver Like H the language of situation calculus is not capable of representing the effects of several concurrently executing actions on a fluent Instead sitcalc depends on the implementation to reason about such effects Eclipse Prolog has built in aggregate functions such as sum L which returns the sum of elements of list L sum L can be used to define balance 1 from Example 6 3 6 2 LANGUAGE ADC The language ADC was introduced by Baral Son and Tuan in 4 as a lan guage for specifying actions with durations continuous effects delayed effects and dependency on non sharable resources ADC Actions with Delayed and Continuous effects is the first language to use a transition function based approach to dealing with such actions Language H also uses a transition function based approach for dealing with such actions In ADC actions can have delayed and continuous effects This means that effects of actions might not happen immediately or can last over a period of
31. cutable in a state s if for every non empty subset a of a there is no executability condition impossible a if 1 ln of AD such that sk l for every i 1 lt i lt n 14 Let a be an clementary action that is executable in a state s EFs a denotes the set of all direct effects of a ie the set of all literals l for which there is a dynamic causal law Ge causes lo if hy in AD such that s Ek 1 for every 7 1 lt i lt n fa is a compound action then E a Uncen E ae A set L of literals of H is closed under a set Z of state constraints of AD if L includes the head lp of every state constraint lo if b ln of AD such that l l C L The set Cnz L of consequences of L under Z is the smallest set of literals that contains L and is closed under Z A transition diagram TD V where 1 is a set of states 2 W is a set of all triples s a s such that a is executable in s and s is a state which satisfies the condition s Cnz Es a U sNs 2 6 where Z is the set of state constraints of AD The argument to C n Z in 2 6 is the union of the set E a of the direct effects of a with the set ss of facts that are preserved by inertia The application of Cn Z adds the indirect effects to this 15 union In Example 2 1 the set E drop of direct effects of drop will be defined as Es drop holding The instantaneous action drop occurs at gl
32. d have happened at time point 0 or time point 2 of step 0 DAI will be unable to explain the unexpected observations in both situations Therefore answer set programming alone is not enough to do diagnosis in such situations We have some ideas on how to approach such problems But before we talk about them there are other issues such as grounding that must be addressed In most of our examples agent s knowledge is encoded in A prolog and inference engines such as SMODELS are used to reason about such knowledge Computing values of processes may involve trignometric functions differential equations complex 54 formulas etc Existing answer set solvers cannot carry out suck computations Also when numbers become large the solvers run out of memory Besides this SMODELS grounds all variables in the program leading to poor efficiency In the following paragraphs we propose an agent architecture for hybrid do mains which will overcome computational problems and aid in efficient diagnosis A solution to the computation problem is to limit the answer set solver to reason about effects of actions and leave the computations to an external program The external program will be called monitor The agent and the monitor will interact with each other in the following manner The agent s task will be reduced to computing the answer sets of an A prolog program The answer sets will contain information about the values of processes at time 0 and the
33. ecursive function fs which in turn calls 37 the function f4 One way of implementing such functions is to link them to lparse Lparse uses pointer arithmetic to deal with the arguments of the user defined func tions It is capable of handling simple recursion but fails to give expected results when functions interact recursively with each other Therefore we simplify these functions considerably so that lparse can handle them Therefore the translations of 4 11 and 4 12 contain modified versions of fz and fy We will call these modified versions as f and f respectively The following equation defines the relationship between fs and f f3Q N T BOND if fa o N T 1 Y Therefore 4 11 is translated as function f3 val f3 Y0 N volume T 1 1 val Y0 volume T I 4 19 val N inflow _rate T I in T 1 1 range inflow _rate N range volume Y0 The following equation defines the relationship between f4 and f4 fY T AND if fo N T Y Therefore 4 12 is translated as function f8 val f4 Y out flow rate T I val Y volume T 1 4 20 range volume Y 38 For a complete listing of the translations along with declarations and domain inde peudent axioms please refer to Appendix A SAMPLE SCENARIO AND RESULTS Let be the collection of observations obs 25 volume 0 0 obs false open 0 0 hpd turn open 0 0 hpd turn close 3 1 The program a AD T
34. en by the causal law withdraw A X causes decrease A X which is translated as val X decrease A 0 I 4 1 o withdraw 4 X T I account A range balance A X We cannot define balance A using our language but we can write the following rules in the language of SMODELS weight val X P T I X 73 val N balance 0 I 1 val Xo balance A 0 7 N feal X3 inerease A 0 I 1 range balance A NN Naleal N deerease d 0 1 1 range balance 1 Val Ns NV No VY No range balance Xo range balance A X1 range balance A X2 range balance A X account A The total increase and decrease in each account A is computed by using the weight literals Ny val X3 increase A 0 1 range balance A X3 X1 Nolval N decrease A 0 I 1 range balance A X4 Xo To be able to determine whether these weight literals are satisfied the weight decla ration weight val X P T I N is used to assign weights to each atom of the form val N P T 1 In this case the weight of the atom val X P T J is X For example y val X3 increase A 0 I 1 range balance A X3 X1 is satisfied if the sum of weights of the satisfied literals of the form val X3 increase A 0 I 1 is equal to Y where VY range balance A Intuitively it can be viewed as aggregating over elements of a set 74 The new balance is obtained by adding the total in
35. f AAAI 97 pages 460 465 1997 2 I Niemela and P Simons Smodels an implementation of the stable model and well founded semantics for normal logic programs In Proceedings of LP NAMR 97 pages 420 429 1997 R Reiter Natural actions concurrency and continuous time in the situation calculus In Principles of Knowledge Representation and Reasoning Proceed ings of the Fifth International Conference KR 96 pages 2 13 Cambridge Massachusetts U S A November 1996 R Reiter Time concurrency and processes In Knowledge in action Logical Foundations for Specifying and Implementing Dynamical Systems pages 149 183 ISBN 0 262 18218 1 MIT 2001 Richard Watson and Sandeep Chintabathina Modeling hybrid systems in ac tion languages In Proceedings of the 2nd International ASP 03 Workshop pages 356 370 Messina Sicily Italy September 2003 Mary Heidt Developing an inference engine for ASET Prolog Master s Thesis University of Texas at El Paso Dec 2001 85 APPENDIX A IMPLEMENTATION OF WATER TANK EXAMPLE A Prolog code for implementing the water tank example 4 1 from chapter 4 Declarations actions action turn open agent action turn close agent processes process open fluent process inflow_rate fluent process outflow_rate continuous process volume continuous time const m 6 time 0 m domain time T T1 T2 step const n 2 step 0 n domain step 1
36. fluent broken is a boolean fluent Therefore range broken is defined as range broken true range broken false ol Now a 1D2 from example 4 1 will contain the rules 4 13 4 14 4 15 4 16 4 18 4 19 4 20 and the following rules Statement 5 9 is translated as val true broken 0 I 41 o break T I Statement 5 10 is translated as o break T I val true broken T I Statement 5 11 is translated as val 3 inflow _rate T I val true open T 1 val false broken T I Statement 5 12 is translated as val 0 in flow rate T 1 val true open T I val true broken T I Example 5 2 Consider the recorded history l containing the observations hpd turn open 0 0 obs false open 0 0 obs 25 volume 0 0 obs 0 in flow rate 0 0 obs false broken 0 0 Gt bo Let O obs 0 in flow rate 0 DY obs 0 in flow ratc 0 1 says that in flow rate was observed to be 0 at time 0 of step 1 Obviously val 3 in flow rate 0 1 predicted by T contradicts the observations This discrepancy can be explained bv unobserved occurrence of action break at time 0 of step 0 We will now see how to compute the possible explanations The program conf C a AD T1 U O is inconsistent Therefore we aug ment it with the diagnostic module DJ o A T I action A er O lt I lt n The resulting program conf C U DAI is consistent
37. functions associated with these processes The only change is that these functions are not evaluated yet The answer sets will be input to the monitor which then evaluates the functions asssociated with processes Each time the agent performs an action the initial values and functions will be input to the monitor The monitor will record all occurrences of agent actions The monitor will be capable of observing actions that occur naturally or trig gered by other actions in the environment It will report such observations to the agent The agent will do the reasoning and send new input to the monitor 55 An important function of the monitor is to help the agent diagnose The computations done by the monitor will become the predictions of the monitor The monitor will record observations with the help of sensors and then compare these observations with its predictions If there is discrepancy it will inform the agent of all those observations that did not match along with the time at which the discrepancy was found With this information the agent s task will become easier Now the agent already knows when the exogenous action s occurred It still needs to find out what exogenous action s took place For this the agent will use answer set programming techniques Once the correct explanation is found the agent reasons about the effects of the exogenous action s and sends input to the monitor The monitor will record the occurrence of exogeno
38. g Notice that this mapping allows one to compute the height of the ball at any global time t 0 7 This is not necessarily true for the value of holding According to our mapping global time 0 corresponds to two local times 0 in state sy and 0 in state s Since the values of holding in sy and s are true and false respectively the global value of holding at So S S2 holding height fo 50 T holding height fo 30 T holding height fi 50 T 0 0 Global 0 time secs Figure 1 3 Mapping between local and global time global time 0 is not uniquely defined Similar behavior can be observed at global time 2 The phenomena is caused by the presence of physically impossible instantaneous actions in the model It indicates that 0 and 2 are the points of transition at which the value of holding is changed from true to false and false to true respectively Therefore it is false at 1 and true during the interval 3 7 Since the instantaneous actions drop and catch do not have a direct effect on height its value at global time 0 and 2 is preserved thereby resulting in unique values for height for every t 0 7 Our new action language H also called as process description language will describe these transitions by defining the continuous process height flucnt holding functions fo Y T fi Y T and actions drop and catch The effects of the action drop will be given by the causal law
39. gure 1 2 Let Gp contain functions POT Y 1 AOT Y 597 where Y range height g is acceleration due to gravity and T is a variable for time points The description is given in language H whose signature Ny contains actions drop and catch a continuous process height and fluents holding height 0 and height end holding is a boolean fluent range height is the set of non negative real numbers It is easy to see that statements 1 3 and 1 6 are dynamic causal laws while statements 1 4 1 5 and 1 7 are executability conditions and statements 1 8 and 1 9 are state constraints Example 2 2 This example is simplied version of the example used by Reiter in 14 Consider an elastic ball moving with uniform velocity on a frictionless floor between two walls w and wy Assume that the floor is the X axis and the walls are parallel to the Y axis We expect the ball to bounce indefinitely between the two walls The bouncing causes velocity of the ball to change discontinuously And as long as the velocity is not zero position changes continuously with time 11 Let us now construct an action description AD of H G A that will enable us to define the velocity and position of the ball Signature X contains the action bounce W which denotes the ball bouncing against wall W a continuous process position and fluents velocity position 0 and position end Since velocity is uniform and is a changed only by b
40. hat denotes the height at time 0 of a state If holding is false then height is defined as follows height hO T if height 0 Y 1 9 sholding Statement 1 9 requires that in any state in which holding is false height is defined by Newtonian equations In the next chapter we will discuss the syntax and semantics of the language and see some more examples CHAPTER 2 SYNTAX AND SEMANTICS 2 1 SYNTAX To define our language we first need to fix a collection A of time points Normally A will be equal to the set RY of non negative real numbers but we can as well use integers rational numbers etc We will use the variable T for the elements of We will also need a collection G of functions defined on A which we will use to define continuous processes Elements of G will be denoted by lower case greek letters a 3 etc A process description language H G A will be parameterized by A G and a tvped signature Whenever possible the parameters X G A will be omitted We assume that contains regular mathematical symbols including 0 1 lt lt gt etc In addition it contains two special classes A and P F UC of symbols called actions and processes Elements of A are elementary actions A set of elementary actions performed simultaneously is called a compound action By actions we mean both elementary and compound actions Actions will be denoted by a s Two types of actions agent and exoge
41. he knowledge base We will try to provide the agent with the reasoning mechanism to explain observations We assume that the agent is capable of making correct observations perform ing actions and remembering the domain history We also assume that normally the agent is capable of observing all relevant exogenous actions occurring in its environ ment Now let us look at some terminology Let D be a diagnostic domain Definition 5 1 Bv a diagnostic domain we mean the pair TD where is a domain signature and TD is a transition diagram over Consider an action description AD of H that describes D Let I be a recorded history of D up to moment n Now consider a mapping a that maps the domain description D AD T into rules of A Prolog The resulting logic program will be denoted by a AD T The recorded history contains a record of all actions the agent performed or observed to have happened upto moment n 1 This knowledge enables the agent to make predictions about values of processes at the current moment n To test these predictions the agent observes the current value of some pro cesses We simply assume that there is a collection P of processes which are observ able at n The set OT obs v p t n P P 48 contains the corresponding observations At this point it is convenient to split the domain s history into two parts The previously recorded history Fn and the current observations
42. ing translated other than the head of a dynamic causal law then it will be written as ao l T I ooll T T is a function that denotes a translation of literal l A literal occurring in the head of a dynamic causal law will be written as ao l 0 1 In this thesis we limit ourselves to translating action descriptions of H in which the heads of dynamic causal laws are either f atoms or their negations The general translations look as follows Wo Ww Statement 2 1 will be translated as ao Io T I agt T 1I 3 1 Statement 2 2 will be translated as amp o lo 0 I 1 os olae T I 3 2 ao l T I Oom T I Statement 2 3 will be translated as o a T 1 3 3 ao T I aolln T I In statement 2 3 if a is the non empty compound action a1 am then o a T I in rule 3 3 will be replaced by o a1 7 J 0 m T We will not translate 2 3 when a is empty ao l T I will be replaced by e val V c 0 if lis an atom of the form c 0 v 23 val V c 0 I is read as V is the value of process e al time 0 of slep 1 E g herght O Y will be translated as val height 0 I val V e 0 1 if 7 is of the form c 0 v val V c 0 I is read as V is not the value of process c at time 0 of step I val V p T 1 ifl is an atom of the form p v other than c 0 v val p T I is read as V is the value of process p at time T of step I E
43. ion S This means that holding is false at 0 In other words it is uniquely defined at 0 This is possible because the start time of Sp is not defined In our approach we use local time Suppose that at local time 0 of the initial state holding is true Now suppose that the ball is dropped at this time This causes holding to be false at local time 0 of the successor state Since both these local times map to the same global time 0 holding is not uniquely defined at 0 Global time 0 is the point of transition for the value of holding from true to false 67 Coming to implementation axioms of situation calculus are translated into rules of Prolog The resulting program can be verified for correctness by querying the prolog interpreter for fluents values and occurrence times of actions The existing prolog systems support floating point numbers thereby allowing fluent values and occurrence times of actions to be real numbers Reiter s group uses the Eclipse Prolog system primarily because as implied by its name the ECLiPSe Constraint Logic Programming Svstem provides built in constraint solving libraries that are used for temporal reasoning Most of the existing prolog systems suffer from floundcring omit occurs check and are not capable of generating multiple models Eclipse Prolog overcomes some problems involving non ground negative atoms but suffers from other drawbacks We translate statements of H into rules of A Prolog A Pro
44. is obtained by adding T to a AD2 In order to run this program the variables and processes are declared as usual For instance I and T take integer values from the intervals 0 2 and 0 6 respectively range volume is the set of integers from the interval 0 60 The program was run on Sparc Ultra 10 running Solaris 8 using the 1 0 9 ver sion of Iparse and 2 26 version of SMODELS The corresponding answer set returned from the program was as expected The average run time was 7 2 seconds of which SMODELS took 3 3 seconds and lparse and SMODELS together took 7 seconds SMODELS directives are used to get a better looking output The resulting answer set is 39 process_name Value Local time Step oul flow_rate 6 0 0 volume 25 0 0 in flow rate 0 0 0 oul flow rate 6 0 1 volume 25 0 1 inflow rate 3 0 1 out flow rate 6 1 1 volume 28 1 1 inflow rate 3 1 1 out flow_rate 7 2 1 volume 31 2 1 inflow rate 3 2 1 out flow rate 7 3 1 volume 33 3 1 in flow rate 3 3 1 out flow_rate 7 0 2 volume 33 0 2 in flow rate 0 0 2 out flow rate 6 1 2 volume 26 1 2 in flow_rate 0 1 2 out flow rate 5 2 2 volume 20 2 2 in flow rate 0 2 2 out flow_rate 4 3 2 volume 15 3 2 in flow_rate 0 3 2 out flow rate 4 4 2 volume 11 4 2 in flow rate 0 4 2 out flow rate 3 5 2 volume 7 5 2 in flow_rate 0 5 2 out flow_rate 2 6 2 volume 4 6 2 in flow_rate 0 6 2 The following answer set
45. log uses a reasoning algorithm that is completely different from the one Prolog uses and overcomes many of Prolog s shortcomings A Prolog programs can have multiple models which means that A prolog can handle non determinism It is also capable of representing defaults The task of predicting the values of processes and the occurrence times of actions is reduced to computing answer sets of A Prolog programs We use existing answer set solvers like SMODELS to compute answer sets of our programs Reiter s main goal was to model natural actions actions that occur in response to known laws of physics For example a ball bouncing on the floor after being dropped The occurrence time of bounce is determined by Newtonian equations 68 In order to represent such an action the laws of physics are embodied in action precondition axioms as in example 6 1 In our language H there are no special axioms that will define when a natural action such as bounce will occur In chapter 2 we mentioned that this task will be accomplished by writing action triggers Let us look at an example where we write triggers Suppose that a book was dropped from a height h above the ground The time at which it hits the ground is equal to 2 h g where g is acceleration due to gravity In order to determine the time of occurrence of hit_ground we need to know the initial value of height plus we need to know whether the book is falling or someone is holding it For this we
46. losion The following proposition of ADC represents this effect set_timer x causes explosion from x to z In the above statement the x in x to x denotes z time units relative to the time point when set_timer was executed Therefore the above causal law says that set timer r causes explosion after exactly x time units since its execution This action does not have continuous effects and the only effect is at the x time unit This is suggested by the to x in the above statement In ADC lower case letters are used to denote variables Let us construct an action description AD of H describing this example The corre sponding signature Ug contains the actions set timer X detonate continuous pro cess time left and fluents explosion time left 0 and timeleft end explosion is a boolean fluent rangeltime left is the set of non negative real numbers Let Ge contain the function x if T 0 fe X T KEET S11 HES where Y rangeltime left and T is a variable for time Setting the timer to Y 77 time units initializes Fimc lefl to N Therclore we write seltimer X causes time te ft 0 N timeleft will be defined by the state constraints timetleft fe X T if timeteft 0 X which says that time_le ft will decrement with every time unit The action detonate will be triggered when time_left becomes 0 causing explosion Therefore we write detonate causes explosion The trigger for detonate
47. ly E g holding height 0 Y height end 0 Note that height 0 Y is a schema for height 0 y The atom p v where v denotes the value of process p will be used to refer to either a c atom or an f atom An atom u or its negation gt u are referred to as literals Negation of will be often written as 4 E g holding height 0 4 20 Definition 2 1 An action description of H is a collection of statements of the form lo if Ed 2 1 Ge causes lg if l ln 2 2 impossible a if l ln 2 3 where a and a are elementary and arbitrary actions respectively and l s are literals of H S G A The ly s are called the heads of the statements 2 1 and 2 2 The set 11 lu of literals is referred to as the body of the statements 2 1 2 2 and 2 3 Please note that literals constructed from f atoms of the form end y will not be allowed in the heads of statements of H A statement of the form 2 1 is called a state constraint It guarantees that any state satifying l l also satisfies l A dynamic causal law 2 2 says if an action a were executed in a state sq satisfying literals l1 ln then any successor state sy would satisfy l An executability condition 2 3 states that action a cannot 10 be executed in a state satisfying l If n 0 then if is dropped from 2 1 2 2 2 3 Example 2 1 Let us now construct an action description AD describing the transition diagram from Fi
48. n of H and F is a set of observations we will construct the logic program ao D by mapping statements of D into rules of A Prolog ao D contains two parts The first part contains declarations for actions and processes and the second part contains translations for the statements of H and the observations in I 3 1 DECLARATIONS Let us look at a general way of declaring actions and processes action action name action type process process name process type 19 actionname and action_type are non numeric constants denoting the name of an action and its type respectively Similarly process_name and process type are non numeric constants denoting the name of a process and its type respectively For instance in Example 2 1 the actions and processes are declared as follows action drop agent action catch agent process height continuous process holding fluent Now let us see how the range of a process is declared There are a couple of wavs of doing this The range of height from Example 2 1 is the set of non negative real numbers In terms of logic programming this means infinite groundings Therefore we made a compromise and chose integers ranging from 0 to 50 values 0 50 range height Y values Y holding is a boolean fluent Therefore we write range holding true range holding false Suppose we have a switch that can be set in three different positions the range of the process s
49. nd end Walk x y and the process of walking from z to y repre sented by relational fluent walking z y s start Walk z y causes the fluent to become true end Walk z y causes it to become false With this device of instantaneous start and end actions arbitarily complex concurrency can be represented For example startWalk A B startChewGum endChewGum startSing endW alk A B is the sequence of actions beginning with simultaneously starting to walk and starting to chew followed by simultaneouly ending to chew and starting to sing followed by ending to walk at which time the singing process is still going on Since we assume that actions of H are instantaneous we adopt Reiter s ap proach to model actions with durations and delayed effects The only difference is that the term process refers to both fluents and continuous processes Reiter adds explicit representation for time to situation calculus which allows 63 to specify the exact times or a range of times at which actions in a world history must occur The temporal argument is added to all instantaneous actions denoting the actual time at which an action occurs For example bounce ball wall 7 3 is the instantaneous action of ball bouncing on wall at time 7 3 Here time refers to global time unlike our approach where local time is used New function symbols are introduced in the language to handle the temporal argument A new function symbol time action real
50. nous are allowed agent actions are performed by an agent and exogenous actions performed by nature Processes from F are called fluents while those from C are referred to as continuous processes Elements of P F and C will be denoted by possibly indexed letters p s ks and c s respectively F contains a special functional fluent end that maps to A end will be used to denote the end time of a state We assume that for every continous process c C F contains two special fluents c 0 and c end For example the fluents height 0 and height end corresponding to height Each process p P will be associated with a set range p of objects referred to as the range of p E g range height R Atoms of H S G A are divided into regular atoms c atoms and f atoms e regular atoms are defined as usual from symbols belonging to neither A nor P E g mother X Y sqrt X Y e c atoms are of the form c a where range c range a E g height 0 height fo Y T height fo 50 T Note that is strictly a function of time Therefore any variable occurring in a c atom other than T is grounded Eg height fo Y T is a schema for height AT fo y T where y is a constant height 0 is a schema for height AT O where AT 0 denotes the constant function 0 e f atoms are of the form k y where y range k If k is boolean i e rangc k T 1 then amp T and k L will be written simply as X and ak respective
51. obal time 0 and has no direct effect on the value of height at O This means that the value of height at the end of sy will be preserved at time 0 of s Therefore So N s height 0 50 The application of Cn Z to E drop U so N s1 gives the set Q holding height 0 50 height f 50 T where Z contains the state constraints 1 8 and 1 9 The set Q will not represent the state s unless end is defined Let us suppose that s1 end 2 Therefore we get s end 2 holding height 0 50 height end 30 height f 50 T Please note that only atoms are shown here 2 3 SPECIFYING HISTORY In addition to the action description the agent s knowledge base may contain the domain s recorded history observations made by the agent together with a record of its own actions 16 The recorded history defines a collection of paths in the diagram which from the standpoint of the agent can be interpreted as the system s possible pasts If the agent s knowledge is complete c g it has complete information about the initial state and the occurrences of actions and the system s actions are deterministic then there is only one such path The Recorded history Cn of a system up to a current moment n is a collection of observations that is statements of the form obs v p t i hpd a t i where is an integer from the interval 0 n and time point t A is an index of
52. on 4 4 The process out flow rate is defined by the state constraint out flow rate fs N T if volume 0 Y 4 12 inflow_rate N which says that in any state s out flow rate is defined by the function fQ N T where is the volume at time 0 and N is the inflow rate The definition of f is obtained by rewriting the equation 4 2 In equation 4 2 the height of water level h is obtained by dividing the volume of water in the tank by the length and breadth of the tank For example if the length and breadth of the tank are 3 and 4 meters respectively and the volume of water in the tank is 36 cubic meters then the height of water level is 3 meters Therefore h is substituted by f3 Y N 7 b in the definition of fa Let a be a mapping from action description AD into rules of A prolog a ADz contains the following rules 36 Statement 1 5 is translated as val truc opcn O 1 1 o turn open T 1 Statement 4 6 is translated as o turn open T I val true open T I Statement 4 7 is translated as val false open 0 I 1 o turn close T 1 And 4 8 is translated as o turn close T I val false open T I Statement 4 9 is translated as val 3 in flow _rate T I val true open T 1 And 4 10 is translated as val 0 in flow rate T I val false open T I 4 14 4 15 4 16 4 17 4 18 Statement 4 11 contains a complex r
53. ounce we treat it as a fluent The range velocity is the set of real numbers and the rangelposition is the set of non negative real numbers Let G contain the function Yo if T 0 fz90 V T fo Yo V T 1 V if T gt 0 where 1o range position and V range velocity On hitting a wall the ball changes direction This is defined by the causal law bounce W causes velocity V if velocity V 2 4 Statement 2 4 says that if the ball moving with velocity V bounces against the wall W at time end in a state s then its new velocity is V in any successor state of s position will be defined by the state constraint position fo Yo V T if position 0 Yo 2 5 velocity V Statement 2 5 says that position is defined by Newtonian equations in any state The occurrence times of the bounce action is determined by Newtonian equations One way to represent such an action is to write statements called action triggers that 12 include these Newtonian equations In gencral action triggers describe the effects of processes or actions on other actions We will not address the issue of how to write triggers in this thesis because it is not the purpose of this thesis Our future work may involve extending language H to include triggers 2 2 SEMANTICS The semantics of process description language H is similar to the semantics of action language B given by McCain and Turner 10 11 An action description AD of H
54. rately needed funding Thank you for giving me an opportunity I am glad that I will be one of your first students to graduate I am looking forward to working with you in future research projects And to all my friends at Texas Tech University a big thank you for checring me up whenever 1 am feeling down Ricardo you are my best friend ever Whether it is working with you or playing with vou or just hanging out I enjoy every bit of it Thank you for being there whenever I needed you A big thanks to Sunil and all my ex roommates for bearing with me Sunil we had a great time as roommates I will never forget that I would like to thank all the KR lab members Each and everyone has con tributed in some way or an other towards this thesis Its nice to be part of a very active and smart group of researchers I enjoy working with you all I would like to thank the faculty and staff of computer science department for their support and cooperation Finally I would like to thank NASA Johnson space center for funding our research projects ili TABLE OF CONTENTS ACKNOWLEDGEMENTS TEE ABSTRACT ee oe iti ae LIST OF FIGURES 1 2 INTRODUCTION EA OE HEES SYNTAX AND SEMANTIESE DERS Es 21 SYNTAX SS SS 22 SEMANTICS BEE N 2 3 SPECIFYING HISTORY TRANSLATION INTO LOGIC PROGRAM 3 1 DECLARATIONS 32 GENERAL TRANSLATIONS 3 3 DOMAIN INDEPENDENT AXIOMS Oe eases 34 EXAMPLE TRANSLATIONS EXAM
55. ring Rules In AAAI Spring 2003 Symposium 2003 3 C Baral and M Gelfond Reasoning agents in dynamic domains In Minker J ed Logic Based AI Kluwer Academic publishers 2000 257 279 C Baral T Son and L Tuan A transition function based characterization of actions with delayed and continuous effects In Proceedings of KR 02 pages 291 302 M Gelfond and V Lifschitz The stable model semantics for logic programming In Logic Programming Proceedings of the Fifth International Conference and Symposium 1988 pp 1070 1080 M Gelfond and V Lifschitz Action Languages In Electronic Transactions on Artificial Intelligence 3 6 1998 M Gelfond and R Watson On Methodology of Representing Knowledge in Dynamic Domains In Proceedings of the 1998 ARO ONR NSF DARPA Mon terey Workshop on Engineering Automation for Computer Based Systems pp 57 66 1999 _ V Lifschitz Two components of an action language In Annals of Mathematics and Artificial Intelligence Vol 21 1997 pp 305 320 _ V Lifschitz Action languages Answer Sets and planning In The Logic Pro gramming Paradigm a 25 year perspective 357 373 Springer Verlag 1999 GO H 10 11 13 14 15 16 Norman McCain and Hudson Turner A causal theory of ramifications and qualifications In Proceedings of IICAI 95 pages 1978 1984 1995 Norman McCain and Hudson Turner Causal theories of action and change In Proceedings o
56. s is introduced time a de notes the time of occurrence of action a For example time bounce ball wall 7 3 7 3 Another function symbol start situation reals is introduced start s denotes the start time of situation s Therefore start do a s time a The start time of the initial situation so is arbitrary and may or may not be defined depending on the application In our approach the initial state starts at global time 0 In sitcalc every action takes time as one of its arguments and every fluent takes situation as one of its arguments In our approach the time and state parameters are not explicitly mentioned in the statements of H but it is implied that they are associated with every action and process The value of a fluent with the situation argument s is its value at the start time of s For example the functional fluent height s denotes height at the start time of s and height do a s denotes height at the start time of do a s 64 The language does not provide any features to compute the value of a fluent at a time other than the start time of a situation If there is an action that occurs at every time point then it is possible to define fluent values at every time point In language H we have a collection G of functions for defining continuous processes For instance in example 2 1 from chapter 2 we have functions fo and f for defining height Let us do an axiom by axiom comparision of situation c
57. s where a diagnosis could not be found We had some ideas on how to do a diagnosis in such circumstances One of the them was to introduce an external program called monitor that would interact with the A Prolog programs do most of the computations and help in diagnosis We would like to pursue this idea in the future Hybrid systems often involve control An agent acting in such a system should be reactive and deliberative A reactive agent is one that acts with respect to its sensor data A deliberative agent is one that acts with respect to its goals Example of a system that combines reactive and deliberative reasoning is the Mars rover If the Mars rover finds a rock that is interesting it would come up with a plan to reach the rock and execute it Hence it is deliberative in this case On its way to the rock it may come across obstacles The system converts its sensory data to motion vectors to avoid obstacles Hence it is reactive in this case Some times it replans depending on the sensor data in which case it combines reactive and deliberative reasoning In this thesis we have not addressed how to combine reactive and deliberative reasoning We would like to address this issue in the future 83 REFERENCES M Balduccini and M Gelfond Diagnostic reasoning with A Prolog In Journal of Theory and Practice of Logic Programming TPLP 3 4 5 425 461 Jul 2003 2 M Balduccini and M Gelfond Logic Programs with Consistency Resto
58. ss drop t s holding s A height s 0 poss catch t s sholding s Successor state axioms define the value of a relational fluent or functional fluent in the successor situation resulting from performing an action in the current situation It has two parts The first part defines what action causes the fluent to have a new value in the successor situation The second part captures inertia It says that the fluent will retain its value from the current situation if the action had no effect on the fluent Let us define the fluents holding and height from Example 2 2 using successor state axioms of situation calculus holding do c s At catch t e V 6 1 holding s A St drop t c 66 sholding do c s 3t drop t c V 6 2 sholding s A a Sb calch t c height do c s h holding s Ah height s V 6 3 sholding s Ah height s 1 G lime c The concurrent action c in the above statements is a collection of simple actions that occur at the same time As you can see the successor state axiom for a fluent f provides the dual functionality of a dynamic causal law of H with f in the head and the inertia axiom for f in a single statement Note that we use state constraints to define height in Example 2 1 Consider the axiom 6 2 Suppose that in the initial situation S holding is true Now suppose that action drop occurs at global time O causing holding to be false in the resulting situat
59. t better looking output volume T I val volume T 1 range volume Y out flow ratc Y T D val Y outflow rate T 1 range out flow rate Y inflow_rate y T I val Y inflow rate T 1 range inflow _rate Y SMODELS directives to hide and show relations hide show inflow_rate T 1 volume Y T I out flow_rate Y T I 92 PERMISSION TO COPY In presenting this thesis in partial fulfillment of the requirements for a master s degree at Texas Tech University or Texas Tech University Health Sciences Center I agree that the Library and my major department shall make it freely available for research purposes Permission to copy this thesis for scholarly purposes may be granted by the Director of the Library or my major professor It is understood that any copying or publication of this thesis for financial gain shall not be allowed without my further written permission and that any user may be liable for copyright infringement Agree Permission is granted Student Signature Date Disagree Permission is not granted Student Signature Date
60. t order logic A state constraint will be written as A gt B where A and B are first order formulas The contrapositive B D 4 will also be true in this case For example the state constraint on z y s Aon 2 z 8s Dy z expresses a truth about the blocks world domain But the contrapositive is not necessarily true y zD 0n z y 8 V 7on z z s This shows that using classical implication for knowledge representation does not give expected results For this and other practical reasons situation calculus does not encourage the use of state constraints In situation calculus the axioms for representing actions and their effects presuppose that actions are deterministic Therefore the action theories contain deterministic actions only On the other hand action theories of H contain both deterministic and non deterministic actions 62 Sitcale requires that the initial situation be complete We do not have such re strictions for language H And the implementation in A Prolog is capable of handling incomplete initial situations In 14 Reiter introduced the term process in order to overcome the problems associated with concurrent execution of actions with durations Reiter conceives actions with duration as processes represented by relational fluents and introduces durationless actions that initiate and terminate these processes For example instead of the action walk z y we might have instantaneous ac tions start Walk x y a
61. t programming techniques is one of them In this approach the answer sets of an A prolog program encode possible plans These plans are generated by so called planning modules In our examples the planning module is often a simple choice rule Answer set planning does not require any specialized planning algorithms The reasoning mechanism used for planning is the same as the one used for deducing answer sets Let us now look at an example that involves planning Example 5 1 Consider a car moving along X axis with uniform velocity The domain consists of two actions start V and stop start V causes the car to move with 42 a velocity V and stop causes the velocity to be 0 position of the car changes continuously with time as long as velocity is not zero Let us construct an action description 1D3 describing the above domain The cor responding siguature 3 contains the actions slart V and stop continuous process position and fluents velocity position 0 and position end The range velocity is the set of real numbers and the range position is the set of non negative real numbers Let Gs contain the function a Yo if T 0 OV T BOSVT DEV if T gt 0 where Yo range position V range velocity and T is a variable for time The action description AD contains the following statements The effects of the action start V where V range velocity will given by the causal law start V causes velocity V
62. the trajectory For example i 5 denotes the step 5 of the trajectory reached after performing a sequence of 5 actions obs v p t i means that process p was observed to have value v at time t of step i hpd a t i means that action a was observed to have happened at time of step i Observations of the form obs y p 0 0 will refer to the initial state of the system Definition 2 6 A pair AD T where AD is an action decription of H and F is a set of observations is called a domain description 17 Definition 2 7 Given an action decription AD of H that describes a transition diagram TD AD and recorded history upto moment n a path so GO S1s ee G n k Sn in the TD AD is a model of P with respect to the domain description AD Da if for every i O lt i lt nandteEdA 1 a a hpd a t i ET 2 if obs v p t i E Fa then p vE s 18 CHAPTER 3 TRANSLATION INTO LOGIC PROGRAM In this chapter we will discuss the translation of a domain description written in language H into rules of an A Prolog program A Prolog is a language of logic programs under the answer set semantics 5 for representing agent s knowledge about the domain and formulating the agent s reasoning tasks Since we use SMODELS 12 to compute answer sets of the resulting A Prolog program the translation will comply with the syntax of the SMODELS inference engine Given a domain description D AD T where AD is an action descriptio
63. time and therefore actions are associated with time intervals of the form t ts where t amp are real numbers such that 0 lt t lt to Example 6 4 The action of driving a car for 10 units of time with velocity v will be represented as drive g 1o v As mentioned earlier language H adopts Reiter s approach for dealing with ac tions with durations and delayed effects For example the action drive in example 6 4 will be represented by the fluent driving and instantaneous actions start_drive v and end_drive start_drive v causes driving to be true and end_drive causes driving to be false Since the duration of drive is not captured in our representation we have to write a trigger for end_drive which says that end_drive will occur after 10 units of time since start_drive v was executed Similarly sitcalc will need triggers to characterize actions with fixed durations When actions do not have fixed durations ADC adopts Reiter s approach of using processes The start and end actions are treated as instantaneous actions which initiate and terminate processes Let us look at how actions with delayed effects are represented in languages ADC and H 76 Example 6 5 Consider a time bomb that explodes when the time left on its timer becomes zero In language ADC we will represent the action of setting a timer to x units of time as sef_timer x This action canses the bomb to explode which is represented by the fluent c rp
64. tion of the units of time in our domain For computability reasons we assign local time to states Therefore the start time of every state s is 0 and the end time of s is the time since the start of s till the occurrence of an action terminating s For example in Figure 1 2 the action drop occurs after a time lapse of 0 units since the start of state so Therefore the end time of sg is 0 The action catch occurs after a time lapse of 2 units since the start of state s Therefore the end time of s is 2 The state sz in Figure 1 2 has the interval 0 5 associated with it This interval was chosen randomly from an arbitrary collection of intervals of the form 0 n where n 2 0 Therefore any of the intervals 0 0 or 0 1 or 0 2 and so on could have been associated with ss In other words performing catch leads to an infinite collection of states which differ from each other in their durations The common feature among all these states is that height is defined by fo 30 7 and holding is true We do not allow the interval 0 co for any state We assume that every state is associated with two symbols 0 and end The constant 0 denotes the start time of the state and the symbol end denotes the end time of the state We will give an accurate definition of end when we discuss the syntax of the language We assume that there is a global clock which is a function that maps every local time point into global time Figure 1 3 shows this mappin
65. us effects 6 1 SITUATION CALCULUS In this section we will compare language H with situation calculus Situation calculus was introduced by John McCarthy in 1963 as a language for representing actions and their effects But it was Reiter who enhanced situation calculus with fea tures like time concurrency and natural actions to be able to model hybrid systems Situation calculus or sitcalc for short uses an approach based on first order logic for modeling dynamical systems The statements of the language are formulas of first order logic We on the other hand use an action language logic programming approach to modeling dynamical systems Situation calculus does not use transition function based semantics to char acterize actions By transition function based semantics we mean the approach in which the world is viewed as a dynamical system represented by a transition diagram 60 whose nodes correspond to possible physical states of the world and whose arcs are labeled by actions Situation calculus uses the term situation to denote a possible world history A situation is a finite sequence of actions An initial situation denotes an empty sequence of actions In 14 Reiter points out the difference between the terms situation and state as a State is a snapshot of the world while situation is a finite sequence of actions A state is a collection of fluents that hold in a situation Two states are the same if they assign the same tr
66. us action s The Figure 5 1 summarizes the interaction between monitor and agent actuators environment monitor Figure 5 1 Architecture of an agent in a hybrid domain 56 The labeled arcs denote the following 1 The agent inputs initial values and functions associated with processes to the monitor 2 Monitor informs the agent about discrepancics actions triggered in the envi ronment initial situation etc 3 Monitor observes the environment Monitor records observations 5 The agent sends messages to the actuators to perform actions 6 The actuators perform actions in the environment Finally we say that with the help of monitor we will be able to find an explanation for the inconsistency in Example 5 3 overcome computational problems and improve efficiency considerably There are still some pending issues such as grounding in SMODELS which can be overcome by delayed grounding Example 5 4 Now let us see an example in which the monitor detects inconsistency and reports it to the agent and the agent uses answer set programming techniques to find out an explanation for inconsistency We will use the water tank example again Consider the recorded history l consisting of 57 obs 3 in flow ratc 0 0 obs 25 volume 0 0 obs false broken 0 0 obs truc open 0 0 Suppose that the monitor observes that in flow rate is 0 at time 3 of step 0 But the predicted value is 3 Since there
67. uth values to all the flucnts Two situations are the same iff they result from the same sequence of actions applied to the initial situation Two situations may be different yet assign the same truth values to the fluents Situations do not repeat while states can repeat E g Consider the blocks world domain Let move a b move c a denote a situation s resulting from performing the action move a b followed by move c a A state st corresponding to the situation s will contain the fluents on a b and on c a Let us talk about some situation calculus terminology The symbol do a s denotes a successor situation to s resulting from performing action a in situation s Relations whose truth values vary from situation to situation are called relational fluents For example on z y s denotes that block z is on y in situation s Functions whose values vary from situation to situation are called functional fluents For exam 61 ple height s denotes the height of an object in situation s Since the language is based on first order logic the full set of quantifiers connectives and logical symbols are used making the language powerful and expressive But there are some limitations Situation calculus does not encourage the use of state constraints because they are a source of deep theoretical and practical difficulties in modeling dynamical systems Let us understand why We know that the statements of the language are formulas of firs
68. vely Now let us look us at the causal laws The effects of the action furn open will be given by the causal law turn open causes open 4 5 which says that opening the faucet at time end in a state s causes open to be true in any successor state of s The executability condition will have the form impossible turn open if open 4 6 which says that it is not possible to open the faucet at time end in a state s if it is already open The effects of the action turn close are given by the causal law turn close causes open 4 7 which says that closing the faucet at time end in a state s causes open to be false in any successor state of s The executability condition will have the form impossible turn close if open 4 8 which says that it is not possible to close the faucet at time end in a state s if it is already closed The fluent in flow rate is defined by the state constraints inflow_rate 3 if open 4 9 35 which says that in any state s in flow rate is 3 when the faucet is open and mflow rate 0 if open 4 10 which says that in any state s inflow_rate is O when the faucet is closed The process volume is defined by the state constraint volume f3 N T if volume 0 Y 4 11 inflow_rate N which says that in any state s volume is defined by the function f3 Y N T where Y is volume at time 0 and V is the inflow rate The definition of f3 is obtained by rewriting equati
69. was obtained when local time was mapped into global time Additional rules were added to the translated program in order to do this mapping We will not talk about these rules in this thesis process_name Value Global time out flow_rate 6 0 volume 25 0 inflow rate changed 0 3 0 out flow rate 6 1 volume 28 1 in flow rate 3 1 out flow rate 7 2 volume 31 2 in flow rate 3 2 out flow rate 7 3 volume 33 3 in flow rate changed 3 0 3 40 out flow rate 6 4 volume 26 4 inflow rate 0 4 out flow_rate 5 5 volume 20 5 inflow rate 0 5 out flow rate d 6 volume 15 6 inflow rate 0 6 outflow rate 4 7 volume l1 7 inflow rate 0 7 out flow rate 3 8 volume 7 8 inflow rate 0 8 out flow_rate 2 9 volume 4 9 in flow_rate 0 9 As we can see in flow rate is not uniquely defined at global time 0 and 3 It changes from 0 to 3 at global time O and from 3 to 0 at global time 3 41 CHAPTER 5 PLANNING AND DIAGNOSIS In this chapter we will look at some examples on how to do planning and diagnosis in a hybrid domain The existing theories for planning and diagnosis can be applied to hybrid domains 5 1 PLANNING The ability to plan is an important characteristic of an agent A plan is a sequence of actions that satisfies the agent s goal By goal we mean a finite set of literals of H the agent wants to make true A planning problem can be solved in different ways Answer se
70. will not be part of ADe When we compare both representations the reader might observe that there are no time intervals associated with actions of H Instead the time intervals are associated with the states of the transition diagram as in Figure 1 2 ADC contains the following propositions to characterize the effects of actions executable aif Ci Ck 6 4 a needs 7 Tm 6 5 a causes f valf f fi fn t from t to te 6 6 a contributes valf f fi fn t to f from t to t 6 7 a initiates p from ts 6 8 78 a terminales p al ty 6 9 p is associated with f valf f hy fn D 6 10 p is associated with f e val f E Fis fr 6 11 When we compare these propositions with the statements of H we see that every proposition except for 6 7 has a counterpart in H The cxccutablity conditions of H are counterparts of the propositions 6 4 and 6 5 The dynamic causal laws of H without the preconditions are counterparts of the propositions 6 6 6 8 and 6 9 Propositions 6 10 and 6 11 contain functions for evaluating f The state constraints of H with empty bodies can be viewed as counterparts of these proposi tions For example height fo 50 T The version of ADC presented in 4 does have conditional effects and state constraints The proposition 6 7 affects the value of f at t by contributing an increase specified by val f f fi fn t during the interval 1 t2 Let us look at an ex
71. witch position is declared as vange suwiteh position low range switch position medium range swilch position high In order to talk about the values of processes and occurrences of actions we have to consider the time and step parameters Integers from some interval 0 n will be used to denote the step of a trajectory I s will be used as variables for step Now every step has a duration associated with it Therefore integers from some interval 0 m will be used to denote the time points of every step In this case m will be the maximum allowed duration for any step T s will be used as variables for time Therefore we write step 0 n time 0 m Assume that n and m are sufficiently large for our applications Then we add the rules domain step I I1 domain time T T1 T2 for declaring the variables 7 71 T T1 and T2 in the language of SMODELS The first domain declaration asserts that the variables and 1 should get their domain from the literal step 3 2 GENERAL TRANSLATIONS Let us look at a general translation of an action description of H into rules of A prolog If a is an elementary action occurring in a statement that is being translated it is translated as ola T I which is read as action a occurs at time T of step I If a is a compound action then for each elementary action a a we write o ae T I If is a literal of H occurring in the any part of the statement that is be

Download Pdf Manuals

Related Search

31295019600575

31295019600575

Contents

Download Pdf Manuals

Related Search

Related Contents