Métodos de Computação Inteligente: 2006-1

General Information:

Lecturer: Jacques Robin (robin.jacques@gmail.com)

Teaching Assistants: Fábio Moura (fabio.mpereira@gmail.com), Marcos Aurelio Silva (maurelio1234@gmail.com), Luiz Lacerda (luiz.francisco.lacerda@gmail.com)

Days & Time:

Lectures: Tuesday & Thursday 08:00-10:00

Seminars and Project Advising: Tuesday 16:00-18:00 & Thursday 14:00-16:00

Room: Grad 3

This page: www.cin.ufpe.br/~in1006/2006/Welcome.html

Textbooks:

Artificial Intelligence: A Modern Approach (2nd Ed.) Russell, S. & Norvig, P. Prentice-Hall. 2003. Site: http://aima.cs.berkeley.edu/.

Introduction to Multi-Agent Systems. Wooldridge, M. Wiley. 2002. Site: www.csc.liv.ac.uk/~mjw/pubs/imas/

Constraint Processing. Dechter, R. Morgan-Kaufmann. 2003.

Essentials of Constraint Programming. Frühwirth, T. & Abdennhader, S. Springer. 2003.

Constraint Programming: an Introduction. Marriott, K. & Stuckey, P. MIT Press. 1998.

Ontologies: a Silver Bullet for Knowledge Management and Electronic Commerce. Fensel, D. Springer. 2003.

UML 2 Toolkit. Eriksson, H.E., Penker, M., Lyons, B. & Fado, D. Wiley. 2004

The Object Constraint Language: Getting Your Models Ready for MDA (2nd Ed.) Warmer, J. & Kleppe, A. Addison-Wesley. 2003.

Logic, Programming and Prolog (2nd Ed). Nilsson, U. & Maluszynski. Wiley. 2000. Site, including free download : http://www.ida.liu.se/~ulfni/lpp/

Evaluation:

Oral seminar (in pairs): 30%

Command & Understanding: 1 point

Completeness Depth (Aprofundamento): 1 point

Completeness Breadth (Abrangência): 1 point

Correctness: 1 point

Conciseness: 1 point

Relevance:  1 point

Clarity: 1 point

Examples: 1 point

Oral skills: 1 point

Slides: 1 point

Material not completely studied with question list ready for first advising meeting 3 weeks before seminar’s date: - 2 points

Slides not completely ready for last advising meeting 1 week before seminar’s date: - 2 points

Project (in teams): 40%

Artifacts: 20%

Scope width: 1 point

Robustness, testing thoroughness: 2 points

Extensibility to new requirements: 1 point

Reusability in new domains: 1 point

Reusability across platforms: 1 point

Documentations, explanations, comments: 1 point

Legibility, conciseness: 1 point

For models, executability: 2 points

For code, performance scalability: 2 points

Written Report: 10%

Project general goal, motivation and context: 1 point

Explanations of artifacts: 1 point

Motivation and discussion of choices among alternative possibilities: 1 point

Limitations of work in terms of scope, robustness, extensibility, reusability : 1 point

Examples: 1 point

Figures: 1 point

Writing clarity: 1 point

Writing relevance and conciseness: 1 point

Completeness depth: 1 point

Correctness: 1 point

Oral Presentation: 10%

Command/understanding: 1 point

Completeness Depth (Aprofundamento): 1 point

Completeness Breadth (Abrangência): 1 point

Correctness: 1 point

Conciseness: 1 point

Relevance:  1 point

Clarity: 1 point

Examples: 1 point

Oral skills: 1 point

Slides: 1 point

Exams (individual) 30%

All documents allowed, for each question get one point by picking the single correct answer out of the four proposed answers

20mn, 4 questions quick tests at the end of randomly chosen classes

Roster

Arianne de Oliveira Albuquerque (aoa2@cin.ufpe.br, pcart)

Daniel Henriques Moreira (dhm@cin.ufpe.br, glr)

Eduardo Araujo Oliveira (eao@cin.ufpe.br, agogear@hotmail.com, pcart)

Fabrício de Siqueira Teles (fst@cin.ufpe.br, fabricio.teles@gmail.com, jr)

Gustavo Galvão Petry (ggp2@cin.ufpe.br, gustavo_petry@hotmail.com, gvc)

Joao dos Prazeres Farias (jpf2@cin.ufpe.br, joaodosprazeres@gmail.com, jr)

Luiz Josué da Silva Filho (ljsf2@cin.ufpe.br, luiz.josue@gmail.com, pcart)

