This Assignment has three parts, the second part and thired part are based on the answer of the first part. I post the module code at the top. This assignment need to be written by Python.

The search module:

from abc import ABCMeta, abstractmethod from collections import namedtuple def generic_search(graph, frontier): """Implements a generic graph search algorithm (see the lecture notes). The actual search behaviour depends on the type of the frontier object. """ for starting_node in graph.starting_nodes(): # Paths are tuples and the first arc on each path is a dummy # arc to a starting node frontier.add((Arc(None, starting_node, "no action", 0),)) for path in frontier: node_to_expand = path[-1].head # head of the last arc in the path if graph.is_goal(node_to_expand): yield path for arc in graph.outgoing_arcs(node_to_expand): frontier.add(path + (arc,)) # add back a new extended path class Arc(namedtuple('Arc', 'tail, head, label, cost')): """Represents an arc in a graph. Keyword arguments: tail -- the source node (state) head -- the destination node (state) label -- a string describing the action that must be taken in order to get from the source state to the destination state. cost -- a number that specifies the cost of the action """ class Graph(metaclass=ABCMeta): """This is an abstract class for graphs. It cannot be directly instantiated. You should define a subclass of this class (representing a particular problem) and implement the expected methods.""" @abstractmethod def is_goal(self, node): """Returns true if the given node is a goal state, false otherwise.""" @abstractmethod def starting_nodes(self): """Returns a sequence of starting nodes. Often there is only one starting node but even then the function returns a sequence with one element. It can be implemented as an iterator if needed. """ @abstractmethod def outgoing_arcs(self, tail_node): """Given a node it returns a sequence of arcs (Arc objects) which correspond to the actions that can be taken in that state (node).""" def estimated_cost_to_goal(self, node): """Return the estimated cost to a goal node from the given state. This function is usually implemented when there is a single goal state. The function is used as a heuristic in search. The implementation should make sure that the heuristic meets the required criteria for heuristics.""" raise NotImplementedError class ExplicitGraph(Graph): """This is a concrete subclass of Graph where vertices and edges are explicitly enumerated. Objects of this type are useful for testing graph algorithms.""" def __init__(self, nodes, edge_list, starting_list, goal_nodes, estimates=None): """Initialises an explicit graph. Keyword arguments: nodes -- a set of nodes edge_list -- a sequence of tuples in the form (tail, head) or (tail, head, cost) starting_list -- the list of starting nodes (states) goal_node -- the set of goal nodes (states) """ # A few assertions to detect possible errors in # instantiation. These assertions are not essential to the # class functionality. assert all(tail in nodes and head in nodes for tail, head, *_ in edge_list)\ , "An edge must link two existing nodes!" assert all(node in nodes for node in starting_list),\ "The starting_states must be in nodes." assert all(node in nodes for node in goal_nodes),\ "The goal states must be in nodes." self.nodes = nodes self.edge_list = edge_list self.starting_list = starting_list self.goal_nodes = goal_nodes self.estimates = estimates def starting_nodes(self): """Returns (via a generator) a sequence of starting nodes.""" for starting_node in self.starting_list: yield starting_node def is_goal(self, node): """Returns true if the given node is a goal node.""" return node in self.goal_nodes def outgoing_arcs(self, node): """Returns a sequence of Arc objects corresponding to all the edges in which the given node is the tail node. The label is automatically generated.""" for edge in self.edge_list: if len(edge) == 2: # if no cost is specified tail, head = edge cost = 1 # assume unit cost else: tail, head, cost = edge if tail == node: yield Arc(tail, head, str(tail) + '->' + str(head), cost) class Frontier(metaclass = ABCMeta): """This is an abstract class for frontier classes. It outlines the methods that must be implemented by a concrete subclass. Concrete subclasses determine the search strategy. """ @abstractmethod def add(self, path): """Adds a new path to the frontier. A path is a sequence (tuple) of Arc objects. You should override this method. """ @abstractmethod def __iter__(self): """Returns a generator. The generator selects and removes a path from the frontier and returns it. A path is a sequence (tuple) of Arc objects. Override this method according to the desired search strategy. """ def print_actions(path): """Given a path (a sequence of Arc objects), prints the actions (arc labels) that need to be taken and the total cost of those actions. The path is usually a solution (a path from the starting node to a goal node.""" if path: print("Actions:") print(", ".join(" {}".format(arc.label) for arc in path[1:]) + ".") print("Total cost:", sum(arc.cost for arc in path)) else: print("There is no solution!")

Part(a)

Writing the RoutingGraph class

