diff options
| -rw-r--r-- | .vscode/launch.json | 70 | ||||
| -rw-r--r-- | search.py | 103 | ||||
| -rw-r--r-- | searchAgents.py | 59 |
3 files changed, 154 insertions, 78 deletions
diff --git a/.vscode/launch.json b/.vscode/launch.json index 2c0f7aa..4788109 100644 --- a/.vscode/launch.json +++ b/.vscode/launch.json @@ -17,7 +17,6 @@ "program": "pacman.py", "args": [ "--frameTime=0.02", - "--catchExceptions", "--pacman=SearchAgent", "--agentArgs=fn=tinyMazeSearch", "--layout=${input:mazeLayout}", @@ -30,7 +29,6 @@ "program": "pacman.py", "args": [ "--frameTime=0.02", - "--catchExceptions", "--pacman=SearchAgent", "--agentArgs=fn=depthFirstSearch", "--layout=${input:mazeLayout}", @@ -43,7 +41,6 @@ "program": "pacman.py", "args": [ "--frameTime=0.02", - "--catchExceptions", "--pacman=SearchAgent", "--agentArgs=fn=breadthFirstSearch", "--layout=${input:mazeLayout}", @@ -56,39 +53,69 @@ "program": "pacman.py", "args": [ "--frameTime=0.02", - "--catchExceptions", "--pacman=SearchAgent", "--agentArgs=fn=uniformCostSearch", "--layout=${input:mazeLayout}", ] }, { - "name": "aStarSearch", + "name": "AStarSearch", "type": "python", "request": "launch", "program": "pacman.py", "args": [ "--frameTime=0.02", - "--catchExceptions", "--pacman=SearchAgent", "--agentArgs=fn=aStarSearch,heuristic=${input:heuristic}", "--layout=${input:mazeLayout}", ] + }, + { + "name": "UCSCorners", + "type": "python", + "request": "launch", + "program": "pacman.py", + "args": [ + "--frameTime=0.02", + "--pacman=SearchAgent", + "--agentArgs=fn=uniformCostSearch,prob=CornersProblem", + "--layout=${input:corners_mazeLayout}", + ] + }, + { + "name": "AStarCorners", + "type": "python", + "request": "launch", + "program": "pacman.py", + "args": [ + "--frameTime=0.02", + "--pacman=AStarCornersAgent", + "--layout=${input:corners_mazeLayout}", + ] + }, + { + "name": "AStarFoodSearchAgent", + "type": "python", + "request": "launch", + "program": "pacman.py", + "args": [ + "--frameTime=0.02", + "--pacman=AStarFoodSearchAgent", + "--layout=${input:corners_mazeLayout}", + ] } ], "inputs": [ { - "id": "searchAlgorithm", + "id": "mazeLayout", "type": "pickString", - "description": "Select the search algorithm", + "description": "Select the maze layout", "options": [ - "tinyMazeSearch", - "depthFirstSearch", - "breadthFirstSearch", - "uniformCostSearch", - "aStarSearch" + "tinyMaze", + "mediumMaze", + "bigMaze" ], - "default": "aStarSearch" + "default": "tinyMaze" }, { "id": "heuristic", @@ -97,11 +124,20 @@ "options": [ "nullHeuristic", "manhattanHeuristic", - "euclideanHeuristic", - "cornersHeuristic", - "foodHeuristic" + "euclideanHeuristic" ], "default": "nullHeuristic" + }, + { + "id": "corners_mazeLayout", + "type": "pickString", + "description": "Select the maze layout", + "options": [ + "tinyCorners", + "mediumCorners", + "bigCorners" + ], + "default": "tinyCorners" } ] }
\ No newline at end of file @@ -96,28 +96,31 @@ def depthFirstSearch(problem): # Initialize start node and push onto nodes, nodes.push((problem.getStartState(), None, 0, [])) - # Dictionary of visited nodes; key: node's (x,y); value: current cost of - # actions to get to the node - visited = {} + # Lists used to keep track of visited nodes and their costs + visitedList = [] + visitedCost = [] while not nodes.isEmpty(): node = nodes.pop() + state = node[0] + actions = node[3] # If the node has been traversed by a cheaper path, skip it - if visited.has_key(node[0]) and visited[node[0]] <= cost(node): + if state in visitedList and visitedCost[visitedList.index(state)] <= cost(node): continue - # Add set the value at the nodes index to the cost - visited[node[0]] = cost(node) + # Add the node to the visited lists + visitedList.append(state) + visitedCost.append(cost(node)) - # Chech if the current node is the goal state and if it is, return the path - if problem.isGoalState(node[0]): - return node[3] + # Check if the current node is the goal state and if it is, return the path + if problem.isGoalState(state): + return actions # Get all successors, and set each nodes's path to previous node's # path + nextNode's direction and push it onto stack - for nextNode in problem.getSuccessors(node[0]): - nextNode = nextNode + (node[3] + [nextNode[1]],) + for state, action, stepCost in problem.getSuccessors(state): + nextNode = (state, action, stepCost, actions + [action]) nodes.push(nextNode) @@ -133,28 +136,31 @@ def breadthFirstSearch(problem): # Initialize start node and push onto nodes, nodes.push((problem.getStartState(), None, 0, [])) - # Dictionary of visited nodes; key: node's (x,y); value: current cost of - # actions to get to the node - visited = {} + # Lists used to keep track of visited nodes and their costs + visitedList = [] + visitedCost = [] while not nodes.isEmpty(): node = nodes.pop() + state = node[0] + actions = node[3] # If the node has been traversed by a cheaper path, skip it - if visited.has_key(node[0]) and visited[node[0]] <= cost(node): + if state in visitedList and visitedCost[visitedList.index(state)] <= cost(node): continue - # Add set the value at the nodes index to the cost - visited[node[0]] = cost(node) + # Add the node to the visited lists + visitedList.append(state) + visitedCost.append(cost(node)) - # Chech if the current node is the goal state and if it is, return the path - if problem.isGoalState(node[0]): - return node[3] + # Check if the current node is the goal state and if it is, return the path + if problem.isGoalState(state): + return actions # Get all successors, and set each nodes's path to previous node's # path + nextNode's direction and push it onto stack - for nextNode in problem.getSuccessors(node[0]): - nextNode = nextNode + (node[3] + [nextNode[1]],) + for state, action, stepCost in problem.getSuccessors(state): + nextNode = (state, action, stepCost, actions + [action]) nodes.push(nextNode) @@ -170,28 +176,31 @@ def uniformCostSearch(problem): # Initialize start node and push onto nodes, nodes.push((problem.getStartState(), None, 0, [])) - # Dictionary of visited nodes; key: node's (x,y); value: current cost of - # actions to get to the node - visited = {} + # Lists used to keep track of visited nodes and their costs + visitedList = [] + visitedCost = [] while not nodes.isEmpty(): node = nodes.pop() + state = node[0] + actions = node[3] # If the node has been traversed by a cheaper path, skip it - if visited.has_key(node[0]) and visited[node[0]] <= cost(node): + if state in visitedList and visitedCost[visitedList.index(state)] <= cost(node): continue - # Add set the value at the nodes index to the cost - visited[node[0]] = cost(node) + # Add the node to the visited lists + visitedList.append(state) + visitedCost.append(cost(node)) - # Chech if the current node is the goal state and if it is, return the path - if problem.isGoalState(node[0]): - return node[3] + # Check if the current node is the goal state and if it is, return the path + if problem.isGoalState(state): + return actions # Get all successors, and set each nodes's path to previous node's # path + nextNode's direction and push it onto stack - for nextNode in problem.getSuccessors(node[0]): - nextNode = nextNode + (node[3] + [nextNode[1]],) + for state, action, stepCost in problem.getSuccessors(state): + nextNode = (state, action, stepCost, actions + [action]) nodes.push(nextNode) @@ -210,35 +219,37 @@ def aStarSearch(problem, heuristic=nullHeuristic): # 2. Nodes: Data structure to store the nodes cost = lambda node: problem.getCostOfActions(node[3]) + heuristic(node[0], problem) nodes = util.PriorityQueueWithFunction(cost) - + # Initialize start node and push onto nodes, nodes.push((problem.getStartState(), None, 0, [])) - # Dictionary of visited nodes; key: node's (x,y); value: current cost of - # actions to get to the node - visited = {} + # Lists used to keep track of visited nodes and their costs + visitedList = [] + visitedCost = [] while not nodes.isEmpty(): node = nodes.pop() + state = node[0] + actions = node[3] # If the node has been traversed by a cheaper path, skip it - if visited.has_key(node[0]) and visited[node[0]] <= cost(node): + if state in visitedList and visitedCost[visitedList.index(state)] <= cost(node): continue - # Add set the value at the nodes index to the cost - visited[node[0]] = cost(node) + # Add the node to the visited lists + visitedList.append(state) + visitedCost.append(cost(node)) - # Chech if the current node is the goal state and if it is, return the path - if problem.isGoalState(node[0]): - return node[3] + # Check if the current node is the goal state and if it is, return the path + if problem.isGoalState(state): + return actions # Get all successors, and set each nodes's path to previous node's # path + nextNode's direction and push it onto stack - for nextNode in problem.getSuccessors(node[0]): - nextNode = nextNode + (node[3] + [nextNode[1]],) + for state, action, stepCost in problem.getSuccessors(state): + nextNode = (state, action, stepCost, actions + [action]) nodes.push(nextNode) - # Abbreviations bfs = breadthFirstSearch dfs = depthFirstSearch diff --git a/searchAgents.py b/searchAgents.py index 1d757b1..9a6f0ab 100644 --- a/searchAgents.py +++ b/searchAgents.py @@ -273,7 +273,7 @@ class CornersProblem(search.SearchProblem): You must select a suitable state space and successor function """ - def __init__(self, startingGameState): + def __init__(self, startingGameState, visualize = True): """ Stores the walls, pacman's starting position and corners. """ @@ -287,22 +287,34 @@ class CornersProblem(search.SearchProblem): self._expanded = 0 # DO NOT CHANGE; Number of search nodes expanded # Please add any code here which you would like to use # in initializing the problem - "*** YOUR CODE HERE ***" + goals = dict(zip(self.corners, [False]*len(self.corners))) + self.startState = (self.startingPosition, goals) + + # For display purposes + self._visited, self._visitedlist, self._expanded = {}, [], 0 # DO NOT CHANGE def getStartState(self): """ Returns the start state (in your state space, not the full Pacman state space) """ - "*** YOUR CODE HERE ***" - util.raiseNotDefined() + return self.startState def isGoalState(self, state): """ Returns whether this search state is a goal state of the problem. """ - "*** YOUR CODE HERE ***" - util.raiseNotDefined() + isGoal = all(state[1].values()) + + # For display purposes only + if isGoal: + self._visitedlist.append(state[0]) + import __main__ + if '_display' in dir(__main__): + if 'drawExpandedCells' in dir(__main__._display): #@UndefinedVariable + __main__._display.drawExpandedCells(self._visitedlist) #@UndefinedVariable + + return isGoal def getSuccessors(self, state): """ @@ -319,14 +331,25 @@ class CornersProblem(search.SearchProblem): for action in [Directions.NORTH, Directions.SOUTH, Directions.EAST, Directions.WEST]: # Add a successor state to the successor list if the action is legal # Here's a code snippet for figuring out whether a new position hits a wall: - # x,y = currentPosition - # dx, dy = Actions.directionToVector(action) - # nextx, nexty = int(x + dx), int(y + dy) - # hitsWall = self.walls[nextx][nexty] + (x,y), goals = state + dx, dy = Actions.directionToVector(action) + nextx, nexty = int(x + dx), int(y + dy) + if not self.walls[nextx][nexty]: + successor = (nextx, nexty) + newGoals = goals.copy() + for corner in self.corners: + if successor == corner: + newGoals[successor] = True + + successors.append(((successor, newGoals), action, 1)) - "*** YOUR CODE HERE ***" + # For display purposes only + if state[0] not in self._visited: + self._visited[state[0]] = True + self._visitedlist.append(state[0]) self._expanded += 1 # DO NOT CHANGE + return successors def getCostOfActions(self, actions): @@ -356,11 +379,17 @@ def cornersHeuristic(state, problem): shortest path from the state to a goal of the problem; i.e. it should be admissible (as well as consistent). """ + corners = problem.corners # These are the corner coordinates - walls = problem.walls # These are the walls of the maze, as a Grid (game.py) - - "*** YOUR CODE HERE ***" - return 0 # Default to trivial solution + # walls = problem.walls # These are the walls of the maze, as a Grid (game.py) + position, visited = state + getDistance = lambda corner: abs(position[0] - corner[0]) + abs(position[1] - corner[1]) + unvisited = filter(lambda corner: not visited[corner], corners) + + if len(unvisited) == 0: + return 0 + + return getDistance(max(unvisited, key=getDistance)) class AStarCornersAgent(SearchAgent): "A SearchAgent for FoodSearchProblem using A* and your foodHeuristic" |