Question $6(3$ points$)$: Corners Problem: Heuristic

Note: Make sure to complete Question $4$ before working on Question $6,$ because Question $6$ builds upon your answer for Question $4.$

Implement a non$-$trivial, consistent heuristic for the CornersProblem in cornersHeuristic.

python

pacman.py $-1$ mediumCorners $-$p AStarCornersAgent $-$z $0\mathrm{.}5$

Note: AStarCornersAgent is a shortcut for

$-$p SearchAgent $-$a fn$=$aStarSearch, prob$=$CornersProblem,heuristic$=$cornersHeuristic.

Admissibility vs$.$ Consistency: Remember, heuristics are just functions that take search states and return numbers that estimate the

cost to a nearest goal. More effective heuristics will return values closer to the actual goal costs. To be admissible, the heuristic values

must be lower bounds on the actual shortest path cost to the nearest goal $($and non$-$negative$).$ To be consistent, it must additionally hold

that if an action has cost $c,$ then taking that action can only cause a drop in heuristic of at most $c.$

Remember that admissibility isn't enough to guarantee correctness in graph search $--$ you need the stronger condition of consistency.

However, admissible heuristics are usually also consistent, especially if they are derived from problem relaxations. Therefore it is usually

easiest to start out by brainstorming admissible heuristics. Once you have an admissible heuristic that works well, you can check whether

it is indeed consistent, too. The only way to guarantee consistency is with a proof. However, inconsistency can often be detected by

verifying that for each node you expand, its successor nodes are equal or higher in in f$-$value. Moreover, if UCS and $A^{*}$ ever return paths of

different lengths, your heuristic is inconsistent. This stuff is tricky!

Non$-$Trivial Heuristics: The trivial heuristics are the ones that return zero everywhere $($UCS$)$ and the heuristic which computes the true

completion cost. The former won't save you any time, while the latter will timeout the autograder. You want a heuristic which reduces total

compute time, though for this assignment the autograder will only check node counts $($aside from enforcing a reasonable time limit$).$

Grading: Your heuristic must be a non$-$trivial non$-$negative consistent heuristic to receive any points. Make sure that your heuristic returns

$0$ at every goal state and never returns a negative value. Depending on how few nodes your heuristic expands, you'll be graded:

Remember: If your heuristic is inconsistent, you will receive no credit, so be careful!