Proceedings of the Eleventh National Conference on Artificial Intelligence
Sponsored by the Association for the Advancement of Artificial Intelligence
Richard Fikes and Wendy Lehnert, Program Cochairs
July 11-15, 1993, Washington, D.C. 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
Automated Reasoning
On Computing Minimal Models / 2
Rachel Ben-Eliyahu, University of California, Los Angeles and Rina Dechter, University of California, Irvine
On the Adequateness of the Connection Method / 9
Antje Beringer and Steffen Hölldobler, Intellektik, Informatik, TH Darmstadt
Rough Resolution: A Refinement of Resolution to Remove Large Literals / 15
Heng Chu and David A. Plaisted, University of North Carolina
Experimental Results on the Crossover Point in Satisfiability Problems / 21
James M. Crawford and Larry D. Auton, AT&T Bell Laboratories
Towards an Understanding of Hill-Climbing Procedures for SAT / 28
Ian P. Gent and Toby Walsh, University of Edinburgh
Reasoning with Characteristic Models / 34
Henry A. Kautz, Michael J. Kearns, and Bart Selman, AT&T Bell Laboratories
The Breakout Method for Escaping from Local Minima / 40
Paul Morris, IntelliCorp
An Empirical Study of Greedy Local Search for Satisfiability Testing / 46
Bart Selman and Henry A. Kautz, AT&T Bell Laboratories
Case-Based Reasoning
Projective Visualization: Acting from Experience / 54
Marc Goodman, Brandeis University
Representing and Using Procedural Knowledge to Build Geometry Proofs / 60
Thomas F. McDougal and Kristian J. Hammond, University of Chicago
Case-Based Diagnostic Analysis in a Blackboard Architecture / 66
Edwina L. Rissland, Jody J. Daniels, Zachary B. Rubinstein and David B. Skalak, University of Massachusetts
A Framework and an Analysis of Current Proposals for the Case-Based Organization and Representation of Procedural Knowledge / 73
Roland Zito-Wolf and Richard Alterman, Brandeis University
Complexity in Machine Learning
Cryptographic Limitations on Learning One-Clause Logic Programs / 80
William W. Cohen, AT&T Bell Laboratories
Pac-Learning a Restricted Class of Recursive Logic Programs / 86
William W. Cohen, AT&T Bell Laboratories
Learnability in Inductive Logic Programming: Some Basic Results and Techniques / 93
Michael Frazier and C. David Page, Jr., University of Illinois
Complexity Analysis of Real-Time Reinforcement Learning / 99
Sven Koenig and Reid G. Simmons, Carnegie Mellon University
Constraint-Based Reasoning
Arc-Consistency and Arc-Consistency Again / 108
Christian Bessire, University of Montpellier II and Marie-Odile Cordier, University of Rennes I
On the Consistency of General Constraint-Satisfaction Problems / 114
Philippe Jégou, Université de Provence
Integrating Heuristics for Constraint Satisfaction Problems: A Case Study / 120
Steven Minton, Sterling Software/NASA Ames Research Center
Coping With Disjunctions in Temporal Constraint Satisfaction Problems / 127
Eddie Schwalb and Rina Dechter, University of California, Irvine
Nondeterministic Lisp as a Substrate for Constraint Logic Programming / 133
Jeffrey Mark Siskind, University of Pennsylvania and David Allen McAllester, MIT Artifical Intelligence Laboratory
Slack-Based Heuristics for Constraint Satisfaction Scheduling / 139
Stephen F. Smith and Cheng-Chung Cheng, Carnegie Mellon University
A Constraint Decomposition Method for Spatio-Temporal Configuration Problems / 145
Toshikazu Tanimoto, Digital Equipment Corporation Japan
Extending Deep Structure / 152
Colin P. Williams and Tad Hogg, Xerox Palo Alto Research Center
Diagnostic Reasoning
Multiple Dimensions of Generalization In Model-Based Troubleshooting / 160
Randall Davis and Paul Resnick, Massachusetts Institute of Technology
Hybrid Case-Based Reasoning for the Diagnosis of Complex Devices / 168
M. P. Féret and J. I. Glasgow, Queen’s University
An Epistemology for Clinically Significant Trends / 176
Ira J. Haimowitz, MIT Laboratory for Computer Science and Isaac S. Kohane, Harvard Medical School
A Framework for Model-Based Repair / 182
Ying Sun and Daniel S. Weld, University of Washington
Discourse Analysis
A Method for Development of Dialogue Managers for Natural Language Interfaces / 190
Arne Jönsson, Linköping University
Mutual Beliefs of Multiple Conversants: A Computational Model of Collaboration in Air Traffic Control / 196
David G. Novick and Karen Ward, Oregon Graduate Institute of Science & Technology
An Optimizing Method for Structuring Inferentially Linked Discourse
Ingrid Zukerman and Richard McConachy, Monash University / 202
Distributed Problem Solving
A One-Shot Dynamic Coordination Algorithm for Distributed Sensor Networks / 210
Keith Decker and Victor Lesser, University of Massachusetts
Quantitative Modeling of Complex Computational Task Environments / 217
Keith Decker and Victor Lesser, University of Massachusetts
Overeager Reciprocal Rationality and Mixed Strategy Equilibria / 225
Edmund H. Durfee and Jaeho Lee, University of Michigan; Piotr J. Gmytrasiewicz, Hebrew University
Solving the Really Hard Problems with Cooperative Search / 231
Tad Hogg and Colin P. Williams, Xerox Palo Alto Research Center
A Fast First-Cut Protocol for Agent Coordination / 237
Andrew P. Kosoresow, Stanford University
Agents Contracting Tasks in Non-Collaborative Environments / 243
Sarit Kraus, Bar Ilan University
IPUS: An Architecture for Integrated Signal Processing and Signal Interpretation in Complex Environments / 249
Victor Lesser, Izaskun Gallastegi and Frank Klassner, University of Massachusetts; Hamid Nawab, Boston University
An Implementation of the Contract Net Protocol Based on Marginal Cost Calculations / 256
Tuomas Sandholm, University of Massachusetts
Intelligent User Interfaces
Generating Explanations of Device Behavior Using Compositional Modeling and Causal Ordering / 264
Patrice O. Gautier and Thomas R. Gruber, Stanford University
Generating Natural Language Descriptions with Examples: Differences between Introductory and Advanced Texts / 271
Vibhu O. Mittal and Cécile L. Paris, University of Southern California
Building Models to Support Synthesis in Early Stage Product Design / 277
R. Bharat Rao, Siemens Corporate Research, Inc. and Stephen C-Y. Lu, University of Illinois at Urbana-Champaign
A Conversational Model of Multimodal Interaction in Information Systems / 283
Adelheit Stein and Ulrich Thiel, German National Research Center for Computer Science
Large Scale Knowledge Bases
Matching 100,045 Learned Rules / 290
Robert B. Doorenbos, Carnegie Mellon University
Massively Parallel Support for Computationally Effective Recognition Queries / 297
Matthew P. Evett, James A. Hendler, and William A. Andersen, University of Maryland
Case-Method: A Methodology for Building Large-Scale Case-Based Systems / 303
Hiroaki Kitano, Hideo Shimazu and Akihiro Shibata, NEC Corporation
Automated Index Generation for Constructing Large-Scale Conversational Hypermedia Systems / 309
Richard Osgood and Ray Bareiss, Northwestern University
Machine Learning
Probabilistic Prediction of Protein Secondary Structure Using Causal Networks
Arthur L. Delcher, Loyola College; Simon Kasif, Harry R. Goldberg and William H. Hsu, Johns Hopkins University / 316
OC1: Randomized Induction of Oblique Decision Trees / 322
Sreerama Murthy, Simon Kasif and Steven Salzberg, Johns Hopkins University; Richard Beigel, Yale University
Finding Accurate Frontiers: A Knowledge-Intensive Approach to Relational Learning / 328
Michael Pazzani and Clifford Brunk, University of California, Irvine
Learning Non-Linearly Separable Boolean Functions With Linear Threshold Unit Trees and Madaline-Style Networks / 335
Mehran Sahami, Stanford University
Natural Language Generation
Generating Argumentative Judgment Determiners / 344
Michael Elhadad, Ben Gurion University of the Negev
Bidirectional Chart Generation of Natural Language Texts / 350
Masahiko Haruno and Makoto Nagao, Kyoto University; Yasuharu Den, ATR Interpreting Telecommunication Research Laboratories; and Yuji Matsumoto, Advanced Institute of Science and Technology, Nara
Communicative Acts for Generating Natural Language Arguments / 357
Mark T. Maybury, The MITRE Corporation
Corpus Analysis for Revision-Based Generation of Complex Sentences
Jacques Robin and Kathleen McKeown, Columbia University / 365
Natural Language Sentence Analysis
Machine Translation of Spatial Expressions: Defining the Relation between an Interlingua and a Knowledge Representation System
Bonnie J. Dorr and Clare R. Voss, University of Maryland / 374
Having Your Cake and Eating It Too: Autonomy and Interaction in a Model of Sentence Processing / 380
Kurt P. Eiselt and Kavi Mahesh, Georgia Institute of Technology; Jennifer K. Holbrook, Albion College
Efficient Heuristic Natural Language Parsing / 386
Christian R. Huyck and Steven L. Lytinen, University of Michigan
Towards a Reading Coach that Listens: Automated Detection of Oral Reading Errors / 392
Jack Mostow, Alexander G. Hauptmann, Lin Lawrence Chase and Steven Roth, Carnegie Mellon University
Nonmonotonic Logic
Minimal Belief and Negation as Failure: A Feasible Approach / 400
Antje Beringer and Torsten Schaub, TH Darmstadt
A Context-based Framework for Default Logics / 406
Philippe Besnard, IRISA and Torsten Schaub, TH Darmstadt
Propositional Logic of Context / 412
Sasa Buvac and Ian A. Mason, Stanford University
Generating Explicit Orderings for Non-monotonic Logics / 420
James Cussens, King’s College; Anthony Hunter, Imperial College; and Ashwin Srinivasan, Oxford University
Reasoning Precisely with Vague Concepts / 426
Nita Goyal and Yoav Shoham, Stanford University
Restricted Monotonicity / 432
Vladimir Lifschitz, University of Texas at Austin
Subnormal Modal Logics for Knowledge Representation / 438
Grigori Schwarz, Stanford University and Miroslaw Truszczynski, University of Kentucky
Algebraic Sematics for Cumulative Inference Operations / 444
Zbigniew Stachniak, University of Toronto
Novel Methods in Knowledge Acquisition
Question-based Acquisition of Conceptual Indices for Multimedia Design Documentation / 452
Catherine Baudin, RECOM Technologies/NASA Ames Research Center; Smadar Kadar, Sterling Software/Northwestern University/NASA Ames Research Center; Jody Gevins Underwood, Sterling Software Inc./NASA Ames Research Center; and Vinod Baya, Stanford University
Learning Interface Agents / 459
Pattie Maes and Robyn Kozierok, MIT Media Laboratory
Learning from an Approximate Theory and Noisy Examples / 465
Somkiat Tangkitvanich and Masamichi Shimura, Tokyo Institute of Technology
Scientific Model-Building as Search in Matrix Spaces / 472
Raúl E. Valdés-Pérez and Herbert A. Simon, Carnegie Mellon University; Jan M. Zytkow, Wichita State University
Plan Generation
An Average Case Analysis of Planning / 480
Tom Bylander, The Ohio State University
Granularity in Multi-Method Planning / 486
Soowon Lee and Paul S. Rosenbloom, University of Southern California
Threat-Removal Strategies for Partial-Order Planning / 492
Mark A. Peot, Stanford University and David E. Smith, Rockwell International
Postponing Threats in Partial-Order Planning / 500
David E. Smith, Rockwell International and Mark A. Peot, Stanford University
Plan Learning
Permissive Planning: A Machine Learning Approach to Linking Internal and External Worlds / 508
Gerald DeJong, University of Illinois at Urbana-Champaign and Scott Bennett, Systems Research and Applications Corporation
Relative Utility of EBG based Plan Reuse in Partial Ordering vs. Total Ordering Planning / 514
Subbarao Kambhampati and Jengchin Chen, Arizona State University
Learning Plan Transformations from Self-Questions: A Memory-Based Approach / 520
R. Oehlmann, D. Sleeman, and P. Edwards, University of Aberdeen
On the Masking Effect / 526
Milind Tambe, Carnegie Mellon University and Paul S. Rosenbloom, University of Southern California/Information Sciences Institute
Qualitative Reasoning
Qualitatively Describing Objects Using Spatial Prepositions / 536
Alicia Abella and John R. Kender, Columbia University
Numeric Reasoning with Relative Orders of Magnitude / 541
Philippe Dague, Université Paris Nord
Efficient Reasoning in Qualitative Probabilistic Networks / 548
Marek J. Druzdzel, Carnegie Mellon University and Max Henrion, Rockwell International Science Center
Generating Quasi-symbolic Representation of Three-Dimensional Flow / 554
Toyoaki Nishida, Advanced Institute of Science and Technology, Nara
Real-Time Planning and Simulation
Real-Time Self-Explanatory Simulation / 562
Franz G. Amador, Adam Finkelstein and Daniel S. Weld, University of Washington
A Comparison of Action-Based Hierarchies and Decision Trees for Real-Time Performance / 568
David Ash and Barbara Hayes-Roth, Stanford University
Planning With Deadlines in Stochastic Domains / 574
Thomas Dean, Leslie Pack Kaelbling, Jak Kirman and Ann Nicholson, Brown University
Task Interdependencies in Design-to-time Real-time Scheduling / 580
Alan Garvey, Marty Humphrey, and Victor Lesser, University of Massachusetts
Reasoning about Physical Systems
Sensible Scenes: Visual Understanding of Complex Structures through Causal Analysis / 588
Matthew Brand, Lawrence Birnbaum and Paul Cooper, Northwestern University
Intelligent Model Selection for Hillclimbing Search in Computer-Aided Design / 594
Thomas Ellman, John Keane, and Mark Schwabacher, Rutgers University
Ideal Physical Systems / 600
Brian Falkenhainer, Xerox Corporate Research & Technology
Numerical Behavior Envelopes for Qualitative Models / 606
Herbert Kay and Benjamin Kuipers, University of Texas at Austin
A Qualitative Method to Construct Phase Portraits / 614
Wood W. Lee, Schlumberger Dowell and Benjamin J. Kuipers, University of Texas
Understanding Linkages / 620
Howard E. Shrobe, Massachusetts Institute of Technology
CFRL: A Language for Specifying the Causal Functionality of Engineered Devices / 626
Marcos Vescovi, Yumi Iwasaki and Richard Fikes, Stanford University; B. Chandrasekaran, The Ohio State University
Model Simplification by Asymptotic Order of Magnitude Reasoning / 634
Kenneth Man-kam Yip, Yale University
Representation and Reasoning
Abduction As Belief Revision: A Model of Preferred Explanations / 642
Craig Boutilier and Veronica Becher, University of British Columbia
Revision by Conditional Beliefs / 649
Craig Boutilier, University of British Columbia and Moisés Goldszmidt, Rockwell International
Reasoning about Only Knowing with Many Agents / 655
Joseph Y. Halpern, IBM Almaden Research Center
All They Know About / 662
Gerhard Lakemeyer, University of Bonn
Representation for Actions and Motion
Towards Knowledge-Level Analysis of Motion Planning / 670
Ronen I. Brafman, Jean-Claude Latombe and Yoav Shoham, Stanford University
EL: A Formal, Yet Natural, Comprehensive Knowledge Representation / 676
Chung Hee Hwang and Lenhart K. Schubert, University of Rochester
The Semantics of Event Prevention / 683
Charles L. Ortiz, Jr., University of Pennsylvania
The Frame Problem and Knowledge-Producing Actions / 689
Richard B. Scherl and Hector J. Levesque, University of Toronto
Rule-Based Reasoning
The Paradoxical Success of Fuzzy Logic / 698
Charles Elkan, University of California, San Diego
Exploring the Structure of Rule Based Systems / 704
Clifford Grossner, Alun D. Preece, P. Gokul Chander, T. Radhakrishnan, and Ching Y. Suen, Concordia University
Supporting and Optimizing Full Unification in a Forward Chaining Rule System / 710
Howard E. Shrobe, Massachusetts Institute of Technology
Comprehensibility Improvement of Tabular Knowledge Bases / 716
Atsushi Sugiura and Yoshiyuki Koseki, NEC Corporation; Maximilian Riesenhuber, Johann Wolfgang Goethe-University
Search
Time-Saving Tips for Problem Solving with Incomplete Information / 724
Michael R. Genesereth and Illah R. Nourbakhsh, Stanford University
Decomposition of Domains Based on the Micro-Structure of Finite Constraint-Satisfaction Problems / 731
Philippe Jégou, Université de Provence
Innovative Design as Systematic Search / 737
Dorothy Neville and Daniel S. Weld, University of Washington
Generating Effective Admissible Heuristics by Abstraction and Reconstitution / 743
Armand Prieditis, University of California, Davis and Bhaskar Janakiraman, Silicon Graphics Inc.
Iterative Weakening: Optimal and Near-Optimal Policies for the Selection of Search Bias / 749
Foster John Provost, University of Pittsburgh
Pruning Duplicate Nodes in Depth-First Search
Larry A. Taylor and Richard E. Korf, University of California, Los Angeles / 756
Conjunctive Width Heuristics for Maximal Constraint Satisfaction / 762
Richard J. Wallace and Eugene C. Freuder, University of New Hampshire
Depth-First vs. Best-First Search: New Results / 769
Weixiong Zhang and Richard E. Korf, University of California, Los Angeles
Statistically-Based Natural Language Processing
Using an Annotated Language Corpus as a Virtual Stochastic Grammar / 778
Rens Bod, University of Amsterdam
Equations for Part-of-Speech Tagging / 784
Eugene Charniak, Curtis Hendrickson, Neil Jacobson and Mike Perkowitz, Brown University
Estimating Probability Distributions over Hypotheses with Variable Unification / 790
Dekai Wu, Hong Kong University of Science and Technology
Trainable Natural Language Systems
A Case-Based Approach to Knowledge Acquisition for Domain-Specific Sentence Analysis / 798
Claire Cardie, University of Massachusetts
KITSS: A Knowledge-Based Translation System for Test Scenarios / 804
Van E. Kelly and Mark A. Jones, AT&T Bell Laboratories
Automatically Constructing a Dictionary for Information Extraction Tasks / 811
Ellen Riloff, University of Massachusetts
Learning Semantic Grammars with Constructive Inductive Logic Programming / 817
John M. Zelle and Raymond J. Mooney, University of Texas
Vision Processing
Polly: A Vision-Based Artificial Agent / 824
Ian Horswill, MIT AI Laboratory
Range Estimation From Focus Using a Non-frontal Imaging Camera / 830
Arun Krishnan and Narendra Ahuja, University of Illinois
Learning Object Models from Appearance / 836
Hiroshi Murase, NTT Basic Research Labs and Shree K. Nayar, Columbia University
On the Qualitative Structure of Temporally Evolving Visual Motion Fields / 844
Richard P. Wildes, SRI David Sarnoff Research Center
Invited Talks
Tiger in a Cage: The Applications of Knowledge-based Systems (1993) / 852
Edward A. Feigenbaum, Stanford University
Artificial Intelligence as an Experimental Science / 853
Herbert A. Simon, Carnegie Mellon University
Video Abstracts
A Demonstration of the Circuit Fix-it Shoppe / 856
D. Richard Hipp and Ronnie W. Smith, Duke University
Instructo-Soar: Learning from Interactive Natural Language Instructions / 857
Scott B. Huffman and John E. Laird, The University of Michigan
Winning the AAAI Robot Competition / 858
David Kortenkamp, Marcus Huber, Charles Cohen, Ulrich Raschke, Clint Bidlack, Clare Bates Congdon, Frank Koss, and Terry Weymouth, The University of Michigan
AIR-SOAR: Intelligent Multi-Level Control / 860
Douglas J. Pearson, Randolph M. Jones, and John E. Laird, The University of Michigan
Selective Perception for Robot Driving / 862
Douglas A. Reece, University of Central Florida and Steven A. Shafer, Carnegie Mellon University
Computer Vision Research at the University of Massachusetts / 863
Edward M. Riseman and Allen R. Hanson, University of Massachusetts; J. Indigo Thomas and Members of the Computer Vision Laboratory, University of Massachusetts
A Fuzzy Controller for Flakey, the Robot / 864
Alessandro Saffiotti, Nicholas Helft, Kurt Konolige, John Lowrance, Karen Myers, Daniela Musto, Enrique Ruspini, and Leonard Wesley, SRI International