Task 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 goal state beforehand and path to Goal state is more important
For the above domain implement the following search algorithms:
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.
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:
Correctness: 10
Report: 5
Code Quality: 5
For Reference :
Heuristic search and Hill Climbing:
https://drive.google.com/file/d/1rNpKGSBK_bd9lhs5suOH8VYaVxqO4dgy/view?usp=sharing Beam Search Tabu Search: https://drive.google.com/file/d/1gbWgDeCurYZN35yd7fov_2U5wqZ1HIQT/view?usp=sharing
Report Format :
Brief description about the domain:State space
Start node and goal node
MOVEGEN and GOALTEST algorithm
Heuristic functions considered ( minimum of 2 )
Best First search analysis and observation
Hill Climbing and Best First search comparison in terms of:States explored
Time taken
Reaching the optimal solution.
