상세정보

This book presents, within a conceptually unified theoretical framework, a body of methods that have been developed over the past fifteen years for building and simulating qualitative models of physical systems--bathtubs, tea kettles, automobiles, the physiology of the body, chemical processing plants, control systems, electrical systems--where knowledge of that system is incomplete. The primary tool for this work is the author's QSIM algorithm, which is discussed in detail.

Qualitative models are better able than traditional models to express states of incomplete knowledge about continuous mechanisms. Qualitative simulation guarantees to find all possible behaviors consistent with the knowledge in the model. This expressive power and coverage is important in problem solving for diagnosis, design, monitoring, explanation, and other applications of artificial intelligence.

The framework is built around the QSIM algorithm for qualitative simulation and the QSIM representation for qualitative differential equations, both of which are carefully grounded in continuous mathematics. Qualitative simulation draws on a wide range of mathematical methods to keep a complete set of predictions tractable, including the use of partial quantitative information. Compositional modeling and component-connection methods for building qualitative models are also discussed in detail.

Qualitative Reasoning is primarily intended for advanced students and researchers in AI or its applications. Scientists and engineers who have had a solid introduction to AI, however, will be able to use this book for self-instruction in qualitative modeling and simulation methods.

Artificial Intelligence series

정보제공 :

CONTENTS
List of Figures = xvii
List of Tables = xxiii
Series Foreword = xxv
Preface= xxvii
1. Introduction to Qualitative Reasoning = 1
 1.1 Incomplete Knowledge = 1
 1.2 Building Models ; Using Models = 2
 1.3 Partial Knowledge of Quantity = 7
  1.3.1 Interval Arithmetic = 7
  1.3.2 Nominal, Ordinal, Interval, Ratio = 7
  1.3.3 Landmark Values = 8
  1.3.4 "Fuzzy" Values = 8
 1.4 Partial Knowledge of Continuous Change = 10
  1.4.1 Discrete State Graphs = 10
  1.4.2 Differential Equations = 11
  1.4.3 Abstractio from Numerical to Symbolic Values = 12
  1.4.4 Abstractio to Qualitative Values and Relations = 14
 1.5 References = 14
  1.5.1 Comparisons = 15
2 Concepts of Qualitative Simulation = 17
 2.1 Qualitative Structure = 17
 2.2 Qualitative Knowledge of State = 20
  2.2.1 Qualitative State Is Dynamic= 22
 2.3 Predicting Behavior from Initial Conditions = 22
  2.3.1 Propagating to the Complete Initial State = 23
  2.3.2 Predicting the Next State = 26
  2.3.3 Moving to a Limit = 27
  2.3.4 Creating New Landmark Values = 29
 2.4 Example : Ballistic Trajectory in Two Dimensions = 33
 2.5 Problems = 33
3 The QSIM Representation = 37
 3.1 Introduction = 37
  3.1.1 Qualitative Differential Equatins = 37
 3.2 Symbolic Descriptions of Continuous Change = 38
  3.2.1 Qualitative Variables = 39
  3.2.2 Quantity Spaces = 40
  3.2.3 Qualitative Values = 41
 3.3 Defining the Qualitative Constraints = 43
  3.3.1 Abstracting Structure from ODE to QDE = 44
  3.3.2 Corresponding Values = 46
 3.4 The Domain of Signs = 47
  3.4.1. Sign-Valued Operators = 47
  3.4.2 Qualitative Addition : Function or Relation? = 48
  3.4.3 Confluences = 50
  3.4.4 Hybrid Sign-Real Algebra = 51
 3.5 Evaluating the Qualitative Constraints = 54
  3.5.1 Monotonic Function Constraints = 54
  3.5.2 Qualitative Addition  = 55
  3.5.3 Qualitative Multiplication = 56
  3.5.4 Qualitative Negation = 57
  3.5.5 Qualitative Derivatives = 57
  3.5.6 The Constant Constraint = 57
  3.5.7 Non-Monotonic Function Constraints = 57
 3.6 Multivariate Constraints = 58
  3.6.1 The Multivariate Monotonic Function Constraint = 58
  3.6.2 The Signed-Sum Constraint = 59
  3.6.3 The Sum Constraint = 60
  3.6.4 The Sum-Zero Constraint = 60
 3.7 Transitions = 61
 3.8 Discussion : Quantity Spaces = 61
  3.8.1 Low Resolution of Quantity Spaces = 61
  3.8.2 Generalized Corresponding Values = 62
  3.8.3 Associative Law Violations = 64
  3.8.4 The Selection Problem = 64
  3.8.5 Distributive Law Violations = 65
  3.8.6 Unrelated Quantity Spaces = 66
 3.9 Example : Algebraic Manipulation = 66
 3.10 Problems = 68
