CODEWITHSUNDEEP
pythona-star
MrWhetherMan
MrWhetherMan

Reputation: 1334

A* search not working in python

I am working on an online AI class assignment. As a part of the assignment, I have to implement A* search in python. My code:

def aStarSearch(problem, heuristic=nullHeuristic):
"""Search the node that has the lowest combined cost and heuristic first."""
"*** YOUR CODE HERE ***"

    fringe = util.PriorityQueue()
    visited = {} # Visited nodes

    if problem.isGoalState(problem.getStartState()):
        return []

    fringe.push((problem.getStartState(),[]),0)

    while not fringe.isEmpty():
        currentState, pathToCurrent = fringe.pop()
        currentCost = problem.getCostOfActions(pathToCurrent)

        if problem.isGoalState(currentState):
            return pathToCurrent

        if currentState not in visited or currentCost<visited[currentState]:
            visited[currentState]=currentCost
            for successor,action,stepCost in problem.getSuccessors(currentState):
                currentTotalCost = currentCost + stepCost + heuristic(currentState, problem)
                fringe.push((successor, pathToCurrent+[action]),currentTotalCost)
    return []

It looks correct to me, but when I run the autograder, it outputs the following:

*** FAIL: test_cases/q4/astar_1_graph_heuristic.test
***     graph:
***              2     3     2
***           S --- A --- C ---> G
***           | \       /       ^
***         3 |  \ 5   / 1     / 
***           |   \   /       / 
***           B --- D -------/
***              4         5  
***         
***         S is the start state, G is the goal.  Arrows mark possible state 
***         transitions.  The number next to the arrow is the cost of that transition.
***         
***         The heuristic value of each state is:
***             S 6.0
***             A 2.5
***             B 5.25
***             C 1.125
***             D 1.0625
***             G 0
***     student solution:       ['0', '0', '2']
***     student expanded_states:    ['S', 'A', 'C', 'D']
*** 
***     correct solution:       ['0', '0', '2']
***     correct expanded_states:    ['S', 'A', 'D', 'C']
***     correct rev_solution:       ['0', '0', '2']
***     correct rev_expanded_states:    ['S', 'A', 'D', 'C']

I'm not too experienced with python, but it seems to me that my code should pass this test. How can I fix my code so it will pass the test? Thanks in advance!

Upvotes: 1

Views: 1365

Answers (1)

happydave
happydave

Reputation: 7187

On this line:

currentTotalCost = currentCost + stepCost + heuristic(currentState, problem)

You're trying to figure out the cost at the successor node: that should be the path to the current node, plus the step cost, plus the heuristic expected cost at the successor node. So I think you should be calling heuristic(successor,problem), rather than heuristic(currentState,problem)

Upvotes: 6

Related Questions