Knowledge-based systems (semantic point of view)

the last modification: Dec 14, 2009

ABOUT THIS COURSE

Main topics

Knowledge-based system: characteristic features. Reasoning (inference). Logical languages as knowledge representation languages. Semantic specification of the consequence operator in various logics. Nonmonotonic reasoning and knowledge representation. Logic programming, answer set programming and knowledge representaation. Planning as a typical application in the field of knowledge-based systems.

Project: each student has to specify a planning task for a domain and to elaborate its specification in a logic progrmming language.

Exercises in DLV^K

Requirements

The final grade depends on: Additional assesments are available in minitests during classes (max. 2%).

A ... at least 85%

B ... at least 75%

C ... at least 65%

D ... at least 5%

E ... at least 45%

Roadmap

Sep 22

basic intuitions - knowledge based system, reasoning, the planning problem; planning with incomplete observations/knowledge, unexpected events, indeterministic actions and a general notion of a goal; a semantic approach to planning

Sep 29

reacop: propositiopnal loogic, interpretation, model, entailment; logic programming within propositional language - definite logic program, the least model, T_P operator

literature: Inteligencia ako vypocet, appendices B,D, chapter 2.3

Oct 6

negation as finite failure, stable model semantics

literature: Inteligencia ako vypocet, appendix B, ch.6.2; Anger, Konczak, Linke, Schaub: Answer set programming

Oct 13

planning domain, planning problem; encoding planning problem in answer set programming; stratified logic programs, locally stratified logic priograms

literature: Subrahmanian, Zaniolo: Relating stable models and AI planing domains ; Inteligencia ako vypocet, ch.6.1

Oct 20

planning poblem in ASP continued; surprises, rigid actions

Oct 27

dynamic logic programming (planning in a changing environment), EVOLP, reactive planning

literature:

Nov 3

