Knowledge Representation and Reasoning (KR): a vibrant subfield of ai jia You

Download 92.5 Kb.
Hajmi92.5 Kb.

Knowledge Representation and Reasoning (KR): A vibrant subfield of AI Jia You

Related Field

  • Computational logic
  • Constraints/Constraint Programming
  • Declarative programming
  • Logic programming (not Prolog)

Intelligent Agent

  • Can acquire knowledge through various means such as learning from experience, observations, reading, etc., and
  • Can reason with this knowledge to make plans, explain observations, achieve goals, etc.

To learn knowledge and to reason with it

  • we need to know how to represent knowledge in a computer readable format.
  • McCarthy 1959 in Programs with commonsense:
  • “In order for a program to be capable of learning something it must first be capable of being told it.”

What does KR entail?

  • We need languages and corresponding methodologies to represent various kinds of knowledge, and be able to reason with it.
  • Forms of reasoning: deduction, abduction, induction, default reasoning, common-sense reasoning, …

Importance of Inventing Suitable KR Languages

  • Development of a suitable knowledge representation language and methodology is as important to AI systems
  • as
  • Calculus is to Physics and Engineering.

What basic properties should a suitable “calculus” of KR possess?

  • have a simple and intuitive syntax and semantics;
  • allow us to withdraw our conclusions;
  • allow us to represent and reason with incomplete information; and
  • allow us to express and answer problem solving queries such as planning queries, explanation queries and diagnostic queries.

Inadequacy of first order logic

  • It is monotonic: More information one has, more consequences one gets.
  • Human communication is typically based on closed world assumption.

An Example of Closed World Assumption

  • ground-wet  watering.
  • ground-wet  raining.
  • In an open world, there could be other reasons that cause ground-wet (we simply don’t know, or have not said).
  • But in a closed world, what we said is all that we know, for Horn clauses, this is called Clark Completion.
  • Ground-wet  watering raining

This is to say …

  • We need to study the semantics of KR languages.

Answer Set Programming (ASP)

  • A program is a collection of rules of form:
  • A  B1, …, Bm, not C1, …, not Cn
  • where A, Bj and Ck are atoms.
  • Intended “models” of a program are called answer sets.

Does tweety fly?

  • fly(X)  bird(X), not ab(X).
  • ab(X)  penguin(X).
  • bird(X)  penguin(X).
  • bird(tweety).
    • We conclude fly(tweety).
  • But if we add
    • penguin(tweety).
    • We can no longer conclude fly(tweety)

Weight and Cardinality Constraints

  • An important extension, where an atom can be a weight/cardinality constraint:
  • L {a1 = w1, …, an = wn } U
  • where ai are atoms and wj are weights.
  • E.g. Given a set = {b,c,d,e}, to express all subsets containing a, we can write
  • a 
  • 0 {b,c,d,e} 4  a.


  • Given a map and k colors, is it possible to color the map so that no adjacent regions have the same color?
  • Represented by a graph:
  • Each vertex is colored with exactly one color;
  • no two vertices connected by an edge have the same color.

A program solving 3-colorability

  • % Each vertex is colored with exactly one color:
  • 1 {color(V,red), color(V,blue),color(V,yellow) } 1 
  • vertex(V).
  • % No adjacent vertexes may be colored with the same color.
  • vertex(V), vertex(U), edge(V,U), isAcolor(C),
  • color(V,C), color(U,C).

Hamiltonian Cycle

  • Given a set of facts defining the vertices and edges of a directed graph and a starting vertex v0, find a path that visits every vertex exactly once.
  • Any subset of edges could be on such a path
  • 0 {in(U,V) : edge(U,V) }.
  • A path must be chained to form a sequence over the edges on it:
  • reachable(V)  in(v0,V).
  • reachable(V)  reachable(U), in(U,V).
  • A vertex cannot be visited more than once.
  •  edge(U,V), in(U,V), edge(W,V), in(W,V), U  W.
  •  edge(U,V), in(U,V), edge(U,W), in(U,W), V  W.
  • Don’t forget to say that every vertex must be reached.
  •  vertex(U), not reachable(U).


  • Represented by a program that expresses:
  • Action choice
  • which action(s) should be chosen at each state
  • Affected objects
  • the affected objects by an action
  • Effects
  • if affected, what are the effects
  • Frame axioms
  • if not affected by any action at a state, the fluents that hold at the current state remain to hold in the next state.

Is ASP a good candidate?

  • Simple syntax
  • It is non-monotonic.
  • Can express defaults and their exceptions.
  • Can represent and reason with incomplete information.
  • Various implementations: Smodels, DLV, ASSAT,
  • CModels, …
  • Many applications built using it.
  • Its initial paper among the top 5 AI source documents in terms of citeseer citation.

What else we should do about ASP?

  • Extensions and semantics;
  • Need building block results;
  • The bottleneck: a program may be too large for answer set computation;
  • should have systems that can learn knowledge in this language;
  • Improving search efficiency
  • - domain dependent knowledge in planning
  • - techniques related to SAT
  • ……

Some of resent publications

  • F Lin and J You. Abductive logic programming by nonground rewrite systems. AAAI-08.
  • J You and G Liu. Loop formulas for logic programs with arbitrary constraint atoms. AAAI-08.
  • Y Shen and J You. A generalized Gelfond-Lifschitz transformation for logic programs with abstract constraints. AAAI-07.
  • G Wu, J You, G Lin. Quartet based phylogeny reconstruction with answer set programming.
  • IEEE/ACM Transactions on Computational Biology and Bioinformatics 2007.
  • F. Lin and J You. Recycling computed answers in rewrite systems for abduction.
  • ACM Transactions on Computational Logic 2007.
  • T Janhunen, I. Niemela, D. Seipel, P. Simons, J. You. Unfolding partiality and disjunctions in stable model semantics. ACM Transactions on Computational Logic 2006.

Download 92.5 Kb.

Do'stlaringiz bilan baham:

Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan © 2020
ma'muriyatiga murojaat qiling