CS 57100: Artificial Intelligence

Assignment 4: Constraint Satisfaction, Planning with Uncertainty

Due 11:59pmEDT Wednesday, 12 October 2022

Please turn in a PDF through Gradescope. ITaP provides these instructions. Make sure that you mark the start/end of each question in Gradescope. Assignments will be graded based on what you mark as the start/end of each question. Please typeset your answers (LaTex/Word/OpenOffice/etc.)

1. Constraint Satisfaction: Modeling

For course scheduling, model taking classes to meet CS core course PhD requirements (one theory course, one systems course, must average 3.5) as a constraint satisfaction problem. Discuss at least one limitation of your model (or why you feel it captures everything of importance.).

2. Constraint Satisfaction: Search

You are given the state diagram below, the goal is to get from start to final with minimum cost. Assume that a 1-letter transition (U,R,L, D) costs 1, a 2 letter transition (DL, DR) costs 1.5.

Find an optimal solution to the problem.
Show a search ordering that makes finding an optimal solution expensive, and an ordering that significantly improves from your expensive solution. Explain how you found the better approach.
Does arc consistency (AC-3) help? Demonstrate.
Would greedy search or beam search be a good idea for a larger version of this problem? Explain why or why not.

3. Markov Decision Processes: Modeling

Again, model taking classes to meet CS core course PhD requirements (one theory course, one systems course, must average 3.5), but this time as a Markov Decision Process. Assume you have an estimate of your probability of getting a certain grade in each class.

Model this problem as a Markov Decision Process.
Discuss what you gain, and what you lose, modeling this as a Markov Decision Process as opposed to modeling as Constraint Satisfaction (problem 1.)

4. Markov Decision Processes: Policy Evaluation

Repeat problem 2.1, but this time assume that the single letter transitions occur with 100% probability, but a two letter transition only succeeds with probability 0.7; with probability 0.3 if you attempt a two-letter transition nothing happens (but you still expend cost 1.5).

Things to think about, but not to turn in. Would the outcome be different if the nothing happens with probability 0.3 had cost 0? What would happen if an attempt at a two-letter transition with probability 0.3 took a randomly selected one of the other transitions instead of staying in place?

5. Markov Chain Monte Carlo

For Problem 4, assume that you didn't know the probability of a move succeeding or failing. Would Markov Chain Monte Carlo be able to give a good estimate of the probabilities? Explain why or why not.