%---------------------------------------
% Foundations of Language Interaction
% Program Two: Intentions in Deliberation
% M. Stone, 5-31-01
% mdstone@cs.rutgers.edu
%---------------------------------------

%---------------------------------------
% List programming
%---------------------------------------

module Lists.

type member	A -> list A -> o.
type remove_elt	A -> list A -> list A -> o.
type remove	list A -> list A -> list A -> o.
type sublist	list A -> list A -> o.
type disjoint	list A -> list A -> o.
type union 	list A -> list A -> list A -> o.

% (member A L) if A is an element of L.

member A (A :: R).
member A (H :: R) :- member A R.

% (sublist L1 L2) if 
%    every element of L1 is an element of L2.

sublist nil L.
sublist (E::R) L :-
	member E L,
	sublist R L.

% (remove_elt A L1 L2) if
%    L2 is like L1 except that
%    all occurrences of A are 
%    omitted in L2.

remove_elt A nil nil.
remove_elt A (A::R) G :- !,
	remove_elt A R G.
remove_elt A (E::R) (E::L) :-
	remove_elt A R L.

% (remove R L1 L2) if
%    L2 is like L1 except that
%    all occurrences of elements of R
%    are omitted in L2.

remove nil L L.
remove (A::R) L F :-
	remove_elt A L M,
	remove R M F.
	
% (disjoint L R) if
%     L and R have no elements in common.

disjoint L R :-
	not (sigma e\ (member e L, member e R)).

% (union X Y Z) if
%      Z is a list with the elements of
%      X in order followed by the elements
%      of Y in order.

union nil R R.
union (A::L) R (A::U) :-
	union L R U.

%%%%%%
%---------------------------------------
% Planning with GPS-style means-end search
% and STRIPS-style action representation.
%---------------------------------------

module BasicPlan.
import Lists.

%---------------------------------------
% 
% facts are things that can be true;
% actions are things you can do

kind fact, action	type.

%---------------------------------------
%
% plans are structures showing how
%    doing a sequence of action
%    in the current circumstances
%    leads to desired effects.
% (finish G) represents the endpoint,
%     when desired facts G are true.
% (step Circ Act Subs) represents
%     a staged plan, that must be
%     executed when Circ are all true;
%     you first do Act, then continue
%     with plan Subs.

kind plan		type.

type finish	list fact -> plan.
type step	list fact -> action -> plan -> plan.

%---------------------------------------

type describe_plan plan -> o.

% (describe_plan Plan)
%   Always true; as a side-effect, print out
%   a description of Plan to the terminal.

describe_plan (finish A) :-
	output std_out "finish\n".

describe_plan (step Circ A P) :-
	term_to_string A S,
	Z is ("do " ^ S ^ " "),
	output std_out Z,
	describe_plan P.

%---------------------------------------

type circ	plan -> list fact -> o.

% (circ P Circ)
%     true if Circ are the circumstances
%     required now for P to be pursued to
%     success.

circ (finish Goals) Goals.
circ (step Pre Act Plan) Pre.

%----------------------------------------

type applies	list fact -> plan -> o.

% (applies Circ Plan)
%     true if Plan can be executed in Circ

applies Facts Plan :-
	circ Plan Deps,
	sublist Deps Facts.

%----------------------------------------

type is_action	action -> list fact -> list fact -> list fact -> o.

% The domain will specify an inventory of action in
% STRIPS representation:
%	(is_action A Preconditions Additions Deletions) 
% true if action A can be executed in a state where
% Preconditions are all true, resulting in establishing
% all the facts in Additions as true while terminating
% all the relationships in Deletions.

%------------------------------------------

type build_plan list fact -> plan -> plan -> (action -> o) -> int -> o.

% (build_plan Circ Current Final Pred Depth) 
%     is true if FINAL is a plan that can be
%     executed in the current circumstances CIRC, that
%     ends with the steps spelled out by CURRENT, but 
%     starts with some possible other steps initially; 
%     FINAL may add at most DEPTH more actions, of
%     which the last to be performed must satisfy PRED.
%
% In the base case, the Current=Final plan applies now

build_plan Facts Plan Plan Constraint Depth :-
	applies Facts Plan.

% In the recursive case, we find an action A that
% there's room for, that meets the constraint.
% We can remove any preconditions of the Initial 
% plan that A establishes; the remaining preconditions,
% become preconditions of the new plan - and we must
% check that doing A won't disrupt these preconditions
% when we establish them before doing A.  Further,
% we add the preconditions of A itself.