Maria Uilma Rodrigues dos Santos de Sousa (murss@cin.ufpe.br, mailto:uilmasantos@tce.pe.gov.br, pjla)

Marcos Aurélio Almeida da Silva (maas@cin.ufpe.br, maurelio1234@gmail.com, jr)

Patricia Takako Endo (pte@cin.ufpe.br, patricia_endo@yahoo.com.br, pasg)

Paulo Salgado Gomes de Mattos Neto (psgmn@cin.ufpe.br, paulosalgado10@gmail.com, gcv)

Priscila Corrêa Saboia (pcs4@cin.ufpe.br, ecdbcf)

Rafael de Amorim Silva (ras5@cin.ufpe.br, rafael_amorim82@hotmail.com, pasg)

Ricardo Enrique Pereira Scholz (reps@cin.ufpe.br, ricardosholz@gmail.com, glr)

Ryan Ribeiro de Azevedo (rra2@cin.ufpe.br, ryanweb9@gmail.com, ecdbcf)

Vitor Cavalcanti Dantas (vcd2@cin.ufpe.br, glr)

Sandra Wanderley Lubambo (swl@cin.ufpe.br, sandra.lubambo@refaz.pe.gov.br, gcv)

Weber Pinto Campos (wpc@cin.ufpe.br, ecdbcf)

1.   Introduction to Intelligent Agents 02/05, 04/05

Jacques

Readings:

Chapters 1, 2 of Russell & Norvig

Chapters 1, 2, 5 of Wooldridge

Outline:

Definition of Artificial Intelligence

Practical Applications of Artificial Intelligence

Tasks and Sub-fields of Artificial Intelligence

Definition of Intelligent Agents

Agents x Objects

Multi-Agent Systems (MAS) x Distributed Systems

Intelligent Agent x Intelligent System

Characteristics of Agent Environments

Agents' Internal Architectures

Slides: IA.ppt

2.  Knowledge-Based Agents 04/05, 09/05

Jacques

Readings:

Sections 7.1, 7.2, 8.3 of Russell & Norvig

Outline:

Knowledge-Based Agent Architectures

Knowledge x Data x Information

Categories of Knowledge

Commitments and Assumptions of Knowledge Representation Languages

Automated Reasoning Tasks

Knowledge Engineering Processes

Slides: KBA.ppt

3. Object-Oriented Knowledge Representation 11/05

Jacques

Readings:

Section 10.2 of Russell & Norvig

Chapter 4 and pp. 163-171 of Eriksson & al.

Outline:

Object-Oriented Knowledge Representation Languages

Semantic Networks

Frames

Frames x Semantic Networks

UML Class Diagrams

UML Object Diagrams

MOF Structural Meta-Knowledge

The UML Meta-Model

UML Activity Diagrams

Case-Study: Representing the Tangram Game with UML Diagrams

UML x Semantic Networks

UML x Frames

Limitations of UML Diagrams

Slides: OOKR.ppt

4. Ontologies 18/05

Jacques

Readings:

Section 10.1, 10.4, 10.5   of Russell & Norvig

Chapter 2 of Fensel

Chapters 2, 6, 7, 9 and Sections 3.3, 3.5, 3.6, 10.1, 10.4, 10.6-10.10 of Warmer & Kleppe

Outline:

Definition of Ontologies

Practical Applications of Ontologies

Typology of Ontologies

Elements of an Ontology

Representing Ontologies with UML: The Object Constraint Language (OCL)

Representing the Tangram Robot Domain with UML and OCL

UML/OCL x Semantic Networks

UML/OCL x Frames

Slides: Onto.ppt

5. UML-OCL Modeling Tools 30/05 & 01/06

Borland Training Staff and Luiz Lacerda, Practical Lectures in Laboratory

Outline

Relevant Functionalities of IBM Rational Software Modeler (IRSM) or Borland Together Designer (BTDes)

Architecture of IRSM or BTD

Creating a Multi-Diagram UML Model

Creating a UML Class Diagram

Adding OCL Constraints

Creating a UML Object Diagram

Creating a UML Component Class Diagram

Creating a UML Component Instance Diagram

Creating a UML Activity Diagram

Linking the Diagrams together

Creating a UML Profile

Using a UML Profile

Verifying the Inter-Diagram Completeness and Consistency

Slides: IRSM.ppt, BTDes.ppt

6. Agent-Oriented Knowledge Representation 06/06, 13/06

Jacques

Readings:

pp. 147-157, 193-203, 239-241, 255-257, 281-288 of Erkisson et al.