In the first step of the assignment you have to write a subclass of Graph for a routing problem in an environment. The map of the environment is given in the form of a multi-line string of characters. The following shows an example map.

map_str = """\ +--------+ | G| | XXX | | S X | | X | +--------+ """ 

Map description

The map is always rectangular. We refer to positions in the map by a pair of numbers (row, col) which correspond to the row and column number of the position. Row numbers start from 0 for the first (topmost) line, 1 for the second line, and so on. The column numbers start from 0 for the first (leftmost) position (character) in the line, 1 for the second position, and so on.

The environment is always surrounded by walls which are represented with characters '+' or '-' or '|'. For example the position (0,0) is always a '+' (i.e. wall) and so are all other three corners of the map. The first and last rows and the first and last columns are always '-' and '|' respectively (except for the corners).

The obstacles are marked by 'X'.

There might be zero or more agents on the map. The location of agents are marked by 'S' or digits 0..9.

Agents indicated by S have solar panels and never require fueling. We can think of their fuel capacity to be infinity.

Agents indicated by digits have fuel tanks. The capacity of the tank is 9. The digit used to indicate the agent shows how much fuel is initially available in the tank.

The location of the destination is marked by a 'G'. To simplify textual representation, we assume that an agent is never initially at the destination. There is always one and only one destination on the map.

The agent can move in eight directions, N, NE, E, SE, S, SW, W, NW, unless there is an obstacle or wall in the way. This means that agents can also go to cells where other agents are present. The agent loses one unit fuel for each move. The order of actions is clockwise starting from N. For example, if from a position all eight directional moves are possible, then the first arc in the sequence of arcs returned by outgoing_arcs is for going north, then northeast, and so on until the last arc which goes to northwest. All the actions (moves) have the same cost which is 2 units of currency. This cost reflects various things such as distance, time, etc.

If an agent is in a cell marked as F and its current fuel amount is less than 9 it can take the action of "Fuel up" which fill the tank to its maximum capacity of 9. The "Fuel up" action (if available) should be given after any possible directional actions. The action costs 5 units of currency (regardless of how much fuel is obtained).

Task

Write a class RoutingGraph which is initialised by the map string and represents the map in the form of a graph by implementing all the required methods in the Graph class including the method estimated_cost_to_goal. Represent the state of the agent by a tuple of the form (row, column, fuel)

Notes

Note the distinction between fuel and cost.

It is recommended that you write your class as a subclass of Graph.

The test cases do not test the method estimated_cost_to_goal in this question.

Try to avoid using indices to refer to elements of a tuple. For example instead of using position[0] and position[1], use readable names. For example use row, col = position instead.

You may find math.inf useful.

If you copy a multi-line string from the examples given in the questions into a function in your code, some leading spaces will be introduced. Use the method strip to get rid of these leading/trailing spaces. Also be mindful of the difference between the following two strings:

str1 = """This string has one line. """ def mina(): str2 = """This string has TWO lines. """ 

It is recommended (but not required) that your answer for RoutingGraph is shorter than 70 lines of code. If your code is much longer, you might be doing something wrong.

Avoid repetitive code. If you wish you can use the following list when implementing outgoing_arcs. You have to decipher it yourself.

[('N' , -1, 0), ('NE', -1, 1), ('E' , 0, 1), ('SE', 1, 1), ('S' , 1, 0), ('SW', 1, -1), ('W' , 0, -1), ('NW', -1, -1)]

Test for part(a):

