Written Assignment 1 (W1): Agents and Search

Question 1 (3 points). Write PEAS descriptions for the following tasks. A correct answer to each task can fit in four lines, one for each aspect.

1. A web-based machine translation system (like Systran)
2. A search and rescue robot for exploring a collapsed mine (similar)
3. A burrito-building robot

Question 2 (3 points). Consider the following search graph in which A is the start state and F is the goal state. Assume that for each search method, the details are such that a state's children will be visted in alphabetical order when possible.

1. In what order will the states be expanded by a depth-first tree search (no closed list)?
2. In what order will the states be expanded by a breadth-first graph search (with closed list)?
3. In what order will the states be expanded by a uniform-cost graph search (with closed list)?

Question 3 (4 points). Burrito assembly scheduling: You manage a taqueria. Making a burrito requires a set of tasks x₁, …, x_n. Each task x_i takes t_i minutes to complete. Also, some tasks require other tasks to be completed before they can be begun. You may schedule tasks among your e employees. How fast can you make a burrito?

Example: You have two (e = 2) employees and the following tasks, with the following requirements and durations listed:

• Steam tortilla: 1
• Cook steak: 3
• Add beans: 1 (requires steamed tortilla)
• Add cheese: 1 (requires steamed tortilla)
• Add steak: 1 (requires steamed tortilla, cooked steak)
• Wrap burrito: 1 (requires all added)
• Prepare to-go bag: 3
• Collect money from customer: 3
• Put burrito in a prepared bag: 1 (requires wrapped burrito, prepared bag)

1. Why can we think of this scheduling problem a single agent search problem rather than a multi-agent problem?
2. Formulate this problem as a single agent search problem. What are the states, successor functions, start state, goal test, and cost function?
3. Describe a non-trivial heuristic for this problem. Your heurisitic should result in a performance improvement for one of the standard search algorithms.
4. How would you modify your formulation if each task could have a different cost for each employee?

Question 4 (5 points). Properties of Search Techniques

1. Show that breadth first search, depth-first search, and uniform-cost search are special cases of best-first search.
2. Show that uniform-cost search is a special case of A* search.
3. Prove that if a heuristic is consistent, it must be admissible. Construct an admissible heuristic that is not consistent.

Question 5 (5 points). The Traveling Salesperson Problem (TSP) is a frequently studied route planning problem. In a TSP, one has a set C of cities connected by roads. The length of the direct roads between cities x and y is given by d(x,y); if two cities are not directly connected by a road, d(x,y) will be infinite. A tour is a list of cities that starts and ends at the same city and visits each city exactly once. The task is to find a tour of minimum total length. It is impractical to enumerate all tours, so one must devise better, often approximate, algorithms to solve TSPs.

1. Assuming there are N cities and all roads exist, how many distinct tours are there? For this question, assume (a, b, c, a), (b, c, a, b), and (a, c, b, a) are all the same tours.
2. Give a formulation which casts the TSP as a single agent search problem in which optimal solutions correspond to TSP solutions. What are the states and successor functions? What is the start state and what is the goal test? What is the cost of a single action? (Hint: without loss of generality, you may assume that some city s in C is to be the beginning of the tour.)
3. If all cities are connected with roads of length 1, compare briefly the behavior of DFS and BFS. Under these circumstances, is DFS complete? Optimal? Is BFS complete? Optimal? Which is better and why?
4. If roads have arbitrary length, which of the following will be optimal: DFS, BFS, uniform cost search, greedy search, and/or A* search?
5. Give a non-trivial and reasonably efficient admissible heuristic for this problem and prove its admissibility.