[SOLVED] CS6601 - Assignment 1 Spring 2026

Assignment Instructions

Assignment Description

The goals of this assignment are as follows:

1. Verify student understanding of foundational Search algorithms taught in lecture. (BFS, UCS, A*)
2. Explore improved search algorithms built upon the foundational Search algorithms. (Bi/Tri-UCS, Bi/Tri-A*)

Your task is to implement several search algorithms that will calculate a route between two points in Romania while seeking to optimize time and space cost. We will be using an undirected network representing a map of Romania.

Assignment Setup

Before beginning this assignment, please ensure that you have completed all prerequisite installation and setup instructions provided in the assignment README file. Please also make sure that you are running this notebook from within a Conda environment.

You will notice that every file to submitted contains several lines of code like that shown below.

# Credits if any
# 1)
# 2)
# 3)

This is for you to identify any external non-preapproved resources that you referenced during your work. Unless otherwise specified, you MUST consult the teaching staff for approval BEFORE referencing a non-preapproved resource. Failure to do so may result in an OSI violation.

If you have discussed this assignment at a whiteboard level with other students that you may want to cite, please also do so so that we are aware in case your algorithm design is uncannily similar to another student’s.

Assignment Contents

This assignment is the first out of six assignments in this course and is scored out of 100 pts. The contents in this notebook are as follows:

Grading

You will edit and then submit the files in the submission folder to Gradescope. Local tests and visualizers are runnable in this notebook, although you are encouraged to take a look at how they work and try out some of your own.

Points for each section are awarded based on finding the most optimal path (for that search algorithm) and then evaluating the number of nodes explored. To track the number of times a node is explored during the search every time you process a node, by calling graph.neighbors(node) on the ExplorableGraph, the count for that node increases by one. You will need to use one of these methods to add a node’s neighbors to the search queue, just be careful not to call it unnecessarily throughout your code. We have created the graph.get_edge_weight(u, v) method to be used to access edge weights between two nodes, u and v. Exercise specific details can be found in the exercise descriptions below.

Frequently Asked Questions

General

1. Do NOT create a copy of the graph structure for any of the algorithms or computations. We refer to this as “caching neighbors” and it is illegal.
2. A walkthrough video will be released with the assignment release on Edstem. It is highly recommended that you watch the video for guidance on how to get started on the project as well as tips for individual exercises.
3. This is a difficult assignment! Get started early, use office hours, and don’t give up!

Error Messages (Gradescope and Local)

1. NoneType object is not subscriptable – This usually occurs when you return a path that is not completely connected (a pair of successive nodes in your path are not connected) or if your path returned is empty when it is not supposed to be empty.
2. Path does not go from start to goal or is invalid – (Gradescope) The path returned by your algorithm does not have the start and end goals at their respective positions; does not have the correct start and end goals; is not the shortest path to the goal; or is not a complete/connected path.
3. Path is longer than optimal path – (Gradescope) Your path cost is greater than the expected optimal path cost/benchmark.
4. Nodes explored should be from a valid frontier and should be kept to a minimum – (Gradescope) Your algorithm is exploring more nodes than necessary or is exploring nodes that should not be explored in that particular test. This is independent of whether or not your path is correct.
5. On average for the failed test case(s), excluding cases where path is longer than optimal: number of nodes explored more than the benchmark = xyz – (Gradescope) The average number of nodes explored in excess by your algorithm (includes only cases where path was optimal)
6. Path cost is incorrect – (Gradescope) The cost of your path is incorrect.
7. List index was out of range – (Gradescope) This is likely due to the fact that your code may not be generalized properly. While we provide the Romania map for local testing, the map on Gradescope is not identical and node labels may not be one character strings. (i.e. multicharacter strings, integers, floats, etc.) Make sure your code is generalized!
8. We check for illegal imports on Gradescope submission, so make sure your code editor did not add any additional package imports on top of what was provided. The sole exception is the typing Python library, which we now allow based on popular demand. However usage of the library is untested and could break GS, use it at your own risk.

Grading

