HW1: Search Solution

Description

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 _abovereturnd_eachbygraph_arrowsearch_.._ForWh_eachnhoosing_ofthean arbitrary_followingorder_graphofstate_searchxpansions_strategies,(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

3. Uniform cost search

   1. Greedy search using the instantaneous transition costs

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

1. 2. Depth rst search

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

6. 3. Breadth rst search

6. 3. Uniform cost search

6. 3. Greedy search with the heuristic values listed at each state

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

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. If_upshe_in“accel_therates”_secondagain,_squareshewill _downendup in_withthe fifth_avelocitysquaredown_of with_{1. If}a velocity_shethenof2. _\coasts”

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

_celerates”vlocities).She_again,wouldlike_sheto _willgetth_endreas_upquickly_{in the}aspossible_fth. _squareHowever, _downifshehas_withanon_a-zero_velocity at_of 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.

2