HW 4 -- Search

The questions below are due on Monday March 09, 2026; 11:59:00 PM.

You are not logged in.
Please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.mit.edu) to authenticate, and then you will be redirected back to this page.

This week's Colab notebook can be found here: Colab Notebook (Click Me!)

1) Written Questions§

1.1) Warm-Up: Algorithm Simulations (Optional)§

Consider the search graph shown below. S is the start state, and G is the (only) goal state. All edges are bidirectional. Note that the heuristic values are written in the circles corresponding to the states.

Make the following assumptions:

Ties are broken alphabetically by last node in search. For example, a partial plan S \to X \to A would be popped from the frontier before S \to X \to B.
All edge costs are positive.

Also note that:

The algorithms in AIMA check for redundant paths when a child state is generated by the successor function before it has been added to the frontier.
All cost-based algorithms, implemented using best-first-search, terminate when a node corresponding to a goal state is popped from the frontier, not when the node is added to the frontier. Breadth-first search in AIMA terminates when a goal is generated by the successor function, before it is added to the frontier.

Click to open image in new window

For each search algorithm below, give the ordering of all the states that the algorithm pops from the frontier. Further, give the path that each algorithm returns. Each answer is a string of state names separated by hyphens, such as "S-A-G".

For breadth-first graph search (ignores costs), enter the states popped (in order).
For breadth-first graph search (ignores costs), enter the path returned.
For uniform-cost graph search, enter the states popped (in order).
For uniform-cost graph search, enter the path returned.
For greedy best-first graph search (ignores costs), enter the states popped (in order).
For greedy best-first graph search (ignores costs), enter the path returned.
For A* graph search, enter the states popped (in order).
For A* graph search, enter the path returned.

1.2) Grids§

Consider a uniform grid that extends infinitely in all directions.

In the grid on the left, each state has four child states (movement on the grid is limited to up, down, left, and right). In the grid on the right, each state has eight children (diagonal moves are allowed).

We start at the grid point marked S. Assume the goal is far away and not shown in the figures.

1.2.1) BFS with NO pruning§

Answer the following questions about breadth-first search with no pruning. Specifically, by no pruning, we mean not even pruning out paths that contain cycles (i.e., include the same state more than once).

In the left grid, how many paths with one edge are ever added to the frontier?
In the left grid, how many paths with 2 edges are ever added to the frontier?
In the right grid, how many paths with one edge are ever added to the frontier?
In the right grid, how many paths with 2 edges are ever added to the frontier?

1.2.2) BFS with a reached test§

Answer the following questions about breadth-first search with a reached test, which never adds a state's descendants to the frontier more than once.

In the left grid, how many paths of length 1 are ever added to the frontier?
In the left grid, how many paths of length 2 are ever added to the frontier?
In the right grid, how many paths of length 1 are ever added to the frontier?
In the right grid, how many paths of length 2 are ever added to the frontier?

1.2.3) Uniform-Cost (UC)§

In the grid on the left, each state has four child states (movement on the grid is limited to up, down, left, and right). In the one on the right, each state has eight children (diagonal moves are allowed).

In this problem, we will consider uniform-cost search in the above domain. Assume that:

The cost of traversing a path is the Euclidean distance of the path.
The distance between points in the vertical and horizontal directions is 1 meter.

Answer the following questions about uniform-cost search without a reached test in the eight-action grid (the grid on the right). Your answers should be decimal numbers accurate to within 0.01.

What is the cost of the second node popped?
What is the cost of the sixth node popped?
What is the cost of the tenth node popped?

1.2.4) A*§

The Manhattan distance between two states (x_0,y_0) and (x_1,y_1) on the grid is defined as:

d_\text{Manhattan}\left(\left(x_0,y_0\right), \left(x_1,y_1\right)\right) = |x_0 - x_1| + |y_0 - y_1| .

In the left grid, are we guaranteed to find an optimal path?

Yes

No
In the right grid, are we guaranteed to find an optimal path?

Yes

No

1.3) Heuristics§

1.3.1) Heuristics 1§

Consider the following graph, where S is the start state and G is the (only) goal state, and the arcs are labeled with their actual costs.

