Logical Foundations for Cognitive Agents

This collection of papers is the outcome of the work of a community of researchers in AI who, during the last twenty years, have developed the logical formalisms and methods for characterizing intelligent behaviors of agents, knowledge-based systems and processes in terms of reasoning about the environment, actions, and activities that are capable of changing the current state. The book deals with commonsense reasoning, in particular with Reiter's Default Logic formalism, the theory of actions and reasoning about actions, including formalisms for high-level robot control, and different approaches to knowledge representation, all based on symbolic logic.

Texte du rabat

It is a pleasure and an honor to be able to present this collection of papers to Ray Reiter on the occasion of his 60th birthday. To say that Ray's research has had a deep impact on the field of Artificial Intel­ ligence is a considerable understatement. Better to say that anyone thinking of do­ ing work in areas like deductive databases, default reasoning, diagnosis, reasoning about action, and others should realize that they are likely to end up proving corol­ laries to Ray's theorems. Sometimes studying related work makes us think harder about the way we approach a problem; studying Ray's work is as likely to make us want to drop our way of doing things and take up his. This is because more than a mere visionary, Ray has always been a true leader. He shows us how to proceed not by pointing from his armchair, but by blazing a trail himself, setting up camp, and waiting for the rest of us to arrive. The International Joint Conference on Ar­ tificial Intelligence clearly recognized this and awarded Ray its highest honor, the Research Excellence award in 1993, before it had even finished acknowledging all the founders of the field. The papers collected here sample from many of the areas where Ray has done pi­ oneering work. One of his earliest areas of application was databases, and this is re­ flected in the chapters by Bertossi et at. and the survey chapter by Minker.

Contenu

Ray Reiter - A Memoir.- 1 The Early Years I: High school.- 2 The Early Years II: The University of Toronto.- 3 The Middle Years I: The University of Michigan.- 4 The Middle Years II: The University of British Columbia.- 5 A Reiter Aphorism.- 6 A Reiter Aphorism.- 7 The Middle Years III: The University of Toronto (Again).- 8 The Future.- Default Logic and Purity of Reasoning.- 1 An overview of Default Logic.- 2 The logical nature of reasoning.- 3 The modal logics of Default Logic.- 4 Default Logic: a strategy for explicit Definability.- 5 Default Logic: from a single to multiple Contexts.- Computing Domain Specific Information.- 1 Introduction.- 2 The Logistics Domain.- 3 Conversion to Successor State Axioms.- 4 Inner and Outer Boundaries.- 5 Some Examples.- 6 Conclusion.- Specifying Database Transactions and Active Rules in the Situation Calculus.- 1 Introduction.- 2 Active Rules.- 3 Specifying Database Updates.- 4 Specifying Transactions.- 5 Representing Active Rules.- 6 Reasoning from the Specification.- 7 Conclusions and Further Work.- The Frame Problem and Bayesian Network Action Representations.- 1 Introduction.- 2 Actions: Semantics and Basic Representations.- 3 Single Actions: Structure and the Frame Problem.- 4 Multiple Actions: The Frame and Ramification Problems.- 5 Concluding Remarks.- Philosophical and Scientific Presuppositions of Logical Al.- 1 Philosophical Presuppositions.- 2 Scientific Presuppositions.....76.- On Existence of Extensions for Default Theories.- 1 Introduction.- 2 Necessary and sufficient conditions for the existence of extensions.- 3 An interpretation of default rules using object-meta pairs.- 4 Appendix.- An Incremental Interpreter for High-Level Programs with Sensing.- 1 Introduction.- 2 Preliminaries.- 3 Off-line lookahead.- 4 Characterizing on-line executions.- 5 An incremental interpreter.- 6 Discussion.- An Improved Incremental Algorithm for Generating Prime Implicates.- 1 Introduction.- 2 A brute-force algorithm.- 3 Improving efficiency.- 4 Results.- Fixpoint 3-valued Semantics for Autoepistemic Logic.- 1 Introduction.- 2 Autoepistemic logic - preliminaries.- 3 A fixpoint 3-valued semantics for autoepistemic logic.- 4 An effective implementation of V.- 5 Relationship to logic programming.- 6 Conclusions and future work.- Toward Efficient Default Reasoning.- 1 Computation and Nonmonotonicity.- 2 Sufficient Tests for Consistency.- 3 Context-Limited Consistency Checking.- 4 The Mitigating Nature of Defaults.- 5 Experimental Evaluation.- 6 Related Work.- 7 Conclusions and Open Problems.- 8 Acknowledgments.- Action, Time and Default.- Explanatory Diagnosis: Conjecturing Actions to Explain Observations.- 1 Introduction.- 2 Representation Scheme.- 3 Preliminaries.- 4 Explanatory Diagnosis.- 5 Exploiting Regression.- 6 Exploiting the Task.- 7 Related Work.- 8 Summary.- On Sensing and Off-line Interpreting in GOLOG.- 1 Introduction.- 2 The Situation Calculus.- 3 GOLOG.- 4 Conditional action trees.- 5 sGOLOG.- 6 A simple implementation.- 7 Summary and discussion.- Reactivity in a Logic-Based Robot Programming Framework (Extended Version).- 1 Introduction.- 2 ConGolog.- 3 Interfacing the High-Level Control Module.- 4 A Mail Delivery Example.- 5 Experimentation.- 6 Discussion.- A Additional Axioms and Procedure Definitions.- Success of Default Logic.- Search Algorithms in the Situation Calculus.- 1 Dedication.- 2 Introduction.- 3 Search Problems and Algorithms.- 4 The Situation Calculus.- 5 Search Problems in the Situation Calculus.- 6 Search Algorithms in the Situation Calculus.- 7 Depth-First Search.- 8 Breadth-First Search.- 9 Best-First Search.- 10 Conclusions.- Logic and Databases: a 20 Year Retrospective - Updated in Honor of Ray Reiter.- 1 Introduction.- 2 Intellectual Contributions of Deductive Databases.- 3 Implementation Status of Deductive Databases.- 4 Emerging Areas and Trends.- 5 Summary.- Action Inventory for a Knowledge-Based Colloquium Agent. Preliminary Version.- 1 The Electronic Colloquium.- 2 Additional application aspects.- 3 Some examples of tasks.- 4 Agent support for electronic colloquia.- 5 Present organization of the colloquium software.- 6 States and Actions in the Colloquium Domain.- 7 Discussion.- A GOLOG Specification of a Hypertext System.- 1 Introduction.- 2 The Situation Calculus.- 3 Hypertext.- 4 GOLOG: Complex Actions.- 5 Run-time Layer.- 6 Conclusions and Future Work.- Explanation Closure, Action Closure, and the Sandewall Test Suite for Reasoning about Change.- 1 Introduction.- 2 DFL, TC, and the test scenarios.- 3 Coda: The Metaphysics of Change.- 4 Conclusion.- What Sort of Computation Mediates Best Between Perception and Action?.- 1 Introduction.- 2 Embodiment.- 3 Logic.- 4 Action and Change.- 5 Space, Noise and Perception.- 6 Planning, Sensing and Computation.- 7 The Sense-Plan-Act Cycle.- 8 An Implemented Robot Controller.- 9 Conclusion.- 10 Acknowledgments.- 11 Postscript: The Influence of Ray Reiter.- Modeling and Analysis of Hybrid Control Systems.- 1 Introduction.- 2 System Modeling in Constraint Nets.- 3 Requirements Specification in Timed V-Automata.- 4 Hybrid Control System Design.- 5 Behavior Verification Using Model Checking.- 6 Conclusions.