Section 10.2 of Warmer & Kleppe

Outline:

UML2 Active Classes and Objects

UML2 Component Class Diagrams

UML2 Component Instance Diagrams

UML Protocol State Machines

UML2 Profiles

A UML2 Profile for Components, Agents and MAS

Case-Study: The Penalty Shot Simulation

Slides: AOKR.ppt

7. Project Topics Presentation 20/06

Jacques

Topics:

1.        A Rollerslam Game Simulator Agent:

2.       Two Different Rollerslam Player Agents:

3.       A Rollerslam Player Agent Reasoning Trace Generator and GUI for Individual Behavior Analysis and Debugging:

4.       A Rollerslam Team Coordination Trace Generator and GUI for Team Work Analysis and Debugging:

Slides: Rollerslam.ppt, ProjectTopics.ppt

8. Exhaustive Search 22/06

Jacques

Readings: Chapter 3 of Russell & Norvig

Outline:

Agent Reasoning as Navigating the Space of Possible Environment States

Formulating an Agent Decision Task as a State Space Search Problem

Incremental x Complete State Formulation

Environments in which State Space Searching Agents Can Effectively Act

Representing the Environment States

Representing the Agent’s Actions Effects on the Environment

Representing the Agent’s Preferences among Environment States

Searching for a Decision Sequence x Executing a Decision Sequence

A Generic Global Exhaustive State Space Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Properties of State Space Search Components

 A Breadth-First Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

Properties

A Uniform-Cost Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

Properties

A Depth-First Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

Properties

A Chronological Backtracking Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

Properties

An Iterative Deepening Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

Properties

A Bi-Directional Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Properties

Component Comparative Table

Avoiding Repeated States

Extending State Space Search Techniques to Partially Observable and/or Non-Deterministic Environments

Slides: ExhaustiveSearch.ppt

9. Heuristic Search 27/06

Eduardo & Patrícia

Readings: Chapter 4 of Russell & Norvig

Outline:

Limitations of Exhaustive State Space Search for Agent Reasoning

Domain-Dependent Pruning Heuristics for Partial State Space Search

A Generic Global Heuristic State Space Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

A Best-First Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

Properties

An A* Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

Properties

An Recursive-Best-First-Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

Properties

Heuristic State Space Pruning Knowledge Representation

Local Search Concepts

A Generic Local Heuristic State Space Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

A Hill-Climbing Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

Properties

Upgrades of Hill-Climbing

A Simulated Annealing Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

Properties

A Local Beam Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

Properties

Local Search in Continuous State Spaces

Online Search

A Generic Online Global Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

An Online Depth-First Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

Properties

A Generic Online Local Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

An Learning Real-Time A* Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

Properties

Component Comparative Table

Slides: HeuristicSearch.ppt

10. Constraint Solving: Problems and Domains 29/06

Jacques

Readings:

Section 5.1 of Russell & Norvig

Chapters 1-2 of Marriott & Stuckey

Chapter 8 of Frühwirth & Abdennadher

Outline:

Agent Reasoning as Solving a System of Constraints over Variables in Various Domains

Example Constraint Systems

The Knowledge Representation Language of Constraint Solving Problems: Sorted Classical First-Order Logic

Specification of Constraint Solving Components

Variable Substitution

Constraint Satisfaction

Absolute Implication and Equivalence

Normalization

Absolute Simplification

Projection

Relative Implication, Equivalence and Simplification

Local Propagation

Optimization

Finite Domain Variable Labeling

Properties of Constraint Solvers

Soft Constraints

Primitive high-arity constraints

Constraint Domains

Practical Applications of Constraint Solvers

Slides: CSPD.ppt

11. Constraint Solving as Search 04/07, 13/07

Gustavo & Paulo

Readings:

Sections 5.2-5.5 of Russell & Norvig

Sections 6.1-6.2, 6.6 of Dechter

Outline:

Finite Domain Constraint Solving as State Space Search

A Backtracking Global Search Component for FD CSP

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

Properties

Domain-Independent Ordering Heuristics in Exhaustive FDCS State Search

Knowledge Representation for Ordering Heuristics: CSP Graph

A Chronological Backtracking FD CSP Global Search Component with Forward Checking

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

K-consistency

A Chronological Backtracking FD CSP Global Search Component with Arc Consistency Constraint Propagation

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

A Conflict-Directed Backjumping FD CSP Local Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

A Min-Conflict FD CSP Local Search Component

UML Component Specification Class Diagram with OCL Constraints

UML Component Realization Class Diagram with OCL Constraints

