New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Sam Rau
Sam Rau
GPA 3.5

Jae Oh

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Jae Oh
Class Notes
25 ?




Popular in Course

Popular in Computer & Information Science

This 52 page Class Notes was uploaded by Sam Rau on Wednesday October 21, 2015. The Class Notes belongs to CIS 467 at Syracuse University taught by Jae Oh in Fall. Since its upload, it has received 44 views. For similar materials see /class/225596/cis-467-syracuse-university in Computer & Information Science at Syracuse University.

Popular in Computer & Information Science


Reviews for Intro


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/21/15
PHILOSOPHICAL FOUNDATIONS Modi ed for Fall 2006 Outline ltgt Intelligence and Mind ltgt Weak AI Position ltgt Strong AI Position O The Chinese Room Argument O The Brain Prosthesis Experiment Modi ed for Fall 2006 2 Weak AI Position It is possible to make machines which would act as if they were intelligent and conscious ltgt Turing Test ltgt Ultimately to be decided by experiments ltgt Who is to blame if a machine makes a mistake Modi ed for Fall 2006 Strong AI Position It is possible to make machines which would be intelligent and conscious ltgt But how do we decide this How do you know you are conscious How do you know other people are conscious Chinese Room Searle Brain Prosthesis ltgtltgtltgtltgtltgt lssues Can you turn off a conscious machine What can you do with Data or HAL Modi ed for Fall 2006 4 The Chinese Room John Searle O A human who speaks only English is in a closed room CPU ltgt There is a slot in the wall through which he is passed pieces of paper with Chinese symbol on them lO ltgt He has access to a rule book written in English Computer Program ltgt Stacks of paper some blank and some with Chinese symbols on them Storage ltgt He looks up the incoming symbolss in the rule book and uses the relevant rules for matching symbols ltgt Ultimately he transcribes Chinese symbols on a blank sheet and passes it to the outside world ltgt If asked in Chinese Do you understand Chinese the room replies Of course in Chinese Modi ed for Fall 2006 5 ltgt Note From outside the input Chinese the output Chinese Modi ed for Fall 2006 The Chinese Room John Searle ltgt Searle39s argument 1 The person does not understand Chinese 2 The rule book and stacks of paper do not understand Chinese 3 If system is constructed from the components that can39t understand Chi nese then the system as a whole can39t understand Chinese 4 Therefore the room doesn39t understand Chinese 5 Therefore running the right program does not guarantee understanding It may pass Turning test Modi ed for Fall 2006 7 The Chinese Room Continued ltgt Counterargument Thinking too small Consciousness is an emergent property of the system as a whole ltgt Searle The only physical medium that can support consciousness is neural Modi ed for Fall 2006 Brain Prosthesis Experiment Hans Moravec ltgt Suppose we have the technology of Star Trek Understand the lO behavior and connectivity of all neurons in the brain Can build microscopic electronic device that can mimic this behavior and can be used to replace neurons in the brain Borg Can replace individual neurons with the devices without interrupting the operation of the brain ltgt Gradually replace all neurons with devices and then reverse the process Modi ed for Fall 2006 9 Brain Prosthesis Experiment Hans Moravec ltgt By definition the external behavior will not be changed ltgt What about the conscious experience of the subject 0 Moravec is convinced that consciousness would be unaffected o Searle believes that consciousness would vanish 0 What39s your opinion Modi ed for Fall 2006 10 Semester Summary ltgt Al researchers try to solve very difficult problems Time and space complexities are important issues O The grand challenge is of course building a truly intelligent system ltgt Until we get there we should concentrate on things that are possible and incrementally improve them Modi ed for Fall 2006 PLANNING CHAPTER 1 1 Modi ed for Fall 2006 Chapter 11 1 II Outline ltgt Search vs Planning ltgt Can use Situation Calculus for Planning ltgt STRIPS language for planner ltgt Partialorder planning Modi ed for Fall 2006 Chapter 11 2 H Search vs planning Consider the task get millt2 bananas and a cordless drill Can we use standard search algorithms Talk to Parrot Go To Pet Store Buy a Dog Go To School Go To Class Cl gt Go To Supermarket Go To Sleep Read A Book a Sit in Chair Afterthe fact heuristicgoal test inadequate Modi ed for Fall 2006 Chapter 11 3 Search vs planning contd Planning systems do the following 1 open up action and goal representation to allow intelligent selection Ex If we know the goal is HaueltMilk and BugMilk leads to HaveltMilk then the agent knows that our plan should include BugMilk 2 divideandconquer by subgoaling 3 relax requirement for sequential construction of solutions Modi ed for Fall 2006 Chapter 11 4 Planning in situation calculus PlanResultp s is the situation resulting from executing p in s PlanResultH s s PlanResultaipl s PlanResultp Resulta 3 Initial state AtH0me So HaueMz lk So Actions as Successor State axioms HaveltMilk Resulta 3 ltgt a BuyMilkAtSupermarket sVHaveMilk sa y DropltMilk Query 8 PlanResultp So AtH0me s HaveltMilk s Solution 10 G0Supermarket BugMilk BugBananas G0HWS Modi ed for Fall 2006 Chapter 11 5 How can we make planning practical ltgt Branching factor is a big problem ltgt Restrict language that define the problem If we want shopping plan make our language to represent that no more ltgt Use special purpose algorithm rather than general purpose theorem prover Modi ed for Fall 2006 Chapter 11 6 Representation for Planning STRIPS ltgt States Conjunction of facts AtH0me HaveMilk HaveBananas ltgt Goals Conjunction of postive literals AtH0me HaueltMilk HaueltBananas ltgt Goals can contain variables Existentially quantified Atx Sellsx Mill goal of being at a store and selling ltgt Actions Operators Action description serves only as a name for a possible action Precondition what must be true before an operator can be applied E ect how the situation changes when the operator is applied Modi ed for Fall 2006 Chapter 11 7 STRIPS operators continued ACTION Buyx PRECONDITION Atp Sellsp x EFFECT Havex Note this abstracts away many important details Restricted language gt efficient algorithm Precondition conjunction of positive literals Effect conjunction of literals Atp Selspx Buyx Havex Modi ed for Fall 2006 Chapter 11 8 N State space vs Plan space ltgt Situation space Progression planner Regression planner ltgt Partial Plan Search the space of plans rather than the space of situations Need to represent plans Use action precond effect tuples Refinement Operators Modification Operators ltgt Principles of Least Commitment Which steps first ltgt Partial Order Planner ltgt Total Order Planner Modi ed for Fall 2006 Chapter 11 9 Partial Planner Initial Plan Start Initial Goal S late I Stale Finish a Modi ed for Fall 2006 Start LeftShonn v Finish b RightShonn Chapter 11 10 N State space vs Plan space Standard search node concrete world state Planning search node partial plan Defn open condition is a precondition of a step not yet fulfilled Operators on partial plans add a link from an existing action to an open condition add a step to fulfill an open condition m one step wrt another Gradually move from incompletevague plans to complete correct plans Modi ed for Fall 2006 Chapter 11 11 Partially ordered plans Start Left Right Sock Sock i LeftShonn quot RightShonn Le sOCkOn Rightcock0n Left Right Finish Shoe Shoe Le Shonn RightShonn A plan is complete ifF every precondition is achieved A precondition is achieved ifF it is the effect of an earlier step and no possibly intervening step undoes it Modi ed for Fall 2006 Chapter 11 12 Partial Order Plan vs Total Order Plan Partial Order Plan Total Order Plans Left Right Sock Sock LeftSockOn RightSockOn Left Right Shoe Shoe LeftShonn RightShonn Modi ed for Fall 2006 Chapter 11 13 Modi ed for Fall 2006 A Partial Order Planning Example We use the shopping example We need to define Initial State OpACTION Start EFFECT AtH0me SellsHWS Drill Sell3SM Milk SellsSM Banana Goal State OpACTION Flnish PRECOND HaveDm ll HaveltMlll H aveltBanana AtH0me Actions OpACTION G0there PRECOND Athere EFFECT Atthere AtUzere OpACTION Bug1 PRECOND Atst0re Sellsst0re 1 EFFECT Havex Chapter 1 1 1 4 H POP Example Continued ltgt Convention Light arrows Ordering constraints Bold arrows Causal links Si igt Sj reads Sl achieves C for SJ By definition all causes are constrained to come before their effects Therefore each bold arrow has a light arrow underneath it ltgt Initial plan for the shopping problem Start AtHome SelsSMBanana SelsSMMik SelsHWSDri HaveDri HaveMik vHaveBanana AtHome Finish Modi ed for Fall 2006 Chapter 11 15 H POP Example Continued Ats SellssDri Ats SellssMik Ats SellssBananas BuyDriII l BuyMik l l BuyBananas HaveDri HaveMik HaveBananas AtHome AtHWS SelsHWSDril AtSM SelsSMMik AtSM SellsSMBananas BuyDriII l BuyMik l l BuyBananas HaveDri HaveMik HaveBananas AtHome 1 Some correct choices 2 Re ning the partial plan Modi ed for Fall 2006 Chapter 11 16 H POP Example Continued AtX AtX AtHWS SellsHWSDriI AtSM SellsSMMik AtSM SellsSMBananas BuyDri BuyMik BuyBananas HaveDn39ll HaveMik HaveBananas AtHome A partial plan that achieves At preconditions of the three Buy actions Modi ed for Fall 2006 Chapter 11 17 H POP Example Continued AtHome AtSM SellsSMBananas AtHome AtHWS Sells WSDriI AtSM Sells MMik HaveDril HaveMik HaveBananas AtHome BuyBananas 1 A awed plan Atx is linked with AtHome Agent can t be HWS and SM at the same time THE PLAN IS DEAD HOW A PLANNER DETECT THIS Modi ed for Fall 2006 Chapter 11 18 Clobbering and promotion demotion ltgt Causal links are protected links n IC C C C C IC 3 b c Figure 1 a 33 threatens a condition 0 that is established by 31 and protected by causal link from 31 to Sg b 33 has been demoted to come before 31 c 33 has been promoted to come after Sg Modi ed for Fall 2006 Chapter 11 19 Clobbering and promotion demotion A clobberer is a potentially intervening step that destroys the condition achieved by a causal link Eg GoHome clobbers AtHWS V DEMOTION m put before G0HWS GoHome AtHome AtHWS I m put after BugDmll PROMOTION AtH me Modi ed for Fall 2006 Chapter 11 20 H POP Example Continued AtHome AtHWS AtHWS SellsHWSDril AtSM SellsSMMik AtSM SellsSMBananas At M BuyDriII BuyMik l BuyBananas l GoHome HaveDriI HaveMik HaveBananas AtHome Figure 2 The GoHWS BuyDm ll causal link is protected ordering the GoSM step after BuyDm ll and GoSM AM BuyMz39lkBananas link is protected by odering GoHome after BugMilk and BuyBananas AtHWS 6 Modi ed for Fall 2006 Chapter 11 21 Modi ed for F 2006 POP Example A solution AtHWS SellsHWSDriI AtHWS AtSM SellsSM Milk AtSM Sells SMBan AtSM HaveMik AtHome HaveBan HaveDriI Modi ed for Fall 2006 Chapter 11 23 POP algorithm sketch function POPlnltlal goal operators returns plan plan lt MAKE M1N1MAL PLANlnltlal goal loop do if SOLUTIONplan then return plan Snead c lt SELECT SUBGOAL plan CHOOSE OPERATOR plan operators Snead c RESOLVE THREATS plan end function SELECT SUBGOALplan returns Snead 0 pick a plan step Snead from STEPS plan with a precondition c that has not been achieved return Snead c Note STEPSpan is the existing steps of the plan so far Modi ed for Fall 2006 Chapter 11 24 POP algorithm contd procedure CHOOSE OPERATORplan operators Snead 0 choose a step Sadd from operators or STEPSplan that has 0 as an effect if there is no such step then fail add the causal link Sada L Snead to LINKS plan add the ordering constraint Sadd lt Snead to ORDERINGS plan if Sadd is a newly added step from operators then add Sadd to STEPSplan add Start lt Sadd lt Finish to ORDERINGSplan procedure RESOLVE THREATsplan for each Sthmn that threatens a link S L Sj in LINKS plan do choose either Demotz39on Add Sthmu lt S to ORDERINGSplan Promotion Add Sj lt Sthmn to ORDERINGSplan if not CONSISTENTplan then fail end POP is sound complete and systematic no repetition Extensions for disjunction universals negation conditionals Modi ed for Fall 2006 Chapter 11 25 Summary Problemsolving vs Planning STRIPS language Partial planner Partial ordering Least commitment ltgtltgtltgtltgtltgtltgt The idea of Causal link Modi ed for Fall 2006 Chapter 11 26 INFORMED SEARCH AND EXPLORATION CHAPTER 4 SECTIONS 174 Modi ed for Fall 2006 Chapter 4 Sections 141 1 Outline History of Genetic Algorithms GAs The idea GAS as search algorithms GAs as learning algorithms later in the semester Generic GA Components Syntax Semantics Genetic Classifier Systems later in the semester ltgtltgtltgtltgtltgtltgtltgtltgtltgt Applications Modi ed for Fall 2006 Chapter 4 Sections 141 2 History ltgt Rather controversial O The idea of evolutionary computing 19605 by l Rechenberg in his work Evolution strategies O J H Holland quotAdaptation in Natural and Artificial Systems 1975 Some theoretical background on GAs ltgt Many other people after 0 J Koza Genetic Programming 0 D Fogel Evolutionary Programming 0 Other buzz words Modi ed for Fall 2006 Chapter 4 Sections 141 3 Genetic Algorithms What are they ltgt Learning algorithms ltgt Search algorithms ltgt Optimization algorithms Modi ed for Fall 2006 Chapter 4 Sections 141 4 What is Learning ltgt Learning denotes changes in the system that are adaptive in the sense that they enable the system to do the same task or tasks drawn from the same population more effectively the next time Hebert Simon 1983 O In which we describe agents that can improve their behavior through diligent study of their own experiences Russell and Norvig ltgt How learning takes place How do you learn Modi ed for Fall 2006 Chapter 4 Sections 141 5 II What is Search O The process of looking for solution ltgt Exploration vs Exploitation ltgt Learning vs Searching Modi ed for Fall 2006 Chapter 4 Sections 141 6 Genetic Algorithms O The idea of evolution ltgt Survival of the fittest ltgt Adaptation in nature ltgt Can you relate the above idea to search Modi ed for Fall 2006 Chapter 4 Sections 141 7 Things to Consider when solving a problem with GA What is the fitness function Evaluation function a part of critic How do we represent the individual Syntax Knowledge Rep How do we interpret the individual Semantics How are individuals selected for reproduction How do individuals reproduce ltgtltgtltgtltgtltgtltgt How is the next generation produced Modi ed for Fall 2006 Chapter 4 Sections 141 8 N Things to Consider short answers ltgt What is a fitness function Evaluation function a part of critic Domain dependent ltgt How do we represent an individual Syntax Knowledge Rep Domain dependent mostly ltgt How do we interpret an individual Semantics Domain dependent ltgt How are individual selected for reproduction Choose better performing individuals solutions probabilistic ltgt How do individuals reproduce Use genetic operators Crossover mutation etc ltgt How is the next generation produced Replace badly performing individuals by new individuals all or just a few Modi ed for Fall 2006 Chapter 4 Sections 141 9 Sketch of GA function GENETICALGORITHMpopulation FITNESSFN returns an individual inputs population a set of individuals FITNESSFN a function that measures the tness of an individual repeat parents lt SELECTION population FITNESSFN population REPRODUCTION parents until some individual is t enough return the best individual in population according to FITNESSFN O a search process in the space of individuals ltgt implicit parallelism The search is parallel an individual is a snap shot of a state in a separate search ltgt hill climbing making small gene changes to find the global extrema Modi ed for Fall 2006 Chapter 4 Sections 141 10 Genetic Algorithms 32752411 32748552 3274852 24748552 24752411 24752411 24415124 20 25 32752411 32752124 352124 32543213 11 14 24415124 24415411 gt 244154 a Initial Population b Fitness Function C Selection d Crossover e Mutation Modi ed for Fall 2006 Chapter 4 Sections 141 11 The idea of schema O A substring in which some of the positions can be left unspecified ltgt Example 246 O An instance of schema 246 24613587 ltgt Theorem If the average of instances of a schema is above the mean the number of instances of the schema in the population will increase over time Modi ed for Fall 2006 Chapter 4 Sections 141 12 H Issues Summary ltgt Population Size Large or small ltgt Genetic Operators What types Rates ltgt Steady state or Generational model ltgt How many new offspring ltgt Static Population Size vs Dynamic Population Size Modi ed for Fall 2006 Chapter 4 Sections 141 13 Local Search in Continuous Spaces Consider finding the place for three new airports that are closest to all cities in Romania e sum of the distances from each city to its nearest airport is minimized ltgt Locations of the airports 1311 2312 3313 ltgt discretize the search space Move one airport at a time to 1 or y with a fixed amount i6 ltgt Use Hillclimbing or Simulated Annealing no discretization needed Modi ed for Fall 2006 Chapter 4 Sections 141 14 Local Search in Continuous Spaces 7 Function minimization O The objective function can be defined as f17 211 27 212 3 33 Then minimize this function Gradient of the landscape The gradient of f is a vector Vf that gives magnitude and direction of the steepest slope So Solve vf i81 17891781 27892781 37833i 0 O Usually not possible to solve the equation in closed form Not for all three cities at the same time Local optimization is possible but not the global Modi ed for Fall 2006 Chapter 4 Sections 141 15


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.