Inductive-Logic-Programming-for-Maze-State-Transition-and-Planning-using-Prolog-Programming

Creator: Iman Sharifi

Email: iman.sharifi.edu@gmail.com

Abstract

Most Machine learning algorithms lack logical reasoning, data-efficiency, and interpretability, which makes the situation worse when is needed to be used in different environments from the training one. However, symbolic methods can simply get rid of these shartages using logical programming. In this project, we are going to find State Transition in the Maze gridworld using Prolog and Aleph. In fact, using pre-defined states, actions, neighborhood relations, and obstacles, we aim to find the next state in a given state by taking a specific action. This project shows that the extracted rules are gereralizeable to new environments.

State Transition in Maze using Aleph

Language Settings

Mode Declaration and Determination

:-modeh(*,next_state(+state,+act,-state)).
:-modeb(*,adjacent(+state,+act,-state)).
:-modeb(*,not_wall(+state)).
:-modeb(*,wall(+state)).

:-determination(next_state/3,adjacent/3).
:-determination(next_state/3,not_wall/1).
:-determination(next_state/3,wall/1).

Background Knowledge

States

state(X). means, X is a state.

state((1,1)). state((2,1)). state((3,1)).
state((1,2)). state((2,2)). state((3,2)).
state((1,3)). state((2,3)). state((3,3)).

If you want to creats maze states automatically, please use this code block:

:- dynamic state/1.
maxWidth(3).
maxHeight(3).

create:-
	maxWidth(N),
	maxHeight(M),
	forall(between(1,N,X),(
	forall(between(1,M,Y),assertz(state((X,Y)))))).

Actions

action(X). means, X is an action.

act(right).
act(left).
act(up).
act(down).

action(X):-act(X).

Neighborhood (adjacent)

adjacent(X,D,Y). means, if we be in state X and move in direction D, then we will be in the state Y.

adjacent((A,B),right,(C,D)):-state((A,B)),state((C,D)),D is B,C is A+1,!.
adjacent((A,B),left ,(C,D)):-state((A,B)),state((C,D)),D is B,C is A-1,!.
adjacent((A,B),up   ,(C,D)):-state((A,B)),state((C,D)),C is A,D is B-1,!.
adjacent((A,B),down ,(C,D)):-state((A,B)),state((C,D)),C is A,D is B+1,!.

adjacent(X,right,Y):-adjacent(Y,left,X).
adjacent(X,up,Y):-adjacent(Y,down,X).

Obstacles (walls)

wall(X). means, state X is an obstacle (wall).

wall((1,1)).
wall((1,2)).
wall((3,2)).
wall((3,3)).

not_wall(X):-not(wall(X)).

Positive Examples

next_state((1,3),right,(2,3)).
next_state((1,3),up,(1,3)).

next_state((2,3),right,(2,3)).
next_state((2,3),left,(1,3)).
next_state((2,3),up,(2,2)).

next_state((2,2),right,(2,2)).
next_state((2,2),left,(2,2)).
next_state((2,2),up,(2,1)).
next_state((2,2),down,(2,3)).

next_state((2,1),right,(3,1)).
next_state((2,1),left,(2,1)).
next_state((2,1),down,(2,2)).

next_state((3,1),left,(2,1)).
next_state((3,1),down,(3,1)).

Negative Examples

next_state((1,1),right,(2,1)).
next_state((1,1),down,(1,2)).

next_state((2,1),right,(2,1)).
next_state((2,1),left,(1,1)).
next_state((2,1),down,(2,1)).

next_state((3,1),left,(3,1)).
next_state((3,1),down,(3,2)).

next_state((1,2),right,(2,2)).
next_state((1,2),up,(1,1)).
next_state((1,2),down,(1,3)).

next_state((2,2),right,(3,2)).
next_state((2,2),left,(1,2)).
next_state((2,2),up,(2,2)).
next_state((2,2),down,(2,2)).

next_state((3,2),left,(2,2)).
next_state((3,2),up,(3,1)).
next_state((3,2),down,(3,3)).

next_state((1,3),right,(1,3)).
next_state((1,3),up,(1,2)).

next_state((2,3),right,(3,3)).
next_state((2,3),left,(2,3)).
next_state((2,3),up,(2,3)).

