Ninth National Conference on Artificial Intelligence

Proceedings of the Ninth National Conference on Artificial Intelligence

Sponsored by the Association for the Advancement of Artificial Intelligence

Thomas L. Dean and Kathleen McKeown, Program Cochairs

July 14-19, 1991, Anaheim, California. 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!

Volume One

Preface

Conference Organization

Best Paper Award

Case-Based Reasoning

Rules and Precedents as Complementary Warrants
L. Karl Branting, University of Wyoming; and Bruce W. Porter, University of Texas at Austin / 3

An Indexing Vocabulary for Case-Based Explanation
David B. Leake, Indiana University / 10

Indexing Stories as Social Advice
Eric A. Domeshek, Institute for Learning Sciences, Northwestern University / 16

Improving Rule-Based Systems Through Case-Based Reasoning
Andrew R. Golding, Stanford University; and Paul S. Rosenbloom, Information Sciences Institute, University of Southern California / 22

Transformation in Design

The Roles of Adaptation in Case-Based Design
Thomas R. Hinrichs and Janet L. Kolodner, Georgia Institute of Technology / 28

Prototype-Based Reasoning: An Integrated Approach to Solving Large Novel Problems
Shankar A. Rajamoney and Hee-Youn Lee, University of Southern California / 34

Communication and Cooperation

Education

Student Modelling with Confluences
Daniel Baril, Jim E. Greer, and Gordon I. McCalla, University of Saskatchewan / 43

FITS: A Fraction Intelligent Tutoring System
Hyacinth S. Nwana, University of Liverpool / 49

Teaching Diagnostic Skills Using AI: An Architecture Suitable for Students and Teachers
Joël Courtois, Institut Supérieur d'Electronique de Paris and Université PARIS VI / 55

User Interfaces

Planning Multimedia Explanations Using Communicative Acts
Mark T. Maybury, The MITRE Corporation / 61

Making Design Objects Relevant to the Task at Hand
Gerhard Fischer, University of Colorado; and Kumiyo Nakakoji, University of Colorado and Software Research Associates, Inc. / 67

A Tool for Achieving Consensus in Knowledge Representation
Loren G. Terveen and David A. Wroblewski, MCC / 74

PICTION: A System That Uses Captions to Label Human Faces in Newspaper Photographs
Rohini K. Srihari, State University of New York at Buffalo / 80

Generation and Interaction

Generating Interactive Explanations
Alison Cawsey, University of Edinburgh / 86

Automatic Generation of Formatted Text
Eduard H. Hovy and Yigal Arens, USC-Information Sciences Institute / 92

Generating Adjectives to Express the Speaker’s Argumentative Intent
Michael Elhadad, Columbia University / 98

Interpreting Prepositions Physically
J. K. Kalita, University of Colorado; and N. I. Badler, University of Pennsylvania / 105

Syntax and Semantics I

Semantics-First Natural Language Processing
Steven L. Lytinen, The University of Michigan / 111

A Cognitively Plausible Approach to Understanding Complex Syntax
Claire Cardie and Wendy Lehnert, University of Massachusetts / 117

From Syntax to Meaning in Natural Language Processing
Alexander G. Hauptmann, Carnegie Mellon University / 125

Tense Interpretation in the Context of Narrative
Fei Song and Robin Cohen, University of Waterloo / 131

Syntax and Semantics II

ULINK: A Semantics-Driven Approach to Understanding Ungrammatical Input
Jeffrey D. Kirtner and Steven L. Lytinen, The University of Michigan / 137

A Tabular Method for Island-Driven Context-Free Grammar Parsing
Giorgio Satta and Oliviero Stock, Istituto per la Ricerca Scientifica e Tecnologica / 143

High Performance Memory-Based Translation on IXM2 Massively Parallel Associative Memory Processor
Hiroaki Kitano, Carnegie Mellon University and NEC Corporation; and Tetsuya Higuchi, Electrotechnical Laboratory / 149

Disambiguation of Prepositional Phrases in Automatically Labelled Technical Text
Lois Boggess, Rajeev Agarwal, and Ron Davis, Mississippi State University / 155

Formalisms for Coordination

A Probabilistic Model of Plan Recognition
Eugene Charniak, Brown University; and Robert Goldman, Tulane University / 160

The Utility of Communication in Coordinating Intelligent Agents
Piotr J. Gmytrasiewicz, Edmund H. Durfee, and David K. Wehe, University of Michigan / 166

