******************************************************************** ELECTRONIC NEWSLETTER ON REASONING ABOUT ACTIONS AND CHANGE Issue 98059 Editor: Erik Sandewall 27.7.1998 Back issues available at http://www.ida.liu.se/ext/etai/actions/njl/ ******************************************************************** ********* TODAY ********* Today, we can advertise an additional submitted article: "Relating Theories of Actions and Reactive Control" by Chitta Baral and Son Cao Tran. Also, Eugenia Ternovskaia continues the review discussion about the article submitted by Marc Denecker et al; it appears that this article and an earlier article by Ternovskaia address somewhat different problems. In the discussion about the ontology (or ontologies?) of time, Erik Sandewall describes two problems where the punctuated timeline approach leads to absurd conclusions. It is a pleasure to see this increasing interest in publishing in the ETAI. Five articles on reasoning about actions and change have been submitted during the last three months (May, June, and July) and are presently in the open review phase; the discussion about them is lively. We hope that more and more authors will see the advantages offered by the ETAI: immediate publication, high visibility especially in the immediate peer community, much feedback, and high publication prestige especially now that the paper edition is published by the Royal Swedish Academy of Sciences. ********* ETAI PUBLICATIONS ********* --- RECEIVED RESEARCH ARTICLES --- The following article has been *received* by the present ETAI area, which means that it will be open for a three-month discussion period, followed by the closed peer-review decision on whether it will be *accepted* by the ETAI. All readers of this Newsletter are invited to participate in the discussion. Questions and comments are sent to the present Newsletter editor, and will be included in forthcoming issues of the Newsletter. Past discussion is collected in structured form in the ETAI webpages. ======================================================== | AUTHORS: Chitta Baral and Son Cao Tran | TITLE: Relating Theories of Actions and Reactive Control | PAPER: http://www.ida.liu.se/ext/epa/cis/1998/009/tcover.html | [provisional location] | REVIEW: http://www.ida.liu.se/ext/etai/received/actions/011/aip.html ======================================================== Abstract: In this paper we give a formal characterization of reactive control using action theories. In the process we formalize the notion of a reactive control program being correct with respect to a given goal, a set of initial states, and action theories about the agent/robot and about the exogenous actions. We give sufficiency conditions that guarantee correctness and use it to give an automatic method for constructing provenly correct control modules. We then extend our approach to action theories and control modules that have specialized sensing actions and that encode conditional plans. Finally we briefly relate our theory with the implementation of our mobile robot Diablo, which successfully competed in the AAAI 96 and 97 mobile robot contests. --- 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: Marc Denecker, Daniele Theseider Dupre, and Kristof | Van Belleghem | TITLE: An Inductive Definition Approach to Ramifications | PAPER: http://www.ida.liu.se/ext/epa/cis/1998/007/tcover.html | [provisional] | REVIEW: http://www.ida.liu.se/ext/etai/received/actions/009/aip.html ======================================================== -------------------------------------------------------- | FROM: Eugenia Ternovskaia -------------------------------------------------------- Dear Marc, Daniele, Kristof, Thank you for your answers to my questions. These answers clarify an important difference between our works. Using generalized inductive definitions to detect ill-defined literals is the advantage of your work. However, after 2-valuedness is shown, all reasoning involving multiple models have to be performed on the metamathematical level. In contrast, first order logic augmented with inductive definitions allows us to work with all models at once therefore allowing for incomplete information. Perhaps your approach could be developed in this direction, but you do not address this problem in the paper. Notice I do not talk about non-determinism here. I completely agree with your point of view about non-deterministic actions. Therefore it seems that we mostly developed different parts of the problem. > In your approach, you impose a syntactical restriction (no cycles) > which guarantees that the effects are unique and well-defined. The syntactic requirement of acyclicity is by no means inherent to my approach. It simplifies the presentation in the LNCS paper. Otherwise I would have to consider the cases where the correct syntactic form of successor state axioms is not obtained, thus making the paper even longer. To verify my method, I worked out the Gear wheels example. The approach works just fine, moreover, it produces successor state axioms in the correct form. Starting from your set of rules, I obtain the following successor state axiom: $$ turn_1(do(a,s)) \equiv [a=start_1 \vee a=start_2 \vee turn_1(s) \wedge a \not =stop_1 \wedge a \not =stop_2] $$ And similar for $turn_2(do(a,s))$. To avoid the cyclic regression problem, regression has to be done with respect to the causal rules for direct effects rather than with respect to successor state axioms. This is the way I do it in the paper Causality via Inductive Definitions. See http://www.cs.utoronto.ca/~eugenia/publications.html. > We can't see in what way we would be applying the Closed World Assumption. I use this term in a sloppy way here to say that a state is represented by a set of positive fluent literal, and the literals not in the set are false in this state. > > It also seems strange that you cannot derive anything > > about "holds", although I understand your motivation. > > Would it be difficult to introduce this feature? > This is not really true. The result of the transition function defines > the holds predicate in the next state. One can verify that the next > state is derived from the previous state and the causal literals as > described by the normal situation calculus persistence axiom. Perhaps I should have chosen a different wording. I used "derive" which I understand as "derive in a formal proof system". I did not mean "makes true in a particular model". > Observe moreover that ramifications need not imply state constraints > even if they restrict Trans. Of course a restriction of Trans rules > out certain transitions, but that does not need to mean that any states > are ruled out: a state is ruled out only if all transitions leading > to it are invalid. The ``counter'' example in our paper gives an example > where this is not the case: whenever an output changes to true, the > counter must be augmented. But a resulting state in which the counter > were not updated (but all other effects applied) need not be invalid > in itself. This state might well have existed at an earlier time in > the history of the network. It can only not be reached from the currently > given state. So ramifications need not imply any state constraints. I do not understand neither this comment nor the "Counter" example. The rules imply a state constraint relating any two consecutive states. This constraint is perfectly valid. Finally, a question about Definition 1. You say "and body B a nonempty set of positive and negative literals of D". Do you mean "and body B, a nonempty set of symbols from D, including $\{t\}$ and $\{f\}$"? Regards, Eugenia ********* DEBATES ********* --- ONTOLOGIES FOR TIME --- -------------------------------------------------------- | FROM: Erik Sandewall -------------------------------------------------------- Pat and Jixin, Here are some additional thoughts on ontologies for time. 1. For use within *cognitive robotics*, I take it from Jixin's latest message (ENRAC 14.7) that we can now safely ignore the dividing instant problem and use dense time (for example, the real numbers) as the time axis. The only requirement is that we are careful about how the values of fluents are defined around their discontinuities (for continuous-valued fluents) or points of change (for discrete-valued fluents). In particular, no article in this category should need to be downgraded by a referee on the grounds that "the author has not considered the dividing instant problem". 2. For use within *commonsense reasoning*, I understand that both of you consider the DIP to still be an issue. I will use the term *dividing instant situation* when, for certain combinations of fluent and clocktime, one wishes to refrain from assigning a value. For example, one may choose to consider that the state of a switch be neither "on" nor "off" at the moment when it is thrown. According to Jixin's latest message, > ... However, from the perspectives of philosophy, or > commonsense reasoning, this approach seems arbitrary in deciding > which end the intervals should include/exclude. The choice has to be > artificial and hence unjustified. For example, there is nothing to > justify the reason why the light MUST BE off (or on) at the > switching point, although, practically, one may just artificially > take a choice which will make the robot work well in most cases... For Pat, if I understand him right, this is one of the reasons why he tries to find a technical approach that satsifies those who want to use a nonstandard concept of time (nonstandard relative to conventional engineering mathematics). In order to make sense, Jixin's objection must refer not only to what conclusions are obtained, but also to the structure of the interpretations, since otherwise there ought to be no problem with the *multiple models* approach that I outlined in an earlier message (ENRAC 24.5): allow some models where the switch is "on" at the moment of change and some other models where the switch is "off" at that time, thereby avoiding getting a conclusion either way. Thus, the representational *dividing instant problem*, if I understand you right, is the problem of representing dividing instant situations in a formal system that is entirely similar to commonsense thinking. But is it reasonable to impose this restriction on the formal semantics? From a classical AI point of view, along the lines of the Turing test, it ought to be sufficient that the intended commonsense *conclusions* are obtained from the formal system in the case of dividing instant situations. From an SB (simulation of behavior) point of view, on the other hand, one must ask whether it is appropriate to use logic at all for characterizing commonsense reasoning. Isn't people's actual reasoning *very* different from what we can render in logics of commonsense? 3. What is even more problematic, however, is that the punctuated time approach (the one concrete proposal for dealing with the DIP) actually runs into technical difficulties. Pat's proposed core theory (ENRAC 7.7) is defined with a distinction between "points" and "clocktimes"; each point has a corresponding clocktime, but it is not required for each clocktime to have a corresponding point. This makes it possible to assume normal arithmetic properties for clocktimes without imposing the same structure on points. Jixin has observed that sometimes it is necessary to assume an intervening point between two intervals, for example, for being able to say that a ball that has been thrown vertically up into the air will be motionless (zero velocity) at a certain point in time. For some other actions or events it is desired not to have an intervening (time-)point, as is the case for two successive intervals, one where a switch was "on" and the next where the switch was "off". Sergio Brandano has already observed (ENRAC 23.4) that the timepoint domain will then be agent-specific. It will also be local to each scenario, so that if additional actions are added to the scenario description, one must change the timepoint domain accordingly. In fact, it even becomes necessary to revise the timepoint domain each time a *query* is asked for a scenario, which seems a bit odd. I suppose one could get used to this mode of thinking, and to accept that time is in the mind of the beholder. However, here are two examples where the punctuated time approach leads to absurd conclusions. A. Jim fires a model rocket and observes its flight. At the moment when it reaches the top of its trajectory, he turns a switch. If the flight of the rocket is modelled like Jixin proposes to model the throwing of a ball, then it requires that there exist a point for the clocktime when it is at its apex, but at the same time the fact that Jim turned the switch implies that there must not be any such point. Therefore, if the scenario description includes the statement that Jim turned the switch at the same (clock-)time as the rocket reached the apex, then it is semantically inconsistent. B. Tom and Bob compete for eating icecream cones. They start with four cones each, and have to eat them as fast as possible, starting at the same time. The referee rings a bell when one of them has finished eating all his cones. If one of the contestants tries to cheat by dropping icecream on the ground, he also rings the bell in order to call off the contest. The bell sounds at time $t$. What conclusions can be drawn from this? Consider the following ontology for this domain which is plausible if one uses punctuated time in order to deal with the DIP: 1. The ringing of the bell is momentary, that is, it occurs at a particular point in time. 2. The cone is supposed to still exist while it is being eaten, it does not exist after it has been consumed, and the clocktime at the end of the eating period does not have a corresponding point. This convention is made in order to avoid the dividing instant problem with respect to the existence of the icecream cone that has just been eaten. With these assumptions, it follows that one of the contestants cheated at time $t$, because in the case of an honest game, a point both exists and does not exist at the clocktime when the winner finishes his last cone and the bells rings. It is easy to generate additional examples of the same kind. I don't see how one can get around them as long as punctuated time is allowed. The only reasonable approaches seem to be either (a) the *transitory value approach*, where one uses an additional fluent value for "undefined or "transitory" for e.g. the state of a switch in the moment it is being thrown, or (b) the *multiple models approach* that I mentioned above. Both of these approaches are sufficiently expressive for dividing instant situations even when complete (unpunctuated) time is used. How else would you deal with these examples? 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/ ********************************************************************