Able to find path using DFS but not able specify the right directions to Pacman _ Python

Question

I am working on an assignment found on an AI course page at berkley website for fun. I need to write a depth-first search for the pacman game so that it can find its path.The problem is the pacman gets stuck. I'll paste the code first to make what I am saying more clear :

import util

class SearchProblem:
  """
  This class outlines the structure of a search problem, but doesn't implement
  any of the methods (in object-oriented terminology: an abstract class).

  You do not need to change anything in this class, ever.
  """

  def getStartState(self):
     """
     Returns the start state for the search problem 
     """
     util.raiseNotDefined()

  def isGoalState(self, state):
     """
       state: Search state

     Returns True if and only if the state is a valid goal state
     """
     util.raiseNotDefined()

  def getSuccessors(self, state):
     """
       state: Search state

     For a given state, this should return a list of triples, 
     (successor, action, stepCost), where 'successor' is a 
     successor to the current state, 'action' is the action
     required to get there, and 'stepCost' is the incremental 
     cost of expanding to that successor
     """
     util.raiseNotDefined()

  def getCostOfActions(self, actions):
     """
          actions: A list of actions to take

     This method returns the total cost of a particular sequence of actions.  The sequence must
     be composed of legal moves
     """
     util.raiseNotDefined()


def tinyMazeSearch(problem):
  """
      Returns a sequence of moves that solves tinyMaze.  For any other
  maze, the sequence of moves will be incorrect, so only use this for tinyMaze
  """
  from game import Directions
  s = Directions.SOUTH
  w = Directions.WEST
  return  [s,s,w,s,w,w,s,w]

def depthFirstSearch(problem):

  """
  Search the deepest nodes in the search tree first [p 74].

  Your search algorithm needs to return a list of actions that reaches
  the goal.  Make sure to implement a graph search algorithm [Fig. 3.18].

  To get started, you might want to try some of these simple commands to
  understand the search problem that is being passed in:

  print 'Start:', problem.getStartState()
  print 'Is the start a goal?', problem.isGoalState(problem.getStartState())
  print 'Start's successors:', problem.getSuccessors(problem.getStartState())

  """

  # *** YOUR CODE HERE ***


  start = [problem.getStartState()]
  for item in start:
      Open=[item]
  State=[]
  Closed=[]
  Path=[]

  if problem.isGoalState(Open[0]) is True:
      return State
  else:
       while Open:
                visit= Open.pop()
                Closed.append(visit)
                if State: 
                  Path.append(State.pop())

                if problem.isGoalState(visit) is True:
                    print Closed
                    return Path
                else:
                    Successors= problem.getSuccessors(visit)
                    for index in Successors:
                            it=iter(index)
                            data=it.next()

                            if data not in Closed :
                              Open.append(data)
                              State.append(it.next())
                            else:
                              print Path

Now if you will read my code under dfs you will see that open list contains all the points I visit and expanded.

The Path file contains the direction set for the pacman. The problem arises when I face the condition that both successors I get are unvisited, my pacman takes a path which leads to a dead end so it needs to backtrace. My Open does it and finds the solution but I am not able to find a way on how to provide the directions of backtracing in my path list. If you will go to http://inst.eecs.berkeley.edu/~cs188/sp09/projects/search/search.html and download the zip and paste my code in search.py under dfs search you will understand my problem.

Answer 1

Some hints:

• Each node you check should encapsulate the data of how you got there.
• DFS is like a stack; you start by pushing the start state. You pop the stack, and push back the nodes that can follow from the node you popped.
• Since you are ultimately trying to find a path, the node data must hold your location and the path you took to get there.

Answer 2

How you store your path is a VERY important topic, when you consider that some of your searches might result in paths 200+ steps long. Iterating over a list that many times.... O(2^N) or O(3^N)? lists for any kind of search as a path storing mechanism are the wrong answer, especially when you get into BFS and any time you have multiple objectives (meaning, multiple paths through the same node can exist). List complexity and the data storage is ridiculous.

I recommend linklisting as a path storage mechanism. When you push your nodes into the fringe, simply key them into a dictionary with a unique key and push the key. Then when you pull a node from the fringe, you can get the entire state, as is, from the dictionary.

If part of your state is the node that that state was in one step previously, then you have a path to the start; the end node links to the one behind it, which links to the one behind it, etc. Using a unique key system like this allows multiple paths through the same point, at EXTREMELY low data cost; you still must be rational about which paths you pull off the fringe. However, any time you pull anything off the fringe, you pull it's entire path, with only 1 number.

Answer 3

I did get it work by making sure each move is only 1 distance. One of the issue with your code was at the end it try to jump 5 or 6 places. Make sure every move it make is one and reverse till move distance become 1 to your next destination. Hint manhattanDistance().

Answer 4

 start = [problem.getStartState()]
  for item in start:
      Open=[item]
  Closed=[]
  Path=[]

  if problem.isGoalState(Open[0]) is True:
      return 
  else:
       count=0
       while Open:
                if count==0:
                  visit=Open.pop()
                else:
                  temp=Open.pop()
                  visit=temp[0]

                Closed.append(visit)                            
                if problem.isGoalState(visit) is True:
                    return Path
                else:
                    Successors= problem.getSuccessors(visit)
                    for index in Successors:
                            if index[0] not in Closed :
                              Open.append((index[0],index[1]))
                print Open
                count=count+1

i changed the code as u said. right now i am not having anything in path.

this open after finding the solution -( 1,1 is the solution)

[((5, 4), 'South'), ((4, 5), 'West')]
[((5, 4), 'South'), ((3, 5), 'West')]
[((5, 4), 'South'), ((2, 5), 'West')]
[((5, 4), 'South'), ((1, 5), 'West')]
[((5, 4), 'South'), ((1, 4), 'South')]
[((5, 4), 'South'), ((1, 3), 'South')]
[((5, 4), 'South'), ((2, 3), 'East')]
[((5, 4), 'South'), ((2, 2), 'South')]
[((5, 4), 'South'), ((2, 1), 'South'), ((3, 2), 'East')]
[((5, 4), 'South'), ((2, 1), 'South'), ((4, 2), 'East')]
[((5, 4), 'South'), ((2, 1), 'South'), ((4, 3), 'North')]
[((5, 4), 'South'), ((2, 1), 'South'), ((5, 3), 'East')]
[((5, 4), 'South'), ((2, 1), 'South'), ((5, 4), 'North')]
[((5, 4), 'South'), ((2, 1), 'South')]
[((5, 4), 'South'), ((1, 1), 'West')]

now if you will notice when it gets three list members it takes a path which was a dead end now the Open is able to backtrace and find the correct path but i need a way to somewhow specify the return direction in the Path variable like

for eg Path = ['south',west' west'.................] etc