next_state((3,3),left,(2,3)).
next_state((3,3),up,(3,2)).

Extracted Rules

next_state(A,B,C) :-
   adjacent(A,B,C), not_wall(C), not_wall(A).
next_state(A,B,A) :-
   adjacent(A,B,C), wall(C).

Accuracy

Confusion Matrix

[Training set performance]
          Actual
       +        - 
     + 14        0        14 
Pred 
     - 0        24        24 

       14        24        38 

Accuracy = 1.0

How to run:

1. Before running, make sure you have installed YAP (Yet Another Prolog) on your OS Linux. To install YAP, you can simply use this link.

2. After installation, type yap in terminal and prolog command prompt will be opened.

3. Use pwd. command to find current directory and cd('files directory'). to change your directory.

4. load Aleph using [aleph]..

5. Use read_all(maze). to load language setting and background knowledge (maze.b), positive (maze.f) and negative examples (maze.n).

6. Use induce. to extract target rules.

7. To find bottum clauses one by one, just use sat(i). i is the number of a rule, and use reduce. to find rules.

8. To save extracted rules use write_rules('filename.txt').

State Transition in Maze using Metagol

Abstract

Meta-Interpretive Learning (MIL) is a machine learning technique that allows a learning system to modify its own knowledge representations and improve its own performance over time. This is in contrast to traditional machine learning, where the model is fixed and the learning process only adjusts the model's parameters.

MIL is based on the idea of learning by interpretation, where the learning system interprets examples, modifies its knowledge, and then re-interprets the examples. This process continues until the learning system reaches a satisfactory level of performance.

MIL has been applied in a variety of domains, including natural language processing, computer vision, and robotics. It has the advantage of allowing for incremental learning and the ability to continuously improve performance over time.

MIL is a relatively new and emerging field, and there is still much work to be done to fully understand its capabilities and limitations. However, it has shown promise as a powerful and flexible approach to machine learning that can be applied to a wide range of problems.

Language Settings

Metagol Settings

:- use_module('metagol').
max_clauses(5).

head_pred(next_state/3).
body_pred(adjacent/3).
body_pred(wall/1).
body_pred(not_wall/1).

Meta-Rules

metarule(postcon,[P,Q,R,S],[P,A,B,C],[[Q,A,B,C],[R,A],[S,C]]).
metarule(postcon2,[P,Q,R,S],[P,A,B,A],[[Q,A,B,C],[R,A],[S,C]]).

Extracted Rules

% learning next_state/3
% clauses: 1
% clauses: 2
next_state(A,B,C):-adjacent(A,B,C),not_wall(A),not_wall(C).
next_state(A,B,A):-adjacent(A,B,C),not_wall(A),wall(C).
true.

How to run:

1. Before running, make sure you have installed SWI-Prolog on your OS Linux.

2. After installation, type prolog in terminal and prolog command prompt will be opened.

3. Use pwd. command to find current directory and cd('files directory'). to change your directory.

4. Type consult('maze.pl')..

You can see the corresponding codes in this link.

Planning in Maze grid world using Prolog

% Next State next_state(S1,A,S2). means If we be in the legal state S1 and go towards action A, we will be in the legal state S2.

next_state(S1,A,S2):-adjacent(S1,A,S2),not_wall(S1),not_wall(S2).
next_state(S1,A,S1):-adjacent(S1,A,S2),not_wall(S1),wall(S2).

Required build-in predicates:

revert(X,Y):-reverse(X,Y).
not_member(X,Y):-not(member(X,Y)).

Planning rules

find_path(Start,Goal,Path):-not_wall(Start),not_wall(Goal),find_path_helper(Start,Goal,[],Path).
find_path_helper(State,State,Visited,Path):-revert([State|Visited],Path).
find_path_helper(State,Goal,Visited,Path):-
	next_state(State,Action,NewState),
	not_member(NewState,Visited),
	writeln(Action),
	find_path_helper(NewState,Goal,[State|Visited],Path),!.

outputs

?- find_path((3,1),(1,3),Path).
left
down
down
left
Path = [(3, 1),  (2, 1),  (2, 2),  (2, 3),  (1, 3)].

