Choice Rules and the Belief-Based View of ASP, Part 4 ========= Date: 27 Dec 2010 From: Michael Gelfond To: Marc Denecker I had a chance to read the discussion (and your paper) again and think about it but I am still not sure I fully understand your criticisms of my view of ASP. I am happy though that we both agree that the USA advisor was developed using this view and this methodology --- this makes me more hopeful. It may be that the substantial part of the problem is simply the differences in our underlining scientific philosophies. You seem comfortable with the view which splits the world into objective and subjective parts -- "objective world" and the agent seem to be modeled separately. (This is more or less how Tarskian semantics does that) I am not comfortable with this view. For me an observing and acting agent is part of the world and I prefer this agent to be at the center of my model. I always viewed simplest programs this way. A program usually gets information from me (or, more generally, from the outside world), performs an appointed reasoning task, and acts on the outside world by printing the output, allocating memory for my use, starting a car, etc. I call such a program "an agent" and routinely ascribe to it some mental properties. For instance, if the reasoning tasks it performs are complex and lead to nontrivial behavior I call the program smart. It the program nicely adapts it behavior to changes in the environment I call it autonomous, etc. It is possible that I developed this view because in my first real programming work I dealt with a large control system for paper production and my first programming assignment was to figure out why some bulb didn't lit when it should have and to make it function properly. (I am sure there are some other reason). I do not see anything overly complex or wrong with this view but of course I realize that other people view it differently. But when you say: "in most ASP applications (including the USA-Advisor), the domain does not naturally involve epistemic agents" I can only object and say that to me it does. You write: "in the USA-Advisor, what WE know about that domain is "objective": it is about material stuff like pipes and valves and actions, and the effect and non-effect of actions. No introspection is involved so far." As I mentioned before it is not exactly true. We know effects of actions, etc but do not know, for instance, if the components of the system are broken. The USA Advisor will make some assumptions about it during its work. If in its interaction with the controllers the advisor is asked to find a plan to achieve a given goal, it will form a program consisting of system description, planning module, and CWA for components being O.K. in the initial state, call ASP solver and output the plan. So to plan the advisor will assume that the components are o.k. and that his plan will work. If the goal were to find an explanation of some unexpected observations the ASP advisor will instead assume that any component could have been originally broken and look for minimal explanation of that discrepancy. I like to describe this process as the advisor assuming that the components are fine, and using this assumption to find a possible plan. He believes that the plan will work but changes its mind after it obtains new information from the outside world. I agree that this view and this language is not necessary but it is very convenient for me. I love other people produce different ideas and different interpretations (but, of course, prefer to understand them). The uniformity is deadly and new points of view increase life. So my main goal in this discussion is to understand your methodology. But you seem to believe that the view I advocate is somehow erroneous. So I try to defend this view hoping that it will make it clearer. Let us look at your argument: One argument you use is Occum's razor. But as any razor it works both ways -- Why do I need to use different languages for knowledge representation (one with NAF as subjective and another with NAF as objective) when I can use one language? Or you say that this method is ad hoc. But I used this view from the beginning, was not forced to modify it, successfully expanded it to CR-Prolog and P-log, etc. I do not think this fits the definition of AD HOC. Another complaint is that what I am doing does not fit "the standard way" knowledge representation is understood. This may be true -- I am not sure who are the people who determine this standard meaning but certainly this will not be very important to me. I'd like to learn how to build thinking agents. agents need knowledge about the world and their own abilities, best representations depend on the way knowledge will be used, so operations on knowledge are fundamental part of KR, etc. Why is it a wrong view? The last part: let's forget about the problems of ASP-belief. I am still trying to understand ASP world. It seems to me that you have two requirements: 1. The knowledge should be objective (and therefore not defeasible?) 2. The knowledge should define a collection of possible worlds by which you seem to mean two valued Herbrand interpretations. Am I right? If so, why it is you want your interpretations to be two valued? What is the problem with having some p(a) undefined? Consider your example: "Bob is a minority student, John is not a minority student, Dave or Ann (or both) are minority students". I'd represent it simply as: minority_student(S) or -minority_student(S) minority_student(bob). -minority_student(john). :- -minority_student(dave),-minority_student(ann) As you can see the program does not contain NAF so problem with non-monotonicity is out. All answer sets are two valued. From my perspective it is a perfectly good ASP belief program which can also be viewed as ASP world program. This is another special case where the difference is not important (The first one being a program with no updates). Do you agree with this? If not, where do I go wrong? I am sorry for the prolonged discussion. I honestly trying to understand your concerns. But even I do not succeed I am sure other people had seen your arguments and will be sympathetic to them so your time has not been wasted. ========= Date: 12 Jan 2011 From: Marc Denecker To: Michael Gelfond Lets face it: this is a tough discussion but one that is on foundations of ASP and FO(.). It would be so great if we could finally settle a few things. > You seem comfortable with the view which splits the world into objective and subjective > parts -- "objective world" and the agent seem to be modeled separately. > (This is more or less how Tarskian semantics does that) > I am not comfortable with this view. For me an observing and acting agent is > part of the world and I prefer this agent to be at the center of my model. I agree that an observing and acting agent is part of the world. We certainly agree on the importance of knowledge base systems: systems like the USA-Advisor, storing knowledge, solving various problems with it, performing actions in the world, receiving new information and updating or revising its knowledge base. You call it the agent and it makes part of the world. There is no disagreement on that point. The disagreement is underlying the second part of your last sentence "I prefer this agent to be at the center of my world". The ASP "agent-centered" methodology turns each and every piece of human expert knowledge into an autoepistemic self-referential introspective statement referring to what the 'agent' believes or does not believe or has to believe. This point should be obvious to each person familiar with ASP theory. The knowledge of the agent is made up of all its ASP rules, and each ASP rule refers explicitly to what this knowledge is. E.g., Suppose we want to feed our agent with the information that: either Ann or Dave belong to minorities. In classical logic, Minority(Dave) <-> -Minority(Ann). In ASP there are several representations. One is: Minority(Dave) <- not Minority(Ann). Minority(Ann) <- not Minority(Dave). which means, e.g., for the first rule: If I (the system) does not believe that Ann is a minority, then I believe that Dave is a minority. Another method is by using disjunction: Minority(Dave) | Minority(Ann) <- which is to be understood as: I believe that Dave is a minority or I believe that Ann is a minority. We started here from a simple OBJECTIVE proposition. Here "objective" has the (standard) meaning that this proposition does not refer to what is known or unknown by some agent or to intentions, obligations, etc... (topics studied in modal logics). The proposition about Dave and Ann is objective, and the ASP agent-centered methodology changes its nature and turns it into a self-referential introspective statement. These introspective self-references are a by-product of the translation in ASP. The reference to the agents knowledge is an artifact of the ASP agent-centered methodology. The above phenomenon is systematic. In almost all applications (including the USA-Advisor), a good proportion of the human expert knowledge is bound to be objective (see below for more on that), and it is all transformed into self-referential introspective rules. You took a philosophical stand: that you dislike a separation between the objective world and what the agent knows and that you prefer an "agent-centered" representation. The arguments you gave are all arguments defending knowledge-based systems, and I agree with them. In practice, your agent-centered representation boils down to turning even the simplest statement into self-referential introspective rules. You have not given an argument what the advantage of this would be. It must not bother you. I on other hand find it very alarming. I'm currently writing a paper about autoepistemic self-referential introspective knowledge and I'm struck everyday by the tricky-ness and the complexity of that form of knowledge. The representation in ASP not only changes the nature of much human expert knowledge but it also seriously complicates it. It is part of the goal of KR to study human knowledge in order to develop languages and methodologies suitable to make accurate and natural representations. Therefore, to me, the mismatch between the human expert knowledge and its ASP representation is a disturbing scientific problem. I think that the consequences of this mismatch are currently not well understood in the ASP. But one is that many people now and in the future will simply refuse to use ASP, just for this reason. There are other consequences as well. They are not easy to show, especially not to pragmatists (no offense ;-) ) because indeed, ASP works! I wouldnt claim that I understand this very well but with what I understand, I guarantee that it is in the long term interest of the ASP community to reconsider this issue. A discussion of this is beyond the scope of this email -- it is too long already- but if you are interested, then lets explore this. > > I always viewed simplest programs this way. > A program usually gets information from me (or, more generally, from the outside world), > performs an appointed reasoning task, and acts on the outside world by > printing the output, allocating memory for my use, starting a car, etc. I call such a program > "an agent" and routinely ascribe to it some mental properties. > For instance, if the reasoning tasks it performs are complex and lead to > nontrivial behavior I call the program smart. It the program nicely adapts it behavior to changes > in the environment I call it autonomous, etc. > No disagreements here! > It is possible that I developed this view because in my first real programming work > I dealt with a large control system for paper production > and my first programming assignment was to figure out why some bulb didn't lit when > it should have and to make it function properly. > (I am sure there are some other reason). > > I do not see anything overly complex or wrong with this view but of course I realize > that other people view it differently. > No, there are no disagreements so far. > But when you say: > "in most ASP applications (including the USA-Advisor), > the domain does not naturally involve epistemic agents" > I can only object and say that to me it does. It is obvious that the ASP methodology turns each or nearly each objective proposition into a self-referential introspective statement. But in the above sentence and in earlier TAG emails, I actually make a much stronger claim, namely that in most ASP applications, the underlying human expert knowledge consists ONLY of objective knowledge, and makes no natural reference to the epistemic state of the agent. Stated differently, the claim is that in most ASP applications, EVERY reference to the agents knowledge is an artifact of the ASP methodology. It is a claim, a hypothesis, it might be too strong. Lets see. Let me sketch my arguments. First of all, the claim does not universally hold. There are some example applications where ASP programs represent genuine autoepistemic introspective statements of the agent, and in which the self-reference in the program is not an artifact. An example from one of your papers is the knowledge base system maintaining information of students and which contains the introspective proposition that if the agent does not know the minority status of a student, the student is interviewed: interview(x) <- not minority(x), not -minority(x). I proposed an informal but useful criterion to recognize such programs. They are the programs of which an answer set consists of the literals believed by us, the ASP programmer who wrote the program, and which cannot be viewed as representations of possible worlds. I called such ASP programs ASP-belief programs. Whether this criterion is correct might be a point of discussion. Very few ASP programs are ASP-belief programs. I see two reasons for that: First, I think that inherently autoepistemic self-referential knowledge in real applications is rare (and that is a relief to me, given how complex this form of knowledge is). Second, I think that compared to autoepistemic logic or default logic, ASP is a poor language to express such autoepistemic statements, as shown in your 92 strong introspection paper. There it is shown that as soon as the minority database contains disjunctive information, e.g., Minority(Ann) or Minority(Dave), the above interview rule does not work anymore, and NAF is to be replaced by a new strong introspective operator. (The problem was recalled in my TAG email of 8 Nov 2010). My guess is therefore that we agree on the latter point. As I understood it, your aim with ASP was to design a pragmatically useful sublogic of AEL and DL. Given the computational complexity of these two, you have given up on expressivity in favour of efficiency. That makes sense. There is of course a price to pay, as shown by the interview example in the presence of disjunctive knowledge, but fortunately such applications are rather rare. I couldnt agree more. As for the first assumption (that genuine self-referential statements are absent in most applications of ASP), you disagree, at least in complex applications such as the USA-Advisor (but perhaps not for graph coloring or hamiltonian path - confer your TAG email of 30 Nov 2010). I think I see your point. In the USA-Advisor, assumptions are made: closed world assumptions on data, default values, the inertia rule. In the tradition started by Reiter, McDermott and Doyle, you think of these assumptions as reflexive autoepistemic statements of the agent. So, you use reflexive autoepistemic statements to build elaboration tolerant representations of these types of common sense knowledge. I see the sense of this, but I disagree with the price to be paid: namely that every objective fact encoded in ASP turns into a complex and unnatural autoepistemic proposition. I've claimed that there is a very large class of ASP programs of which their answer sets can be naturally interpreted as Tarskian Herbrand interpretations representing possible states of the world. Such programs were called ASP-world programs. My idea is that for such programs, an alternative objective interpretation should exist. What could be the nature of this alternative interpretation? Certainly, it should involve nonmonotonic constructs which allow to build elaboration tolerant representations of assumptions of the above kind. In various places (e.g., our paper in your anniversary symposium) we have claimed that the concept of rule-based definitions is a suitable construct (I know, I'm predictable :-)). This view can be explained also in your terminology. There is an intuitive match between (formal) LP-functions and (informal) parametrized definitions. They both define some concepts in terms of other parameter concepts. All meaningful examples of LP-functions that I have seen in your papers were representations of definitions (if I am wrong then I would be glad to know). My claim is that ASP-world programs can be viewed as a set of FO axioms (the constraints) plus the union of a set of LP-functions plus Open World Declarations for all predicates that are defined in none of the LP-functions. The basics of this interpretation was worked out in: (although there is room for improvement) Mariën, Maarten; Gilis, David; Denecker, Marc. On the relation between ID-Logic and answer set programming, Logics in Artificial Intelligence, 9th European Conference, JELIA 2004, volume 3229, pages 108-120, 2004 > You write: > "in the USA-Advisor, what WE know about that domain is > "objective": it is about material stuff like pipes and valves and > actions, and the effect and non-effect of actions. No introspection is > involved so far." > As I mentioned before it is not exactly true. We know effects of actions, etc but do not know, for instance, > if the components of the system are broken. The USA Advisor will make some assumptions about it during its work. > If in its interaction with the controllers the advisor is asked to find a plan to achieve a given goal, > it will form a program consisting of system description, planning module, and CWA for components being O.K. > in the initial state, call ASP solver and output the plan. > So to plan the advisor will assume that the components are o.k. and that his plan will work. > If the goal were to find an explanation of some unexpected observations the ASP advisor will instead assume that > any component could have been originally broken and look for minimal explanation of that discrepancy. > I like to describe this process as the advisor assuming that the components are fine, and using this > assumption to find a possible plan. He believes that the plan will work but changes its mind after it > obtains new information from the outside world. I agree with all you say. Yet, I dont see how this contradicts with my idea that the USA-advisor is an ASP-world program. I think its answer sets can be interpreted as Tarskian Herbrand interpretations representing possible evolutions of the shuttle system. I think that all assumptions that are made in the USA-Advisor are expressed well (and of course equally elaboration tolerant) when interpreting the ASP program in the above described way -as the union of LP-functions each representing a definition, with constraints and open domain declarations. In line with this I think that the expert knowledge encoded in it is inherently about material stuff (valves, tubes, reservoirs, pressures, etc..) and does not need to involve self-reference to what the knowledge base agent knows. This view seems to be consistent with what your wrote about the USA-Advisor, as I mentioned in my email of 19 Nov 2010: + In the conclusion of the paper [1], it is written that: "It was interesting to notice that many fluents of the RCS domain had natural recursive definitions, easily expressible in A-Prolog." [1] Marcello Balduccini, Michael Gelfond, Monica Nogueira, and Richard Watson. Planning with the USA-Advisor. In 3rd International NASA Workshop on Planning and Scheduling for Space, Sep 2002. + In a post on TAG on 22 Oct 2010, you expressed that the USA-Advisor "was viewed by us as a collection of LP-functions -- or in current terminology collection of modules. LP function had a collection of input and output predicates and was viewed as a mapping from some domain -- set of collections of input literals -- to the set of collections of output literals". Combining both remarks seems to support my claim. Would you not agree? > I agree that this view and this language is not necessary but it is very convenient for me. > I love other people produce different ideas and different interpretations > (but, of course, prefer to understand them). The uniformity is deadly > and new points of view increase life. Sometimes uniformity is life-saving. At some stages of research, diversity is good. At later stages, reflection, synthesis and integration is good: taking the best from different approaches. That is what I hope I am doing. > But you seem to believe that the view I advocate is somehow erroneous. So I try to defend this view > hoping that it will make it clearer. > Let us look at your argument: > One argument you use is Occum's razor. But as any razor it works both ways -- Why do I need to use different > languages for knowledge representation (one with NAF as subjective and another with NAF as objective) > when I can use one language? Or you say that this method is ad hoc. But I used this view from the beginning, > was not forced to modify it, successfully expanded it to CR-Prolog and P-log, etc. I do not think this fits the definition > of AD HOC. What I mean with the ad hoc aspect of ASP is that it introduces complex self-references to propositions that do not contain them. Worse, these self-references cannot be avoided in ASP. > Another complaint is that what I am doing does not fit "the standard way" knowledge representation is understood. > This may be true -- I am not sure who are the people who determine this standard meaning but certainly this will > not be very important to me. I'd like to learn how to build thinking agents. agents need knowledge about the world and > their own abilities, best representations depend on the way knowledge will be used, so operations on knowledge are fundamental > part of KR, etc. Why is it a wrong view? I agree with your view on agents. I disagree with the way you feed knowledge in them. I think that the ASP-methodology makes it impossible to compare KR in ASP and FO. I think the incomparability of the ASP and FO methodologies is a real scientific problem. > The last part: let's forget about the problems of ASP-belief. I am still trying to understand ASP world. > It seems to me that you have two requirements: > 1. The knowledge should be objective (and therefore not defeasible?) > 2. The knowledge should define a collection of possible worlds by which you seem to mean > two valued Herbrand interpretations. Am I right? Yes. In fact, I think that (1) is a consequence of (2). > If so, why it is you want your interpretations to be two valued? What is the problem with having > some p(a) undefined? I don't think this is a relevant question in the context of our discussion so I prefer to delay this question. > Consider your example: > "Bob is a minority student, > John is not a minority student, > Dave or Ann (or both) are minority students". > I'd represent it simply as: > minority_student(S) or -minority_student(S) > minority_student(bob). > -minority_student(john). > :- -minority_student(dave),-minority_student(ann) > As you can see the program does not contain NAF so problem with non-monotonicity is out. > All answer sets are two valued. From my perspective it is a perfectly good ASP belief program > which can also be viewed as ASP world program. This is another special case where the difference > is not important (The first one being a program with no updates). > Do you agree with this? If not, where do I go wrong? No. Let us do the analysis. If a human agent (like me) is told the above problem, what literals does he believe to be true? I dont think there can be any doubt about this. It is: Bob is a minority student, John is not a minority student. The other literals are unknown. An ASP belief program is one such that its answer set(s) correspond to the set of believed literals of the human agent. So its answer set should be: {Minority(Bob), -Minority(John)} An ASP-world program is one such that its answer sets correspond to the possible worlds. What are the possible worlds of the informal specification? It depends on information that has not been explicitated: namely whether or not domain closure and unique names properties hold. Lets assume they do. Then there are obviously 3 possible worlds depending on the minority status of Ann and Dave. The answer sets of your ASP program are: {Minority(Bob), -Minority(John), Minority(Ann), -Minority(Dave) } {Minority(Bob), Minority(John), -Minority(Ann), Minority(Dave) } {Minority(Bob), Minority(John), Minority(Ann), Minority(Dave) } By forgetting about -Minority literals, we get three Herbrand interpretations that represent the three worlds that are possible according to the human agent. None represents the set of literals believed by the agent. So it is an ASP-world program, not an ASP-belief program. Now, lets verify my claim that this program has an alternative objective interpretation. * recall that in this view -minority_student/1 is a new predicate, whose interpretation I can choose freely, as long as it is disjunct with the minority relation in each possible world. I choose the obvious interpretation : -minority_student(x) means that x is not a minority. * minority_student(x) or -minority_student(x). This rule has two roles. It expresses the (tautological) property that "a person is a minority or is not a minority". Tautologies are not important. More importantly, such a disjunctive rule is also a standard way to open up the interpretation of the main predicate minority_student. I.e., it is declaration that the CWA should not be applied on the minority predicate. * minority_student(bob). -minority_student(john). In view of the fact that CWA should not be applied on minority_student, these atomic rules simply express two simple FO assertions that bob is a minority and john is not. * :- -minority_student(dave),-minority_student(ann) This property expresses the same as the FO sentence: -(-minority_student(dave) & -minority_student(ann)) There are no definitions (=LP-functions) in this scenario. I dont think this analysis is very surprising or difficult. Yet, this interpretation differs in a meaningful way from the ASP reading: it is an objective theory that self-refers nowhere to what the agent knows. --------- (See Part 5 for the continuation of this discussion.)