This is the first part of the Pacman AI project. In this part of the project, I implemented several search algorithm, such as DFS, BFS, A*, UCS, Sub-optimal Search etc. In this post, I will also discuss how these algorithms can turn into each other under certain conditions.
Implementation of Algorithms
The implementation of these algorithms are all based on the graph search, and their differences are just that they have different priorities for unvisited paths/nodes to enqueue or dequeue.
Two search algorithms are defined to be equivalent if and only if they expand the same nodes in the same order and return the same path.
- How can we make Uniform Cost Search equivalent to Breadth-First Search?
We can set the cost dij = a, a>0.
- How can we make Uniform Cost Search equivalent to Depth-First Search?
We can set the cost dij = a, a<0.
- How can we make a new UCS with cost dij equivalent to a know UCS with cij?
We can set dij = a*cij, a>0.
- How to choose costs dij that make running Uniform Cost Search algorithm with these costs dij equivalent to running Greedy Search with the original costs cij and heuristic function h?
We can set dij = h(j) − h(i).
- How to choose the costs dij that make running Uniform Cost Search algorithm with these costs dij equivalent to running A* Search with the original costs cij and heuristic function h.
We can set dij = cij + h(j) − h(i).
As we may see from the above comparison, all these search algorithms are essentially under the same logic. The only difference between each other is how they decide the priority of the nodes to search.
This is the end of Pacman AI, Part I. Code can be found my GitHub.
Readers of the post should not copy any of my code for their own course assignment, but feel free to be inspired and come up with your own ones.
A current master student in WUSTL, department of Electrical and System Engineering.