AI Planning Tree Search Algorithm for Missionary And Cannibal Problem in Java

I have been doing AI Planning course and I decided to implement the first basic problem in Java. To implement this, i tried to create the algorithm with right level of abstractions so that it can be applied to any problem in future.

Some take aways in my package structure is that, I have maintained all the generic reusable code in definitions package and problem specific code in monkcannibal package.

To solve the problem, I have implemented State which had successor method, IProblem which defined the problem to solve and IStrategy which defined the strategy to take for state transition. Here I have used two strategies for tree travesal, breadth first search aka, BFS and Depth First Search, aka DFS.

The code is available on github at: https://github.com/biplav/aiplanning

The main file is : com.biplav.aiplanning.problems.monkcanibbal.MissionaryCannibalPlan.java


And the output is:

1:L->3m1cfalseboat R->0m2ctrueboat

2:L->3m2ctrueboat R->0m1cfalseboat

3:L->3m0cfalseboat R->0m3ctrueboat

4:L->3m1ctrueboat R->0m2cfalseboat

5:L->1m1cfalseboat R->2m2ctrueboat

6:L->2m2ctrueboat R->1m1cfalseboat

7:L->0m2cfalseboat R->3m1ctrueboat

8:L->0m3ctrueboat R->3m0cfalseboat

9:L->0m1cfalseboat R->3m2ctrueboat

10:L->1m1ctrueboat R->2m2cfalseboat

11:L->0m0cfalseboat R->3m3ctrueboat

Time consumed is 3

1:L->2m2cfalseboat R->1m1ctrueboat

2:L->3m2ctrueboat R->0m1cfalseboat

3:L->3m0cfalseboat R->0m3ctrueboat

4:L->3m1ctrueboat R->0m2cfalseboat

5:L->1m1cfalseboat R->2m2ctrueboat

6:L->2m2ctrueboat R->1m1cfalseboat

7:L->0m2cfalseboat R->3m1ctrueboat

8:L->0m3ctrueboat R->3m0cfalseboat

9:L->0m1cfalseboat R->3m2ctrueboat

10:L->0m2ctrueboat R->3m1cfalseboat

11:L->0m0cfalseboat R->3m3ctrueboat

Time consumed is 1