1) Implement a Queue class which inherits from Structure. It should implement add and remove the way a queue would and it should ignore the weight argument. You can uncomment the breadthfs lines at the bottom of search.py to test your code.

Codes are below. Write it in python

CoordinatedMovement code Below:

import copy import itertools import math from State import State

def getSuccessors(state): actionList = state.actionList() return {state.doAction(act) for act in actionList}

dirs = { 'up':[0,-1], 'down':[0,1], 'left':[-1,0], 'right':[1,0] }

# Moves is the same set as dirs, except that it includes staying in place moves = copy.deepcopy(dirs) moves['stay'] = [0,0]

# Utility function which given a collection of collections # (lists or sets), makes the set of # tuples of all combinations of those items. # That is, allCombos([[1,2],[3,4]]) returns {(1,3),(2,3),(1,4),(2,4)} def allCombos(ll): if not ll: return {(),} head,*tail = ll output = set() for item in head: output = output.union({ (item,)+tc for tc in allCombos(tail) }) return output

class CoordinatedMovement(State): def __init__(self): super().__init__() self.blankboard = [list('xxxxxxx'), list('x x gx'), list('x gx'), list('x x gx'), list('xxxxxxx'),] self.board = copy.deepcopy(self.blankboard) self.ydim = len(self.blankboard) self.xdim = len(self.blankboard[0]) # Assumes board is rectangle self.numrobots = 3 self.robotpositions = {1:[1,1],2:[1,2],3:[1,3]} for robot in range(1,self.numrobots+1): rpos = self.robotpositions[robot] self.board[rpos[1]][rpos[0]] = str(robot)

self.goalpositions = [] for y in range(0,self.ydim): for x in range(0,self.xdim): if self.board[y][x] == 'g': self.goalpositions.append([x,y]) def __str__(self): output = "" for y in range(0,self.ydim): for x in range(0,self.xdim): output += self.board[y][x] output += (" ") return output def __eq__(self,other): if self.numrobots != other.numrobots: return False if self.robotpositions != other.robotpositions: return False return self.board == other.board def __ne__(self,other): return not self.__eq__(other) def __hash__(self): return hash(tuple(tuple(space for space in row) for row in self.board)) def get_actions(self): robotMoves = [] for robot in range(1,self.numrobots+1): robotMoves.append(['stay']) for direction,adjustments in dirs.items(): rpos = self.robotpositions[robot] space = self.board[rpos[1]+adjustments[1]][rpos[0]+adjustments[0]] if space == ' ' or space == 'g': robotMoves[robot-1].append(direction) possibleActions = allCombos(robotMoves)

def movesToSameSpace(robotmoves): robotFuturePositions = {(rpos[0]+moves[robotmoves[r-1]][0], rpos[1]+moves[robotmoves[r-1]][1]) for r,rpos in self.robotpositions.items() } return len(robotFuturePositions) < 3

return [a for a in possibleActions if not movesToSameSpace(a)] def apply_action(self,action): newstate = super().apply_action(action) newstate.robotpositions = copy.copy(self.robotpositions) newstate.board = copy.deepcopy(self.board) for robot in range(1,self.numrobots+1): rindex = robot-1 move = action[rindex] adj = moves[move] currentrpos = self.robotpositions[robot] futurerpos = [currentrpos[0]+adj[0],currentrpos[1]+adj[1]] newstate.robotpositions[robot] = futurerpos newstate.board[currentrpos[1]][currentrpos[0]] = self.blankboard[currentrpos[1]][currentrpos[0]] newstate.board[futurerpos[1]][futurerpos[0]] = str(robot) return newstate

def get_cost(self,action): total = 0 for act in action: if act != "stay": total += 1 return total

def is_goal(self): for robot in self.robotpositions: rpos = self.robotpositions[robot] if self.blankboard[rpos[1]][rpos[0]] != 'g': return False return True

def copy(self): copy = CoordinatedMovement() return copy

Search code Below:

from Structure import Structure from PriorityQueue import PriorityQueue from VacuumWorld import VacuumWorld from CoordinatedMovement import CoordinatedMovement