Click to open image in new window

For each of the two heuristics h_1 and h_2 in the table below, determine whether the heuristic is admissible and/or consistent.

Mark all that are true.

	h_1 is admissible.
	h_1 is consistent.
	h_2 is admissible.
	h_2 is consistent.

1.4) Heuristics 2§

Consider a search problem where all edges have cost 1 and the optimal solution has cost C. Let h be a heuristic which is \max(h^{*} - k, 0) where h^{*} is the actual cost to the closest goal and k is a nonnegative constant.

Mark all that are necessarily true.

h is admissible.

h is consistent.
Now consider the same search problem, but with a heuristic h' which is 0 at all states that lie along an optimal path to a goal and h^* elsewhere.

Mark all that are necessarily true.

h is admissible.

h is consistent.

1.5) Moving Day§

Here is a really big problem to help think about constructing heuristics. Imagine that you have to do the logistics planning for trucks that drive around and pick up packages from different businesses. You know the sizes of the packages (thankfully, all cubes, but not of the same dimension) and the complete road map in advance.

Your possible actions are:

to drive from one intersection to another in the city map (cost of this action is the length of the drive),
to pick up a package and place it in the truck at a specific position (in x, y, z, relative to a given corner of the cargo compartment) (cost of this action is 1).

The requirements of this problem are:

You can only drive on roads.
You cannot unload a package from the truck once you pick it up.
You cannot re-arrange packages once you place them in the truck.
You cannot move packages through other packages inside the truck when placing the package.
When you place a package in the truck it has to be fully supported by the floor of the truck or on a bigger (or equal) package.
The dimensions of the truck cargo compartment are given: (W, L, H) and the packages must be fully inside the cargo compartment.
All the distances between intersections (and the depot) are greater or equal to 1.

Given a list of packages (id, size, location) and a map, your job is to find the shortest path (in driving distance) starting at the depot, that picks up all the packages and returns to the depot.

What information below must be included in the minimal state space for the search?

Mark all that apply (such that your selection is minimal).

	truck location (an intersection)
	distance traveled to reach truck location (number)
	path traveled to reach truck location (list of intersections)
	uncollected package ids (set of ids)
	uncollected package locations (set of (id, intersection))
	uncollected package sizes (set of (id, size))
	location of the packages in the truck (set of (id, xyz))
	sizes of the packages in the truck (set of (id, size))

Which of the following heuristics are admissible (and not always zero) for this problem class?

Mark all that are admissible and not always zero.

	h_0: The straight-line distance from the current location to the depot
	h_1: The number of uncollected packages
	h_2: The sum of distances from current location to the locations of the uncollected packages
	h_3: The distance to the closest uncollected package

Which of the following heuristics are admissible (and not always zero) for this problem class?

Mark all that apply.

h_0 + h_1

h_0 + h_2

h_0 + h_3

h_1 + h_2

h_1 + h_3

h_2 + h_3

\max(h_0, h_1)

\max(h_0, h_2)

\max(h_0, h_3)

\max(h_1, h_2)

\max(h_1, h_3)

\max(h_2, h_3)

If we consider the sub-problem of getting from the current state in the search to the goal and ignore some constraints, we get a relaxation. Which of the following relaxations produce non-trivial admissible heuristics (non-trivial in the sense that it is not always zero) for this problem class?

Mark all that apply.

	Solve the problem assuming there are no packages to pick up
	Solve the problem ignoring the choice of package locations in the truck, assuming they will fit somewhere.
	Solve the problem ignoring the map constraint, assuming we can go to any location in a straight line.

2) Search§

2.1) Driving§

You are driving an electric vehicle over a road network that connects up a set of small towns. You know the locations of the towns and the road map, which contains at most one road between each pair of distinct towns. The roads are all two-way.