1. The grade you see in Gradecope is the grade that you will get, unless an OSI violation is detected. In the event that an OSI violation is detected, you will be notified at some point after the assignment closure for administrative steps. So please, check with teaching staff before you do anything that might result in an OSI violation.
2. Are in-person and OMSCS folk graded together? No. They are two separate sections.
3. Gradescope automatically marks your most recent submission as the one for grading. Make sure you activate your best submission for grading before the final deadline.
4. The autograder is set to timeout in 10 minutes, so if your submissions runs for longer than 10 minutes it will be terminated and not graded. Note that in some cases, this will fail to occur due to infinite loops or memory overflow, in which case you will have crased the autograder and should reach on Edstem to see if the teaching staff can manually terminate the autograder for you.
5. You are allowed a maximum of 2 submissions within a rolling 30 minute window. Please use your submissions wisely.

Setup Verification

First, let’s make sure you have installed the correct versions of all of the libraries. To install all the libraries, make sure you built the conda environment using conda env create -f a1_yml.yaml or ran pip install -r requirements.txt in your Conda environment.

Simply run the cell below. You can click on the cell and press ⇧↩ (Shift + Enter) to run it. If you see any warning/error messages, please make sure you have followed the installation instructions in the README. In case you can’t resolve them please check out Edstem thread dedicated to “Assignment 1”.

Name [1pt]

A simple task to begin the assignment. Fill out the function return_your_name() in submission/bfs.py. You should see your name printed when you run the cell below.

Warmup 0 – Priority Queue (Optional)

You may use our provided Priority Queue or implement your own Priority Queue from scratch (the provided Priority Queue does not implement the remove function, which some students may find useful for their own work). If you choose to use our provided Priority Queue, you can submit submission/priority_queue.py to Gradescope unchanged. Regardless, please make sure you submit submission/priority_queue.py to Gradescope for the autograder to execute.

We provide some tests to check basic functionality of your priority queue in the cells below, and there are also unweighted Gradescope tests that check if your Priority Queue satisfies the necessary requirements. Note that the tests are identical to those encounted in Assignment 0.

A common data structure used in search algorithms is the Priority Queue, often used to identify which path to investigate next, prioritizing shorter paths in hopes of finding the shortest path from a source to a destination. In this exercise, we ask you to implement a Priority Queue that takes on elements in the form of a tuple: (priority, payload), where elements with a higher priority (in our case a smaller value) should be removed first, and if two elements have the same priority, the element that joined the queue earlier should be removed first (FIFO ordering). The file for you to edit and submit to Gradescope is submission/priority_queue.py.

A common implementation of a Priority Queue is via a Binary Heap. Binary heaps are a popular option because they provide amortized  insertion and  removal time. To pass our tests, your Priority Queue must perform better than the naive implementation in our tests (InsertionSortQueue), which sorts the entire list after every insertion. We recommend looking at the Python documentation for their heapq module for inspiration if you are stuck, although please do your best to try to figure it out on your own.

Do NOT add or remove any imports to priority_queue.py! If you find some imports helpful while you are working on the file, please make sure to remove them before submitting to Gradescope. Some local tests have been provided for you below, note that they are not comprehensive and you are encouraged to add your own!

FAQ

1. Can I use special Python libraries? No. You may not use libraries like heapq for your implementation, it is expected that students be able to implement the Priority Queue from scratch. Only the libraries provided in this assignment are allowed.
2. Implement the functions pop and append in the PriorityQueue class at a minimum. You can add extra helper functions within the class if you’d like and you may also implement remove if you find that necessary.
3. Preserve FIFO. It is possible for the priority queue to receive two elements with the same priority. In the event that that occurs, the element that joined the priority queue first should be returned first. The best hint we can give you is to think about using some sort of a counter to keep track of when each node joined the Priority Queue…
4. Generalize. The nodes provided to the priority queue will be Python tuples in the form of (priority, payload). You may assume that the datatype for priority is a standard Python datatype (i.e. int, float, str, etc.). The payload can be of any datatype (standard or custom).
5. It is possible for duplicate nodes to enter the queue. (i.e. identical priority, identical payload)

Recommended (Approved) Resources

• heapq module

Warmup 1 – Breadth-First Search [6pts]

To get you started with handling graphs, implement breadth-first search over the test network by completing the breadth_first_search() method in submission/bfs.py. The function should return a path of nodes from a given start node to a given end node, as a list.

Requirements

