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!
Contents
Volume One
Case-Based Reasoning
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
Volume Two
Learning
Learning Search Control
Synthesizing UNIX Shell Scripts Using Derivational Analogy: An Empirical
Assessment
Sanjay Bhansali and Mehdi T. Harandi, University of Illinois at
Urbana-Champaign / 521
SteppingStone: An Empirical and Analytical Evaluation
David Ruby and Dennis Kibler, University of California, Irvine / 527
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
AAAI Digital Library
AAAI relies on your generous support through membership and donations. If you find these resources useful, we would be grateful for your support.