build_plan Facts Initial Plan Constraint Depth :-
	Depth > 0,
	is_action A Pre Post Del,
	Constraint A,
	circ Initial Deps,
	remove Post Deps SomeDeps,
	disjoint SomeDeps Del,
	union Pre SomeDeps NewDeps,
	NewDepth is Depth - 1,
	build_plan Facts (step NewDeps A Initial) Plan (a\true) NewDepth.

%------------------------------------------

type repair_plan 	list fact -> plan -> plan -> int -> o.

% (repair_plan Facts Old New Depth)
%     returns true if New is a plan that involves
%     at most Depth steps that aren't in Old plan,
%     eliminates at least one step of Old plan,
%     and can be executed in the circumstances
%     described by Facts.

repair_plan Facts (step Pre B Post) Next Depth :-
	build_plan Facts Post Next (a \ not (a = B)) Depth.

repair_plan Facts (step Pre B Post) Next Depth :-
	repair_plan Facts Post Next Depth.

%%%%%%
%---------------------------------------
% Simulation Loop for an Agent with Intentions.
%---------------------------------------

module IntendingAgent.
import BasicPlan.

%---------------------------------------
%
% As always we'll record the agent's
% history in state data structures.

kind state 	type.
type start	state.
type do		action -> state -> state.

%---------------------------------------
% Interact with the world 
%    (via side effects).

type perceive	state -> list fact -> o.

perceive State Facts :-
	output std_out "What is agent's current db?\n",
	input_line std_in FactString,
	string_to_term FactString Facts.

type execute	state -> action -> o.

execute State Action :-
	output std_out "Agent performs action ",
	term_to_string Action AS,
	output std_out AS,
	output std_out ".\n\n".

%---------------------------------------
%
% Predicates describing deliberation.
%   At each point, the agent has a
%   history and its intentions for the future.

type agitate 	state -> plan -> o.
type act 	state -> plan -> o.
type update	state -> list fact -> plan -> plan -> o.

% Agent simulation involves carrying out a
%    Perception,
%    Deliberation,
%    Action 
% loop.

agitate State Intentions :-
	perceive State Beliefs,
	update State Beliefs Intentions NewIntentions,
	!,
	act State NewIntentions.

% Act:
%  Stop if you're done;
%  Otherwise, do the next action, and continue
%    deliberating.

act State (finish G).
act State (step C A P) :-
	execute State A,
	agitate (do A State) P.

%----------------------------------------------
% Iterative deepening search.

type id		(int -> o) -> int -> o.

id Pred Tried :-
	Pred Tried.

id Pred Tried :-	
	Next is Tried + 1,
	id Pred Next.

% To determine your new intentions:
% - continue with what you were doing, if it's working,
% - make the smallest fix to what you're doing, otherwise.

update State Facts Plan Plan :-
	applies Facts Plan,
	output std_out "Agent continues with plan.\n".

update State Facts Plan Next :-
	id (n \ (build_plan Facts Plan Next (a \ true) n;
	         repair_plan Facts Plan Next n)) 0,
	output std_out "Agent decides ",
	describe_plan Next.

%%%%%%
%---------------------------------------
% Test domain.
%---------------------------------------

module A5.
accumulate IntendingAgent.

type closed, open, empty, keyed, locked, unlocked	fact.
type key, turn, pull, unkey				action.

is_action key (empty::nil) (keyed::nil) (empty::nil).
is_action turn (keyed::locked::nil) (unlocked::nil) (locked::nil).
is_action turn (keyed::unlocked::nil) (locked::nil) (unlocked::nil).
is_action pull (closed::unlocked::nil) (open::nil) (closed::nil).
is_action unkey (keyed::nil) (empty::nil) (keyed::nil).

% :- agitate start (finish (open::empty::nil)).
%
% Typical transition:
%   from closed::empty::locked::nil.
%   agent decides on plan
%      key, turn, unkey, pull
%
% At that point, if things work, we should see
% A: key
% P: closed::keyed::locked::nil.
% A: turn
% P: closed::keyed::unlocked::nil.
% A: unkey
% P: closed::empty::unlocked::nil.
% A: pull
% P: open::empty::unlocked::nil.
%
% Another experiment:
%  unexpected opportunities (skip one)
%  setbacks (repeat one).