Proceedings of the Thirteenth National Conference on Artificial Intelligence
Sponsored by the Association for the Advancement of Artificial Intelligence
Bill Clancey and Dan Weld, Program Cochairs
August 4-8, 1996, Portland, Oregon. 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
Organization of AAAI / xix
AAAI-96 Program Committee / xxi
IAAI-96 Program Committee / xxv
AAAI-96 Best Paper Award / xxvi
Volume One
Agents
Interaction
Agent Amplified Communication / 3
Henry Kautz, Bart Selman, and Al Milewski, AT&T Laboratories
The ContactFinder Agent: Answering Bulletin Board Questions with Referrals / 10
Bruce Krulwich and Chad Burkey, Andersen Consulting
Deciding to Remind during Collaborative Problem Solving: Empirical Evidence for Agent Strategies / 16
Pamela W. Jordan, University of Pittsburgh and Marilyn A. Walker, ATT Research Laboratories
Toward a Semantics for an Agent Communications Language Based on Speech-Acts / 24
Ira A. Smith and Philip R. Cohen, Oregon Graduate Institute
Internet Agents
Planning to Gather Information / 32
Chung T. Kwok and Daniel S. Weld, University of Washington
Query-Answering Algorithms for Information Agents / 40
Alon Y. Levy, AT&T Research; Anand Rajaraman, Stanford University; and Joann J. Ordille, Bell Laboratories
Hybrid Hill-Climbing and Knowledge-Based Methods for Intelligent News Filtering / 48
Kenrick J. Mock, University of California, Davis
Syskill & Webert: Identifying Interesting Web Sites / 54
Michael J. Pazzani, Jack Muramatsu and Daniel Billsus, University of California, Irvine
Multiagent Learning
Learning Models of Intelligent Agents / 62
David Carmel and Shaul Markovitch, Technion
Cooperative Learning over Composite Search Spaces: Experiences with a Multi-Agent Design System / 68
M V Nagendra Prasad, University of Massachusetts; Susan E. Lander, Blackboard Technology Group, Inc.; and Victor R. Lesser, University of Massachusetts
Scaling Up: Distributed Machine Learning with Cooperation / 74
Foster John Provost, NYNEX Science & Technology and Daniel N. Hennessy, University of Pittsburgh
Tracking Dynamic Team Activity / 80
Milind Tambe, University of Southern California
Multiagent Problem Solving
Nearly Monotonic Problems: A Key to Effective FA/C Distributed Sensor Interpretation? / 88
Norman Carver, Southern Illinois University; Victor Lesser and Robert Whitehair, University of Massachusetts
Analysis of Utility-Theoretic Heuristics for Intelligent Adaptive Network Routing / 96
Armin R. Mikler, Vasant Honavar and Johnny S. K. Wong, Iowa State University
The Use of Artificially Intelligent Agents with Bounded Rationality in the Study of Economic Markets / 102
Vijay Rajan and James R. Slagle, University of Minnesota
Total-Order Multi-Agent Task-Network Planning for Contract Bridge / 108
S. J. J. Smith and D. S. Nau, University of Maryland; T. A. Throop, Great Game Products
Negotiation & Coalition
Learning other Agents’ Preferences in Multiagent Negotiation / 114
H. H. Bui, D. Kieronska and S. Venkatesh, Curtin University of Technology
Incorporating Opponent Models into Adversary Search / 120
David Carmel and Shaul Markovitch, Technion
Advantages of a Leveled Commitment Contracting Protocol / 126
Tuomas W. Sandholm and Victor R. Lesser, University of Massachusetts at Amherst
A Kernel-Oriented Model for Coalition-Formation in General Environments: Implementation and Results / 134
Onn Shehory and Sarit Kraus, Bar Ilan University
AI in Art and Entertainment
Video
Coping with Temporal Constraints in Multimedia Presentation Planning / 142
Elisabeth André and Thomas Rist, German Research Center for Artificial Intelligence (DFKI)
Video
Declarative Camera Control for Automatic Cinematography / 148
David B. Christianson, Sean E. Anderson, Li-Wei He, David H. Salesin, and Daniel S. Weld, University of Washington; Michael F. Cohen, Microsoft Research
A Model of Poetic Comprehension / 156
Kenneth Haase, MIT Media Laboratory
A Framework for Plot Control in Interactive Story Systems / 162
N. M. Sgouros, G. Papakonstantinou, and P. Tsanakas, National Technical University of Athens
Constraint Satisfaction
Constraint Satisfaction
Approximate Resolution of Hard Numbering Problems / 169
Olivier Bailleux and Jean-Jacques Chabrier, CRID Université de Bourgogne
Mixed Constraint Satisfaction: A Framework for Decision Problems under Incomplete Knowledge / 175
Hélène Fargier and Jérôme Lang, IRIT Université Paul Sabatier; Thomas Schiex, INRA
Russian Doll Search for Solving Constraint Optimization Problems / 181
Gérard Verfaillie and Michel Lemaître, CERT-ONERA; Thomas Schiex, INRA
Enhancements of Branch and Bound Methods for the Maximal Constraint Satisfaction Problem / 188
Richard J. Wallace, University of New Hampshire
Data Consistency
Path-Consistency: When Space Misses Time / 196
Assef Chmeiss and Philippe Jégou, Université de Provence
Neighborhood Inverse Consistency Preprocessing / 202
Eugene C. Freuder and Charles D. Elfe, University of New Hampshire
Generalized Arc Consistency for Global Cardinality Constraint / 209
Jean-Charles Régin, ILOG S. A.
Lazy Arc Consistency / 216
Thomas Schiex, INRA; Jean-Charles Régin, ILOG S. A. ; Christine Gaspin, INRA; and Gérard Verfaillie, CERT/ONERA
Game-Tree Search
Searching Game Trees Under Memory Constraints / 222
Subir Bhattacharya and Amitava Bagchi, Indian Institute of Management
Partition Search / 228
Matthew L. Ginsberg, CIRL/University of Oregon
Exploiting Graph Properties of Game Trees / 234
Aske Plaat, Erasmus University; Jonathan Schaeffer, University of Alberta; Wim Pijls and Arie de Bruin, Erasmus University
Forward Estimation for Game-Tree Search / 240
Weixiong Zhang, University of Southern California
Phase Transition
The Constrainedness of Search / 246
Ian P. Gent, Ewan MacIntyre and Patrick Prosser, University of Strathclyde; Toby Walsh, IRST & DIST
Exploiting a Theory of Phase Transitions in Three-Satisfiability Problems / 253
David M. Pennock and Quentin F. Stout, University of Michigan
A Second Order Parameter for 3SAT / 259
Tuomas W. Sandholm, University of Massachusetts
The Very Particular Structure of the Very Hard Instances / 266
Dan R. Vlasie, University of Nice
Search Control
Heuristic-Biased Stochastic Sampling / 271
John L. Bresina, Recom Technologies/NASA Ames Research Center
Easy and Hard Testbeds for Real-Time Search Algorithms / 279
Sven Koenig and Reid G. Simmons, Carnegie Mellon University
Improved Limited Discrepancy Search / 286
Richard E. Korf, University of California, Los Angeles
Efficient Goal-Directed Exploration / 292
Yury Smirnov, Sven Koenig, Manuela M. Veloso and Reid G. Simmons, Carnegie Mellon University
Search & Learning
A Complexity Analysis of Space-Bounded Learning Algorithms for the Constraint Satisfaction Problem / 298
Roberto J. Bayardo, Jr. and Daniel P. Miranker, University of Texas at Austin
Improving the Learning Efficiencies of Realtime Search / 305
Toru Ishida and Masashi Shimbo, Kyoto University
Dynamic Improvements of Heuristic Evaluations during Search / 311
Gerhard Kainz and Hermann Kaindl, Siemens AG Österreich
Inference-Based Constraint Satisfaction Supports Explanation / 318
Mohammed H. Sqalli and Eugene C. Freuder, University of New Hampshire
Stochastic Search
Constraint Satisfaction Using a Hybrid Evolutionary Hill-Climbing Algorithm that Performs Opportunistic Arc and Path Revision / 326
James Bowen, National University of Ireland at Cork and Gerry Dozier, North Carolina A&T State University
Adding New Clauses for Faster Local Search / 332
Byungki Cha and Kazuo Iwama, Kyushu University
Weighting for Godot: Learning Heuristics for GSAT / 338
Jeremy Frank, University of California, Davis
Duplication of Coding Segments in Genetic Programming / 344
Thomas Haynes, The University of Tulsa
A Graph-Based Method for Improving GSAT / 350
Kalev Kask and Rina Dechter, University of California, Irvine
Tuning Local Search for Satisfiability Testing / 356
Andrew J. Parkes, University of Oregon and Joachim P. Walser, Universität des Saarlandes
Tabu Search Techniques for Large High-School Timetabling Problems / 363
Andrea Schaerf, Università di Roma "La Sapienza"
Combining Local Search and Backtracking Techniques for Constraint Satisfaction / 369
Jian Zhang and Hantao Zhang, The University of Iowa
Temporal Reasoning
A Simple Way to Improve Path Consistency Processing in Interval Algebra Networks / 375
Christian Bessière, LIRMM
A Representation for Efficient Temporal Reasoning / 381
James P. Delgrande and Arvind Gupta, Simon Fraser University
Maximal Tractable Subclasses of Allen’s Interval Algebra: Preliminary Report / 389
Thomas Drakengren and Peter Jonsson, Linköping University
A New Proof of Tractability for ORD-Horn Relations / 395
Gérard Ligozat, LIMSI/CNRS & Université Paris-Sud
Education
A Novel Application of Theory Refinement to Student Modeling / 403
Paul T. Baffes, SciComp, Inc. and Raymond J. Mooney, University of Texas at Austin
A Simulation-Based Tutor that Reasons about Multiple Agents / 409
Christopher Rhodes Eliot III and Beverly Park Woolf, University of Massachusetts, Amherst
Scaling Up Explanation Generation: Large-Scale Knowledge Bases and Empirical Studies / 416
James C. Lester, North Carolina State University and Bruce W. Porter, The University of Texas at Austin
Dynamically Sequencing an Animated Pedagogical Agent / 424
Brian A. Stone and James C. Lester, North Carolina State University
Information Retrieval
& Natural Language Processing
Machine Learning of User Profiles: Representational Issues / 433
Eric Bloedorn, The MITRE Corporation & George Mason University; Inderjeet Mani and T. Richard MacMillan, The MITRE Corporation
Interactive Information Retrieval Systems with Minimalist Representation / 439
Eric Domeshek, Smadar Kedar and Andrew Gordon, Northwestern University
Learning Word Meanings by Instruction / 447
Kevin Knight, University of Southern California
Significant Lexical Relationships / 455
Ted Pedersen, Mehmet Kayaalp and Rebecca Bruce, Southern Methodist University
Knowledge-Based Systems
Knowledge-Based Navigation of Complex Information Spaces / 462
Robin D. Burke, Kristian J. Hammond and Benjamin C. Young, University of Chicago
Explicit Representations of Problem-Solving Strategies to Support Knowledge Acquisition / 469
Yolanda Gil and Eric Melz, USC/Information Sciences Institute
CommonKADS Models for Knowledge-Based Planning / 477
John Kingston, University of Edinburgh; Nigel Shadbolt, University of Nottingham; and Austin Tate, University of Edinburgh
Detecting Knowledge Base Inconsistencies Using Automated Generation of Text and Examples / 483
Vibhu O. Mittal and Johanna D. Moore, University of Pittsburgh
Knowledge Compilation
Path-Based Rules in Object-Oriented Programming / 490
James M. Crawford, University of Oregon; Daniel Dvorak, Diane Litman, Anil Mishra and Peter F. Patel-Schneider, AT&T Laboratories
Approximate Knowledge Compilation: The First Order Case / 498
Alvaro del Val, Universidad Autónoma de Madrid
A New Algorithm for Computing Theory Prime Implicates Compilations / 504
Pierre Marquis and Samira Sadaoui, CRIN-CNRS and INRIA-Lorraine
Compilation for Critically Constrained Knowledge Bases / 510
Robert Schrag, University of Texas at Austin
Knowledge Representation
Abstraction
Spatial Aggregation: Language and Applications / 517
Christopher Bailey-Kellogg and Feng Zhao, The Ohio State University; Kenneth Yip, MIT Artificial Intelligence Laboratory
Computing Abstraction Hierarchies by Numerical Simulation / 523
Alan Bundy, University of Edinburgh; Fausto Giunchiglia, IRST and University of Trento; Roberto Sebastiani, University of Genoa; Toby Walsh, IRST and University of Genoa
Hierarchical A*: Searching Abstraction Hierarchies Efficiently / 530
Robert C. Holte, University of Ottawa; M. B. Perez, BNR Ltd. ; R. M. Zimmer and A. J. MacDonald, Brunel University
Commitment Strategies in Hierarchical Task Network Planning / 536
Reiko Tsuneto, University of Maryland; Kutluhan Erol, Intelligent Automation, Inc.; James Hendler and Dana Nau, University of Maryland
Belief & Belief Revision
A Semantic Characterization of an Algorithm for Estimating Others’ Beliefs from Observation / 543
Hideki Isozaki and Hirofumi Katsuno, NTT Basic Research Laboratories
What Is Believed Is What Is Explained (Sometimes) / 550
Renwei Li and Luís Moniz Pereira, Universidade Nova de Lisboa
The Complexity of Model Checking for Belief Revision and Update / 556
Paolo Liberatore and Marco Schaerf, Università di Roma "La Sapienza"
Updating Knowledge Bases with Disjunctive Information / 562
Yan Zhang, University of Western Sydney and Norman Y. Foo, University of Sydney
Description Logics & Probabilistic Reasoning
Irrelevance and Conditioning in First-Order Probabilistic Logic / 569
Daphne Koller, Stanford University and Joseph Y. Halpern, IBM Almaden Research Center
The Limits on Combining Recursive Horn Rules with Description Logics / 577
Alon Y. Levy, AT&T Research and Marie-Christine Rousset, University of Paris-Sud
Verification of Knowledge Bases Based on Containment Checking / 585
Alon Y. Levy, AT&T Research and Marie-Christine Rousset, University of Paris-Sud
Closed Terminologies in Description Logics / 592
Robert A. Weida, IBM T. J. Watson Research Center and Columbia University
Knowledge Bases & Context
Quantificational Logic of Context / 600
Sasa Buvac, Stanford University
Utilizing Knowledge-Base Semantics in Graph-Based Algorithms / 607
Adnan Darwiche, Rockwell Science Center
Scaling up Logic-Based Truth Maintenance Systems via Fact Garbage Collection / 614
John O. Everett and Kenneth D. Forbus, Northwestern University
Contextual Reasoning Is NP-Complete / 621
Fabio Massacci, Università di Roma "La Sapienza"
Nonmonotonic Reasoning
Toward Efficient Default Reasoning / 627
David W. Etherington and James M. Crawford, University of Oregon
Situation Calculus on a Dense Flow of Time / 633
Akira Fusaoka, Ritsumeikan University
Reasoning about Continuous Processes / 639
Christoph S. Herrmann, TH Darmstadt and Michael Thielscher, International Computer Science Institute
Splitting a Default Theory / 645
Hudson Turner, University of Texas at Austin
Reasoning about Action
Formalizing Narratives Using Nested Circumscription / 652
Chitta Baral and Alfredo Gabaldon, University of Texas at El Paso; Alessandro Provetti, Università di Bologna
Reasoning about Nondeterministic and Concurrent Actions: A Process Algebra Approach / 658
Guiseppe De Giacomo and Xiao Jun Chen, Università di Roma "La Sapienza"
On the Range of Applicability of Baker’s Approach to the Frame Problem / 664
G. Neelakantan Kartha, Honeywell Technology Center
Embracing Causality in Specifying the Indeterminate Effects of Actions / 670
Fangzhen Lin, University of Toronto
Learning
Case-Based Reasoning
Improving Case Retrieval by Remembering Questions / 678
Richard Alterman and Daniel Griffin, Brandeis University
Acquiring Case Adaptation Knowledge: A Hybrid Approach / 684
David B. Leake, Andrew Kinley, and David Wilson, Indiana University
Detecting Discontinuities in Case-Bases / 690
Hideo Shimazu and Yosuke Takashima, NEC Corporation
Source Selection for Analogical Reasoning: An Empirical Approach / 696
William A. Stubblefield, Sandia National Laboratories and George F. Luger, University of New Mexico
Decision Trees
An Efficient Algorithm for Finding Optimal Gain-Ratio Multiple-Split Tests on Hierarchical Attributes in Decision Tree Learning / 703
Hussein Almuallim, King Fahd University of Petroleum & Minerals; Yasuhiro Akiba and Shigeo Kaneda, NTT Communication Science Labs
Learning Trees and Rules with Set-Valued Features / 709
William W. Cohen, AT&T Laboratories
Lazy Decision Trees / 717
Jerome H. Friedman, Stanford University; Ron Kohavi, Silicon Graphics, Inc.; and Yeogirl Yun, Stanford University
Bagging, Boosting, and C4. 5 / 725
J. R. Quinlan, University of Sydney
Discovery
The Discovery of the Causes of Leprosy: A Computational Analysis / 731
Vincent Corruble and Jean-Gabriel Ganascia, Université Paris VI
Machine Discovery Based on Numerical Data Generated in Computer Experiments / 737
Tsuyoshi Murata and Masamichi Shimura, Tokyo Institute of Technology
Using a Hybrid Genetic Algorithm and Fuzzy Logic for Metabolic Modeling / 743
John Yen, Bogju Lee and James C. Liao, Texas A&M University
Incremental Discovery of Hidden Structure: Applications in Theory of Elementary Particles / 750
Jan M. Zytkow, Wichita State University and Polish Academy of Sciences; Paul J. Fischer, Sterling Commerce
Enhancing Efficiency
Formalizing Dependency Directed Backtracking and Explanation Based Learning in Refinement Search / 757
Subbarao Kambhampati, Arizona State University
Learning Efficient Rules by Maintaining the Explanation Structure / 763
Jihie Kim and Paul S. Rosenbloom, University of Southern California
Compilation of Non-Contemporaneous Constraints / 771
Robert E. Wray III, John E. Laird and Randolph M. Jones, The University of Michigan
Fundamental Issues
Sequential Inductive Learning / 779
Jonathan Gratch, University of Southern California
Learning to Take Actions / 787
Roni Khardon, Harvard University
Testing the Robustness of the Genetic Algorithm on the Floating Building Block Representation / 793
Robert K. Lindsay and Annie S. Wu, University of Michigan
Inductive Learning
Identifying and Eliminating Mislabeled Training Instances / 799
Carla E. Brodley, Purdue University and Mark A. Friedl, Boston University
Generation of Attributes for Learning Algorithms / 806
Yuh-Jyh Hu and Dennis Kibler, University of California, Irvine
Structural Regression Trees / 812
Stefan Kramer, Austrian Research Institute for Artificial Intelligence
Knowledge Bases
Discovering Robust Knowledge from Dynamic Closed-World Data / 820
Chun-Nan Hsu and Craig A. Knoblock, University of Southern California
Post-Analysis of Learned Rules / 828
Bing Liu and Wynne Hsu, National University of Singapore
KI: A Tool for Knowledge Integration / 835
Kenneth S. Murray, Cycorp
Planning
Multi-Strategy Learning of Search Control for Partial-Order Planning / 843
Tara A. Estlin and Raymond J. Mooney, University of Texas at Austin
Design and Implementation of a Replay Framework Based on a Partial Order Planner / 849
Laurie H. Ihrig and Subbarao Kambhampati, Arizona State University
Is There Any Need for Domain-Dependent Control Information?: A Reply / 855
Steven Minton, USC/Information Sciences Institute
Searching for Planning Operators with Context-Dependent and Probabilistic Effects / 863
Tim Oates and Paul R. Cohen, University of Massachusetts
Reinforcement Learning
Learning Robust Plans for Mobile Robots from a Single Trial / 869
Sean P. Engelson, Bar-Ilan University
An Average-Reward Reinforcement Learning Algorithm for Computing Bias-Optimal Policies / 875
Sridhar Mahadevan, University of South Florida
Auto-Exploratory Average Reward Reinforcement Learning / 881
DoKyeong Ok and Prasad Tadepalli, Oregon State University
Video
Evolution-Based Discovery of Hierarchical Behaviors / 888
Justinian P. Rosca and Dana H. Ballard, University of Rochester
VOLUME TWO
Mobile Robots
Estimating the Absolute Position of a Mobile Robot Using Position Probability Grids / 896
Wolfram Burgard, Dieter Fox, Daniel Hennig, and Timo Schmidt, Universität Bonn
Navigation for Everyday Life / 902
Daniel D. Fu, Kristian J. Hammond and Michael J. Swain, University of Chicago
Guaranteeing Safety in Spatially Situated Agents / 909
Robert C. Kohout and James A. Hendler, University of Maryland; David J. Musliner, Honeywell Technology Center
Video
Recognizing and Interpreting Gestures on a Mobile Robot / 915
David Kortenkamp, Eric Huber, and R. Peter Bonasso, Metrica Inc.
Classifying and Recovering from Sensing Failures in Autonomous Mobile Robots / 922
Robin R. Murphy and David Hershberger, Colorado School of Mines
GARGOYLE: An Environment for Real-Time, Context-Sensitive Active Vision / 930
Peter N. Prokopowicz, Michael J. Swain, R. James Firby, and Roger E. Kahn, University of Chicago
Robot Navigation Using Image Sequences / 938
Christopher Rasmussen and Gregory D. Hager, Yale University
Integrating Grid-Based and Topological Maps for Mobile Robot Navigation / 944
Sebastian Thrun, Carnegie Mellon University and Arno Bücken, Universität Bonn
Model-Based Reasoning
Model-Based Reasoning
Improving Model-Based Diagnosis through Algebraic Analysis: The Petri Net Challenge / 952
Luigi Portinale, Università di Torino
A Model-Based Approach to Blame Assignment: Revising the Reasoning Steps of Problem Solvers / 959
Eleni Stroulia, Center for Applied Knowledge Processing and Ashok K. Goel, Georgia Institute of Technology
Qualitative Multiple-Fault Diagnosis of Continuous Dynamic Systems Using Behavioral Modes / 965
Siddarth Subramanian, National Instruments - Georgetown and Raymond J. Mooney, University of Texas at Austin
A Model-Based Approach to Reactive Self-Configuring Systems / 971
Brian C. Williams and P. Pandurang Nayak, Recom Technologies/NASA Ames Research Center
Qualitative Physics
Trajectory Constraints in Qualitative Simulation / 979
Giorgio Brajnik, Università di Udine and Daniel J. Clancy, University of Texas at Austin
A Formal Hybrid Modeling Scheme for Handling Discontinuities in Physical System Models / 985
Pieter J. Mosterman and Gautam Biswas, Vanderbilt University
Building Steady-State Simulators via Hierarchical Feedback Decomposition / 991
Nicolas F. Rouquette, Jet Propulsion Laboratory, California Institute of Technology
Managing Occurrence Branching in Qualitative Simulation / 998
Lance Tokuda, University of Texas at Austin
Spatial & Functional Reasoning
Diagrammatic Reasoning and Cases / 1004
Michael Anderson, University of Hartford and Robert McCartney, University of Connecticut
Augmenting the Diagnostic Power of Flow-Based Approaches to Functional Reasoning / 1010
Luca Chittaro and Roberto Ranon, Università di Udine
A Qualitative Model of Physical Fields / 1016
Monika Lundell, Swiss Federal Institute of Technology
Generating Multiple New Designs from a Sketch / 1022
Thomas F. Stahovich, Randall Davis and Howard Shrobe, MIT Artificial Intelligence Laboratory
Natural Language
Learning
Tree-Bank Grammars / 1031
Eugene Charniak, Brown University
Left-Corner Unification-Based Natural Language Processing / 1037
Steven L. Lytinen and Noriko Tomuro, DePaul University
Automatically Generating Extraction Patterns from Untagged Text / 1044
Ellen Riloff, University of Utah
Learning to Parse Database Queries Using Inductive Logic Programming / 1050
John M. Zelle, Drake University and Raymond J. Mooney, University of Texas
Semantics & Discourse
HUNTER-GATHERER: Three Search Techniques Integrated for Natural Language Semantics / 1056
Stephen Beale, Sergei Nirenburg, and Kavi Mahesh, New Mexico State University
Semantic Interpretation of Nominalizations / 1062
Richard D. Hull and Fernando Gomez, University of Central Florida
Building Up Rhetorical Structure Trees / 1069
Daniel Marcu, University of Toronto
Using Plan Reasoning in the Generation of Plan Descriptions / 1075
R. Michael Young, University of Pittsburgh
Perception
Perception
Interfacing Sound Stream Segregation to Automatic Speech Recognition -- Preliminary Results on Listening to Several Sounds Simultaneously / 1082
Hiroshi G. Okuno, Tomohiro Nakatani and Takeshi Kawabata, Nippon Telegraph and Telephone Corporation
Motion and Color Analysis for Animat Perception / 1090
Tamer F. Rabie and Demetri Terzopoulos, University of Toronto
Noise and the Common Sense Informatic Situation for a Mobile Robot / 1098
Murray Shanahan, Queen Mary & Westfield College
Vision
A Hybrid Learning Approach for Better Recognition of Visual Objects / 1104
Ibrahim F. Imam, SRA International and Srinivas Gutta, George Mason University
Using Elimination Methods to Compute Thermophysical Algebraic Invariants from Infrared Imagery / 1110
J. D. Michel and N. Nandhakumar, University of Virginia; Tushar Saxena and Deepak Kapur, State University of New York at Albany
Video
Approximate World Models: Incorporating Qualitative and Linguistic Information into Vision Systems / 1116
Claudio S. Pinhanez and Aaron F. Bobick , MIT Media Laboratory
Integrating Visual Information across Camera Movements with a Visual-Motor Calibration Map / 1124
Peter N. Prokopowicz, University of Chicago and Paul R. Cooper, Northwestern University
Planning
The Environment
A Bias towards Relevance: Recognizing Plans where Goal Minimization Fails / 1133
Abigail S. Gertner, University of Pittsburgh and Bonnie L. Webber, University of Pennsylvania
What Is Planning in the Presence of Sensing? / 1139
Hector J. Levesque, University of Toronto
Opportunity Recognition in Complex Environments / 1147
Louise Pryor, University of Edinburgh
Generalizing Indexical-Functional Reference / 1153
Marcel Schoppers and Richard Shu, Robotics Research Harvesting
Handling Uncertainty
Rewarding Behaviors / 1160
Fahiem Bacchus, University of Waterloo; Craig Boutilier, University of British Columbia; Adam Grove, NEC Research Institute
Computing Optimal Policies for Partially Observable Decision Processes Using Compact Representations / 1168
Craig Boutilier and David Poole, University of British Columbia
A Qualitative Model for Temporal Reasoning with Incomplete Information / 1176
Hector Geffner, Universidad Simón Bolívar
On the Size of Reactive Plans / 1182
Peter Jonsson and Christer Bäckström, Linköping University
Search
Is "Early Commitment" in Plan Generation Ever a Good Idea? / 1188
David Joslin, CIRL/University of Oregon and Martha E. Pollack, University of Pittsburgh
Pushing the Envelope: Planning, Propositional Logic, and Stochastic Search / 1194
Henry Kautz and Bart Selman, AT&T Laboratories
Finding Optimal Solutions to the Twenty-Four Puzzle / 1202
Richard E. Korf and Larry A. Taylor, University of California, Los Angeles
Linear Time Near-Optimal Planning in the Blocks World / 1208
John Slaney, Australian National University and Sylvie Thiébaux, IRISA
Temporal Reasoning
Planning for Temporally Extended Goals / 1215
Fahiem Bacchus, University of Waterloo and Froduald Kabanza, Universite de Sherbrooke
A Cost-Directed Planner: Preliminary Report / 1223
Eithan Ephrati, Bar Ilan University; Martha E. Pollack and Marina Milshtein, University of Pittsburgh
Monitoring the Progress of Anytime Problem-Solving / 1229
Eric A. Hansen and Shlomo Zilberstein, University of Massachusetts
A Linear-Programming Approach to Temporal Reasoning / 1235
Peter Jonsson and Christer Bäckström, Linköping University
Rule-Based Reasoning & Connectionism
Production Systems Need Negation as Failure / 1242
Phan Minh Dung, Asian Institute of Technology and Paolo Mancarella, University of Pisa
Using Constraints to Model Disjunctions in Rule-Based Reasoning / 1248
Bing Liu and Joxan Jaffar, National University of Singapore
A Connectionist Framework for Reasoning: Reasoning with Examples / 1256
Dan Roth, Weizmann Institute of Science
Uncertainty
Bayesian Networks
Goal Oriented Symbolic Propagation in Bayesian Networks / 1263
Enrique Castillo and José Manuel Gutiérrez, University of Cantabria; Ali S. Hadi, Cornell University
A Clinician’s Tool for Analyzing Non-Compliance / 1269
David Maxwell Chickering and Judea Pearl, University of California, Los Angeles
Building Classifiers Using Bayesian Networks / 1277
Nir Friedman, Stanford University and Moises Goldszmidt, Rockwell Science Center
Generalized Queries on Probabilistic Context-Free Grammars / 1285
David V. Pynadath and Michael P. Wellman, University of Michigan
Foundations
On the Foundations of Qualitative Decision Theory / 1291
Ronen I. Brafman, University of British Columbia and Moshe Tennenholtz, Technion -- Israel Institute of Technology
Plausibility Measures and Default Reasoning / 1297
Nir Friedman, Stanford University and Joseph Y. Halpern, IBM Almaden Research Center
First-Order Conditional Logic Revisited / 1305
Nir Friedman, Stanford University; Joseph Y. Halpern, IBM Almaden Research Center; and Daphne Koller, Stanford University
A Counterexample to Theorems of Cox and Fine / 1313
Joseph Y. Halpern, IBM Almaden Research Center
AAAI-96 Invited Presentations
Robots with AI: A Retrospective on the AAAI Robot Competitions and Exhibitions / 1321
Pete Bonasso, Metrica, Inc. , Johnson Space Center, NASA and Tom Dean, Brown University
Moving Up the Information Food Chain: Deploying Softbots on the World Wide Web / 1322
Oren Etzioni, University of Washington
Brain Dynamics in the Genesis of Trust as the Basis for Communication by Representations / 1327
Walter J. Freeman, University of California, Berkeley
Using Multi-Agent Systems to Represent Uncertainty / 1329
Joseph Y. Halpern, IBM Almaden Research Center
Refinement Planning: Status and Prospectus / 1331
Subbarao Kambhampati, Arizona State University
Boosting Theory Towards Practice: Recent Developments in Decision Tree Induction and the Weak Learning Framework / 1337
Michael Kearns, AT&T Research
Challenge Problems for Artificial Intelligence / 1340
Bart Selman, AT&T Laboratories; Rodney A. Brooks, Massachusetts Institute of Technology; Thomas Dean, Brown University; Eric Horvitz, Microsoft; Tom M. Mitchell, Carnegie Mellon University; and Nils J. Nilsson, Stanford University
The Database Approach to Knowledge Representation / 1346
Jeffrey D. Ullman, Stanford University
AAAI-96 Robot Competition & Exhibition Abstracts
A Reactive Mobile Robot Based on a Formal Theory of Action / 1350
C. Baral, L. Floriano, A. Gabaldon, D. Morales, T. Son, and R. Watson, University of Texas at El Paso
CoMRoS: Cooperative Mobile Robots Stuttgart / 1351
Thomas Bräunl, Martin Kalbacher, Paul Levi, and Günter Mamier, Universität Stuttgart, Germany
McMaster University’s Artificial Computing System / 1352
Andrew Dawes and Mark Bentley, McMaster University
Doing Tasks with Multiple Mini-Robots / 1353
John Fischer, Paul Rybski, Dirk Edmonds, and Maria Gini, University of Minnesota
Lola, the Mobile Robot from NC State / 1354
Ricardo Gutierrez-Osuna, Daniel S. Schudel, Jason A. Janet, and Ren C. Luo, North Carolina State University
Clementine: Colorado School of Mines / 1355
Robin R. Murphy and the Undergraduate Interdisciplinary Robotics Team, Colorado School of Mines
Mobile Robot Navigation and Control: A Case Study / 1356
Nicholas Roy, Gregory Dudek, and Michael Daum, McGill University, Canada
YODA: The Young Observant Discovery Agent / 1357
Wei-Min Shen, Jafar Adibi, Bonghan Cho, Gal Kaminka, Jihie Kim, Behnam Salemi, and Sheila Tejada, University of Southern California
Amelia / 1358
Reid Simmons, Sebastian Thrun, Greg Armstrong, Richard Goodwin, Karen Haigh, Sven Koenig, Shyjan Mahamud, Daniel Nikovski, and Joseph O'Sullivan, Carnegie Mellon University
SIGART/AAAI Doctoral Consortium Abstracts
Selection of Passages for Information Reduction / 1360
Jody J. Daniels, University of Massachusetts
Towards a Unified Approach to Concept Learning / 1361
Pedro Domingos, University of California, Irvine
A Computational Theory of Turn-Taking / 1362
Toby Donaldson, University of Waterloo, Canada
Learning in Multi-Agent Systems / 1363
Claudia V. Goldman, The Hebrew University, Israel
Bounding the Cost of Learned Rules: A Transformational Approach / 1364
Jihie Kim, University of Southern California
Agent-Centered Search: Situated Search with Small Look-Ahead / 1365
Sven Koenig, Carnegie Mellon University
Recurrent Expert Networks / 1366
Cathie LeBlanc, Florida State University
Semi-Deterministic Reasoning / 1367
Chengjiang Mao, University of Delaware
A Connectionist Model of Instructed Learning / 1368
David C. Noelle, University of California, San Diego
Symptom Management for Schizophrenic Agents / 1369
Phoebe Sengers, Carnegie Mellon University
Adaptive Shared Control for an Intelligent Power Wheelchair / 1370
Richard C. Simpson and Simon P. Levine, University of Michigan Hospital
Induction of Selective Bayesian Networks from Data / 1371
Moninder Singh, University of Pennsylvania
Why Dissect a Frog When You Can Simulate a Lion? / 1372
Brian K. Smith, Northwestern University
Algorithm Evolution for Signal Understanding / 1373
Astro Teller, Carnegie Mellon University
The Use of Knowledge-Based Systems Techniques for Risk Assessment / 1374
Botond Virginas, University of Portsmouth, United Kingdom
AAAI-96 Student Abstracts
Efficient Planning by Graph Rewriting / 1376
José Luis Ambite and Craig A. Knoblock, University of Southern California
Expecting the Unexpected: Detecting and Reacting to Unplanned-for World States / 1377
Ella M. Atkins, Edmund H. Durfee, and Kang G. Shin, University of Michigan
Experiments in Evolutionary Synthesis of Robotic Neurocontrollers / 1378
Karthik Balakrishnan and Vasant Honavar, Iowa State University
A Reinforcement Learning Framework for Combinatorial Optimization / 1379
Justin A. Boyan, Carnegie Mellon University
Learning Topological Maps: An Alternative Approach / 1380
Arno Bücken and Sebastian Thrun, University of Bonn, Germany
Computing Default Logic Extensions: An Implementation / 1381
A. P. Courtney and N. Y. Foo, University of Sydney; G. Antoniou, Griffith University, Australia
Characterizing Temporal Repetition / 1382
Diana Cukierman and James Delgrande, Simon Fraser University, Canada
Achieving Agent Coordination via Distributed Preferences / 1383
Joseph G. D'Ambrosio and William P. Birmingham, The University of Michigan
Fast Discovery of Simple Rules / 1384
Pedro Domingos, University of California, Irvine
Multistrategy Learning: A Case Study / 1385
Pedro Domingos, University of California, Irvine
Simple Bayesian Classifiers Do Not Assume Independence / 1386
Pedro Domingos and Michael Pazzani, University of California, Irvine
CADI — An Intelligent, Multimedia Tutor for Cardiac Auscultation / 1387
Kurt D. Fenstermacher, University of Chicago
Integration of an Expert Teaching Assistant with Distance Learning Software / 1388
Steven P. Fonseca and Nancy E. Reed, University of California, Davis
Self-Adaptation of Mutation Rates and Dynamic Fitness / 1389
Matthew R. Glickman and Katia P. Sycara, Carnegie Mellon University
Heterogeneous and Homogeneous Robot Group Behavior / 1390
Dani Goldberg, Brandeis University
Inducing Design Biases that Characterize Successful Experimentation in Weak-Theory Domains: TIPS / 1391
Vanathi Gopalakrishnan, University of Pittsburgh
Belief Network Algorithms: A Study of Performance / 1392
Nathalie Jitnah, Monash University, Australia
Proposed Interestingness Measure for Characteristic Rules / 1393
Micheline Kamber, Simon Fraser University and Rajjan Shinghal, Concordia University, Canada
A Transformational Analysis of the EBL Utility Problem / 1394
Jihie Kim and Paul S. Rosenbloom, University of Southern California
Controlling State-Space Abstraction in Bayesian Networks / 1395
Chao-Lin Liu, University of Michigan
Ad Hoc Attribute-Value Prediction / 1396
Gabor Melli, Simon Fraser University, Canada
An Incremental Interactive Algorithm for Regular Grammar Inference / 1397
Rajesh Parekh and Vasant Honavar, Iowa State University
Constructive Neural Network Learning Algorithms / 1398
Rajesh Parekh, Jihoon Yang, and Vasant Honavar, Iowa State University
A Computational Model of Persistent Beliefs / 1399
Sunju Park, The University of Michigan
Contracting Strategy Based on Markov Process Modeling / 1400
Sunju Park and Edmund H. Durfee, The University of Michigan
Learning Procedural Planning Knowledge in Complex Environments / 1401
Douglas J. Pearson, The University of Michigan
MarketBayes: A Distributed, Market-Based Bayesian Network / 1402
David M. Pennock, The University of Michigan
The Kritzel System for Handwriting Interpretation / 1403
Gaofeng Qian, The University of Texas at Dallas
SplitNet: A Dynamic Hierarchical Network Model / 1404
Jürgen Rahmel, University of Kaiserslautern, Germany
Symbolic Performance & Learning in Continuous Environments / 1405
Seth O. Rogers, University of Michigan
Effects of Local Information on Group Behavior / 1406
Shounak Roychowdhury, Neeraj Arora, and Sandip Sen, University of Tulsa
Automated Formulation of Constraint Satisfaction Problems / 1407
Mihaela Sabin and Eugene C. Freuder, University of New Hampshire
Dynamic Constraint-Based Planning in Trauma Management / 1408
Moninder Singh, University of Pennsylvania
Blocking as a Middle-Ground for Step-Order Commitments in Planning / 1409
Biplav Srivastava and Subbarao Kambhampati, Arizona State University
Experimentation-Driven Operator Learning / 1410
Kang Soo Tae, University of Texas at Arlington
Hybrid Knowledge- and Databases / 1411
Merwyn Taylor, University of Maryland
Learning Models for Multi-Source Integration / 1412
Sheila Tejada, Craig A. Knoblock, and Steven Minton, University of Southern California
Rabbi: Exploring the Inner World through Stories / 1413
Marina Umaschi, MIT Media Laboratory
Constructive Induction of Features for Planning / 1414
Michael van Lent, University of Michigan
Agents Modeling Agents in Information Economies / 1415
José M. Vidal and Edmund H. Durfee, University of Michigan
Optimal Factory Scheduling Using Stochastic Dominance A* / 1416
Peter R. Wurman, University of Michigan
Dynamic Map: Representation of Interactions between Robots / 1417
Christian Zanardi, GRPR, École Polytechnique de Montréal, Canada
Neural Network Guided Search Control in Partial Order Planning / 1418
Terry Zimmerman and Subbarao Kambhampati, Arizona State University
Invited Talks
The BOEING 777 - Concurrent Engineering and Digital Pre-Assembly / 1589
Bob Abarbanel, Boeing Information & Support Services
Data Mining and Knowledge Discovery in Databases: Applications in Astronomy and Planetary Science / 1590
Usama M. Fayyad, Microsoft Research