1. Implement the breadth_first_search() method in submission/bfs.py.
2. If the start and goal are the same, simply return an empty list like [].
3. Return the best path found via BFS as a Python list from the start node to the goal node (inclusive).
4. You can obtain a dictionary of the neighbors of a node by calling graph.neighbors(node).
5. Sort the neighbors of a node alphabetically before adding them to the queue.
6. Make sure no node is explored more than once.
7. Implement the optimization trick which reduces the number of explored nodes (required for passing the autograder). You may find it useful to re-watch the Canvas videos for this.

FAQ

1. Are there multiple correct paths possible? No. If you follow the above instructions, each pair of start and goal nodes will result in a unique solution.
2. Do I need Priority Queue for this? No. BFS does not need to use a priority queue, a simple FIFO queue using a Python list is sufficient. As such, we do not allow you to import priority queue for this task.
3. Why does it say I don’t have the right path when my true path cost is shorter? Remember, BFS treats all edges as having a cost of 1, so the true path cost does not come into play!!
4. I am having trouble reconstructing my optimal path. What should I do? You can either try to keep track of where you came from and reconstruct the path by chaining parent information, or you can store entire paths in your frontier so that when you find the goal node you can just return the path found without having to do reconstruction.
5. Why does it say my path is invalid? Did you return the path as a list of nodes including both the start and the goal node? Did you make sure that the path is a valid path and doesn’t skip around? (Traverse the graph by hand to make sure it is valid)
6. Why does it say I’m exploring too many nodes? Did you implement the optimization trick mentioned above? If so, are you making sure that you are not exploring any node more than once? You can check the set of nodes you’ve explored and how many times they’ve been explored by calling graph.explored_nodes. However please make sure that you remove this call from your code after you are done debugging as it will cause Gradescope to fail. If you wish to call it repeatedly during your local testing, make sure you call graph.reset_search() to reset the explored count.
7. I’m consistently exploring one too many nodes! Perhaps you are exploring the goal node when you don’t actually need to…

Recommended (Approved) Resources

• Canvas Search Modules
• Course AIMA Textbook 4th Edition, Section 3.4.1
• R&N Slides on Uninformed Search
• Interactive BFS vs DFS demo

Grading

Case Visualizer

Now that you’ve implemented BFS, let’s take a second to explore a handy visualization tool we’ve added to help with the rest of the assignment. Obviously working on these search algorithms without being able to see what your algorithm is outputting in a network graph format is tough, so we’ve made it easy for you! The cell below shows how you can use the visualizer to visualize any test case that might be giving you trouble.

Warmup 2 – Uniform Cost Search [12pts]

Implement uniform-cost search by completing the uniform_cost_search() method in submission/ucs.py by using PriorityQueue as your frontier. From now on, PriorityQueue should be your default frontier. The function should return a path from the start to the goal node as a list of nodes.

The astute of you may have noticed that uniform-cost search is a special case of A, where the heuristic is the null heuristic, UCS is still different from A (even though the search behavior will be identical). The difference lies in the fact that UCS is an uninformed search, relying solely on path costs, unaware of any heuristics or a node’s location. That’s why you should NOT call A* with a null heuristic, you should NOT use heuristics in your implementation, and you should NOT be attempting to access a node’s position anywhere in your UCS implementation. Doing so will give you a “call(s) to astar detected” error on Gradescope.

Requirements

1. Implement the uniform_cost_search() method in submission/ucs.py.
2. If the start and goal are the same, simply return an empty list like [].
3. Return the best path found as a Python list from the start node to the goal node (inclusive).
4. You can obtain a dictionary of the neighbors of a node by calling graph.neighbors(node).
5. Sort the neighbors of a node alphabetically before processing them.
6. You can access the edge weight between two nodes u and v by using graph.get_edge_weight(u, v).
7. Make sure no node is explored more than once.

Recommended (Approved) Resources

• Canvas Search Modules
• Course AIMA Textbook 4th Edition, Section 3.4.2
• R&N Slides on Uninformed Search

Grading

Warmup 3 – A* [12pts]

Implement A* search using Euclidean distance as your heuristic. You’ll need to implement euclidean_dist_heuristic() then pass that function to a_star() as the heuristic parameter. We provide null_heuristic() as a baseline heuristic to test against when calling a_star tests.