Test	Result
from student_answer import RoutingGraph map_str = """\ +-------+ | 9 XG| |X XXX | | S 0F | +-------+ """ graph = RoutingGraph(map_str) print("Starting nodes:", sorted(graph.starting_nodes())) print("Outgoing arcs (available actions) at starting states:") for s in sorted(graph.starting_nodes()): print(s) for arc in graph.outgoing_arcs(s): print (" " + str(arc)) node = (1,1,5) print(" Is {} goal?".format(node), graph.is_goal(node)) print("Outgoing arcs (available actions) at {}:".format(node)) for arc in graph.outgoing_arcs(node): print (" " + str(arc)) node = (1,7,2) print(" Is {} goal?".format(node), graph.is_goal(node)) print("Outgoing arcs (available actions) at {}:".format(node)) for arc in graph.outgoing_arcs(node): print (" " + str(arc)) node = (3,6,5) print(" Is {} goal?".format(node), graph.is_goal(node)) print("Outgoing arcs (available actions) at {}:".format(node)) for arc in graph.outgoing_arcs(node): print (" " + str(arc)) node = (3,6,9) print(" Is {} goal?".format(node), graph.is_goal(node)) print("Outgoing arcs (available actions) at {}:".format(node)) for arc in graph.outgoing_arcs(node): print (" " + str(arc))	Starting nodes: [(1, 3, 9), (3, 2, inf), (3, 5, 0)] Outgoing arcs (available actions) at starting states: (1, 3, 9) Arc(tail=(1, 3, 9), head=(1, 4, 8), label='E', cost=2) Arc(tail=(1, 3, 9), head=(2, 2, 8), label='SW', cost=2) Arc(tail=(1, 3, 9), head=(1, 2, 8), label='W', cost=2) (3, 2, inf) Arc(tail=(3, 2, inf), head=(2, 2, inf), label='N', cost=2) Arc(tail=(3, 2, inf), head=(3, 3, inf), label='E', cost=2) Arc(tail=(3, 2, inf), head=(3, 1, inf), label='W', cost=2) (3, 5, 0) Is (1, 1, 5) goal? False Outgoing arcs (available actions) at (1, 1, 5): Arc(tail=(1, 1, 5), head=(1, 2, 4), label='E', cost=2) Arc(tail=(1, 1, 5), head=(2, 2, 4), label='SE', cost=2) Is (1, 7, 2) goal? True Outgoing arcs (available actions) at (1, 7, 2): Arc(tail=(1, 7, 2), head=(2, 7, 1), label='S', cost=2) Arc(tail=(1, 7, 2), head=(2, 6, 1), label='SW', cost=2) Is (3, 6, 5) goal? False Outgoing arcs (available actions) at (3, 6, 5): Arc(tail=(3, 6, 5), head=(2, 6, 4), label='N', cost=2) Arc(tail=(3, 6, 5), head=(2, 7, 4), label='NE', cost=2) Arc(tail=(3, 6, 5), head=(3, 7, 4), label='E', cost=2) Arc(tail=(3, 6, 5), head=(3, 5, 4), label='W', cost=2) Arc(tail=(3, 6, 5), head=(3, 6, 9), label='Fuel up', cost=5) Is (3, 6, 9) goal? False Outgoing arcs (available actions) at (3, 6, 9): Arc(tail=(3, 6, 9), head=(2, 6, 8), label='N', cost=2) Arc(tail=(3, 6, 9), head=(2, 7, 8), label='NE', cost=2) Arc(tail=(3, 6, 9), head=(3, 7, 8), label='E', cost=2) Arc(tail=(3, 6, 9), head=(3, 5, 8), label='W', cost=2)
from student_answer import RoutingGraph map_str = """\ +--+ |GS| +--+ """ graph = RoutingGraph(map_str) print("Starting nodes:", sorted(graph.starting_nodes())) print("Outgoing arcs (available actions) at the start:") for start in graph.starting_nodes(): for arc in graph.outgoing_arcs(start): print (" " + str(arc)) node = (1,1,1) print(" Is {} goal?".format(node), graph.is_goal(node)) print("Outgoing arcs (available actions) at {}:".format(node)) for arc in graph.outgoing_arcs(node): print (" " + str(arc))	Starting nodes: [(1, 2, inf)] Outgoing arcs (available actions) at the start: Arc(tail=(1, 2, inf), head=(1, 1, inf), label='W', cost=2) Is (1, 1, 1) goal? True Outgoing arcs (available actions) at (1, 1, 1): Arc(tail=(1, 1, 1), head=(1, 2, 0), label='E', cost=2)
from student_answer import RoutingGraph map_str = """\ +------+ |S S| | GXXX| |S | +------+ """ graph = RoutingGraph(map_str) print("Starting nodes:", sorted(graph.starting_nodes()))	Starting nodes: [(1, 1, inf), (1, 6, inf), (3, 1, inf)]

Part(b)

Writing the AStarFrontier class

Write a class AStarFrontier for performing A* search on graphs. An instance of AStarFrontier together with an instance of RoutingGraph that you wrote in the previous question will be passed to the generic search procedure in order to find the lowest cost solution (if one exists) from one of the agents to the goal node.

In this question, the heuristic value returned by a graph object for any node (state) must be zero.

Notes:

Your solution must contain the definitions of both AStarFrontier and RoutingGraph classes.

Unlike other frontier objects, the AStarFrontier objects are initialised with an instance of a graph. This is because AStarFrontier needs to access the estimated_cost_to_goal method of the graph object.

Remember that in this course priority queues must be stable.

The algorithm must halt on all valid maps even when there is no solution.

