Proceedings of the Eleventh National Conference on Artificial Intelligence
Sponsored by the Association for the Advancement of Artificial Intelligence
Barbara Hayes-Roth and Richard E. Korf, Program Cochairs
August 1-4, 1994, 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
Volume One
The Arts
Art
Criticism, Culture, and the Automatic Generation of Artworks
Lee Spector and Adam Alpern, Hampshire College / 3
Believable Agents
Research Problems in the Use of a Shallow Artificial Intelligence Model of Personality and Emotion
Clark Elliott, DePaul University and Northwestern University / 9
ChatterBots, TinyMuds, and the Turing Test: Entering the Loebner Prize Competition
Michael L. Mauldin, Carnegie Mellon University / 16
Social Interaction: Multimodal Conversation with Social Agents
Katashi Nagao and Akikazu Takeuchi, Sony Computer Science Laboratory Inc. / 22
Case-Based Reasoning
Experience-Aided Diagnosis for Complex Devices
Michel P. Féret and Janice I.Glasgow, Queen’s University / 29
Heuristic Harvesting of Information for Case-Based Argument
Edwina L. Rissland, David B. Skalak and M. Timur Friedman, University of Massachusetts / 36
Case-Based Acquisition of User Preferences for Solution Improvement in Ill-Structured Domains
Katia Sycara, Carnegie Mellon University and Kazuo Miyashita, Matsushita Electric Industrial Co. / 44
Towards More Creative Case-Based Design Systems
Linda M. Wills and Janet L. Kolodner, Georgia Institute of Technology / 50
Retrieving Semantically Distant Analogies with Knowledge-Directed Spreading Activation
Michael Wolverton and Barbara Hayes-Roth, Stanford University / 56
Cognitive Modeling
A Reading Agent
Tamitha Carpenter and Richard Alterman, Brandeis University / 62
The Capacity of Convergence-Zone Episodic Memory
Mark Moll, University of Twente; Risto Miikkulainen, The University of Texas at Austin; Jonathan Abbey, Applied Research Laboratories / 68
A Model of Creative Understanding
Kenneth Moorman and Ashwin Ram, Georgia Institute of Technology / 74
Ordering Relations in Human and Machine Planning
Lee Spector, Mary Jo Rattermann, and Kristen Prentice, Hampshire College / 80
Experimentally Evaluating Communicative Strategies: The Effect of the Task
Marilyn A. Walker, Mitsubishi Electric Research Laboratories / 86
Music and Audition
Automated Accompaniment of Musical Ensembles
Lorin Grubb and Roger B. Dannenberg, Carnegie Mellon University / 94
Auditory Stream Segregation in Auditory Scene Analysis with a Multi-Agent System
Tomohiro Nakatani, Hiroshi G. Okuno, and Takeshi Kawabata, NTT Basic Research Laboratories / 100
Simulating Creativity in Jazz Performance
Geber Ramalho and Jean-Gabriel Ganascia, Université Paris VI / 108
The Synergy of Music Theory and AI: Learning Multi-Level Expressive Interpretation
Gerhard Widmer, University of Vienna and the Austrian Research Institute for Artificial Intelligence / 114
Theater and Video
Knowledge Representation for Video
Marc Davis, Interval Research Corporation / 120
Semi-Autonomous Animated Actors
Steve Strassmann, Apple Computer, Inc. / 128
Automated Reasoning
Rule Based Updates on Simple Knowledge Bases
Chitta Baral, University of Texas at El Paso / 136
Recovering Software Specifications with Inductive Logic Programming
William W. Cohen, AT&T Bell Laboratories / 142
Can We Enforce Full Compositionality in Uncertainty Calculi?
Didier DuBois and Henri Prade, Université Paul Sabatier / 149
An Empirical Evaluation of Knowledge Compilation by Theory Approximation
Henry Kautz and Bart Selman, AT&T Bell Laboratories/ 155
ModGen: Theorem Proving by Model Generation
Sun Kim and Hantao Zhang, University of Iowa / 162
Small is Beautiful: A Brute-Force Approach to Learning First-Order Formulas
Steven Minton and Ian Underwood, Recom Technologies, NASA Ames Research Center / 168
Avoiding Tests for Subsumption
Anavai Ramesh and Neil V. Murray, State University of New York at Albany / 175
On Kernel Rules and Prime Implicants
Ron Rymon, University of Pittsburgh / 181
Using Hundreds of Workstations to Solve First-Order Logic Problems
Alberto Maria Segre and David B. Sturgill, Cornell University / 187
Termination Analysis of OPS5 Expert Systems
Hsiu-yen Tsai and Albert Mo Kim Cheng, University of Houston / 193
Description Logic
Refining the Structure of Terminological Systems: Terminology = Schema + Views
M. Buchheit and W. Nutt, German Research Center for Artificial Intelligence; F. M. Donini and A. Schaerf, Università di Roma "La Sapienza"/ 199
Boosting the Correspondence between Description Logics and Propositional Dynamic Logics
Giuseppe De Giacomo and Maurizio Lenzerini, Università di Roma "La Sapienza" / 205
A Description Classifier for the Predicate Calculus
Robert M. MacGregor, USC / Information Sciences Institute / 213
Causal Reasoning and Uncertainty Management
Causal Reasoning
Forming Beliefs about a Changing World
Fahiem Bacchus, University of Waterloo; Adam J. Grove, NEC Research Institute; Joseph Y. Halpern, IBM Almaden Research Center; Daphne Koller, University of California, Berkeley / 222
Probabilistic Evaluation of Counterfactual Queries
Alexander Balke and Judea Pearl, University of California, Los Angeles / 230
Symbolic Causal Networks
Adnan Darwiche, Rockwell International Science Center and Judea Pearl, University of California, Los Angeles/ 238
Causal Default Reasoning: Principles and Algorithms
Hector Geffner, Universidad Simín Bolóvar / 245
Testing Physical Systems
Peter Struss, Technical University of Munich / 251
Uncertainty Management
Abstraction in Bayesian Belief Networks and Automatic Discovery from Past Inference Sessions
Wai Lam, University of Waterloo/ 257
Noise and Uncertainty Management in Intelligent Data Modeling
Xiaohui Liu, Gongxian Cheng, and John Xingwang Wu, University of London / 263
Markov Chain Monte-Carlo Algorithms for the Calculation of Dempster-Shafer Belief
Serafín Moral, Universidadde Granada and Nic Wilson, Queen Mary and Westfield College / 269
Focusing on the Most Important Explanations: Decision-Theoretic Horn Abduction
Paul O'Rorke, University of California, Irvine/ 275
The Emergence of Ordered Belief from Initial Ignorance
Paul Snow / 281
Constraint Satisfaction
Advances in Backtracking
The Hazards of Fancy Backtracking
Andrew B. Baker, University of Oregon / 288
Dead-End Driven Learning
Daniel Frost and Rina Dechter, University of California, Irvine / 294
In Search of the Best Constraint Satisfaction Search
Daniel Frost and Rina Dechter, University of California, Irvine / 301
Solution Reuse in Dynamic Constraint Satisfaction Problems
Gerard Verfaillie and Thomas Schiex, ONERA-CERT / 307
Weak-Commitment Search for Solving Constraint Satisfaction Problems
Makoto Yokoo, NTT Communication Science Laboratories / 313
Constraint Satisfaction Techniques
Planning from First Principles for Geometric Constraint Satisfaction
Sanjay Bhansali, Washington State University and Glenn A. Kramer, Enterprise Integration Technologies / 319
GENET: A Connectionist Architecture for Solving Constraint Satisfaction Problems by Iterative Improvement
Andrew Davenport, Edward Tsang, Chang J. Wang, and Kangmin Zhu, University of Essex / 325
Expected Gains from Parallelizing Constraint Solving for Hard Problems
Tad Hogg and Colin P. Williams, Xerox Palo Alto Research Center / 331
Noise Strategies for Improving Local Search
Bart Selman, Henry A. Kautz and Bram Cohen, AT&T Bell Laboratories / 337
Improving Repair-Based Constraint Satisfaction Methods by Value Propagation
Nobuhiro Yugami, Yuiko Ohta, and Hirotaka Hara, Fujitsu Laboratories Ltd. / 344
Tractable Constraint-Satisfaction Problems
An Approach to Multiply Segmented Constraint Satisfaction Problems
Randall A. Helzerman and Mary P. Harper, Purdue University / 350
Reasoning about Temporal Relations: A Maximal Tractable Subclass of Allen’s Interval Algebra
Bernhard Nebel, Universität Ulm and Hans-Jürgen Bürckert, DFKI/ 356
A Filtering Algorithm for Constraints of Difference in CSPs
Jean-Charles Rëgin, Université Montpellier II / 362
On the Inherent Level of LocalConsistency in Constraint Networks
Peter van Beek, University of Alberta / 368
Distributed AI
Collaboration
Divide and Conquer in Multi-Agent Planning
Eithan Ephrati, University of Pittsburgh and Jeffrey S. Rosenschein, Hebrew University/ 375
Progressive Negotiation for Resolving Conflicts among Distributed Heterogeneous Cooperating Agents
Taha Khedro and Michael R. Genesereth, Stanford University / 381
A Collaborative Parametric Design Agent
Daniel Kuokka and Brian Livezey, Lockheed Palo Alto Research Laboratories / 387
Exploiting Meta-Level Information in a Distributed Scheduling System
Daniel E. Neiman, David W. Hildum, Victor R. Lesser and Tuomas W. Sandholm, University of Massachusetts / 394
A Computational Market Model for Distributed Configuration Design
Michael P. Wellman, University of Michigan / 401
Coordination
Emergent Coordination through the Use of Cooperative State-Changing Rules
Claudia V. Goldman and Jeffrey S. Rosenschein, Hebrew University / 408
Forming Coalitions in the Face of Uncertain Rewards
Steven Ketchpel, Stanford University / 414
The Impact of Locality and Authority on Emergent Conventions: Initial Observations
James E. Kittock, Stanford University / 420
Learning to Coordinate without Sharing Information
Sandip Sen, Mahendra Sekaran, and John Hale, University of Tulsa / 426
Coalition, Cryptography, and Stability: Mechanisms for Coalition Formation in Task OrientedDomains
Gilad Zlotkin, MIT and Jeffrey S. Rosenschein, Hebrew University / 432
Software Agents
An Experiment in the Design of Software Agents
Henry Kautz, Bart Selman, Michael Coen, Steven Ketchpel and Chris Ramming, AT&T Bell Laboratories / 438
Collaborative Interface Agents
Yezdi Lashkari, Max Metral and Pattie Maes, MIT Media Laboratory / 444
Enabling Technologies
Combining Left and Right Unlinking for Matching a Large Number of Learned Rules
Robert B. Doorenbos,Carnegie Mellon University / 451
Discovering Procedural Executions of Rule-Based Programs
David Gadbois and Daniel Miranker, University of Texas at Austin / 459
Mechanisms for Efficiency in Blackboard Systems
Michael Hewett, University of Texas at Austin and Rattikorn Hewett, Florida Atlantic University / 465
Model-Based Automated Generation of User Interfaces
Angel R. Puerta, Henrik Eriksson, John H. Gennari and Mark A. Musen, Stanford University / 471
The Relationship between Architectures and Example-Retrieval Times
Eiichiro Sumita, Naoya Nisiyama and Hitoshi Iida, ATR Interpreting Telecommunications Research Laboratories / 478
Instructional Environments
An Instructional Environment for Practicing Argumentation Skills
Vincent Aleven and KevinD. Ashley, University of Pittsburgh / 485
Tailoring Retrieval to Support Case-Based Teaching
Robin Burke, University of Chicagoand Alex Kass, Northwestern University / 493
Situated Plan Attribution for Intelligent Tutoring
Randall W. Hill, Jr., Jet Propulsion Laboratory / Caltech and W. Lewis Johnson, USC / Information Sciences Institute / 499
Learning from Highly Flexible Tutorial Instruction
Scott B. Huffman and John E. Laird, University of Michigan / 506
Case-Based Retrieval Interface Adapted to Customer-Initiated Dialogues in Help Desk Operations
Hideo Shimazu, Akihiro Shibata and Katsumi Nihei, NEC Corporation / 513
Knowledge Bases
Knowledge Acquisition, Capture, and Integration
Knowledge Refinement in a Reflective Architecture
Yolanda Gil, USC / Information Sciences Institute / 520
A User Interface for Knowledge Acquisition from Video
Henry Lieberman, Massachusetts Institute of Technology / 527
Building Non-Brittle Knowledge-Acquisition Tools
Jay T. Runkel and William P. Birmingham, University of Michigan / 535
The Acquisition, Analysis and Evaluation of Imprecise Requirements for Knowledge-Based Systems
John Yen, Xiaoqing Liu and Swee Hor Teh, Texas A&M University / 541
Knowledge Bases
Extracting Viewpoints from Knowledge Bases
Liane Acker, IBM Corporation and Bruce Porter, University of Texas at Austin / 547
Using Induction to Refine Information Retrieval Strategies
Catherine Baudin and Barney Pell, NASA Ames Research Center; Smadar Kedar, Northwestern University / 553
Formalizing Ontological Commitments
Nicola Guarino, National Research Council, Italy; Massimiliano Carrara; Pierdaniele Giaretta, University of Padova / 560
Machine Learning
Control Learning
Exploiting the Ordering of Observed Problem-Solving Steps for Knowledge Base Refinement: An Apprenticeship Approach
Steven K. Donoho and David C. Wilkins, University of Illinois / 569
Improving Learning Performance through Rational Resource Allocation
Jonathan Gratch and Gerald DeJong, University of Illinois; Steve Chien, JPL / California Institute of Technology / 576
Learning Explanation-Based Search Control Rules for Partial Order Planning
Suresh Katukam and Subbarao Kambhampati, Arizona State University / 582
Creating Abstractions Using Relevance Reasoning
Alon Y. Levy, AT&T Bell Laboratories / 588
Flexible Strategy Learning: Analogical Replay of Problem Solving Episodes
Manuela M. Veloso, Carnegie Mellon University / 595
Decision-Tree Learning
Branching on Attribute Values in Decision Tree Generation
Usama M. Fayyad, JPL / California Institute of Technology / 601
Induction of Multivariate Regression Trees for Design Optimization
B. Forouraghi, L. W. Schmerr and G. M. Prabhu, Iowa State University / 607
Bottom-Up Induction of Oblivious Read-Once Decision Graphs: Strengths and Limitations
Ron Kohavi, Stanford University / 613
Learning Decision Lists Using Homogeneous Rules
Richard Segal and Oren Etzioni, University of Washington / 619
Decision Tree Pruning: Biased or Optimal?
Sholom M. Weiss, Rutgers University and Nitin Indurkhya, University of Sydney / 626
Discovery
An Implemented Model of Punning Riddles
Kim Binsted and Graeme Ritchie, University of Edinburgh / 633
Bootstrapping Training-Data Representations for Inductive Learning: A Case Study in Molecular Biology
Haym Hirsh and Nathalie Japkowicz, Rutgers University / 639
A Discovery System for Trigonometric Functions
Tsuyoshi Murata, Masami Mizutani and Masamichi Shimura, Tokyo Institute of Technology / 645
Induction
Compositional Instance-Based Learning
Patrick Broos and Karl Branting, University ofWyoming / 651
Learning to Recognize Promoter Sequences in E. coli by Modeling Uncertainty in the Training Data
Steven W. Norton, Rutgers University / 657
Inductive Learning for Abductive Diagnosis
Cynthia A. Thompson and Raymond J. Mooney, University of Texas / 664
Learning Fault-Tolerant Speech Parsing with SCREEN
Stefan Wermter and Volker Weber, University of Hamburg / 670
PAC Learning
Pac-Learning Nondeterminate Clauses
William W. Cohen, AT&T Bell Laboratories / 676
Learning to Reason
Roni Khardon and Dan Roth, Harvard University / 682
Reinforcement Learning
Catching a Baseball: A Reinforcement Learning Perspective Using a Neural Network
Rajarshi Das, Santa Fe Institute and Sreerupa Das, University of Colorado / 688
Incorporating Advice into Agents that Learn from Reinforcements
Richard Maclin and Jude W. Shavlik, University of Wisconsin / 694
Reinforcement Learning Algorithms for Average-Payoff Markovian Decision Processes
Satinder P. Singh, Massachusetts Institute ofTechnology / 700
Meta AI
Using Knowledge Acquisition and Representation Tools to Support Scientific Communities
Brian R. Gaines and Mildred L. G. Shaw, University of Calgary / 707
Talking About AI: Socially Defined Linguistic Subcontexts in AI
Amy M. Steier and Richard K. Belew, University of California, San Diego / 715
Natural Language Processing
Corpus-Based Natural Language Processing
Some Advances in Transformation-Based Part of Speech Tagging
Eric Brill,MIT / 722
Context-Sensitive Statisticsfor Improved Grammatical Language Models
Eugene Charniak and Glenn Carroll, Brown University / 728
Toward the Essential Nature of Statistical Knowledge in Sense Resolution
Jill Fain Lehman, Carnegie Mellon University / 734
A Probabilistic Algorithm for Segmenting Non-Kanji Japanese Strings
Virginia Teller and Eleanor Olds Batchelder, The City University of New York / 742
Inducing Deterministic Prolog Parsers from Treebanks: A Machine Learning Approach
John M. Zelle and Raymond J. Mooney, University of Texas / 748
Lexical Acquisition
The Ups and Downs of Lexical Acquisition
Peter M. Hastings, University of Michigan and Steven L. Lytinen, DePaul University / 754
Lexical Acquisition in the Presence of Noise and Homonymy
Jeffrey Mark Siskind, University of Toronto / 760
Natural Language Applications
Kalos -- A System for Natural Language Generation with Revision
Ben E. Cline and J. Terry Nutter, Virginia Polytechnic Institute and State University / 767
Building a Large-Scale Knowledge Base for Machine Translation
Kevin Knight and Steve K. Luk, USC / Information Sciences Institute / 773
Automated Postediting of Documents
Kevin Knight and Ishwar Chander, USC / Information Sciences Institute / 779
A Prototype Reading Coach that Listens
Jack Mostow, Steven F. Roth, Alexander G. Hauptmann and Matthew Kane, Carnegie Mellon University / 785
Visual Semantics: Extracting Visual Information from Text Accompanying Pictures
Rohini K. Srihari and Debra T. Burhans, StateUniversity of New York at Buffalo / 793
Natural Language Discourse
A Plan-Based Model for Response Generation in Collaborative Task-Oriented Dialogues
Jennifer Chu-Carroll and Sandra Carberry, University of Delaware / 799
Classifying Cue Phrases in Text and Speech Using Machine Learning
Diane J. Litman, AT&T Bell Laboratories / 806
An Artificial Discourse Language for Collaborative Negotiation
Candace L. Sidner, Lotus Development Corporation / 814
Emergent Linguistic Rules from Inducing Decision Trees: Disambiguating Discourse Clue Words
Eric V. Siegel and Kathleen R. McKeown, Columbia University / 820
Corpus-Driven Knowledge Acquisition for Discourse Analysis
Stephen Soderland and Wendy Lehnert, University of Massachusetts / 827
Syntax
Principled Multilingual Grammars for Large Corpora
Sharon Flank and Paul Krause, Systems Research and Applications Corporation; Carol Van Ess-Dykema, Department of Defense / 833
L* Parsing: A General Framework for Syntactic Analysis of Natural Language
Eric K. Jones and Linton M. Miller, Victoria University of Wellington / 839
Volume Two
Neural Networks
Unclear Distinctions Lead to Unnecessary Shortcomings: Examining the Rule Versus Fact, Role versus Filler, and Type Versus Predicate Distinctions from a Connectionist Representation and Reasoning Perspective
Venkat Ajjanagadde, Universitaet Tuebingen/ 846
Associative Memory in an Immune-Based System
C.J. Gibert and T. W. Routen, De Montfort University / 852
Parsing Embedded Clauses with Distributed Neural Networks
Risto Miikkulainen, University of Texas at Austin and Dennis Bijwaard, University of Twente / 858
Spurious Symptom Reduction in Fault Monitoring Using a Neural Network and Knowledge Base Hybrid System
Roger M. Records and Jai J. Choi, Boeing Computer Services / 865
Learning to Learn: Automatic Adaptation of Learning Bias
Steve G. Romaniuk, National University of Singapore / 871
Neural Programming Language
Hava T. Siegelmann, Bar-Ilan University / 877
Multi-Recurrent Networks for Traffic Forecasting
Claudia Ulbricht, Austrian Research Institute for Artificial Intelligence / 883
Knowledge Matrix -- An Explanation and Knowledge Refinement Facility for a Rule Induced NeuralNetwork
Daniel S. Yeung and Hank-shun Fong, Hong Kong Polytechnic / 889
Epsilon-Transformation: Exploiting Phase Transitions to Solve Combinatorial Optimization Problems Initial Results
Weixiong Zhang and Joseph C. Pemberton, University of California, Los Angeles / 895
Nonmonotonic Reasoning
Belief Revision
A Preference-Based Approach toDefault Reasoning: Preliminary Report
James P. Delgrande, Simon Fraser University / 902
On the Relation between the Coherence and Foundations Theories of Belief Revision
Alvaro del Val, Stanford University / 909
Conditional Logics of Belief Change
Nir Friedman, Stanford University and Joseph Y. Halpern, IBM Almaden Research Center / 915
Incremental Recompilation of Knowledge
Goran Gogic and Christos H. Papadimitriou, University of California, San Diego; Martha Sideri, Athens University of Economics and Business / 922
Qualitative Decision Theory
Sek-Wah Tan and Judea Pearl, University of California, Los Angeles / 928
Nonmonotonic Reasoning
Soundness and Completeness of a Logic Programming Approach to Default Logic
Grigoris Antoniou and Elmar Langetepe, University of Osnabrueck / 934
Reasoning about Priorities in Default Logic
Gerhard Brewka, GMD / 940
Is Intractability of Non-Monotonic Reasoning a Real Drawback?
Marco Cadoli,Francesco M. Donini and Marco Schaerf, Università di Roma "La Sapienza" / 946
A Knowledge Representation Framework Based on Autoepistemic Logic of Minimal Beliefs
Teodor C. Przymusinski, University of California, Riverside / 952
Perception
A New Approach to Tracking 3D Objects in 2D Image Sequences
Michael Chan and Dimitri Metaxas, University of Pennsylvania; Sven Dickinson, University of Toronto / 960
Automatic Symbolic Traffic Scene Analysis Using Belief Networks
T. Huang, D. Koller, J. Malik, G. Ogasawara, B. Rao, S. Russell and J. Weber, University of California, Berkeley / 966
Sensible Decisions: Toward a Theory of Decision-Theoretic Information Invariants
Keiji Kanazawa, University of California, Berkeley/ 973
Topological Mapping for Mobile Robots Using a Combination of Sonar and Vision Sensing
David Kortenkamp and Terry Weymouth, University of Michigan / 979
Applying VC-Dimension Analysis to 3D Object Recognition from Perspective Projections
Michael Lindenbaum and Shai Ben-David, Technion / 985
Planning and Scheduling
Causal-Link Planning
Derivation Replay for Partial-Order Planning
Laurie H. Ihrig and Subbarao Kambhampati, Arizona State University / 992
Tractable Planning with State Variables by Exploiting Structural Restrictions
Peter Jonsson and Christer Bäckström, Linköping University / 998
Least-Cost Flaw Repair: A Plan Refinement Strategy for Partial-Order Planning
David Joslin and Martha E. Pollack, University of Pittsburgh / 1004
Temporal Planning with Continuous Change
J. Scott Penberthy, IBM T. J. Watson Research Center and Daniel S. Weld, University of Washington / 1010
Planning: Agents
Using Abstractions for Decision-Theoretic Planning with Time Constraints
Craig Boutilier and Richard Dearden, University of British Columbia / 1016
Acting Optimally in Partially Observable Stochastic Domains
Anthony R. Cassandra, Leslie Pack Kaelbling and Michael L. Littman, Brown University / 1023
Cost-Effective Sensing during Plan Execution
Eric A. Hansen, University of Massachusetts / 1029
Using Abstraction and Nondeterminism to Plan Reaction Loops
David J. Musliner, University of Maryland / 1036
The First Law of Robotics (A Call to Arms)
Daniel Weld and Oren Etzioni, University of Washington / 1042
Planning: Representation
Omnipotence without Omniscience: Efficient Sensor Management for Planning
Keith Golden, Oren Etzioni and Daniel Weld, University of Washington / 1048
On the Nature of Modal Truth Criteria in Planning
Subbarao Kambhampati , Arizona State University and Dana S. Nau, University of Maryland / 1055
Causal Pathways of Rational Action
Charles L. Ortiz, Jr., University of Pennsylvania / 1061
Temporal Reasoning with Constraints on Fluents and Events
Eddie Schwalb, Kalev Kask and Rina Dechter, University of California, Irvine / 1067
Planning Under Uncertainty
An Algorithm for Probabilistic Least-Commitment Planning
Nicholas Kushmerick, Steve Hanks and Daniel Weld, University of Washington / 1073
Control Strategies for a Stochastic Planner
Jonathan Tash and Stuart Russell, University of California, Berkeley / 1079
Scheduling
Generating Feasible Schedules under Complex Metric Constraints
Cheng-Chung Cheng and Stephen F. Smith, Carnegie Mellon University / 1086
Experimental Results on the Application of Satisfiability Algorithms to Scheduling Problems
James M. Crawford and Andrew B. Baker, University of Oregon / 1092
Just-In-Case Scheduling
Mark Drummond, John Bresina, and Keith Swanson, NASA Ames Research Center / 1098
On the Utility of Bottleneck Reasoning for Scheduling
Nicola Muscettola, Recom Technologies, NASA Ames Research Center / 1105
A Constraint-Based Approach to High-School Timetabling Problems: A Case Study
Masazumi Yoshikawa, Kazuya Kaneko, Yuriko Nomura and Masanobu Watanabe, NEC Corporation / 1111
Task Network Planning
Task-Decomposition via Plan Parsing
Anthony Barrett and Daniel S. Weld, University of Washington / 1117
HTN Planning: Complexity and Expressivity
Kutluhan Erol, James Hendler and Dana S. Nau, University of Maryland / 1123
The Use of Condition Types to Restrict Search in an AI Planner
Austin Tate, Brian Drabble and Jeff Dalton, University of Edinburgh / 1129
Qualitative and Model-Based Reasoning
Model-Based Reasoning
Prediction Sharing Across Time and Contexts
Oskar Dressler and Hartmut Freitag, Siemens AG / 1136
An Operational Semantics for Knowledge Bases
Ronald Fagin and Joseph Y. Halpern, IBM Almaden Research Center; Yoram Moses, Weizmann Institute of Science; Moshe Y. Vardi, Rice University / 1142
Reasoning with Models
Roni Khardon and Dan Roth, Harvard University / 1148
Representing Multiple Theories
P. Pandurang Nayak, Recom Technologies, NASA Ames Research Center / 1154
How Things Appear to Work: Predicting Behaviors from Device Diagrams
N. Hari Narayanan, Masaki Suwa, and Hiroshi Motoda, Hitachi Ltd. / 1161
Qualitative Reasoning: Modeling
A Qualitative Physics Compiler
Adam Farquhar, Stanford University/ 1168
Using Qualitative Physics to Build Articulate Software for Thermodynamics Education
Kenneth D. Forbus, Northwestern University and Peter B. Whalley, Oxford University / 1175
Automated Model Selection for Simulation
Yumi Iwasaki, Stanford University and Alon Y. Levy, AT&T Bell Laboratories / 1183
Automated Modeling for Answering Prediction Questions: Selecting the Time Scale and System Boundary
Jeff Rickel and Bruce Porter, University of Texas / 1191
Decompositional Modeling through Caricatural Reasoning
Brian C. Williams and Olivier Raiman, Xerox Palo Alto Research Center / 1199
Qualitative Reasoning: Simulation
Comparative Simulation
Michael Neitzke and Bernd Neumann, Universität Hamburg / 1205
Qualitative Reasoning for Automated Exploration for Chaos
Toyoaki Nishida, Nara Institute of Science and Technology / 1211
Activity Analysis: The Qualitative Analysis of Stationary Points for Optimal Reasoning
Brian C. Williams, Xerox Palo Alto Research Center and Jonathan Cagan, Carnegie Mellon University / 1217
Intelligent Automated Grid Generation for Numerical Simulations
Ke-Thia Yao and Andrew Gelsey, Rutgers University / 1224
Robotics
Formal Models of Reactive Control
Structured Circuit Semantics for Reactive Plan Execution Systems
Jaeho Lee and Edmund H. Durfee, University of Michigan / 1232
Estimating Reaction Plan Size
Marcel Schoppers, Robotics Research Harvesting / 1238
Learning Robotic Agents
Results on Controlling Action with Projective Visualization
Marc Goodman, Cognitive Systems, Inc. and Brandeis University / 1245
Learning to Select Useful Landmarks
Russell Greiner, Siemens Corporate Research and Ramana Isukapalli, Rutgers University / 1251
Agents that Learn to Explain Themselves
W. Lewis Johnson, USC / Information Sciences Institute / 1257
Learning to Explore and Build Maps
David Pierce and Benjamin Kuipers, University of Texas at Austin / 1264
High Dimension Action Spacesin Robot Skill Learning
Jeff G. Schneider, University of Rochester / 1272
Robot Control, Locomotion and Manipulation
Robot Behavior Conflicts: Can Intelligence Be Modularized?
Amol Dattatraya Mali and Amitabha Mukerjee, Indian Institute of Technology Kanpur / 1279
Merging Path Planners and Controllers through Local Context
Sundar Narasimhan, MIT Artificial Intelligence Laboratory / 1285
Teleassistance: Contextual Guidance for Autonomous Manipulation
Polly K. Pook and Dana H. Ballard, University of Rochester / 1291
Automatically Tuning Control Systems for Simulated Legged Robots
Robert Ringrose, MIT Artificial Intelligence Laboratory / 1297
Reactive Deliberation: An Architecture for Real-Time Intelligent Control in Dynamic Environments
Michael K. Sahota, University of British Columbia / 1303
Search and Genetic Algorithms
Genetic Algorithms and Simulated Annealing
Exploiting Problem Structure in Genetic Algorithms
Scott H. Clearwater and Tad Hogg,Xerox Palo Alto Research Center / 1310
Increasing the Efficiency of Simulated Annealing Search by Learning to Recognize (Un)Promising Runs
Yoichiro Nakakuki, NEC Corp. and Norman Sadeh, Carnegie Mellon University / 1316
Improving Search through Diversity
Peter Shell, Carnegie Mellon University; Juan Antonio Hernandez Rubio and Gonzalo Quiroga Barro, Union Fenosa / 1323
Genetic Programming and AI Planning Systems
Lee Spector, Hampshire College / 1329
Hierarchical Chunking in Classifier Systems
Gerhard Weiss, Technische Universität München / 1335
Search
Exploiting Algebraic Structure in Parallel State Space Search
Jonathan Bright, Simon Kasif and Lewis Stiller, The Johns Hopkins University / 1341
The Trailblazer Search: A New Method for Searching and Capturing Moving Targets
Fumihiko Chimura and Mario Tokoro, Keio University / 1347
ITS: An Efficient Limited-Memory Heuristic Tree Search Algorithm
Subrata Ghosh and Dana S. Nau, University of Maryland; Ambuj Mahanti, Indian Institute of Management Calcutta / 1353
Memory-Bounded Bidirectional Search
Hermann Kaindl, Siemens AG Österreich and Aliasghar Khorsand / 1359
Two-Player Games
Best-First Minimax Search: Othello Results
Richard E. Korf and David Maxwell Chickering, University of California, Los Angeles / 1365
Evolving Neural Networks to Focus Minimax Search
David E. Moriarty and Risto Miikkulainen, University of Texas at Austin / 1371
A Strategic Metagame Player for General Chesslike Games
Barney Pell, RIACS, NASA Ames Research Center / 1378
An Analysis of Forward Pruning
Stephen J. J. Smith and Dana S. Nau, University of Maryland / 1386
Spatial Reasoning
Basic Meanings of Spatial Relations: Computation and Evaluation in 3D Space
Klaus-Peter Gapp, Universität des Saarlandes / 1393
Spatial Reasoning in Indeterminate Worlds
Janice Glasgow, Queen’s University / 1399
Automatic Depiction of Spatial Descriptions
Patrick Olivier, University of Wales; Toshiyuki Maeda, Matsushita Electric Ind. Co. Ltd.; Jun-ichi Tsujii, University of Manchester / 1405
A Model for Integrated Qualitative Spatial and Dynamic Reasoning about Physical Systems
Raman Rajagopalan, University of Texas atAustin/ 1411
A Theory for Qualitative Spatial Reasoning Based on Order Relations
Ralf Röhrig, University of Hamburg / 1418
Student Abstracts
Classification of NounPhrases into Concepts or Individuals
Saliha Azzam, CRILIngénierie / 1425
Regression Based Causal Induction with Latent Variable Models
Lisa A. Ballesteros, University of Massachusetts / Amherst / 1426
Probabilistic Knowledge of External Events in Planning
Jim Blythe, Carnegie Mellon University / 1427
DANIEL: Integrating Case-Based and Rule-Based Reasoning in Law
StefanieBrüninghaus, Universität Mannheim / 1428
Decision-Theoretic Plan Failure Debugging and Repair
Lisa J. Burnell,University of Texas at Arlington / 1429
Decidability of Contextual Reasoning
Vanja Buvac, Dartmouth College / 1430
Simplifying Bayesian Belief Nets while Preserving MPE or MPGE Ordering
YaLing Chang, City University of New York / 1431
Abstract of the Forest Management Advisory Systems
Yousong Chang and Donald Nute, University of Georgia / 1432
SodaBot: A Software Agent Environment and Construction System
Michael H. Coen, MIT Artificial Intelligence Laboratory / 1433
Empirical Knowledge Representation Generation Using N-Gram Clustering
Robin Collier, University of Sheffield / 1434
Case-Based Introspection
Michael T. Cox, Georgia Institute of Technology / 1435
Time Units and Calendars
Diana Cukierman and James Delgrande, Simon Fraser University / 1436
Local Search in the Coordination of Intelligent Agents
Daniel E. Damouth and Edmund H. Durfee, University of Michigan / 1437
GKR: A Generic Model of Knowledge Representation
Angélica de Antonio, Jesús Cardeñosa, Loïc Martinez Normand, Campus de Montegancedo / 1438
Experiments Towards Robotic Learning by Imitation
John Demiris, University of Edinburgh / 1439
Goal-Clobbering Avoidance in Non-Linear Planners
Rujith de Silva, Carnegie Mellon University / 1440
Dynamically Adjusting Categories to Accommodate Changing Contexts
Mark Devaney and Ashwin Ram, Georgia Institute of Technology / 1441
Substructure Discovery Using Minimum Description Length Principle and Background Knowledge
Surnjani Djoko, University of Texas at Arlington / 1442
Exploiting the Ordering of Observed Problem-Solving Steps for Knowledge Base Refinement: An Apprenticeship Approach
Steven K. Donoho and David C. Wilkins, University of Illinois / 1443
The KM / KnEd System: An Integrated Approach to Building Large-Scale Multifunctional Knowledge Bases
Erik Eilerts, University of Texas/ 1444
Situated Agents Can Have Plans
Mark Fasciano, University of Chicago / 1445
Introspective Reasoning in a Case-Based Planner
Susan Fox and David Leake, Indiana University / 1446
A Statistical Method for Handling Unknown Words
Alexander Franz, Carnegie Mellon University / 1447
Low Computation Vision-Based Navigation for a Martian Rover
Andrew S. Gavin, Massachusetts Institute of Technology / 1448
Learning about Software Errors Via Systematic Experimentation
Terrance Goan and Oren Etzioni, University of Washington / 1449
Reasoning about What to Plan
Richard Goodwin, Carnegie Mellon University / 1450
The Crystallographer’s Assistant
Vanathi Gopalakrishnan, Daniel Hennessy, Bruce Buchanan and Devika Subramanian, University of Pittsburgh / 1451
Time-Critical Scheduling in Stochastic Domains
Lloyd Greenwald and Thomas Dean, Brown University / 1452
Planning for Compotent-Based Configurations
Gail Haddock, University of Texas at Arlington / 1453
The Epistemology of Physical System Modeling
Kyungsook Han and Andrew Gelsey, Rutgers University / 1454
Testing a KBS Using a Conceptual Model
Corinne Haouche, DIAM-SIM & LAMSADE / 1455
A Dynamic Organization in Distributed Constraint Satisfaction
Katsutoshi Hirayama, Seiji Yamada and Junuichi Toyoda, Osaka University/ 1456
Tractable Anytime Temporal Constraint Propagation
Louis J.Hoebel, University of Rochester/ 1457
Processing Pragmatics for Computer-Assisted Language Instruction
Keiko Horiguchi, Carnegie Mellon University / 1458
Generating Rhythms with Genetic Algorithms
Damon Horowitz, MIT Media Laboratory / 1459
The Automated Mapping of Plans for Plan Recognition
Marcus J. Huber, Edmund H. Durfee and Michael P. Wellman, The University of Michigan / 1460
Preliminary Studies in Agent Design in Simulated Environments
Scott B. Hunter, Cornell University / 1461
Dempster-Shafer and Bayesian Networks for CAD-Based Feature Extraction: A Comparative Investigation and Analysis
Qiang Ji, Michael M. Marefat and Paul J. A. Lever, University of Arizona / 1462
Finding Multivariate Splits in Decision Trees Using Function Optimization
George H. John, Stanford University / 1463
When the Best Move Isn’t Optimal: Q-learning with Exploration
George H. John, Stanford University / 1464
HIPAIR: Interactive Mechanism Analysis and Design Using Configuration Spaces
Leo Joskowicz, IBM T. J. Watson Research Center and Elisha Sacks, Princeton University / 1465
Learning Sorting Networks By Grammars
Thomas E. Kammeyer and Richard K. Belew, University of California, San Diego / 1466
The Formation of Coalitions among Self-Interested Agents
Steven Ketchpel, Stanford University / 1467
Learning from Ambiguous Examples
Stephen V. Kowalski, University of Southern California / 1468
Exploiting the Environment: Urban Navigation as a Case Study
Nicholas Kushmerick, University of Washington / 1469
Quantitative Evaluation of the Exploration Strategies of a Mobile Robot
David Lee and Michael Recce, University College London / 1470
Everyday Reasoning Meets Geometry Theorem-Proving
Thomas F. McDougal, University of Chicago / 1471
Determination of Machine Condition Using Neural Networks
John MacIntyre, Peter Smith and John Tait, University of Sunderland / 1472
Building a Parser that Can Afford to Interact with Semantics
Kavi Mahesh, Georgia Institute of Technology / 1473
Using Errors to Create Piecewise Learnable Partitions
Oded Maron, MIT Artificial Intelligence Lab / 1474
Development of an Intelligent Forensic System for Hair Analysis and Comparison
C. Medina, L. Pratt and C. Ganesh, Colorado School of Mines / 1475
Model-Based Sensor Diagnosis: When Monitoring Should be Monitored
Joel Milgram, Electricité De France / 1476
Theoretical and Experimental Studies of Temporal Constraint Satisfaction Problem
Debasis Mitra, University of Southwestern Louisiana / 1477
A Theory of Reading
Kenneth Moorman and Ashwin Ram, Georgia Institute of Technology / 1478
A Hybrid Parallel IDA Search
Shubha S. Nerur, University of Texas at Arlington / 1479
Time-Situated Reasoning within Tight Deadlines and Realistic Space and Computation Bounds
Madhura Nirkhe, University of Maryland / 1480
Integrating Induction & Instruction: Connectionist Advice Taking
David C. Noelle and Garrison W. Cottrell, University of California, San Diego / 1481
A Comparison of Reinforcement Learning Methods for Automatic Guided Vehicle Scheduling
DoKyeong Ok, Oregon State University / 1482
Making the Most of What You've Got: Using Models and Data to Improve Learning Rate and Prediction Accuracy
Julio Ortega, Vanderbilt University / 1483
Learning Quality-Enhancing Control Knowledge
M. Alicia Perez, Carnegie Mellon University / 1484
Database Learning for Software Agents
Mike Perkowitz and Oren Etzioni, University of Washington / 1485
Diagnosing Multiple Interacting Defects with Combination Descriptions
Nancy E. Reed, University of Minnesota / 1486
Building Emotional Characters for Interactive Drama
W. Scott Reilly, Carnegie Mellon University / 1487
On the Computation of Point ofView
Warren Sack, MIT Media Laboratory / 1488
Multi-Agent Learning in Non-Cooperative Domains
Mahendra Sekaran and Sandip Sen, University of Tulsa / 1489
Coalition Formation Methods in Multi-Agent Environments
Onn Shechory, Bar Ilan University / 1490
Integrating Specialized Procedures in Proof Systems
Vishal Sikka, Stanford University / 1491
Towards Situated Explanation
Raja Sooriamurthi and David Leake, Indiana University / 1492
Reflective Reasoning and Learning
Eleni Stroulia, Georgia Institiute of Technology / 1493
Case-Based Reasoning for Weather Prediction
C. Vasudevan, Florida Atlantic University / 1494
Agent Modeling Methods Using Limited Rationality
José M. Vidal and Edmund H. Durfee, University of Michigan / 1495
Learning by Observation and Practice: A Framework for Automatic Acquisition of Planning Operators
Xuemei Wang, Carnegie Mellon University / 1496
A Modular Visual Tracking System
Mike Wessler, MIT Artificial Intelligence Laboratory / 1497
Utility-Directed Planning
Mike Williamson and Steve Hanks, University of Washington / 1498
Fuzzy Irrigation Decision Support System
Hong Xiang, Brahm P. Verma, and Gerrit Hoogenboom, University of Georgia / 1499
Synthetic Robot Language Development
Holly A. Yanco, MIT Artificial Intelligence Laboratory / 1500
Computer Simulation of Statistics and Educational Measurement StatSim: An Intelligent Tutoring System for Statistics
Liu Zhang and Donald Potter, University of Georgia / 1501
Video Program
Guardian: A Prototype Intelligent Agent for Intensive-Care Monitoring
Barbara Hayes-Roth, Serdar Uckun, and Jan Eric Larsson, KSL / Stanford University; David Gaba, Juliana Barr, and Jane Chien, Stanford University School of Medicine / 1503
Dynamic Generation of Complex Behavior
Randolph M. Jones, University of Michigan / 1504
HIPAIR: Interactive Mechanism Analysis and Design Using Configuration Spaces
Leo Joskowicz, IBM T.J. Watson Research Center and Elisha Sacks, Princeton University / 1505
ALIVE: Artificial Life Interactive Video Environment
Pattie Maes, Trevor Darrell, Bruce Blumberg and Sandy Pentland, MIT Media Laboratory / 1506
A Reading Coach that Listens: (Edited Video Transcript)
Jack Mostow, Alex Hauptmann, Steven F. Roth, Matt Kane, Adam Swift, Lin Chase and Bob Weide, Carnegie Mellon Robotics Institute / 1507
Machine Rhythm
David Rosenthal, International Media Research Foundation / 1508
Index to Volumes One and Two / 1509