UML Component Realization Activity Diagram with OCL Expressions

Running Example

Component Comparative Table

Slides: CSS.ppt

Advising:

Questions: 13:00-14:00

Abduction I: 18:30-19:30

Belief Update I:  19:30-20:30

12: GUI Modeling with UML 06/07

1.      1.      §       Luiz

2.     2.     §       Readings:

3.     3.     §       A UML Profile for GUI Layout: http://www.bitfolge.de/pubs/thesis/index.html

4.     4.     §       Chapter 6 of Software Engineering for Adaptive Hypermedia Systems: http://www.pst.informatik.uni-muenchen.de/ personen/kochn/PhDThesisNoraKoch.pdf

5.     5.     §       The Authoring Process of the UML-based Web Engineering Approach: http://www.pst.informatik.uni-muenchen.de/ publications/uwe_iwwost01.pdf

6.     6.     §       Outline:

7.     7.     §       UMLWE notation and method

8.     8.     §       UML profile for GUI layout

9.     9.     §       KobrA 2.0 GUI Engineering

10.  10.  §       GUI Component Specification Artifacts

11.   11.   §       GUI Aspects Specification Artifacts

12.  12.  §       GUI Component Realization Artifacts

13.  13.  §       GUI Aspects Specification Artifacts

14.  14.  §       Slides: GUIModeling.ppt

13. Propositional Classical Deduction 11/07

Jacques

Readings: Sections 7.3-7.7 of Russell & Norvig

Outline

Logical Knowledge Representation and Reasoning

Possible Worlds and Models

Logical Reasoning Services

Logically Reasoning Agents

Properties of Logics and Logical Inference Engines

Classical Full Propositional Logic (CFPL)

CFPL Syntax

CFPL Semantics

CFPL Properties

Inference Methods for CFPL

Truth-Table Calculation

Model Checking

Application of Inference Rules

Resolution Strategies

Propositional Deduction as Boolean Constraint Solving

A CHRV backtracking solver for satisfiability

A CHRV backtracking solver for entailment

A Min-Confict Satisfiability Solver

Practical Applications of CFPL Theorem Proving

Horn Propositional Logic

HPL Syntax

HPL Properties

Inference Methods for HPL

Forward-Chaining

Reusing a CHRV Engine for Forward Chaining inference engine for HPL knowledge base

Backward-Chaining

CHRV as a backward inference engine for HPL knowledge base

Practical Applications of Inference in HPL

Slides: PCD.ppt

Advising:

Project: 13:00-14:00

Abduction II:  18:30-19:30

Belief Update II: 19:30-20:30

14. First-Order Classical Deduction 13/07

Jacques

Readings: Sections 8.1-8.2, 8.4, 9.1-9.2, 9.5 of Russell & Norvig

Outline

Classical Full First-Order Logic (CFFOL)

Syntax

Semantics

Properties

Inference Methods for CFFOL

Propositionalization

Inference Rules for Quantifiers

Unification and Lifted Inference Rules

Inference Rules for Equality

Reusing a CHRV Engine for Resolution and Refutation Based Theorem Proving in CFFOL

Practical Applications of CFFOL Theorem Proving

First-Order Horn Logic (FOHL)

Syntax

Properties

Inference Methods for FOHL

Lifting Forward and Backward Chaining

Reusing a CHRV Engine for Forward and Backward Chaining Inference with FOHL Knowledge Bases

Practical Applications of Inference in FOHL

Slides: FOCD.ppt

Advising:

Bayesian Reasoning I: 18:30-19:30

Object-Oriented Rules and Inheritance I: 19:30-20:30

15.  Project Deliverables and Feedback 1 13/07

Version1.0 of Artifacts for UML Model Component Specification

Provided and Required Interfaces with OCL Pre and Post-conditions

Class Diagrams with OCL Constraints of Interface Operation Parameters

Protocol State Machine

Version1.0 of Additional Artifacts for GUI Component Specification

Use Cases

Screen Layout using ...

Navigation Structure using ...

 

18/07

Advising:

Bayesian Reasoning I: 17:30-18:30

Abduction II: 18:30-19:30
Belief Update II:
19:30-20:30

 

16. Rule-Based Constraint Solving 20/07

Jacques

Readings:

Section 4 of Theory and Practice of Constraint Handling Rules

Sections 5.1, 5.2.3-5.2.6 of Rule-Based Constraint Programming: Theory and Practice

Chapters 9, 11, 12, 13 of Frühwirth & Abdennadher