The Clarke Tax as a Consensus Mechanism Among Automated Agents
Eithan Ephrati and Jeffrey S. Rosenschein, Hebrew University / 173

The Function of Time in Cooperative Negotiations
Sarit Kraus, Hebrew University; and Jonathan Wilkenfeld, University of Maryland / 179

Multiagent Architectures

A Dynamic Organizational Architecture for Adaptive Problem Solving
Les Gasser, University of Southern California; Toru Ishida, NTT Communications and Information Processing Laboratories / 185

Sophisticated Cooperation in FA/C Distributed Problem Solving Systems
Norman Carver, Zarko Cvetanovic, and Victor Lesser, University of Massachusetts / 191

Combining Specialized Reasoners and General Purpose Planners: A Case Study
Subbarao Kambhampati, Mark Cutkosky, Marty Tenenbaum, and Soo Hong Lee, Stanford University / 199

Toward an Intelligent Agent Framework for Enterprise Integration
Jeff Y-C Pan and Jay M. Tenenbaum, Enterprise Integration Technologies Corporation and Stanford University / 206

Constraint Reasoning and Component Technologies

Constraint-Based Reasoning

Conditional Existence of Variables in Generalized Constraint Networks
James Bowen and Dennis Bahler, North Carolina State University / 215

Arc-Consistency in Dynamic Constraint Satisfaction Problems
Christian Bessiere, Laboratoire d'Informatique, de Robotique et de Microelectronique de Montpellier / 221

Eliminating Interchangeable Values in Constraint Satisfaction Problems
Eugene C. Freuder, University of New Hampshire / 227

On Generalized Interval Calculi
Gérard Ligozat, LIMSI, Universite Paris-Sud / 234

Temporal Constraints

Integrating Metric and Qualitative Temporal Reasoning
Henry A. Kautz, AT&T Bell Laboratories; and Peter B. Ladkin, International Computer Science Institute / 241

Temporal Reasoning During Plan Recognition
Fei Song and Robin Cohen, University of Waterloo / 247

Metric Constraints for Maintaining Appointments: Dates and Repeated Activities
Massimo Poesio, University of Rochester; and Ronald J. Brachman, AT&T Bell Laboratories / 253

Combining Qualitative and Quantitative Constraints in Temporal Reasoning
Itay Meiri, University of California, Los Angeles / 260

Extensions of Truth Maintenance

Efficiency of Production Systems When Coupled with an Assumption Based Truth Maintenance System
Geneviève Morgue and Thomas Chehire, Thomson-CSF/RCC / 268

Using Attention in Belief Revision
Xueming Huang, Gordon I. McCalla, and Eric Neufeld, University of Saskatchewan / 275

CATMS: An ATMS Which Avoids Label Explosions
John W. Collins, University of Illinois; and Dennis DeCoste, Northwestern University / 281

Context Maintenance
Charles J. Petrie, Jr., Microelectronics and Computer Technology Corporation / 288

Parallel Support for Rule-Based Systems

IXM2: A Parallel Associative Processor for Knowledge Processing
Tetsuya Higuchi, Electrotechnical Laboratory; Hiroaki Kitano, Carnegie Mellon University; Tatsumi Furuya, Ken-ichi Handa, and Akio Kokubu, Electrotechnical Laboratory; Naoto Takahashi, University of Tsukuba / 296

Implementation of Multiple Rule Firing Production Systems on Hypercube
Steve Kuo and Dan Moldovan, University of Southern California / 304

Control Issues in Parallel Rule-Firing Production Systems
Daniel E. Neiman, University of Massachusetts / 310

Using Abstraction to Automate Program Improvement by Transformation
Ian Green, University of Cambridge / 317

Verification of Rule-Based Systems

Verification of Multi-Level Rule-Based Expert Systems
Pedro Meseguer, C.S.I.C. / 323

Formal Verification of Pure Production System Programs
Rose F. Gamble, Gruia-Catalin Roman, and William E. Ball, Washington University / 329

Learning Meta Knowledge for Database Checking
Jeffrey C. Schlimmer, Carnegie Mellon University / 335

Formal Methods in Knowledge Representation

Time and Action

A Logic of Situated Know-How
Munindar P. Singh, University of Texas / 343

Provably Correct Theories of Action (Preliminary Report)
Fangzhen Lin and Yoav Shoham, Stanford University / 349