4 Solving Qualitative Constraints = 75
 4.1 Introduction = 75
 4.2 Constraint Propagation = 75
  4.2.1 Propagation Is Efficient = 78
  4.2.2 Propagation Can Be Blocked = 78
 4.3 Constraint Satisfaction = 80
  4.3.1 Constraint Filtering = 81
 4.4 Constraint-Filtering Examples = 85
  4.4.1 Successor Generation for the Bathtub Model = 85
  4.4.2 Successor Generation for the Spring Model = 89
 4.5 Completing the Initial State Description = 93
 4.6 Problems = 94
5 Dynamic Qualitative Simulation = 97
 5.1 Introduction = 97
 5.2 The Immediate Successors of a State = 98
  5.2.1 Validity of the Qualitative Successor Table = 101
 5.3 Behavior Generation = 102
 5.4 Global Filters = 104
  5.4.1 The "No Change" Filter = 105
  5.4.2 Infinite Values and Infinite Time = 105
  5.4.3 Recognizing a Quiescent state = 106
  5.4.4 Creating New Landmarks = 107
  5.4.5 Creating New Corresponding Values = 109
  5.4.6 Identifying Cycles = 109
  5.4.7 Propagating Inconsistency = 111
 5.5 Examples = 111
  5.5.1 The Bathtub = 111
  5.5.2 The Spring = 114
 5.6 Guarantees = 117
  5.6.1 Guaranteed Coverage = 118
  5.6.2 Incompleteness = 119
  5.6.3 Discussion : Using Qualitative Predictions = 122
 5.7 Total Envisionment = 123
  5.7.1 Attainable Envisionment = 123
  5.7.2 Transition Graph or Behavior Tree? = 125
 5.8 Non-Standard Models of time = 126
 5.9 Problems = 128
6 Case Studies : Elementary Qualitative Models = 131
 6.1 One-compartment Balance System = 131
 6.2 Thermostat : Proportional Control = 136
 6.3 Equilibrium Mechanisms in the Kidney = 136
  6.3.1 The Starling Equilibrium Mechanism = 140
  6.3.2 Water Balance = 140
  6.3.3 Sodium Balance = 146
 6.4 Problems = 149
7 Comparative Statics = 151
 7.1 The Quasi-Equilibrium Assumption = 151
 7.2 Solving Comparative Statics Problems = 152
 7.3 Example : The Water Tank = 153
  7.3.1 Solve for Basic Qualitative States = 153
  7.3.2 Solve a Comparative Statics Problem = 156
  7.3.3 Solving for Initial and Final Response = 157
  7.3.4 Generalize to slowly Moving Equilibrium = 158
 7.4 Equilibrium Must Be Stable = 159
  7.4.1 The Locus of Equilibrium States = 159
  7.4.2 Testing Stability by Simulation = 161
  7.4.3 Testing Stability Algebraically = 162
 7.5 Case Study : Supply and Demand Curves = 163
 7.6 case Study : The Pressure Regulator = 167
 7.7 Case Study : Recycle Tank = 167
 7.8 Problems = 167