CHREX: a Java-Embedded Engine for CHRV

Outline

CHR

Syntax

Declarative Semantics in Classical First-Order Logic and its Limitations

Operational Semantics

Provided Constraint Solving Services

Data-Driven x Goal-Driven x Hybrid Rule-Based Reasoning

Matching x Unification

Properties of CHR Bases

Limitations of CHR as a Rule-Based Constraint Solving Language Extension

Limitations of CHR as a Knowledge Representation Language

Limitations of CHR as a Programming Language

CHRV

Syntax Extension

Declarative Semantics in Classical First-Order Logic and its Limitations

Operational Semantics Extension

Additional Provided Constraint Solving Services

Properties of CHRV

Limitations of CHRV as a Rule-Based Constraint Solving Language Extension

Limitations of CHRV as a Knowledge Representation Language

Limitations of CHRV as a Programming Language

Example CHRV Solvers:

Boolean Domain: Digital Circuit Fault Diagnosis in CHRV

Symbolic Finite Domain: Map coloring in CHRV

Numeric Finite Domain: Interval Integer Bounds Consistency CHRV

Real Domain: Mortgage Calculation in CHRV

CHR Inference Engines

Pratical Applications of CHR and CHR Engines

Slides: CHR.ppt

17.   Rule-Based Deduction 20/07

Jacques

Readings:

Sections 9.3, 9.4 of Russell & Norvig

Production Systems and Rewrite Systems

Sections 2.2-2.4, 3.1, 3.3, 3.6 of Nilsson & Maluszynski

Outline

Term Rewriting Systems

Syntax

Recursive Unification

Operational Semantics

Conflict Resolution Heuristics

Properties of Term Rewriting Rule Bases

Practical Applications

Reusing a CHRV Engine as a Term Rewriting Engine

Limitations of Term Rewriting Systems as Inference Engines

Limitations of Term Rewriting Systems as Programming Languages

Production Systems

Syntax

Operational Semantics

Conflict Resolution Heuristics

Properties of Production Rule Bases

Practical Applications

Reusing a CHRV Engine as a Production Rule Engine

Production Systems x Term Rewriting Systems

Production Systems x Lifted Forward Chaining

Limitations of Production Rule Languages as Knowledge Representation Language

Limitations of Production Rule Languages as Programming Languages

Limitations of Production Systems as Inference Engines

Pure Prolog and Logic Programming

The Logic Programming Paradigm

Syntax

Intensional Declarative Semantics (Clark’s Completion)

Translating a Pure Prolog Program into a CHRV Program

Extensional Declarative Semantics

Operational Semantics

Properties of Pure Prolog Rule Bases

Pure Prolog Inference x Lifted Backward Chaining

Pure Prolog Inference x Lifted Forward Chaining

Pure Prolog Inference x SLD Resolution

Pure Prolog x CHRV

Pure Prolog x Production Systems

Pure Prolog x Term Rewriting Systems

Pure Prolog x CFFOL Theorem Provers

Limitations of Pure Prolog as a Knowledge Representation Language

Limitations of Standard Prolog Engines as Inference Engines

Limitations of Pure Prolog as a Programming Language

Extensions of Pure Prolog

Tabled Logic Programming (TLP)

TLP x CHRV

Constraint Logic Programming (CLP)

CLP x CHRV

Slides: RBD.ppt

Advising:

Decision Theoretic Reasoning I: 17:00-18:00

Bayesian Reasoning II: 18:30-19:30
Inheritance II:
19:30-20:30

18.  Abduction, Default Reasoning and Belief Revision 27/07

Daniel, Priscila & João

Readings:

Sections 10.7-10.8 of Russell & Norvig

Chapter 4 of Nilsson & Maluszynski (skip the proofs)

Sections 1, 2, 5, 6 of CHICA: an Abductive Planning System Based on the Event Calculus

Sections 1-3, 4.1, 5.1, 8 of The Role of Abduction in Logic Programming

Sections 5.2.1-5.2.2 of Rule-Based Constraint Programming: Theory and Practice

Outline

Default Reasoning

Default Logic

General Logic Programs (GLP) and Negation As Failure (NAF)

Syntax

Intensional Declarative Semantics in CFFOL (Clark’s Completion) and its Limitations

Extensional Declarative Answer Set Semantics

Extensional Declarative Well-Founded Semantics (WFS)

Operational Semantics of WFS: SLG Resolution

Limitations of SLG Resolution: Floundering

NAF with Forward Chaining

Default Logic x NAF