A Critique of Yoav Shoham’s Theory of Causal Reasoning
Antony Galton, University of Exeter / 355

A Logic and Time Nets for Probabilistic Inference
Keiji Kanazawa, Brown University / 360

Nonmonotonic Reasoning I

The P-Systems: A Systematic Classification of Logics of Nonmonotonicity
Wolfgang Nejdl, Technical University of Vienna / 366

Some Variations on Default Logic
Piotr Rychlik, Polish Academy of Sciences / 373

Default Logic, Propositional Logic, and Constraints
Rachel Ben-Eliyahu, University of California, Los Angeles; and Rina Dechter, University of California, Irvine / 379

Strong Introspection
Michael Gelfond, University of Texas at El Paso / 386

Nonmonotonic Reasoning II

Default Reasoning From Statistics
Fahiem Bacchus, University of Waterloo / 392

System-Z+: A Formalism for Reasoning with Variable-Strength Defaults
Moisés Goldszmidt and Judea Pearl, University of California, Los Angeles / 399

Incorporating Nonmonotonic Reasoning in Horn Clause Theories
James P. Delgrande, Simon Fraser University / 405

Step-Logic and the Three-Wise-Men Problem
Jennifer J. Elgot-Drapkin, Arizona State University / 412

Issues in Automated Reasoning

General Deduction Systems

Logic Morphisms as a Framework for Backward Transfer of Lemmas and Strategies in Some Modal and Epistemic Logics
Ricardo Caferra, Stephane Demri, and Michel Herment, LIFIA-IMAG / 421

Mechanization of Analytic Reasoning About Sets
Alan F. McMichael, AT&T Bell Laboratories / 427

Search

Depth-First Versus Best-First Search
Nageshwara Rao Vempaty, University of Central Florida; Vipin Kumar, University of Minnesota; and Richard E. Korf, University of California, Los Angeles / 434

Optimal Satisficing Tree Searches
Dan Geiger and Jeffrey A. Barnett, Northrop Research and Technology Center / 441

A New Admissible Heuristic for Minimal-Cost Proofs
Eugene Charniak and Saadia Husain, Brown University / 446

Is There any Need for Domain-Dependent Control Information?
Matthew L. Ginsberg and Donald F. Geddis, Stanford University / 452

Terminological Reasoning

Integrating Rules in Term Subsumption Knowledge Representation Servers
Brian R. Gaines, University of Calgary / 458

Deduction as Parsing: Tractable Classification in the KL-ONE Framework
Marc Vilain, The MITRE Corporation / 464

Concept Languages as Query Languages
Maurizio Lenzerini and Andrea Schaerf, Universita di Roma "La Sapienza" / 471

Belief Functions

Combining Opinions About the Order of Rule Execution
Jeffrey A. Barnett, Northrop Research and Technology Center / 477

Explanation, Irrelevance, and Statistical Independence
Solomon E. Shimony, Brown University / 482

Conditions for the Existence of Belief Functions Corresponding to Intervals of Belief
John F. Lemmer, CTA Incorporated; and Henry E. Kyburg, Jr., University of Rochester / 488

Truth Maintenance Systems

An Efficient First-Order Horn-Clause Abduction System Based on the ATMS
Hwee Tou Ng and Raymond J. Mooney, University of Texas at Austin / 494

The Common Order-Theoretic Structure of Version Spaces and ATMS’s (Extended Abstract)
Carl A. Gunter and Teow-Hin Ngair, University of Pennsylvania; Prakash Panangaden, McGill University; Devika Subramanian, Cornell University / 500

ACP: Reason Maintenance and Inference Control for Constraint Propagation Over Intervals
Walter Hamscher, Price Waterhouse Technology Centre / 506

Controlling Inequality Reasoning in a TMS-Based Analog Diagnosis System
David Jerald Goldstone, Massachusetts Institute of Technology and Xerox Palo Alto Research Center / 512

STATIC: A Problem-Space Compiler for PRODIGY
Oren Etzioni, University of Washington / 533

Integrating Abstraction and Explanation-Based Learning in PRODIGY
Craig A. Knoblock, Carnegie Mellon University; Steven Minton, Sterling Federal Systems; and Oren Etzioni, University of Washington / 541

Learning Theory and MDL

Learning with Many Irrelevant Features
Hussein Almuallim and Thomas G. Dietterich, Oregon State University / 547