?- find_path((1,3),(3,1),Path).
right
up
up
right
Path = [(1, 3),  (2, 3),  (2, 2),  (2, 1),  (3, 1)].

You can readily find paths from one state (cell) to another state using Prolog in this link.

Planning in Maze grid world using Metagol

Language Settings

Metagol Settings

:- use_module('metagol').

max_clauses(10).

%% metagol settings
%head_pred(find_path/3).
body_pred(next_state/2).
body_pred(wall/1).
body_pred(not_wall/1).
body_pred(valid_state/1).

Meta-Rules

metarule(ident, [P,Q], [P,A,B], [[Q,A,B]]).
metarule(ident1, [P,Q], [P,A,B,C], [[Q,A,B,C]]).
metarule(ident2, [P,Q], [P,A,B,[A,B]], [[Q,A,B]]).
metarule(postcon, [P,Q,R], [P,A,B], [[R,B], [Q,A,B]]).
metarule(postcon1, [P,Q,R], [P,A,B], [[Q,A,B], [R,B]]).
metarule(recursion, [P,Q,R], [P,A,B,[A|L1]], [[R,B], [Q,A,C], [R,C], [P,C,B,L1]]).

Positive Examples

find_path((1,3),(2,3),[(1,3),(2,3)]),
find_path((1,3),(2,2),[(1,3),(2,3),(2,2)]),
find_path((1,3),(2,1),[(1,3),(2,3),(2,2),(2,1)]),
fid_path((1,3),(3,1),[(1,3),(2,3),(2,2),(2,1),(3,1)]),
find_path((3,1),(2,1),[(3,1),(2,1)]),
find_path((3,1),(2,2),[(3,1),(2,1),(2,2)]),
find_path((3,1),(2,3),[(3,1),(2,1),(2,2),(2,3)]),
find_path((3,1),(1,3),[(3,1),(2,1),(2,2),(2,3),(1,3)])

Negative Examples

find_path((1,3),(1,2),[(1,3),(1,2)]),
find_path((1,3),(2,2),[(1,3),(1,2),(2,2)]),
find_path((1,3),(2,1),[(1,3),(1,2),(1,1),(2,1)]),
find_path((1,3),(3,1),[(1,3),(2,3),(3,3),(3,2),(3,1)]),
find_path((3,1),(3,2),[(3,1),(3,2)]),
find_path((3,1),(2,2),[(3,1),(3,2),(2,2)]),
find_path((3,1),(2,3),[(3,1),(3,2),(3,3),(2,3)]),
find_path((3,1),(1,3),[(3,1),(2,1),(1,1),(1,2),(1,3)]),
find_path((1,1),(1,2),[(1,1),(1,2)]),
find_path((1,1),(2,1),[(1,1),(2,1)])

Extracted Rules

?- learn.
% learning find_path/3
% clauses: 1
% clauses: 2
find_path(A,B,[A,B]):-next_state(A,B).
find_path(A,B,[A|C]):-not_wall(B),next_state(A,D),not_wall(D),find_path(D,B,C).
true ;
find_path(A,B,[A,B]):-next_state(A,B).
find_path(A,B,[A|C]):-valid_state(B),next_state(A,D),valid_state(D),find_path(D,B,C).
true ;
% clauses: 3
find_path(A,B,C):-find_path_1(A,B,C).
find_path_1(A,B,[A,B]):-next_state(A,B).
find_path_1(A,B,[A|C]):-not_wall(B),next_state(A,D),not_wall(D),find_path_1(D,B,C).
true ;
find_path(A,B,C):-find_path_1(A,B,C).
find_path_1(A,B,[A,B]):-next_state(A,B).
find_path_1(A,B,[A|C]):-valid_state(B),next_state(A,D),valid_state(D),find_path_1(D,B,C).
true 

How to run:

1. Before running, make sure you have installed SWI-Prolog on your OS Linux.

2. After installation, type prolog in terminal and prolog command prompt will be opened.

3. Use pwd. command to find current directory and cd('files directory'). to change your directory.

4. Type consult('maze_planning_metagol.pl')..

We extracted some rules for finding paths from one state (cell) to another state using Metagol in this link.