It is recommended that before you submit your solution, you test it against the given test cases and some new examples (maps) designed by yourself with different positioning of agents and building blocks. It is up to you to decide whether or not the frontier should perform pruning.

Note the distinction between the cost and fuel consumption. We are interested in a solution with the lowest cost.

The requirement of having a zero heuristic implies that the generic graph search algorithm will behave as an LCFS (lowest-cost-first search). In the next question, we will more thoroughly test your A* frontier and graph class.

When there is no solution, the generic graph search automatically returns None instead of a path which causes the print_actions procedure to print "There is no solution." This happens when the frontier becomes empty and no solution has been reached.

It is recommended (but not required) that your answer for AStarFrontier is shorter than 30 lines of code. If your code is much longer, you might be doing something wrong.

part(b) test:

Test	Result
from student_answer import RoutingGraph, AStarFrontier from search import * map_str = """\ +-------+ | G | | | | S | +-------+ """ map_graph = RoutingGraph(map_str) frontier = AStarFrontier(map_graph) solution = next(generic_search(map_graph, frontier), None) print_actions(solution)	Actions: N, N. Total cost: 4
from student_answer import RoutingGraph, AStarFrontier from search import * map_str = """\ +-------+ | XG| |X XXX | | S | +-------+ """ map_graph = RoutingGraph(map_str) frontier = AStarFrontier(map_graph) solution = next(generic_search(map_graph, frontier), None) print_actions(solution)	Actions: E, E, E, NE, NE. Total cost: 10
from student_answer import RoutingGraph, AStarFrontier from search import * map_str = """\ +-------+ | F XG| |X XXXX | | 2 | +-------+ """ map_graph = RoutingGraph(map_str) frontier = AStarFrontier(map_graph) solution = next(generic_search(map_graph, frontier), None) print_actions(solution)	Actions: N, NE, Fuel up, SW, SE, E, E, E, NE, N. Total cost: 23
from student_answer import RoutingGraph, AStarFrontier from search import * map_str = """\ +--+ |GS| +--+ """ map_graph = RoutingGraph(map_str) frontier = AStarFrontier(map_graph) solution = next(generic_search(map_graph, frontier), None) print_actions(solution)	Actions: W. Total cost: 2
from student_answer import RoutingGraph, AStarFrontier from search import * map_str = """\ +---+ |GF2| +---+ """ map_graph = RoutingGraph(map_str) frontier = AStarFrontier(map_graph) solution = next(generic_search(map_graph, frontier), None) print_actions(solution)	Actions: W, W. Total cost: 4
from student_answer import RoutingGraph, AStarFrontier from search import * map_str = """\ +----+ | S | | SX | | X G| +----+ """ map_graph = RoutingGraph(map_str) frontier = AStarFrontier(map_graph) solution = next(generic_search(map_graph, frontier), None) print_actions(solution)	Actions: SE, E. Total cost: 4
from student_answer import RoutingGraph, AStarFrontier from search import * map_str = """\ +---------+ | | | G | | | +---------+ """ map_graph = RoutingGraph(map_str) frontier = AStarFrontier(map_graph) solution = next(generic_search(map_graph, frontier), None) print_actions(solution)	There is no solution!

Part(c):

The print_map procedure

Write a procedure print_map that takes three parameters: an instance of RoutingGraph, a frontier object, and a solution (which is a sequence of Arc objects that make up a path from a starting position to the goal position) and then prints a map such that:

the position of the walls, obstacles, agents, and the goal point are all unchanged and they are marked by the same set of characters as in the original map string; and

those free spaces (space characters) that have been expanded during the search are marked with a '.' (a period character); and

those free spaces (spaces characters) that are part of the solution (best path to the goal) are marked with '*' (an asterisk character).

Further assumptions and requirements

For this question, the graph class must have a proper heuristic function named estimated_cost_to_goal. You have to design the most dominant (highest value) function that can be computed in constant time. See the signature of the method in the Graph class in search.py.

In this question, we are only concerned with agents of type Sagents that have infinite amount of fuel and do not require to fuel up. The test cases do not include any fuel-based agents or fuel stations. Do not consider anything fuel-related when devising the heuristic function.

Only the first solution returned by the generic search procedure (if there is one) is used to test your procedure.

In addition to print_map, your solution must include the code for RoutingGraph and AStarFrontier.

Notes

A node is said to have been expanded if a path leading to that node is removed from the frontier and then if the node has neighbours, corresponding extended paths are added to the frontier.