''' 1) Put start state into structure and seen list 2) Get state from structure if structure is empty return failure 3) Check if state is the goal state if so return that state as the answer 4) Get children of state 5) For each child: if not yet seen, add to seen list and structure 6) Go back to 2 ''' def search(structure,start_state,weight_f): seen = set() num_visited = 0 structure.add(start_state,weight_f(start_state)) seen.add(start_state) while not structure.is_empty(): num_visited += 1 current = structure.remove() if current.is_goal(): print("Search completed successfully.") print("Number of states visited: "+str(num_visited)) return current actions = current.get_actions() for action in actions: child = current.apply_action(action) if child not in seen: seen.add(child) structure.add(child,weight_f(child)) print("Search failed to find solution.") print("Number of states visited: "+str(num_visited)) return False

class Stack(Structure): def __init__(self): self.stack = [] def add(self,thing,weight): self.stack.append(thing) def remove(self): return self.stack.pop() def is_empty(self): return len(self.stack)==0

def dummy_weight(state): return 0

def cost_weight(state): return state.cost

def vw_huerisitic1(state): return 3*(state.floor.count("*"))

## Vacuum World Searches. Uncomment to run. vw1_start = VacuumWorld(1," * * ") #vw1_depthfs_answer = search(Stack(),vw1_start,dummy_weight) #vw1_depthfs_answer.print_history() #vw1_breadthfs_answer = search(Queue(),vw1_start,dummy_weight) #vw1_breadthfs_answer.print_history() #vw1_cfs_answer = search(PriorityQueue(),vw1_start,cost_weight) #vw1_cfs_answer.print_history() #vw1_bestfs_answer = search(PriorityQueue(),vw1_start,vw_huerisitic1) #vw1_bestfs_answer.print_history() #vw1_astar_answer = search(PriorityQueue(),vw1_start,vw_astar_weight) #vw1_astar_answer.print_history()

## Coordinated Movement Searches. Uncomment to run. cm1_start = CoordinatedMovement() #cm1_depthfs_answer = search(Stack(),cm1_start,dummy_weight) #cm1_depthfs_answer.print_history() #cm1_breadthfs_answer = search(Queue(),cm1_start,dummy_weight) #cm1_breadthfs_answer.print_history() #cm1_costfs_answer = search(PriorityQueue(),cm1_start,cost_weight) #cm1_costfs_answer.print_history() #cm1_bestfs_answer = search(PriorityQueue(),cm1_start,cm_huerisitic1) #cm1_bestfs_answer.print_history() #cm1_astar_answer = search(PriorityQueue(),cm1_start,cm_astar_weight) #cm1_astar_answer.print_history()

State Code Below:

class State: def __init__(self): self.cost = 0 self.parent = None self.parent_action = None def get_actions(self): return [] def get_cost(self,action): return 1 def apply_action(self,action): child = self.copy() child.cost = self.cost + self.get_cost(action) child.parent = self child.parent_action = action return child def is_goal(self): return False def __hash__(self): return 0 def __str__(self): return "the state" def copy(self): return State() def print_history(self): if self.parent is not None: self.parent.print_history() print(self.parent_action) print(self)

Structure Code Below:

class Structure: def add(self,thing,weight): return 0 def remove(self): return 0

VaccumWorld Code Below:

from State import State

class VacuumWorld(State): def __init__(self,pos,floor): super().__init__() self.pos = pos self.floor = floor def get_actions(self): actions = ['suck'] if self.pos != 0: actions.append('left') if self.pos != len(self.floor)-1: actions.append('right') return actions def get_cost(self,action): if action == 'suck': return 2 else: return 1 def apply_action(self,action): next = super().apply_action(action) if action == 'left': next.pos = next.pos - 1 elif action == 'right': next.pos = next.pos + 1 elif action == 'suck': next.floor = next.floor[0:next.pos]+' '+next.floor[next.pos+1:] return next def __str__(self): output = ' '*self.pos output += '^ ' output += self.floor return output def is_goal(self): return '*' not in self.floor def __hash__(self): return hash((self.pos,self.floor)) def __eq__(self,other): return self.pos == other.pos and self.floor == other.floor def __ne__(self,other): return not self.__eq__(other) def copy(self): copy = VacuumWorld(self.pos,self.floor) return copy