Analyses of Instance-Based Learning Algorithms
Marc K. Albert, University of California, Irvine; and David W. Aha, The Turing Institute / 553

Regularity and Structure
Alexander Botta, New York University / 559

A Minimal Encoding Approach to Feature Discovery
Mark Derthick, MCC / 565

Learning Connectionist Representations

Error-Correcting Output Codes: A General Method for Improving Multiclass Inductive Learning Programs
Thomas G. Dietterich and Ghulum Bakiri, Oregon State University / 572

Analysis of the Internal Representations in Neural Networks for Machine Intelligence
Lai-Wan Chan, The Chinese University of Hong Kong / 578

Direct Transfer of Learned Information Among Neural Networks
Lorien Y. Pratt and Jack Mostow, Rutgers University; Candace A. Kamm, Bellcore / 584

Rule Learning by Searching on Adapted Nets
LiMin Fu, University of Florida / 590

Learning and Evaluation Functions

Two Kinds of Training Information For Evaluation Function Learning
Paul E. Utgoff and Jeffrey A. Clouse, University of Massachusetts / 596

Adaptive Pattern-Oriented Chess
Robert Levinson and Richard Snyder, University of California, Santa Cruz / 601

A Complexity Analysis of Cooperative Mechanisms in Reinforcement Learning
Steven D. Whitehead, University of Rochester / 607

Constructive Induction on Domain Information
James P. Callan and Paul E. Utgoff, University of Massachusetts / 614

Planning, Perception, and Robotics

Mathematical Foundations of Planning

On the NP-Hardness of Blocks World
Stephen V. Chenoweth, NCR Research & Development / 623

Complexity Results for Blocks-World Planning
Naresh Gupta and Dana S. Nau, University of Maryland / 629

Systematic Nonlinear Planning
David McAllester, Massachusetts Institute of Technology, and David Rosenblitt, WEB Development Corporation / 634

An Efficient Reactive Planner for Synthesizing Reactive Plans
Patrice Godefroid and Froduald Kabanza, Université de Liège / 640

Path and Assembly Planning

Dealing with Uncertainties in CAD-Based Assembly Motion Planning
S. N. Gottschlich, and A. C. Kak, Purdue University / 646

Augmenting a Nominal Assembly Motion Plan with a Compliant Behavior
Gordon A. Dakin and Robin J. Popplestone, University of Massachusetts / 653

A Fast Path Planner for a Car-Like Indoor Mobile Robot
Jean-Claude Latombe, Stanford University / 659

Path Planning for Highly Redundant Manipulators Using a Continuous Model
Akira Hayashi and Benjamin J. Kuipers, The University of Texas at Austin / 666

Hierarchy in Planning

A Quantitative Theory for Plan Merging
David E. Foulser, Silicon Graphics Computer Systems; Ming Li and Qiang Yang, University of Waterloo / 673

Explanation-Based Generalization of Partially Ordered Plans
Subbarao Kambhampati, Stanford University; and Smadar Kedar, NASA Ames Research Center / 679

Search Reduction in Hierarchical Problem Solving
Craig A. Knoblock, Carnegie Mellon University / 686

Characterizing Abstraction Hierarchies for Planning
Craig A. Knoblock, Carnegie Mellon University; Josh D. Tenenberg, University of Rochester; and Qiang Yang, University of Waterloo / 692

Representation in Planning

Preferential Semantics for Goals
Michael P. Wellman, Wright-Patterson AFB; and Jon Doyle, Massachusetts Institute of Technology / 698

AGENT0: A Simple Agent Language and Its Interpreter
Yoav Shoham, Stanford University / 704

Vision and Sensor Interpretation

Automatic Generation of Object Class Descriptions Using Symbolic Learning Techniques
R. L. Cromwell and A. C. Kak, Purdue University / 710

An Algorithm for Real-Time Tracking of Non-Rigid Objects
John Woodfill and Ramin Zabih, Stanford University / 718

A New Framework for Sensor Interpretation: Planning to Resolve Sources of Uncertainty
Norman Carver and Victor Lesser, University of Massachusetts / 724

The Geometry of Visual Coordination
Jean-Yves Hervé, Rajeev Sharma, and Peter Cucka, University of Maryland / 732

Sensing and Reaction

Anytime Problem Solving Using Dynamic Programming
Mark Boddy, Honeywell Systems and Research Center / 738

