Sponsored by the Association for the Advancement of Artificial Intelligence

Kenneth Forbus and Howard Shrobe, Program Cochairs

July 13–17, 1987, Seattle, Washington. 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 Architectures

Recent Developments in Butterfly(TM) Lisp / 2
Donald C. Allen, Seth A. Steinberg, and Lawrence A. Stabile, BBN Advanced Computers, Inc.

CCLISP(TM) on the iPSC(TM) Concurrent Computer / 7
David Billstrom and Joseph Brandenburg, Intel Scientific Computers; and John Teeter, Gold Hill Computers

A Parallel Resolution Procedure Based on Connection Graph / 13
P. Daniel Cheng, Advanced Information Services, Inc. and J. Y. Juang, Northwestern University

Achieving Flexibility, Efficiency, and Generality in Blackboard Architectures / 18
Daniel D. Corkill, Kevin Q. Gallagher, and Philip M. Johnson, University of Massachusetts

Forward Chaining Logic Programming with the ATMS / 24
Nicholas S. Flann, Thomas G. Dietterich, and Dan R. Corpron, Oregon State University

Integrating Diverse Reasoning Methods in the BB1 Blackboard Control Architecture / 30
M. Vaughan Johnson, Jr., and Barbara Hayes-Roth, Stanford University

A Multiprocessor Architecture for Production System Matching / 36
Michael A. Kelly and Rudolph E. Seviora, University of Waterloo

TREAT: A Better Match Algorithm for AI Production Systems / 42
Daniel P. Miranker, University of Texas at Austin

Joshua: Uniform Access to Heterogeneous Knowledge Structures, or, Why Joshing Is Better than Conniving or Planning / 48
Steve Rowley, Howard Shrobe, and Robert Cassels, Symbolics Cambridge Research Center and Walter Hamscher, MIT Artificial Intelligence Laboratory

CP as a General-Purpose Constraint-Language / 53
Vijay A. Saraswat, Carnegie Mellon University and Carnegie Group Inc.

Non-Deterministic Lisp with Dependency-Directed Backtracking / 59
Ramin Zabih, David McAllester, and David Chapman, MIT Artificial Intelligence Laboratory

AI and Education

From Intelligent Tutoring to Computerized Psychotherapy / 66
David Servan-Schreiber, Carnegie Mellon University and Western Psychiatric Institute and Clinic

An Intelligent Tutoring System for Interpreting Ground Tracks / 72
Kathleen Swigger, Hugh Burns, Harry Loveland, and Terresa Jackson, Air Force Human Resources Laboratory, Brooks Air Force Base

Plan Inference and Student Modeling in ICAI / 77
Y. M. Visetti, Universite Paris-Sud and P. Dague, IBM Research Center, Paris

Building a Community Memory for Intelligent Tutoring Systems / 82
Beverly Woolf, University of Massachusetts and Pat Cunningham, Hartford Graduate Center

Automated Reasoning

A Model of Two-Player Evaluation Functions / 90
Bruce Abramson, Columbia University and University of California, Los Angeles and Richard E. Korf, University of California, Los Angeles

Proof Analogy in Interactive Theorem Proving: A Method to Express and Use It Via Second Order Pattern Matching / 95
Thierry Boy de la Tour and Ricardo Caferra, LIFIA

Comparing Minimax and Product in a Variety of Games / 100
Ping-Ching Chi and Dana S. Nau, University of Maryland

Removing Redundancies in Constraint Networks / 105
Avi Dechter, California State University and University of California, Los Angeles and Rina Dechter, Hughes Research Laboratories and University of California, Los Angeles

Computational Costs versus Benefits of Control Reasoning / 110
Alan Garvey, Craig Cornelius, and Barbara Hayes-Roth, Stanford University

Filming a Terrain under Uncertainty Using Temporal and Probabilistic Reasoning / 116
Raymond D. Gumb, University of Lowell

On the Expressiveness of Rule-Based Systems for Reasoning with Uncertainty / 121
David E. Heckerman and Eric J. Horvitz, Stanford University

Inferring Formal Software Specifications from Episodic Descriptions / 127
Van E. Kelly and Uwe Nonnenmann, AT&T Bell Laboratories

Real-Time Heuristic Search: First Results / 133
Richard E. Korf, University of California, Los Angeles

