******************************************************************** ELECTRONIC NEWSLETTER ON REASONING ABOUT ACTIONS AND CHANGE Issue 98061 Editor: Erik Sandewall 1.8.1998 Back issues available at http://www.ida.liu.se/ext/etai/actions/njl/ ******************************************************************** ********* TODAY ********* Today, the first questions and comments re Murray Shanahan's ETAI submitted article. ********* 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: Murray Shanahan | TITLE: A Logical Account of the Common Sense Informatic | Situation for a Mobile Robot | PAPER: http://www.dcs.qmw.ac.uk/~mps/robotics_long.ps.Z | REVIEW: http://www.ida.liu.se/ext/etai/received/actions/010/aip.html ======================================================== -------------------------------------------------------- | FROM: Paulo Eduoardo Santos -------------------------------------------------------- I have several questions and comments about the paper "A Logical Account of the Common Sense Informatic Situation for a Mobile Robot" by Murray Shanahan. I organised them in two parts, one very specific about the proofs of propositions and another about general questions and comments. PART A: 1- In appendix A: Proof of proposition 5.9 should be 5.8; 2- In appendix A: I could not find proof of proposition 7.9; 3- In appendix A: I could not find proposition 7.12 in the text; 4- In appendix B: Proof of theorem 7.12 shoud be 7.13. PART B: 1- In section 1, when defining the assimilation of sensor data, it is proposed a background theory $\Sigma_B$ comprising axioms for change, actions, space and shape. However along the paper I did not see anyother mention of such a theory, my question is whether is $\Sigma_B$ represented by the last formula of section 4? 2- If so, why include in the theory $\Sigma_E$ (section 5) again the axioms for actions and change, space and shape already included in $\Sigma_B$, since it is considered the conjunction of $\Sigma_B$ and $\Sigma_E$ for the abduction process? 3- All along the paper, Circumscription is done in parts of theories (rather than in the whole theory). I understand it is done 'by construction' since the chosen version of Event Calculus considered, is the one defined using forced separation (as presented in Shanahan's book "Solving the Frame Problem" \cite{Shan:97}). My question is why do we have to circumscribe parts of the theories in the way presented, and not in any other way? Is there any formal justification for using forced separation ? 4- At the beginning of section 9 we read: "An alternative approach is to tailor made algorithms for specific tasks, such as sensor data assimilation, whose correctness with respect to the logical account can be demonstrated. This is the methodology I will adopt here, and the logic programming approach is left for further research." In another paper by Shanahan ("What Sort of Computation Mediates Best between Perception and Action" \cite{Shan:96) we read: " It is important to note that the logiscist prescription does not demand a one to one correspondence between the data structures in the machine and the sentences of the chosen formal language. (...). In other words, the machine does not have to implement a theorem prover directly. Between the abstract description of a logic-based AI program and the actual implementation can come many steps of transformation, compilation, and optimisation." I have two questions about these statements: first, by assuming a logic programming approach, aren't we contradicting the last statement above ? and, if it is not to have a theorem prover implementing the logic-based description of the system, what is exactly the role of logic in this framework? My last question is about computational complexity: In the framework presented in the paper under discussion two important points are 'explanation by adbuction' and 'circumscribing theories'. As presented in \cite{EG:92} the complexity of logic-based abduction is NP-hard (for the problem of finding an abductive explanation with the additional constraint that it has to contain a predefined letter p); the results about complexity of Circumscription are not much more impressive (as can be seen in \cite{CS:93}). My question is, taking into account these complexity results, can we still apply this framework in robotics ? @InProceedings{EG:93, author = "T. Eiter and G. Gottlob", title = "The Complexity of Logic Based Abduction", OPTcrossref = "", OPTkey = "", OPTeditor = "", OPTvolume = "", OPTnumber = "", OPTseries = "", OPTpages = "", booktitle = "Tenth Symposium of Theoretical Aspects of Computer Science (STACS-93)", year = "1993", } @Article{CS:93, author = "M. Cadoli and M. Schaerf", title = "A Survey of Complexity Results for Non-monotonic Logics", OPTcrossref = "", OPTkey = "", journal = "Journal of Logic Programming", year = "1993", volume = "17", OPTnumber = "", pages = "127-160", OPTmonth = "", OPTnote = "", OPTannote = "" } @Book{Shan:97, author = "M. Shanahan", title = "Solving the frame problem", publisher = "The MIT press", year = "1997", OPTcrossref = "", OPTkey = "", OPTeditor = "", OPTvolume = "", OPTnumber = "", OPTseries = "", OPTaddress = "", OPTedition = "", OPTmonth = "", OPTnote = "", OPTannote = "" } @Misc{Shan:96, OPTcrossref = "", OPTkey = "", author = "M. Shanahan", title = "What Sort of Computation Mediates Between Perception and Action?", howpublished = "Working notes of the AAAI Fall Symposium on Embodied Cognition", year = "1996", OPTmonth = "", OPTnote = "", OPTannote = "" } Paulo Eduardo Santos ******************************************************************** 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/ ********************************************************************