The astute of you may have noticed that UCS is a special case of A*. Perhaps it may save you some time if you implement A* first, then transfer your code over to UCS, and then make the necessary modifications to make the code reflect the UCS requirements…

Requirements

1. Implement the euclidean_dist_heuristic() and the a_star() method in submission/astar.py.
2. If the start and goal are the same, simply return an empty list like [].
3. Return the best path found as a Python list from the start node to the goal node (inclusive).
4. You can obtain a dictionary of the neighbors of a node by calling graph.neighbors(node).
5. Sort the neighbors of a node alphabetically before processing them.
6. You can access the edge weight between two nodes u and v by using graph.get_edge_weight(u, v).
7. You can access the (x, y) position of a node u by using graph.pos(u). You may find this useful for calculating the Euclidean heuristic.
8. Make sure no node is explored more than once.

Recommended (Approved) Resources

• Canvas Search Modules
• Course AIMA Textbook 4th Edition, Section 3.5.2
• R&N Slides on Informed Search
• Interactive A* demo

Grading

• Your A* implementation must first fully pass null heuristic tests in order to receive any credit.
• Scores below are based on pass ratio of A* implementation on euclidean heuristic tests after passing null heuristic tests.

Exercise 1 – Bidirectional Uniform Cost Search [20pts]

In order to reduce the number of nodes explored by the search process, we can instead use an alternative approach called bidirectional search to simultaneously search from the start and the goal nodes and hope that the two searches will meet in the middle (AIMA 4th Ed. Section 3.4.5). Implement bidirectional uniform cost search by completing the bidirectional_ucs() method in submission/bi_ucs.py. This function should return the path from the start node to the goal node (as a list of nodes).

Stopping Conditions

With Uniform Cost Search, we understand that every time a node is explored by a frontier, the shortest path to this node becomes known by the source from which it is explored from. Because of how frontiers are structured, we also know that any remaining paths on the frontier are guaranteed to have a true path cost of greater than or equal to the paths explored so far. Leveraging this information, we can intuitively conclude that when an intersection is found between the explored nodes of the forward search and the explored nodes of the backwards search, a path can be constructed through this common explored node to form a path between the start and the goal, and no further exploration will yield any paths that can possibly be shorter than this joined path (See page 130 of the Ira Pohl paper). In other words, there is no need for further exploration or expansion of frontiers as it is impossible to find a shorter path through exploration than the one we have just created. An equivalent mathematical expression of this stopping condition would be to stop when  where  is the current shortest unexplored path on the forward frontier,  is the current shortest unexplored path on the backward (reverse) frontier, and  is the current shortest path found that connects the start and the goal (See slide 10 of the Bi-Directional Slides).

However, while the intersection of explored nodes guarantees that no further exploration is necessary, we can create pathological examples to show that the path through the intersection of explored nodes is not necessarily the shortest path, as seen in the scenario below (Via UCS, the start and the goal will meet and join a path at node A before exploring the direct path between the start and the goal. Clearly the joined path through node A is not the shortest path in this scenario).

If we know for certain that no further exploration will yield components of the shortest path, then that must mean that the shortest path is already within the information that we have collected, and so a post-processing step is necessary for going through the information collected to find other candidate paths via crossover nodes, and checking each candidate path to ensure that we guarantee return of the shortest possible path. A past student example of how this post-processing step may proceed can be seen in this provided resource.

Search Ordering

Since there is no multithreading involved, a decision regarding the policy on expansion of the frontiers must be made. Do we alternate between forward and backward frontiers? Or do we expand the frontier with the minimum cost element on top? We leave this investigation up to the student, it may help to try both to see which one performs better with respect to the evaluation metrics.

Requirements

1. Implement the bidirectional_ucs() method in submission/bi_ucs.py.
2. If the start and goal are the same, simply return an empty list like [].
3. Return the best path found as a Python list from the start node to the goal node (inclusive).
4. You can obtain a dictionary of the neighbors of a node by calling graph.neighbors(node).
5. Sort the neighbors of a node alphabetically before processing them.
6. You can access the edge weight between two nodes u and v by using graph.get_edge_weight(u, v).
7. Make sure no node is explored more than once, regardless of which frontier explored it.
8. We provide a small margin of error for your explored count when grading.

