Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems

Raymond Reiter

MIT Press, Jul 27, 2001 - Computers - 446 pages

Specifying and implementing dynamical systems with the situation calculus.

Modeling and implementing dynamical systems is a central problem in artificial intelligence, robotics, software agents, simulation, decision and control theory, and many other disciplines. In recent years, a new approach to representing such systems, grounded in mathematical logic, has been developed within the AI knowledge-representation community.

This book presents a comprehensive treatment of these ideas, basing its theoretical and implementation foundations on the situation calculus, a dialect of first-order logic. Within this framework, it develops many features of dynamical systems modeling, including time, processes, concurrency, exogenous events, reactivity, sensing and knowledge, probabilistic uncertainty, and decision theory. It also describes and implements a new family of high-level programming languages suitable for writing control programs for dynamical systems. Finally, it includes situation calculus specifications for a wide range of examples drawn from cognitive robotics, planning, simulation, databases, and decision theory, together with all the implementation code for these examples. This code is available on the book's Web site.

Contents

• Introduction: xxi
• Logical Preliminaries: 3
• 22 SecondOrder Logic: 10
• 23 Exercises: 13
• 24 Bibliographic Remarks: 16
• Introduction to the Situation Calculus: 17
• 32 A Simple Solution to the Frame Problem Sometimes: 21
• 33 Deductive Planning with the Situation Calculus: 33
• 34 Formalizing Database Transactions in the Situation Calculus: 37
• 35 Exercises: 39
• 36 Bibliographic Remarks: 42
• Foundations of the Situation Calculus: 45
• 42 Axioms for the Situation Calculus: 46
• 43 Reasoning about Situations Using Induction: 52
• 44 Basic Theories of Action: 56
• 45 Regression: 59
• 46 Using Regression: 65
• 47 Regression with Functional Fluents: 68
• 48 Database Logs and Historical Queries: 71
• 49 Exercises: 76
• 410 Bibliographic Remarks: 81
• Implementing Basic Action Theories: 83
• 52 LloydTopor Normal Forms for Arbitrary Definitions and Goals: 88
• 53 Basic Action Theories Definitions and Regressable Queries: 93
• 54 Exercises: 105
• 55 Bibliographic Remarks: 106
• Complex Actions Procedures and Golog: 109
• 62 An Elevator Controller in Golog: 117
• 63 Implementation: 120
• 64 Discussion: 130
• 65 Proving Properties of Golog Programs: 132
• 66 Summary: 136
• 67 Exercises: 138
• 68 Bibliographic Remarks: 143
• Time Concurrency and Processes: 147
• 73 The Sequential Temporal Situation Calculus: 150
• 74 Sequential Temporal Golog: 153
• 75 The Concurrent NonTemporal Situation Calculus: 162
• 76 Axiomatizing Concurrent Worlds: 164
• 77 The Concurrent Temporal Situation Calculus: 165
• 78 Concurrent Temporal Golog: 167
• 79 Natural Actions: 168
• 710 Exercises: 180
• 711 Bibliographic Remarks: 181
• Exogenous Actions Interrupts and Reactive Golog: 183
• 82 The Semantics of RGolog: 185
• 83 An RGolog Interpreter: 188
• A Reactive Elevator Controller: 189
• 85 Interrupts with Priorities: 196
• 86 Discussion: 197
• 87 Exercises: 200
• 88 Bibliographic Remarks: 201
• Progression: 203
• 91 Logical Foundations of Progression: 205
• 92 Two FirstOrder Progressable Cases: 208
• 93 STRIPS Planning Systems: 214
• 94 Strongly ContextFree Successor State Axioms: 221
• 95 Progression and Relational STRIPS: 222
• 96 An OpenWorld STRIPS: 224
• 97 Correctness of Relational and OpenWorld STRIPS: 226
• 98 Exercises: 228
• 99 Bibliographic Remarks: 229
• Planning: 231
• Planning in the Blocks World: 233
• 103 Planning with Concurrent Actions: 240
• A MultiHanded Blocks World Agent: 245
• 105 A Simple DepthFirst Planner: 253
• 106 OpenWorld Planning: 257
• 107 Planning vs Nondeterministic Programming: 273
• 108 Exercises: 275
• 109 Bibliographic Remarks: 278
• Sensing and Knowledge: 281
• 112 Knowledge and the Designers Perspective: 290
• 113 KnowledgeProducing Actions: 291
• 114 The Frame Problem for KnowledgeProducing Actions: 292
• 115 Accessibility in the Initial Situation: 300
• 116 Regression for KnowledgeProducing Actions: 304
• 117 KnowledgeBased Programming: 307
• 118 Discussion: 325
• 119 Exercises: 326
• 1110 Bibliographic Remarks: 330
• Probability and Decision Theory: 333
• 122 Derived Probabilities: 339
• 123 Exogenous Events: 347
• 124 Uncertainty in the Initial Situation: 357
• 125 Markov Decision Processes: 361
• 126 Discussion: 377
• 127 Exercises: 378
• 128 Bibliographic Remarks: 381
• Concluding Remarks: 383
• Some Useful FirstOrder Inference Rules: 387
• A2 Generation Rules: 389
• A3 Success Rules: 390
• A5 Simplification Rules: 391
• A6 Additional Success Rules: 392
• A8 Exercises: 397
• The Qualification and Ramification Problems: 399
• B2 Constraints and the Qualification Problem: 400
• B3 Solving the Qualification and Ramification Problems: 402
• Resources: 405
• References: 407
• Index: 417

About the author

Raymond Reiter is Professor and Co-Director of the Cognitive Robotics Project in the Department of Computer Science at the University of Toronto.

Bibliographic information

• Title: Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems; The MIT Press
• Author: Raymond Reiter
• Publisher: MIT Press, 2001
• ISBN: 0262264315, 9780262264310
• Length: 446 pages
• Subjects: Computers / Artificial Intelligence / General