UDel CISC681/481-010 Artificial Intelligence, Fall 2009news | syllabus | schedule | homework |

Homework #2: Informed search, CSPs, games, and logic

Posted 10/6; due at the beginning of class on 10/15.
  1. Heuristics (10 points): The Manhattan distance heuristic for the 8-puzzle is the sum of the Manhattan distances of each tile to its correct location on the 3x3 board. This heuristic is admissible.
    1. Show that the Manhattan distance heuristic is consistent.
    2. Now consider a slight variation: h' = the Manhattan distance heuristic plus the Manhattan distance from the blank space to the upper left space. Show that h' is inadmissible.
    3. Prove that as long as a heuristic does not overestimate the cost by more than a fixed constant c, the solution A* finds will have cost that exceeds the true cost by no more than c.

  2. Constraint satisfaction and logic (20 points):
    1. Problem 5.13 in the book lists a series of facts and asks a question to be answered. Formulate the problem as a CSP. Clearly state your variables, their domains, and the constraints.
    2. Sketch the first five steps of a solution to the CSP problem using backtracking, forward checking, and the MRV and least-constraining value heuristics.
    3. Now reformulate the given facts as a propositional logic knowledge base. Use propositional inference rules to determine the answer to the question.

  3. Games 1 (15 points): Problem 6.1 in the book.

  4. Games 2 (681 students, 15 points): Problem 6.8 in the book.