Lab 2 2014

From 6.034 Wiki

Revision as of 01:21, 29 September 2008

This problem set will be due on Friday, October 3rd.

To work on this problem set, you will need to get the code, much like you did for the first two problem sets.

• You can view it at: http://web.mit.edu/6.034/www/labs/lab2/
• Download it as a ZIP file: http://web.mit.edu/6.034/www/labs/lab2/lab2.zip
• Or, on Athena, add 6.034 and copy it from /mit/6.034/www/labs/lab2/.

Your answers for the problem set belong in the main file lab2.py.

Search

Explanation

This section is an explanation of the system you'll be working with. There aren't any problems to solve. Read it carefully anyway.

We've learned a lot about different types of search in lecture the last several weeks. This problem set will involve implementing several search techniques. For each type of search you are asked to write, you will get a graph (consisting of a list of nodes and a list of edges), a start node, and a goal node.

A graph is a dictionary that contains the keys 'NODES' and 'EDGES'. The 'NODES' entry contains a list of nodes; the 'EDGES' entry contains a list of edges.

Each node consists of a description, called NAME, and a HEURISTIC value that guesses its distance to a goal node. In most places, you will represent the node using simply the node's name.

Each edge expression contains a NAME, a LENGTH, and two endpoints (specified as node names, NODE1 and NODE2).

An example of a graph representation looks like this:

{ 'NODES':
  [ { 'NAME': 'Forbidden 3rd Floor Corridor', 'HEURISTIC': 10 },
    { 'NAME': 'Common Room', 'HEURISTIC': 15 },
    { 'NAME': 'Kitchens', 'HEURISTIC': 20 } ],
  'EDGES':
  [ { 'NAME': 'e1', 'LENGTH': 10, 'NODE1': 'Forbidden 3rd Floor Corridor', 'NODE2': 'Common Room' },
    { 'NAME': 'e2', 'LENGTH': 4, 'NODE1': 'Common Room', 'NODE2': 'Kitchens' } ] }

In this graph representation, there are three nodes (Forbidden 3rd Floor Corridor, Common Room, and Kitchens), followed by their respective heuristic values. There are two edges in this graph. One edge connects the Forbidden 3rd Floor Corridor with the Common Room, and the other connects the Common Room with the Kitchens.

The representation for an entire graph, described above, is mainly used in the tester. Your search procedures will receive the nodes and edges as separate parameters. You can access the data within the node and edge expressions by using the procedures defined in search.py.

Helper functions

These functions will help you work with the graph representation:

• get_connected_nodes(node, edges): Given a node name and a list of edges, return a list of all nodes that are connected to the specified node by an edge.
• get_edge(node1, node2, edges): Given two node names and a list of all edges in a graph, return the edge that connects those nodes, or None if there is no such edge.
• get_node(node_name, nodes): Given a node name and a list of nodes, return the node (the node dictionary) with this name in the list; or, return None if there is no such node.
• are_connected(node1, node2, edges): Return True iff there is an edge running directly between node1 and node2; False otherwise
• is_valid_path(path, graph): Given 'path' as an ordered list of node names and 'graph' as a graph dictionary, return True iff there is an edge between every two adjacent nodes in the list, False otherwise
• get_heuristic(nodename, nodes): Given the name of a node and the set of nodes in the graph, return the node's heuristic value

In addition, you're expected to know how to access elements in lists and dictionaries at this point. Recall that you can get at dictionary elements via myDict['KEY']. Also, for some portions of this lab, you may want to use lists like either stacks or queues, as documented at <http://docs.python.org/tut/node7.html>.

You also may need to sort Python lists. Python has built-in sorting functionality, documented at <http://wiki.python.org/moin/HowTo/Sorting>. If you read that document, recall that Solaris-Athena computers (the purple Athena computers, not the black ones) still have an older version of Python prior to v2.4 installed.

The Queue

Different search techniques utilize the queue differently. Some add paths to the beginning of the queue while others add paths to the end of the queue. Some queues are organized by heuristic value while others are ordered by path distance. Your job will be to show your knowledge of search techniques by implementing different types of search and making slight modifications to how the queue is accessed and updated.

Note: When you add multiple paths to the queue (that is, when you extend a node), you should add them in the same order as the nodes are listed in the NODES list for the graph..

Extending a path in the queue

