Title



CSC 447 :: MidTerm Study Sheet

In addition to what is below – look over examples of tests from previous semesters.

Topics, concepts, facts, ideas covered

Python

1 – in Python, write a recursive function to compute factorial

 

def fact(n):

    if n > 0:

        return n*fact(n-1)

    else:

        return 1

2 – let L be a list of integers; use map & lambda to write a line of code which produces a list of those integers squared.

 

>>> L = [3,44,5,66,31]

>>> map((lambda x: x*x),L)

[9, 1936, 25, 4356, 961]

>>>

3 – write the generator function gensym which yields a new, unique symbol each time it is invoked; show how it is set up and called.

 

>>> def gensym():

count = -1

while True:

count += 1

yield 'node'+str(count)

>>> g = gensym()

>>> g.next()

'node0'

>>> g.next()

'node1'

>>> 

4 – given, L, a list of pairs of integers, write a line of code to sort that list by the first elements of the list; then by the second elements.

 

>>> L.sort(sort1s)

>>> L

[[2, 3], [6, 1], [55, 77], [99, 44]]

>>> def sort2s(pair1,pair2):

return cmp(pair1[1],pair2[1])

>>> L.sort(sort2s)

>>> L

[[6, 1], [2, 3], [99, 44], [55, 77]]

>>>

5 – from the CDR project, write the function getDistances which takes a list of buildings as argument, opens a file containing a 2d matrix of distances and returns a dictionary object indexed by buildings and giving the distances between them.

 

def getDistances(bldgs):

dtable = open('distanceTable.txt','r')

dist = {}

for frm in bldgs:

dist[frm] = {}

rowList = readIntegers(dtable)

index = 0

for to in bldgs:

dist[frm][to] = rowList[index]

index += 1

return dist

>>> bldgs = readBuildings()

>>> dist = getDistances(bldgs)

>>> dist['OM']['LY']

31

>>> type(dist)

>>>

6 – write Python code to find the minimum & maximum item in a list and to obtain the sum of all elements of a list.

 

>>> L = [55,87,23,11,98,121,4]

>>> min(L)

4

>>> max(L)

121

>>> sum(L)

399

>>>

Myro

1 – what does the following Myro code do (approximately)?

 

forward(1, 1)

turnLeft(1, .3)

forward(1, 1)

turnLeft(1, .3)

forward(1, 1)

turnLeft(1, .3)

forward(1, 1)

turnLeft(1, .3)

 

go in a square

 

2 – write a Myro program to do a little dance routine

Here's an example:

 

def yomama(times):

for i in range(times):

forward(.5)

wait(.5)

backward(.5)

wait(.5)

stop()

def wigout(speed,waitt):

rotate(-speed)

wait(waitt)

rotate(speed)

wait(waitt)

stop()

def yowig(x,y,z):

yomama(x)

wigout(y,z)

yomama(x)

wigout(y,z)

beep(.5,400)

stop()

3 – write a line of code to have Myro give you a greeting

Here's an example:

speak('good morning')

4 – write Myro code to take a picture storing it in a variable; then show it. Take the picture first in color, then in grayscale.

 

>>> pColor = takePicture()

OR: pColor = takePicture("color")

>>> show(pColor)

>>> type(pColor)

 

>>> pGray = takePicture("gray")

>>> show(pGray)

5 – write Myro code to take a picture storing it in a variable; then show it and store the red, green, blue values of some pixel from that picture. Finally, save the picture on the hard drive for later use.

 

>>> pColor = takePicture()

>>> show(pColor)

 

>>> p00 = getPixel(pColor,0,0)

>>> p00

>>> type(p00)

>>> getRGB(p00)

(15, 12, 43)

>>> r,g,b = getRGB(p00)

>>> r

15

>>> g

12

>>> b

43

OR::

