ࡱ> oqn;@ 51bjbjkk (\ (;*******>111812>G22222222????E@C\G$IRKG*17221717G**22G<<<17*2*2?<17?<R<>**>22 -_1C8b>Q>G0G>}L:}L>>>****}L*><2H3<45222GG>>.1<">>1Problem Solving And Skill Problem Solving Knowledge-Based Behavior Declarative Knowledge (Facts, Episodic Memory) Skill Acquisition Transition from Knowledge-Based to Skill-based Procedural Knowledge How do we use knowledge/memory to achieve our goals? Bridge from Memory to Problem Solving and Skill Search Problem Solving Important Component of Learning Planning Future Courses of Action Scientific Discovery Modern Research On Problem Solving Artificial Intelligence Problem Solving as Search Herbert Simon and Alan Newell A Theory of Action Goals: What We Want to Happen The Central Role of Goals in Problem Solving Execution: What We Do To The World Memory for the Required Actions Possibility of Inferring Them Evaluation Comparing What Happened With What We Wanted To Happen The Roles of Attention, Comprehension, and Memory The World Problem Solving Fundamental Part of Intelligent Behavior When ever we dont know how to reach a goal Finding a lost article Homework problems Planning for a day, life, etc. Learning new skills Scientific discovery Creativity Many test of intelligence are problem-solving tasks Professions Outline of Lectures (1) Understanding the problem (2) Problem solving-methods (3) Why problem solving is hard Types of Problems Used in Studies of Problem Solving Insight Problems Two String Problem Candle Stick Problem One critical step, the insight Gestalt Psychologists Intermediate steps hidden Puzzles Water Jug Problems River Crossing Problems Tower of Hanio Limited background knowledge Visible intermediate steps Physics, Algebra, Geometry, etc. Problems Background knowledge required Visible intermediate steps Design Problems Research Methods Just Record Success or Failure Not very useful Need to try to make intermediate steps visible Record Visible Intermediate Steps Number of steps, error, etc. time to solution Verbal Protocols! Think aloud Computer Simulations Incorporate theory into program Compare behavior of program to subjects Artificial Intelligence Branch of computer science Famous Programs General Problem Solver (GPS) Deep Blue Water Jug Problems and Other Puzzles? Why use such tasks to study problem solving? Can by solved by novices History Can manipulate problem structure to test theories Detours Why build computer simulation models? Make sure that the theory actually works Compute predictions to compare with human data Atwood and Polson (1976) Theory Three Stage Move Selection Process 1. Pick moves that lead to states that are similar to the goal 2. New moves (Use of LTM) 3. Best move or random (STM limits) Memory Very simplified model Water Jugs Figure showing (8,5,3) problem Test of means-ends assumption (8,5,3) vs (24,21,3) Goodness of fit Observed and Predicted Means and Standard Deviations (8, 5, 3) Observed Predicted Mean 24.90 23.69 StD 14.75 15.31 (24, 21, 3) Observed Predicted Mean 12.03 11.84 StD 7.44 6.66 Task Environments (Kinds of Problem Solving Tasks) Closed Problems Specific Goal Well Defined Moves Laboratory and School Tasks Puzzles Mathematics and Physics Problems Games Open Problems Poorly Specific Goal Ill Defined Moves Real World Problems Design Real Science Plan a happy life Solve the population problem Major Parts of Problem Solving Task 1) Finding the problem! 2) Understanding the problem! What is the goal? (Goal State) What is given? (Start State) What can be done? (Rules, Actions, Moves, Operations) Can the problem be broken up into simpler problems? Problem Solving as Understanding 3) Solving the problem! Problem Spaces Search! Search Methods (Heuristics) Problem Solving as Search Understanding is Hard The Right Representation is Hard to Find Mutilated-checkerboard The Two String Problem The Candle Problem Word Problems Students can easily perform required manipulations Cannot build correct problem representation Mary is 10 years younger than twice Susans age. Five years from now, Mary will be 8 years older than Susans age at that time. How old are Mary and Susan? Word Arithmetic Problems for 1st and 2nd Graders Sets: Whole-Set, Part-Set-1, Part-Set-2 There are 5 birds and 3 worms. How many more birds are there than worms? There are 5 birds and 3 worms. How many birds will not get a worm? Search is Hard!!! Problem Solution: Find path from start state to goal state that satisfies the rules VERY Large Number of Possible Paths Example A Problem That Takes 10 Moves to Solve 10 Different Moves From Each State 10,000,000,000 Possible Paths Number of Possible Games of Chess: 10 Followed by 40 Zeros Search Methods (Problem Solving Approaches) Generate and Test (Trial and Error) Difference Reduction-Similarity Means-Ends Analysis Simple Puzzles High Schools Math and Science Problems Computer Chess Scientific Discovery Problem Solving As Search Understanding Before Search Understand What Goal Is Know All of Moves Know About Detours Search Methods Generate and Test (Trial and Error) Difference Reduction-Similarity Working Backwards Means-Ends Analysis Simple Puzzles High Schools Math and Science Problems Computer Chess Scientific Discovery Search is Guided By Goals Goals Something Person Is Trying to Accomplish Examples Solve Puzzle Record TV Program Using VCR Write Paper Using Work Processor Win Game Design Beautiful House That Does Not Cost To Much Behavior is Guided by Goals Solve Hard Problems by Breaking Down into Simpler Problems Subgoal Decomposition Focused On Trying to Discover Correct Sequence of Moves Generate And Test Problem solvers adhering to the generate-and-test paradigm use two basic modules. > One module, the generator, enumerates possible solutions. > The second, the tester, evaluates each proposed solutions, either accepting or rejecting that solution. All Depends on Properties of Generator A powerful intelligent Generator will only produce a few "good" solutions including the correct one. Evolution is an example of Generate-and-Test All controversies about Darwin and the application of evolutionary ideas focus on the claim that the generator is NOT intelligent. Blind trial and error Difference Reduction-Similarity Select moves by comparing consequences of each move from the current state with goal. Pick move that leads to state that is "closer" (more similar to ) the goal. Measure difference between current situation and goal Pick more that you think will lead you closer to the goal Water Jug Problems Atwood and Polson (1976) Learning to use computers, phone mail, and other complex systems. The Cognitive Walkthrough (Wharton, Lewis, Rieman, & Polson) Label following Find information on the Web The Scent of Information Hill Climbing Working Backwards Geometry Novices Solving Physics Problems Planning problems Paint the ladder and ceiling green Define new subgoals Monkey and the Bananas Trivial (for humans) Huge search space Important Problem in the Early History of AI Means-Ends Analysis General Problem Solver Newell, Shaw, and Simon (1968) Difference Reduction Several Kinds of Differences Between Goal and Current State Ends (goals and subgoals) Set Up Goals and Subgoals to Reduce Differences Means (Operators) Operators Effect Some Differences and Not Others Table of Connections Examples Tower of Hanoi Algebra Monkey and Bananas Top Goal = (Transform the Initial-Object into the Desired-Object) Initial-Object = (Monkeys-Place = Place-1, Boxs-Place = Place-2, Contents-of-Monkeys-Hand = Empty) Desired-Object = (Monkeys-Place = On-Box, Boxs-Place = Under-Bananas, Contents-of-Monkeys-Hand = Bananas) Operators Walk, Move-Box, Climb, Get-Bananas Preconditions Difference Ordering Table of Connections Monkey-PlaceBox-PlaceMonkey-HandWalkXMove-BoxXXClimbXGet-BananasXTrace of GPS Solving Problem 1 Transform Initial-Obj into Desired-Obj 2 Reduce Contents-of-Monkeys Hand Diff On Initial-Obj 3 Apply Get-Bananas on Initial-Obj 4 Reduce Location-of-Box Diff On Initial-Obj 5 Apply Move-Box to Under-Bananas On Initial-Obj 6 Reduce Location-of-Monkey Diff On Initial-Obj 7 Apply Monkey Walk to Location of Box on Initial-Obj (Monkeys-Place = Place-2, Boxs-Place = Place-2, Contents-of-Monkeys-Hand = Empty) 8 Apply Move-Box to Under-Bananas (Monkeys-Place = Under-Bananas, Boxs-Place = Under-Bananas, Contents-of-Monkeys-Hand = Empty) 9 Apply Get-Bananas to Current-Obj 10 Reduce Location-of-Monkey Diff 11 Apply Climb to Current-Obj 12 Apply Get-Bananas to Current-Obj 13 Transform Initial-Obj into Desired-Obj Simple Algebra Problems Problem: Solve ax - b = x for x Goal State: Term x on the left side of the equation; all other terms on the right Possible Operators Add x to both sides Subtract x from both sides Multiply x on both sides Divide through x on both sides Add a to both sides Subtract a from both sides Multiply a on both sides Divide through a on both sides Add b to both sides Subtract b from both sides Multiply b on both sides Divide through b on both sides Factor something on one side ... Means-Ends Applied to Simple Algebra Problems Problem: Solve ax - b = x for x Goal State: Term x on the left side of the equation; all other terms on the right 1. Current state: ax - b = x Differences: a on left, b on left, x on right. Apply operator: Add b to both sides 2. Current state: ax = x + b Differences: a on left, x on right. Apply operator: Subtract x from both sides 3. Current state: ax - x = b Differences: a on left, x on left twice. Apply operator: Factor x on left 4. Current state: x(a - 1) = b Differences: (a-1) on left. Apply operator: Divide both sides by (a-1). 5. Current state: x = b/(a-1) Differences: None Factors That Effect Problem Solving When Means-Ends Does Not Work Detours When the label following strategy fails Mental Set Transfer Doing it the hard way(?) Functional Fixedness Insight Problems Incubation Expertise Experts Build Better Representations Schemata, Problem types Elaborating on Initial States (Planning) Programming Writing Soviet political economy (Voss et al, 1983) Experts are More Effective Searchers Metacognitive Skills Allocating Time to Planning Error Recovery Control of Search MEMORY Chess Players (De Groot, 1966) Many other domains Remembering where you have been!!! Problem Solving Lectures Cognitive Psychology Page ]v 7 N  U&'rsM[ \wkUxAJ~) a!! ""d"Y&|&&)********** ++'+)+C+F+c+f+x+y+++++++++ h5CJ h5CJ h6h& h6h5CJ0aJ0hR`h)h?/ h>*hhL*Fw 9 B i r  / 7 N {  gdgdgd041 O Y Z j   0 ; o { " 3 G ] } gd?/gd?/gdgd .Xw6ew*IUgd)gd)gd?/U{)RAH^i4LkgdR`gdR`gdR`gdR`&GM[p9gdgdgdgdgdgdR`9Z}  %5>[\wx =j  ;cX|()Uy!=Ugzgdgdgd)8Mgm$@{.kb^gdgdgd h^h`gdgdgdgdgdb ) * J &!a!t!!!"";"U"d"v""""""##gd0]0gd&gd`gd^gdgd#+#Y#Z#n#####$C$U$$$$$$$%}%%%!&/&C&X&Y&f&p&$Ifgdp&|&}&&&&& $$Ifa$nkd$$IfP4\@$$ $ $ $ 4 Paf4$If&&&&&& $$Ifa$$Ifnkd~$$IfP4\@$$ $ $ $ 4 Paf4&&&&&& $$Ifa$$Ifnkd$$IfP4\@$$ $ $ $ 4 Paf4&&&&&& $$Ifa$$Ifnkdz$$IfP4\@$$ $ $ $ 4 Paf4&&&&0'U''''6(((6)])||||r|||||| ]^ |]|^ |]|^nkd$$IfP4\@$$ $ $ $ 4 Paf4 ])))))*8****** ++:+T+t++++++,/,P,,,0]0^ 0]0^+/,.00111314151hjheUhe h5CJ h,,-2-W----- .).V.t......//+/@/Q/\/]/g/h///////00A0B0W0u0000000(1)1213141511$1$1$$a$gd&0 P<0/ =!"#$%|$$If!vh5$ 5$ 5$ 5$ #v$ :V P45$ / 44 Pf4|$$If!vh5$ 5$ 5$ 5$ #v$ :V P45$ / 44 Pf4|$$If!vh5$ 5$ 5$ 5$ #v$ :V P45$ / 44 Pf4|$$If!vh5$ 5$ 5$ 5$ #v$ :V P45$ / 44 Pf4|$$If!vh5$ 5$ 5$ 5$ #v$ :V P45$ / 44 Pf4h@h NormalH]^`H$CJ$OJQJ_HkH'mH nHsH tHDA@D Default Paragraph FontVi@V  Table Normal :V 44 la (k@(No List 4 @4 Footer  !4@4 Header  !>>@> Title$$$a$5CJ08O"8 subtitle $hCJ$>O2> Level 1$^`>OB> Level 2$^`dod TitleS.$$$]^`a$CJ8OJPJQJ5) \ *Fw9Bir/7N{OYZj0;o{"3G]}.Xw6ew*IU{ ) R   A H ^ i   4 L k   & G M [ p     9 Z }  %5>[\wx =j  ;cX|()Uy!=Ugz)8Mgm$@{.kb)*J&at;Udv+YZnCU}!/CXYfp|}0U6 6!]!!!!!"8"""""" ##:#T#t######$/$P$$$$%2%W%%%%% &)&V&t&&&&&&''+'@'Q'\']'g'h''''''((A(B(W(u(((((((()))2)3)6)00000p0000000000000@+0@0@-0@-0@0@-0@-0@-0@0@-0@-0@0]y0000p0p0p0p0p0p00p0p0p000000p0p0p0p0p0p0p00p0p0p0p0p00p000p0p0p0p0p0p0p00p0p00p0p0p0p0p00000p000000000p0000*00000000p000000000000000000000000p0p0p0p0p0p00p0p0p0p0p0p000p0p0p00p0p0p0p0p0p0p0p0p00p0p00p00p0p0p0p0p0p0p0p0p00p0p00p0p0p00p0p0p0p0p0p0p0000p0p0p0000000000000000000000000p0p0p0p0p0p00p00p0p00p0p0p0p0p0p0p00p0p0*0p0p0p0p0p0p0p00p0p0000p0p0p0p0p0p0p00( 0( 0( 0( 0, 0( 0( 0( 0( 0, 0( 0( 0( 0( 0, 0( 0( 0( 0( 0, 0( 0( 0( 0( 0, 00p0p0p0p0p0p0p00p000p0000*0p0p0p0p0p0p00p0p00p0p0p0p00000p0p0p0p0p0p0p00p0p000p0p0p0p00p0p0p0p0p0p0p00p0p0*0p0p0p0p0p0p0p00p0p000p00000@0]y00@0]y000\00:::=+51+ U9b#p&&&&&]),/51 !"#$%&'()*,-41T.$xU.uV. yW.xX.<& Y.xZ.x[.4u\.:].$ ^.o_.!`.oa.xb.tzc.ud.dqe.of.ug.,yh.Loi.!j.N N S p p v 8"8"="P$P$U$6)     R X X u { { <"B"B"T$Z$Z$6)  8 *urn:schemas-microsoft-com:office:smarttagsCity=*urn:schemas-microsoft-com:office:smarttags PlaceType=*urn:schemas-microsoft-com:office:smarttags PlaceName9*urn:schemas-microsoft-com:office:smarttagsplace   : = {,/QT2 5 Y!\!!!!!!!!!B(O((((3)6)?F.NUzz ~ : = /5^`06`d-#$!#vx!!"""""""" ##'#.#C#H#c#h#x#}#########$$@%A%%%%&m&o&$'('(3)6)333333333333333333333333333333333333333333333333Oj"34GN]^}XYwx6evx+,J : l G M  !=,*;<UVcY!"(')+)1)3)6)(3)6)Peter G. PolsonPeter G. PolsonPeter G. PolsonPeter G. PolsonPeter G. PolsonPeter G. PolsonPeter G. Polson Peter PolsonPeter G. PolsonPeter G Polson e?/c;)&]6R`Zjl !M@*+Y/CXYfp|}(6)E0@HP LaserJet 2100 Series PSNe00:winspoolHP LaserJet 2100 Series PSHP LaserJet 2100 Series PSS odLetPRIV0''''\KhC;g HP LaserJet 2100 Series PSS odLetPRIV0''''\KhC;g p/5)@UnknownGz Times New Roman5Symbol3& z ArialY New YorkTimes New Roman;" Helvetica9Palatino3Times"AZZE"J"J!;24(( 3q;H(??/Problem Solving And SkillPeter G. PolsonPeter G PolsonOh+'0|  8 D P\dltProblem Solving And Skill.robPeter G. Polsonete Normal.dotlPeter G Polson7teMicrosoft Word 10.0@ޡ @] _@tV_"՜.+,0 hp  University of ColoradoJ(; Problem Solving And Skill Title  !"#$%&'()*+,-.012345689:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]_`abcdeghijklmpRoot Entry FPq/_rData /1Table7}LWordDocument(\SummaryInformation(^DocumentSummaryInformation8fCompObjj  FMicrosoft Word Document MSWordDocWord.Document.89q