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, commonsense reasoning, …
 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.
 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  groundwet watering.
 groundwet raining.
 In an open world, there could be other reasons that cause groundwet (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.
 Groundwet 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).
 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.

Colorability  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 3colorability  % 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).
Planning  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 nonmonotonic.
 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. AAAI08.
 J You and G Liu. Loop formulas for logic programs with arbitrary constraint atoms. AAAI08.
 Y Shen and J You. A generalized GelfondLifschitz transformation for logic programs with abstract constraints. AAAI07.
 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.
Do'stlaringiz bilan baham: 