Hints

• Your optimal path should be the same optimal path found via unidirectional UCS and A*.

Recommended (Approved) Resources

• Canvas Search Modules
• Course AIMA Textbook 4th Edition, Section 3.4.5
• Ira Pohl Paper (resources/Bi Directional A Star.pdf)
• Bi-Directional Slides (resources/Bi Directional A Star – Slides.pdf)
• Post-Processing Step – Student Example (resources/Student Piazza 17 Example.pdf)

Grading

Exercise 2 – Bidirectional A* [29pts]

We know that A* can further reduce the number of nodes explored with respect to UCS. So, now we upgrade our search algorithm further by implementing the bidirectional_a_star() method in submission/bi_astar.py. This function should return the path from the start node to the goal node (as a list of nodes).

Stopping Conditions

With the involvement of heuristics, the stopping condition from Bi-UCS can be further optimized so that we may stop earlier. Intuitively we understand that our stopping formula should reduce to an equivalent expression to that used in Bi-UCS above when the heuristic function returns zero, but what about the rest of the expression? According to Rice and Tsotras, termination of the algorithm when  guarantees a shortest path, but what does this mean?

Let us first translate the expression into something more recognizable, , seen in slide 16 of the Bi-Directional Slides.  is once again our best path found so far, and  and  are the top paths on the frontiers for the forward and backward searches respectively. But wait, it’s not that simple! Paying careful attention to the syntax definitions from slides 14 through 16 we can see that  and  aren’t simply the true path cost + admissible heuristic, instead its the true path cost + a customized expression of heuristics! Let us take a closer look at the syntax definitions.

First,  and  are the start and goal nodes respectively.  is an estimate on the distance between node  and , a heuristic which is functionally equivalent to our euclidean heuristic measuring the distance from  to the goal () for the forward search. Likewise,  is an estimate on the distance between node  and , a heuristic from node  to the start. We can easily see that  and  are equivalent, an estimate on the distance between the start and the goal. Looking at  and , we see:

and  are the true path costs from the start to the node  and the goal to the node  respectively, equivalent to our  term in standard A*.  and  replace our heuristic  term. Looking at their definitions on slide 15 we see:

At a glance these heuristics seem complicated and aren’t intuitive, but we can put them in the context of the stopping condition to try to decipher what is actually happening. Substituting all of this information into the stopping condition, we get:

The term on the right, , can be seen as an upper bound for how much unseen distance there can be between the two frontier nodes for the connected path to be shorter than the current . If the total length of the edge(s) of the shortest path connecting  and  are greater than this upper bound, then it is guaranteed that the path to be found is going to be larger than , hence we can stop and we won’t be able to find anything new that is better than .

The term on the left is an average of two possible lower bounds on how much this unseen distance between  and  can be, lower bounds calculated using  and . A visual example for  can be seen below, and we can see that if we make  and  collinear, it will produce the shortest possible distance that can connect  and , a lower bound.

And so, if the proposed lower bound on what the unseen distance can be between  and  is greater than or equal to the upper bound on what the unseen distance between  and  is allowed to be, we can safely terminate knowing that further exploration is futile towards finding even shorter paths.

Like bi-UCS, post-processing is also necessary to guarantee that the shortest path is selected as the stopping condition clearly does not reflect which path is shortest. We can also see that when the heuristic is zero, the stopping condition reduces to , matching our bi-UCS stopping condition.

When to update ?

As an aside, constantly updating  is important and page 84 of the Rice and Tsotras paper hints at how best to repeatedly update  to ensure that  is a guaranteed lower bound on all possible connecting paths seen thus far and also to ensure valid termination of the algorithm as early as possible.

Search Ordering

Just like with Bi-UCS there is no multithreading involved and a decision regarding the policy on expansion of the frontiers must be made…

Requirements

1. Implement the bidirectional_a_star() method in submission/bi_astar.py.
2. If the start and goal are the same, simply return an empty list like [].
3. Return the best path found as a Python list from the start node to the goal node (inclusive).
4. You can obtain a dictionary of the neighbors of a node by calling graph.neighbors(node).
5. Sort the neighbors of a node alphabetically before processing them.
6. You can access the edge weight between two nodes u and v by using graph.get_edge_weight(u, v).
7. Make sure no node is explored more than once, regardless of which frontier explored it.
8. We provide a small margin of error for your explored count when grading.

