Proceedings of the Eighth National Conference on Artificial Intelligence
Sponsored by the Association for the Advancement of Artificial Intelligence
Thomas Dietterich and William Swartout, Program Cochairs
July 29-August 3, 1990, Boston, Massachusetts. Published by The AAAI Press, Menlo Park, California. This proceedings is also available in book and CD format.
Please Note: Abstracts are linked to individual titles, and will appear in a separate browser window. Full-text versions of the papers are linked to the abstract text. Access to full text may be restricted to AAAI members. PDF file sizes may be large!
Contents
Automated Reasoning
Constraint Satisfaction Problems
Complexity of K-Tree Structured Constraint Satisfaction Problems
Eugene C. Freuder, University of New Hampshire / 4
Tree Decomposition with Applications to Constraint Processing
Itay Meiri and Judea Pearl, University of California at Los Angeles; and
Rina Dechter, Technion--Israel Institute of Technology / 10
Solving Large-Scale Constraint-Satisfaction and Scheduling Problems
Using a Heuristic Repair Method
Steven Minton, Andrew B. Philips, and Philip Laird, NASA Ames Research
Center; and Mark D. Johnston, Space Telescope Science Institute / 17
Dynamic Constraint Satisfaction Problems
Sanjay Mittal and Brian Falkenhainer, Xerox Palo Alto Research Center /
25
The Complexity of Constraint Satisfaction in Prolog
Bernard A. Nadel, Wayne State University / 33
An Algebraic Approach to Conflict Resolution in Planning
Qiang Yang, University of Waterloo / 40
Some Applications of Graph Bandwidth to Constraint Satisfaction
Problems
Ramin Zabih, Stanford University / 46
Distributed and Parallel Systems
An Organizational Approach to Adaptive Production Systems
Toru Ishida and Makoto Yokoo, NTT Communications and Information
Processing Laboratories; and Les Gasser, University of Southern California /
52
The Design of a Marker Passing Architecture for Knowledge Processing
Wing Lee and Dan Moldovan, University of Southern California / 59
A Parallel Asynchronous Distributed Production System
James G. Schmolze and Suraj Goel, Tufts University / 65
Distributed Artificial Intelligence
Distributed Truth Maintenance
David Murray Bridgeland and Michael N. Huhns, Microelectronics and
Computer Technology Corporation / 72
DARES: A Distributed Automated REasoning System
S. E. Conry, D. J. MacIntosh, and R. A. Meyer, Clarkson University /
78
A Hierarchical Protocol for Coordinating Mulitagent Behaviors
Edmund H. Durfee and Thomas A. Montgomery, University of Michigan / 86
On Acting Together
Hector J. Levesque and José H. T. Nunes, University of Toronto;
and Philip R. Cohen, SRI International / 94
Negotiation and Conflict Resolution in Non-Cooperative Domains
Gilad Zlotkin and Jeffrey S. Rosenschein, Hebrew University / 100
Evidential Reasoning
Probabilistic Semantics for Cost Based Abduction
Eugene Charniak and Solomon E. Shimony, Brown University / 106
Two Views of Belief: Belief as Generalized Probability and Belief as
Evidence
Joseph Y. Halpern and Ronald Fagin, IBM Almaden Research Center / 112
The Belief Calculus and Uncertain Reasoning
Yen-Teh Hsia, Université Libre de Bruxelles / 120
Symbolic Probabilistic Inference in Belief Networks
Ross D. Shachter and Brendan A. Del Favero, Stanford University; and
Bruce D'Ambrosio, Oregon State University / 126
Planning
An Approach to Reasoning About Continuous Change for Applications in
Planning
Thomas Dean and Greg Siegle, Brown University / 132
Anytime Synthetic Projection: Maximizing the Probability of Goal
Satisfaction
Mark Drummond and John Bresina, NASA Ames Research Center / 138
Incremental, Approximate Planning
Charles Elkan, University of Toronto / 145
Admissible Criteria for Loop Control in Planning
Roy Feldman and Paul Morris, IntelliCorp / 151
Practical Temporal Projection
Steve Hanks, University of Washington / 158
Synthesis of Reactive Plans for Multi-Path Environments
Froduald Kabanza, Université de Liège / 164
Mapping and Retrieval During Plan Reuse: A Validation Structure Based
Approach
Subbarao Kambhampati, Stanford University / 170
A Theory of Plan Modification
Subbarao Kambhampati, Stanford University / 176
Introducing the Tileworld: Experimentally Evaluating Agent
Architectures
Martha E. Pollack, SRI International; and Marc Ringuette, Carnegie
Mellon University / 183
Getting Serious About Parsing Plans: A Grammatical Analysis of Plan
Recognition
Marc Vilain, The MITRE Corporation / 190
The STRIPS Assumption for Planning Under Uncertainty
Michael P. Wellman, Wright-Patterson AFB / 198
ABTWEAK: Abstracting a Nonlinear, Least Commitment Planner
Qiang Yang, University of Waterloo; and Josh D. Tenenberg, University of
Rochester / 204
Search
Search Lessons Learned from Crossword Puzzles
Matthew L. Ginsberg, Michael Frank, Michael P. Halpin, and Mark C.
Torrance, Stanford University / 210
Iterative Broadening
Matthew L. Ginsberg and William D. Harvey, Stanford University / 216
Path-Focused Duplication: A Search Procedure for General Matings
Sunil Issar, Carnegie Mellon University / 221
Consistent Linear Speedups to a First Solution in Parallel State-Space
Search
Vikram A. Saletore and L. V. Kalé, University of Illinois at
Urbana-Champaign / 227
Theorem Proving and Program Synthesis
Inductive Synthesis of Equational Programs
Nachum Dershowitz, University of Illinois; and Eli Pinchover, Bar-Ilan
University / 234
Mechanizing Inductive Reasoning
Emmanuel Kounalis and Michaël Rusinowitch, CRIN / 240
Skolem Functions and Equality in Automated Deduction
William McCune, Argonne National Laboratory / 246
Automatically Generating Universal Attachments Through Compilation
Karen L. Myers, Stanford University / 252
Solving Term Inequalities
Gerald E. Peterson, McDonnell Douglas Corporation / 258
Truth Maintenance Systems
Exploiting Locality in a TMS
Johan de Kleer, Xerox Palo Alto Research Center / 264
Computing Stable Models by Using the ATMS
Kave Eshghi, Hewlett Packard Laboratories / 272
Computing the Extensions of Autoepistemic and Default Logics with a Truth
Maintenance System
Ulrich Junker, GMD; and Kurt Konolige, SRI International / 278
Maintaining Consistency in a Stratified Production System Program
Louiqa Raschid, University of Maryland / 284
Cognitive Modeling
Case-Based Reasoning
Integrating Planning and Acting in a Case-Based Framework
Kristian J. Hammond, Timothy Converse, and Charles Martin, University of Chicago / 292
A Method of Calculating the Measure of Salience in Understanding
Metaphors
Makoto Iwayama, Takenobu Tokunaga, and Hozumi Tanaka, Tokyo Institute of
Technology / 298
Distributed Cases for Case-Based Reasoning; Facilitating Use of Multiple
Cases
Michael Redmond, Georgia Institute of Technology / 304
Validated Retrieval in Case-Based Reasoning
Evangelos Simoudis and James Miller, Brandeis University and Digital
Equipment Corporation / 310
Commonsense Reasoning
Model-Based Diagnosis and Design
Model-Based Diagnosis of Planning Failures
Lawrence Birnbaum, Gregg Collins, Michael Freed, and Bruce Krulwich,
Northwestern University / 318
Characterizing Diagnoses
Johan de Kleer, Xerox Palo Alto Research Center; Alan K. Mackworth,
University of British Columbia; and Raymond Reiter, University of Toronto /
324
Physical Impossibility Instead of Fault Models
Gerhard Friedrich, Georg Gottlob, and Wolfgang Nejdl, Technical
University of Vienna / 331
On the Role of Coherence in Abductive Explanation
Hwee Tou Ng and Raymond J. Mooney, University of Texas at Austin / 337
Abductive and Default Reasoning: A Computational Core
Bart Selman and Hector J. Levesque, University of Toronto / 343
Interaction-Based Invention: Designing Novel Devices from First
Principles
Brian C. Williams, Xerox Palo Alto Research Center / 349
Efficient Diagnosis of Multiple Disorders Based on a Symptom Clustering
Approach
Thomas D. Wu, Massachusetts Institute of Technology / 357
Qualitative Modeling of Physical Systems
QPC: A Compiler from Physical Models into Qualitative Differential
Equations
James Crawford, Adam Farquhar, and Benjamin Kuipers, University of Texas at Austin / 365
Dynamic Across-Time Measurement Interpretation
Dennis DeCoste, University of Illinois / 373
Self-Explanatory Simulations: An Integration of Qualitative and Quantitative
Knowledge
Kenneth D. Forbus, University of Illinois; and Brian Falkenhainer, Xerox
Palo Alto Research Center / 380
Obtaining Quantitative Predictions from Monotone Relationships
Joseph Hellerstein, IBM T. J. Watson Research Center / 388
Reasoning with Multiple Models
Shifting Ontological Perspectives in Reasoning About Physical Systems
Zheng-Yang Liu and Arthur M. Farley, University of Oregon / 395
Qualitative Reasoning with Microscopic Theories
Shankar A. Rajamoney and Sang Hoe Koo, University of Southern California / 401
Approximation Reformulations
Daniel S. Weld, University of Washington / 407
Finding the Average Rates of Change in Repetitive Behavior
Alexander Yeh, Massachusetts Institute of Technology / 413
Education and AI
Towards a System Architecture Supporting Contextualized Learning
Gerhard Fischer, Andreas C. Lemke, and Raymond McCall, University of
Colorado / 420
Backward Model Tracing: An Explanation-Based Approach for Reconstructing
Student Reasoning
Danilo Fum, Università di Trieste; Paolo Giangrandi and Carlo
Tasso, Università di Udine / 426
A Blackboard-based Dynamic Instructional Planner
William R. Murray, FMC Corporate Technology Center / 434
Intelligent Interfaces
Multimedia
Coordinating Text and Graphics in Explanation Generation
Steven K. Feiner and Kathleen R. McKeown, Columbia University / 442
Avoiding Unwanted Conversational Implicatures in Text and Graphics
Joseph Marks and Ehud Reiter, Harvard University / 450
Pointing: A Way Toward Explanation Dialogue
Johanna D. Moore, University of Pittsburgh; and William R. Swartout,
USC/Information Science Institute / 457
Understanding Natural Language with Diagrams
Gordon S. Novak Jr. , University of Texas at Austin, and William C.
Bulko, IBM Corporation / 465
Plan Recognition
Incorporating Default Inferences Into Plan Recognition
Sandra Carberry, University of Delaware / 471
A Cooperative Problem Solving System for User Interface Design
Andreas C. Lemke and Gerhard Fischer, University of Colorado / 479
Models of Plans to Support Communication: An Initial Report
Karen E. Lochbaum and Barbara J. Grosz, Harvard University; and Candace
L. Sidner, Digital Equipment Corporation / 485
A Collaborative Interface for Editing Large Knowledge Bases
Loren G. Terveen and David A. Wroblewski, MCC Human Interface Laboratory / 491
Knowledge Acquisition
Expert System Design Methodologies
An Experiment in Direct Knowledge Acquisition
Peter W. Mullarkey, Schlumberger Laboratory for Computer Science / 498
Parametric Engineering Design: Using Constraint-Based Reasoning
Niall Murtagh and Masamichi Shimura, Tokyo Institute of Technology /
505
Establishing the Coherence of an Explanation to Improve Refinement of an
Incomplete Knowledge Base
Young-Tack Park and David C. Wilkins, University of Illinois / 511
A Design Based Approach to Constructing Computational Solutions to
Diagnostic Problems
D. Volovik, I. A. Zualkernan, and P. E. Johnson, University of
Minnesota; and C. E. Matthews, IBM Corporation / 517
Knowledge Representation
Causality and Introspection
Causal Theories for Nonmonotonic Reasoning
Hector Geffner, IBM T. J. Watson Research Center / 524
Decidable Reasoning in First-Order Knowledge Bases with Perfect
Introspection
Gerhard Lakemeyer, University of Toronto / 531
A Formal Theory of Multiple Agent Nonmonotonic Reasoning
Leora Morgenstern, IBM T. J. Watson Research Center / 538
A Circumscriptive Theory for Causal and Evidential Support
Eunok Paek, Stanford University / 545
Complexity and Expressiveness
The Complexity of Closed World Reasoning and Circumscription
Marco Cadoli and Maurizio Lenzerini, Università di Roma "La
Sapienza" / 550
On the Expressiveness of Networks with Hidden Variables
Rina Dechter, Technion--Israel Institute of Technology / 556
An Optimally Efficient Limited Inference System
Lokendra Shastri and Venkat Ajjanagadde, University of Pennsylvania /
563
It’s Not My Default: The Complexity of Membership Problems in Restricted
Propositional Default Logics
Jonathan Stillman, General Electric Research and Development Center /
571
Connectionism
Connectionism, Rule Following, and Symbolic Manipulation
Robert F. Hadley, Simon Fraser University / 579
A Structured Connectionist Unification Algorithm
Steffen Hölldobler, International Computer Science Institute /
587
Default Representations
Conditional Logics of Normality as Modal Systems
Craig Boutilier, University of Toronto / 594
Nonmonotonicity and the Scope of Reasoning: Preliminary Report
David W. Etherington, AT&T Bell Laboratories; Sarit Kraus and Donald
Perlis, University of Maryland / 600
The Representation of Defaults in Cyc
Ramanathan V. Guha, MCC / 608
The Generalized Theory of Model Preference
Piotr Rychlik, Polish Academy of Sciences / 615
Inheritance
Terminological Cycles in KL-ONE-based Knowledge Representation
Languages
Franz Baader, German Research Center for Artificial Intelligence / 621
On the Complexity of Monotonic Inheritance with Roles
Ramiro A. de T. Guerreiro and Andrea S. Hemerly, IBM Brazil; and Yoav
Shoham, Stanford University / 627
Boolean Extensions of Inheritance Networks
John F. Horty, University of Maryland; and Richmond H. Thomason,
University of Pittsburgh / 633
A Temporal Terminological Logic
Albrecht Schmiedel, Technische Universität Berlin / 640
Representation and Uncertainty
A Maximum Entropy Approach to Nonmonotonic Reasoning
Moisés Goldszmidt and Judea Pearl, University of California at
Los Angeles; and Paul Morris, IntelliCorp / 646
A Hybrid Framework for Representing Uncertain Knowledge
Alessandro Saffiotti, Université Libre de Bruxelles / 653
A Probabilistic Interpretation for Lazy Nonmonotonic Reasoning
Ken Satoh, Institute for New Generation Computer Technology / 659
Probabilities that Imply Certainties
Haim Shvaytser, SRI David Sarnoff Research Center / 665
Architectures
Very Fast Decision Table Execution of Propositional Expert Systems
Robert M. Colomb and Charles Y. C. Chung, CSIRO Division of Information
Technology / 671
The Intelligent Database Interface: Integrating AI and Database
Systems
Don McKay, Timothy Finin and Anthony O'Hare, Unisys Center for Advanced
Information Technology / 677
On the Performance of Lazy Matching in Production Systems
Daniel P. Miranker, David A. Brant, Bernie Lofaso, and David Gadbois,
University of Texas at Austin / 685
A Framework for Investigating Production System Formulations with
Polynomially Bounded Match
Milind Tambe, Carnegie Mellon University; and Paul S. Rosenbloom,
University of Southern California-ISI / 693
A Principled Approach to Reasoning About the Specificity of Rules
John Yen, Texas A&M University / 701
Temporal and Spatial Reasoning
Solving Geometric Constraint Systems
Glenn A. Kramer, University of Sussex and Schlumberger Laboratory for
Computer Science / 708
Weak Representations of Interval Algebras
Gérard Ligozat, Université Paris-Sud / 715
A Qualitative Model for Space
Amitabha Mukerjee and Gene Joe, Texas A&M University / 721
Reasoning about Qualitative Temporal Information
Peter van Beek, University of Waterloo / 728
Machine Learning
Inductive Learning
Myths and Legends in Learning Classification Rules
Wray Buntine, Turing Institute / 736
Learning from Textbook Knowledge: A Case Study
William W. Cohen, Rutgers University / 743
What Should Be Minimized in a Decision Tree?
Usama M. Fayyad and Keki B. Irani, University of Michigan / 749
Generalization with Taxonomic Information
Alan M. Frisch and C. David Page, Jr., University of Illinois / 755
Constructor: A System for the Induction of Probabilistic Models
Robert M. Fung and Stuart L. Crawford, Advanced Decision Systems / 762
Learning Causal Trees from Dependence Information
Dan Geiger, Northrop Research and Technology Corporation; Azaria Paz,
Israel Institute of Technology; and Judea Pearl, University of California at
Los Angeles / 770
Theory Reduction, Theory Revision, and Retranslation
Allen Ginsberg, AT&T Bell Laboratories / 777
A Hybrid Connectionist, Symbolic Learning System
Lawrence O. Hall and Steve G. Romaniuk, University of South Florida /
783
Empirical Studies on the Speed of Convergence of Neural Network Training
Using Genetic Algorithms
Hiroaki Kitano, Carnegie Mellon University / 789
Learning to Coordinate Behaviors
Pattie Maes and Rodney A. Brooks, Massachusetts Institute of Technology / 796
Adding Domain Knowledge to SBL Through Feature Construction
Christopher John Matheus, GTE Laboratories Incorporated / 803
Inductive Learning in Probabilistic Domain
Yoichiro Nakakuki, Yoshiyuki Koseki, and Midori Tanaka, NEC Corporation / 809
Changing the Rules: A Comprehensive Approach to Theory Refinement
Dirk Ourston and Raymond J. Mooney, University of Texas / 815
Knowledge Level and Inductive Uses of Chunking (EBL)
Paul S. Rosenbloom, University of Southern California--ISI; and Jans
Aasman, Rijksuniversiteit Groningen / 821
A Proven Domain-Independent Scientific Function-Finding Algorithm
Cullen Schaffer, Rutgers University / 828
Complementary Discrimination Learning: A Duality Between Generalization and
Discrimination
Wei-Min Shen, MCC / 834
Inductive Learning in a Mixed Paradigm Setting
David B. Skalak and Edwina L. Rissland, University of Massachusetts /
840
Incremental Non-Backtracking Focusing: A Polynomially Bounded Generalization
Algorithm for Version Spaces
Benjamin D. Smith and Paul S. Rosenbloom, University of Southern
California / 848
Two Case Studies in Cost-Sensitive Concept Acquisition
Ming Tan and Jeffrey C. Schlimmer, Carnegie Mellon University / 854
Refinement of Approximate Domain Theories by Knowledge-Based Neural
Networks
Geoffrey G. Towell, Jude W. Shavlik, and Michiel O. Noordewier,
University of Wisconsin, Madison / 861
On Analytical and Similarity-Based Classification
Marc Vilain, Phyllis Koton, and Melissa P. Chase, The MITRE Corporation / 867
Effective Generalization of Relational Descriptions
Larry Watanabe and Larry Rendell, University of Illinois at
Urbana-Champaign / 875
Explaining Temporal Differences to Create Useful Concepts for Evaluating
States
Richard C. Yee, Sharad Saxena, Paul E. Utgoff, and Andrew G. Barto,
University of Massachusetts / 882
Automated Discovery in a Chemistry Laboratory
Jan M. Zytkow, Jieming Zhu, and Abul Hussam, George Mason University /
889
Learning and Problem Solving
Adaptive Search by Explanation-Based Learning of Heuristic Censors
Neeraj Bhatnagar, Siemens Corporate Research; and Jack Mostow, Rutgers
University / 895
Empirical Comparisons of Some Design Replay Algorithms
Brad Blumenthal, University of Texas at Austin / 902
Learning Search Control for Constraint-Based Scheduling
Megan Eskey and Monte Zweben, NASA Ames Research Center / 908
Why PRODIGY/EBL Works
Oren Etzioni, Carnegie Mellon University / 916
Learning Abstraction Hierarchies for Problem Solving
Craig A. Knoblock, Carnegie Mellon University / 923
Extending EBG to Term-Rewriting Systems
Philip Laird and Evan Gamble, NASA Ames Research Center / 929
Operationality Criteria for Recursive Predicates
Stanley Letovsky, Carnegie Mellon University / 936
The Utility of EBL in Recursive Domain Theories
Devika Subramanian and Ronen Feldman, Cornell University / 942
Natural Language
Discourse
Accent and Discourse Context: Assigning Pitch Accent in Synthetic
Speech
Julia Hirschberg, AT&T Bell Laboratories / 952
Structure of Perspectivity: A Case of Japanese Reflexive Pronoun
"zibun"
Yasuhiro Katagiri, NTT Basic Research Laboratories / 958
PRAGMA--A Flexible Bidirectional Dialogue System
John M. Levine, University of Cambridge / 964
Logical Task Modelling for Man-Machine Dialogue
M. D. Sadek, Centre National d'Etudes des
Télécommunications / 970
Interpretation
Integrating Natural Language Processing and Knowledge Based Processing
Rebecca Passonneau, Carl Weir, Tim Finin, and Martha Palmer, Unisys
Corporation / 976
Parsing a Natural Language Using Mutual Information Statistics
David M. Magerman and Mitchell P. Marcus, University of Pennsylvania /
984
Towards Incremental Disambiguation with a Generalized Discrimination
Network
Manabu Okumura and Hozumi Tanaka, Tokyo Institute of Technology / 990
Truly Parallel Understanding of Text
Yeong-Ho Yu and Robert F. Simmons, University of Texas at Austin / 996
Robotics
A Hierarchical Planner that Generates Its Own Hierarchies
Jens Christensen, Stanford University / 1004
Coping with Uncertainty in a Control System for Navigation and
Exploration
Thomas Dean, Kenneth Basye, Robert Chekaluk, Seungseok Hyun, Moises
Lejter and Margaret Randazza, Brown University / 1010
Learning General Completable Reactive Plans
Melinda T. Gervasio, University of Illinois at Urbana-Champaign / 1016
Integrating, Execution, Planning, and Learning in Soar for External
Environments
John E. Laird, University of Michigan; and Paul S. Rosenbloom,
University of Southern California--ISI / 1022
Indexical Knowledge in Robot Plans
Yves Lespérance and Hector J. Levesque, University of Toronto /
1030
Symmetry Constraint Inference in Assembly Planning: Automatic Assembly
Configuration Specification
Yanxi Liu and Robin J. Popplestone, University of Massachusetts at
Amherst / 1038
LOGnets: A Hybrid Graph Spatial Representation for Robot Navigation
Peter K. Malkin and Sanjaya Addanki, IBM T. J. Watson Research Center /
1045
Becoming Increasingly Reactive
Tom M. Mitchell, Carnegie Mellon University / 1051
Vision
Constraints for the Early Detection of Discontinuity from Motion
Michael J. Black and P. Anandan, Yale University / 1060
Generalized Shape Autocorrelation
Andrea Califano and Rakesh Mohan, IBM T. J. Watson Research Center /
1067
Computing Exact Aspect Graphs of Curved Objects: Parametric Surfaces
Jean Ponce, University of Illinois; and David J. Kriegman, Yale
University / 1074
Invited Talks & Panels
The Future of Knowledge Representation
Ronald J. Brachman, AT&T Bell Laboratories / 1082
Rationality and Its Roles in Reasoning
Jon Doyle, Massachusetts Institute of Technology / 1093
Probably Approximately Correct Learning
David Haussler, University of California at Santa Cruz / 1101
Truth Maintenance
David McAllester, Massachusetts Institute of Technology / 1109
Massively Parallel AI
David L. Waltz, Thinking Machines Corporation / 1117
AI and Software Engineering: Will the Twain Ever Meet?
Robert Balzer, University of Southern California--ISI / 1123
AI and Software Engineering--Managing Exploratory Programming
Richard Fikes, Price Waterhouse Technology Centre / 1126
Looking For the AI in Software Engineering: An Applications
Perspective
Mark S. Fox, Carnegie Mellon University / 1128
Developing Software Is Like Talking to Eskimos About Snow
John McDermott, Digital Equipment Corporation / 1129
The Techies Versus the Nontechies: Today’s Two Cultures
Elliot Soloway, University of Michigan / 1134
User Modeling and User Interfaces
Susan T. Dumais, Bellcore / 1135
User Models and User Interfaces: A Case for Domain Models, Task Models, and
Tailorability
James D. Hollan, Bell Communications Research / 1137
User Modeling and User Interfaces
Kathleen R. McKeown, Columbia University / 1138
What’s In a User?
Karen Sparck Jones, University of Cambridge / 1140