In this challenge you will explore the implementation of heuristics for our maze problem and the representational challenges therein. In the first part, you will implement a heuristic I have provided. In the second part, you will implement one of several, and in the third part you will develop your own.
1. Follow the Left Wall
Begin with the Prolog program we developed in class for solving the maze problem. Modify it so that it solves the problem using the “follow the left wall” heuristic. That is, pretend you are the agent walking through the maze. Stick out your left hand so that it touches the wall. Keep your hand on the wall, following whatever turns you must, until you reach the exit!
2. Heuristic Improvement
Once again, begin with a copy of the Prolog program we developed in class. Select one of the following potential improvements to maze solving and implement it within the program:
- Prefer a movement which results in moving generally in the direction of the end of the maze.
- Prefer short hallways to long ones.
- Notice bad paths or regions of the maze and remove them from consideration (this is hard!)
3. Do Your Own Thing!
Develop a heuristic which you think would improve the maze solving, and test it out! Some thoughts:
- Would a change in representation of some part of the world improve things?
- Are there any tips or tricks we could integrate into the solution finding?
For this one, write up a one to three paragraph note in a comment in your code about what your heuristic does, why you chose it, and how successful it was. Reflect on what you might change.