DIAGRAMMATIC REASONING IN AI RobbieNakatsu AJOHNWILEY&SONS,INC.,PUBLICATION DIAGRAMMATIC REASONING IN AI DIAGRAMMATIC REASONING IN AI RobbieNakatsu AJOHNWILEY&SONS,INC.,PUBLICATION Copyright©2010byJohnWiley&Sons,Inc.Allrightsreserved PublishedbyJohnWiley&Sons,Inc.,Hoboken,NewJersey PublishedsimultaneouslyinCanada Nopartofthispublicationmaybereproduced,storedinaretrievalsystem,ortransmittedinany formorbyanymeans,electronic,mechanical,photocopying, recording,scanning,orotherwise, exceptaspermittedunderSection107or108ofthe1976UnitedStatesCopyrightAct,without eitherthepriorwrittenpermissionofthePublisher,orauthorizationthroughpaymentofthe appropriateper-copyfeetotheCopyrightClearanceCenter,Inc.,222RosewoodDrive,Danvers, MA01923,(978)750–8400,fax(978)750–4470,oronthewebatwww.copyright.com.Requests tothePublisherforpermissionshouldbeaddressedtothePermissionsDepartment,JohnWiley& Sons,Inc.,111RiverStreet,Hoboken,NJ07030,(201)748–6011,fax(201)748–6008,oronline atwww.wiley.com/go/permission. LimitofLiability/DisclaimerofWarranty:Whilethepublisherandauthorhaveusedtheirbest effortsinpreparingthisbook,theymakenorepresentationsorwarrantieswithrespecttothe accuracyorcompletenessofthecontentsofthisbookandspecificallydisclaimanyimplied warrantiesofmerchantabilityorfitnessforaparticularpurpose.Nowarrantymaybecreatedor extendedbysalesrepresentativesorwrittensalesmaterials.Theadviceandstrategiescontained hereinmaynotbesuitableforyoursituation.Youshouldconsultwithaprofessionalwhere appropriate.Neitherthepublishernorauthorshallbeliableforanylossofprofitoranyother commercialdamages,includingbutnotlimitedtospecial,incidental,consequential,orother damages. Forgeneralinformationonourotherproductsandservicesorfortechnicalsupport,pleasecontact ourCustomerCareDepartmentwithintheUnitedStatesat(800)762–2974,outsidetheUnited Statesat(317)572–3993orfax(317)572–4002. Wileyalsopublishesitsbooksinavarietyofelectronicformats.Somecontentthatappearsinprint maynotbeavailableinelectronicformats.FormoreinformationaboutWileyproducts,visitour websiteatwww.wiley.com. LibraryofCongressCataloging-in-PublicationData: Nakatsu,RobbieT.,1964– DiagrammaticreasoninginAI / RobbieT.Nakatsu. p.cm. ISBN978-0-470-33187-3 (cloth) 1. Artificialintelligence–Graphicmethods. 2. Artificialintelligence–Mathematics. 3. Reasoning–Graphicmethods. I. Title. Q335.N3552009 006.3–dc22 2009015920 PrintedintheUnitedStatesofAmerica 10987654321 CONTENTS PREFACE vii CHAPTER1 INTRODUCTION:WORKINGAROUND THELIMITATIONSOFAI 1 CHAPTER2 MENTALMODELS:DIAGRAMSINTHE MIND’SEYE 23 CHAPTER3 TYPESOFDIAGRAMS 57 CHAPTER4 LOGICREASONINGWITHDIAGRAMS 108 CHAPTER5 RULE-BASEDEXPERTSYSTEMS 143 CHAPTER6 RULE-BASEDREASONINGWITHDIAGRAMS 188 CHAPTER7 MODEL-BASEDREASONING 228 CHAPTER8 INEXACTREASONINGWITHCERTAINTY FACTORSANDBAYESIANNETWORKS 264 CHAPTER9 AFRAMEWORKFORUNDERSTANDING DIAGRAMMATICREASONING 302 INDEX 321 v PREFACE This book is really the end product of over a decade of work, on and off, on diagrammatic reasoning in artificial intelligence (AI). In developing this book, I drew inspiration from a variety of sources: two experimental studies, the devel- opment of two prototype systems, an extensive literature review and analysis in AI, human–computer interaction (HCI), and cognitive psychology. This work especially contributes to our understanding of how to design the graphical user interface to support the needs of the end user in decision-making and problem- solving tasks. These are important topics today because there is an urgent need to understand how end users can cope with increasingly complex information technologies and computer-based information systems. Diagrammatic represen- tations can help in this regard. Moreover, I believe that reasoning with diagrams will become an important part of the newest generation of AI systems to be developed in the future. I began investigating the topic of diagrammatic reasoning several years ago asadoctoralstudentwhile workingonresearchonuserinterfacedesign.Almost serendipitously,Istumbledonaconceptincognitivepsychologyknownasmental models. This is the idea that we construct models of the world in our minds to help us in our daily interactions with the world. I was intrigued by the idea and wanted to learn more about how, when, and why people do this. I believed that if we could better understand what these mental models are about, then we might use this knowledge to design computer user interfaces and aids, such as tutorialsandexplanationsthatmightsupportpeopleincomplextasks,andintheir everyday lives. I devote an entire chapter (Chapter 2) to the subject of mental models. It turns out that my investigation on mental models naturally and gradually evolved into a more general investigation on diagrams. This is because I soon vii