Hints

• Your optimal path should be the same optimal path found via unidirectional UCS and A*.
• How different is the stopping condition from bidirectional UCS? Perhaps there is some accelerated stopping condition that works for both Bi-UCS and Bi-A*…

Recommended (Approved) Resources

• Canvas Search Modules
• Course AIMA Textbook 4th Edition, Section 3.4.5
• Ira Pohl Paper (resources/Bi Directional A Star.pdf)
• Rice and Tsotras Paper (resources/Bi Directional A Star with Additive Approx Bounds.pdf)
• Bi-Directional Slides (resources/Bi Directional A Star – Slides.pdf)
• Post-Processing Step – Student Example (resources/Student Piazza 17 Example.pdf)

Grading

• Your Bi-A* implementation must first fully pass null heuristic tests in order to receive any credit.
• Scores below are based on pass ratio of Bi-A* implementation on euclidean heuristic tests after passing null heuristic tests.

Exercise 3 – Tridirectional UCS [12pts]

Let’s take our search algorithms a step further and investigate what happens when we are trying to connect multiple nodes. With tridirectional UCS, perform uniform-cost search from each of the three starting nodes and keep expanding until you have a continuous shortest path that connects all three nodes. For example, suppose we have goal nodes [a,b,c]. What we want you to do is to start at node a and expand like in a normal search. However, notice that you will be searching for both nodes b and c during this search and a similar search will also start from nodes b and c. Eventually you will be able to construct a path connecting a, b, and c that is the shortest path to travel and visit all three nodes. Note that this is different from performing 3 bidirectional searches (which would generate 6 frontiers instead of the 3 we seek!).

Complete the tridirectional_ucs() method in submission/tri_ucs.py. The function should return a list of nodes in any order as long as the list starts and ends with goal nodes, e.g. (a->b->c == c->b->a == b->a->c etc.).

Stopping Conditions

We know when to stop when performing unidirectional UCS and we know when to stop when performing bi-directional UCS, can we use this knowledge to construct a stopping condition for tri-directional UCS? There are only three UCS searches simultaneously active, can we perhaps view the interaction between two of the three searches as a bi-UCS sub-problem?

At a higher level, we can guarantee a solution by finding the shortest path between each pair of goals, e.g. a-b, a-c, b-c, and then constructing the solution by stitching together the two shortest paths out of the three. But is it truly necessary to find all three paths? If not, can we be happy when we find the first two of the three paths? Or does there need to be some sort of a middle ground between the first two and finding all three?

Search Ordering

Just like with the bidirectional searches there is no multithreading involved and a decision regarding the policy on expansion of the frontiers must be made…

Requirements

1. Implement the tridirectional_search() method in submission/tri_ucs.py.
2. If all three goals are the same, simply return an empty list like [].
3. If there are 2 identical goals (i.e. [a,b,b]) then return the path [a...b] (i.e. just the path from a to b). Do NOT call your bidirectional searches for this, your tridirectional search should naturally handle this scenario.
4. Return the best path found as a Python list connecting all three goal nodes (inclusive).
5. You can obtain a dictionary of the neighbors of a node by calling graph.neighbors(node).
6. Sort the neighbors of a node alphabetically before processing them.
7. You can access the edge weight between two nodes u and v by using graph.get_edge_weight(u, v).
8. Make sure no node is explored more than once, regardless of which frontier explored it.
9. We provide a small margin of error for your explored count when grading.

Hints

1. Why can’t I just run three bidirectional searches? If you run three bidirectional searches, you aren’t taking advantage of the team knowledge collected by all the searches, and end up exploring multiple nodes, multiple times, blowing up your explored count. This is a team effort, all three goals should be searching for each other together, sharing information as necessary to prevent exploration of any node more than once.
2. Why can’t I just take the first two paths I find and call it a day? Are you sure that’s guaranteed to be the most optimal path and the third path found is guaranteed to be larger than the two paths you’ve found? This could vary based on your implementation.
3. Why can’t I just find all three paths and then take the two shortest ones? Are you sure you HAVE to find all three paths in order to pick the two shortest ones? You might end up exploring too many nodes in some cases…
4. Ok if I can’t do either of the above then what can I even do? Is it really black and white? Is there really no in-between option?
5. How is it possible not to explore any node more than once when there are two searches? The search is a team effort. All teammates are aware of each other’s knowledge so no node should ever have to be explored more than once.
6. Why are there no provided resources? This is a thinking exercise. You are meant to build upon what you have learned so far from the assignment and to think about what a Tridirectional search brings to the table and how you can deal with those new issues and tricks.
7. Try creating small graph scenarios on paper to see what interesting situations may arise. This will help you as you try to develop your stopping condition(s).

