Proceedings of the Sixth National Conference on Artificial Intelligence
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