Description
Heuristic Search Algorithms
Domain for this assignment is : Blocks World Domain –
Blocks World Domain Game starts with an initial state consisting of a fixed number of blocks arranged in 3 stacks and we can move only top blocks of the stacks and we have to achieve a goal state that is a particular arrangement of blocks by moving these blocks. Blocks World is a planning problem where we know the goal state beforehand and the path to the Goal state is more important.
For the above domain implement the following search algorithms:
1. Best First Search :
Try out a minimum of 3 different heuristic functions and compare the results with valid reasoning. Use a priority queue for the OPEN list to make it computationally efficient.
2. Hill Climbing :
With a slight modification of code, implement Hill Climbing for the domain. Compare the performance of the two in terms of time and space.
Evaluation Criteria: Total : 20 Points
Correctness: 10
Report: 5
Code Quality: 5
NOTE:
2. Submit the following files named with your group number.
a. Code: <group_number>.py
b. Input file if there (input.txt)
c. Report: <group_number>.pdf
d. Readme.txt ( How to execute your program)
3. Mode of submission is moodle.
Report Format :
1. Brief description about the domain:
a. State space
b. Start node and goal node
c. MOVEGEN and GOALTEST algorithm
2. Heuristic functions considered ( minimum of 2 )
3. Best First search analysis and observation
4. Hill Climbing and Best First search comparison in terms of:
a. States explored
b. Time taken
c. Reaching the optimal solution.