The length of each road segment r is \text{length}(r).
Your battery can hold m units of charge, maximum.
Every mile requires 1 unit of charge.
You drive 1 mile per minute.
Some towns have chargers that charge at the rate of 10 units per minute, and some have no charger at all.
If you run out of charge you can no longer continue.
Some roads have cell service and some do not. Your car is so modern it does not have a radio, so if there's no cell service you will be bored. When you are bored, your perceived time goes slower—you will perceive time twice as long as the actual time. (You won't be bored when charging the vehicle, since you can always walk around the town).
You would like to find a path (including charging stops) to a goal town that minimizes your overall perceived time.

Formulate this as a min-cost-path problem, where the action space consists of drive(r) where r is a road segment connecting two towns, and charge(t) where t \in \{10, 20,\ldots, 100\} is a duration of charging in minutes.

Which of the following components must be included in a minimal state space representation for this problem? Select all that apply.

Current location

Current time

Boredom status

Battery charge level

Which towns have chargers

In what states s is the action drive(r) necessarily executable?

	When \text{length}(r) \leq \text{battery charge in } s.
	When the town in s is equal to the start town of r and \text{length}(r) \leq \text{battery charge in } s.
	When the battery charge in s > 0.
	When there is a valid path from the town in s to the start town of r and \text{length}(r) \leq \text{battery charge in } s.
	When \text{length}(r) \leq \text{battery charge in } s and the destination town has a charging station.

Which of the following statements correctly describe the cost function C(s, a, s') for this problem? (Select all that apply)

	The cost of charge(t) is t minutes.
	The cost of charge(t) is 10 \cdot t minutes.
	Given r, the cost of drive(r) depends on s and s'.
	The cost of drive(r) is 2 \cdot \text{length}(r) minutes if r lacks cell service.

For each of the following heuristics, indicate whether it is admissible and whether it has a smaller search space than the original problem.

The cost of the minimum cost path, under the assumption that the battery level never decreases.

admissible

smaller search space than original

neither
The cost of the minimum cost path under the assumption that the penalty for boredom is half as high.

admissible

smaller search space than original

neither

2.2) Flying§

Now, let's assume that you are a drone, flying above the terrain, but staying at a fixed altitude.

You can still go 1 mile per minute, your battery still holds m units, and the chargers and charging time remain the same (this is a big drone)!
Drones never get bored.
There are some high peaks that prevent you from moving within some regions of the space at your fixed altitude, essentially forming obstacles in a planar problem.
This drone has no problem hovering and is insensitive to wind, so you can assume that forces and velocities are handled by the controller and you only need to worry about paths and charging.
Drone motion is holonomic; it can move in any direction.
The chargers are in the same place, and your start and goal locations will be towns, but the road network is irrelevant.

You can do long-distance induction charging (!). You are given a function (\text{charge-delta}(l_i, l_j)) that returns the aggregate change in charge (which may be positive or negative) due to flying from (l_i) to (l_j) in a straight line. This is the change before applying the battery's max-capacity cap: the battery has over-charge protection, so it stops accumulating charge once it is at max capacity.

You decided to use trajectory optimization to approach this problem. The overall cost of the trajectory is the sum of the costs of n individual linear segments:

J((l_0, b_0), (l_1, b_1), \ldots, (l_n, b_n)) = \sum_i C((l_i, b_i), (l_{i+1}, b_{i+1}))

l_0 = \text{start}

b_0

l_n = \text{goal}

The cost for each segment includes several terms, including the segment length, the degree to which the segment penetrates an obstacle, and the degree to which the charging dynamics are respected (\alpha and \beta are constants that trade off the relative importance of the terms):

C((l_i,b_i), (l_j, b_j)) = | l_i - l_j |^2 + \alpha \cdot \text{penetration}((l_i, l_j, \text{obstacles})) + \beta \cdot \text{charge}_{i,j}

Which of the following terms captures the degree to which charging dynamics are respected (\text{charge}_{i,j})?

| b_i - b_j |^2

| b_i + b_j |^2

| b_i + \text{charge-delta}(l_i, l_j) + b_j |^2

| b_i + \text{charge-delta}(l_i, l_j) - b_j |^2

Explain your choice from above. Why is this the correct term?

	Because the charge must always increase monotonically.
	Because the change in charge between the endpoints has to match the charge-delta.
	Because the battery must end at maximum capacity.
	Because the absolute value of the charges must be minimized.

