COS 402: Artificial Intelligence

Numbers in brackets indicate approximate number of points each problem is worth.  See the course home page for information on when and where to submit written exercises, and grading criteria.

1.  [10] There are many "chatterbots" on the web that attempt to carry on human-level conversations, often within a limited domain.  These include:

• "Alice" at alicebot (previous winner of the Loebner Prize, an annual competition of chatterbots).  Click on "chat with Alice".
• "Bildgesmythe" at www.personalityforge.com (previous winner of the Chatterbox Challenge).
• "English tutor".
• Many, many others at www.simonlaven.com and the Chatterbox Challenge.

Have a "conversation" with one or more of these chatterbots.  Try to test what they can or cannot do, what they are good at, and what they are not so good at.  See what you can learn about how they work.  Then briefly (say, in three paragraphs or less) describe and analyze your experience.

2.  [15] Exercise 3.15 in R&N.

3.  [10] Exercise 3.18 in R&N.  Be sure to justify your answer.

4.  [15] Consider the following toy search problem:

The states are the vertices of this graph.  The start state is S, and the goal state is G.  The actions permit movement along directed edges with costs as indicated.  (For instance, the cost of moving from S to U is 2; the cost from U to V is 9.)  The numbers in blue by each vertex indicate heuristic h values.  (For instance, h(S)=9; h(U)=10.)

a.  Show that this choice of h is consistent.

b.  Draw the search tree that would result from running greedy best-first search.  Also number the nodes of the search tree in the order in which they are expanded.  For instance, place the number 1 by the start node (associated with the start state S).

c.  Do the same thing for A*.  Also indicate the g and f values associated with each search node.

5.  [10] Exercise 3.29 in R&N.  Also, answer the following:  Does the admissible-but-not-consistent heuristic that you constructed have the monotone property that we discussed?  In other words, is it the case that the f-values are nondecreasing along every path?

6.  [8 HP] Referring to the graph-search variant of A*, RN states: "With an admissible, but inconsistent heuristic, A* requires some extra bookkeeping to ensure optimality".

a.  Where does this statement appear in RN ? (indicate the page and the location on the page)

b.  Modify the graph-search A* algorithm to ensure that it is optimal for all admissible heuristics.

c.  Prove that your algorithm finds the optimal solution for admissible heuristics.

7.  [8 HP] In class, we have talked about the pathfinding problem where the task is to find the shortest path through a labyrinth from the initial location to a target location. Consider now a different problem where one is given a set of target locations, and is asked to find the shortest path that goes though ALL target locations (See figure below - green is initial point, red are target locations, and blue is a solution path). Assume that the agent can only move up, down, left or right (i.e. no diagonal moves).

a.  Formulate the problem as a search problem (what is a state, the transition function, the cost function, the goal test, etc). Are the actions reversible? Could you use bidirectional search?

b.  Propose an admissible heuristic function for the problem. Be sure to justify why your heuristic is admissible. (Better heuristic functions will receive more points)