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

Artificial Intelligence

by: Roman McCullough

Artificial Intelligence CMPSCI 683

Roman McCullough
GPA 3.57

Shlomo Zilberstein

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

Shlomo Zilberstein
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 35 page Class Notes was uploaded by Roman McCullough on Friday October 30, 2015. The Class Notes belongs to CMPSCI 683 at University of Massachusetts taught by Shlomo Zilberstein in Fall. Since its upload, it has received 19 views. For similar materials see /class/232259/cmpsci-683-university-of-massachusetts in ComputerScienence at University of Massachusetts.


Reviews for Artificial Intelligence


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/30/15
Anytime A Hierarchical A Other Examples of Hierarchical Problem Solving Jiaying Shen I I I CMPSCI 683 Revrews of A and Its varatrons Fall 2004 o Ais bestfirstsearch vvith fn gn t hn gm 0 Three changes make it an anytime algorithm ill Use a nonadmissible evaluation function f n to select node to expand next so that suboptimal solutions arefound quickly ital lZl Continuethe search atterthefirst solution is found using an auxiliary admissible evaluation function my to prunethe open list 0 Ideal m lllm l quality in quot0 lime 3i When the open list is empty the last solution generated Is 0 Traditional qualify maximizing optimal Anytime lillvm limilingl o Hovvto chooseanonadmissible evaluation function fin Uwynyhl SZhrsbrnEV umrurszrm K unwary SlhersbrnEV umrurszm t 0 Use n 1 whgm mhln o Higherweight on hn tends to search deeper o Admissible ifhn is admissible and w s05 0 Otherwise the search may not be optimal but it normally nds solutions much faster 0 An appropriate w makes possible a tradeoff between the solution quality and the computation time cwnmi mummy 2mm Suppose you ad the lollcwing situations hcw ustw d would you a i the open list has gotten so largethat you are running 7 out of memory you are running out of time and you have not yet er7 reached an answ re are a number of nodes on the open list Whose h value is very small7 mum mmwm 2mm For each node store real fin glnhn in is the lower bound on the cost of the best solution path throu h n When nd solution node n1 ini is an upper bound oithe cost oithe optimal solution Prune all nodes n on the open list that have real in gt rim cwnmi mummy 2mm What would w 75 lppklihe7 Heavierweighls lend to Create more nl an anytime elieut mum mmwm 2mm Idea Find a highlevel structure for a solution and then use to nd detail solution Bene t Potentially Reduce signi cantly the size ofthe detail search space that needs to be searched comm S krshnlvlakr 2mm v lgnoring features of the world lgnoring constraints Limiting the horizon Limiting the number of goals demsian Comm S krshnlvlakr 2mm H mm summon 2mm u Operates like A exceptthat hs is computed by searching at the next higher level of abstraction quot5d 5i unal The result is combined with other estimates eg cheapest operator cost to produce the nal hs iii 5 gtlo cheapest operator cost Heuristic values are being cached to improve performance cwnmi summevmi 2mm A mapping if of states from state space ltSdgt into ltS d gt is an abstraction transformation iff d39ltbls1 ciszn sdls1 s2 Abstraction can be used in order to automatically create admissible heuristic f nctions hsi d msi mi Searching in Abstraction Space to Compute h using lin search mum summon mm H Embedding adding edges to the original graph corresponds to macro or relaxed operators Homomorphism grouping together sets of states to create a single abstract st te corresponds to dropping a featurdvariable from the state representation cwnmi summevmi 2mm Eliminate conditions Make possible new opeiatoi mum mmwm 2mm in The primary risk in using a heuristic created by abstraction is that the total cost of computing h over the course of the search can exceed the sailings comm sze enevt 2mm n If state s must be expanded by blind search then either s or Xs must be expanded by A using M A state is neeessaniy expanded by ahna seamh Wits distance lmm the start state is stnetiy less than the distance hmnthe start state to the goal state As a result 7 no speedup when a is an embedding Since s to s e pnssiblespeeorup when e is a homomorphism not equal 39 Q What speedup can be achieved mnw smemm swam The state with the highest degree is grouped together with its neighbors within a certain distance the abstraction radius to form a single abstract state comm sze enevt swim w 51 mum Inga stages mm a certain nuance start mnw smemm swam Isgrmpedtoglher Ml quotsuitors repeater mn goupm sates TABLE 1 Naive Hierarchical A absuactioo deus 2 Search 12203 slates Nodes Expanded Spam 1 Base mal I39hemwluutilAquot Leve1 Levei Seazch All Levels Baselevel Flinnksri llnn 866 389 7766 l 18 5 puzzle 951 720 343 3119 224 Fooi aDisk 4709 409 1635 12680 629 Hannl 7 7894 7m mag MSW 7m 100 3107 2736 1236 7059 641 Ml 0 40 2 7073 ms 914 747 707 Pclulullx 731 720 286 80b 1 5330 4493 1923 19386 604 A single base level search can spawn a large number of searches at the abstract level ow SZilbustnlnElessq DiAPSElnxJ Observation all searches related to the same base level problem have the same goal This allows additional types of caching of values It leads to breaking Valtoita s barrier in 5 out of 8 search spaces DOV Wk s zilaesiain EVlAssq 39mwscl m Naive Hierarchical A a Cacne n in abstract space v1 h caching a Cacne exact n s n0 along optimal solution in abstract space Exploit inronnersearcnes in abstract space and cacnerorose ln base level Search 7 Does not preserve monotone properties nt not comparable Witn n but don t need to reopen nodes 7 Cacne optimal patn in abstract space optimalpatn cacning v3 7 Remember opumal patn lengtn in abstract searcn space Peg cacning p being optimal patn lengtn rrorn startto goal in abstractspace am 5 lebustnln vlgssq masons 39lAELL Z Hierarchical A zlbslltwlluululliU 2 Nodes Expanded u probiems Scuwh 1hunuuluuul A V3 lt BS Spare VI V7 V7 mil nf 700 15100165 48 402 5rpllZZ1e 854 560 1xl Fool39s Dlsk 3950 525 132 Hanm7 515 N74 0 102000 1596 1023 171 MC bile 10739 1154 863 128 Permmer i 86 806 482 279 242 113 Wuula 1923 191180 591 2849 410 124 DOV Wk s zilaesiain EVlAssq 39mwscl m 0 Increasing the radius nf abstractinn has th cnntradictnry effects new 31ucmchicuu39 mast absmuomwhus PH manna abstract spaces cnhtain fewer states and each lt 131 w out uJ39 200 Search 39 abstract search prnduces values fnr mare m 59 35 36 40 states but 873 902 11 108 the heunstlc ls less dlscrlmmatulg 39 3M 17th S l The best case breaks the Valtnrta s barrier in W33 3 every search space mm s mmsvuss mam Wm sznbasmmsvtgssq msmm 39 a e a 39 12 o z o 3 u 0 lt o E 2 39 go o L39 395 o WWW mum w Pmacuun 39 7 Produce sotutton m htghest abstractton Space Map mm uperaturs nd states m gruund space 7 Re ne down to ground tevet Map tn uperaturs and states m gruund space an sum space 12 new 5 msst wwscmx mm s mmsvuss mam 1 quot 5 Pl llll MOVEVolsmfROMVPEczjojEca mums 1 quot Ski Pl llll A wallel elsl L8quot be always melee Wlmnul llllellelmg wlll a lalge lskll WWW smwvml cmlm Pl P2 P3 Idea Abstraction spaces are formed by removing sets of literals from the operators and states of the domain Premise Literals in a domain only interact with some ofthe other liter Is 7 lllelals lll D3 mules do llm llllelaelWllll lllelals lll D2 mules Metho artition literals into classes based on their interactions and orderthe c sses This forms a monotonic hierarchy of abstraction spaces that is any plan to achieve a literal cannot add or delete a literal higher in the hierarchy mm smwem 2mm m M m yummyWamwlhnng D mm llmlmmllsl l WMWEW e an um arlllllm mm l WM mm nlllww mm 0cmplell ly 0Elrl7 u is number ell u pelaluls n is numhel ulelllelenl lnslanllalee llelals WWW smwvml cmlm A smallel lsk L8quot be am smeleewlnem llllellellng W a large lskll waned an E undul pqzlgluldrl pag l Law s ln lLalESlllallllE W lllelal mistbe a1 a nlgnelellne same level on elm well lm ml Wagon elm Pal on elm Peagle and Val Level 1 Level 2 mm smemm 2mm Solution to an ndisk problem will require 2quot steps Backtracking across abstraction levels or subproblems within an abstraction level is never require Search space reduction is from exponential Ob39 to linear 0L in length of the solution where b is the branching factor Never factored in construction of abstraction space assumption used over and over for many problems oumgm SlebevstemKV Lassen CMPSCl 683 as Cupright SlebevstemKV Lassen CMPSOl 683 34 Plans using a hierarchy of abstraction spaces Tries to avoid backtracking by working on more important goals first Criticality assigned to preconditions by user and adjusted by system based on ability of operators to achieve them At each level planner would assume less critical preconditions to be true Cumllgm SlebevstemKV Lassen CMPSCl 583 35 Cupright SlebevstemKV Lassen mm Hf 36 Assign precondition criticali ee 5 m mquot 2 man a WWW mm mm W m in mm And m 7 w mmmmngs bm w v 3 32 39 Hm u minim mm mm Hm x 33 mm smhemmvussev mvsmm 37 qum an 5sazamzs What are open list and closed list Why do we f 5 Fixx need them 222mm Why is A optimal Why does A suffer from high memory requirement M Ma Xpnmimg mm m 39Mw v an 25 mama szararseo EW1 xgseqzmsz snang unmanaqu mvsmsxa 39 Emynghl s mhmuwvussen wwsmsx an Am J Am 39 i y m mu w w my 1m taun i A m m Emwmislkmnlvt w 2mm n m Aim quotWing m m m idcummghgaa cwiszt tmmcmm a How is DA different from standard iterative deepening What is the fbnund of each iteration Why does DA use less memory than Aquot What problems dnes DArsuffer from mm sznmenevm 2mm u r 399lEv iiii MN M W m Wright mm sznmenevm mum is Why do we need to memorize the best alternative path Why do we need to memorize the best descendent of a forgotten node Why does RBFS need less space than A Why is RBFS optimal What problem does RBFS suffer from comm szrmenevmy curser t5 m 1 Do We end hem cwmszmmmmmm 7 mm mmwm mm m w m m w a m w m o am a m mm mmwm 2mm Sn utmn found 8 t nphmaW Why do we need to back up the best fvalue of all the successors of a node Why do we need to back up the fvalue of a node s best forgotten child ls SMA optimal Why Why is SMAquot guaranteed not to get stuck in a loop aw mmquotth wwscmxx Iterative Improvement Simulated Annealing Hill Climbing Solution RepairDebugging GSAT Heuristics for CSP texture measures amts mimosa mam Jiaying Shen CMPSCI 683 Fall 2002 Example tracing A with two different heuristics m with mmilllilwt tiu Space and time variations of A cwngni slimmev Limi tlti39Slim Problem How to handle the exponential growth of memory used by admissible search algorithms such as A Solutions DA Koif1985 RBFS Koif1993 SMA Russe1992 cumin smmev DELEWEUW Beginning with an fbound equal to the fvalue of the E in I tate perform a depth rst search bounded by the fbound instead of a depth bound Unless the goal is found increase the fbound to the lowest fvalue found in the previous search that exceeds the previous fbound and restart the depth rst searc Eavywvl sairasuiisvusa DiAPSElnXJ The more informed a heuristic the more the contours will be stretched toward the goal they will be more focused around the optimal path Eavywvl sairasuiisvusa DiAPSElnXJ Algorithm lterativeDeepeningA 1 Set THRESHOLD the heuristic evaluation ofthe start state 2 Conduct a depth rst search based on minimal cost from current no e pruning any branch when its total cost function g h39 exceeds THRESHOLD If a so ution path is found during the search return it 3 Otherwise increment THRESHOLD by the minimum amount it was exceeded during the previous step and then go to Step 2 Start state always on path so iriitiai estimate is always overestimate and never decreasing DOW mt SlebaStAmEVtAssd 39mwscim B 222quot A A 54th Wriltc3rzu wzrrihu w may may cum mm M rated Elsaa gum in 4 imam wzaiiim 61 iiquot rm rims esaiu rqs ijuu ue Nodes are labeled with f g h The h values are the straightline distances to Bucharest What is the next Contour DOW mt SlebaStAmEVtAssd 39mwscim s lDA is asymptotically same time as A but only Od in space versus Ob for A r Avoids overhead of sorted queue of nodes lDA is simpler to implement no closed lists limited open list ln Korl s15puzzle experiments IDA solved all problems ran faster even though it generated more nodes than A e A solved no problems due to insuf cient space ran slower than 1 Wm SlebusmlnElessq wwsclnx fum lui RLCURSlVIVBESTrFlRSTVSEARCUtlimb41ml relums a soluliun m llllllln RnFSlMl KLVODlillNl l I l s l lll 17117715m5gtn function RBFSI plvbmlJlndvfl39ml39ll wlurns a salmon or failure and l new frcosl limit ifGOo Le TLSTlprtlblwn39lUlul um mlurn HUME llLl8 llll l PM W lilmmpriililmil it imamw is em ty than munn follow no for Carl 5 in success y lo M Him 1 6 9 t 5 115 pimp 11 l Ml ye lhe lllwcst frwluu nod m Minion ir gt llimilliieii return mum lm frh lllle among llL L mm X mill fibule illBt Slpmblellibcsl iiiliimlimii minimalich ifEmll 7 lullm lien reliirii mull illDrilmw xi tile semndrlmw ow smimevoss mm Mimics bestfirst search with linear space Similar to recursive depthfirst Limits recursion by keeping track of the fvalue of the best alternative path from any ancestor node If current node exceeds this value recursion unwinds back to the alternative path As recursion unwinds replaces fvalue of node with best fvalue of children Allows to remember whether to reexpand path at later time mm s museums stclnxa mm s museums stclnxa an AM uwvuwtmslm macwn up man Wham 5mm lam culscrm i3 mm mm ml is m uim in mi mm W mummmmmcmmm m More efficient than IDA and still optimal Like IDA suffers from excessive node regeneration Note mind changes in example IDA and RBFS not good for graphs Can t check for repeated states otherthan those on current path twww mva lam culscrm l5 Uses a given amount ofmemory to remember nodes so that they don t have to be repeatedly regenerated It will utilize whatevermemory is made available to it It avoids repeated states as faras its memory allows It is complete provided the available memo sufficient to store the shallowest solution path It is optimal ifenough memory is available to store the shallowest optimal solution path Othenivise it returns the best solution if any that can be reached with the available memory When enough memory is available forthe entire search tree its behavior replicates that ofAquot mummmmmcmmm m 1 Expand deepest lowest I cost leafnode 2 Update I cost ofnodes whose successors have higher I cost 3 Drop shallowest amp highest I cost leaf node remember best forgotten descendant 4 Paths longerthan node limit get on cost Emwmt snmmmy 2mm thn h mu t mm sammm 2mm rwthnmtummmx MStmm r mwwun n ttnmwmmdzvthlhm w t 3 mt Mt MW mam nu at n mmmm m may t m mum at rm WM mm mm mm hmrtiunVtA39rtvthttttrrtmiuttutnmmnmu Wm WM 4mm hr w nwwrltt Mtnmhmtm W m myer Mt mmwwwqu rr t w Warm u mmmt tm mum hr thtnkmm tn mu mm m min thpnnm t m4thth tumthwartm mmmnmm m M 0mm m 0mm uumnmnm mr mmsmstrmmrm mum Jr t rmt 3n 535 Emwmt snmmmy 2mm K mt mm sznmmevm 2mm A A A l5 ism mm a e 8 l5 l5 2mm c D vvl 7 Why oon lwe need in Search anymore allerlmdmg D calme Snmencvmy 2mm Staged search involves periodically pruning unpromising paths SMA is an example of a staged search llode expansion may be so costly because the branching factor is high or the cost to apply operators is high that exhaustive node expansion is not practical mm summon cmch 22 Use a generator approach to incrementally produce successors in order by quality must have operatorordering function Limit expansion so that only likely successors are generated often called plausiblemove generator Prune unpromising successors immediately following node expans on 39 Delay state computation until expansion time when possible must be able to compute hvvithout state only on operatorlprevious state calme Snmencvmy 2mm Practical and theoretical dif culties Agents have limited computational power They must react within an acceptable time Computation time normally reduces the value of the result There is a high degree of uncertainty regarding the rate of progress The appropriate level of deliberation is situation dependent mm summon cmch 2 A theory of rationality that does not give an account of problem solving in the face of complexity is sadly incomplete It is worse than incomplete It can be seriously misleading b providing solutions that are without operational signi cance The global optimization problem is to nd the least cost or bestreturn decision net of computational costs Herbert Simon 1958 mbmnavueg msmm 25 A Scottish word which means satisfying Denotes decision making that searches until an alternative is found that is satisfactory by the agent39s aspiration level criterion Heuristic search as satisficing Formalizing the notion of satisficing nowm s lebusmvv Evussq 39mwsm m It appears probable that however adaptive the behavior of organisms in learning and choice situations this adaptiveness falls far short of the ideal quotmaximizingquot postulated in economic theory Evidently organisms adapt well enough to satis ce they do not in general optimize quot mm s mbmnavueg msmm 27 In complex realworld situations optimization becomes me lWl m world is radically simpli ed until reduced to a degree of complication that the decision maker can handle Satis cing seeks simplification in a somewhat different direction retaining more of the detail of the realworld situation but settling fora satisfactory rather than approximatebest decision 0 Which approach is preferable nowm s lebusmvv Evussq 39mwsm m Goal reduce the execution time an Minimin lookhead search see next slide 39 39 39 7 Returns backup Natue m a nude hem hmkmg ahead Methnd39 limit the search hnrlznn an and select an action single move in constant quotquotWW WMWE quotE quotWquot t 7 VteWed as SWDW a more accurate and ccmputahchauy 39me expenswe heunshc when Make dechshon about nextmove m reatWortd Whthout 7 Reaseh mhe heu stmhm tmnhhs nnshstent and a comptete ptan path to reach goat state admhssmte then the error m the hackeeup Dost ntermhx parthat search WW1 executhon of aothon mm mm quotmm W mmquot mm Twn stages Make indwwduat move decision Perform mimmm search Whth atpha pman Make a sequence of dechshons to arrwe at a somthon 7 cheht mtmmum c1 hcnzch nude 8 essthan Man mtermemate nDdE the mtermemate heme and any successors can he ehmmatea hcmmrther Dnnst erath 7 Reason hsmchctcmcahd you are chhseamhmgtc recovermg from mappropnate acttons hcnzch ach t need gcah state to prune avohd hoops cwszmevmycmm 1 mmsmenevm 2mm an procedure evamatetmovehmih a return hackedup estimate r tmovet hy pmhihg search to depth Iimi 1 Open moveu u 2 move g movetehtmovet 3 While tapequot not emptyt do node a a to en 5 expand node at each child olnode do 476 wk 10 C 70 s We a q tchim q thodet e movecost 7 assummg you needto go to the gasstate thru 5 ham 3 7 chimp chili e h tummy Prune child illtchildt gt at As a result of ex lorln n the search spaoe from ate a a immim lt a an you can re lace apM the better more Informed 39 estimate g a to c c 9 nudepth 741 armltchumn then I 10 I th39ld0ddd Thseads toamore Informed declslonatSmmetherto 11 511 c I aquot m D D D take the action Inthe real world of movmgquot to eIther 39 state y a or X WWW Smxrshnlvtaw cmm m mm shhmevm cuescm 2 aasic Principic One shouhi hacktrackto a picuiousiy uisitcu statcwncn thc cstiinatc oi soiuing thc prohicni iron that statc pius thc cost oi muniiiig to that statc is icss than thc cstiinatcu cost oi going iorwani iroin thc cuncnt statcquot Kori Mcrit oicucry node m gtnt c Mm is incasurcu rciatiuc to thc cuncnt poshion oithc prohicni soiucr in thc rcaiworhi a initiai state is micuant iionc inoucs hackto a prcuiousiy uisitcu rcaiworhi statc than it nccus to takc into account that on aircauy has takcn action thcrc rvaiue Msiaie is maxi basil cmwmi snkrshnMtay cuEim cmwmi snkrshnMtay cuEim Ma39nta39nsinahashtaiiicaiistoithoscnoucsthathavchccn visited by an actual niovc oithc pmhlau solvu39 ncnt statcis expandm anuthc hcuristic iunction poss39hly augmemaii 1y iookahcai scaich is mplied to cash stats which is not inthc hash taiiig ihc wl adi na39ghhoiing stats is conuntai 1y ahiing thc hvaiuc piustnccost oithciink to thccu icnt stats ihc ncighhor with thc nininuinvaiuc is chosen iorthc mnmt stat ihc seconii hcst value is 51mm in thchash tahic tor thc cuncnt stats 7 Repiesemsme estimateu in Lust oisohingthc piohiem by vetuining 0 this slate a Semn beslavm sinnps mm Salaamtwin cunscim AnytimeA Hierarchical A mm Salaamtwin cunscim Victor R Lesser CMPSCI 683 Fall 2004 Many Slides Courtesy of Shlomo Zilberstein Also Slides Courtesy of Milind Tambe USC Tuomas Sandholm CMU and many others Vimltf lm Instructor VictorR Lesser liters1322 all merenu Email lessercsumassedu hours Tuesdays 1llll 230pm CSClllll TA Mike O Neill Email mpncsumassedu ehnurs Wednesdaysldlll Clllll Tlill Course Web Page htto mascsumasseduolasseso5603 39 Learning Support Services will contain DVD on the 10th lloorof the DuBois Library yummy Nominally you need an undergraduate course in Al Not necessary to be successful in course Will move quickly over elementary material Vimltf lm Encouragement to ask questions during class Without your feedback it is impossible for me to know what you don t know There is no reason not to ask questions during class Ofcourse you could also send email or meet in person Encouragement to read course material prior to class After this course you will be able to construct simple Al systems t uxxvcssmrmm understand stateoftheart Al techniques read the Al literature evaluate Alrelated technology claims apply Al techniques in nonAl settings pursue specialized Al courses and research Historical Definition of Al The study of the conjecture that every aspect of learning or any other feature of intelligence can in principle be so precisely described that a machine can be made to simulate it Dartmouth Workshop Summer of 1956 Constructing intelligent machines for a wide range of applications Augmenting human problem solving Formalizing knowledge and mechanizing intelligence Uslng computational models to understand complex behavior Making computers a easy to won t uxxvcssmrmm with aspeople Complexity ofWork Place Rappaport 1991 comptva BUSlNESS ENVlRONMENl lea iaei zoom is zlnlumallm Syseiiis vunmsilmlm v Ambiguity I dropped the egg on the table and it broke Resource limitations Is there a winning opening move in chess Many applications are NPcom plete Con icting goals and tradeoffs Computer I need more free disk space Uncertainty and missing information 7 Missing lnlormalmn pinnamiisiiu aUlimiS open and dynamic environments vunmsilmlm ii Cheaper Sensors and Better Sensor Processing vision speech and text Orders of magnitude increase in computing power Commodity processors gtbillion instructions per econ Special purpose processors for sensor processing Parallel computing ne and large gr in Distributed processing and highspeed communication Nll Large online knowledge bases Tremendous Progress in Providing Formal and Practical Underpinning to the Discipline overthe last 20 years mnmsilmlb W Conventional software can be contrasted with Al systems in a number ofways Language arithmetic vs logical probalistic Data numbers vs symbols Coding procedural code vs declarative sentences 0perations calculations vs reasoning symbolic and decision theorectic Knowledge formulas vs heuristics Program output deterministic vs nondeterministic certaianellde ned vs uncertainlsearch Problem speci cation precise vs impreciselrelative Solution quality exactloptimal vs approximatelsatisficing mnmsilmlb i2 Scheduling and Planning 7 olnvnsonni system used in Desert 81mm and Desert snelu apeiaimsla plan iagislisaipeapieanusup ies 7 Anienmnnunins remuling mnlingmcypamei 7 European maceagenoypianning me scheduling aimaaemll asanmiy inegralian and ysihcalan Speech Recnglllllnn r PEGIRSUS Wakequot lmguage lrlerlxeln Ainslmn Alrlines EMSV SIRERE reservation system Computer Mslnn 7 raceiemgnnian paganism use hyhmks myeinnienh etc 7 We ALVlNN syseni nun cMu ammoniausiyemyea van mni Wasnnglm o c tn sanoiega all ml 52 mm miles averagngES nipi davandnlg andlnali weaneicmenims 7 Hamwlllrlglemgmlnn eimmnlsand nimuladunrg inwedlm hagwge irsrmnn amanialicaiiycmsiua so geanieliicniaaeis Diagnostic Systems 7 Microsoll oncenssslanl 7 Paihnneei lei eiagnesis nl hrnphneee eiseases pe rniseltpe snaeesgneenapprnveehynmn 7 Whirlpool customer assistance Lenlel System Configuration 7 DEC SXCONSSlemlnlLusmmllal wale connguialion Financial Decision Making 7 Fraud delELIlml and llansaLllnn approval by credit card companies mongage companies banks and the U s gmelnmenl 7 implnvlng ple lLllml oloaily revenues and stalling iepuiiernenlsloi a usi 7 Help desksuppnn sysierrslennelhe ngntansneile any Luslnmal s uESllDll Classification Systems NASA s system lorclassilying very laint areas in astronomical images into eitherstars or galaxies with very high accuracy by learning lrom human experts Mathematical Theorem Proving Use inlerence methorls to prove newtheorems Game Playing Computer programs heat world s best players in chess checkers aml backgammon MacnlneTransiatlon 7 Alavisa snanslaiieneiwehpages 7 Translation ol Caterpillar Truth manuals lllll U languages An agent is anytnlng tnat can be Viewed as percelVlng its enVlronment tnrougn sensors and acting upon tnat enVlronment tiirollgn effectors sensors Illnlors MEANING PROPERTV 7 situatoo Sense an act in oynamrciuncenarn enyrronments 7 Flexible neactrye responos to cnan es in tne enyrronment Proactrye actrnoaneaoo time 7 Autonomous Exercises controi oyer its own actions 7 eoaionontoo Purposelttl 7 Learning Aoaptiye 7 Persistent Continuously mnnrno process 7 Social intoractsntn otner agentspeopie 7 Mobile Aole to transpon riseir 7 Personality Ctiarauter Emotionai stale umsm n Applications information gattiering integration Distributed sensors Ecommerce Distributed Virtual organization Virtual humans for training entertainment Rapidly growing area 7 quot Simple re exive agents Agents that keep track of the world Deliberative agents Explicit representation oi domain knowledge Runtime probiemsoiying and reasoning Modeling tire World Selfmodeling and metareasoning How are agents different from the traditional view of system de nition 7 Wiren sensorstatic input eiiectors nxep output tne ooai isto ropuce tne correct nulpttl anp enyironment is staticiirreieyant we raii into tne cateoory oitrapitionai systems BUT 7 Enyironmentmaype pynamic 7 Sensino may be an ongoing situation assessment process 7 Eirectors may reouire compiex pia l 7 Goai may be termed wrtn respect to current state oienyironment As a resut 7 Deriyino tne inputoutput mappino rromtne ooai is not opyiousi How to decide what to do Given BIG resource Bounded Information h ring 7 The performance measure 7 The percept sequence Gat e 7 The agent s knowledge 7 The set of available actions Takes role of human in support ofdecision process I An Ida gem WIquot omperform any Other agent Integration of Planning scheduling text processing In maxlmlzmg the performance measure and interpretation style reasoning A Lofty Goal But AI is a Very Long Way Helps pick so ware packages from Being Able to Address this Question for Complicated Applications t uxxlcssmrmm Rapid growth of WW Growth has outstripped technology Information Retrieval technology a start Ef cient fast general Access to enormous amount of data Input 7 Word processing package for a Mac Browsing amp processing documents manually nontrivial 7 200 pnce llrn ll 7 Search process should take 10 mlrl amp Cost leVSS than 535 v lgxxlcssmfmm z t uxxlcssmrmnt BIG recommends Corel WP35 Active search and discovery 7 WVWVpageS on tne tnternet Resource Bounded Reasoning 7 Can only process a llrntteo arnount or tnronnatton wttn tn resource constratnts ttrne and money Goaldriven and Opportunistic control 7 Foo sea on spectnc goals but need to react to ernergrng tntonnatton Information extraction 7 Structured and unstmctured lnforrnatlon Information fusion 7 incomplete unreliable contraotctorylnrorrnarlon t texxlcssmrmm Auctioning multiple distinguishable items when bidders have preferences over combinations of item Example applications 7 Allocation of transponalon tasks 7 Allocallon d handwldlh Dynanlallyln compulernaworks sratlcally egg by Fee 7 Helnsuratoe markets 7 Hetal ecommerce collectllales tllgntsnotelsevent Ildltets 7 Resource a task alocatlon In operating systems a mobile agent plallorms Example procurement in supply chains Auctioneer wants to buy a set of items has to get all Sellers place bids on how cheaply they are willing to sell bundles of items t texxlcssmrmm r r mg Auctioneer wlnner ddermlnatlon problem so oinsnis M i z aim sa minis pn 3 BM 314551 wthJCMisasaol ems aidplisaprioe SJuSktilllllnipllhilis oonoern the sane set Mitems dl but the highest bid car he dismidat l1y aplwlool i Problem Ldiel the bids as winning 3 1 or losing 3 0 so as to naxinl39xe auctioneu s quotvalue sich tha each itan is allocated to at moi ne hid vmsm Courtesy of mamas Sandhalm a NPoon39plete nnnmswnn an What are theideas that you can use to develop a search algorithm for winner determination for 1000 s of bids and 1000 s of items in a reasonable time trame seconds 7 Optimal anytime satisficing vulmsixmlm m A Computational Perspective on the Design of Intelligent Agents What is theform ofthe computational structures that are required How does this differ from or relate to other computational problems nnnmswnn 2 There is no universal approach to the design Dealing with the Ubiquity of Uncertainty a 5 95quotquot Environment Sensing Action and Knowledge We will be exploring the design space Components and architectures Dealing With Limited Resources Different approaches Computation memory communication For different classes of problems bandWidth39 etc39 For different environments For different criteria for success a t uxxicssmrmni I Text Book Arti cial Intelligence A Modern 0 Factors Approachquot 2nd Edition Stuart Russell and Peter Norvig Prentice Hall 2003 evic ilvolrkd m I I t Book s website lthttplaimacsberkeleyedugt 39 39quot e pr 9quot39quot39quot39quot9 55399quotm9quot 5 Will Augment with Material Not Covered in Book Midterm exam 30A Additional Readings Available on the course web Final exam 30 SI e Required readings Suggested readings Mll add to suggested readings to ensure you have plenty of reference 39 l Not necessary to read through suggested readings Late Policy Usually each assignment has two weeks time to nish Assignments will not be accepted later without the express permission of the instructor or the teaching assistant v uxxicssmrmm 35 t uxxicssmrmni Reasoning Under Uncertainty Introduction 1 p ro lem solving using sophisticated search 7 Reasoning under uncertainty 8 Learnin 7 9 Intelligent Systems 3 Summa Won t be Covered e Adversanal Game Playan 7 Elementary Loglcal Formallsm for knowledge Representatlon May add in lectures on Planning Knowledge Representation Blackboard Systems as an Lectures 9 and 1D Architecture for Interpretation Lecture 1 Informatio Lectures 12 and 13 Probabilistic Reasoning with Belief Networks Lect Lecture 14 Alternative Models of Uncertainty eor ure 15 Decision Th Lecture 16 Decision Networks May add lecture Hidden Markov Models HMMs 1 Representing and Reasoning with Uncertain n Introduction Lecture 1 Search Lecture 2 Introduction and Course Information Overview of Issues in Heuristic Search Lecture 3 Heuristic Searc Lecture 4 Search Complexity and Applications Lecture 5 Time and Space Variations of A Lecture 6 Abstraction Approximation and RealTime Search Lecture 7 Lecture 8 Iterative Improvement SearchGSAT Constraint Satisfaction and Genetic Algorithms t uxxlcssmrmm Learning Lecture 17 Learning from Observations Lecture 18 Leaming Techniques Lecture 19 Neural Netw rks Lectures 20 and 21 Markov Decision Processes and Reinforcement Learning Lecture 22 Data Mining Lecture 23 Analytical Learning and Planning t uxxlcssmrmm May add lecture on Kernel Machines Intelligent Systems Lecture 24 ResourceBounded Reasoning Systems Lectures 25 and 26 Intelligent Agent Architectures Lecture 27 MultiAgent Systems and Summary Operate in a satis cing mode 7 Do the best they can Wltrllrl available resource constraints 7 Deal witn uncertainty as an integral part of networkproblem solyin 7 Complex organizational relationsnips among agents Highly adaptivehighly reliable 7 Learning will be an important part ofthelrstructure terrnlorlgrterm shorty iAble to adapt thelrproblemrsolvlng structure to respond to charlglrlg taskenvironmental conditions Profound implications Computer Science Network of Cooperating IntelligentAgents peoplemachines Constructionist perspective build out of heterogeneous systems highevel arti cial language for cooperation problem solving for effective cooperation will be as or more sophisticated than the actual domain problem solving reasoning about goals plans intentions and knowledge of other agents u uxxlcssmrmm Satisficing ComputationBounded Rationality a computational frameworkthat allows you to trade offthe quality ottne answer derived witn the amount otresources used to derive it Uncertaintyinconsistency as integral part of problem solving 7 omputational frameworkthat allows you to liye witn lti ratner tnan eliminate it intelligent Control 7 Computational irameworkthat allows you to effectively manage your resources to satisfy tne giyen goals AgencySemiAutonomousAgent e computational framework tnat allows agents to interact autonomously witn tne world in terms of sensing perceiving planning effecting arid communicating u uxxlcssmrmm Why is search the key problem solving technique in Al Formulating and solving search problems Reading Sections 3137 39SmaH 20 Dagmar radar unns 30 s 7 Scan nne nf W22 20 semnrs m a m dn mm meme supmmpmm xnz Mb mm Framnnz H mm mnmsumm w An mm aumnn calm na mmmm mmlmsummelmusm amnmmma mm Me a gas a eemww apaan veqwemzns A s Mumpsawe swam quotmansquot matmeml manage mm laughs mm mm mmgxwungmnml mommnn maul his APDB Amerwcan Patent DB WSJ WaH Street Journa AP Assomated Press News


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

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!"

Anthony Lee UC Santa Barbara

"I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

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."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

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.