Positive Abductive Logic Programs (PALP)

Syntax

Bias

Operational Semantics: SLDA

Default Reasoning as Positive Abduction

Default x Non-Default Abducibles

Translating a GLP into a PALP

Translating a PALP into a GLP

General Abductive Logic Programs (GALP)

Syntax

Bias

Operational Semantics: SLDNFA

Belief Revision and Truth Maintenance

Belief Revision Services

AGM Belief Revision Postulates

The Needs for Truth Maintenance

Justification-based Truth Maintenance Systems (JTMS)

JTMS x NAF

Assumption-based Truth Maintenance Systems (ATMS)

ATMS x JTMS

Reusing the GALP Abductive Proof Procedure to integrate JTMS and ATMS

Adbuction in CHRV

Translating a GALP into a CHRV Base

Truth Maintenance for CHR Inference

Slides:  ADRBR.ppt

19.   Belief Update and Temporal Reasoning 27/07

Luiz & Rafael

Readings:

Section 10.3 do Russell & Norvig

Sections 3, 4, 7, 8, 9, 10 of CHICA: an Abductive Planning System Based on the Event Calculus

Sections 1-4, 7.8, 7.9 and pp. 117-120 of Transaction Logic Programming

A Unified View of Belief Revision and Update (skip the proofs)

Outline

Reasoning of Actions and Changes in a Dynamic Environment

Belief Updates

Temporal Projection

Planning

Illustrative Case-Study for Reasoning of Actions and Changes: the Block World

Overview of Knowledge Representation Languages for Reasoning about Actions and Changes

The Situation Calculus

Syntax

The Representational Frame Problem

The Inferential Frame Problem

The Ramification Problem

The Qualification Problem

Representing the Block World with the Situation Calculus

Implementing the Situation Calculus Specification of the Block World using CHRV Engine as CFFOL Theorem Prover

Limitations of the Situation Calculus

 

The Event Calculus

Syntax

Representing the Block World with the Event Calculus

Implementing the Event Calculus Specification of the Block World using CHRV Engine as a GALP Engine

Limitations of the Event Calculus

Transaction Logic

Purposes

Syntax

Representing the Block World in Transaction Logic

Limitations of Transaction Logic as a Knowledge Representation Formalism to Reason About Actions and Changes

Representing Actions and Changes Directly as CHRV Rules

Representing the Block World Directly by CHRV Rules

Limitations of the Approach

Comparative Table of the Approaches

Slides: BUTR.ppt

20.  Object-Oriented Rules and Inheritance 01/08

Marcos Aurelio and Fabrício Teles (Student Seminar 6)

Readings:

Deductive and Object Data Languages: a Quest for Integration

Sections 1-3 of Logical Foundations of Object-Oriented and Frame-Based Languages

Sections 2, 6 and 11.1 of A Model Theory for Non-monotonic Multiple Value and Code Inheritance in Object-Oriented Knowledge Bases

CHORD: Constraint Handling Object-Oriented Rules

Outline:

Knowledge Representation and Programming Language Paradigms

Limitations of Purely Relational Rule Languages

Limitations of Purely Object-Oriented Languages

Design Options for Hybrid Object-Relational Rule Languages

CHORD: Extending CHRV with High-Order Object-Oriented Constraints

CHORD syntax extensions (from Frame Logic):

Object-Oriented Logical Atoms

Object-Oriented Logical Molecules

Object-Oriented Path Expressions

A Typology of Inheritance:

Signature x Value x Code Inheritance

Simple Inheritance x Single Source Multiple Inheritance x Multiple Source Inheritance

Inheritance with x without Overriding

Monotonic x Non-Monotonic Inheritance

Complex Interferences between Deduction and Inheritance

Yang’s Inheritance Postulates

Monotonic Inheritance as Deduction

Non-Monotonic Inheritance as Belief Revision

CHORD Inheritance x UML Inheritance

CHORD Inheritance x Java Inheritance

Case-Study in Object-Oriented Rule-Based Knowledge Representation: the Tangram Game in CHORD

Slides: OORI.ppt

Advising:

Project Agent  Group: 13:00-14:00

Project Agent Analysis and Debugging Group Group: 18:30-19:30

Project Environment Group: 19:30-20:30

Project Environment Analysis and Debugging Group 20:30-21:30

21.  Propositional Bayesian Reasoning 03/08

Victor & Ricardo

Readings: Chapter 13 and Sections 14.1-14.5, 15.1-15.5 of Russell & Norvig

Outline:

Uncertain Knowledge Representation