However, we're missing a term in the cost function! What is it?

A penalty for traveling faster than 1 mile per minute.

A penalty for the battery charge going negative.

A penalty for the battery exceeding maximum capacity m.

A penalty for hovering too long.
Of these four terms (the three we listed, plus the one you provided above), which ones, if any, need to be driven to 0 to obtain a legal trajectory?

length (| l_i - l_j |^2)

penetration (\text{penetration}((l_i, l_j, \text{obstacles})))

charge-delta (\text{charge}_{i,j})

missing (answer to previous)

3) Search Algorithms §

In this section you will implement the best-first search framework. To help with your implementation, we have provided you various utilities in the Colab notebook. Before starting on the implementations, you should read the utilities we provide you carefully.

3.1) Best-first Search§

Complete an implementation of the best-first search, encompassing A*, GBFS, or UCS. You can assume any heuristics are consistent. You should follow the psuedocode given in lecture closely. In particular, your implementation should prune redundant paths by remembering the reached states.

For reference, our solution is 55 line(s) of code.

def run_best_first_search(
    problem: PathCostProblem,
    get_priority: Callable[[Node], float],
    step_budget: int = 1000) -> Tuple[StateSeq, ActionSeq, CostSeq, int]:
  '''A generic heuristic search implementation.

Depending on `get_priority`, can implement A*, GBFS, or UCS.

The `get_priority` function here should determine the order
  in which nodes are expanded. For example, if you want to
  use path cost as part of this determination, then the
  path cost (node.g) should appear inside of get_priority,
  rather than in this implementation of `run_best_first_search`.

Important: for determinism (and to make sure our tests pass),
  please break ties using the state itself. For example,
  if you would've otherwise sorted by `get_priority(node)`, you
  should now sort by `(get_priority(node), node.state)`.

Args:
    problem: a path cost problem.
    get_priority: a callable taking in a search Node and returns the priority
    step_budget: maximum number of `problem.step` before giving up.

Returns:
    state_sequence: A list of states.
    action_sequence: A list of actions.
    cost_sequence: A list of costs.
    num_steps: number of taken `problem.step`s. Must be less than or equal to `step_budget`.

Raises:
    error: SearchFailed, if no plan is found.
  '''
  raise SearchFailed("Implement me!")

3.2) Uniform Cost Search§

Use your implementation of run_best_first_search to implement uniform cost search.

For reference, our solution is 3 line(s) of code.

In addition to all of the utilities defined at the top of the colab notebook, the following functions are available in this question environment: run_best_first_search. You may not need to use all of them.

3.3) A* Search§

Use your implementation of run_best_first_search to implement A* search.

For reference, our solution is 3 line(s) of code.

3.4) Greedy Best-First Search§

Use your implementation of run_best_first_search to implement GBFS.

For reference, our solution is 3 line(s) of code.

4) Feedback§

How many hours did you spend on this homework?
Do you have any comments or suggestions (about the problems or the class)?

	h_0 + h_1
	h_0 + h_2
	h_0 + h_3
	h_1 + h_2
	h_1 + h_3
	h_2 + h_3
	\max(h_0, h_1)
	\max(h_0, h_2)
	\max(h_0, h_3)
	\max(h_1, h_2)
	\max(h_1, h_3)
	\max(h_2, h_3)

	Current location
	Current time
	Boredom status
	Battery charge level
	Which towns have chargers

	\| b_i - b_j \|^2
	\| b_i + b_j \|^2
	\| b_i + \text{charge-delta}(l_i, l_j) + b_j \|^2
	\| b_i + \text{charge-delta}(l_i, l_j) - b_j \|^2

	A penalty for traveling faster than 1 mile per minute.
	A penalty for the battery charge going negative.
	A penalty for the battery exceeding maximum capacity m.
	A penalty for hovering too long.

	length (\| l_i - l_j \|^2)
	penetration (\text{penetration}((l_i, l_j, \text{obstacles})))
	charge-delta (\text{charge}_{i,j})
	missing (answer to previous)

	Yes
	No

	Yes
	No