Programming Methodology Date: Fri, 21 Apr 2000 From: Vladimir Lifschitz To: TAG The program of the recent workshop on nonmonotonic reasoning (NMR-2000) included a tutorial on answer set programming by Ilkka Niemelae. He talked, among other things, about the methodology of programming in smodels. This was discussed by other speakers also. On the basis of these discussions, I'd like to propose a specific way to organize smodels input files. An smodels input file consists of 5 parts. First we define the domain predicates. This part of the program has a unique answer set. It is followed by a group of rules that generate a "search space"--a set of potential solutions. The first two parts of the program together have usually many answer sets, a lot more than the whole program. The third part defines new atoms in terms of the atoms occurring in the first two parts. Adding this part doesn't change the number of answer sets, but, generally, it makes every answer set bigger by adding some new atoms to it. The next part consists of constraints; its role is to weed out the elements of the search space that do not represent solutions. Adding this part removes some answer sets but does not change those that are left in. Finally, we specify which elements of each answer set should be displayed and which should be "hidden." An example is appended below. Please tell me what you think. -------- % File 'hamiltonian': Computing Hamiltonian cycles in a directed graph. % Command line: 'lparse -n 0 < hamiltonian | smodels'. % DOMAINS % There are two domain predicates: node/1 and edge/2. Their definitions % describe the graph whose Hamiltonian cycles we want to find. node(0..5). edge(0,1). edge(1,2). edge(2,0). edge(3,4). edge(4,5). edge(5,3). edge(4,0). edge(2,5). % GENERATE % A subset of edges belongs to the search space if it is a union of % disjoint cycles. 1 {in(X,Y) : edge(X,Y)} 1 :- node(X). 1 {in(X,Y) : edge(X,Y)} 1 :- node(Y). % DEFINE % The auxiliary predicate reachable/1 expresses reachability from node 0. reachable(X) :- node(X), in(0,X). reachable(Y) :- node(X), node(Y), reachable(X), in(X,Y). % TEST % Using reachable/1 we state a constraint that weeds out all elements of % the search space other than Hamiltonian cycles. :- not reachable(X), node(X). % DISPLAY % The only predicate to be displayed is in/2. hide node(X). hide edge(X,Y). hide reachable(X). ======= Date: Tue, 9 May 2000 From: Michael Gelfond To: TAG This is a (somewhat long) comment on Vladimir's note on methodology of programming in SMODELS. I find methodology a very important subject which is very rarely discussed. So I'll be really interested in your comments. I was somewhat surprised by Vladimir's proposal. I do not seem to program in the way he described. I do not normally start program development thinking about a particular inference engine like SMODELS, CCALC or DLV. Instead I program in a declarative language A-Prolog (Answer set Prolog). Theoretically, the resulting ``knowledge structure'' can be used to answer different types of queries (which may determine the type of engine to use). My first goal is to divide my knowledge in modules (normally located in different files). Often some of the modules I need for a particular task are already implemented so I can just use them in the new context. I often view modules as functions which take as an input (complete) sets of literals over some signature and output (one or more) sets of output literals. Let me illustrate this by example of a simple action theory. (Do not take me too seriously, I just copied it from some of my files) In this case the design is centered around actions, which is close to traditional notion of a procedure. Other choices are also possible. That is what I had in my file (with some comments of course): %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% A module describing an action 'a' has a header (signature) consisting of statements: 1. action(a). 2. Complete list of fluents relevant to 'a': rel_fluent(f,a). ... This info is needed to combine this module with other modules. The body of the action module consists of (a) A complete list of executability conditions (for 'a' to be executable 'c' must have value 'v') in a form of constraints: :- occurs_at(a,1,t), holds_at(c,v1,t),v1 =/= v. ... (If second parameter in 'occurs' is 1 then 'a' occurs at 't', if it is 0 then 'a' does not.) (b) Complete list of the dynamic causal laws. (Dynamic law 'd' says that execution of 'a' in any state in which fluents p1,...,pn have values v1,...,vn causes fluent 'f' to take on value 'v'.) dynamic_law(a,d). effect_of(f,val,d). precond_of(p1,v1,d). ... precond_of(pn,vn,d). ... (I prefer this form since it is slightly more elaboration tolerant) (c) The effect axiom: holds_at(F,T+1,V) :- dynamic_law(A.D), occurs_at(A,1,T), effect_of(F,V,D), not l_fail(D,T). l_fail(D,T) :- dynamic_law(A,D), precond_of(P,V,D), not holds_at(P,V,T). (d) The inertia axioms: Inertia 1: Normally fluents do not change. holds_at(F,1,T+1) :- holds_at(F,1,T), not holds_at(F,0,T+1). holds_at(F,0,T+1) :- holds_at(F,0,T), not holds_at(F,1,T+1). Inertia 2: Normally, actions do not occur. occurs(A,0,T) :- not occurs(A,1,T). (e) Complete list of state constraints of the form: holds_at(F,V,T) :- holds_at(F1,V1,T),...,holds_at(Fn,Vn,T). ... If time t is fixed, this module can be viewed as a mapping which takes as an input a complete description of a domain's state at time 't' (given in terms of atoms formed by holds_at) and a statement occurs_at(a,1,t) and returns possible successor states in which the domain can move on 'a'. Each such state is given by a set of atoms {holds_at(f,v,t+1)} from some answer set of the corresponding program. (If t is fixed then variable T is constraints ranges over t. t+1) p.s. Actually, statements (c) and (d) are common to all action modules but I ignore this by now. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%55%%%%%%%%%%%%%%%%%%%%%%%%%%%% For instance a (parameterized) action 'agent A buys object O' may be described as follows. (This is of course a simplification. Finding a more complete description may be interesting though.) HEADER: action(buy(A,O)) :- object(O), agent(A). rel_fluent(buy(A,O),has(A,O)) :- object(O), agent(A). rel_fluent(buy(A,O),has(A,money)) :- agent(A). rel_fluent(buy(A,O),available_at(O,L)) :- object(O), location(L). rel_fluent(buy(A,O),is_at(A,L)) :- agent(A), location(L). rel_fluent(buy(A,O),right_loc(A,O)) :- agent(A), object(O). EXECUTABILITY CONDITIONS: :- occurs_at(buy(A,O),1,t), holds_at(has(A,money),0,t). :- occurs_at(buy(A,O),1,t), holds_at(at(A,L),1,t), holds_at(at(O,L),0,t). etc. DYNAMIC LAW: dynamic_law(buy(A,O), d1(A,O)) :- object(O), agent(A). effect_of(has(A,O),1,d1(A,O)) :- object(O), agent(A). STATE CONSTRAINT: holds_at(at(X,L),0,t+1) :- holds_at(at(X,L1),1,t+1), L =\= L1. etc PLUS statements (c) and (d). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% The point of this long exercise is to show that for the problem is to find proper templates (or patterns), understand how to instantiate them into particular modules, combine these modules into more complex knowledge bases (e.g. but putting different action together), etc. This problems are typical for all types of programming and we should address them and use as much as possible from what is already known and understood. Now if I decide to use this knowledge for planning I can construct a planning module describing ``the search space''. But I can use the same knowledge base to check correctness of plans, or to do diagnosis, or many other things. If I decide to use SMODELS I have to add types, etc. I do not know if I need to eliminate function symbols to use DLV. (They used to be prohibited). Similarly for other systems. (The fact that I avoided classical negation shows that I really was thinking about running this on SMODELS but I shouldn't have done it. ) I think that inability to construct 'inference system' independent knowledge bases is a substantial drawback of current 'answer set programming'. It is interesting to see how this view can be reconciled with the one mentioned by Vladimir. Should it be? Are we talking about different problems? Any comments will be appreciated. ======== Date: Thu, 1 Jun 2000 From: Vladimir Lifschitz To: Michael Gelfond Thank you for your reply to my message about organizing smodels input files. In my new paper, available at http://www.cs.utexas.edu/users/vl/mypapers/asppg.ps , the idea of dividing an smodels file into sections is applied to two additional examples. I agree, it may be good to start program development by thinking in terms of answer sets in general, and not about a specific answer set solver. But it seems to me that most of what my message says about answer set programming does not really depend on the choice of smodels as the solver. No matter which system we use, we can distinguish between describing a set of potential solutions ("GENERATE"), constraining it to eliminate the potential solutions that are not solutions ("TEST") and defining useful predicates ("DEFINE"). For instance, in the action module that you write about, we can label part (a) by TEST and parts (b)-(e) by DEFINE. The "planning module" that you briefly mention will probably include some GENERATE rules that would designate arbitrary sequences of actions to be potential solutions and also TEST rules that would weed out the sequences of actions which don't achieve the given goal. The idea of dividing knowledge into modules and reusing them seems orthogonal to my proposal. I would try to further subdivide each module into GENERATE-DEFINE-TEST sections. I have a quesion about your example. In the discussion of action modules, you mention the predicate rel_fluent that is needed, you say, to combine modules with each other. Can you explain how this predicate would be used? ======== Date: Thu, 15 Jun 2000 From: Michael Gelfond To: Vladimir Lifschitz I'll have to do some slight changes in the previous formalization. I modified it for my purpose last time but not accurately enough. I include below the module ``buy'' which differs from the previous one in two ways: 1. In the definition of relevant fluents the first parameter ``buy(A,O)'' is replaced by the module name ``buy''. 2. Quantifiers over fluents are restricted to relevant fluents. This is the key idea of this device but unfortunately in my previous message it was deleted together with other types needed for SMODELS. (It maybe a good idea to also limit action variables, etc to those relevant to the module but this was meant to be a simple example. ) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% module(buy): HEADER: action(buy(A,O)) :- object(O), agent(A). rel_fluent(buy,has(A,O)) :- object(O), agent(A). rel_fluent(buy,has(A,money)) :- agent(A). rel_fluent(buy,at(O,L)) :- object(O), location(L). rel_fluent(buy,at(A,L)) :- agent(A), location(L). EXECUTABILITY CONDITIONS: :- occurs_at(buy(A,O),1,T), holds_at(has(A,money),0,T). :- occurs_at(buy(A,O),1,t), holds_at(at(A,L),1,t), holds_at(at(O,L),0,t). etc. DYNAMIC LAW: dynamic_law(buy(A,O), d1(A,O)) :- object(O), agent(A). effect_of(has(A,O),1,d1(A,O)) :- object(O), agent(A). STATE CONSTRAINT: holds_at(at(X,L),0,T+1) :- holds_at(at(X,L1),1,T+1), L =\= L1. etc EFFECT AXIOM: holds_at(F,T+1,V) :- rel_fluent(F), dynamic_law(A.D), occurs_at(A,1,T), effect_of(F,V,D), not l_fail(D,T). l_fail(D,T) :- dynamic_law(A,D), precond_of(P,V,D), not holds_at(P,V,T). INERTIA AXIOMS Inertia 1: Normally fluents do not change. holds_at(F,1,T+1) :- rel_fluent(buy,F), holds_at(F,1,T), not holds_at(F,0,T+1). holds_at(F,0,T+1) :- rel_fluent(buy,F), holds_at(F,0,T), not holds_at(F,1,T+1). Inertia 2: Normally, actions do not occur. occurs(A,0,T) :- action(A), not occurs(A,1,T). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Now let us consider another object, say Jack, who is normally an unhappy person. Buying things makes him happy but only momentarily. This and other information about Jack can be collected in a module, say %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% module(jack): This module contains relevant fluents, say rel_fluent(j,happy(j)). rel_fluent(j,has(j,O)) :- object(O). (I am assuming here that all my modules share the same objects). The default is written as (d1) holds_at(happy(j),0,T) :- not holds_at(happy(j),1,T). The exception is: holds_at(happy(j),1,T+1) :- object(O), occurs_at(buy(j,O),1,T). To complete the module I'd like to import the module ``buy'' above. This can be done by just putting all the rules together. Notice that if the inertia in ``buy'' were not restricted to fluents relevant to this module such a combination would not be correct (default (d1) would interfere with the Inertia axiom producing unintended extensions). DOES THIS ANSWER THE QUESTION? ========= Date: Mon, 19 Jun 2000 From: Vladimir Lifschitz To: Michael Gelfond Thank you for your message explaining the use of the predicate rel_fluent. In your example, buying things makes Jack happy, but only momentarily; normally, he is unhappy. I see that the fluent happy(j) should be exempted from inertia, so that the presence of rel_fluent in holds_at(F,0,T+1) :- rel_fluent(buy,F), holds_at(F,0,T), not holds_at(F,1,T+1). is essential. But it seems to me that the same effect can be achieved by simpler means. I would write: holds_at(F,1,T+1) :- inertial(F), holds_at(F,1,T), not holds_at(F,0,T+1). holds_at(F,0,T) :- default_false(F), not holds_at(F,0,T). The use of the 2-place predicate rel_fluent instead of a small number of 1-place predicates (such as inertial and default_false) obscures the fact that there are very few useful types of propositional fluents, in terms of their default behavior. For instance, the ccalc standard file C.t identifies 6 useful subsorts of fluents: :- sorts fluent >> ( ( inertialFalseFluent; inertialTrueFluent ) >> inertialFluent ; ( defaultFalseFluent; defaultTrueFluent ) >> exogenousFluent ); and that seems to be more than enough. On the contrary, the number of modules can be very large. What are your thoughts about this? ========== Date: Tue, 20 Jun 2000 15:49:39 -0500 (CDT) From: Michael Gelfond To: Vladimir Lifschitz You are right. This example can be formalized using relations like ``inertial'' and ``default''. I am not sure that the arity of predicates matter though. Does it? A few comments: 1. As far as I remember I used ``rel_fluent'' just to draw the students attention to the need to hide information inside modules. If modules ``share'' some ``variables'' - for instance if a module Jack defines Jack's moods and a module ``friends'' contains default about happiness of talking to friends - then one may want to establish priorities between the modules or between rules in these modules. If modules define functions with disjoint output values then some simple theorems should allow to put them together. (In this context the use of ``fluents'' is not important. We can use rel(fluent,f). rel(action,a). etc. ) I do believe that a good language allowing modules, information hiding, inheritance, etc is necessary. Unfortunately my attempts to understand how things like these are done in logic programming and/or object oriented languages failed because I either do not understand what I read or do not like it. Does anyone have anything to say on the subject? Or have some suggestion on the reading material? 2. I am not sure if the use of CCALC sorts in the form :- sorts fluent >> ( ( inertialFalseFluent; inertialTrueFluent ) >> inertialFluent ; ( defaultFalseFluent; defaultTrueFluent ) >> exogenousFluent ); is always a good idea. First we of course are not limited to propositional fluents. But even if fluents are propositional we may want to have a little more. Let me modify my previous example and formalize it in the style suggested last time. Maybe if you, and/or some other people, care to formalize it differently we can gain some insight in KR. EXAMPLE: ------------------------------------------------------------------------- Winter is normally a bad time for Jack. He is unhappy most of the time. Of course the situation is quite different when he spends winter in London. In this city his moods normally open to the outside influences and do not change without reason. It is of course unless he spends winter with Mary. In this case his moods change erratically and are completely unpredictable. (As before) buying things always makes him happy, but only momentarily, etc. -------------------------------------------------------------------------- In other words Jack's feeling are more refined, i.e. depend on a bigger number of factors and can be described by a collection of defaults with exceptions. First notice that Jack's happiness is false by default in a winter and true by default in, say, a summer. This means that your types should be defined in a language more complex than just atoms. I opt for allowing to define types by arbitrary logic programs. (I think you mentioned that something like this as available in CCALC now. Is that right?). The second complication is that the ``winter unhappiness'' default can be defeated by another default which says that, in London, Jack's moods are inertial. There are exceptions to that too, etc. Instead of defining when the fluent is inertial and when it is not I would probably prefer to write something like this: (This is of course programming on the fly so do not take it too seriously) module(jack): Relevant fluents, say rel_fluent(j,happy(j)). (Other fluents and actions are going to be imported from other modules). The first default is written as (d1) holds_at(happy(j),0,T) :- holds_at(winter,1,T), not ab(d1(T)), not holds_at(happy(j),1,T). The first exception to d1 is, as before, holds_at(happy(j),1,T+1) :- object(O), occurs_at(buy(j,O),1,T). The second exception to d1 itself has a form of default, (d2) holds_at(happy(j),V,T+1) :- boolean(V),boolean(V'), contrary(V,V'), holds_at(in(j,london),1,T), holds_at(in(j,london),1,T+1), not ab(d2(T,V)), holds_at(happy(j),V,T), not holds_at(happy(j),V',T). which is just a form of inertia. d2 has a priority over d1 which I may express as ab(d1(T)) :- holds_at(in(j,london),1,T), holds_at(in(j,london),1,T+1). (I am assuming complete information about Jack's location). If Jack is with Mary I'd like to stop both defaults which I can do by writing ab(d1(T)) :- holds_at(together(j,m),1,T). ab(d2(T,V)) :- boolean(V), holds_at(together(j,m),1,T), I can combine it with ``buying module as before'' and with modules defining locations and being together with other people, etc. Notice that if Jack were to buy something in London (with no Mary in sight) he would stay happy afterwards. If Mary is around he will be happy for one moment and after that his mood will be undefined again. Any comments? p.s. Another way to formalize this story is by using a ``second order'' language like the one we used with Son in our paper on prioritized defaults. Son, what is your opinion on that?