In this problem set, a path consists of a list of node id values. When it comes time to extend a new path, a path is selected from the queue. The last node in the path is identified as the node to be extended. All nodes that connect to the extended node are identified as well. These are the possible extensions to the path. Of the possible extensions, the following nodes are NOT added:

• nodes that already appear in the path.
• nodes that have already been extended (if an extended list is being used.)

As an example, if node A is connected to nodes S, B, and C, then the path ['S', 'A'] is extended to the new paths ['S', 'A', 'B'] and ['S', 'A', 'C'].

The paths you create should be new objects. If you try to extend a path by modifying (or "mutating") the existing path, such as using append, you will probably find yourself in a world of hurt.

The Extended List

The extended list is often used to speed up searches. You will be implementing types of search that use extended lists. Remember that an extended list prevents you from extending a node more than one time. So if you're using an extended list, a maximum of one of each node name should appear in the extended list.

Returning a Search Result

A search result should consist of a list of node names, ordered from the start node to the final node that your search algorithm turned up.

Multiple choice

This section contains the first graded questions for the problem set. The questions are located in lab2.py and let you check your knowledge of different types of search. You should, of course, try to answer them before checking the answers in the tester.

Basic Search

The first two types of search to implement are breadth-first search and depth-first search. When necessary, use backtracking for the search.

Breadth-first Search and Depth-first Search

Your task is to implement the following functions:

def bfs(graph, start, goal):

def dfs(graph, start, goal):

The input to the functions are:

• graph: The graph, represented as a dictionary with 'NODES' and 'EDGES' keys
• start: The name of the node that you want to start traversing from
• end: The name of the node that you want to reach

When a path to the goal node has been found, return the result as explained in the section Returning a Search Result (above).

Hill Climbing

Hill climbing is very similar to depth first search. There is only a slight modification to the ordering of paths that are added to the queue. For this part, implement the following function:

def hill_climbing(graph, start, goal):

The hill-climbing procedure you define here should use backtracking, for consistency with the other methods, even though hill-climbing typically is not implemented with backtracking.

Optimal Search

The search techniques you have implemented so far have not taken into account the edge distances. Instead we were just trying to find one possible solution of many. This part of the problem set involves finding the path with the shortest distance from the start node to the goal node. The search types that guarantee optimal solutions are branch and bound and A*.

Since this type of problem requires knowledge of the length of a path, implement the following function that computes the length of a path:

def path_length(node_names, edges):

The function takes in a list of node names that make up a path and the edges in a graph and computes the length of a path. You can assume the path is valid (there are edges between each node in the graph), so you do not need to test to make sure there is actually an edge between consecutive nodes in the path. If there is only one node in the path, your function should return 0.

Branch and Bound

Now that you have a way to measure path distance, this part should be easy to complete. You might find the list procedure remove, and/or the Python 'del' keyword, useful. For this part, complete the following:

def branch_and_bound(graph, start, goal):

A*

You're almost there! You've used heuristic estimates to speed up search and edge lengths to compute optimal paths. Let's combine the two ideas now to get the A* search method. In A*, the path with the least (heuristic estimate + path length) is taken from the queue to extend. A* always uses an extended list; if extended is set to None, set it to a list and use it.

def a_star(graph, start, goal):

Graph Heuristics

A heuristic value gives an approximation from a node to a goal. You've learned that in order for the heuristic to be admissible, the heuristic value for every node in a graph must be less than the distance of the shortest path from the goal to that node. In order for a heuristic to be consistent, for each edge in the graph, the edge length must be greater than or equal to the absolute value of the difference between the two heuristic values of its nodes.

In lecture and tutorials, you've seen examples of graphs that have admissible heuristics that were not consistent. Have you seen graphs with consistent heuristics that were not admissible? Why is this so? (This should give you an idea of how to program this problem.) For this part, complete the following function, which returns:

• True if a graph has heuristics that are admissible and consistent
• False otherwise

Note: You can assume for this problem that the heuristic value of the goal node is 0. Is your solution guaranteed to be correct if it is not?

def is_admissible_and_consistent(graph):

Survey

Please answer these questions at the bottom of your lab2.py file:

• How many hours did this problem set take?
• Which parts of this problem set, if any, did you find interesting?
• Which parts of this problem set, if any, did you find boring or tedious?

(We'd ask which parts you find confusing, but if you're confused you should really ask a TA.)

Checking your submission

When you're finished with your lab, don't forget to submit your code and run the online unit tests!

Questions?

If you find what you think is an error in the problem set, tell 6.034-tas@mit.edu about it.