Knowledge in Action - Table of Contents

September 2001
7 x 9, 444 pp.
$63.00/£46.95 (CLOTH)
Short

ISBN-10:
0-262-18218-1
ISBN-13:
978-0-262-18218-8

Related Links

< BACK
Knowledge in Action
Logical Foundations for Specifying and Implementing Dynamical Systems
Raymond Reiter

	Preface Sample Chapter - Download PDF (16 KB)

	Acknowledgments

1	Introduction Sample Chapter - Download PDF (43 KB)

2	Logical Preliminaries

		2.1	First-Order Logic

			2.1.1	Syntax

			2.1.2	Semantics

			2.1.3	Soundness and Completeness

			2.1.4	Many-Sorted First-Order Languages

			2.1.5	Reducing Many-Sorted Logic to Standard Logic

			2.1.6	Some Useful First-Order Inference Rules

			2.1.7	A Limitation of First-Order Logic

		2.2	Second-Order Logic

			2.2.1	Syntax

			2.2.2	Semantics

			2.2.3	Inductive Definitions and Second-Order Logic

			2.2.4	The Incompleteness of Second-Order Logic

		2.3	Exercises

		2.4	Bibliographic Remarks

3	Introduction to the Situation Calculus

		3.1	The Situation Calculus

			3.1.1	Intuitive Ontology for the Situation Calculus

			3.1.2	Axiomatizing Actions in the Situation Calculus

			3.1.3	The Qualification Problem for Actions

			3.1.4	The Frame Problem

		3.2	A Simple Solution to the Frame Problem (Sometimes)

			3.2.1	Frame Axioms: Pednault's Proposal

			3.2.2	Frame Axioms: The Davis/Haas/Schubert Proposal

			3.2.3	A Simple Solution (Sometimes)

			3.2.4	Aside: Normal Forms for Effect Axioms

			3.2.5	A Simple Solution: The General Case

			3.2.6	A SimpleSolution: FunctionalFluents

			3.2.7	A Simple Solution: Summary

			3.2.8	Some Limitations of These Action Descriptions

		3.3	Deductive Planning with the Situation Calculus

		3.4	Formalizing Database Transactions in the Situation Calculus

			3.4.1	Motivation and Background

			3.4.2	Database Updates: A Proposal

			3.4.3	The Basic Approach: An Example

			3.4.4	Querying a Situation Calculus Database

		3.5	Exercises

		3.6	Bibliographic Remarks

4	Foundations of the Situation Calculus

		4.1	The Language of the Situation Calculus

		4.2	Axioms for the Situation Calculus

			4.2.1	Number Theory

			4.2.2	Foundational Axioms for Situations

			4.2.3	Some Consequences of the Foundational Axioms

			4.2.4	Executable Situations

			4.2.5	Further Consequences of the Foundational Axioms

		4.3	Reasoning about Situations Using Induction

			4.3.1	Some Examples of Inductive Proofs

			4.3.2	State Constraints

		4.4	Basic Theories of Action

		4.5	Regression

		4.6	Using Regression

			4.6.1	Executable Ground Action Sequences

			4.6.2	The Projection Problem and Query Evaluation

		4.7	Regression with Functional Fluents

		4.8	Database Logs and Historical Queries

			4.8.1	Querying All Past Situations

			4.8.2	Querying Some Past Situations

			4.8.3	The Projection Problem Revisited

		4.9	Exercises

		4.10	Bibliographic Remarks

5	Implementing Basic Action Theories

		5.1	Logical Foundations of Prolog

			5.1.1	Why Insist on a Proper Prolog Interpreter?

			5.1.2	More on the Equational Theory of Clark's Theorem

		5.2	Lloyd-Topor Normal Forms for Arbitrary Definitions and Goals

			5.2.1	What Are the Lloyd-Topor Auxiliary Predicates?

			5.2.2	Accommodating Arbitrary Goals

			5.2.3	Definitional Theories: Soundness, Completeness, and Closed Worlds

		5.3	Basic Action Theories, Definitions, and Regressable Queries

			5.3.1	Definitional Form for Action Precondition Axioms

			5.3.2	Definitional Form for Successor State Axioms

			5.3.3	Unfolding the Lloyd-Topor Auxiliary Predicates

			5.3.4	Revised Lloyd-Topor Transformations

		5.4	Exercises

		5.5	Bibliographic Remarks

