%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% %%% %%% 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).