Reasoning in the Presence of Inconsistency / 139
Fangzhen Lin, Hua Chiao University

A New Structural Induction Scheme for Proving Properties of Mutually Recursive Concepts / 144
Peiya Liu, Siemens Research and Technology Laboratories and Ruey-Juin Chang, University of Texas at Austin

Synthesizing Algorithms with Performance Constraints / 149
Robert D. McCartney, Brown University

The Deductive Synthesis of Imperative LISP Programs / 155
Zohar Manna, Stanford University; and Richard Waldinger, SRI International

Path Dissolution: A Strongly Complete Rule of Inference / 161
Neil V. Murray, State University of New York at Albany and Erik Rosenthal, Wellesley College

Revised Dependency-directed Backtracking for Default Reasoning / 167
Charles J. Petrie, Jr., Microelectronics and Computer Technology Corporation

Efficiency Analysis of Multiple-Context TMSs in Scene Representation / 173
Gregory M. Provan, Oxford University

A Parallel Implementation of Iterative-Deepening-A* / 178
V. Nageshwara Rao, Vipin Kumar, and K. Ramesh, University of Texas at Austin

Foundations of Assumption-Based Truth Maintenance Systems: Preliminary Report / 183
Raymond Reiter, University of Toronto and Johan de Kleer, Xerox PARC

Planning

Reasoning about Exceptions during Plan Execution Monitoring / 190
Carol A. Broverman and W. Bruce Croft, University of Massachusetts

Incremental Causal Reasoning / 196
Thomas Dean and Mark Boddy, Brown University

An Investigation into Reactive Planning in Complex Domains / 202
R. James Firby, Yale University

On Stratified Autoepistemic Theories / 207
Michael Gelfond, University of Texas at El Paso

Possible Worlds and the Qualification Problem / 212
Matthew L. Ginsberg and David E. Smith, Stanford University

Simple Causal Minimizations for Temporal Persistence and Projection / 218
Brian A. Haugh, Martin Marietta Laboratories

Using Goal Interactions to Guide Planning / 224
Caroline Hayes, Carnegie Mellon University

Compiling Plan Operators from Domains Expressed in Qualitative Process Theory / 229
John C. Hogge, University of Illinois at Urbana-Champaign

Models of Axioms for Time Intervals / 234
Peter Ladkin, Kestrel Institute

Localized Representation and Planning Methods for Parallel Domains / 240
Amy L. Lansky, SRI International and Stanford University and David S. Fogelsong, Stanford University

A Model for Concurrent Actions Having Temporal Extent / 246
Richard N. Pelavin, Philips Laboratories; and James F. Allen, University of Rochester

The Consistent Labeling Problem in Temporal Reasoning / 251
Edward P. K. Tsang, University of Essex

The Satisfiability of Temporal Constraint Networks / 256
Raul E. Valdes-Perez, Carnegie Mellon University

Validating Generalized Plans in the Presence of Incomplete Information / 261
Marianne Winslett, Stanford University

Cognitive Modeling

Pengi: An Implementation of a Theory of Activity / 268
Philip E. Agre and David Chapman, MIT Artificial Intelligence Laboratory

Compare and Contrast: A Test of Expertise / 273
Kevin D. Ashley and Edwina L. Rissland, University of Massachusetts

Modular Learning in Neural Networks / 279
Dana H. Ballard, University of Rochester

Reducing Indeterminism in Consultation: A Cognitive Model of User/Librarian Interactions / 285
Hsinchun Chen and Vasant Dhar, New York University

A Mechanism for Early Piagetian Learning / 290
Gary L. Drescher, MIT Artificial Intelligence Laboratory

Rules for the Implicit Acquisition of Knowledge about the User / 295
Robert Kass and Tim Finin, University of Pennsylvania

Case-Based Problem Solving with a Large Knowledge Base of Learned Cases / 301
Wendy G. Lehnert, University of Massachusetts

Material Handling: A Conservative Domain for Neural Connectivity and Propagation / 307
H. Van Dyke Parunak, James Kindrick, and Bruce Irish, Industrial Technology Institute

AQUA: Asking Questions and Understanding Answers / 312
Ashwin Ram, Yale University

Information Retrieval from Never-Ending Stories / 317
Lisa F. Rau, General Electric Company