8 Region Transitions = 175
 8.1 Introduction = 175
  8.1.1 Moving from One Region to Another = 175
  8.1.2 The Transition Mapping = 176
  8.1.3 Interpretations of Region Transitions = 177
 8.2 Case : The Bouncing Ball = 178
  8.2.1 Bounce Viewed as Spring = 178
  8.2.2 Bounce Viewed as Reflection = 179
 8.3 Representing Saturation : S^+ and S^- Constraints = 182
  8.3.1 Case : Drug Metabolism = 183
  8.3.2 Example : Irreversible Population Change = 185
 8.4 U^+ and U^- Constraints = 185
 8.5 Example : On-Off Control = 187
 8.6 Example : Linear and Rotary Motion = 190
 8.7 Example : Glaucoma = 194
 8.8 Problems = 198
9 Semi-Quantitative Reasoning = 203
 9.1 Example : The Water Tank = 204
 9.2 Generating Equations From a Behavior = 205
  9.2.1 Value-Denoting Terms= 209
  9.2.2 Set-Denoting Terms = 209
  9.2.3 Arithmetic Constraints = 210
  9.2.4 Quantity Spaces = 211
  9.2.5 Derivative Constraints : (d/dt x y) = 211
  9.2.6 Monotonic Function Constraints : (M+ x y) = 212
  9.2.7 Indexing the Equations = 213
 9.3 Interval Constraint Propagation = 214
  9.3.1 Representation : Intervals around Values = 215
  9.3.2 Representation : Envelopes around Functions = 215
  9.3.3 Interval Arithmetic= 217
  9.3.4 Expression Evaluation = 217
  9.3.5 Intersecting New Intervals with Old = 218
  9.3.6 Benefits of the Interval Representation = 219
  9.3.7 Inference : Propagation = 219
 9.4 Soudness = 220
 9.5 Discussion = 223
  9.5.1 Applications to Diagnosis = 223
  9.5.2 Applications to Design = 225
  9.5.3 Other Representations = 226
  9.5.4 Tighter Bounds Building on QSIM + Q2 = 227
 9.6 Example : An Autonomous Clock = 228
 9.7 Problems = 233
10 Highter-Order Derivatives = 237
 10.1 Introduction = 237
 10.2 Highter-Order Derivatives = 239
  10.2.1 Identifying Chattering Variables = 240
  10.2.2 Applying the Higher-Order Derivative Constraint = 242
  10.2.3 Deriving an Expression for sd2(υ,t) = 244
  10.2.4 Determining the Value of sd3(υ,t) = 245
 10.3 Examples : Cascades = 249
  10.3.1 The Two-Tank Cascade = 249
  10.3.1 The Three-Tank Cascade = 251
 10.4 Monotonic Function Constraints = 253
  10.4.1 The Sign-Equality Assumption = 254
  10.4.2 Example : Violating the Sign-Equality Assumption = 255
  10.4.3 Avoiding Prediction Failure = 256
 10.5 The Analytic-Function Constraint = 258
 10.6 Behavior Abstraction = 259
  10.6.1 Collapsing Descriptions = 260
  10.6.2 Verifying Viability = 262
  10.6.3 Discussion = 263
 10.7 Conclusions = 264
 10.8 Problems = 266
11 Global Dynamical Constraints = 269
 11.1 Introduction = 269
 11.2 Solution 1 : Make the Invariant Explicit = 271
 11.3 Example : Predator-Prey Ecology = 271
 11.4 Solution 2 : The Kinetic Energy Theorem = 276
  11.4.1 Determining Signs of terms = 277
  11.4.2 Example : Undamped Spring = 278
  11.4.3 Example : Damped Spring = 279
  11.4.4 Proof of the Kinetic Energy Theorem = 279
  11.4.5 Identifying the Kinetic Energy Constraint = 282
 11.5 Solution 3 : The Phase-Space Representation = 283
  11.5.1 Qualitative Phase Space = 284
  11.5.2 Identifying Intersections Qualitatively = 286
  11.5.3 Limitations = 286
 11.6 Example : The PI Controller = 287
 11.7 Qualitative Phase Portraits = 290
 11.8 Discussion = 295
  11.8.1 From the Algebraic Point of View = 296
  11.8.2 From the Geometric Point of View = 296
 11.9 Problems = 297
