CS 312: Artificial Intelligence
Assignment 2
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:
1. Due date for Assignment is 11:59 PM 2 Jan 2022.
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.
4. We will run a plagiarism check for all the submissions, If found copied, 0% score will be
awarded.
5. Penalty of 10% will be issued per day if the deadline is not met.
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.
