% id_plan
%  General planning algorithm using iterative-deepening search

% This planner needs the predicates below to be defined:
%     - legal_move(BeforeState,Move,AfterState)
%     - initial_state(State)
%     - goal_state(State)

% plan(L): L is a list of moves from the initial state to a goal state.
id_plan(L) :-
    initial_state(I),
    id_plan(I, L).

% This version takes initial state as first argument
id_plan(I, L) :-
    goal_state(G),
    list(L), 
    print_curr_depth(L),
    reachable(I, L, G).

print_curr_depth(L):- length(L, Len), write(Len), nl.

% reachable(S1,L,S2): S2 is reachable from S1 using moves L.
reachable(S,[],S).           
reachable(S1,[M|L],S3) :-
    legal_move(S1,M,S2),
    reachable(S2,L,S3).

% generate lists of increasing lengths.
list([]).
list([_|T]) :- list(T).


% idg_plan iterative deepening graph search (cycle avoidance).

:- use_module(sets).
   
idg_plan(I, L):-
    list_to_set([I], Visited),  % generate set of states already seen
    goal_state(G),
    list(L),
    reachable(I, Visited, L, G).

% reachable(S0, Visited, Actions, S) -- like reachable/3 but avoiding states
%     that have already been visited on path (Visited set) to avoid cycles.

% TODO: complete this predicate
