HW1: Search Solution

Alice the agent really wants to go skiing right after AI class is over. She starts 1 Graph Search

in the lecture hall (the \start" state below) and wants to make it to Alta (the

\goal"Alicethe state)agentreallyas wantssoontoasgo possibleskiingright. afterThereAIclassareis severalover.She startspossibleinthe pathslecturehallshe(thecan“start”
state below) and wants to make it to Alta (the “goal” state) as soon as possible. There are several possible
take denoted in the graph below:
paths she can take denoted in the graph below:


Start
2
B
1
D


h=3

h=1





3

2
4
5





A

C
1
Goal
h=2

h=1









3



The available actions at each state are denoted by arrows with a path cost label above each arrow. For each
The available actions at each state are denoted by arrows with a path cost la-
of the following graph search s rategies, figure out the order in which states are expanded as well as the
belpath abovereturndeachbygrapharrowsearch..ForWheachnhoosingofthean arbitraryfollowingordergraphofstatesearchxpansionsstrategies,(tobreakties),gurese an alphabetical ordering. Remember that in graph search, states are expanded only once.
out the order in which states are expanded as well as the path returned by graph search. When choosing an arbitrary order of state expansions (to break
1. Greedy search
ties), use an alphabetical ordering. Remember that in graph search, states are
2. Depth first search
expanded only once.
    3. Breadth first search

    4. Uniform cost search
        1. Greedy search using the instantaneous transition costs
    5. Greedy search with the heuristic values listed at each state
        2. Depth  rst search
    6. A* search with the heuristic values listed at each state

        3. Breadth  rst search

        4. Uniform cost search

        5. Greedy search with the heuristic values listed at each state

        6. A* search with the heuristic values listed at each state





1









1
    • Downhill Skiing

HW1: Search
2

After getting to Alta, Alice takes the lift up to the top of the mountain. The

run is really rocky, so her only option is to go straight downhill. She begins 2 Downhill Skiing

with a velocity of 0 and can safely maintain a maximum velocity of V . At any state, she has three actions she can take: accelerate, decelerate or coast. If the
After getting to Alta, Alice takes the lift up to the top of the mountain. The run is really rocky, so her only
accelerates, her velocity increases by 1; if she decelerates, it decreases by 1; if
option is to go straight downhill. She begins with a velocity of 0 and can safely maintain a maximum velocity
sheofV . coasts,Atanystate,itstaysshehasthethreesameactions.Aftershecanhertake:velocityaccelerate,isdecelerateadjustedor coastbyher.If theaction,accelerates,she
her velocity increases by 1; if she decelerates, it decreases by 1; if she coasts, it stays the same. After her
moves downhill an equal number of squares to her current velocity.
velocity is adjusted by her action, she moves downhill an equal number of squares to her current velocity.











G

Consider the above figure. If Alice’s first action is “accelerate” then she will end up in the second square
Consider the above    gure. If Alice’s    rst action is \accelerate" then she will
down with a velocity of 1. If she then “coasts” then she will end up in the third square down with a velocity endof1. Ifupshein“acceltherates”secondagain,squareshewill downendup inwiththe fifthavelocitysquaredownof with1. Ifa velocityshethenof2. \coasts"

thenAlice’s shegoal iswilltorendachtheupchairin thelift(markedthird “G”)squarewith downavelocitywithofzeroa. velocity(N,Alice ofcannot1. Ifhaveshen gative\ac-

celerates"vlocities).Sheagain,wouldlikesheto willgetthendreasupquicklyin theaspossiblefth. squareHowever, downifshehaswithanona-zerovelocity atof the goal, she skies into the parking lot and destroys her skis.
2.

1. If the mountain is N units tall (eg., it is N = 6 units tall in the figure), what is the size of the state
Alice’s goal is to reach the chair lift (marked \G") with a velocity of zero.
space? Justify your answer. (You may ignore “unreachable” states.) What are the start/goal states?
(No, Alice cannot have negative velocities). She would like to get there as
2. Give an example of a state that is not reachable. Suppose that Alice cannot coast (she must either
quickly as possible. However, if she has a non-zero velocity at the goal, she
accelerate or decelerate): this yeilds more unreachable states; give an example of one and justify it.
skies into the parking lot and destroys her skis.
3. Is Alice’s current elevation (i.e., distance from the chair lift) an admissible heuristic? Why or why not?

4. State and justify a non-trivial, admissible heuristic for this problem which is not current elevation.

1. If the mountain is N units tall (eg., it is N = 6 units tall in the gure), what is the size of the state space? Justify your answer. (You may ig-nore \unreachable" states.) What are the start/goal states?


2. Give an example of a state that is not reachable. Suppose that Alice cannot coast (she must either accelerate or decelerate): does this yield more unreachable states? If so, give an example of one and justify your answer either way.

3. Is Alice’s current elevation (i.e., distance from the chair lift) an admissi-ble heuristic? Why or why not?

4. State and justify a non-trivial, admissible heuristic for this problem which is not current elevation.