12 Time-Scale Abstraction = 299
 12.1 Hierarchical Structure = 299
  12.1.1 Communicating across Time-Scales = 299
 12.2 Simulating at Multiple Time-Scales = 301
  12.2.1 Fast-to-Slow : Abstracting a Process to a Constraint = 301
  12.2.2 Linking Models at Different Time-Scales = 302
  12.2.3 Translation from One Model to Another = 304
 12.3 Example : Adaptive Controllers = 306
  12.3.1 The Basic Tank and Controller = 306
  12.3.2 Adaptive Control = 306
  12.3.3 Simulation with Time-Scale Abstraction = 308
  12.3.4 Simulating the Fast Model = 310
  12.3.5 Simulating the Slow Model = 310
  12.3.6 Completing the State of the Fast Model = 312
  12.3.7 Inconsistent Completion Refutes Slow Behaviors = 314
 12.4 Case Study : Aristotelean Physics = 315
 12.5 Related Work = 317
 12.6 Problems = 318
13 Component-Connection Models = 321
 13.1 Model Building and Model Simulation = 321
 13.2 A Component Ontology for Model Building = 323
  13.2.1 Part and Whole = 323
  13.2.2 The Closed-World Assumption = 324
  13.2.3 Generic Quantities and Bond Graphs = 325
  13.2.4 "No Function in Structure" = 326
 13.3 A Model-Building Language = 328
  13.3.1 CC : A Language for Component-Connection Models = 328
  13.3.2 Compiling a CC Model to a QSIM QDE = 329
  13.3.3 Mapping CC Names to QSIM Variables = 330
 13.4 Example : The Electrical Domain = 331
  13.4.1 The RC Circuit = 331
  13.4.2 Electrical Component Library = 331
  13.4.3 Compiling the Model = 335
 13.5 Example : The Hydraulic Domain =  340
  13.5.1 Hydraulic Component Library = 340
  13.5.2 The Two-Tank Pumped Loop = 344
 13.6 Discussion = 347
  13.6.1 Diagnosis from First Principles = 347
  13.6.2 Relaxation of Assumptions = 347
 13.7 Problems = 348
14 Compositional Modeling = 351
 14.1 What to Leave In, What to Leave Out? = 351
 14.2 Composing Models = 352
  14.2.1 Signed Directed Influence Graphs = 352
  14.2.2 Qualitative Process Theory = 352
  14.2.3 Influences and Constraints = 353
  14.2.4 QPC = 355
  14.2.5 Axiomatizing Compositional Modeling = 356
 14.3 Building Models = 357
  14.3.1 The Participants= 357
  14.3.2 The QPC Model-Building Algorithm = 358
 14.4 Modeling Assumptions and Negligibility = 360
  14.4.1 Types of Modeling Decisions = 361
  14.4.2 Selecting Modeling Assumptions = 362
 14.5 A Simple Domain Theory for Fluids = 365
  14.5.1 Ontology : Objects and Relations = 365
  14.5.2 Model Fragment Library : Liquid Flow = 366
  14.5.3 Create Entities Only As Needed = 368
 14.6 Example : The Water Tank = 369
  14.6.1 Building the Initial Model = 370
  14.6.2 Creating an Initial State and Simulating = 371
  14.6.3 Building an Model after Overflow = 372
  14.6.4 Creating a New Initial State and Simulating = 374
 14.7 Large Knowledge Bases = 374
  14.7.1 Thermodynamics = 375
  14.7.2 Botany = 376
  14.7.3 Chemical Engineering = 377
 14.8 The Future = 378
 14.9 Problems = 379
A Glossary = 381
B QSIM Functions = 385
C Creating and Debugging a QSIM Model = 391
Reference = 397
Index = 411