Analogical Processing: A Simulation and Empirical Corroboration / 322
Janice Skorstad, Brian Falkenhainer, and Dedre Gentner, University of Illinois at Urbana-Champaign

Goal-Based Generation of Motivational Expressions in a Learning Environment / 327
Ingrid Zukerman, Monash University

Default Reasoning

Incremental Inference: Getting Multiple Agents to Agree on What to Do Next / 334
Gary C. Borchardt, California Institute of Technology

An Approach to Default Reasoning Based on a First-Order Conditional Logic / 340
James P. Delgrande, Simon Fraser University

Counterfactual Reasoning with Direct Models / 346
Mark Derthick, Carnegie Mellon University

More on Inheritance Hierarchies with Exceptions: Default Theories and Inferential Distance / 352
David W. Etherington, AT&T Bell Laboratories

A Skeptical Theory of Inheritance in Nonmonotonic Semantic Networks / 358
John F. Horty, University of Maryland; Richmond H. Thomason, University of Pittsburgh; and David S. Touretzky, Carnegie Mellon University

Circumscriptive Theories: A Logic-Based Framework for Knowledge Representation, Preliminary Report / 364
Vladimir Lifschitz, Stanford University

Embracing Causality in Formal Reasoning / 369
Judea Pearl, University of California, Los Angeles

The Logic of Representing Dependencies by Directed Graphs / 374
Judea Pearl and Thomas Verma, University of California, Los Angeles

Default Reasoning through Belief Revision Strategy / 380
Chern H. Seet, Information Technology Institute

A Theory of Default Reasoning / 385
Wlodek W. Zadrozny, IBM T. J . Watson Research Center

Knowledge Representation

The Goal/Subgoal Knowledge Representation for Real-Time Process Monitoring / 394
James R. Allard and William F. Kaemmerer, Honeywell

Partial Compilation of Strategic Knowledge / 399
Russ B. Altman and Bruce G. Buchanan, Stanford University

Representing Databases in Frames / 405
Ey-Chih Chow, Hewlett-Packard Laboratories

Intention = Choice + Commitment / 410
Philip R. Cohen, SRI International and Hector J. Levesque, University of Toronto

TAXI: A Taxonomic Assistant / 416
Thomas Y. Galloway, USC-Information Sciences Institute

Complexity in Classificatory Reasoning / 421
Ashok Goel, N. Soundararajan, and B. Chandrasekaran, Ohio State University

All I Know: An Abridged Report / 426
Hector J. Levesque, University of Toronto

Algorithm Synthesis through Problem Reformulation / 432
Michael R. Lowry, Stanford Artificial Intelligence Laboratory and Kestrel Institute

Curing Anomalous Extensions / 437
Paul Morris, IntelliCorp

Semantically Sound Inheritance for a Formally Defined Frame Language with Defaults / 443
Robert Nado and Richard Fikes, IntelliCorp

Assimilation: A Strategy for Implementing Self-Reorganizing Knowledge Bases / 449
Jane Terry Nutter, Virginia Polytechnic Institute and State University

Machine Learning and Knowledge Acquisition

Learning to Control a Dynamic Physical System / 456
Margaret E. Connell and Paul E. Utgoff, University of Massachusetts

Improving Inference through Conceptual Clustering / 461
Douglas Fisher, University of California, Irvine

Learning Conjunctive Concepts in Structural Domains / 466
David Haussler, University of California, Santa Cruz

An Experimental Comparison of Knowledge Engineering for Expert Systems and for Decision Analysis / 471
Max Henrion, Carnegie Mellon University and Daniel R. Cooley, University of Massachusetts

Formulating Concepts According to Purpose / 477
Smadar T. Kedar-Cabelli, Rutgers University

Defining Operationality for Explanation-Based Learning / 482
Richard M. Keller, Rutgers University

A KNACK for Knowledge Acquisition / 488
Georg Klinker, Casey Boyd, Serge Genetet, and John McDermott, Carnegie Mellon University

PROLEARN: Towards a Prolog Interpreter that Learns / 494
Armand E. Prieditis and Jack Mostow, Rutgers University

Knowledge Level Learning in Soar / 499
Paul S. Rosenbloom, Stanford University; John E. Laird, University of Michigan; and Allen Newell, Carnegie Mellon University