Recommended (Approved) Resources

• Canvas Search Modules (for tridirectional inspiration)
• This is a thinking exercise! Build off of the lessons you’ve learned from the previous sections to tackle this problem!

Grading

Exercise 4 – Tridirectional A* [8pts]

This is the heart of the assignment. Implement tridirectional search in such a way as to consistently improve on the performance of your previous implementation. This means consistently exploring fewer nodes during your search in order to reduce runtime. Keep in mind, we are not performing 3 bidirectional A* searches. We are searching from each of the goals towards the other two goals, in the direction that seems most promising. Think about how you want the search algorithm to be have as it expands away from its source nodes, is there a peculiar shape that it should look like while this expansion occurs?

Complete the tridirectional_upgraded() method in submission/tri_astar.py. The function should return a list of nodes in any order as long as the list starts and ends with goal nodes, e.g. (a->b->c == c->b->a == b->a->c etc.).

Requirements

1. Implement the tridirectional_upgraded() method in submission/tri_astar.py. Optionally, you can also implement custom_heuristic() if you so choose.
2. If all three goals are the same, simply return an empty list like [].
3. If there are 2 identical goals (i.e. [a,b,b]) then return the path [a...b] (i.e. just the path from a to b). Do NOT call your bidirectional searches for this, your tridirectional search should naturally handle this scenario.
4. Return the best path found as a Python list connecting all three goal nodes (inclusive).
5. You can obtain a dictionary of the neighbors of a node by calling graph.neighbors(node).
6. Sort the neighbors of a node alphabetically before processing them.
7. You can access the edge weight between two nodes u and v by using graph.get_edge_weight(u, v).
8. Make sure no node is explored more than once, regardless of which frontier explored it.
9. We provide a small margin of error for your explored count when grading.

Hints

1. What makes tridirectional A* different from tridirectional UCS? Well for starters, A* uses heuristics to accelerate the exploration process. While the Euclidean heuristic is still available, there are two goals for every search that is expanding, which means there will be two heuristic values. Which one should you choose? Could we combine them? Its time to get creative!

Recommended (Approved) Resources

• Canvas Search Modules (for tridirectional inspiration)
• This is a thinking exercise! Build off of the lessons you’ve learned from the previous sections to tackle this problem!

Grading

Further Reading

Here are other pre-approved resources that you may look at over the course of this assignment, note that some of them are duplicates of resources presented throughout this notebook.

General resources:

• Canvas Course Videos: Search Module
• AIMA 4th Edition Textbook
• R&N slides on Uninformed Search
• R&N slides on Informed Search
• Comparing BFS and DFS
• A* Search Demo

Advanced resources:

• A Star meets Graph Theory (resources/A Star meets Graph Theory.pdf)
• Bi Directional A Star – Slides (resources/Bi Directional A Star – Slides.pdf)
• Bi Directional A Star with Additive Approx Bounds (resources/Bi Directional A Star with Additive Approx Bounds.pdf)
• Bi Directional A Star (resources/Bi Directional A Star.pdf)
• Search Algorithms Slide Deck (resources/Search Algorithms Slide Deck.pdf)
• Bi Directional Stopping Conditions, Piazza ’17
• Bi Directional Search Visualizations
• Piazza: Landmark Example

Interesting reads – links from Canvas, below the videos:

• Finding Optimal Solutions to Rubik’s Cube Using Pattern Databases
• God’s Number is 26 in the Quarter-Turn Metric
• Reach for A∗: An Efficient Point-to-Point Shortest Path Algorithm
• Computing the Shortest Path: A∗ Search Meets Graph Theory
• Reach-based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks

Please refrain from referring to code/psuedocode from other resources aside from these.