Probability Axioms and Bayes Rule

Probabilistic using Full-Joint Distributions (FJD)

An UML Component for FJD-Based Probabilistic Inference

Exploring the Wumpus World Using FJD-Based Probabilistic Inference

Bayesian Networks

Abstract Syntax

Illustrative Example

Semantics

A UML Component for Variable Elimination (VE) Based Exact Inference in Bayesian Networks

Representing Bayesian Networks and the VE Component as a CHORD Base

Illustrative example run of the VE Component

Time and Uncertainty

Stationary Processes and the Markov Assumption

Probabilistic Temporal Reasoning Services

Dynamic Bayesian Networks (DBN)

Abstract Syntax

Illustrative Example

Exact Inference in DBN

A UML Component for Particle Filtering

Illustrative example run of the Particle Filtering Component

Slides: PBR.ppt

22.  Propositional Optimization and Decision-Theoretic Reasoning 03/08

Uilma & Sandra

Readings:  Chapter 16 and Sections 17.1-17.4 of Russell & Norvig

Outline:

Utility Theory

Decision Networks

Abstract Syntax

Illustrative Example

Optimization using Decision Networks

The Value of Information

Decision Theoretic Expert Systems

Sequential Decision Problems

Markov Decision Process

Abstract Syntax

Fully Observable x Partially Observable MDP

Illustrative Example

A UML Component for Value Iteration

Illustrative example run of Value Iteration Component

Decision-Theoretic Agents

Slides: PODTR.ppt

23.  Project Deliverables and Feedback 2 08/08

Version 1.0 of Artifacts for UML Model Component Realization

For imperative components to be implemented in Java

Class Diagrams with OCL Constraints

Activity Diagrams with OCL Expressions

For declarative components to be implemented in CHORD

Class Diagrams

OCL Expressions

Version 1.0 of Additional Artifacts for GUI Component Realization

Class Diagrams with OCL Constraints, Including Interfaces of Graphics API

Activity Diagrams with OCL Opaque Expressions Calling Operation of the Graphics API

Version 2.0 of Artifacts for UML Model Component Specification

Provided and Required Interfaces with OCL Pre and Post-conditions

Class Diagrams with OCL Constraints of the Interfaces’ Operation Parameters

Protocol State Machine with OCL Expressions

Version 2.0 of Additional Artifacts for GUI Component Specification

Use Cases

Screen Layout using ...

Navigation Structure using ...

Exam: 15/08
07:15-08:00 Reposition
08:00-10:00 Final

24.  Semantic Web Infrastructure 17/08

Fred Freitas

Readings:

http://www.scientificamerican.com/article.cfm?articleID=00048144-10D2-1C70-84A9809EC588EF21&pageNumber=1&catID=2

http://www.w3schools.com/xml/xml_whatis.asp

http://www.w3schools.com/xml/xml_syntax.asp

http://www.w3schools.com/xml/xml_elements.asp

http://www.w3schools.com/xml/xml_attributes.asp

http://www.w3schools.com/xml/xml_namespaces.asp

http://www.w3schools.com/schema/schema_intro.asp

http://www.w3schools.com/schema/schema_why.asp

http://www.w3schools.com/schema/schema_schema.asp

http://www.w3schools.com/schema/schema_simple.asp

http://www.w3schools.com/schema/schema_simple_attributes.asp

http://www.w3schools.com/schema/schema_facets.asp

http://www.w3schools.com/schema/schema_complex.asp

http://www.w3schools.com/schema/schema_dtypes_string.asp

http://www.w3schools.com/schema/schema_dtypes_date.asp

http://www.w3schools.com/schema/schema_dtypes_numeric.asp

http://www.w3schools.com/schema/schema_dtypes_misc.asp

http://www.w3schools.com/schema/schema_elements_ref.asp

http://www.w3schools.com/rdf/rdf_intro.asp

http://www.w3schools.com/rdf/rdf_rules.asp

http://www.w3schools.com/rdf/rdf_example.asp

http://www.w3schools.com/rdf/rdf_main.asp

http://www.w3schools.com/rdf/rdf_containers.asp

http://www.w3schools.com/rdf/rdf_collections.asp

http://www.w3schools.com/rdf/rdf_schema.asp

http://www.w3schools.com/rdf/rdf_reference.asp

http://www.w3schools.com/rdf/rdf_owl.asp

http://www.w3schools.com/webservices/ws_intro.asp

http://www.w3schools.com/webservices/ws_why.asp

http://www.w3schools.com/webservices/ws_platform.asp

