CS534 Artificial Intelligence 
Homework 4 - Spring 2019

PROF. CAROLINA RUIZ 

Due Date: Friday, March 15th, 2019 during office hours 10-11 am or 1-2 pm  

Homework Instructions:

1. Read Chapters/Sections 10 and 11.1 of the textbook.

2. This is a group homework. Students *must* form groups of 2 students. Students are free to select their HW4 teammate (it doesn't need to be the same teams as in previous homework). You can post on the Canvas discussion board if you are looking for a HW4 teammate.

3. Do *not* split the problems between you and your teammate. Instead, solve each and every required HW problem by yourself and then meet with your teammate to compare your solutions and work on a joint solution together. This will prepare you both for the exam.

4. Turn in your group's written solutions (hardcopy) ONLY TO THE PROBLEMS MARKED AS REQUIRED BELOW by 10:59 am right before the beginning of class when the homework is due. No late homework will be accepted, no exceptions.

5. Solve the other, non-required problems in preparation for Exam 2 but don't submit your solutions as part of HW4 submission.

6. Only a subset of problems will be graded in detail (for a total of 90 points) and the remaining ones will receive credit based on a quick review (for a total of 10 points). The set of problems to be graded will be selected by the professor and won't be revealed until the HW has been submitted.

Homework Problems:

• Chapter 10: (pp. 396-400)
  • Required for the HW:
    • 10.1
    • 10.2
    • Monkey and Bananas planning problem (adapted from 10.3) following the steps below:
      • Use this initial situation, final situation and action schemas provided here. Note: This version is slightly different to the handout used in class, so please use this online version.
      • Use partial-order planning (PoP) to construct a plan to go from the initial situation to the final situation in this problem. See Section 10.4.4 (pp. 390-391) of the textbook and the textbook slides. Follow the PoP algorithm in Slide 9 showing your work at each step of the search:
        1. Show each state of the search (i.e., partial plan) separately. That is, do not show just the final result; instead show each state in the search starting with the initial state (containing just the initial and final situations), intermediate search states (containing partially constructed plans) and the goal state (containing a fully constructed plan where all subgoals and action preconditions are met, and "promotion/demotion" ordering constraints are added as needed to resolve threats). Perform the search following the PoP algorithm.
        2. At each step of the PoP search, explain what action or what link between an action as a precondition/subgoal or what ordering constraint is added to the partial plan and why.
        3. If the PoP search needs to backtrack due to a conflict, show and explain the backtracking steps as well.
  • Not required for the HW but useful to study for the exam:
    • 10.12

• Chapter 11:
  • Required for the HW:
    • Read Section 11.1 (Time, Schedules, and Resources pp.401-405) of the Russell's and Norvig's textbook. Write an explicatory summary (couple of paragraphs) highlighting the main points covered in that section in your own words.