This question puts your code for the graph and A* frontier into real test. Previous questions did not test the heuristic function and as long as the frontier class could provide the functionality of the LCFS, it would pass the test cases. In this question, however, your code needs to produce the correct A* behaviour. Therefore, even if your code has passed previous tests, you may still need to modify it in order to meet the required spec in this question.

Note that you only need to consider movement actions when designing the heuristic function and that all movement actions have the same cost of 2.

If your algorithm expands more nodes than the expected output, you might be using a heuristic that is not good enough; you need to find a better heuristic. Refer to the specification of the heuristic function stated above.

If for any reason you decide to answer this question before Question 2, please remember that in Question 2 the heuristic function is required to always return zero.

The generic graph search algorithm returns None when no solution if found.

It is recommended (but not required) that your answer for print_map is shorter than 20 lines of code. If your code is much longer, you might be doing something wrong.

Part(c) test:

Test	Result
from student_answer import RoutingGraph, AStarFrontier, print_map from search import * map_str = """\ +-------+ | XG| |X XXX | | S | +-------+ """ map_graph = RoutingGraph(map_str) frontier = AStarFrontier(map_graph) solution = next(generic_search(map_graph, frontier), None) print_map(map_graph, frontier, solution)	+-------+ | XG| |X XXX* | | S*** | +-------+
from student_answer import RoutingGraph, AStarFrontier, print_map from search import * map_str = """\ +--+ |GS| +--+ """ map_graph = RoutingGraph(map_str) frontier = AStarFrontier(map_graph) solution = next(generic_search(map_graph, frontier), None) print_map(map_graph, frontier, solution)	+--+ |GS| +--+
from student_answer import RoutingGraph, AStarFrontier, print_map from search import * map_str = """\ +----+ | | | SX | | X G| +----+ """ map_graph = RoutingGraph(map_str) frontier = AStarFrontier(map_graph) solution = next(generic_search(map_graph, frontier), None) print_map(map_graph, frontier, solution)	+----+ | | | SX | | X*G| +----+
from student_answer import RoutingGraph, AStarFrontier, print_map from search import * map_str = """\ +------------+ | | | | | | | S | | | | | | G | | | +------------+ """ map_graph = RoutingGraph(map_str) frontier = AStarFrontier(map_graph) solution = next(generic_search(map_graph, frontier), None) print_map(map_graph, frontier, solution)	+------------+ | | | | | | | S | | * | | * | | G | | | +------------+
from student_answer import RoutingGraph, AStarFrontier, print_map from search import * map_str = """\ +------------+ | | | | | | | S | | | | | | G | | | +------------+ """ map_graph = RoutingGraph(map_str) # changing the heuristic so the search behaves like LCFS map_graph.estimated_cost_to_goal = lambda node: 0 frontier = AStarFrontier(map_graph) solution = next(generic_search(map_graph, frontier), None) print_map(map_graph, frontier, solution)	+------------+ | ...... | | ...... | | ...... | | ..S... | | .*.... | | *..... | | G...... | | | +------------+
from student_answer import RoutingGraph, AStarFrontier, print_map from search import * map_str = """\ +---------------+ | G | |XXXXXXXXXXXX | | X | | XXXXXX X | | X S X X | | X X | | XXXXXXXXXX | | | +---------------+ """ map_graph = RoutingGraph(map_str) frontier = AStarFrontier(map_graph) solution = next(generic_search(map_graph, frontier), None) print_map(map_graph, frontier, solution)	+---------------+ | G******* | |XXXXXXXXXXXX* | |..******...X*. | |.*XXXXXX*..X*..| |.*X.S**X*..X*..| |.*X....*...X*..| |.*XXXXXXXXXX*..| |..**********...| +---------------+
from student_answer import RoutingGraph, AStarFrontier, print_map from search import * map_str = """\ +---------+ | | | G | | | +---------+ """ map_graph = RoutingGraph(map_str) frontier = AStarFrontier(map_graph) solution = next(generic_search(map_graph, frontier), None) print_map(map_graph, frontier, solution)	+---------+ | | | G | | | +---------+
from student_answer import RoutingGraph, AStarFrontier, print_map from search import * map_str = """\ +-------------+ | G | | S | | S | +-------------+ """ map_graph = RoutingGraph(map_str) frontier = AStarFrontier(map_graph) solution = next(generic_search(map_graph, frontier), None) print_map(map_graph, frontier, solution)	+-------------+ | G | | S .*. | | S | +-------------+

lecture note:

https://drive.google.com/open?id=1Dnq40CiiTwORYOIIxBI3CE0ejHDxlNoJ