Wednesday, February 11, 2015

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