Q: Define two non-trivial admissible heuristics functions for the coffee shop domain. Your first heuristic, h1, should not take into account the locations of the coffee shops or the blocked squares. The second heuristic, h2, should take into account the locations of the coffee shops, but not locations of the blocked squares.

Hint: a useful concept is the Manhattan distance between two points (x1; y1) and (x2; y2) which is |x1 - x2|+ |y1 - y2| . The Python function abs finds the absolute value of a number. For each heuristic (as well as the trivial heuristic, h = 0), report on the number of paths expanded by A*search both with and without multiple-path pruning. Thus complete the following table:

A* without MPP A* with MPP

h = 0 279827 73

h1

h2

where the h = 0 entries are from the posted problem representation. You may have difrerent numbers.

This is my sketch in python with AIpython and I need more codes. Please provide me some codes I have to fill in to complete this question

# CMPT 380 Artificial Intelligence

from searchProblem import Search_problem, Arc

# a state is a triple ((x,y),c) where # robot is at position (x,y) where the bottom left location is (0,0) # Boolean c specified whether the robot has coffee

class CoffeeProblem(Search_problem): def start_node(self): """returns the start node""" return ((5,2),False) def is_goal(self,node): """returns True when node is a goal node""" return node == ((3,3),True) def neighbors(self,node): """returns a list of the neighbors of node. note that the neighbors are arcs. """ ((x,y),c) = node return [Arc(node,(pos,True)) if self.at_coffee(pos) else Arc(node,(pos,c)) for pos in ((x+dx,y+dy) for (dx,dy) in [(-1,0),(1,0),(0,1),(0,-1)]) if self.legal(pos)] def legal(self,pos): """returns True when pos is a legal position""" (x,y) = pos return x>=0 and x=0 and y

from searchGeneric import Searcher, AStarSearcher from searchMPP import SearcherMPP

# Try some of the following in iPython (or uncomment): print(" A* with MPP and h=0:") coffeesearchermpp = SearcherMPP(CoffeeProblem()) print(coffeesearchermpp.search()) print("A* without MPP with h=0 (warning slow):") coffeesearchera = AStarSearcher(CoffeeProblem()) print(coffeesearchera.search()) print(" A* with MPP and h=1:")

And this is the searchMPP.py

from searchGeneric import AStarSearcher, visualize from searchProblem import Path

class SearcherMPP(AStarSearcher): """returns a searcher for a problem. Paths can be found by repeatedly calling search(). """ def __init__(self, problem): super().__init__(problem) self.explored = set()

@visualize def search(self): """returns next path from an element of problem's start nodes to a goal node. Returns None if no path exists. """ while not self.empty_frontier(): path = self.frontier.pop() if path.end() not in self.explored: self.display(2, "Expanding:",path,"(cost:",path.cost,")") self.explored.add(path.end()) self.num_expanded += 1 if self.problem.is_goal(path.end()): self.display(1, self.num_expanded, "paths have been expanded and", len(self.frontier), "paths remain in the frontier") self.solution = path # store the solution found return path else: neighs = self.problem.neighbors(path.end()) self.display(3,"Neighbors are", neighs) for arc in neighs: self.add_to_frontier(Path(path,arc)) self.display(3,"Frontier:",self.frontier) self.display(1,"No (more) solutions. Total of", self.num_expanded,"paths expanded.")

from searchGeneric import test if __name__ == "__main__": test(SearcherMPP)

import searchProblem

And this is searchGeneric.py

from display import Displayable, visualize

class Searcher(Displayable): """returns a searcher for a problem. Paths can be found by repeatedly calling search(). This does depth-first search unless overridden """ def __init__(self, problem): """creates a searcher from a problem """ self.problem = problem self.initialize_frontier() self.num_expanded = 0 self.add_to_frontier(Path(problem.start_node())) super().__init__()

def initialize_frontier(self): self.frontier = [] def empty_frontier(self): return self.frontier == [] def add_to_frontier(self,path): self.frontier.append(path) @visualize def search(self): """returns (next) path from the problem's start node to a goal node. Returns None if no path exists. """ while not self.empty_frontier(): path = self.frontier.pop() self.display(2, "Expanding:",path,"(cost:",path.cost,")") self.num_expanded += 1 if self.problem.is_goal(path.end()): # solution found self.display(1, self.num_expanded, "paths have been expanded and", len(self.frontier), "paths remain in the frontier") self.solution = path # store the solution found return path else: neighs = self.problem.neighbors(path.end()) self.display(3,"Neighbors are", neighs) for arc in reversed(neighs): self.add_to_frontier(Path(path,arc)) self.display(3,"Frontier:",self.frontier) self.display(1,"No (more) solutions. Total of", self.num_expanded,"paths expanded.")

import heapq # part of the Python standard library from searchProblem import Path

class FrontierPQ(object): """A frontier consists of a priority queue (heap), frontierpq, of (value, index, path) triples, where * value is the value we want to minimize (e.g., path cost + h). * index is a unique index for each element * path is the path on the queue Note that the priority queue always returns the smallest element. """

def __init__(self): """constructs the frontier, initially an empty priority queue """ self.frontier_index = 0 # the number of items ever added to the frontier self.frontierpq = [] # the frontier priority queue

def empty(self): """is True if the priority queue is empty""" return self.frontierpq == []

def add(self, path, value): """add a path to the priority queue value is the value to be minimized""" self.frontier_index += 1 # get a new unique index heapq.heappush(self.frontierpq,(value, -self.frontier_index, path))

def pop(self): """returns and removes the path of the frontier with minimum value. """ (_,_,path) = heapq.heappop(self.frontierpq) return path

def count(self,val): """returns the number of elements of the frontier with value=val""" return sum(1 for e in self.frontierpq if e[0]==val)

def __repr__(self): """string representation of the frontier""" return str([(n,c,str(p)) for (n,c,p) in self.frontierpq]) def __len__(self): """length of the frontier""" return len(self.frontierpq)

def __iter__(self): """iterate through the paths in the frontier""" for (_,_,path) in self.frontierpq: yield path class AStarSearcher(Searcher): """returns a searcher for a problem. Paths can be found by repeatedly calling search(). """

def __init__(self, problem): super().__init__(problem)

def initialize_frontier(self): self.frontier = FrontierPQ()

def empty_frontier(self): return self.frontier.empty()

def add_to_frontier(self,path): """add path to the frontier with the appropriate cost""" value = path.cost+self.problem.heuristic(path.end()) self.frontier.add(path, value)

import searchProblem as searchProblem

def test(SearchClass): print("Testing problem 1:") schr1 = SearchClass(searchProblem.problem1) path1 = schr1.search() print("Path found:",path1) assert list(path1.nodes()) == ['g','d','c','b','a'], "Shortest path not found in problem1" print("Passed unit test")

if __name__ == "__main__": #test(Searcher) test(AStarSearcher) # example queries: # searcher1 = Searcher(searchProblem.acyclic_delivery_problem) # DFS # searcher1.search() # find first path # searcher1.search() # find next path # searcher2 = AStarSearcher(searchProblem.acyclic_delivery_problem) # A* # searcher2.search() # find first path # searcher2.search() # find next path # searcher3 = Searcher(searchProblem.cyclic_delivery_problem) # DFS # searcher3.search() # find first path with DFS. What do you expect to happen? # searcher4 = AStarSearcher(searchProblem.cyclic_delivery_problem) # A* # searcher4.search() # find first path

2 3 1 2 3 1