CPS 822 / CP8314 Artificial Intelligence 2
Dynamical Systems in Artificial Intelligence
Course Management Form, Winter 2018
| Office Hour
Introduction and Motivation.
Reasoning about action and event is one of the most mature research areas
in Artificial Intelligence (AI): it is almost as old as AI itself.
This research area has a direct connection to one of the central AI topics -
how to solve a problem by finding transformations or constructors/destructors
that create a desired partially specified condition from a
given initial state of affairs. This research area
has strong foundations in mathematical logic. It is influenced and
inspired by modern research in logic, knowledge representation, natural
language understanding, high-level robot control, database transactions,
and several areas in computer science.
In the 1990s, this area experienced rapid growth that was to
a significant degree stimulated by research done in Toronto, and in a few other
universities world-wide. This area consists of several sub-areas,
where researchers are seeking different ways to overcome computational
difficulties associated with reasoning about effects of actions (events) in large,
incompletely known application domains. The major areas of application are
planning, problem solving, discovery in natural sciences,
high-level robot control, verification of business processes,
database transactions, multi-agent systems and languages.
This course starts with basic introduction to mathematical logic:
prepositional logic and first order logic. The students are expected to learn
a professional logical jargon and conceptual basis that will help them
to succeed in this course. This logical language serves to provide a formal
specification that facilitates a correct implementation in one of the
programming languages. Moreover, using logical specification, it becomes
possible to formulate interesting, general and realistic AI research problems
that cannot be stated in other terms. After that, we review the most important
results in this research area, and then focus on modern developments. We will
discuss the compromises involved in providing useful logical representations
that allow reasoning about actions to remain computationally tractable.
There are some limits imposed by computational tractability; we will mention
what we can do when trying to develop efficient AI implementations.
The assignments will include problem solving exercises, but one of
the assignments on planning may include also running a benchmark problem
using the state-of-the-art planners and doing comparison with a simple
planner that was explained in CPS721.
Topics include: the situation calculus, the projection problem (whether
a given state can be reached after executing a given sequence of actions
when initial states are not known completely),
regression (reasoning backwards), progression (reasoning forward), the frame,
ramification and qualification problems, the precondition and successor state
axioms, planning, execution monitoring, reasoning about effects of continuous
and concurrent processes extended in time.
It was long time
recognized that actions have not only direct, but also indirect effects, and in
many cases, have no effect on most of the features characterizing application
domains. For example, pressing an electric switch button has a direct effect
on the button - it becomes pressed, but also has an indirect effect - lights
turn on. It turns out that chains of mutual dependencies leading to
indirect effects may be quite complicated.
We may consider representations developed to specify non-effects
succinctly and to reason about indirect effects correctly. For the latter
purpose, representations based on causality turned out to be most successful.
We may explore some of the recent results about using causality to compile
implicit indirect effects into explicit effects.
If time permits, the course may include several optional advanced topics
including complex actions and procedures, their applications to cognitive
robotics, stochastic actions and related computational problems.
This course provides sufficient background for the students who would like
to be involved in research on reasoning about actions in artificial intelligence.
The course will focus on the theory and implementation of discreet
dynamical systems considered from the perspective of artificial intelligence.
Modern logical representations of actions and their effects will be discussed
in detail. The emphasis will be on the compromises required to ensure computational
tractability of reasoning about effects of actions. The course will show how these
research issues are relevant to artificial intelligence and to applications beyond
the traditional area of artificial intelligence. Topics may include: logical foundations,
reasoning about direct and indirect effects of actions, lifted planning,
time and concurrency, causality, stochastic actions, modular representations.
Recommended Textbooks (some of the readings are optional
and/or supplementary to your lecture notes)
Edward A. Bender, S. Gill Williamson ``Short Course in Discrete Mathematics",
Dover, 2005. ($14 on Amazon.ca). See sections on
Functions and Order posted online in PDF. Alternatively, recall differences
between function and relation from a short and readable overview of
The Language and Grammar of Mathematics, published as Section I.2
(Part 1 "Introduction"): pages 8-16, in Timothy Gowers (Editor)
The Princeton Companion to Mathematics, Princeton University Press, 2008.
Uwe Schoning ``
Logic for Computer Scientists", published by Birkhauser, Boston
online from the Ryerson library. A paperback edition is $33 on
Amazon.com). [Skip resolution, since we
consider only a semantic tableau algorithm for logical reasoning: Sections 1.1 - 1.2,
and Sections 2.1 - 2.2].
Mordechai Ben-Ari ``Mathematical Logic For Computer Science'', corrected 6th printing
of the 2nd edition, Springer 2003, or a more recent edition of this book.
The recent 3rd edition
of his book (published in 2012). [This is a textbook for a Ryerson course
Concentrate on Section 2.6 , Section 5.5 and skip the rest].
Slides for the course
CSC 438S/2404S: Computability and Logic, Winter, 2014.
The following slides can be relevant:
Propositional Calculus, read pages 2-6 only, and
Predicate Calculus, read the pages 18-26 only.
Elliot Mendelson ``Introduction to mathematical logic", any recent edition is fine.
Joseph R. Shoenfield ``Mathematical Logic" (paperback).
Publisher: A K Peters/CRC Press, 2001. ($42 on Amazon.ca) [Chapters 2 and 3].
Ronald Brachman and Hector Levesque
``Knowledge Representation and Reasoning", published by Morgan Kaufmann, 2004.
ISBN: 978-1-55860-932-7 [Chapters 14, 15.1 and 16].
Available in the university library.
Raymond Reiter ``
Knowledge in Action: Logical Foundations for Specifying
and Implementing Dynamical Systems". MIT Press, 2001. [
Available online from the Ryerson library:
Chapters 3, 4, 5, 7, 9, 10.]
Hector Geffner and Blai Bonet:
A Concise Introduction to Models and Methods for Automated Planning, 141 pages.
This book is available online from the Ryerson Library.
This book was published in June 2013, by Morgan and Claypool publishers, in
the series Synthesis Lectures on Artificial Intelligence and Machine Learning
S. Russell and P. Norvig "Artificial Intelligence", published by Pearson.
The following chapters are relevant:
Planning (Chapter 11)
from the 2nd edition, 2003, p. 375-416, ISBN 0137903952;
Solving Problems by
Searching (Chapter 3), from the 3rd edition, 2010, p. 65-122, ISBN 0136042597.
Frank van Harmelen, Vladimir Lifschitz, Bruce Porter (Editors)
``Handbook of Knowledge Representation", published by ELSEVIER, 2007,
1034 Pages, ISBN: 978-0-444-52211-5. [Chapters 3, 16, 23.] Available in the
Optional/required readings may also include a selection of research
papers published in journals or in the proceedings of international
For undergraduate students: An undergraduate level course in AI (e.g., CPS721 at Ryerson).
For graduate students: interest in AI and more specifically in Knowledge Representation.
Since no previous knowledge of mathematical logic is expected,
this course starts with a brief introduction into propositional logic, and
first order logic. In addition, a popular reasoning algorithm based on semantic
tableau is also introduced and illustrated on several examples.
Lectures: 3 hours. Assigned readings, out-of-class discussions (in a tutorial
or a lab) might be possible too.
Undergraduate students: see the table on the bottom. There are two exceptions.
The undergraduate students who missed half or more than half of the lectures
fail the course for non-attendance. Class attendace is mandatory. Additionally,
the undergraduate students who did not submit 3 out of 5 homework assignments
are deemed to fail this course. Home work includes mostly problem solving.
Graduate students may be asked to complete a term project in addition
to work expected from undergraduate students and/or do in-class presentation.
For the graduate students who choose to do a project, some of the home work
assignments might be optional if they have similar background from another
university. Otherwise, for graduate students, the final grade is based on 80%
of marks for assignments and exams, and 20% on the project (possibly including
Lecture Topics (tentative list):
Introduction to propositional logic.
Syntax: well-formed formulas, sub-formulas of a formula, defined connectives.
Semantics: truth assignment, satisfiability, tautology, logical consequence,
well-known propositional equivalences.
DNF (disjunctive normal form), CNF (conjunctive normal form), NNF (negation normal form).
The satisfiability problem for a formula in propositional logic. The entailment problem.
Reasoning in propositional logic using semantic tableau:
alpha-formulas and beta-formulas, examples. A semantic tableau algorithm for solving
the satisfiability problem in Propositional Logic: a tableau branch,
an expanded, terminated branch / tableaux, a closed branch / tableau. Soundness and
completeness of the tableau algorithm for solving the satisfiability problem.
Introduction to first order logic (FOL). Syntax: predicate symbols, function symbols,
terms, quantifiers, free and bound variables. Semantics: interpretation (structure),
object assignments, model, basic semantic definition (BSD), satisfiability, logical
consequence, validity, examples of FOL equivalences.
How to prove logical consequence and logical equivalence using BSD: examples.
Substitution in terms and in formulas, a term freely substitutable for a variable
in a formula, substitution theorem.
Reasoning in FOL using semantic tableau: gamma-formulas, delta-formulas,
systematic construction of a tableau, examples.
Godel's soundness and completeness theorem for FOL.
Examples of constructing a systematic semantic tableau. Examples of counter-models
for some satisfiable FOL formulas. Prenex normal form, Skolem normal form.
Finitely axiomatizable theories, incomplete and complete theories: linear dense order.
The satisfiability and entailment problems in FOL are undecidable
(Church-Turing theorem). Compactness of FOL.
A theory of single successor, its axiomatization, and models, including
Limitations of FOL: transitive closure cannot be formulated in FOL.
Second order logic: Syntax and semantics.
Introduction to reasoning about action. Intuitive ontology for the situation calculus.
The qualification problem: the precondition axioms as a tentative solution in FOL.
Deterministic, primitive, atemporal actions without side-effects.
Frame axioms (axioms about lack of effects for actions), the
Reiter's solution. Effect axioms, normal form for effect axioms. Transforming
effect axioms for a given fluent into a single positive effect axiom and
a single negative effect axiom for the fluent. Explanation closure, causal
completeness assumption, successor state axioms.
Foundational axioms for the situation calculus, the tree of situations.
Principles of induction.
Uniform formulas, regressable formulas.
Basic action theories (BATs): precondition axioms, successor state
axioms, initial theory, foundational axioms, unique name axioms (UNA).
The projection and executability problems.
Two techniques for solving these problems: regression (reasoning backwards) and
progression (reasoning forward). The regression operator.
The relative satisfiability theorem. The theorem about reducing the projection problem
to entailment of a regressed formula from an initial theory (together with UNA).
Data base update transactions formalized in the situation calculus.
STRIPS assumption vs ADL theories vs arbitrary basic action theories.
Implementing basic action theories in Prolog: closed world assumption (CWA),
open world assumption (OWA).
Optimal planning: A* algorithm. Heuristics. The Planning Domain Definition
Language (PDDL). State of the art planners. Translating from PDDL to CPS721
Prolog representation based on situations and fluents. The planning
problem formulated as an entailment problem in the situation calculus.
Advantages of this formulation.
Reasoning about indirect effects of actions.
Circumscription: general definition, circumscription with fixed and variable
predicates, examples when circumscription can be expressed in FOL.
State constraints, the ramification and qualification problems, causality,
causal rules, compiling state constraints into successor state axioms.
Reasoning forward in the situation calculus.
Forgetting about a single ground atom and about multiple ground atoms.
Progression in the situation calculus. Local-effect basic
action theories. Computing progression efficiently.
Advanced topics in reasoning about action: time and concurrency.
Instantaneous actions, processes extended in time. The sequential temporal
situation calculus and Golog. Approaches to axiomatizing concurrency.
Natural actions: representing physical laws, least natural time point.
- (If time permits)
Advanced topics in reasoning about action: stochastic actions.
Markov Decision Processes (MDPs), decision theoretic (DT) planning.
Decision-tree based methods to solving the DT-planning problem with a finite horizon.
DT-Golog: problem representation, semantics, computing a policy and its value,
sensing actions, on-line interpreter. Applications to robot programming and
to requirements engineering.
- (If time permits)
Taxonomies of actions: troponyms (the possible relations between verbs in
the semantic network of the WordNet database). Computational advantages of
taxonomies of actions. Successor state axioms using taxonomies of
Policy on collaboration in homework assignments
The midterm exam, and the final exam may include problem solving
and short essay questions. The duration of these examinations will be
1h40min, and 2h30min, respectively.
The second test will be cumulative and will include all the material
covered throughout the term. There will be no supplemental examination.
Grades are earned for the demonstration of knowledge. If you miss a midterm
test, a final exam or a deadline for an assignment for medical reasons,
you have to provide an
official Health Certificate AND
form to the department of Computer Science within 3 working days. You have
to bring your documents yourself to the CS reception. Similarly, all
documentation related to special accommodation or academic consideration
should be submitted to the CS program office within the specified time limits.
Dates are subject to change, all changes will be announced in class and on
the course Web pages.
Assignments should be submitted on or
before the deadline specified in the assignment
(you are encouraged to submit assignments earlier).
Your assignment is considered late if any part of the assignment is late and
the penalty for a late assignment is 10% off. No assignments will be accepted
if more than 24 hours late. Start solving your assignment on the same day
when it is posted. Do not procrastinate. No make-up assignments.
Late assignments: to hand in the printout, you can give it in person to
a secretary at the CS front desk and ask her/him to put a stamp on your assignment
to confirm that you handed in your assignment on time. Send email to the TA
who is responsible for marking this assignment: inform that a hard copy of
your assignments is available from the front desk.
From time to time, I will hand out exercises.
The students are expected to solve the exercises, but
they will not be graded. However, working on exercises
will improve your understanding of this course
and will help you to get better marks on tests.
Up to 5% extra credit may be assigned for class participation, e.g.,
a student attends the entire class, participates actively by
asking/answering questions, works on
problems in class and/or attends office hours. Class participation marks
are earned for active course participation and given at discretion of
the course instructor; they cannot be requested by the students.
Handouts and assignments will be made available on the Web only.
You are responsible for visiting the course Web pages regularly and
reading assignments related information that is provided or linked from
these Web pages. Before sending your questions by e-mail to the
instructor, check these Web pages whether similar questions have been
Email communication: please send me email from local Ryerson's
email addresses only. Please be aware that email sent from Yahoo, Hotmail
and other popular domains can be filtered out as spam and might not
reach me. Email messages will be normally answered within 24 hours;
however, messages sent on weekend (starting from Friday evening) will be
usually answered on Monday.
Grades for tests and assignments will be posted electronically no later
than two weeks after the due date (test date). Marking guides, the assignments
and some other course related documents will be posted on the Ryerson University
password-protected Web portal only. Graded assignments will be usually returned
to the students within two weeks. The students are welcome to discuss their graded
work (or pick-it up) with the instructor during the posted office hours.
Discussing general approaches to problems is allowed. However, home
work assignments are individual, unless group work is allowed
in the assignment. No collaboration is allowed between groups when you
write final solutions. You may discuss assignments only
with other students currently taking the course. However, you should
never put your name on anything you do not understand.
If challenged, you must be able to reproduce and explain all
solutions by yourself, or solve similar exercises.
If you cannot explain a solution that you handed in, or if you cannot
solve an exercise similar to questions in your home work, this will
negatively affect your grade. In particular, you might be asked to solve
exercises during the office hours, or in class (as a quiz). Grades are earned
for the demonstration of knowledge. In cases when a student fails
to demonstrate knowledge about a home work, the grade for the home work
can be decreased to 0.
The first page of your homework should include: the name of all
students with whom you discussed any homework problems (even briefly).
Otherwise, it is assumed that you didn't discuss with anyone except the
instructor. Copied work (both original and copies) will be graded as 0.
An additional penalty for copied work may be assigned up to -5%
of the final course grade, i.e., cheating students can get
a negative grade on an assignment. This is in accordance with the new
Ryerson Senate Policy 60 on Academic Integrity. Repeated involvement
with plagiarism will be penalized in accordance with the departmental
policy and the Student Code of Academic Conduct.
Committing academic misconduct, such as plagiarism and cheating,
will trigger academic penalties including failing grades,
suspension and possibly expulsion from the University.
As a Ryerson student, you are responsible for familiarizing yourself
Student Code of Academic Conduct.
Grades are earned for the demonstration of knowledge.
Read carefully the marking guide for the assignment
you'd like to be remarked.
Fill in this
remarking form (available online).
Give the form and the assignment to a person who marked the assignment/test
or to the instructor (at lecture time or scheduled
office hour), who will forward it to a marker.
You canot request remarking or recalculation later than TEN DAYS from the date
on which your assignment/test mark was posted or your assignment was returned.
It's your responsibility to pick up your work as soon as possible.
Mark can decrease or remain the same if a marker finds something that
was incorrectly awarded too high a mark.
Tentative Course Calendar
(subject to change: all changes will be announced in class)
||Grade Value (%)
|Assignment 1 (in two parts)
January 30 and February 6
|Assignment 2 (in two parts)
February 13 and February 27
Thurday, March 8, noon-2pm, TBA
The total mark is the sum of marks for assignments, midterm and
the final exam. If the total mark is less than 50%, then the grade F is assigned.