6	Complex Actions, Procedures, and Golog

		6.1	Complex Actions and Procedures in the Situation Calculus

			6.1.1	Procedures

			6.1.2	Programs and Executable Situations

			6.1.3	Why Macros?

			6.1.4	Programs as Macros: What Price Must Be Paid?

			6.1.5	Golog

		6.2	An Elevator Controller in Golog

		6.3	Implementation

			6.3.1	An Interpreter

			6.3.2	Assumptions Underlying the Implementation

			6.3.3	Correctness of the Interpreter for Basic Action Theories with Closed Initial Database

			6.3.4	The Elevator Example

			6.3.5	The University of Toronto Implementation of Golog

		6.4	Discussion.

		6.5	Proving Properties of Golog Programs

			6.5.1	Induction Principle for While Loops

			6.5.2	Example: A Blocks World

		6.6	Summary

		6.7	Exercises

		6.8	Bibliographic Remarks

7	Time, Concurrency, and Processes

		7.1	Concurrency and Instantaneous Actions

		7.2	Concurrency via Interleaving

			7.2.1	Examples of Interleaved Concurrency

			7.2.2	Limitations of Interleaved Concurrency

		7.3	The Sequential, Temporal Situation Calculus

			7.3.1	Concurrent Temporal Processes

		7.4	Sequential, Temporal Golog

			7.4.1	Example: A Coffee Delivery Robot

			7.4.2	A Singing Robot

			7.4.3	Plan-Execution Monitoring

		7.5	The Concurrent, Non-Temporal Situation Calculus

		7.6	Axiomatizing Concurrent Worlds

			7.6.1	Successor State Axioms

			7.6.2	Action Precondition Axioms

		7.7	The Concurrent, Temporal Situation Calculus

		7.8	Concurrent, Temporal Golog

		7.9	Natural Actions

			7.9.1	Representing Physical Laws

			7.9.2	Permissiveness of the Situation Calculus

			7.9.3	Natural Actions and Executable Situations

			7.9.4	An Example: Enabling Actions

			7.9.5	Zeno's Paradox

			7.9.6	The Natural-World Assumption

			7.9.7	Least-Natural-Time Points

			7.9.8	Simulating Natural Worlds

			7.9.9	Animating Natural Worlds

		7.10	Exercises

		7.11	Bibliographic Remarks

8	Exogenous Actions, Interrupts, and Reactive Golog

		8.1	Interrupts

		8.2	The Semantics of RGolog

			8.2.1	Intuitive Semantics of RGolog

			8.2.2	Formal Semantics of RGolog

		8.3	An RGolog Interpreter

		8.4	Example: A Reactive Elevator Controller

			8.4.1	A Reactive Elevator with Interactively Generated Exogenous Actions

			8.4.2	A Reactive Elevator with Randomly Generated Exogenous Actions

		8.5	Interrupts with Priorities

		8.6	Discussion

			8.6.1	Sensing and Exogenous Actions

			8.6.2	On-Line vs. Off-Line Program Execution

		8.7	Exercises

		8.8	Bibliographic Remarks

9	Progression

		9.1	Logical Foundations of Progression

			9.1.1	Finite Progression Is Second-Order Definable

			9.1.2	Progression Is Not Always First-Order Definable

			9.1.3	But Why Not Do the Obvious?

		9.2	Two First-Order Progressable Cases

			9.2.1	Progressing Relatively Complete Databases

			9.2.2	Context-Free Successor State Axioms and the Progression of Isolated Fluents

		9.3	STRIPS Planning Systems

			9.3.1	STRIPS Databases

			9.3.2	STRIPS Operator Descriptions

			9.3.3	Planning with STRIPS

		9.4	Strongly Context-Free Successor State Axioms

		9.5	Progression and Relational STRIPS

		9.6	An Open-World STRIPS

		9.7	Correctness of Relational and Open-World STRIPS

		9.8	Exercises

		9.9	Bibliographic Remarks

