How to implement locked doors game in Prolog?

Question

I am working on a search problem in prolog where agent whose goal is to get to some treasure. At each time step, the agent can move between rooms using doors arranged according to an undirected graph. However, some of the doors are locked, and the agent must acquire the appropriate key in order to pass through a locked door. I worked on code, and code produces following actions "Actions = [move(0, 1), move(1, 3), move(3, 4), move(4, 2), move(2, 5), move(5, 6)]" but the supposed actions are: "Actions = [move(0, 1), move(1, 3), move(3, 4), move(4, 2), move(2, 5), move(5, 6)]." code is:

initial(0).

door(0,1).
door(0,2).
door(1,2).
door(1,3).
door(2,4).

locked_door(2,5,red).
locked_door(5,6,blue).

key(3,red).
key(4,blue).

treasure(6).

initial_state(state(Pos, noKey, noKey)) :- % Initial position with no keys
    initial(Pos).

% Moving without picking up a key or using a key
take_action(state(A, RedKey, BlueKey), move(A,B), state(B, RedKey, BlueKey)) :-
    door(A,B).
take_action(state(A, RedKey, BlueKey), move(A,B), state(B, RedKey, BlueKey)) :- 
    door(B,A).


% Picking up a red key
take_action(state(A, noKey, noKey), move(A,B), state(B, hasKey(red), noKey)) :-
    door(A,B),
    key(B, red).


% Picking up a blue key
take_action(state(A, hasKey(red), noKey), move(A,B), state(B, hasKey(red), hasKey(blue))) :-
    door(A,B),
    key(B, blue).


% open locked doors
take_action(state(A, hasKey(red), hasKey(blue)), move(A,B), state(B, hasKey(red), hasKey(blue))) :-
    locked_door(A,B,blue).
take_action(state(A, hasKey(red), hasKey(blue)), move(A,B), state(B, hasKey(red), hasKey(blue))) :-
    locked_door(B,A,blue).
take_action(state(A, hasKey(red), hasKey(blue)), move(A,B), state(B, hasKey(red), hasKey(blue))) :-
    locked_door(A,B,red).
take_action(state(A, hasKey(red), hasKey(blue)), move(A,B), state(B, hasKey(red), hasKey(blue))) :-
    locked_door(B,A,red).

final_state(state(Pos, _, _)) :- treasure(Pos).

take_steps(S0, [Action], S1) :- take_action(S0, Action, S1).
take_steps(S0, [Action | Rest], SFinal) :-
    take_action(S0, Action, SNew),
    take_steps(SNew, Rest, SFinal).

search(Actions) :-
    initial_state(S0),
    length(Actions, _), 
    take_steps(S0, Actions, SFinal),
    final_state(SFinal), !.

Answer 1

The Logtalk distribution includes a state-space searching programming example implementing a framework for solving state-space search problems. It includes abstractions of heuristic and non-heuristic state spaces plus several search methods allowing applying multiple search methods to a state space and applying a search method to multiple state spaces. A corrected definition of the "locked doors" state space using this framework could be:

:- object(doors,
    instantiates(state_space)).

    initial_state(start, s(Room, no_key, no_key)) :-
        initial(Room).

    goal_state(end, s(Room, _, _)) :-
        treasure(Room).

    % moving without picking up a key or using a key
    next_state(s(A, Red, Blue), s(B, Red, Blue)) :-
        door(A, B).
    next_state(s(A, Red, Blue), s(B, Red, Blue)) :-
        door(B, A).
    % picking up a red key
    next_state(s(A, no_key, Blue), s(B, red, Blue)) :-
        door(A, B),
        key(B, red).
    % picking up a blue key
    next_state(s(A, Red, no_key), s(B, Red, blue)) :-
        door(A, B),
        key(B, blue).
    % open locked doors
    next_state(s(A, Red, blue), s(B, Red, blue)) :-
        locked_door(A, B, blue).
    next_state(s(A, Red, blue), s(B, Red, blue)) :-
        locked_door(B, A, blue).
    next_state(s(A, red, Blue), s(B, red, Blue)) :-
        locked_door(A, B, red).
    next_state(s(A, red, Blue), s(B, red, Blue)) :-
        locked_door(B, A, red).

    print_state(State) :-
        write(State),
        nl.

    initial(0).

    door(0, 1).
    door(0, 2).
    door(1, 2).
    door(1, 3).
    door(2, 4).

    locked_door(2, 5, red).
    locked_door(5, 6, blue).

    key(3, red).
    key(4, blue).

    treasure(6).

:- end_object.

Note that grabbing a key is independent of holding or not holding the other key, something that's incorrect in your code (unless your description of the problem is incomplete). Other changes are for either making the code more compact, simpler, or coding guidelines.

To get the shortest solution, we can use the provided breadth-first search method. Assuming the object above saved in a doors.lgt file in the current directory and using Logtalk with the Trealla Prolog backend:

$ tplgt -q
?- {searching(loader), doors}.
   true.
?- doors::initial_state(Initial), breadth_first(20)::solve(doors, Initial, Path), doors::print_path(Path).
s(0,no_key,no_key)
s(1,no_key,no_key)
s(3,red,no_key)
s(1,red,no_key)
s(2,red,no_key)
s(4,red,blue)
s(2,red,blue)
s(5,red,blue)
s(6,red,blue)
   Initial = s(0,no_key,no_key), Path = [s(0,no_key,no_key),s(1,no_key,no_key),s(3,red,no_key),s(1,red,no_key),s(2,red,no_key),s(4,red,blue),s(2,red,blue),s(5,red,blue),s(6,red,blue)]
;

Backtracking will give you solutions of increasing length.