Proceedings of the Seventh National Conference on Artificial Intelligence
Sponsored by the Association for the Advancement of Artificial Intelligence
Tom M. Mitchell and Reid G. Smith, Program Cochairs
August 21-26, 1988, Saint Paul, Minnesota. 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
AI and Education
Facilitating Self-Education by Questioning Assumptive Reasoning / 2
Robert Farrell, Yale University
Automated Reasoning
Automatic Programming
Integrating Multiple Sources of Knowledge Into Designer-Soar, an Automatic
Algorithm Designer / 8
David Steier and Allen Newell, Carnegie Mellon University
Invariant Logic. A Calculus for Problem Reformulation / 14
Michael R. Lowry, Stanford University and Kestrel Institute
Being Suspicious: Critiquing Problem Specifications / 19
Stephen Fickas and P. Nagarajan, University of Oregon
Dominic II: Meta-Level Control in Iterative Redesign / 25
Mark F. Orelup, John R. Dixon and Paul R. Cohen, University of
Massachusetts; Melvin K. Simmons, General Electric Corporate Research and
Development
Constraints
FRM: An Intelligent Assistant for Financial Resource Management / 31
Andrew Gelman, Susan Altman, Matt Pallakoff, Ketan Doshi, Catherine
Manago, Thomas C. Rindfleisch and Bruce G. Buchanan, Stanford University
Belief Maintenance in Dynamic Constraint Networks / 37
Rina Dechter, University of California, Los Angeles; Avi Dechter,
California State University, Northridge
Planning
Prevention Techniques for a Temporal Planner / 43
John C. Hogge, Texas Instruments
An Analysis of Time-Dependent Planning / 49
Thomas Dean and Mark Boddy, Brown University
Extending Conventional Planning Techniques to Handle Actions with
Context-Dependent Effects / 55
Edwin P. D. Pednault, AT&T Bell Laboratories
Goals as Parallel Program Specifications / 60
Leslie Pack Kaelbling, SRI International and Stanford University
Predictability Versus Responsiveness: Coordinating Problem Solvers in
Dynamic Domains / 66
Edmund H. Durfee and Victor R Lesser, University of Massachusetts
Intelligent Real-Time Monitoring / 72
Thomas J. Laffey, Scott M. Weitzenkamp, Jackson Y. Read, Simon A. Kao
and James L. Schmidt, Lockheed Artificial Intelligence Center
Reactive Plan Revision / 77
Peng Si Ow, Stephen F. Smith and Alfred Thirlez, Carnegie Mellon
University
Integrating Planning, Execution and Monitoring / 83
Jose A. Ambros-lngerson, University of California, Irvine; Sam Steel,
University of Essex
Reasoning about Action Using a Possible Models Approach / 89
Marianne Winslett, University of Illinois
A Theory of Debugging Plans and Interpretations / 94
Reid G. Simmons, Massachusetts Institute of Technology
Plan Abstraction Based on Operator Generalization / 100
John S. Anderson and Arthur M. Farley, University of Oregon
Geometric Reasoning and Organized Optimization for Automated Process
Planning / 105
Yasuyuki Maeda and Katsuya Shinohara, NEC Corporation
Rule-Based Reasoning
Reasoning Under Varying and Uncertain Resource Constraints / 111
Eric J. Horvitz, Stanford University
Conflict Resolution in Fuzzy Forward-Chaining Production Systems / 117
James Bowen, North Carolina State University; Jianchu Kang, Beijing
Institute of Aeronautics and Astronautics
Search
Parallel Best-First Search of State-Space Graphs: A Summary of Results / 122
Vipin Kumar, K. Ramesh and V. Nageshwara Rao, University of Texas at
Austin
Distributed Tree Search and Its Application to Alpha-Beta Pruning / 128
Chris Ferguson and Richard E. Korf, University of California, Los
Angeles
Some Experiments with Case-Based Search / 133
Steven Bradtke and Wendy G. Lehnert, University of Massachusetts
Real-Time Heuristic Search: New Results / 139
Richard E. Korf, University of California, Los Angeles
An Exact Best-First Search Procedure for the Constrained Rectangular
Guillotine Knapsack Problem / 145
K. V. Viswanathan and A. Bagchi, Indian Institute of Management Calcutta
Tree-Clustering Schemes for Constraint-Processing / 150
Rina Dechter and Judea Pearl, University of California, Los Angeles
A Rearrangement Search Strategy for Determining Propositional
Satisfiability / l55
Ramin Zabih, Stanford University; David McAllester, Cornell University
Theorem Proving
Using Specialists to Accelerate General Reasoning / 161
Stephanie A. Miller and Lenhart K. Schubert, University of Alberta
Goal-Directed Equation Solving / 166
Nachum Dershowitz and G. Sivakumar, University of Illinois at Urbana-
Champaign
Tableau-Based Theorem Proving in Normal Conditional Logics /
171
Chris Groeneboer and James P. Delgrande, Simon Fraser University
A General Proof Method for Modal Predicate Logic without the Barcan
Formula / 177
Peter Jackson, McDonnell Douglas Research Laboratories; Han Reichgelt,
Nottingham University
Truth Maintenance Systems
An Efficient ATMS for Equivalence Relations / 182
Caroline N. Koff, Hewlett Packard; Nicholas S. Flann and Thomas G.
Dietterich, Oregon State University
A General Labeling Algorithm for Assumption-Based Truth Maintenance / 188
Johan de Kleer, Xerox Palo Alto Research Center
Focusing the ATMS / 193
Kenneth D. Forbus, University of Illinois; Johan de Kleer, Xerox Palo
Alto Research
Massively Parallel Assumption-Based Truth Maintenance / 199
Michael Dixon, Xerox Palo Alto Research Center and Stanford University;
Johan de Kleer, Xerox Palo Alto Research Center
Uncertainty
Evidential Reasoning Using DELIEF / 205
Debra K. Zarley, Yen-Teh Hsia and Glenn
Shafer, University of Kansas
Belief Maintenance: An Integrated Approach to Uncertainty Management / 210
Kathryn B. Laskey, Decision Science Consortium, Inc.; Paul E. Lehner,
George Mason University
A Note on Probabilistic Logic / 215
Mary McLeish, University of Guelph
Cognitive Modeling
Learning a Second Language / 222
Steven L. Lytinen and Carol E. Moon, University of Michigan
Ethical Understanding: Recognizing and Using Belief Conflict in Narrative
Processing / 227
John F. Reeves, University of California, Los Angeles
A Computational Account of Basic Level and Typicality Effects / 233
Douglas H. Fisher, Vanderbilt University
Waiting on Weighting: A Symbolic Least Commitment Approach /
239
Kevin D. Ashley and Edwina L. Rissland, University of Massachusetts
Resolving Goal Conflicts via Negotiation / 245
Katia P. Sycara, Carnegie Mellon University
Evaluating Explanations / 251
David B. Leake, Yale University
Reasoning about Evidence in Causal Explanations / 256
Phyllis Koton, Massachusetts Institute of Technology
Common Sense Reasoning
Qualitative Reasoning
MINIMA: A Symbolic Approach to Qualitative Algebraic Reasoning / 264
Brian C. Williams, Massachusetts Institute of Technology
A Qualitative Approach to Mechanical Constraint / 270
Paul Nielsen, University of Illinois at Urbana-Champaign
Global Filters for Qualitative Behaviors / 275
Peter Struss, Siemens Corporation
Generating Global Behaviors Using Deep Knowledge of Local Dynamics / 280
Kenneth Man-Kam Yip, Massachusetts Institute of Technology
Non-Intersection of Trajectories in Qualitative Phase Space: A Global
Constraint for Qualitative Simulation /
286
Wood W. Lee and Benjamin J. Kuipers, University of Texas at Austin
Exaggeration / 291
David S. Weld, University of Washington
Qualitative Reasoning at Multiple Resolutions / 296
Seshashayee S. Murthy, IBM Thomas J. Watson Research Center
Setting up Large-Scale Qualitative Models / 301
Brian Falkenhainer and Kenneth D. Forbus, University of Illinois at
Urbana-Champaign
Formal Basis for Common Sense Abstraction of Dynamic Systems / 307
Yumi Iwasaki and Inderpal Bhandari, Carnegie Mellon University
Causal Ordering in a Mixed Structure / 313
Yumi Iwasaki, Carnegie Mellon University
Controlling Qualitative Resolution / 319
Jean-Luc Dormoy, Electricite de France Research Centre
Using Incomplete Quantitative Knowledge in Qualitative Reasoning /
324
Benjamin Kuipers and Daniel Berleant, University of Texas at Austin
Design
Assembling a Device / 330
Jean-Luc Dormoy, Electricite de France Research Centeri Olivier Raiman,
IBM Scientific Center
Upgrading Design Systems / 336
Sarosh Talukdar, Jim Rehg, Rob Woodbury and Alberto Elfes, Carnegie
Mellon University
Function Sharing in Mechanical Design / 342
Karl T. Ulrich and Warren P. Seering, Massachusetts Institute of
Technology
From Kinematics to Shape: An Approach to Innovative Design / 347
Leo Joskowicz, Courant Institute; Sanjaya Addanki, IBM Thomas J. Watson
Research Center
Diagnosis
The Induction of Fault Diagnosis Systems from Qualitative Models / 353
D. A. Pearce, The Turing Institute
Design for Testability / 358
Peng Wu, Massachusetts Institute of Technology
Specialized Strategies: An Alternative to First Principles in Diagnostic
Problem Solving / 364
Nancy E. Reed, Elizabeth R. Stuck and James B. Moen, University of
Minnesota
Robust Operative Diagnosis as Problem Solving in a Hypothesis Space / 369
Kathy H. Abbott, NASA Langley Research Center
Knowledge Representation
How to Print a File: An Expert System Approach to Software Knowledge
Representation / 380
Peter G. Selfridge, AT&T Bell Laboratories
Representing Genetic Information with Formal Grammars / 386
David B. Searls, Unisys Paoli Research Center
Overview of an Approach to Representation Design / 392
Jeffrey Van Baalen and Randall Davis, Massachusetts Institute of
Technology
Mechanisms for Reasoning about Sets / 398
Michael P. Wellman and Reid G. Simmons, Massachusetts Institute of
Technology
Inheritance
A Deductive Pattern Matcher / 403
Robert M. MacGregor, USC/Information Sciences Institute
A Model and Representation for Type Information and Its Use in Reasoning
with Defaults / 409
Lin Padgham, Linkoping University
Beyond ISA: Structures for Plausible Inference in Semantic Networks /
415
Paul R. Cohen and Cynthia L. Loiselle, University of Massachusetts
Tractable Theories of Multiple Defeasible Inheritance in Ordinary
Nonmonotonic Logics / 421
Brian A. Haugh, Martin Marietta Laboratories
Mixing Strict and Defeasible Inheritance / 427
John F. Horty, Carnegie Mellon University and University of Maryland;
Richmond H. Thomason, University of Pittsburgh
Nonmonotonlc Inheritance and Generic Reflexives / 433
David S. Touretzky, Carnegie Mellon University; Richmond H. Thomason,
University of Pittsburgh
Nonmonotonlc Logic
Hierarchic Autoepistemic Theories for Nonmonotonic Reasoning / 439
Kurt Konolige, SRI International
On the Relationship Between Logic Programming and Nonmonotonlc Reasoning / 444
Teodor C. Przymusinski, University of Texas
On the Logic of Defaults / 449
Hector Geffner, University of California, Los Angeles
Compiling Circumscriptive Theories into Logic Programs: Preliminary
Report / 455
Michael Gelfond, University of Texas at El Paso; Vladimir Lifschitz,
Stanford University
On Reducing Parallel Circumscription / 460
Li Yan Yuan and Cheng Hui Wang, University of Southwestern Louisiana
Some Computational Aspects of Circumscription / 465
Phokion G. Kolaitis, Stanford University; Christos H. Papadimitriou,
University of California, San Diego
A Circumscriptive Theorem Prover: Preliminary Report / 470
Matthew L. Ginsberg, Stanford University
Nonstandard Logics
Investigations into a Theory of Knowledge Base Revision: Preliminary Report / 475
Mukesh Dalal, Rutgers University
A Logic for Hypothetical Reasoning
Anthony J. Bonner, Rutgers University
Adding Number Restrictions to a Four-Valued Terminological Logic / 485
Peter F. Patel-Schneider, Schlumberger Palo Alto Research
Normal Multimodal Logics / 491
Laurent Catach, IBM Paris Scientific Center
Temporal Reasoning
The Persistence of Derived Information / 496
Karen L. Myers and David E. Smith, Stanford University
Representing and Computing Temporally Scoped Beliefs / 501
Steve Hanks, Yale University
Stable Closures, Defeasible Logic, and Contradiction Tolerant Reasoning / 506
Paul Morris, IntelliCorp
Satisfying First-Order Constraints about Time Intervals / 512
Peter B. Ladkin, Kestrel Institute
Why Things Go Wrong: A Formal Theory of Causal Reasoning / 518
Leora Morgenstern and Lynn Andrea Stein, Brown University
Probabilistic Temporal Reasoning / 524
Thomas Dean and Keiji Kanazawa, Brown University
Learning and Knowledge Acquisition
Learning
The Utility of Difference-Based Reasoning / 530
Brian Falkenhainer, University of Illinois at Urbana-Champaign
Learning from Opportunities: Storing and Re-using Execution-Time
Optimizations / 536
Krlstian Hammond, Tim Converse and Mitchell Marks, University of Chicago
Explanation-Based Indexing of Cases /
541
Ralph Barletta and William Mark, Lockheed Artificial Intelligence Center
Parsing to Learn Fine Grained Rules / 547
Subrata Roy and Jack Mostow, Rutgers University
Simulation-Assisted Inductive Learning / 552
Bruce G. Buchanan, John Sullivan and Tze-Pin Cheng, Stanford University;
Scott H. Clearwater, Los Alamos National Laboratory and Stanford University
The Automatic Acquisition of Proof Methods / 558
Kurt Ammon, University of Hamburg
Analytic Learning
Quantitative Results Concerning the Utility of Explanation-Based
Learning / 564
Steven Minton, Carnegie Mellon University
Approximate Theory Formation: An Explanation-Based Approach / 570
Thomas Ellman, Columbia University
IMEX: Overcoming Intractability in Explanation Based Learning / 575
Michael S. Braverman and Stuart J. Russell, University of California,
Berkeley
Some Philosophical Problems with Formal Learning Theory / 580
Jonathan Amsterdam, Massachusetts Institute of Technology
Knowledge-Base Reduction: A New Approach to Checking Knowledge Bases for
Inconsistency and Redundancy / 585
Allen Ginsberg, AT&T Bell Laboratories
Theory Revision via Prior Operationalization / 590
Allen Ginsberg, AT&T Bell Laboratories
Empirical Learning
Credit Assignment in Genetic Learning Systems / 596
John J. Grefenstette, Naval Research Laboratory
Perceptron Trees: A Case Study in Hybrid Concept Representations / 601
Paul E. Utgoff, University of Massachusetts
Bayesian Classification / 607
Peter Cheeseman, RIACS; Matthew Self, Jim Kelly, Will Taylor and Don
Freeman, Sterling Software; John Stutz, NASA
Combining Symbolic Learning Techniques and Statistical Regression
Analysis / 612
Carlo Berzuini, University of Pavia
Recovery from Incorrect Knowledge in Soar / 618
John Laird, University of Michigan
Formal Results in Learning
Inferring Probabilistic Theories from Data / 624
Edwin P. D. Pednault, AT&T Bell Laboratories
Functionality in Neural Nets / 629
L. G. Valiant, Harvard University
Learning Complicated Concepts Reliably and Usefully / 635
Ronald L. Rivest and Robert Sloan, Massachusetts Institute of Technology
Tree-Structured Bias / 641
Stuart J. Russell, University of California, Berkeley
Knowledge Acquisition
Knowledge Base Refinement Using Apprenticeship Learning Techniques / 646
David C. Wilkins, University of Illinois at Urbana-Champaign
Machine Architectures and Computer Languages for AI
Towards a Virtual Parallel Inference Engine / 654
Howard E. Shrobe, John G. Aspinall and Neil L. Mayle, Symbolics
Cambridge Research Center
Generality versus Specificity: An Experience with AI and OR Techniques / 660
Pascal Van Hentenryck, European Computer-Industry Research Center;
Jean-Philippe Carillon, CEGOS
Knowledge-Based Real-Time Control: A Parallel Processing Perspective / 665
D. D. Sharma and N. S. Sridharan, FMC Corporation
Architectures and Languages for Problem Solving
Tuning a Blackboard-Based Application: A Case Study: Using GBB / 671
Daniel D. Corkill and Kevin Q. Gallagher, University of Massachusetts
A Tree Representation for Parallel Problem Solving / 677
L. V. Kale, University of Illinois at Urbana-Champaign
Parallel Hardware for Constraint Satisfaction / 682
Michael J. Swain and Paul R Cooper, University of Rochester
Production Systems
Suitability of Message Passing Computers for Implementing Production
Systems / 687
Anoop Gupta, Stanford University; Milind Tambe, Carnegie Mellon
University
Comparison of the Rete and Treat Production Matchers for Soar / 693
Pandurang Nayak and Anoop Gupta, Stanford University; Paul Rosenbloom,
USC/Information Sciences Institute
Optimizing Rules in Production System Programs
Toru Ishida, NTT Communications and Information Processing Laboratories
/ 699
The Challenge of Real-Time Process Control for Production Systems / 705
Franz Barachini and Norbert Theuretzbacher, ALCATEL Austria
Natural Language
Syntax
Representing Pronouns in Logical Form: Computational Constraints and
Linguistic Evidence / 712
Mary P. Harper, Brown University
Principle-Based Interpretation of Natural Language Quantifiers / 718
Samuel S. Epstein, Bell Communications Research
Speech
The Integration of Unification-Based Syntax/Semantics and Memory-Based
Pragmatics for Real-Time Understanding of Noisy Continuous Speech Input / 724
Hideto Tomabechi and Masaru Tomita, Carnegie Mellon University
Using Dialog-Level Knowledge Sources to Improve Speech Recognition / 729
Alexander G. Hauptmann, Sheryl R. Young and Wayne H. Ward, Carnegie Mellon
University
Data-Driven Execution of Multi-Layered Networks for Automatic Speech
Recognition / 734
Renato De Mori, Yoshua Bengio and Regis Cardin, McGill University
Dialogue
Acquiring Lexical Knowledge from Text: A Case Study / 739
Paul Jacobs and Uri Zemik, General Electric Research and Development
Center
The Interpretation of Temporal Relations in Narrative / 745
Fei Song and Robin Cohen, University of Waterloo
Beyond Semantic Ambiguity / 751
Galina Datskovsky Moerdler and Kathleen R. McKeown, Columbia University
Exploiting User Expertise in Answer Expression / 756
David N. Chin, University of Hawaii at Manoa
Robotics
Compliance Viewed as Programming a Damped Spring / 762
Stephen J. Buckley, IBM Thomas J. Watson Research
Reasoning about Grasping / 768
S. A. Stansfield, Sandia National Laboratories
A Robust, Qualitative Method for Robot Spatial Learning / 774
Benjamin J. Kuipers and Yung-Tai Byun, University of Texas at Austin
Subassembly Stability / 780
Nico Boneschanscher and Hans van der Drift, Delft University; Stephen J.
Buckley and Russell H. Taylor, IBM Thomas J. Watson Research Center
Integrated Robotics
Inferring Ignorance from the Locality of Visual Perception / 786
Ernest Davis, New York University
Connectionist Networks for Learning Coordinated Motion in Autonomous
Systems / 791
Jahir Pabon and David Gossard, Massachusetts Institute of Technology
Situated Vision in a Dynamic World: Chasing Objects / 796
Ian Douglas Horswill and Rodney Allen Brooks, Massachusetts Institute of
Technology
User Interfaces
Knowledge-Based Spreadsheets / 802
Gerhard Fischer and Christian Rathke, University of Colorado
Automatic Construction of User-lnterface Displays / 808
Yigal Arens, Lawrence Miller, Stuart C. Shapiro and Norman K.
Sondheimer, USC/Information Sciences Institute
Specification by Reformulation: A Paradigm for Building Integrated User
Support Environments / 814
John Yen, Robert Neches and Michael DeBellis, USC/Information Sciences
Institute
Multi-Modal References in Human-Computer Dialogue / 819
Jeannette G. Neal, Zuzana Dobes, Keith E. Bettinger and Jong S. Byoun,
Calspan-UB Research Center
Vision
On the Extraction of Shape Information from Shading / 826
Alex Pentland, Massachusetts Institute of Technology
Feature Recognition Using Correlated Information Contained in Multiple
Neighborhoods / 831
Andrea Califano, IBM Thomas J. Watson Research Center
Performance of a System to Locate Address Blocks on Mail Pieces / 837
Ching-Huei Wang, Paul W. Palumbo, and Sargur N. Srihari, State University
of New York at Buffalo
Invited Talks and Panels
What Is the Computational Power of the Brain
Terrence Sejnowsky, Johns Hopkins University
Computer Vision: From Ad Hocs to Sciences
Takeo Kanade, Carnegie Mellon University
Exploiting Task Structure to Automate Knowledge Acquisition
John McDermott, Digital Equipment Corporation
Panel: Results from a Study of the First Wave of Expert System Applications
to Business
Edward Feigenbaum, Stanford University
Presidential Address--Towards a Theory of Knowledge
Raj Reddy, Carnegie Mellon University
In Search of the Real World: Practical Utility of AI
Earl Sacerdoti, SoftTouch Systems
Panel: Where We Are and Where We Are Going
Howard Shrobe, Symbolics
Physically-Based Modeling for Vision and Graphics
Andrew Witkln, Schlumberger Palo Alto Research
Challenges for AI in Future CAD/CAM Systems
David Gossard, Massachusetts Institute of Technology
Future Intelligent Information Systems: AI and Database Technologies Working
Together / 844
Michael L. Brodie, GTE Laboratories Incorporated
How to Draw Three People in a Botanical Garden / 846
Harold Cohen, University of California, San Diego
Analog VLSI Models of Neural Systems
Carver Mead, California Institute of Technology