Proceedings of the Tenth National Conference on Artificial Intelligence
Sponsored by the Association for the Advancement of Artificial Intelligence
Paul Rosenbloom and Peter Szolovits, Program Cochairs
July 12-16, 1992, San Jose, 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
Explanation and Tutoring
Understanding Causal Descriptions of Physical Systems / 2
Gary C. Borchardt, Massachusetts Institute of Technology
Generating Cross-References for Multimedia Explanation / 9
Kathleen R. McKeown, Steven K. Feiner, Jacques Robin, Dorée D.
Seligmann, and Michael Tanenblatt, Columbia University
Results of Encoding Knowledge with Tutor Construction Tools / 17
Tom Murray and Beverly Park Woolf, University of Massachusetts
Steps from Explanation Planning to Model Construction Dialogues / 24
Daniel Suthers, Beverly Woolf, and Matthew Cornell, University of
Massachusetts
Learning
Learning: Constructive and Linguistic
A Connectionist Parser with Recursive Sentence Structure and Lexical
Disambiguation / 32
George Berg, State University of New York at Albany
Learning to Disambiguate Relative Pronouns / 38
Claire Cardie, University of Massachusetts
Discrimination-Based Constructive Induction of Logic Programs / 44
Boonserm Kijsirikul, Masayuki Numao, and Masamichi Shimura, Tokyo
Institute of Technology
Learning Relations by Pathfinding / 50
Bradley L. Richards and Raymond J. Mooney, University of Texas at Austin
Learning: Discovery
Symmetry as Bias: Rediscovering Special Relativity / 56
Michael Lowry, NASA Ames Research Center
Theory-Driven Discovery of Reaction Pathways in the MECHEM System / 63
Raul E. Valdes-Perez, Carnegie Mellon University
Discovery of Equations: Experimental Evaluation of Convergence / 70
Robert Zembowicz and Jan M. Zytkow, Wichita State University
Operational Definition Refinement: A Discovery Process / 76
Jan M. Zytkow, Jieming Zhu, and Robert Zembowicz, Wichita State
University
Learning: Inductive
Learning in FOL with a Similarity Measure / 82
Gilles Bisson, Université Paris-sud
Learning to Learn Decision Trees / 88
Vlad G. Dabija, Stanford University; Katsuhiko Tsujino and Shogo Nishida
Mitsubishi Electric Corporation
A Personal Learning Apprentice / 96
Lisa Dent, Jesus Boticario, Tom Mitchell and David Zabowski, Carnegie
Mellon University; John McDermott, Digital Equipment Corporation
The Attribute Selection Problem in Decision Tree Generation / 104
Usama M. Fayyad, Jet Propulsion Laboratory / California Institute of
Technology; Keki B. Irani, The University of Michigan
COGIN: Symbolic Induction with Genetic Algorithms / 111
David Perry Greene and Stephen F. Smith, Carnegie Mellon University
Polynomial-Time Learning with Version Spaces / 117
Haym Hirsh, Rutgers University
ChiMerge: Discretization of Numeric Attributes / 123
Randy Kerber, Lockheed AI Center
The Feature Selection Problem: Traditional Methods and a New Algorithm / 129
Kenji Kira, Mitsubishi Electric Corporation; Larry A. Rendell,
University of Illinois
Discrete Sequence Prediction and its Applications / 135
Philip Laird, NASA Ames Research Center
Classifier Learning from Noisy Data as Probabilistic Evidence
Combination / 141
Steven W. Norton, Rutgers University and Siemens Corporate Research;
Haym Hirsh, Rutgers University
Sparse Data and the Effect of Overfitting Avoidance in Decision Tree
Induction / 147
Cullen Schaffer, CUNY/Hunter College
Complementary Discrimination Learning with Decision Lists / 153
Wei-Min Shen, Microelectronics and Computer Technology Corporation
Learning: Neural Network and Hybrid
A Framework for Integrating Fault Diagnosis and Incremental Knowledge
Acquisition in Connectionist Expert Systems / 159
Joo-Hwee Lim, Ho-Chung Lui and Pei-Zhuang Wang, National University of
Singapore
Using Knowledge-Based Neural Networks to Improve Algorithms: Refining the
Chou-Fasman Algorithm for Protein Folding / 165
Richard Maclin and Jude W. Shavlik, University of Wisconsin
Adapting Bias by Gradient Descent: An Incremental Version of
Delta-Bar-Delta / 171
Richard S. Sutton, GTE Laboratories Incorporated
Using Symbolic Learning to Improve Knowledge-Based Neural Networks / 177
Geoffrey G. Towell, Siemens Corporate Research; Jude W. Shavlik,
University of Wisconsin
Learning: Robotic
Reinforcement Learning with Perceptual Aliasing: The Perceptual Distinctions
Approach / 183
Lonnie Chrisman, Carnegie Mellon University
Acquisition of Automatic Activity through Practice: Changes in Sensory
Input / 189
Jack Gelfand, Marshall Flax, Raymond Endres, Stephen Lane and David
Handelman, Princeton University
Automatic Programming of Robots Using Genetic Programming / 194
John R. Koza and James P. Rice, Stanford University
Reinforcement Learning with a Hierarchy of Abstract Models / 202
Satinder P. Singh, University of Massachusetts
Learning: Theory
Inferring Finite Automata with Stochastic Output Functions and an
Application to Map Learning / 208
Thomas Dean, Kenneth Basye, Leslie Kaelbling, Evangelos Kokkevis, and
Oded Maron, Brown University; Dana Angluin and Sean Engelson, Yale University
Oblivious PAC Learning of Concept Hierarchies / 215
Michael J. Kearns, AT&T Bell Laboratories
An Analysis of Bayesian Classifiers / 223
Pat Langley, Wayne Iba, and Kevin Thompson, NASA Ames Research Center
A Theory of Unsupervised Speedup Learning / 229
Prasad Tadepalli, Oregon State University
Learning: Utility and Bias
COMPOSER: A Probabilistic Solution to the Utility Problem in Speed-Up
Learning / 235
Jonathan Gratch and Gerald DeJong, University of Illinois at
Urbana-Champaign
A Statistical Approach to Solving the EBL Utility Problem / 241
Russell Greiner, Siemens Corporate Research; Igor Juriusica, University
of Toronto
Empirical Analysis of the General Utility Problem in Machine Learning / 249
Lawrence B. Holder, University of Texas at Arlington
Inductive Policy / 255
Foster John Provost and Bruce G. Buchanan, University of Pittsburgh
Multi-Agent Coordination
Constrained Intelligent Action: Planning Under the Influence of a Master
Agent / 263
Eithan Ephrati and Jeffrey S. Rosenschein, Hebrew University
Using Joint Responsibility to Coordinate Collaborative Problem Solving in
Dynamic Environments / 269
N. R. Jennings and E. H. Mamdani, Queen Mary and Westfield College
On the Synthesis of Useful Social Laws for Artificial Agent Societies
(Preliminary Report) / 276
Yoav Shoham and Moshe Tennenholtz, Stanford University
A General-Equilibrium Approach to Distributed Transportation Planning / 282
Michael P. Wellman, USAF Wright Laboratory
Natural Language
Natural Language: Intepretation
An Approach to the Representation of Iterative Situations / 291
Michael J. Almeida, SUNY Plattsburgh
Actions, Beliefs and Intentions in Rationale Clauses and Means Clauses / 296
Cecile T. Balkanski, Harvard University
An On-Line Computational Model of Human Sentence Interpretation / 302
Daniel Jurafsky, University of California, Berkeley
Literal Meaning and the Comprehension of Metaphors / 309
Steven L. Lytinen, Robert R. Burridge, and Jeffrey D. Kirtner, The
University of Michigan
Natural Language: Parsing
Parsing Run Amok: Relation-Driven Control for Text Analysis / 315
Paul S. Jacobs, GE Research and Development Center
A Probabilistic Parser Applied to Software Testing Documents / 322
Mark A. Jones, AT&T Bell Laboratories; Jason Eisner, Cambridge
University
Classifying Texts Using Relevancy Signatures / 329
Ellen Riloff and Wendy Lehnert, University of Massachusetts
Shipping Departments vs. Shipping Pacemakers: Using Thematic Analysis to
Improve Tagging Accuracy / 335
Uri Zernik, General Electric Research and Development Center
Perception
Computation of Upper-Bounds for Stochastic Context-Free Languages / 344
A. Corazza, Istituto per la Ricerca Scientifica e Tecnologica; R. De
Mori, McGill University; G. Satta, University of Pennsylvania
A Computational Model for Face Location Based on Cognitive Principles / 350
Venu Govindaraju, Sargur N. Srihari and David Sher, State University of New York at Buffalo
Grouping Iso-Velocity Points for Ego-Motion Recovery / 356
Yibing Yang and Alan Yuille, Harvard University
Planning
Cultural Support for Improvisation / 363
Philip E. Agre, University of California, San Diego; Ian D. Horswill,
Massachusetts Institute of Technology
The Expected Value of Hierarchical Problem-Solving / 369
Fahiem Bacchus and Qiang Yang, University of Waterloo
Achieving the Functionality of Filter Conditions in a Partial Order
Planner / 375
Gregg Collins and Louise Pryor, Northwestern University
On the Complexity of Domain-Independent Planning / 381
Kutluhan Erol, Dana S. Nau, and V. S. Subrahmanian, University of
Maryland
Analyzing Failure Recovery to Improve Planner Design / 387
Adele E. Howe, University of Massachusetts
Constrained Decision Revision / 393
Charles Petrie, MCC AI Lab
Learning from Goal Interactions in Planning: Goal Stack Analysis and
Generalization / 401
Kwang Ryel Ryu and Keki B. Irani, The University of Michigan
Problem Solving
Problem Solving: Constraint Satisfaction
Efficient Propositional Constraint Propagation / 409
Mukesh Dalal, Rutgers University
Semantic Evaluation as Constraint Network Consistency / 415
Nicholas J. Haddock, Hewlett Packard Laboratories
An Efficient Cross Product Representation of the Constraint Satisfaction
Problem Search Space / 421
Paul D. Hubbe and Eugene C. Freuder, University of New Hampshire
On the Density of Solutions in Equilibrium Points for the Queens
Problem / 428
Paul Morris, IntelliCorp
An Improved Connectionist Activation Function for Energy Minimization / 434
Gadi Pinkas, Washington University; Rina Dechter, University of
California, Irvine
A New Method for Solving Hard Satisfiability Problems / 440
Bart Selman, AT&T Bell Laboratories; Hector Levesque, University of Toronto; David Mitchell, Simon Fraser University
On the Minimality and Decomposability of Constraint Networks / 447
Peter van Beek, University of Alberta
Solving Constraint Satisfaction Problems Using Finite State Automata / 453
Nageshwara Rao Vempaty, University of Central Florida
Problem Solving: Hardness and Easiness
Hard and Easy Distributions of SAT Problems / 459
David Mitchell, Simon Fraser University; Bart Selman, AT&T Bell
Laboratories; Hector Levesque, University of Toronto
How Long Will It Take? / 466
Ron Musick and Stuart Russell, University of California, Berkeley
Using Deep Structure to Locate Hard Problems / 472
Colin P. Williams and Tad Hogg, Xerox Palo Alto Research Center
Problem Solving: Real-Time
Run-Time Prediction for Production Systems / 478
Franz Barachini and Hans Mistelberger, Alcatel-ELIN Research Center;
Anoop Gupta, Stanford University
Can Real-Time Search Algorithms Meet Deadlines? / 486
Babak Hamidzadeh and Shashi Shekhar, University of Minnesota
Comparison of Three Algorithms for Ensuring Serializable Executions in
Parallel Production Systems / 492
James G. Schmolze, Tufts University; Daniel E. Neiman, University of
Massachusetts
Real-time Metareasoning with Dynamic Trade-off Evaluation / 500
Ursula M. Schwuttke, Jet Propulsion Laboratory, California Institute of Technology; Les Gasser, University of Southern California
Problem Solving: Search and Expert Systems
On Optimal Game Tree Propagation for Imperfect Players / 507
Eric B. Baum, NEC Research Institute
Improved Decision-Making in Game Trees: Recovering from Pathology / 513
Arthur L. Delcher, Loyola College in Maryland; Simon Kasif, The Johns
Hopkins University
Modeling Accounting Systems to Support Multiple Tasks: A Progress
Report / 519
Walter C. Hamscher, Price Waterhouse Technology Centre
Moving Target Search with Intelligence / 525
Toru Ishida, NTT Communication Science Laboratories
Linear-Space Best-First Search: Summary of Results / 533
Richard E. Korf, University of California, Los Angeles
Performance of IDA on Trees and Graphs / 539
Ambui Mahanti, Subrata Ghosh, Dana S. Nau, L. N. Kanal, University of Maryland; Asim K. Pal, IIM, Calcutta
An Average-Case Analysis of Branch-and-Bound with Applications: Summary of
Results / 545
Weixiong Zhang and Richard E. Korf, University of California, Los
Angeles
Representation and Reasoning
Representation and Reasoning: Abduction and Diagnosis
Dynamic MAP Calculations for Abduction / 552
Eugene Charniak, and Eugene Santos, Jr., Brown University
Consistency-Based Diagnosis in Physiological Domains / 558
Keith L. Downing, Linkoping University
Adaptive Model-Based Diagnostic Mechanism Using a Hierarchical Model
Scheme / 564
Yoichiro Nakakuki, Yoshiyuki Koseki, and Midori Tanaka, NEC Corporation
Reasoning MPE to Multiply Connected Belief Networks Using Message
Passing / 570
Bon K. Sy, Queens College, City University of New York
Representation and Reasoning: Action and Change
Formalizing Reasoning about Change: A Qualitative Reasoning Approach
(Preliminary Report) / 577
James M. Crawford and David W. Etherington, AT&T Bell Laboratories
Deriving Properties of Belief Update from Theories of Action / 584
Alvaro del Val and Yoav Shoham, Stanford University
Concurrent Actions in the Situation Calculus / 590
Fangzhen Lin and Yoav Shoham, Stanford University
Nonmonotonic Sorts for Feature Structures / 596
Mark A. Young, The University of Michigan
Representation and Reasoning: Belief
From Statistics to Beliefs / 602
Fahiem Bacchus, University of Waterloo; Adam Grove and Daphne Koller,
Stanford University; Joseph Y. Halpern, IBM Almaden Research Center
A Logic for Revision and Subjunctive Queries / 609
Craig Boutilier, University of British Columbia
Lexical Imprecision in Fuzzy Constraint Networks / 616
James Bowen, Robert Lai and Dennis Bahler, North Carolina State University
A Symbolic Generalization of Probability Theory / 622
Adnan Y. Darwiche and Matthew L. Ginsberg, Stanford University
A Logic of Knowledge and Belief for Recursive Modeling: A Preliminary
Report / 628
Piotr J. Gmytrasiewicz and Edmund H. Durfee, University of Michigan
Ideal Introspective Belief / 635
Kurt Konolige, SRI International
A Belief-Function Logic / 642
Alessandro Saffiotti, Université Libre de Bruxelles
Combining Circumscription and Modal Logic / 648
Jacques Wainer, University of Colorado
Representation and Reasoning: Case-Based
Generating Dialectical Examples Automatically / 654
Kevin D. Ashley and Vincent Aleven, University of Pittsburgh
Common Sense Retrieval / 661
A. Julian Craddock, University of British Columbia
When Should a Cheetah Remind You of a Bat? Reminding in Case-Based Teaching / 667
Daniel C. Edelson, Northwestern University
Model-Based Case Adaptation / 673
Eric K. Jones, Victoria University of Wellington
Representation and Reasoning: Qualitative
Qualitative Simulation Based on a Logical Formalism of Space and Time / 679
Z. Cui, A. G. Cohn and D. A. Randell, University of Leeds
Self-Explanatory Simulations: Scaling Up to Large Models / 685
Kenneth D. Forbus, Northwestern University; Brian Falkenhainer, Xerox
Palo Alto Research Center
Towards a Qualitative Lagrangian Theory of Fluid Flow / 691
Gordon Skorstad, University of Illinois
On the Qualitative Structure of a Mechanical Assembly / 697
Randall H. Wilson and Jean-Claude Latombe, Stanford University
Representation and Reasoning: Qualitative Model Construction
Causal Approximations / 703
P. Pandurang Nayak, Stanford University
Automated Model Selection Using Context-Dependent Behaviors / 710
P. Pandurang Nayak, Stanford University; Leo Joskowicz and Sanjaya
Addanki, IBM T. J. Watson Research Center
Learning Engineering Models with the Minimum Description Length
Principle / 717
R. Bharat Rao and Stephen C-Y. Lu, University of Illinois at
Urbana-Champaign
Automatic Abduction of Qualitative Models / 723
Bradley L. Richards and Benjamin J. Kuipers, University of Texas,
Austin; Ina Kraan, University of Edinburgh
Representation and Reasoning: Temporal
Complexity Results for Serial Decomposability / 729
Tom Bylander, The Ohio State University
Temporal Reasoning in Sequence Graphs / 735
Jürgen Dorn, Technical University Vienna
Algorithms and Complexity for Reasoning about Time / 741
Martin Charles Golumbic, IBM Israel Scientific Center and Bar-Ilan
University; Ron Shamir, Tel Aviv University
On the Computational Complexity of Temporal Projection and Plan
Validation / 748
Bernhard Nebel, German Research Center for Artificial Intelligence;
Christer Backström, Linköping University
Representation and Reasoning: Terminological
Computing Least Common Subsumers in Description Logics / 754
William W. Cohen, AT&T Bell Laboratories; Alex Borgida and Haym
Hirsh, Rutgers University
A Non-Well-Founded Approach to Terminological Cycles / 761
Robert Dionne, Eric Mays and Frank J. Oles, IBM T. J. Watson Research
Center
An Empirical Analysis of Terminological Representation Systems / 767
Jochen Heinsohn, Daniel Kudenko, Bernhard Nebel and Hans-Jürgen
Profitlich, German Research Center for Artificial Intelligence
Recognition Algorithms for the Loom Classifier / 774
Robert M. MacGregor and David Brill, USC/Information Sciences Institute
Representation and Reasoning: Tractability
An Improved Incremental Algorithm for Generating Prime Implicates / 780
Johan de Kleer, Xerox Palo Alto Research Center
Forming Concepts for Fast Inference / 786
Henry Kautz and Bart Selman, AT&T Bell Laboratories
The Complexity of Propositional Default Logics / 794
Jonathan Stillman, General Electric Research and Development Center
Robot Navigation
A Reactive Robot System for Find and Fetch Tasks in an Outdoor
Environment / 801
R. Peter Bonasso, H. James Antonisse, and Marc G. Slack, The MITRE
Corporation
Integrating Planning and Reacting in a Heterogeneous Asynchronous
Architecture for Controlling Real-World Mobile Robots / 809
Erann Gat, Jet Propulsion Laboratory, California Institute of Technology
Landmark-Based Robot Navigation / 816
Anthony Lazanas and Jean-Claude Latombe, Stanford University
Reactive Navigation through Rough Terrain: Experimental Results / 823
David P. Miller, Rajiv S. Desai, Erann Gat, Robert Ivlev and John Loch,
Jet Propulsion Laboratory, California Institute of Technology
Scaling Up
Learning 10,000 Chunks: What’s It Like Out There? / 830
Bob Doorenbos, Milind Tambe, and Allen Newell, Carnegie Mellon
University
Mega-Classification: Discovering Motifs in Massive Datastreams / 837
Nomi L. Harris, Lawrence Hunter, and David J. States, National
Institutes of Health
Building Large-Scale and Corporate-Wide Case-Based Systems: Integration of
the Organizational and Machine Executable Algorithms / 843
Hiroaki Kitano, Akihiro Shibata, Hideo Shimazu, Juichirou Kajihara, and Atsumi Sato, NEC Corporation
Wafer Scale Integration for Massively Parallel Memory-Based Reasoning / 850
Hiroaki Kitano and Moritoshi Yasunaga, Carnegie Mellon University
Invited Talks
What Your Computer Really Needs to Know, You Learned in Kindergarten / 858
Edmund H. Durfee, University of Michigan
Reasoning as Remembering: The Theory and Practice of CBR / 865
Kristian Hammond, University of Chicago
Artificial Intelligence and Molecular Biology / 866
Lawrence Hunter, National Library of Medicine