## CS4341 Introduction to Artificial Intelligence. C-2002 Solutions Exam 1 - February 5, 2002

### By Wendy Kogel, Yakov Kronrod, Greg Milette, and Carolina Ruiz

#### Problem I. Search (25 points)

In this problem, you are asked to select the best search strategy for each of the situations given below. Although you are not required to write a justification for your choices, if you do, you may earn partial credit in case that your answer is wrong but your justification is sound.
1. (5 points) Cost is given but not heuristic information. You need to find an optimal path.
```Search method: Branch and Bound

Although it is an informed search it only uses cost and not heuristic information.
It is also guaranteed to find an optimal solution.

```
2. (4 points) No cost and no heuristic information are given. You know that the search space is finite and that you don't have space available to store more than one path at the time. Any solution (if more than one exist) is acceptable.
```Search method: Depth First

It is not an informed search, and because the space is finite it is guaranteed to find a
solution, if there is one.  Depth 1st also only saves one path at a time and therefore
meets the space requirements.

```
3. (4 points) Cost and heuristic information are given. You need to find an optimal solution and you want to save as much time as possible.
```Search method: A*

A* uses cost and heuristic, it's guaranteed to find optimal paths,
and its time performance is optimal among search algorithms that find optimal paths.

```
4. (4 points) No cost and no heuristic information are given. You need to find the shallowest solution, you want to optimize time, and you have plenty of memory/space to use.
```Search method: Breadth First

Will find the most shallow solution because it goes level by level.  It requires less time
then Iterative Deepening because it does not have to rebuild the tree.
(If you answer was Iterative Deepening you should have lost 1 point.)

```
5. (4 points) No cost and no heuristic information are given. You need to find the shallowest solution but you don't have memory/space available to store more than one path at the time.
```Search method: Iterative Deepening

This method allows you to only search down one path at a time while
gradually increasing the depth of the search space.  This way you will
find the shallower solution with limited space.
(If your answer was Depth-Limited you lost 2 points because you do not
points because of violating the memory requirement.)

```
6. (4 points) Heuristic information is given. The search space is finite, but quite large. You want to find a good solution fast but don't have enough memory to keep more than one path at the time.
```Search method: Hill Climbing

Hill Climbing narrows the search area to follow one path at a time
through the search space.  It does not find an optimal solution but it
will find a good solution if one exists, given that the search space
is finite.
(If your answer was Beam Search you lost 2 points because Beam Search
stores more that one path at the time. Also, Beam Search is not
guaranteed to find a solution.  If your answer was Greedy you lost 2
points because you violated the space requirement.  For Depth First you
lost 2 points for not using the heuristic information that was given,
preventing the search from being fast.  For Iterative Deepening you
lost 3 points because you did not use the heuristic information and for
not going as fast as possible through the search space.)

```

#### Problem II. Rule-Based Systems (25 points)

Consider the following set of rules for determining the risk that a person has of suffering from hypertension.

• R1: IF salt-intake ?x high THEN risk ?x high

• R2: IF smokes ?x yes THEN risk ?x high

• R3: IF alcohol-consumption ?x heavy THEN risk ?x high

• R4: IF parent ?x ?y AND risk ?y high THEN risk ?x high

• R5: IF age ?x 18-24 AND risk ?x high THEN recommend ?x treatment
The working memory contains the following assertions:
• A1: parent mary bob
• A2: age mary 18-24
• A3: smokes bob yes
Use backward chaining to determine whether or not treatment is recommended in Mary's case (that is, recommend mary treatment). Construct a tree showing the steps followed by backward chaining and show when and how the working memory is updated during the depth 1st search. Your depth-1st search should explore the rules in the order in which they appear in the rule base. Show your work.

#### Problem III. Logic-Based Systems (25 points)

Consider the following set of axioms:
• Jack owns a dog
• A1: there-exists z [dog(z) & owns(jack,z)]
• Every dog owner is an animal lover.
• A2: forall x [there-exists y [dog(y) & owns(x,y)] -> animal-lover(x)]
• No animal lover kills an animal.
• A3: forall w forall s [animal-lover(w) & animal(s) -> !kills(w,s)]
• Either Jack or Curiosity killed the cat, whose name is Tuna.
• A4: kills(jack,tuna) || kills(curiosity,tuna)
• A5: cat(tuna)
• Every cat is an animal.
• A6: forall u [cat(u) -> animal(u)]
• Conclusion: Curiosity killed Tuna.
• C: kills(curiosity,tuna)
here:
• constants symbols: jack, curiosity, tuna.
• relation symbols: dog, owns, animal-lover, animal, kills, cat.
• variable symbols: s, u, w, x, y, z.
Prove the conclusion from the axioms by refutation using resolution:
• (8 points) Translate the axioms and the negation of the conclusion into clausal form. Show each step of the translation (remember that the order in which you apply the steps is crucial). To simplify your life, the translations of A1, and A2 into clausal form are already provided below. Note that in order to translate A1 into clausal form, a new constant called spot has been introduced in order to eliminate the existential quantifier.

1. A1.1: dog(spot)

2. A1.2: owns(jack,spot)

3. A2: !dog(y) || !owns(x,y) || animal-lover(x)

4. A3: !animal-lover(w) || !animal(s) || !kills(w,s)

5. A4: kills(jack,tuna) || kills(curiosity,tuna)

6. A5: cat(tuna)

7. A6: !cat(u) || animal(u)

8. !C: !kills(curiosity,tuna)

```

```

