I'm working on an assignment from an archived AI course from 2014.
The parameter "problem" refers to an object that has different cost functions chosen at run (sometimes it is 1 cost per move; sometimes moves are more expensive depending on which side of the pacman board the moves are done on).
As written below, I get the right behavior but I open more search nodes than expected (about 2x what the assignment expects).
If I turn the cost variable to negative, I get the right behavior on the 1-unit cost case AND get a really low number of nodes. But the behavior is opposite for the cases of higher costs for a given side of the board.
So basically question is: Does it seem like I'm opening any nodes unnecessarily in the context of a uniform cost search?
def uniformCostSearch(problem):
"""Search the node of least total cost first."""
def UCS(problem, start):
q = util.PriorityQueue()
for node in problem.getSuccessors(start): ## Comes a tuple ((x,y), 'North', 1)
q.push([node], node[2]) ##Push nodes onto queue one a time (so they are paths)
while not q.isEmpty():
pathToCheck = q.pop() ##Pops off the lowest priorty path on the queue?
#if pathToCheck in q.heap:
# continue
lastNode = pathToCheck[-1][0] ## Gets the coordinates of that last node in that path
if problem.isGoalState(lastNode): ##Checks if those coordinates are goal
return pathToCheck ## If goal, returns that path that was checked
else: ## Else, need to get successors of that node and put them on queue
for successor in problem.getSuccessors(lastNode): ##Gets those successors the popped path's last node and iterates over them
nodesVisited = [edge[0] for edge in pathToCheck] ##Looks at all the edges (the node plus its next legal move and cost) and grabs just the coords visited (nodes)
if successor[0] not in nodesVisited: ## ##Checks to see if those visited were in THIS particular path (to avoid cyclces)
newPath = pathToCheck + [successor] ## If ONE successor was not in path, adds it to the growing path (will do the next one in next part of loop)
cost = problem.getCostOfActions([x[1] for x in newPath])
q.update(newPath, cost) #Pushes that validated new path onto the back of the queue for retrieval later
return None
start = problem.getStartState()#Starting point of stack
successorList = UCS(problem, start)
directions = []
for i in range(len(successorList)):
directions += successorList[i]
return directions[1::3]