An Analysis of Error Recovery and Sensory Integration for Dynamic Planners
Bruce Abramson, University of Southern California / 744

Global Symbolic Maps from Local Navigation
David P. Miller, Jet Propulsion Laboratory; and Marc G. Slack, MITRE Corporation / 750

Sensible Planning: Focusing Perceptual Attention
Lonnie Chrisman and Reid Simmons, Carnegie Mellon University / 756

Robot Learning

Fuzzy Modeling Using Generalized Neural Networks and Kalman Filter Algorithm
Jyh-Shing R. Jang, University of California, Berkeley / 762

Automatic Programming of Behavior-Based Robots Using Reinforcement Learning
Sridhar Mahadevan and Jonathan Connell, IBM T. J. Watson Research Center / 768

Cost-Sensitive Reinforcement Learning for Adaptive Classification and Control
Ming Tan, Carnegie Mellon University / 774

Programming Robots Using Reinforcement Learning and Teaching
Long-Ji Lin, Carnegie Mellon University / 781

Integration and Recovery

Stabilizing Environments to Facilitate Planning and Activity: An Engineering Argument
Kristian J. Hammond and Timothy M. Converse, The University of Chicago / 787

Underwater Experiments Using a Reactive System for Autonomous Vehicles
R. Peter Bonasso, The MITRE Corporation / 794

Failure Recovery: A Model and Experiments
Adele E. Howe and Paul R. Cohen, University of Massachusetts / 801

Reasoning About Physical Systems

Qualitative Analysis

Automated Phase Portrait Analysis by Integrating Qualitative and Quantitative Analysis
Toyoaki Nishida, Kenji Mizutani, Atsushi Kubota, and Shuji Doshita, Kyoto University / 811

Qualitative Analysis of Causal Feedback
Philippe Rose and Mark A. Kramer, Massachusetts Institute of Technology / 817

The Qualitative Difference Resolution Rule
Tom Bylander, The Ohio State University / 824

Analytic Solution of Qualitative Differential Equations
Philip Schaefer, Martin Marietta Advanced Computing Technology / 830

Diagnosis

Model-Based Reconfiguration: Toward an Integration with Diagnosis
Judith Crow and John Rushby, SRI International / 836

Focusing on Probable Diagnoses
Johan de Kleer, Xerox Palo Alto Research Center / 842

Characterizing Non-Intermittent Faults
Olivier Raiman, Johan de Kleer, Vijay Saraswat, and Mark Shirley, Xerox Palo Alto Research Center / 849

Domain Structure and the Complexity of Diagnostic Problem Solving
Thomas D. Wu, Massachusetts Institute of Technology / 855

Aggregation and Geometric Reasoning

Behavioral Aggregation Within Complex Situations: A Case Study Involving Dynamic Equilibria
Shankar A. Rajamoney and Sang Hoe Koo, University of Southern California / 862

Structural Aggregation in Common-Sense Reasoning
Zheng-Yang Liu, EDS Research; and Arthur M. Farley, University of Oregon / 868

Geometric Reasoning for Shape Design
George Turkiyyah and Omar Ghattas, Carnegie Mellon University / 874

The Use of Intelligently Controlled Simulation to Predict a Machine’s Long-Term Behavior
Andrew Gelsey, Rutgers University / 880

Incremental Configuration Space Construction for Mechanism Analysis
Leo Joskowicz, IBM T. J. Watson Research Center; and Elisha Sacks, Princeton University / 888

Tractable Inference

Negation and Proof by Contradiction in Access-Limited Logic
J. M. Crawford and B. J. Kuipers, The University of Texas at Austin / 897

Knowledge Compilation Using Horn Approximations
Bart Selman and Henry Kautz, AT&T Bell Laboratories / 904

Observations on Cognitive Judgments
David McAllester, Massachusetts Institute of Technology / 910

Natural Language Based Inference Procedures Applied to Schubert’s Steamroller
Robert Givan, David McAllester, and Sameer Shalaby, Massachusetts Institute of Technology / 915

Invited Talks

Approximate Reasoning Systems: A Personal Perspective
Piero P. Bonissone, General Electric Corporate R & D / 923

Robot Planning
Drew McDermott, Yale University / 930

Index

Proceedings of the Ninth National Conference on Artificial Intelligence

Contents

AAAI Digital Library

Other Links