planning - concurrent actions, indirect effects; literature Lifschitz Answer sets programming and plans generation
Nov 10
defeasible logic programing
Nov 24
planning with defesible logic programming
  • Simari, Garcia, Capobianco: Actions, Planning and Defeasible Reasoning

    modularity - development of KB; action language

    Dec 1

    planning and preferences

    Dec 8

    automated planning; Handbook of KR, ch. 22

    Dec 15

    knowledge-based systems - a survey; Handbook of KR,ch. 25

    Results

    minitest: M

    homework: H

    trest: T

    final report: F

    name M1310 T
    Adam 2 10
    Kocan 2 10

    back

    blog

    assessment of blog contributions
    both the quantity and quakity of contributions is evaluated

    QUALITY

    each contribution will be marked by grades from the set 1,2,3; if a contribution is not marked by one of those grades, it will not be considered

    QUANTITY

    Martin Homola's instructions:
    Starting with Blogging
    Blogging is best used for expressing, summarizing, discussing by the learners of what they have learned during your course. This discussion ought to be subjective and opinion based. Possible assignments include: It is advisable for lecturers and other teaching staff of your course to create blog accounts within the portal and to contribute to the blogging assignment by: In order to track your students content, think of a distinctive tag related to your course. Ask your students to include always this tag when they post an article related to the course.

    WE WILL USE THE TAG szzs09

    Instruction for Students
    The proposed structure of your contrbutions is as follows:

    < post ... >

    < title > ...< /title >

    < content > ... < / content >

    < tags > < tag > szzs09 < / tag >

    < tag > ...< / tag >

    ...

    < / tags >

    < / post >

    A simple list of instructions you may want to consider:

    1. Sign a written learning agreement in which you agree that you will publish on a publicly available blog, under your real name.
    2. Register to the blog portal. blog.matfyz.sk
    3. Configure your blog, add your photo (not necessarily real photo of you, but it looks more professional if you have a real one), fill in your real name and short statement about you and your professional/study interests.
    4. If you want to publish an article related to the course, that should be taken into account (read) by the lecturers, use a specific tag (invent one as suggested above) on your article.
    5. Publish regularly.
    6. Feel encouraged to comment under the articles of others and discuss their ideas and opinions.
    7. Fell free to express feedback also on the topic of the course, the syllabus, organization of the course and of your studies, etc.
    8. It's OK to write also articles that are not connected with the course at all.

      back

      PROJECT

      rough specification

      The goal of the project is to use a language of logic programing which is suitable for representing incomplete knowledge and to apply it to a planning problem.

      It is preferred to choose a planning problem in a dynamically evolving domain with unexpected events. Such domains require usually alternative plans, so-called beta-plans and revisions.

      a specification of the first hoework

      to suggest a planning problem for a suitable domain;

      specify a goal, aan initial situation, a set of actions, a set of possible situations; present a proposal, able to evolve froma simple, deterministic planning problem weith a complete information to a problem with some kinds of indeterminism, incompleteness and uncertainty

      students' projects

      blog.matfyz.sk

      contibutions with the tag szzs09

      evaluation of blog contributions

      name 1st 2nd 3th 4th 5th 6th
      Adam 1 1 1 1 1 1
      Kocan 1

      back

      LINKS

      Esra Erdem, experiments

      back

      PAPERS, TEXTBOOKS, OTHER TEXTS

      basic papers

      Inteligence as a computation (in Slovak)

      download: pdf , ps

      Dix, Brewka: Knowledge representation with logic programs

      download: pdf ps

      Chitta Baral: Knowledge representation, reasoning and declarative problem solving

      Oxford University Press 2003; download slides

      Thomas Eiter:

      download Part 1 Part 2

      Anger, Konczak, Linke, Schaub: Answer set programming

      download ps pdf

      other papers and presentatiopns

      back

      FROM THE HISTORY OF THE COURSE

      2009 (Spring)

      Roadmap

      Feb 9

      interpretation, model, Herbrand interpretation, Herbrand model, logical consequence (for propositional logic)

      definite propositional logic program, the least model; CWA

      literature: Inteligencia ako vypocet, appendices B,D, chapter 2.3

      homework: Informal description of a program (an agent), which is able to propose plans. (What types of knowledge are needed, what properties of the specified knowledge types are appropriate, what processes are required for knowledge processing?)

      Feb 16

      first-order language, semantics; skolemization, first order logic programs, semantic problems of negation, normal and extended logic programs, stable mddel; answer set programming

      literature: Inteligencia ako vypocet, appendix B, ch.6.2; Anger, Konczak, Linke, Schaub: Answer set programming

      planning task

      homework: Informal descrription of a domain for a planning task

      Feb 23

      planning domain, planning problem; encoding planning problem in answer set programming; stratified logic programs, locally stratified logic priograms

      literature: Subrahmanian, Zaniolo: Relating stable models and AI planing domains ; Inteligencia ako vypocet, ch.6.1

      homework: a formal specification of your planning task - planning operators (name, preconditions, add-list, delete-list); initial state; goal (it is assumed that this specification is only an approximation, a simplification of your intended planning task

      Mar 2

      a presentation of homeworks; exercise - stable models; planning: surprises and rigid actions; minitest

      homework: introducing surprises and/or rigid actions into your planning tasks

      Mar 9

      modular development of a knowledge base in the frame of logic programming; literature: Gelfond: Going places - notes on a modular development of knowledge about travel

      Mar 16

      planning - concurrent actions, indirect effects; literature Lifschitz Answer sets programming and plans generation

      Mar 23

      logic programs with preferences; literature
      • Sakama, Inoue Prioritizxed logic programming and its applications to commonsense reasoning
      • Delgrande et al. A framdework for compiling preferences in logic programs
      • Schaub What is your preference? And how to express and implement it in logic programming
      • Sefranek Preferred answer sets supported by arguments

      Apr 6

      multidimensional dynamic logic programming, EVOLP, planning

      literature:

      Apr 13

      defeasible logic programming and planning

      Apr 20

      automated planning; Handbook of KR, ch. 22

      Apr 27

      knowledge-based stsrems - a survey

      Results

      minitest: M

      homework: H

      trest: T

      final report: F
      name M0209 H0209 M0216 H0216 H0223 M0302 H0302 H0309 T0309 HO0316 H0323 H0406 H0420 H0427 T SUM
      Grega 1% 2% 4% 0.75% 4% 4% 6% 4% 4% 10% 39.75%
      Kovac 1% 4% 2% 4% 4% 2% 4% 4% 12% 4% 4% 4% 4% 4% 10% 67%
      Kralik 1.5% 4% 4% 4% 1.5% 4% 4% 12% 4% 4% 4% 4% 4% 10% 65%
      Vince 2% 4% 2% 4% 2% 4% 4% 12% 4% 4% 4% 4% 4% 10% 64%
      Sarkozi 1% 4% 4% 6% 4% 4% 4% 4% 10% 41%
      Haviarova 1% 4% 4% 4% 1.75% 4% 4% 8% 4% 4% 4% 4% 4% 10% 60.75%
      Arbet 1% 4% 2% 4% 4% 0.25% 4% 4% 5% 10% 38.25%
      Hornakova 1% 2% 4% 4% 1.75% 4% 4% 6% 4% 4% 4% 4% 10% 52.75%
      Mikulas 1.5% 4% 4% 4% 2% 4% 4% 4% 4% 10% 41.5%
      Kravec 4% 1.75% 4% 4% 10% 4% 4% 4% 4% 4% 10% 53.75%

      PROJECT

      students' projects

      2008

      Roadmap

      Feb 13

      Knowledge-based systems. Reasoning as a fundamental feature from our point of view (with an accent on a semantic specification of reasoning).

      Recap of the semantics of a first order language (interpretation, truth, model, entailment). Logic programming view on databases. Semantics of definite logic programs.

      Literature: Sefranek, chapter 2.1, 2.3, appendices B and D

      Feb 20

      Negation in logic programming. Stable model (answer set) semantics. Extended, disjunctive programs and other generalizations.

      Literature: Brewka, Dix; Sefranek chapter 6.2

      Feb 27

      NP-completeness of the problem of existence of a stable model of a finite propostional logic program. Literature Dantsin et al.

      Planning problems and stable model semantics acording to Subrahmanian and Zaniolo .

      Startified and locally stratified logic programs. Literature: Sefranek, chap. 6.1.

      Mar 5

      Subrahmanian, Zaniolo, continued. An example of a planning problem.

      Mar 19

      another approach (actions with indirect effects; indirect description of executability of actions) to planning in the frame of answer set programming - Lifschitz: Answer set programming and plan generation

      Mar 26

      dynamic logic programming, EVOLP; planning under evolving knowledge Literature:

      Apr 2

      default logic; literature - Sefranek, 4.1.1, 4.1.2

      Apr 16

      planning with defeasible logic progrmming; literature

      Apr 23

      preferences, prioritized logic programs; literature: Delgrande, Schaub, Tompits

      Apr 30

      diagnosing plan execution, abduction;

      literature:

      links to student projects

      Projects, Spring 2007

      Roadmap

      Default theories. Literature: Sefranek, chap. 4.1

      Mar 14

      Dynamic logic programming, EVOLP. Literature:

      Mar 21

      Planning. Literature:

      Mar 28

      Computational aspects of nonmonotonic reasoning. Literature:

      Apr 4

      Project seminar. Hierarchical networks. Revisions. Literature: Sefranek, chap. 4.2, 7.1

      Apr 11

      Project seminar. Induction. Literature: Sefranek, chap. 5.1.

      Apr 18

      Project seminar. Induction, abduction. Literature: Sefranek, chap. 5

      May 2

      Preferred answer sets of extended logic programs. Literature: Torsten Schaub: What's your preference? And how to express and implement it in logic programming !

      May 9

      Project seminar. Presentation of all projects.