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

AAAI relies on your generous support through membership and donations. If you find these resources useful, we would be grateful for your support.

AI Magazine Articles

Conference Proceedings Papers

Funding Tutorial

Presidential Addresses

Policy Reports

Symposia Papers

Workshop Papers

AAAI Home Page

Awards

Calendar

Jobs

Meetings

AAAI Press

Resources

AAAI Workshops