A Declarative Approach to Bias in Concept Learning / 505
Stuart J. Russell, University of California, Berkeley and Benjamin N. Grosof, Stanford University

Learning and Representation Change / 511
Jeffrey C. Schlimmer, University of California, Irvine

BAGGER: An EBL System that Extends and Generalizes Explanations / 516
Jude W. Shavlik and Gerald F. DeJong, University of Illinois at Urbana

Optimizing the Predictive Value of Diagnostic Decision Rules / 521
Sholom M. Weiss, Rutgers University; Robert S. Galen, Cleveland Clinic Foundation; and Prasad V. Tadepalli, Rutgers University

Natural Language

Interpreting Clues in Conjunction with Processing Restrictions in Arguments and Discourse / 528
Robin Cohen, University of Waterloo

UNITRAN: An Interlingual Approach to Machine Translation / 534
Bonnie Dorr, MIT Artificial Intelligence Laboratory

Recovering from Erroneous Inferences / 540
Kurt P. Eiselt, University of California, Irvine

Interpretation in Generation / 545
Eduard H. Hovy, USC-Information Sciences Institute

Word-Order Variation in Natural Language Generation / 550
Aravind K. Joshi, University of Pennsylvania

Porting and Extensible Natural Language Interface: A Case History / 556
Candace E. Kalish and Matthew B. Cox, MITRE Corporation

Inference in Text Understanding / 561
Peter Norvig, University of California, Berkeley

The Acquisition of Conceptual Structure for the Lexicon / 566
James Pustejovsky, Brandeis University and Sabine Bergler, University of Massachusetts

Ambiguity Procrastination / 571
Elaine Rich, Jim Barnett, Kent Wittenburg, and David Wroblewski, MMicroelectronics and Computer Technology Corporation

Memory-Based Reasoning Applied to English Pronunciation / 577
Craig W. Stanfill, Thinking Machines Corporation

Nondestructive Graph Unification / 582
David A. Wroblewski, MCC

Engineering Problem Solving

Reasoning about Fluids via Molecular Collections / 590
John W. Collins and Kenneth D. Forbus, University of Illinois

Extending the Mathematics in Qualitative Process Theory / 595
Bruce D'Ambrosio, Oregon State University

Troubleshooting: When Modeling Is the Trouble / 600
Philippe Dague and Olivier Raiman, IBM Scientific Center, Paris; and Philippe Deves, Electronique Serge Dassault

Explanation-Based Failure Recovery / 606
Ajay Gupta, Hewlett-Packard Laboratories

Shape and Function in Mechanical Devices / 611
Leo Joskowicz, New York University

Critical Hypersurfaces and the Quantity Space / 616
Mieczyslaw M. Kokar, Northeastern University

Abstraction by Time-Scale in Qualitative Simulation / 621
Benjamin Kuipers, University of Texas at Austin

Reasoning with Orders of Magnitude and Approximate Relations / 626
Michael L. Mavrovouniotis and George Stephanopoulos, MIT

Making Partial Choices in Constraint Reasoning Problems / 631
Sanjay Mittal and Felix Frayman, Xerox PARC

PROMPT: An Innovative Design Tool / 637
Seshashayee S. Murthy and Sanjaya Addanki, IBM T. J . Watson Research Center

Reasoning about Discontinuous Change / 643
Toyoaki Nishida and Shuji Doshita, Kyoto University

Hierarchical Reasoning about Inequalities / 649
Elisha Sacks, MIT Laboratory for Computer Science

Piecewise Linear Reasoning / 655
Elisha Sacks, MIT Laboratory for Computer Science

Probabilistic Semantics for Qualitative Influences / 660
Michael P. Wellman, MIT Laboratory for Computer Science

Extracting Qualitative Dynamics from Numerical Experiments / 665
Kenneth Man-kam Yip, MIT Artificial Intelligence Laboratory

Robotics

An Architecture for Intelligent Task Automation / 672
Jeffrey M. Becker and Fred L. Garrett, Martin Marietta Denver Aerospace

Reactive Reasoning and Planning / 677
Michael P. Georgeff and Amy L. Lansky, SRI International

Visual Grammars for Visual Languages / 683
Fred Lakin, Stanford University

