File: travel %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% %%% %%% TM: COMMONSENSE THEORY OF TRAVEL %%% %%% %%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%% TM's basics: %%%%%%%%%%%%%%%%%%% % % % The travel module, TM, is populated by people (P;P1;P2) % % who travel between various cities (C;C1;C2). % % ( In Prolog capital letters stand for variables) % % TM can be used to evaluate the possibility % % of such travel in a given interval of time as well as % % likely whereabouts of people after some travel related % % events. % % To formalize the travel domain we introduce a notion of % % a TRIP (a journey). A trip, which may have many participants,% % use many vehicles of different types, and follow complex % % routes needs to have the name, the origin, and the % % destination. It may also have other attributes such as % % modes_of_transportation, vehicle_used, etc. % % We often name a trip from C1 to C2 by j(C1,C2). % % Since the names must be unique we can only do that % % if the story involves only one trip from C1 to C2. % % At any given step T a trip may be in transit (en_route) % % or in one of its possible stops (in our case - cities). % % To embark on the trip a person may need to have some % % travel documents. Things packed in various containers % % can make the trip more pleasant, etc. % % % % The travel module is used in conjunction with particular % % scenarios. Some of them will be included in the message. % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%% To actually run our examples we need to import %%%%%% parts of our geographic and other modules. %%%%%% Here we will only have very small pieces of %%%%%% such information. %%%%%%%%%%%%%% Defining the Objects %%%%%%%%%%%%%%%% %%%% TIME STEPS %%%% % This definition uses a constant n - max number % of steps (consecutive actions) performed in % a particular scenario. Such a scenario must have % a definition of n, e.g. #const n=3. step(0..n). #domain step(T;T1;T2). %%%% GEOGRAPHY %%%% city(rome). city(baghdad). city(boston). city(berlin). city(paris). #domain city(C;C1;C2). % This defines typed variables % for cities. country(usa). country(france). country(italy). country(iraq). #domain country(Country;Country1;Country2). union(eu). #domain union(Union;Union1;Union2). in(boston,usa). in(paris,france). in(rome,italy). in(baghdad,iraq). in(italy,eu). in(france,eu). in(C,Union) :- in(C,Country), in(Country,Union). %%%% PEOPLE %%%% person(john). #domain person(P;P1;P2). %%%% TRIPS %%%% trip(j(C1,C2)) :- neq(C1,C2). origin(j(C1,C2),C1). dest(j(C1,C2),C2). #domain trip(J;J1;J2). % Of course other names for trips can also be used. %%%% TRIP LOCATIONS %%%% l(en_route). l(C). #domain l(D;D1;D2). %%%% ITINERARY %%%% % A knowledge base can be supplied with a detailed itinerary % of the trip given by statements of the form: % leg_of(J,C1,C2) - C2 is the next stop of J after C1. %%%% TRAVEL DOCUMENTS %%%% travel_document(passport(P)). travel_document(tickets(J)). #domain travel_document(TD;TD1). %%%% BELONGINGS %%%% belongings(laptop(P)). belongings(book1). #domain belongings(B;B1;B2). %%%% LUGGAGE and other CONTAINERS %%%% % We assume that a traveler P may have two types of % luggage, i.e. containers for his belongings: % carry_on(P) - luggage item(s) compact enough to % be carried aboard an aircraft; % lugg(P) - suitcases and other larger containers % Normally people own luggage of both types. owns(P,carry_on(P)) :- not -owns(P,carry_on(P)). owns(P,lugg(P)) :- not -owns(P,lugg(P)). luggage(carry_on(P)). luggage(lugg(P)). #domain luggage(Luggage;Luggage1;Luggage2). container(Luggage). #domain container(Container;Container1;Container2). %%%% PERSONAL POSSESSIONS %%%% possession(TD). possession(B). possession(Container). #domain possession(PP;PP1;PP2). %%%% VEHICLES %%%% % I am not sure what to do here. At the moment % I assume that vehicles are named 1, 2, etc. % and represented by statements % vehicle(name,vehicle_type), e.g. This part % is not really used in the axioms. vehicle_name(1..3). #domain vehicle_name(V;V1;V2). type_of_transp(car). type_of_transp(plane). type_of_transp(boat). type_of_transp(bus). type_of_transp(train). #domain type_of_transp(TypeOfTransp;TypeOfTransp1;TypeOfTransp2). vehicle(1,car). vehicle(2,car). vehicle(3,plane). %%%% Transportable Objects %%%% % These are objects which may change their locations. object(J). object(P). object(PP). object(V). #domain object(O;O1;O2). %%%% CALENDAR TYPES %%%% day(1..5). #domain day(Day;Day1;Day2). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % The rest of the representation is based on the % theories of actions. A collection of dynamic % causal laws, state constraints, and executability % conditions defines a transition diagram containing % all the possible trajectories of the domain (ref?) % Even though correctness (and completeness) of some % query answering algorithms can only be demonstrated % with the help of such theories the rules below % should be intuitively understandable. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%% ACTIONS and FLUENTS %%%%%%%%%%% % % We will try to use meaningful names but to % really understand the effects of actions and % the meaning of fluents one will need to study % the corresponding axioms. %% ACTIONS Performed by Trips %% action(depart(J)). % Trip J departs its origin actor(depart(J),J). action(stop(J,C)). % stops at city C actor(stop(J,C),J). %% ACTIONS Performed by People %% % go_on(P,J) Person P goes on trip J action(go_on(P,J)). actor(go_on(P,J),P). % embark(P,J). P becomes a participant of J action(embark(P,J)). actor(embark(P,J),J). % Normally people embark on trips at the trip's origin. place(embark(P,J),C1) :- origin(J,C1), not place(embark(P,J),C2), neq(C1, C2). % disembark(P,J). P ceases to be a participant of J action(disembark(P,J)). actor(disembark(P,J),J). % get(P,PP) - P gets a personal possession PP action(get(P,PP)). actor(get(P,PP),P). % pack(P,PP,Container) action(pack(P,PP,Container)). actor(pack(P,PP,Container),P). % unpack(P,PP,Container) action(unpack(P,PP,Container)). actor(unpack(P,PP,Container),P). % change_to(J,TypeOfTransp) action(change_to(J,TypeOfTransp)). actor(change_to(J,TypeOfTransp),J). %%%%%%%% FLUENTS %%%%%%%% %%% Inertial Fluents fluent(at(O,D)). fluent(participant(P,J)). fluent(has(P,PP)). % Note that "has" differ from "owns", % it implies "immediately accessible" fluent(inside(B,Container)). fluent(lost(Luggage)). fluent(trip_by(J,TypeOfTransp)). #domain fluent(Fl;Fl1;Fl2). %%%%%%% Inertia %%%%%%% %% This is a standard representation of the default %% "Things tend to stay as they are" %% in Answer Set Prolog. h(Fl,T) stands for %% "Fluent Fl holds at time point T". h(Fl,T+1) :- T < n, h(Fl,T), not -h(Fl,T+1). -h(Fl,T+1) :- T < n, -h(Fl,T), not h(Fl,T+1). %%%%%% Default Initial Values for Some Fluents %%%%%%% % We can assume that in the begining of the story % the traveler already has his passport, % and his luggage. h(has(P,passport(P)),0) :- not -h(has(P,passport(P)),0). h(has(P,Luggage),0) :- owns(P,Luggage), not -h(has(P,Luggage),0). % If in the initial situation P goes on journey J % then, in the absence of contrary evidence, we % assume that J and P are at the origin of J. % o(A,T) says that "action A occurs at time step T". h(at(J,C),0) :- o(go_on(P,J),0), origin(J,C), not -h(at(J,C),0). h(at(P,C),0) :- o(go_on(P,J),0), origin(J,C), not -h(at(P,C),0). %%%%%%%%%%%%%%%%%% ACTION DESCRIPTION %%%%%%%%%%%%%% % % In this section we describe direct and indirect % effects of actions. % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%% AGENT's ACTIONS: %%%%%%%%%%%%%%% ACT: embark(P,J) %%%%%%%%%%%%%%%%% %%%%%%%% Direct Effects: h(participant(P,J),T+1) :- % becomes a participant o(embark(P,J),T). -h(has(P,lugg(P)),T+1) :- % ckeck in the luggage o(embark(P,J),T), h(trip_by(J,plane),T). %%%%%%%% Executability conditions: % Can't embark if already there. :- o(embark(P,J),T), h(participant(P,J),T). % Need to be at the right place: :- o(embark(P,J),T), h(at(P,D1),T), h(at(J,D2),T), neq(D1,D2). % Need to have necessary documents: :- o(embark(P,J),T), need(P,TD,J), -h(has(P,TD),T). % Documents Needed: % Passport is normally needed to cross the borders: need(P,passport(P),J) :- place(embark(P,J),C1), dest(J,C2), diff_countries(C1,C2), not -need(P,passport(P),J). diff_countries(C1,C2) :- in(C1,Country1), in(C2,Country2), neq(Country1,Country2). % Exception -need(P,passport(P),J) :- citizen(P,eu), place(embark(P,J),C1), dest(J,C2), in(C1,eu), in(C2,eu). % Tickets are normally needed need(P,tickets(J),J) :- not -need(P,tickets(J),J). % Exception -need(P,tickets(J),J) :- car_trip(J). -car_trip(J) :- h(trip_by(J,TypeOfTransp),T), neq(TypeOfTransp,car). car_trip(J) :- h(trip_by(J,car),0), not -car_trip(J). %%%%%%%%%%%%%%% ACT: disembark(P,J) %%%%%%%%%%%%%%%%% % Direct Effect: -h(participant(P,J),T+1) :- o(disembark(P,J),T). h(has(P,lugg(P)),T+1) :- o(disembark(P,J),T), o(embark(P,J),T1), h(has(P,lugg(P)),T1), not h(lost(lugg(P)),T+1). % Executability Conditions :- o(disembark(P,J),T), -h(participant(P,J),T). :- o(disembark(P,J),T), h(at(J,en_route),T). %%%%%%%%%%%%%% ACT: go_on(P,J) %%%%%%%%%%%%%%% % We view go_on as a sequence of two simpler actions: o(embark(P,J),T) :- o(go_on(P,J),T). o(depart(J),T+1) :- o(go_on(P,J),T). % We assume that air travel takes not more than one day. % time(T2,d,Day) | time(T2,d,Day + 1) :- o(go_on(P,J),T1), o(disembark(P,J),T2), time(T1,d,Day), h(trip_by(J,plane),T1). %%%%%%%%%%% ACT: get(Person,Possession) %%%%%%%%%%%% % Direct Effect h(has(P,PP),T+1) :- o(get(P,PP),T). % Executability Conditions %:- o(get(P,PP),T), % h(has(P,PP),T). % Min time needed to get a passport. :- duration(get(P,passport(P)),Day), Day < 3. %%%%%%%%%%% ACT: pack(P,PP,Container) %%%%%%%%%% %%%%%%%%%% ACT: unpack(P,PP,Container) %%%%%%%%%% % Direct Effects: h(inside(PP,Container),T+1) :- o(pack(P,PP,Container),T). -h(inside(PP,Container),T+1) :- o(unpack(P,PP,Container),T). % Executability Conditions -o(pack(P,PP,Container),T) :- % -h(has(P,PP),T). -o(pack(P,PP,Container),T) :- -h(has(P,Container),T). -o(unpack(P,PP,Container),T) :- -h(has(P,Container),T). -o(unpack(P,PP,Container),T) :- -h(inside(P,Container),T). %%%%%% TRIP's ACTIONS: %%%%%%%% ACT: depart(J), stop(J,C)%%%%%%%%%%%%% %%% Actions occurrences are mutually dependent % Direct Effects: % After the departure J is en_route h(at(J,en_route),T+1) :- o(depart(J),T). % Stops are successful h(at(J,C),T+1) :- o(stop(J,C),T). % (The action "disembark" is caused when the trip % stops at the destination) o(disembark(P,J),T+1) :- h(participant(P,J),T), o(stop(J,D),T), dest(J,D). % Executability Conditions -o(depart(J),T) :- h(at(J,en_route),T). -o(stop(J,C),T) :- -h(at(J,en_route),T). % Normally the trip goes directly to its destination. % (Or at least we are not interested in the % intermediate stops) o(stop(J,C),T) :- h(at(J,en_route),T), dest(J,C), not -o(stop(J,C),T). % Normally after a stop the trip continues to its destination: o(depart(J),T+1) :- o(stop(J,C),T), not dest(J,C), not -o(depart(J),T+1). %%%%% ITINERARY %%%%% % The trip stops at the inermediate stops: o(stop(J,C2),T+1) :- leg_of(J,C1,C2), h(at(J,C1),T), o(depart(J),T). % J can only stop at one place at the time -o(stop(J,C),T) :- o(stop(J,C1),T), neq(C,C1). % Changing type of transportation is always successful h(trip_by(J,TypeOfTransp),T+1) :- o(change_to(J,TypeOfTransp),T). %%%%%%%%%%%%% State Constraints %%%%%%%%%% % % % State constraints together with direct % % effects and the inertia axioms define % % all the effects of an action. This is % % the answer set prolog solution to the % % frame and ramification problems. % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Location of a moving object is unique -h(at(O,D1),T) :- h(at(O,D2),T), neq(D1,D2). % Trip uses one mode of transportation at a time. -h(trip_by(J,TypeOfTransp2),T) :- h(trip_by(J,TypeOfTransp1),T), neq(TypeOfTransp1,TypeOfTransp2). % Personal possessions are attached to a person. h(at(PP,D),T) :- h(has(P,PP),T), h(at(P,D),T). % Participants share the current location of the trip h(at(P,D),T) :- h(participant(P,J),T), h(at(J,D),T). % A container share location with its content h(has(P,PP),T) :- h(inside(PP,Container),T), h(has(P,Container),T). % A very simplified definition of duration % of action in terms of "time". duration(A,Day) :- action(A), o(A,T), time(T,d,Day1), time(T+1,d,Day2), Day = Day2 - Day1. % time(T,U,V) is a relation from the CALENDER module % which says that a step T occurred at time V measured in units U. %%%%%%%%%%%%%%%%%%%% Display %%%%%%%%%%%%%%%%% %%% This are just thing I use for display %%%% e_action(embark(P,J)). e_action(disembark(P,J)). e_action(get(P,PP)). e_action(pack(P,PP,Container)). e_action(unpack(P,PP,Container)). e_action(depart(J)). e_action(stop(J,C)). do(Act,T) :- e_action(Act), o(Act,T). at(O,C,T) :- h(at(O,C),T). has(O,T) :- h(has(john,O),T). has_carry_on(T) :- h(has(john,carry_on(john)),T). has_not_carry_on(T) :- -h(has(john,carry_on(john)),T). has_laptop(T) :- h(has(john,laptop(john)),T). trip_at(D,T) :- h(at(j(paris,baghdad),D),T). File: AboutTime %%%%%%%% CONSTRAINT SOLVER 1{time(T,d,X) : day(X)}1 :- T < n. :- time(T1,d,Day1), time(T2,d,Day2), T1 < T2, Day2 < Day1. :- time(T,d,Day1), time(T,d,Day2), neq(Day1,Day2). % The following actions are performed % during a day. time(T+1,d,Day) :- o(pack(P,PP,Container),T), time(T,d,Day). time(T+1,d,Day) :- o(embark(P,J),T), time(T,d,Day). time(T+1,d,Day) :- o(stop(J,C),T), time(T,d,Day). time(T+1,d,Day) :- o(disembark(P,J),T), time(T,d,Day). === File: scenario0 % This is a simple scenario - a short story, % followed by a question. %%%%%%%%%%%%%%%%%%%% SCENARIO 0 %%%%%%%%%%%%%%%%% % John took the plane from Paris to Baghdad. % % Is John in Baghdad? % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% #const n=4. % The story should be tranlated into a collection % of atoms and a definition of constant n (number % of steps of the domain) which will be used in % conjunction with the travel module. % WE DO TRANSLATION BY HAND. THE PROBLEM IS TO DO % IT AUTOMATICALLY. % THE TRANSLATION % Recall that h(F,S) says that fluent F is true at step S, % and o(A,S) says that action A occur at S. % John took the plane from Paris to Baghdad. h(at(john,paris),0). o(go_on(john,j(paris,baghdad)),0). % The query is translated as: % the answer to the query is "true" if... answer_true(q) :- h(at(john,baghdad),n). % John is in Baghdad at the current step % the answer to the query is "false" if... answer_false(q) :- -h(at(john,baghdad),n). % John is not in Baghdad at the current step % the answer to the query is yes, no, or maybe. type_query(q,boolean). % To answer the query we will use the rules: yes :- type_query(Q,boolean), answer_true(Q). no :- type_query(Q,boolean), answer_false(Q). maybe :- type_query(Q,boolean), not yes, not no. % together with Smodels display directives hide. show yes, no, maybe. % Note that the value of "n" is not given in advance. % The right number is 4. Using larger values will % not change the answer to a query which will persist % by inertia. % How "n" will be computed by the corresponding natural language % translator (NLT) is an open question. % One possibility is to run the program with n = 1,2,... % and display the actions. Stop when the last action % occurs at n-1. % To see how it works uncomment the "show" statement below % and run the program with i = 1..4. % show do(A,B). %lparse --true-negation scenario0 travel | smodels 0 | mkatoms === File: scenario1 %%%%%% THIS IS A MODIFICATION of scenario0 %%%%%% in which we have a more detailed %%%%%% information about the trip itinerary. %%%%%% New thing in the theory of travel are %%%%%% marked by the word itinerary #const n=8. %%%%%%%%%%%%%%%%%%%% SCENARIO 1 %%%%%%%%%%%%%%%%%% % % % John took the plane from Paris to Baghdad. % % The plane has sceduled intermediate stops % % in Berlin and Rome. Is John in Baghdad? % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % THE TRANSLATION % The first statement and the query are translated % as in scenario0. % To tranalsate the second statement we need % to recall that leg_of(J,C1,C2) says that % "C2 is the next stop of J after C1". % Overall we have: % John took the plane from Paris to Baghdad. h(at(john,paris),0). o(go_on(john,j(paris,baghdad)),0). % The plane has sceduled intermediate stops % in Berlin and Rome. leg_of(j(paris,baghdad),paris,berlin). leg_of(j(paris,baghdad),berlin,rome). leg_of(j(paris,baghdad),rome,baghdad). % The query: answer_true(q) :- h(at(john,baghdad),n). answer_false(q) :- -h(at(john,baghdad),n). type_query(q,boolean). % As before we'll run the program together with % the rules and directives below. % Note that this time n=8. yes :- type_query(Q,boolean), answer_true(Q). no :- type_query(Q,boolean), answer_false(Q). maybe :- type_query(Q,boolean), not yes, not no. hide. show yes,no,maybe,do(A,B). === File: scenario2 #const n=6. %%%%%%%%%%%%%%%%%%%% SCENARIO 2 %%%%%%%%%%%%%%%%%% % % % John took the plane from Paris to Baghdad. % % On the way the plane stopped in Rome. % % Is John in Baghdad? % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % THE TRANSLATION % Statement 1 and the query as before. % Statement 2 is new. % John took the plane from Paris to Baghdad. h(at(john,paris),0). o(go_on(john,j(paris,baghdad)),0). % On the way the plane stopped in Rome. o(stop(j(paris,baghdad),rome),2). % The query: answer_true(q) :- h(at(john,baghdad),n). answer_false(q) :- -h(at(john,baghdad),n). type_query(q,boolean). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % The difficulty with the translation of % statement 2 is in figuring out that "stopping % in Rome" happened between departure from Paris % and arrival in Baghdad. But even if this is done % we need to determine the exact "step" when % it occurs (in our case, 2). % One possible way to find this value is to % translate the first sentence and run % the program with n=1,2,... as before. % With n=4 you'll obtain: % do(embark(john,j(paris,baghdad)),0) % do(depart(j(paris,baghdad)),1) % do(stop(j(paris,baghdad),baghdad),2) % do(disembark(john,j(paris,baghdad)),3) % This information can be useful in determining % that stopping in Rome happened at step 2. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % As before we'll run the program together with % the rules and directives below. yes :- type_query(Q,boolean), answer_true(Q). no :- type_query(Q,boolean), answer_false(Q). maybe :- type_query(Q,boolean), not yes, not no. hide. show yes,no,maybe,do(A,B). === File: scenario3 #const n=6. %%%%%%%%%%%%%%%%%%%% SCENARIO 3 %%%%%%%%%%%%%%%%%% % % % John took the plane from Paris to Baghdad. % % On the way the plane stopped in Rome. % % Where is John? % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % This only differ from scenario 2 by the query. % This time, we want to know which elements of % a class of fluents are true at the current % state of the domain. % THE TRANSLATION % John took the plane from Paris to Baghdad. h(at(john,paris),0). o(go_on(john,j(paris,baghdad)),0). % On the way the plane stopped in Rome. o(stop(j(paris,baghdad),rome),2). % Query: % The test to check for which values of C the % query is satisfied is written by defining % predicate answer_true with the name of the % query as argument. Since variables are % involved, the name of the query is a term % of the form q(V1,...Vn), where V1,...,Vn % are the variables whose values the query % is requesting. % answer_true(q(C)) :- h(at(john,C),n). type_query(q(C),find). % Note the use of variable C for cities % (used by the travel module as locations) % In general we need a properly typed variable. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % To run the new query we'll use the rules: ans(Q) :- type_query(Q,find), answer_true(Q). % and the display directives: hide. show ans(A). === File: scenario4 #const n=6. %%%%%%%%%%%%%%%%%%%% SCENARIO 4 %%%%%%%%%%%%%%%%%% % % % John took the plane from Paris to Baghdad. % % On the way the plane stopped in Rome, where % % John was arrested. Is John in Baghdad? % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % THE TRANSLATION % Statement 1 and the query as in scenario 2. % The second part of statement 2 is new. % John took the plane from Paris to Baghdad. h(at(john,paris),0). o(go_on(john,j(paris,baghdad)),0). % On the way the plane stopped in Rome... o(stop(j(paris,baghdad),rome),2). % ...where John was arrested o(arrest(john),3). % The query: answer_true(q) :- h(at(john,baghdad),n). answer_false(q) :- -h(at(john,baghdad),n). type_query(q,boolean). % As before we'll run the program together with % the rules and directives below. yes :- type_query(Q,boolean), answer_true(Q). no :- type_query(Q,boolean), answer_false(Q). maybe :- type_query(Q,boolean), not yes, not no. hide. show yes,no,maybe,do(A,B). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % The story contains an action arrest(P) not normally % related to travel. The corresponding axiom: -h(participant(P,J),T+1) :- o(arrest(P),T). % which can be viewed as a special case of a statement % "arrest stops the person participation in his % current activities" will be loaded from the % module associated with "arrest". === File: scenario5 #const n=4. %%%%%%%%%%%%%%%%%%%% SCENARIO 5 %%%%%%%%%%%%%%%%%% % % % John took the plane from Paris to Baghdad. % % Where is John's carry-on? % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % THE TRANSLATION % 1. John goes to Baghdad: o(go_on(john,j(paris,baghdad)),0). % The query: answer_true(q(C)) :- h(at(carry_on(john),C),n). type_query(q(C),find). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % To run use ans(Q) :- type_query(Q,find), answer_true(Q). hide. show ans(A). === File: scenario6 #const n=4. %%%%%%%%%%%%%%%%%%%% SCENARIO 6 %%%%%%%%%%%%%%%%% % % % John is in Paris. On Dec 1st he packs his % % laptop in the carry-on luggage and takes a % % plane to Baghdad. % % Was his laptop in Baghdad on Dec 2nd? % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % This is the first scenario in which we deal % with time. To do that properly we need % a Calendar - knowledge base containing % information about various measures of % time, e.g. days, months, seasons, etc. % But since our goal here is to better % understand the Travel module we ignore % all these subtleties and simply use % integers from 1 to 5 to count days. % Relevant relations in Travel are % duration(Action,NumOfDays). % time(T,U,V) - a step T occurred at time V % measured in units U. In our case U=d (days). % THE TRANSLATION % John is in Paris. h(at(john,paris),0). % On Dec 1st he packs his laptop in the carry-on luggage. o(pack(john,laptop(john),carry_on(john)),0). time(0,d,1). % Step 0 corresponds to day 1. % John goes to Baghdad: h(trip_by(j(paris,baghdad),plane),1). o(go_on(john,j(paris,baghdad)),1). time(1,d,1). % Query: % In the previous examples we queried our knolwedge % base about the values of fluents at the last % step n of the scenario. % The question asked here is of the form "Was fluent % Fl true at a given time D?". % Since we are measuring time in days I reformulate % this question as "Was Fl true at some point % during D?". % To answer this question we need to map steps of % the scenario into days. Note that two different steps can be % mapped into the same day. Step 1 at which John % leaves Paris is mapped into Dec 1. % Step 4 at which he arrives to Baghdad can be % associated with the first or second of Dec % depending on the trip's duration. In the first % case both steps, 1 and 4, are mapped into Dec 1. % The mapping is performed by a module called AboutTime. % I am just going to copy it here: %%%%%%%% AboutTime 1{time(T,d,X) : day(X)}1 :- T < n. :- time(T1,d,Day1), time(T2,d,Day2), T1 < T2, Day2 < Day1. :- time(T,d,Day1), time(T,d,Day2), neq(Day1,Day2). % The following actions are performed % during a single day. time(T+1,d,Day) :- o(pack(P,PP,Container),T), time(T,d,Day). time(T+1,d,Day) :- o(embark(P,J),T), time(T,d,Day). time(T+1,d,Day) :- o(stop(J,C),T), time(T,d,Day). time(T+1,d,Day) :- o(disembark(P,J),T), time(T,d,Day). % The new relation true_on(Fl,Day) states that fluent Fl was true % sometime during the day Day. Similarly for false_on(Fl,Day). true_on(Fl,Day) :- time(T,d,Day), h(Fl,T). false_on(Fl,Day) :- time(T,d,Day), -h(Fl,T). % Of course similar relations can be defined for occurrences of actions. % The NLP translation of the query may look as follows: answer_true(q) :- true_on(at(laptop(john),baghdad),2). answer_false(q) :- false_on(at(laptop(john),baghdad),2), not answer_true(q). % Note that the last line is needed since the laptop can % be in Paris and in Baghdad at the same day. type_query(q,boolean). % Of course this approach will work for an arbitrary fluent % (or action occurrence) and arbitrary collection of time % atoms encoding dates and other time measures. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % As before we'll run the program together with % the rules and directives below. yes :- type_query(Q,boolean), answer_true(Q), not answer_false(Q). no :- type_query(Q,boolean), answer_false(Q), not answer_true(Q). maybe :- type_query(Q,boolean), not yes, not no. hide. show yes,no,maybe. % If you run the program you will get two answer sets. % In the first one all travel is done in one day, % the second requires two days. % In the first case John arrives in Baghdad on the % first, the program has no information about his % whereabouts on the second. Hence the first answer set % contains the answer "maybe". % The second answer set assumes that John arrives in % Baghdad on the second. This time the answer is "yes". % To see what happens you can uncomment % show answer_true(X),answer_false(X),do(A,B),time(A,B,C). % Note that if we assume that, in the absence of recorded % actions, an object stays in one place for at least a day, % and write true_on(at(O,C),Day+1) :- h(at(O,C),n), time(n,d,Day). false_on(at(O,C),Day+1) :- -h(at(O,C),n), time(n,d,Day). === File: scenario7 #const n=4. %%%%%%%%%%%%%%%%%%%% SCENARIO 7 %%%%%%%%%%%%%%%% % % % John is in Paris. On Dec 1st he packs his % % laptop in the carry-on luggage and takes a % % plane to Baghdad. % % Where is his laptop on Dec 2nd? % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % This differs from scenario 6 only by the query. % We are asking to find out what fluents of a given % class are true on a given day. % THE TRANSLATION % John is in Paris. h(at(john,paris),0). % On Dec 1st he packs his laptop in the carry-on luggage. o(pack(john,laptop(john),carry_on(john)),0). time(0,d,1). % Step 0 corresponds to day 1. % John goes to Baghdad: h(trip_by(j(paris,baghdad),plane),1). o(go_on(john,j(paris,baghdad)),1). time(1,d,1). % Query: % We need to find C such that true_on(at(laptop(john), C),2). % The query differ from that in scenario6 by % an extra variable, C, of q. % In general we will have q(V1,...Vn), where V1,...,Vn % are the variables whose values the query % is requesting. answer_true(q(C)) :- true_on(at(laptop(john),C),2). % type of query type_query(q(C),find). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % To run the program we use ans(Q) :- type_query(Q,find), answer_true(Q). hide. show ans(A),time(A,B,C). % As before we need our "AboutTime" module: %%%%%%%% AboutTime 1{time(T,d,X) : day(X)}1 :- T < n. :- time(T1,d,Day1), time(T2,d,Day2), T1 < T2, Day2 < Day1. :- time(T,d,Day1), time(T,d,Day2), neq(Day1,Day2). % The following actions are performed % during a single day. time(T+1,d,Day) :- o(pack(P,PP,Container),T), time(T,d,Day). time(T+1,d,Day) :- o(embark(P,J),T), time(T,d,Day). time(T+1,d,Day) :- o(stop(J,C),T), time(T,d,Day). time(T+1,d,Day) :- o(disembark(P,J),T), time(T,d,Day). % The new relation true_on(Fl,Day) states that fluent Fl was true % sometime during the day Day. Similarly for false_on(Fl,Day). true_on(Fl,Day) :- time(T,d,Day), h(Fl,T). false_on(Fl,Day) :- time(T,d,Day), -h(Fl,T). % We will use the same defaults as in scenario6: true_on(at(O,C),Day+1) :- h(at(O,C),n), time(n,d,Day). false_on(at(O,C),Day+1) :- -h(at(O,C),n), time(n,d,Day). % In both answer sets the answer is Baghdad === File: scenario8 #const n=3. %%%%%%%%%%%%%%%%%%%% SCENARIO 8 %%%%%%%%%%%%%%%%%%%% % % % John is in Boston on Dec 1. He has no passport. % % Can he go to Paris on Dec. 3? % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% We (possibly incorrectly) interpret "can" as %%% "May it be possible". %%% We plan to also look at other interpretations. % THE TRANSLATION % translation of the first two sentences is straightforward. % John is in Boston on Dec 1. h(at(john,boston),0). time(0,d,1). % He has no passport. -h(has(john,passport(john)),0). % The query however is rather different from what we've seen % so far. It can be interpreted as asking if there is a plan % (a sequence of actions) which may, under proper circumstances % allow John to go to Paris on Dec 3. % (Recall that to go John needs a passport and that getting % one requires at least three days. So no such plan exists % and the answer to our query should be "NO"). % The query can be translated by a rule: answer_true(q) :- o(go_on(john,j(boston,paris)),T), time(T,d,3). % In general we may have % % answer_true(Q) :- h(F,T),...,o(a,T)... % time(T,U,V),... % % that is, the query may contain conditions % regarding several fluents, occurrences of actions, % and time atoms encoding dates and other time % measures. type_query(q,can). % The next fact states that the query % is about JOHN's ability to plan % his trip to Paris. planner(q,john). % To answer this query we need a planning module % described below: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % THE PLANNING MODULE % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % The module, used in conjunction with "scenario8" % and travel takes a non-negative integer n % as a parameter and finds a plan of maximum % length n which achieves the goal. If no % such plan exists the program has no model. yes :- type_query(Q,can), answer_true(Q). :- not yes. {o(Act,T) : action(Act) : actor(Act,P)}1 :- planner(Q,P), T < n-1. hide. show yes, time(A,B,C), do(A,B). % If you run the program you'll see that it has no model. % There is no way John can go to Paris that early. % As before we need our "AboutTime" module: %%%%%%%% AboutTime 1{time(T,d,X) : day(X)}1 :- T < n. :- time(T1,d,Day1), time(T2,d,Day2), T1 < T2, Day2 < Day1. :- time(T,d,Day1), time(T,d,Day2), neq(Day1,Day2). % The following actions are performed % during a single day. time(T+1,d,Day) :- o(pack(P,PP,Container),T), time(T,d,Day). time(T+1,d,Day) :- o(embark(P,J),T), time(T,d,Day). time(T+1,d,Day) :- o(stop(J,C),T), time(T,d,Day). time(T+1,d,Day) :- o(disembark(P,J),T), time(T,d,Day). === File: scenario9 #const n=3. %%%%%%%%%%%%%%%%%%%% SCENARIO 9 %%%%%%%%%%%%%%%%%%%% % % % John is in Boston on Dec 1. He has no passport. % % Can he go to Paris on Dec. 4? % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % The only difference here is the date of departure. % This means that the only change is the constant % in definnition of answer_true. % This time it is possible for John to go to Paris % on time (assuming of course that he'll receive % his passport quickly). Hence the answer to the query % should be YES. % THE TRANSLATION % translation of the first two sentences is straightforward. % John is in Boston on Dec 1. h(at(john,boston),0). time(0,d,1). % He has no passport. -h(has(john,passport(john)),0). % The query however is rather different from what we've seen % so far. It can be interpreted as asking if there is a plan % (a sequence of actions) which will allow John to go to % Paris on Dec 3. % (Recall that to go John needs a passport and that getting % one requires at least three days. So no such plan exists % and the answer to our query should be "NO"). % The query can be translated by a rule: answer_true(q) :- o(go_on(john,j(boston,paris)),T), time(T,d,4). % In general we may have % % answer_true(Q) :- h(F,T),...,o(a,T)... % time(T,U,V),... % % that is, the query may contain conditions % regarding several fluents, occurrences of actions, % and time atoms encoding dates and other time % measures. type_query(q,can). % The next fact states that the query % is about JOHN's ability to plan % his trip to Paris. planner(q,john). % To answer this query we need a planning module % described below: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % % THE PLANNING MODULE % % % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % The module, used in conjunction with "scenario9" % and travel takes a non-negative integer n % as a parameter and finds a plan of maximum % length n which achieves the goal. If no % such plan exists the program has no model. yes :- type_query(Q,can), answer_true(Q). :- not yes. {o(Act,T) : action(Act) : actor(Act,P)}1 :- planner(Q,P), T < n-1. hide. show yes. % show time(A,B,C), do(A,B). % As before we need our "AboutTime" module: %%%%%%%% AboutTime 1{time(T,d,X) : day(X)}1 :- T < n. :- time(T1,d,Day1), time(T2,d,Day2), T1 < T2, Day2 < Day1. :- time(T,d,Day1), time(T,d,Day2), neq(Day1,Day2). % The following actions are performed % during a single day. time(T+1,d,Day) :- o(pack(P,PP,Container),T), time(T,d,Day). time(T+1,d,Day) :- o(embark(P,J),T), time(T,d,Day). time(T+1,d,Day) :- o(stop(J,C),T), time(T,d,Day). time(T+1,d,Day) :- o(disembark(P,J),T), time(T,d,Day).