******************************************************************** ELECTRONIC NEWSLETTER ON REASONING ABOUT ACTIONS AND CHANGE Issue 98075 Editor: Erik Sandewall 3.10.1998 Back issues available at http://www.ida.liu.se/ext/etai/rac/ ******************************************************************** ********* TODAY ********* Graham White's article "Simulation, Ramification, and Linear Logic" has rapidly invited discussion. We had a question/comment from Tom Costello a few days ago. Today's issue contains the author's answre to Costello's questions, and a new set of questions by Andreas Herzig. Note that the author had an earlier article on the same topic at the Commonsense workshop in London in January, and that already our on-line discussion of the article at that time contained a number of interactions. Our discussion about Wolfgang Bibel's IJCAI article (September 1997 - January 1998) also touched on the present topic. In addition, the present issue carries the first set of questions and comments to the article by Chitta Baral and Son Cao Tran on "Relating Theories of Actions and Reactive Control" ********* ETAI PUBLICATIONS ********* --- DISCUSSION ABOUT RECEIVED ARTICLES --- The following debate contributions (questions, answers, or comments) have been received for articles that have been submitted to the ETAI and which are presently subject of discussion. To see the full context, for example, to see the question that a given answer refers to, or to see the article itself or its summary, please use the web-page version of this Newsletter. ======================================================== | AUTHOR: Graham White | TITLE: Simulation, Ramification, and Linear Logic | PAPER: http://www.ep.liu.se/ea/cis/1998/011/ | REVIEW: http://www.ida.liu.se/ext/etai/ra/rac/012/ ======================================================== -------------------------------------------------------- | FROM: Graham White -------------------------------------------------------- Dear Tom, Thanks for your question. It seems to me that I would want first of all to differentiate between your two formulations of the basic objection: i) "some local properties ... are expressed as $\Pi_i$ formulas", and ii) "many effect axioms will have preconditions that say that the effect will occur in certain circumstances, unless there is something that prevents it". The first formulation has to do with local properties, which I take to be a fairly general, phenomenological notion; the second is to do with action preconditions, which is a notion internal to certain treatments of the frame problem. I'll deal with the second notion first. My approach doesn't really use action preconditions *per se*. I don't have anything like a result function: given linear logic terms s and a representing a situation and an action, there may or may not be a valid inference of the form s, a |- s' where s' is also a situation term. So there are, in some sense, implicit action preconditions, but I don't represent them explicitly. I can deal with your example in my framework as follows. We have to introduce constraints on the space of situations, which I can do by having an extra pair of fluents, say good and bad, which say whether situations are physically realisable or not, and also having extra ramification transitions (on(b,l) * on(b',l) * good) ~> (on(b,l) * on(b',l) * bad) for b and b' unequal. We now apply the ramification machinery that I described: that is, we look for sequents corresponding to performing the action, followed by a terminating sequence of ramification transitions, such that we eventually end up with a situation of the form X * good. All of this can be carried out with entirely local data, but the implicit preconditions are as you described. (I'm a bit unsure about the other part of the precondition, which says that you can't pick up a block with another block on top of it. My immediate response to that is "well, I can", but I'm not sure exactly what the impossibility is supposed to be here.) Incidentally, I'm not at all sure about the phenomenological motivation of the concept of precondition. It seems to me that it conflates two quite distinct phenomena: the first is of actions (such as "opening the door") described by what Ryle called "success words", where it doesn't make sense to talk of performing them when they don't succeed. The other is of action descriptions such as "trying to open the door", where the possibility of failure is allowed for, and where we usually also have some intuitions about what happens in the case of failure. As Ryle (and I suppose also Wittgenstein) point out, the second case is rather more complex than the first, and probably needs a more elaborate description than simply giving preconditions. The first is the usual case in a great deal of everyday language, but, by its nature, does not need any explicit talk of preconditions (although one could, presumably, in many cases find implicit preconditions). Your first objection is that many local concepts are in fact $\Pi_i$. This may be true, but what surely matters for my analysis is not local concepts per se, but the local concepts that are used in the sort of representation that I am describing. One probably also ought to distinguish between genuine universal quantification and universal quantifications which are, in some way, bounded. Most local concepts would, presumably, only be $\Pi_i$ in the latter sense, and it would be a sense corresponding to some natural means of verification -- I check, for example, that there is nothing on my desk by looking at the locations on my desk and verifying that they are all empty (and I can tell that they're empty just by looking at them). I certainly don't do it by finding all of the objects that there are and verifying that none of them is on my desk; and an analysis of "there is nothing on my desk" that reduces it to a $\Pi_1$ *of that sort* is likely to be epistemologically misleading. I hope this helps, anyway. Graham -------------------------------------------------------- | FROM: Andreas Herzig -------------------------------------------------------- Dear Graham, I appreciate the aims of the paper, viz. the discussion about the logical form and the proof-theoretic account of reasoning about actions as given in sections 1, 2.1.1, 2.4. I think that too little work has been done in the community on such fundamental issues. Basically you propose Linear Logic (LL) as a proof theory to reason about actions, following Girard who claimed from the beginning that LL would be much better suited for reasoning about actions and change than any other logical system. LL people have tried to support that claim, such as Masseron et al. (LNCS 427, 1990) or Bidoit et al. (JLC, 1996). The same has been tried also by people coming from Bibel's linear connection method - see e.g. Bibel's IJCAI'97 invited lecture, as well as work of Fronhofer and Grosse et al. that Bibel cites; see also the subsequent discussion at http://www.ida.liu.se/ext/etai/actions/deb/bibel/index.html In my opinion all these attemps have failed in the sense that the only thing they can handle within LL is the simplest case: deterministic actions, no state constraints, knowledge about the initial situation only. They didn't succeed in going beyond that without violating the spirit of LL: they all introduced extra concepts that were used to constrain deduction in one way or another. In the present paper it is time which is made explicit in the encoding of reasoning about action problems (section 3, 3rd paragraph). But I would expect time to be implicit in a LL account of reasoning about actions: it is the implication of LL which - if we take Girard seriously - should be able capture the dynamics, and not formulas such as ``time(0) & occurs(lift)(0)''. There seem to be other extra concepts, such as grouping of those sequent rules corresponding to an action (see below). This is my main criticism. What follows are more detailed comments. Sections 2.2. The two-blocks Example 1 is similar to Lifschitz' two switches example, I suppose. (Btw. on p.4, line 8 should be dropped.) I guess circumscription doesn't give *the* solution, but several ones, one of which you give in the table. (Btw. one b_1 should be b_2 there.) Sections 2.3. I don't understand the difference between Example 1 and Examples 2 and 3. Where does the `support' concept come from? I need more comments here. Section 2.4. The expression `` equivalent in first order logic to theory T, but expressed in L' '' is inaccurate. I don't know whether you refer to logical equivalence in the union of the two languages L and L' under the translation theory of Table 3, or rather to interpretability as in the end of the subsection. Section 3.2. You claim your rewrite rules for the two blocks theory is `local data', in the sense that they remain valid `if we introduce new types of cause'. But what about introducing an action such as cutting or removing the string between the blocks? Then the rewrite rules `linking' the blocks do not hold any longer. Section 4.1. Wy don't you mention the cut rule here? (you talk about its elimination in the proof of Proposition 1). In the statement of Proposion 1, you don't say what ACI is. If you have cut, how can composition of rewrites be a problem? Cut is just doing that job, viz. chaining sequents. I guess this relates to my main criticism: in order to identify actions in proofs, you must group together sequences of rules related to the same action. This means that there is a new concept that is exterior to LL. (I think the problem of termination of sequences is similar.) Section 4.2. I don't understand how the introduction of modal operators solves the above problem. In the basic rewrite rule of Definition 1, I suppose the LL `times' operator is rather an ACI bullet. I found it difficult to understand the exposition on termination. I suppose termination refers to termination of a rewrite sequence corresponding to an action. In the rule, the notation A - A_i has not explained. What is a `state' A_i? ======================================================== | AUTHORS: Chitta Baral and Son Cao Tran | TITLE: Relating Theories of Actions and Reactive Control | PAPER: http://www.ep.liu.se/ea/cis/1998/009/ | REVIEW: http://www.ida.liu.se/ext/etai/ra/rac/011/ ======================================================== -------------------------------------------------------- | FROM: Erik Sandewall -------------------------------------------------------- Dear Chitta and Son Cao, Your article addresses a very interesting topic for our group. I have some specific questions about the contents of the article, and also some comments about how it relates to other current approaches to the same or similar problems. I'll write them as two separate contributions. With respect to the article itself, I have the following questions. 1. For maintenance control modules, which are treated in section 3.3, you write: > But in the presence of exogenous actions the robot with no control over > those actions can only strive to make the maintenance goal true if they > are made false by some exogenous action. In other words a maintenance > control module can not guarantee that the maintenance goal will never > be false... This seems right if the maintenance goal is characterized by one single state in the state space. However, many applications do require controllers to keep the controlled system in an acceptable state at all times, which is possible if there is a number of such acceptable states, and the state transitions due to exogenous "actions" sometimes only move within the acceptable set. In such cases the controller strives to keep the system in those states among the acceptable ones that are "at a safe distance" from the unacceptable ones. More precisely, even if the system is in an acceptable state, the controller may perform actions as a precaution against future exogenous "actions", thereby shifting the system to a state where exogenous actions can not be harmful. Possibly one can reduce this case to the one you consider by identifying the maintenance goal with a subset of the acceptable states, namely those acceptable states where that are at a safe distance from a transition to the unacceptable ones. Is this the way you intend maintenance goals to be defined, and if so, do you claim that the reduction is always valid? (Concurrency and the use of combined achievement and maintenance modules may introduce complications, I believe). 2. A second question concerns to what extent this work relates to current, logic-based theories of actions and change. In section 9.1 you write: > ... in this paper we do not use any specific action theory... rather > we use an abstract "entailment relation". Because of this, our > formulation need not change with more sophisticated action theories. However, as I read the paper I wonder whether it depends on any of the concepts or results of current action theories at all? (This is not a criticism, of course, I just want to understand the character of your definitions and results). For example, definition 6.1 on page 28 begins > Let ... $A$ be an action theory with a transition function \Phi and then the rest of the definition is expressed only in terms of \Phi. Could it be the case, then, that everything in this article could as well be expressed only in terms of states, state spaces, and transition functions? In this case, action languages and other logicist devices ought to be seen simply as a convenient notation for specifying transition functions, but otherwise they'd not play any role in this particular development. 3. Here is a standing question that I now ask regularly to authors in our area. Given that your paper proclaims a number of theorems, as do many of our publications, (a) do your results rely on any theorem previously published in this literature, (b) do you foresee any of your theorems later being used in a forthcoming publication by yourself or someone else? If the answers to both questions are "no", what do you think is the purpose of including theorems in our research articles? 4. There seems to be a close connection between your $Closure$ concept and the most commonly studied cases of ramification. In both cases, one first specifies the effects of an action "in itself", and then one adds the possibility of additional changes due to phenomena that are characterized separately from that action. Is this a connection that you have also considered? The relation to ramification is particularly transparent by comparison with my KR-96 paper, . That article uses two types of state transitions: one *result* function that maps an action and a state to a set of possible result states, and a binary *successor* relation that characterizes further transitions. The "closure* of an action, in that case, is the set of all states that can be reached via one member of the set of action result states, followed by an arbitrary number of steps using the successor relation, and that do not in turn have any successor. For ramification, the successor relation characterizes spontaneous and "caused" transitions in the world; in your work they would instead characterize the results of exogenous "actions". These two cases seem to be very close to each other. The KR article is in fact formulated entirely in terms of states and state transitions, and analyses ramification methods without introducing any logic language at all. Its way of looking at actions is therefore quite close to what you use in your paper. (The main results in my article are assessments that characterize the range of sound applicability for a number of previously published approaches to ramification). Relating back to my question 2, this adds to the impression that ramification and exogenous events are related phenomena. 5. I put quotes around "actions" because I can not get used to the idea of calling natural events `actions'. Although I understand the background of this terminology, which comes from the situation calculus, I do think it makes communication with neighboring disciplines a lot more difficult than it ought to be. Best regards, Erik ******************************************************************** This Newsletter is issued whenever there is new news, and is sent by automatic E-mail and without charge to a list of subscribers. To obtain or change a subscription, please send mail to the editor, erisa@ida.liu.se. Contributions are welcomed to the same address. Instructions for contributors and other additional information is found at: http://www.ida.liu.se/ext/etai/actions/njl/ ********************************************************************