r,g,b = getRGB(getPixel(pColor,0,0)

savePicture(pColor, "savedPColor.jpg")

5 – write Myro code to retrieve a picture from the disk for processing. Assume that the function allReds returns a list of all R values in the picture. Write code to find the average value of the R component of the picture.

 

>>> p = makePicture("savedPColor.jpg")

>>> show(p)

rr = allReds(p)

avRed = sum(rr)/len(rr)

CDR Problem

Analysis of genPerms

– Big O of space

– Big O of time

– number of calls to function Perm

Exhaustive search solution of CDR

– basic algorithm

generate all permutations of tasks

compute total time for each permutation

identify optimal sequence of tasks

A* applied to CDR

– a heuristic function for A*

is the heuristic admissible?

– contents of a node

name

path

current dropoff location

deliveries (tasks) remaining

endpoint

g-value

h-value

f-value

– role of nodelist

store all unexpanded nodes

keep nodes ordered by f-value

– expanding a node

create children, one for each delivery remaining

for each child node created

move delivery chosen from deliveries remaining to path

compute g-value

(add cost of delivery to previous g-value)

compute h-value

compute f-value

remove expanded node from nodelist

add all children to nodelist, keeping list sorted by f-value

– recognizing solution

when node at head of nodelist has a completed path, that is a

solution

Note: completed path has all tasks completed & Dieter has

reached endpoint

No node remaining on nodelist could be a better solution, because heuristic is admissible

Improving A* applied to CDR

– compute an upper bound to final path cost

– when expanding, discard any child nodes with f-value greater than

upper bound

– upper bound algorithm

arrange dropoff and pickup points as 2d matrix

basic idea:: any solution must have exactly one entry from each

row and one from each column

choose the minimum value in the matrix

add that value to SUM

remove the row and the column in which it is found

continue this process until matrix is empty

– alternate upper bound algorithm

find maximum value in the matrix

choose the smallest value in either the row or the column of that value

AI History & Theory

Questions from previous tests & exams:

State space search:

(1-4) Identify these criteria for evaluating search strategies:

1. Is the strategy guaranteed to find a solution if there is one?

completeness

 

2. How long does it take to find a solution?

time complexity

 

3. How much memory does it need to do the search?

space complexity

 

4. If there are several solutions, does it find the best one?

optimality

 

(5-8) Identify the two basic categories of search.

5. Has no information about the search space.

uninformed search

 

6. also known as . . .

blind search

 

7. Makes use of information about the search space.

informed search

 

8. often also called . . .

heuristic search

 

(9-12) Identify the search strategies described below:

9. Tries successively deeper depth limits.

iterative deepening search

 

10. Finish one branch before starting on another.

depth-first search

 

11. All nodes at depth d are expanded before any nodes at depth d+1.

breadth-first search

 

12. Imposes cutoff on maximum depth of search.

depth-limited search

 

(13-32) Give the requested information about each search strategy listed below.

Depth-first search:

13. Complete?

no

 

14. Time complexity?

bm, where m is the maximum depth of the search tree

 

15. Space complexity?

bm, where m is the maximum depth of the search tree

 

16. Optimal?

no

 

Breadth-first search:

17. Complete?

yes

 

18. Time complexity?

bd+1, where d is the depth of the shallowest goal state

 

19. Space complexity?

bd+1, where d is the depth of the shallowest goal state

 

20. Optimal?

Yes, if path cost is a non-decreasing function of the depth of the node.

 

Bidirectional search:

21. Complete?

yes

 

22. Time complexity?

bd/2,where d is the depth of the shallowest goal state

 

23. Space complexity?

bd/2, where d is the depth of the shallowest goal state

 

24. Optimal?

Yes

 

 

Depth-limited search:

25. Complete?

Yes/no – only if d ≤ L

 

26. Time complexity?

bL, where L is the search depth limit

 

27. Space complexity?

bL, where L is the search depth limit

 

28. Optimal?

no

 

Iterative deepening search:

29. Complete?

yes

 

30. Time complexity?

bd, where d is the depth of the shallowest goal state

 

31. Space complexity?

bd, where d is the depth of the shallowest goal state

 

32. Optimal?

Yes, if path cost is a non-decreasing function of the depth of the node.

  

(33-37) Identify the basic components of a state space search node:

33. the current configuration in the state space

state

 

34. the steps taken to reach this state

the steps taken to reach this state

path

 

35. the value computed by the heuristic function; an estimate of the distance

remaining to the goal state

h

 

36. The cost of reaching this state

g

 

37. f

g + h

(38-44) Identify the following periods in the development of AI.

38. 1966-73: Problems encountered; simple approaches do not “scale up”

A dose of reality

 

40. 1995 - present :: Work on building complete agents, pulling together work from subareas.

Intelligent agents

 

39. 1952-69: Rapid development of ideas amid unbridled optimism.

Early enthusiasm; great expectations

 

40. 1986 - present :: Revival of McCulloch & Pitts’ model of computation.

Neural Networks again

 

41. 1956: Dartmouth Conference

Birth of AI

 

42. 1943-55: “Seeds” of ideas developed.

Gestation

 

40. 1987 - present :: Build on existing systems; base claims on rigorous theorems and/or hard experimental evidence

AI adopts scientific method

 

44. 2001-present: Apply machine learning methods to the "knowledge Bottleneck"

Availability of very large data sets

 

43. 1969-79: Wide spread use of expert systems.

Knowledge-based systems

 

44. 1980-present: Specialized A.I. hardware & software companies sprout.

The AI Industry

(45-48) Identify the approach to the study of A.I. named.

45. Rational agent approach

acting rationally

46. Turing Test approach

acting humanly

47. Laws of thought approach

thinking rationally

48. Cognitive modeling approach

thinking humanly

(49-50) Identify these events in the history of AI.

49. A report in Britain critical of AI which formed the basis for a decision by the British government to end support for AI research in all but two universities.

The Lighthill Report

50. A period of time when AI fell out of favor, especially with respect to funding agencies.

AI Winter

 

Short Answer Questions

72. A heuristic for A* is called admissible when . .

It never overestimate the distance to the goal

73. Given two heuristics, h1 and h2, we say h1 dominates h2 if . .

h1(n) ( h2(n) for all configurations/nodes n.

74. Give a cogent argument why OOP (number of tiles out of place) and manh (Manhattan distance) are admissible for the 8 puzzle.

OOP – if a tile is out of place, it must be moved. Therefore the number of steps to the goal can never be less than the number of tiles out of place.

manh – each out of place tile must travel the Manhattan distance to reach its goal position. Therefore the number of total steps can never be less than the sum of distances each of the tiles must travel.

75-75. Prove: manh dominates OOP.

Proof:

Since both sum a value obtained for each tile, all we need do is prove that for an arbitrary tile, t, manh(t) (OOP(t).

There are two cases:

1. t is already in the goal position

manh(t) = 0

OOP(t) = 0

So, manh(t) ( OOP(t)

2. t is not in the goal position

OOP(t) = 1

manh(t) ( 1, since t must travel some nonzero distance.

So, manh(t) ( OOP(t)

This proves that manh dominates OOP.

78-80. At the lines indicated by ** give the result of the execution of the sequence of entries to the Python shell.

>>> L1 =[1,2,3]

>>> L1.append(5)

>>> L1

**

>>> L2 = [6,7,8]

>>> L3 = L1 + L2

>>> L3

**

>>> L4 = L3.append(L2)

>>> L3

**

>>> 

ANSWER:

>>> L1 =[1,2,3]

>>> L1.append(5)

>>> L1

[1, 2, 3, 5]

>>> L2 = [6,7,8]

>>> L3 = L1 + L2

>>> L3

[1, 2, 3, 5, 6, 7, 8]

>>> L4 = L3.append(L2)

>>> L4

>>> L3

[1, 2, 3, 5, 6, 7, 8, [6, 7, 8]]

>>> 

>>> L1

[1, 2, 3, 5]

>>> L1 + 7

Traceback (most recent call last):

  File "", line 1, in

    L1 + 7

TypeError: can only concatenate list (not "int") to list

>>> 

 

81. Suppose we have the list, L

L = [[1,10,11],[2,5,19],[3,12,21]]

Write a function which, when used with sort will allow us to transform L into this list:

[[2, 5, 19], [1, 10, 11], [3, 12, 21]]

In other words to allow us to sort on the second element in each of the sublists of L.

>>> L = [[1,10,11],[2,5,19],[3,12,21]]

ANSWER:

>>> def cmp2nd(a,b):

        return cmp(a[1],b[1])

 

>>> L = [[1,10,11],[2,5,19],[3,12,21]]

>>> L.sort(cmp2nd)

>>> L

[[2, 5, 19], [1, 10, 11], [3, 12, 21]]

>>> 

 

86-90. Compare A* search with respect to the 4 evaluation criteria – completeness, optimality, space complexity and time complexity – to depth-first and breadth-first search. Give justification for your analysis.

completeness – yes

optimality – yes

space complexity – more than depth-first, because must store a wider swath than just the direct path; but less than breadth-first, since as you go deeper the swath gets more narrow & never gets wide enough to encompass all nodes at all levels higher than d.

time complexity – less than both depth-first and breadth-first, because less nodes are considered and expanded.

Additional factor – the amount by which it is better depends on how good the heuristic is. In worst case, A* degenerates to breadth-first.

More formally{This discussion of #86-90 will not be on the midterm}:

Let h0 be the null heuristic, defined as follows:

h0(n) = 0, ∀n in the A* search tree.***

In other words, this heuristic gives us no information, so we are back to the blind search situation.

And let hcb be the crystal ball heuristic, defined as follows:

hcb(n) = s-dist(n), ∀n in the A* search tree,

where s-dist(n) is the actual distance from node n to the goal node.

In other words, this heuristic has perfect knowledge of the search space.

And let ha be any generic admissible heuristic.

Then,

h0(n) ( ha(n) ( hcb(n), ∀n in the A* search tree.

In other words, being admissible ha can never overestimate the distance to the goal. Hence:

ha(n) ( hcb(n)

And, as stated in Russell and Norvig, A* only works in a state space where there is never a negative cost for an action. Hence:

h0(n) ( ha(n)

We now explore each of these cases in turn. Suppose,

ha(n) = h0(n)

Then A* degenerates to breadth-first search, since there is no differentiation between nodes. We wind up expanding every node a one level, and then go on to expand all the nodes at the next level, and so on. In this case, as with breadth-first search, both time and space complexity of A* is bd+1.

On the other hand, suppose,

ha(n) = hcb(n)

Then, at every level, A* chooses for expansion that node from the Waiting List which is on the shortest path. Since, the process of expansion produces all the children of the node being expanded, the set of nodes produced is the nodes on the shortest path along with all of their siblings. Thus, both time and space complexity are bd. It is important to note that the siblings of the node on the shortest path are never expanded if, in case of a tie with respect to f-value, we always choose the most recently produced node.

This is summarized in the table below:

| |A* – best case |Depth 1st |A* – worst case |Breadth 1st |

| O(time) | bd | bm | bd+1 | bd+1 |

| O(space) | bd | bm | bd+1 | bd+1 |

| Complete | Yes | No | Yes | Yes |

| Optimal | Yes | No | Yes | Yes |

Thus, just as breadth first is better than depth first in terms of time, A* is also – even in the worst case scenario. And, although space usage depends on the merit of the heuristic, it can in some cases be an improvement over depth first search. With respect to breadth first search, A* can be no worse in both space and time and – as long as the heuristic yields even a modicum of useful information – A* is better.

Or, put in terms of comparison – on the average:

O(time):: A*b < A*w/Brd < Dpth

O(space):: A*b < Dpth < A*w/Brdt

where,

A*b = A*-best

A*w/Brd = A*-worst, which is same as Breadth-1st

The reason why A* can be worse than depth first in terms of space is explored in #EC-5.

***Strictly speaking, heuristic functions are not applied to nodes but to the states of nodes. So we should write h(ns), where ns is the state of node n. For simplicity, though, we will write h(n).

  

Beginnings of A.I.:

 

1. The beginning of A.I. is widely held to be the _____ which took place in 1956.

Dartmouth Conference

  

2-4. Among those attending the conference were A.I. pioneers _____, _____, and _____.

John McCarthy

Herbert Simon

Allen Newell

  

5. Additionally, in attendance was _____, the father of information theory, who had written a paper on computer chess.

Claude Shannon

  

6. Two conference attendees discussed their _____, a program for proving theorems from Principia Mathematica.

Logic Theorist

  

7. The following year they introduced their GPS or _____, a generalized state space search mechanism.

General Problem Solver

  

8. At Stanford Research Institute this was transformed into _____, a robot planning program used in Shakey.

STRIPS

  

9. After the initial successes of A.I. came the period known as the _____ when funding for A.I. research was hard to come by.

A.I. Winter

 

Theoretical basis & issues:

 

10. A.I. has historically been at the center of computing theory. The _____, a theoretical machine described by Alan Turing, is widely held as the theoretical model of computation.

Turing Machine

  

11. After two other models of computation were shown to be logically equivalent the _____ proposed that whatever is computable is computable by these.

Church-Turing Thesis

  

12. One of these models, the _____, is found in the logical framework of forward chaining expert systems.

Post production system

  

13-14. The other, the _____, proposed by Alonzo Church formed the basis of the programming language _____.

lambda calculus

Lisp

  

Theoretical issues – again:

 

57-58. Brachman and Levesque showed that in the design of A.I. systems there is a fundamental tradeoff between _____ and _____.

expressiveness

tractability

 

59. _____ is the process of complex pattern formation from more basic constituent parts or behaviors.

emergence

 

60. Boids, developed by Craig Reynolds in 1986, is an artificial life program, simulating the _____.

flocking behavior or birds

 

61-63. The behavior-based (BB) paradigm in A.I. (and especially in robotics) was proposed because reactive systems were found to be too _____, deliberative systems too _____, and hybrid systems required _____ among components.

inflexible

slow and cumbersome

complex interactions

 

64. The BB paradigm was inspired by biological systems which achieve complexity with _____ components.

simple and consistent

 

Robot control architectures:

 

65-68. In robotics a control architecture provides guiding principles and constraints for organizing a robot’s control system. List the four main control architectures.

deliberative

reactive

hybrid

behavior-based

69. _____ is the scientific study of animal behaviors.

ethology

 

70-71. Two of the pioneers in this field are:

Lorenz, Tinbergen

 

72-73. And two of the pioneers in applying biological studies of animal behavior to robotics are:

Moravec, Arbib

 

74. _____ is a specific stimulus which triggers a stereotypical pattern of action.

an innate releasing mechanism

 

75-76. Perception serves two functions with respect to action.  It serves to _____ and then to ____ by providing information necessary to accomplish it.

release the behavior

guide the behavior

 

77. A _____ is a generic template for doing some activity.

schema

 

78. It consists of _____ to act and/or perceive . .

knowledge of how

 

79. and of the _____ for accomplishing the activity.

computational process

 

80. The subsumption architecture of Rodney Brooks solves the _____ by eliminating the need to model the world.

frame problem

 

81. Within this architecture behaviors are arranged in _____.

layers of competence

 

Enhanced True/False

 

(82-94) For each statement, indicate whether it is true or false.  Correct those that are false to make them true.

 

92. When using depth-limited search, the first solution encountered is guaranteed to be optimal.

False: There may be a better solution on a branch yet to be explored.

 

93. Depth limited search has an inefficiency in that on each iteration the search space covered on the previous iteration is covered again.

False: Iterative deepening

Short Answer Questions

 

State space search:

 

95. Describe the Manhattan distance heuristic for the 8 Puzzle.

h(x) = number of moves each tile must make to reach its proper place

  

96-97. In A* search all active nodes are kept in a ordered list that is ordered by a function known as f(x). How is f(x) computed? How are the components of f(x) computed?

f(x) = g(x) + h(x)

g(x) is the cost of the path to this point

h(x) is the value given by the heuristic function

 

98. A key requirement of A* is that the heuristic function be admissible. When is a heuristic function admissible?

When it never overestimates the cost of reaching the goal

 

99. We found that the Manhattan heuristic dominates the OOP heuristic. What does that mean?

For all configurations, c, Manh(c) ( OOP(c).

 

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download