Qualitative Landmark-Based Path Planning and Following / 689
Tod S. Levitt, Daryl T. Lawton, David M. Chelberg, and Philip C. Nelson, Advanced Decision Systems

Insertions Using Geometric Analysis and Hybrid Force-Position Control on a PUMA 560 with VAL II / 695
David R. Strip, Sandia National Laboratories

Vision

The Sensitivity of Motion and Structure Computations / 700
John L. Barron, Allan D. Jepson, and John K. Tsotsos, University of Toronto

Using Generic Geometric Models for Intelligent Shape Extraction / 706
Pascal Fua and Andrew J. Hanson, SRI International

Detecting Runways in Aerial Images / 712
A. Huertas, W. Cole, and R. Nevatia, University of Southern California

Hypothesis Testing in a Computational Theory of Visual Word Recognition / 718
Jonathan J . Hull, State University of New York at Buffalo

An Integrated System that Unifies Multiple Shape from Texture Algorithms / 723
Mark L. Moerdler and John R. Kender, Columbia University

Similitude-lnvariant Pattern Recognition Using Parallel Distributed Processing / 728
K. Prazdny, Artificial Intelligence Center, FMC Corporation

Range Image Interpretation of Mail Pieces with Superquadrics / 733
Franc Solina and Ruzena Bajcsy, University of Pennsylvania

Closed Form Solution to the Structure from Motion Problem from Line Correspondences / 738
Minas E. Spetsakis and John (Yiannis) Aloimonos, University of Maryland

Bounds on Translational and Angular Velocity Components from First Order Derivatives of Image Flow / 744
Muralidhara Subbarao, State University of New York at Stony Brook

Regularization Uses Fractal Priors / 749
Richard Szeliski, Carnegie Mellon University

Energy Constraints on Deformable Models: Recovering Shape and Non-Rigid Motion / 755
Demetri Terzopoulos, Andrew Witkin, and Michael Kass, Schlumberger Palo Alto Research

Shadow Stereo--Locating Object Boundaries Using Shadows / 761
William B. Thompson and Michael T. Checky, University of Minnesotak and William F. Kaemmerer, Honeywell Inc.

Perceptual Significance Hierarchy: A Computer Vision Theory for Color Separation / 767
Deborah Walters and Ganapathy Krishnan, State University of New York at Buffalo

Visual Estimation of 3-D Line Segments from Motion--A Mobile Robot Vision System / 772
William M. Wells III, SRI International

Expert Systems

Data Validation during Diagnosis: A Step beyond Traditional Sensor Validation / 778
B. Chandrasekaran and W. F. Punch III, Ohio State University

MU: A Development Environment for Prospective Reasoning Systems / 783
Paul R. Cohen, Michael Greenberg, and Jefferson DeLisio, University of Massachusetts

Diagnostic Improvement through Qualitative Sensitivity Analysis and Aggregation / 789
Keith L. Downing, University of Oregon

CAMEX--An Expert System for Process Planning on CNC Machines / 794
O. Eliyahu, L. Zaidenberg, and M. Ben-Bassat, lET-Intelligent Electronics and Tel Aviv University

A Multiple Representation Approach to Understanding the Time Behavior of Digital Circuits / 799
Robert J. Hall and Richard H. Lathrop, MIT Artificial Intelligence Laboratory; and Robert S. Kirk, Gould, Inc.

KADBASE--A Prototype Expert System-Database Interface for Integrated CAE Environments / 804
H. Craig Howard, Stanford University and Daniel R. Rehak, Expert Technologies, Inc.

An Automated Reasoning Technique for Providing Moment-by-Moment Advice Concerning the Operation of a Process / 809
William F. Kaemmerer and James R. Allard, Honeywell

TEST: A Model-Driven Application Shell / 814
Gary S. Kahn, AI Kepner, and Jeff Pepper, Carnegie Group Inc.

Script-Based Reasoning for Situation Monitoring / 819
Sharon J. Laskowski and Emily J. Hofmann , MITRE Corporation

Assessing the Maintainability of XCON-in-RlME: Coping with the Problems of a VERY Large Rule-Base / 824
Elliot Soloway, Yale University; and Judy Bachant and Keith Jensen, Digital Equipment Corporation

Design as Refinement Plus Constraint Propagation: The VEXED Experience / 830
Louis I. Steinberg, Rutgers University

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