10	Planning

		10.1	A Simple Breadth-First Planner

		10.2	Example: Planning intheBlocksWorld

			10.2.1	A Planning Problem Example

		10.3	Planning with Concurrent Actions

		10.4	OCTOPUS: A Multi-Handed Blocks World Agent

		10.5	A Simple Depth-First Planner

		10.6	Open-WorldPlanning

			10.6.1	Prime Implicates and Compiling an Initial Database

			10.6.2	A Regression-Based Theorem-Prover

			10.6.3	Bad Situations for Open-World Planning

			10.6.4	Axiomatizing Incomplete Initial Situations

			10.6.5	A Blocks World with Incomplete Initial Situation

		10.7	Planning vs. Nondeterministic Programming

		10.8	Exercises

		10.9	Bibliographic Remarks

11	Sensing and Knowledge

		11.1	Knowledge in the Situation Calculus

			11.1.1	Accessibility Relations and Knowledge

			11.1.2	Alternatives to the Initial Situation

			11.1.3	Knowing a Referent

			11.1.4	Knowledge and Action

			11.1.5	Knowledge Defined

			11.1.6	Some Consequences of This Approach

			11.1.7	A Useful Notation

			11.1.8	Quantifiers and Knowledge

		11.2	Knowledge and the Designer's Perspective

			11.2.1	Logical Omniscience Revisited

		11.3	Knowledge-Producing Actions

		11.4	The Frame Problem for Knowledge-Producirig Actions

			11.4.1	The No-Side-Effects Assumption for Knowledge Producing Actions

			11.4.2	A Successor State Axiom for K

			11.4.3	More General Knowledge-Producing Actions

			11.4.4	Some Consequences of this Solution

		11.5	Accessibility in the Initial Situation

			11.5.1	New Foundational Axioms for Situations

			11.5.2	Some Possible Accessibility Relations

			11.5.3	Basic Action Theories for Knowledge

		11.6	Regression for Knowledge-Producing Actions

		11.7	Knowledge-Based Programming

			11.7.1	Two Simplifying Assumptions

			11.7.2	Sense Actions

			11.7.3	Reducing Knowledge to Provability for the Initial Situation

			11.7.4	On-Line Execution of Knowledge-Based Programs

			11.7.5	Reduction of Knowledge to Provability for On-Line Programs

			11.7.6	The Dynamic Closed-World Assumption

			11.7.7	Interpreter for Knowledge-Based Programs with Sensing

			11.7.8	Computing Closed-World Knowledge

			11.7.9	Putting It All Together

		11.8	Discussion

		11.9	Exercises

		11.10	Bibliographic Remarks

12	Probability and Decision Theory

		12.1	Stochastic Actions and Probability

			12.1.1	How to Specify a Probabilistic Domain: A Guide for the Perplexed

			12.1.2	Some Properties of the Specification

		12.2	Derived Probabilities

			12.2.1	stGolog: Stochastic Golog

		12.3	Exagenous Events

		12.4	Uncertainty in the Initial Situation

		12.5	Markov Decision Processes

			12.5.1	Sensing and stGolog Programs

			12.5.2	Fully Observable MDPs

			12.5.3	Partially Observable MDPs

			12.5.4	Implementing Policies: Run-Time Sense Actions

			12.5.5	Exogenous Actions

			12.5.6	Solving MDP Planning Problems

		12.6	Discussion

		12.7	Exercises

		12.8	Bibliographic Remarks

13	Concluding Remarks

	Appendix A: Some Useful First-Order Inference Rules

		A.1	Decomposition Rules

		A.2	Generation Rules

		A.3	Success Rules

		A.4	Proof Rules for Unique Names Axioms

		A.5	Simplification Rules

		A.6	Additional Success Rules

		A.7	Examples of Proofs

		A.8	Exercises

	Appendix B: The Qualification and Ramification Problems

		B.1	Constraints and the Ramification Problem

		B.2	Constraints andthe QualificationProblem

		B.3	Solving the Qualification and Ramification Problems

	Appendix C: Resources

	References

	Index Sample Chapter - Download PDF (51 KB)

	Join an E-mail Alert List

TECHNOLOGY PARTNER: Azility, Inc.