http://www.w3schools.com/webservices/ws_example.asp

http://www.w3schools.com/webservices/ws_use.asp

http://www.w3schools.com/soap/soap_intro.asp

http://www.w3schools.com/soap/soap_syntax.asp

http://www.w3schools.com/soap/soap_envelope.asp

http://www.w3schools.com/soap/soap_header.asp

http://www.w3schools.com/soap/soap_body.asp

http://www.w3schools.com/soap/soap_example.asp

http://www.w3schools.com/wsdl/wsdl_intro.asp

http://www.w3schools.com/wsdl/wsdl_documents.asp

http://www.w3schools.com/wsdl/wsdl_ports.asp

http://www.w3schools.com/wsdl/wsdl_binding.asp

http://www.w3schools.com/wsdl/wsdl_uddi.asp

http://www.w3schools.com/wsdl/wsdl_syntax.asp

http://www.w3schools.com/semweb/default.asp

http://www.w3schools.com/semweb/semantic_example.asp

Outline:

Semantic Web Vision

Semantic Web Layers

eXtensible Markup Language (XML)

XML Schema

Representing the Tangram Game in XML/XMLS

Resource Description Framework (RDF)

RDF x XML

RDF Schema

Representing the Tangram Game in RDF/RDFS

RDFS x XMLS

Web Services

Web Service Description Language (WDLS)

The Universal Description, Discovery and Integration (UDDI) Protocol

Simple Object Access Protocol (SOAP)

Publishing the Tangram Robot as a Web Service

Slides: SemanticWebInfra.ppt

25.  Semantic Web Ontology and Service Languages 24/08

Fred Freitas

Readings

pp. 353-354 of Russell & Norvig

An Introduction to Description Logics

From SHIQ and RDF to OWL: the Making of a Web Ontology Language

http://www.w3.org/Submission/OWL-S/

http://www.w3.org/Submission/SWSF-SWSL/

Outline:

Description Logics

Key ideas

Commitments and Properties

Language Family Variations

Set Theoretic Declarative Semantics

Classical First-Order Logic Declarative Semantics

The Description Logics SHIF(D) and SHOIN(D)

MOF Abstract Syntax

Textual Concrete Syntax

Representing the Tangram Game in SHIF(D) and SHOIN(D)

Limitations of SHIF(D) and SHOIN(D) as Knowledge Representation Languages

Inference Engines for SHIF(D) and SHOIN(D)

Translating SHIF(D) and SHOIN(D) Knowledge Bases into CHORD Knowledge Bases

Comparing SHIF(D) and SHOIN(D) with CHORD and UML/OCL

The Ontology Web Language (OWL)

OWL Lite

OWL DL

OWL Full

OWL-S: Representing Web Services in OWL

Semantic Web Service Language (SWSL)

MOF Abstract Syntax

Textual Concrete Syntax

Representing the Tangram Game in  SWSL

Inference Engines for SWSL

Limitations of SWSL as a Knowledge Representation Language

Translating SHIF(D) and SHOIN(D) Knowledge Bases into CHORD Knowledge Bases

SWSL x CHORD

SWSL x UML/OCL

SWLS x OWL-S

Slides: OWLSWSL.ppt

26.  Final Project Presentation 17/10

Version 2.0 of Artifacts for Java and CHORD Components

Java Code

CHORD Code

Component Integration Test Suite

Component Integration Test Suite Results

Demo of Rollerslam Games

Demo of Rollerslam Simulator Agent Debugging and Analysis

Demo of Rollerslam Player Agent Individual Behavior Debugging and Analysis

Demo of Rollerslam Team Coordination Debugging and Analysis

Version 2.1 of Artifacts for UML Model Component Realization

For imperative components to be implemented in Java

Class Diagrams with OCL Constraints

Activity Diagrams with OCL Expressions

For declarative components to be implemented in CHORD

Class Diagrams

OCL Expressions

Version 2.1 of Additional Artifacts for GUI Component Realization

Class Diagrams with OCL Constraints, Including Interfaces of Graphics API

Activity Diagrams with OCL Opaque Expressions Calling Operation of the Graphics API

Version 2.2 of Artifacts for UML Model Component Specification

Provided and Required Interfaces with OCL Pre and Post-conditions

Class Diagrams with OCL Constraints of the Interfaces’ Operation Parameters

Protocol State Machine with OCL Expressions

Version 2.2 of Additional Artifacts for GUI Component Specification

Use Cases

Screen Layout using ...

Navigation Structure using ...