• (17 points) Apply resolution (state explicitly what clauses are resolved and which substitutions are made) until the empty clause is found.
```
!C:    !kills( curiosity, tuna )
A4:    kills( jack, tuna ) || kills( curiosity, tuna )

A7:    kills( jack, tuna)
A3:    !animal-lover( w ) || !animal( s ) || !kills ( w, s )

w <- jack
s <- tuna

A8:    !animal-lover( jack ) || !animal( tuna )
A6:    !cat( u ) || animal( u )

u <-tuna
A9:    !animal-lover( jack) || !cat( tuna )
A5:    cat( tuna )

A10:   !animal-lover( jack )
A3:    !Dog( y ) || !Owns( x, y ) || animal-lover( x )

A11:   !Dog( y ) || !Owns( jack, y)
A1.2:  Owns( jack, Spot )

A12:   !Dog( Spot )
A1.1:  Dog( Spot )

A13:

Success!

Hence Curiosity Killed the Cat!!!

```

#### Problem IV. Search (25 points)

Suppose that you need to find a path between S and G in the following graph. The number attached to each edge in the graph represents the COST of traversing the edge.

Assume also that the ESTIMATED distances to the goal are given by the following table:

 Node: S K Y A P V B G Estimated Distance to G: 10 4 8 2 4 4 2 0

For EACH of the following search methods list the nodes in the order in which they are EXPANDED by the search method while looking for a solution. Also, show the search tree as it is constructed by the search method. When everything else is equal, order the nodes in alphabetical order.

1. (7 points) Branch-and-Bound WITH Dynamic Programming
Branch and Bound works by expanding the head of the queue, and then sorting by least cost-so-far. Costs at nodes appear next to the letter. Dynamic Programming refers to the removal of nodes that are the same letter as another node but with a higher cost-so-far. These are marked by an X in the tree.

List of expanded nodes: S Y A K V P B G

Search Tree:

```

/ \
/   \
K-7    Y-2
X    /   \
/     \
A-4      K-6
/ |      |  \
/  |      |   \
K-9  V-6   A-11   P-11
X  /   \    X     X
/     \
B-9    P-7
|      |
|      |
G-11   K-12
X
```
2. (6 points) A*
A* works by expanding the head of the queue, and then sorting by least cost-so-far plus heuristic. Cost+Heuristic at nodes appears next to the letter.

List of expanded nodes: S Y A K V B G

Search Tree:

```
S
/ \
/   \
K-11   Y-10
/   \
/     \
A-6      K-10
/ |      |   \
/  |      |    \
K-13  V-10  A-13   P-15
/   \
/     \
B-11    P-11
|
|
G-11

```
3. (6 points) Greedy Search (= Best 1st Search)
Greedy Search works by expanding the head of the queue, and then sorting by heuristic. Heuristics at nodes appear next to the letter.

List of expanded nodes: S K A P V B G or S K A P V A B G

Search Tree(s):

```                           S               .                          S
/ \              .                         / \
/   \             .                        /   \
K-4    Y-8           .                     K-4    Y-8
/ | \                 .                    / | \
/  |  \                .                   /  |  \
A-2  Y-8  P-4             .                A-2  Y-8  P-4
/ |        |              .                / |        |
/  |        |              .               /  |        |
Y-8  V-4      V-4             .            Y-8  V-4      V-4
/   \                     .                         /   \
/     \                    .                        /     \
P-4    B-2                   .                      A-2    B-2

|                    .                       |      |
G-0                   .                      Y-8    G-0

```
4. (6 points) Hill-climbing
Hill Climbing works by expanding the head of the queue, sorting the children by heuristic, and placing those sorted children into the queue. Heuristics at nodes appear next to the letter.

List of expanded nodes: S K A V B G

Search Tree:

```                           S
/ \
/   \
K-4    Y-8
/ | \
/  |  \
A-2  Y-8  P-4
/ |
/  |

/   \
/     \
P-4    B-2
|
|
G-0

```

#### EXTRA CREDIT Problem. Planning (10 points)

Given
• an initial state,
• a desired goal state,
• a collection of operators to transform states into other states, each operator having preconditions and postconditions
Describe:
1. (2 points)Describe what a plan (to go from the initial state to the goal state) is.
```A plan is a (partially) ordered collection of operators that, when
applied in the order specified, tranform the initial state into
the goal state.

```
2. (8 points) Describe how to construct a plan.
Outline the overall process, explaining in particular (1)how the search for the plan is conducted, (2) when an operator is added to the plan, (3) what a threat is and how it is resolved, and (4) when the search ends.
```(1) A plan is constructed using "backward chaining"
starting from the goal state and finding operators
whose postconditions match the assertions in the
goal state, and then the process is applied recursively
to satisfy the preconditions of those operators.
(2) An operator is introduced when there is an assertion
in the goal state or a precondition in any of the
operators currently in the plan that is still not
satified by other operators in the plan or the assertions
in the initial state. If there are
several operators that can be introduced to satisfy
such assertion or precondition, then those operators
are explored in a depth-1st manner (with backtracking).
(3) When the postcondition of an operator 1 in the plan
matches/satisfies the precondition of another operator 2
in the plan, we say that operator 1 "establishes"
operator 2. A "threatening"  situation is present when
the postcondition of a third operator in the plan
invalidates the precondition of operator 2 that operator
1 has established.
A way to resolve this conflict is to add time constraints
to the plan, requiring that operators 1 and 2 be executed
before operator 3, or that operator 3 be executed before
operators 1 and 2. If both options are impossible to
satisfy, then the current branch of the search fails and
the whole process backtracks.
(4) The search for a plan ends successfully when all the
assertions in the goal state as well as all preconditions
of the operators in the plan are satisfied. The search for
a plan ends unsuccessfully when the search has backtracked
to the end and there are no more ways to combine the operators
to satisfy all conditions.
```