%% %% %% HOME ASSIGNMENT II - ARTIFICIAL INTELLIGENCE %% %% %% %% Represent the following information as a Prolog program. %% %% Make sure that your program entails that Tom's and Dick's cars are defective. %% %% Assume that no one has more than one car and hence cars can be identified by %% %% the name of their owners. %% %% %% %% A VW Rabbit is a VW. %% %% Tom's car is a VW Rabbit. %% %% Dick's car is a VW Rabbit. %% %% A VW has an electrical system. %% %% Part of the electrical system is an alternator. %% %% The alternator is defective on every VW. %% %% %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %% %% SOLUTION %% %% %% %% To make a discussion slightly more interesting I introduce more types of %% %% cars, assume every car has an electrical system, and that electrical systems %% %% of all types except, say, hm (handmade) have alternators. %% %% %% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% OBJECTS: people, their cars, types of these cars, and the car parts. %% People will be denoted by their names. The car of a person X will %% be denoted by c(X). Parts of a car C (e.g., electrical system, %% alternator, etc.) will be denoted by part(C) (e.g. es(C), alt(C), etc) %% HIERARCHY. %% Cars, their types, and their parts are organized in a simple %% class/property inheritance hierarchy H with links denoted by %% subclass(Class1,Class2), isa(C,Class), and partof(Part1(C),Part2(C)). %% The first link indicates that Class1 is a proper subclass of Class2, %% the second is a membership relation between a car C and a class Class, %% and the third holds if Part1 of a car C is an "immediate" subpart of %% part Part2 of the same car. For simplicity we will view cars as parts. %% THE CLASS HIERARCHY, H1. owner(dick). owner(tom). owner(mary). owner(pat). owner(john). owner(jim). car(c(P)) :- owner(P). type(car). type(vw). type(toyota). type(hm). type(golf). type(rabbit). type(corolla). a_part(es(C)) :- car(C). a_part(alt(C)) :- car(C). a_part(C) :- car(C). subclass(vw, car). subclass(rabbit, vw). subclass(golf, vw). subclass(toyota,car). subclass(corolla,toyota). subclass(hm,car). isa(c(dick), vw). isa(c(tom), rabbit). isa(c(mary), rabbit). isa(c(pat), corolla). isa(c(john), hm). isa(C,T) :- car(C), subclass(T0,T), isa(C,T0). %% If we want our program to correctly answer queries about the %% subclass relation we need to introduce a new relation is_subclass %% and write rules is_subclass(S1,S2) :- subclass(S1,S2). is_subclass(S1,S2) :- type(S2), subclass(S1,S3), is_subclass(S3,S2). %% PROPERTIES. %% To define a collection of parts for every car, C, in the hierarchy H1 %% we observe that these parts also form a hierarchy, H2(C). %% To specify H2(C) we will use strict rules of the form %% partof(part1(C), Part2(C)) :- isa(C, Class) or defeasible rules %% partof(part1(C), Part2(C)) :- isa(C, Class), not ab(), e,g, %% Every car has an electrical system. partof(es(C),C) :- isa(C,car), car(C). %% Electrical system of cars with the exception of those of hm type, %% have alternators. partof(alt(C),es(C)) :- isa(C,car), car(C), not ab(C). ab(C) :- isa(C,hm), car(C). %% The "immediate" partof relation between parts can be extended to a new %% relation is_partof defined as the transitive closure of partof. is_partof(P1,P2) :- a_part(P1), a_part(P2), partof(P1,P2). is_partof(P1,P2) :- a_part(P1), a_part(P2), a_part(P3), partof(P1,P3), is_partof(P3,P2). %% Notice, that the relation "partof(Part1(C),Part2(C)" can be seen as %% a property of C in the hierarchy H. This is different from hierarchies %% you have seen in class only in the use of function symbols. %% USING THE HIERARCHY: DEFECTIVE PARTS. %% Now we use the hierarchy H to incode information about defective %% parts of particular cars, e.g. defective(alt(C)) :- car(C), isa(C,vw). %% Of course, a part with a defective subpart is also defective. %% Hence we need defective(P) :- a_part(P0), a_part(P), is_partof(P0,P), defective(P0). %% ARE WE DONE? %% Well, we didn't have a precise specification for our program %% so we cannot prove that we are. We can check however that %% our program, (or, the reasoning agent represented by it) %% understood the above story. We can do it the way we check %% if a child understood the story - by asking questions. So first %% we need to ask ourselves if the program correctly answers queries %% about relations defective, is_partof, is_subclass, and isa. %% The answer to this question seems to be ambiguous. We seem %% to be able to obtain correct positive answers to ground queries, %% and to find objects satisfying the above relations. But what about %% negative answers? Here the situation is more difficult. %% First there is an ambiguity in the meaning of Prolog's answer "NO" %% to a ground query Q. It can mean that Q is false or that the %% program does not know wether Q is true or false. %% (a) Suppose we assume the first interpretation (which implies %% that the relevant knowledge about the "query" relations %% incoded in H and the definition of "defective" is complete. %% Now expand our program by the following new information: isa(c(jim),car). %% The intent is just to record that Jim has a car. But %% the resulting program entails that Jim's car is neither VW %% nor Toyota nor any other type of car mentioned in the hierarchy. %% This does not seem to be the intended meaning. To avoid this problem %% one may limit oneself to isa-updates for the lowest classes of %% the H hierarchy. The alternative is to expand the syntax and semantics %% of Prolog to be able to encode negative knowledge explicitly. %% (b) If you assume that "No" means "I do not know" then the answer %% seem correct but missing some understanding of the story. %% For instance, the query "Does Dick have a Toyota" will be answered %% definite NO by a human. Under the second interpretation the %% Prolog answer to isa(c(dick),toyota) will mean only "I do not know". %% Correctness is not the only problem with our formalization. %% It does not have sufficient expressive power to understand a %% simple question like "What is wrong with Dick's car". %% This can of course be remedeed by introduction of a new relation, %% diagnosis(C,P) which holds iff a part P is a smollest defective part %% of a car C. (A part is smallest defective if it is defective but %% its subparts are o.k.). We will need an auxilary relation %% subpart_bad(P) defined as follows subpart_bad(P) :- a_part(P), a_part(P0), partof(P0,P), defective(P0). %% subparts_ok(P) is defined as subparts_ok(P) :- a_part(P), not subpart_bad(P). %% Finally, diagnosis(C,P) :- car(C), a_part(P), is_partof(P,C), defective(P), subparts_ok(P). %% We have a smarter program as a result, but it still cannot %% understand a question "Are all VW defective?", etc %% ALL THIS WORKS FINE IN PROLOG. %% Now something I didn't discuss in class. %% Since we worked in Prolog we were basically forced to assume %% CWA for all the relations of the program. As a result isa link was %% allowed to appear only on the bottom of the hierarchy. %% In some situations this is not a reasonable assumption. %% The police may know the maker of the car driven by the suspect (i.e. VW) but %% not its model, etc. %% On the other hand it is natural to assume completeness of information %% for the subclass hierarchy (This info is changed seldomly). %% The program describing the hierarchy without CWA for "isa" will %% have multiple models and hence cannot be queried in Prolog. %% %% We can however use SMODELS. Here is a solution: %% Completeness of the subclass hierarchy is expressed by two rules: %% 1. CWA for is_subclass neg(is_subclass(T1,T2)) :- type(T1), type(T2), not is_subclass(T1,T2). :- type(T1),type(T2),is_subclass(T1,T2),neg(is_subclass(T1,T2)). %% 2. Completeness of partitioning: %% if a car C belongs to a class T it belongs to one of its subclasses. isa(C,T1) :- car(C), type(T), type(T1), isa(C,T), subclass(T1,T), not other_type(C,T1,T). other_type(C,T1,T) :- car(C), type(T1), isa(C,T2), subclass(T2,T), neq(T1,T2). %% We also decided to assume that classes in the hierarchy are disjoint. neg(isa(C,T1)) :- car(C), type(T1), type(T2), isa(C,T2), not is_subclass(T2,T1), not is_subclass(T1,T2), neq(T1,T2). :- type(T),car(C),isa(C,T),neg(isa(C,T)). %% Notice, that this solution does not allow neg(isa(c,t)) as an input. %% To allow negative isa links we need more rules. %% But what we really need to say here is that X belongs to a class iff %% it belongs to one of its subclasses. Maybe it will be easier to express %% it in CCALC. %% It will be really interesting to compare efficiency of various solutions. %% Maybe we can improve it using different engines for different %% queries. For example, if isa(c,t) where t is the leaf of the hierarchy %% we can use Prolog, otherwise, SMODELS, etc. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Auxiliary Predicates hide neg(X). hide subclass(X,Y). %hide isa(X,Y). hide car(X). hide a_part(X). hide owner(X). hide type(X). hide is_subclass(X,Y). hide partof(X,Y). hide is_partof(X,Y). hide ab(X). hide subpart_bad(X). hide subparts_ok(X). hide defective(X). hide other_type(X,Y,Z). hide diagnosis(X,Y). hide other_type(X,Y).