Proceedings of the Nineteenth National Conference on Artificial Intelligence
Sponsored by the Association for the Advancement of Artificial Intelligence
George Ferguson and Deborah McGuinness, Program Cochairs
July 25–29, 2004, San Jose, California. Published by The AAAI Press, Menlo Park, California. This proceedings is also available in book and CD format.
Contents
AAAI Organization / xvii
Conference Program Committees / xviii
Outstanding Paper Award / xxi
Sponsoring Organizations / xxii
Preface / xxiii
Invited Talks / xxv
Agents and Multi-Agent Systems
Performance Bounded Reinforcement Learning in Strategic Interactions / 2
Bikramjit Banerjee and Jing Peng
Searching for Stable Mechanisms: Automated Design for Imperfect Players / 8
Andrew J. Blumberg and Abhi Shelat
Affective Recruitment of Distributed Heterogeneous Agents / 14
Aaron Gage and Robin R. Murphy
Visibility-Based Pursuit-Evasion with Limited Field of View / 20
Brian P. Gerkey, Sebastian Thrun, and Geoff Gordon
Task Allocation via Self-Organizing Swarm Coalitions in Distributed Mobile Sensor Network / 28
Kian Hsiang Low, Wee Kheng Leow, and Marcelo H. Ang, Jr.
GROWRANGE: Anytime VCG-Based Mechanisms / 34
David C. Parkes and Grant Schoenebeck
Useful Roles of Emotions in Artificial Agents: A Case Study from Artificial Life / 42
Matthias Scheutz
Automated Reasoning
Low-Knowledge Algorithm Control / 49
Tom Carchrae and J. Christopher Beck
Implementing a Generalized Version of Resolution / 55
Heidi E. Dixon, Matthew L. Ginsberg, David K. Hofer, Eugene M. Luks, and Andrew J. Parkes
SAT-Based Answer Set Programming / 61
Enrico Giunchiglia, Yuliya Lierler, and Marco Maratea
A Polynomial-Time Algorithm for Simple Temporal Problems with Piecewise Constant Domain Preference Functions / 67
T. K. Satish Kumar
Using Performance Profile Trees to Improve Deliberation Control / 73
Kate Larson and Tuomas Sandholm
On Odd and Even Cycles in Normal Logic Programs / 80
Fangzhen Lin and Xishun Zhao
Logic Programs with Abstract Constraint Atoms / 86
Victor W. Marek and Miroslaw Truszczynski
Adding Time and Intervals to Procedural and Hierarchical Control Specifications / 92
Tran Cao Son, Chitta Baral, and Le-Chi Tuan
Model Checking Temporal Logics of Knowledge in Distributed Systems / 98
Kaile Su
Identifying Linear Causal Effects / 104
Jin Tian
Complexity
The Complexity of Global Constraints / 112
Christian Bessiere, Emmanuel Hebrard, Brahim Hnich, and Toby Walsh
Complexity of Contextual Reasoning / 118
Floris Roelofsen and Luciano Serafini
The Backdoor Key: A Path to Understanding Problem Hardness / 124
Yongshao Ruan, Henry Kautz, and Eric Horvitz
Constraint Satisfaction and Satisfiability
Hiding Satisfying Assignments: Two Are Better than One / 131
Dimitris Achlioptas, Haixia Jia, and Cristopher Moore
Modeling Choices in Quasigroup Completion: SAT Versus CSP / 137
Carlos Ansótegui, Alvaro del Val, Iván Dotuacute;, Cèsar Fernández, and Felip Manyà
Leap Before You Look: An Effective Strategy in an Oversubscribed Scheduling Problem / 143
Laura Barbulescu, L. Darrell Whitley, and Adele E. Howe
Domain Transmutation in Constraint Satisfaction Problems / 149
James Bowen and Chavalit Likitvivatanavong
Collapsibility and Consistency in Quantified Constraint Satisfaction / 155
Hubie Chen
Complete Local Search for Propositional Satisfiability / 161
Hai Fang and Wheeler Ruml
QUICKXPLAIN: Preferred Explanations and Relaxations for Over-Constrained Problems / 167
Ulrich Junker
MAX-2-SAT: How Good Is Tabu Search in the Worst-Case? / 173
Monaldo Mastrolilli and Luca Maria Gambardella
The Practice of Approximated Consistency for Knapsack Constraints / 179
Meinolf Sellmann
Study of Lower Bound Functions for MAX-2-SAT / 185
Haiou Shen and Hantao Zhang
Additive versus Multiplicative Clause Weighting for SAT / 191
John Thornton, Duc Nghia Pham, Stuart Bain, and Valnir Ferreira Jr.
Tractable Tree Convex Constraint Networks / 197
Yuanlin Zhang and Eugene C. Freuder
Game Theory and Economic Models
Eliciting Bid Taker Non-price Preferences in (Combinatorial) Auctions / 204
Craig Boutilier, Tuomas Sandholm, and Rob Shields
Combinatorial Auctions with Structured Item Graphs / 212
Vincent Conitzer, Jonathan Derryberry, and Tuomas Sandholm
Computing Shapley Values, Manipulating Value Division Schemes, and Checking Core Membership in
Multi-Issue Domains / 219
Vincent Conitzer and Tuomas Sandholm
Learning Social Preferences in Games / 226
Ya’akov Gal, Avi Pfeffer, Francesca Marzo, and Barbara J. Grosz
Methods for Boosting Revenue in Combinatorial Auctions / 232
Anton Likhodedov and Tuomas Sandholm
Using Contracts to Influence the Outcome of a Game / 238
Robert McGrew and Yoav Shoham
Knowledge Representation and Reasoning
Scaling Up Reasoning about Actions Using Relational Database Technology / 245
Giuseppe De Giacomo and Toni Mancini
Conservative Belief Revision / 251
James P. Delgrande, Abhaya C. Nayak, and Maurice Pagnucco
Mereological Semantics for Bio-Ontologies / 257
Udo Hahn, Stefan Schulz, and Kornél Markó
CASEE: A Hierarchical Event Representation for the Analysis of Videos / 263
Asaad Hakeem, Yaser Sheikh, and Mubarak Shah
Making Argumentation More Believable / 269
Anthony Hunter
Towards Higher Impact Argumentation / 275
Anthony Hunter
Loop Formulas for Circumscription / 281
Joohyung Lee and Fangzhen Lin
An Instance-Based State Representation for Network Repair / 287
Michael L. Littman, Nishkam Ravi, Eitan Fenson, and Rich Howard
Logical Foundations of Negotiation: Outcome, Concession, and Adaptation / 293
Thomas Meyer, Norman Foo, Rex Kwok, and Dongmo Zhang
Repeated Observation Models / 299
Avi Pfeffer
Encoding Probabilistic Causal Model in Probabilistic Action Language / 305
Nam Tran and Chitta Baral
Evaluating Ontology Cleaning / 311
Christopher Welty, Ruchi Mahindru, and Jennifer Chu-Carroll
Negotiation as Mutual Belief Revision / 317
Dongmo Zhang, Norman Foo, Thomas Meyer, and Rex Kwok
Learning
Hierarchical Hidden Markov Models with General State Hierarchy / 324
Hung H. Bui, Dinh Q. Phung, and Svetha Venkatesh
An Ensemble Technique for Stable Learners with Performance Bounds / 330
Ian Davidson
On the Optimality of Probability Estimation by Random Decision Trees / 336
Wei Fan
Fibring Neural Networks / 342
Artur S. d’Avila Garcez and Dov M. Gabbay
Learning and Inferring Transportation Routines / 348
Lin Liao, Dieter Fox, and Henry Kautz
Learning and Applying Competitive Strategies / 354
Esther Lock and Susan L. Epstein
Bayesian Network Classifiers Versus k-NN Classifier Using Sequential Feature Selection / 360
Franz Pernkopf
Online Parallel Boosting / 366
Jesse A. Reichler, Harlan D. Harris, and Michael A. Savchenko
Bayesian Inference on Principal Component Analysis Using Reversible Jump Markov Chain Monte Carlo / 372
Zhihua Zhang, Kap Luk Chan, James T. Kwok, and Dit-Yan Yeung
Error Detection and Impact-Sensitive Instance Ranking in Noisy Datasets / 378
Xingquan Zhu, Xindong Wu, and Ying Yang
Natural Language Processing and Information Extraction Comparing Cognitive and Computational Models of Narrative Structure / 385
David B. Christian and R. Michael Young
Methods for Domain-Independent Information Extraction from the Web: An Experimental Comparison / 391
Oren Etzioni, Michael Cafarella, Doug Downey, Ana-Maria Popescu, Tal Shaked, Stephen Soderland, Daniel S. Weld, and Alexander Yates
Interpreting Loosely Encoded Questions / 399
James Fan and Bruce Porter
Learning Indexing Patterns from One Language for the Benefit of Others / 406
Udo Hahn, Kornél Markó, and Stefan Schulz
Interactive Information Extraction with Constrained Conditional Random Fields / 412
Trausti Kristjansson, Aron Culotta, Paul Viola, and Andrew McCallum
Identification and Tracing of Ambiguous Names: Discriminative and Generative Approaches / 419
Xin Li, Paul Morie, and Dan Roth
Text Classification by Labeling Words / 425
Bing Liu, Xiaoli Li, Wee Sun Lee, and Philip S. Yu
On the Relationship between Lexical Semantics and Syntax for the Inference of Context-Free Grammars / 431
Tim Oates, Tom Armstrong, Justin Harris, and Mark Nejman
Distributed Representation of Syntactic Structure by Tensor Product Representation and Non-Linear Compression / 437
Heidi H. T. Yeung and Peter W. M. Tsang
Perception
Rapid Object Recognition from Discriminative Regions of Interest / 444
Gerald Fritz, Christin Seifert, Lucas Paletta, and Horst Bischof
Automatically Transforming Symbolic Shape Descriptions for Use in Sketch Recognition / 450
Tracy Hammond and Randall Davis
Large-Scale Map-Making / 457
Kurt Konolige
A Multi-Resolution Pyramid for Outdoor Robot Terrain Perception / 464
Michael Montemerlo and Sebastian Thrun
Self-Organizing Visual Maps / 470
Robert Sim and Gregory Dudek
Reconstruction of 3D Models from Intensity Images and Partial Depth / 476
Luz A. Torres-Méndez and Gregory Dudek
Perceptually Based Learning of Shape Descriptions for Sketch Recognition / 482
Olya Veselova and Randall Davis
On the Integration of Grounding Language and Learning Objects / 488
Chen Yu and Dana H. Ballard
Planning and Scheduling
Generating Safe Assumption-Based Plans for Partially Observable, Nondeterministic Domains / 495
Alexandre Albore and Piergiorgio Bertoli
Regrets Only! Online Stochastic Optimization under Time Constraints / 501
Russell Bent and Pascal Van Hentenryck
Assessing the Complexity of Plan Recognition / 507
Christopher W. Geib
Forward-Chaining Planning in Nondeterministic Domains / 513
Ugur Kuter and Dana Nau
Transport Logistics Planning with Service-Level Constraints / 519
Hoong Chuin Lau, Kien Ming Ng, and Xiaotao Wu
Distance Estimates for Planning in the Discrete Belief Space / 525
Jussi Rintanen
Continuous Time in a SAT-Based Planner / 531
Ji-Ae Shin and Ernest Davis
Analogical Path Planning / 537
Saul Simhon and Gregory Dudek
An Effective Algorithm for Project Scheduling with Arbitrary Temporal Constraints / 544
Tristan B. Smith and John M. Pyle
Shortest Path Discovery Problems: A Framework, Algorithms and Experimental Results / 550
Csaba Szepesvári
Regression with Respect to Sensing Actions and Partial States / 556
Le-Chi Tuan, Chitta Baral, Xin Zhang, and Tran Cao Son
Effective Approaches for Partial Satisfaction (Over-Subscription) Planning / 562
Menkes van den Briel, Romeo Sanchez, Minh B. Do, and Subbarao Kambhampati
Branching and Pruning: An Optimal Temporal POCL Planner Based on Constraint Programming / 570
Vincent Vidal and Héctor Geffner
High-Level Goal Recognition in a Wireless LAN / 578
Jie Yin, Xiaoyong Chai, and Qiang Yang
Qualitative Modeling
Spatial Aggregation for Qualitative Assessment of Scientific Computations / 585
Chris Bailey-Kellogg and Naren Ramakrishnan
A Qualitative-Quantitative Methods-Based e-Learning Support System in Economic Education / 592
Tokuro Matsuo, Takayuki Ito, and Toramatsu Shintani
Robotics
Skill Acquisition and Use for a Dynamically-Balancing Soccer Robot / 599
Brett Browning, Ling Xu, and Manuela Veloso
Common Sense Data Acquisition for Indoor Mobile Robots / 605
Rakesh Gupta and Mykel J. Kochenderfer
Machine Learning for Fast Quadrupedal Locomotion / 611
Nate Kohl and Peter Stone
Interleaving Temporal Planning and Execution in Robotics Domains / 617
Solange Lemai and Félix Ingrand
Reinforcement Learning for CPG-Driven Biped Robot / 623
Takeshi Mori, Yutaka Nakamura, Masa-aki Sato, and Shin Ishii
Advice Generation from Observed Execution: Abstract Markov Decision Process Learning / 631
Patrick Riley and Manuela Veloso
Search
Compressing Pattern Databases / 638
Ariel Felner, Ram Meshulam, Robert C. Holte, and Richard E. Korf
A General Solution to the Graph History Interaction Problem / 644
Akihiro Kishimoto and Martin Müller
Best-First Frontier Search with Delayed Duplicate Detection / 650
Richard E. Korf
Temperature Discovery Search / 658
Martin Müller, Markus Enzenberger, and Jonathan Schaeffer
Simple Search Methods for Finding a Nash Equilibrium / 664
Ryan Porter, Eugene Nudelman, and Yoav Shoham
Towards Efficient Sampling: Exploiting Random Walk Strategies / 670
Wei Wei, Jordan Erenrich, and Bart Selman
Space-Efficient Memory-Based Heuristics / 677
Rong Zhou and Eric A. Hansen
Structured Duplicate Detection in External-Memory Graph Search / 683
Rong Zhou and Eric A. Hansen
Uncertainty
Stochastic Local Search for POMDP Controllers / 690
Darius Braziunas and Craig Boutilier
A Computational Study of the Kemeny Rule for Preference Aggregation / 697
Andrew Davenport and Jayant Kalagnanam
PROBCONS: Probabilistic Consistency-Based Multiple Alignment of Amino Acid Sequences / 703
Chuong B. Do, Michael Brudno, and Serafim Batzoglou
Dynamic Programming for Partially Observable Stochastic Games / 709
Eric A. Hansen, Daniel S. Bernstein, and Shlomo Zilberstein
Solving Concurrent Markov Decision Processes / 716
Mausam and Daniel S. Weld
Low-cost Addition of Preferences to DTPs and TCSPs / 723
Bart Peintner and Martha E. Pollack
mCP Nets: Representing and Reasoning with Preferences of Multiple Agents / 729
F. Rossi, K. B. Venable, and T. Walsh
Extending CP-Nets with Stronger Conditional Preference Statements / 735
Nic Wilson
Solving Generalized Semi-Markov Decision Processes Using Continuous Phase-Type Distributions / 742
Håkan L. S. Younes and Reid G. Simmons
User Modeling
Exploring More Realistic Evaluation Measures for Collaborative Filtering / 749
Giuseppe Carenini and Rita Sharma
Mining Opinion Features in Customer Reviews / 755
Minqing Hu and Bing Liu
Just How Mad Are You? Finding Strong and Weak Opinion Clauses / 761
Theresa Wilson, Janyce Wiebe, and Rebecca Hwa
Student Abstracts
A Correspondence Metric for Imitation / 944
R. Amit and Maja Mataric
Fuzzy Induction in Dynamic User Profiling for Information Filtering / 946
Rafal A. Angryk and Costin Barbu
Semantically Guiding a First-Order Theorem Prover with a Soft Model / 948
Arnold Binas and John Slaney
Metrics for Finite Markov Decision Processes / 950
Norm Ferns, Prakash Panangaden, and Doina Precup
Robust Solutions for Constraint Satisfaction and Optimization / 952
Emmanuel Hebrard
Generation of Emotional Behavior for Non-Player Characters — Development of EmoBot for Quake II / 954
Tye Hooley, Burt Hunking, Mike Henry, and Atsushi Inoue
Knowledge State Reconsideration: Hindsight Belief Revision / 956
Frances L. Johnson and Stuart C. Shapiro
Utilizing Internal State in Multi-Robot Coordination Tasks / 958
Chris Jones and Maja J. Mataric
Generating “Random” 3-SAT Instances with Specific Solution Space Structure / 960
Pushkin R. Pari, Jane Lin, Lin Yuan, and Gang Qu
Occam’s Razor and a Non-Syntactic Measure of Decision Tree Complexity / 962
Goutam Paul
Discriminating Among Word Meanings by Identifying Similar Contexts / 964
Amruta Purandare and Ted Pedersen
A Bayes Net Approach to Argumentation / 966
Sabyasachi Saha and Sandip Sen
Identifying an Object that is Perceptually Indistinguishable from One Previously Perceived / 968
John F. Santore and Stuart C. Shapiro
Evaluating Consistency Algorithms for Temporal Metric Constraints / 970
Yang Shi, Anagh Lal, and Berthe Y. Choueiry
Mixed-Initiative Workflow Composition / 972
Marc Spraragen
Mobile Agent-Based Search for Service Discovery on Dynamic Peer-to-Peer Networks / 974
Evan A. Sultanik
Finding Redundant Constraints for FSM Minimization / 976
Lin Yuan, Pushkin R. Pari, and Gang Qu
SIGART/AAAI Doctoral Consortium
Semi-Supervised Clustering with Limited Background Knowledge / 979
Sugato Basu
Learnable Similarity Functions and their Applications to Clustering and Record Linkage / 981
Mikhail Bilenko
Flexible Decision-Making in Sequential Auctions / 983
Gangshu Cai
A Framework for Optimal Sequential Planning in Multiagent Settings / 985
Prashant J. Doshi
User-Sensitive Text Summarization / 987
Noemie Elhadad
Connecting Cognitive and Physical Worlds with Dynamic Cost Function Definition / 989
Jamie Lennon
Interesting Instance Discovery in Multi-Relational Data / 991
Shou-de Lin
Adaptive Algorithms for Routing and Traffic Engineering in Stochastic Networks / 993
Sudip Misra and B. John Oommen
Inducing Constraint-Based Grammars using a Domain Ontology / 995
Smaranda Muresan
Capturing User Intent for Information Retrieval / 997
Hien Nguyen
A Metric for the Evaluation of Imitation / 999
Amit Ramesh
Planning and Verification for Stochastic Processes with Asynchronous Events / 1001
Håkan L. S. Younes
Intelligent Systems Demonstrations
Intelligent Systems Demonstration: The Secure Wireless Agent Testbed (SWAT) / 1004
Gustave Anderson, Andrew Burnheimer, Vincent Cicirello, David Dorsey, Saturnino Garcia, Moshe Kam, Joseph Kopena, Kris Malfettone, Andy Mroczkowski, Gaurav Naik, Max Peysakhov, William Regli, Joshua Shaffer, Evan Sultanik, Kenneth Tsang, Leonardo Urbano, Kyle Usbeck, and Jacob Warren
Multi-Agent System Development: Design, Runtime, and Analysis / 1006
K. S. Barber, J. Ahn, K. Fullam, T. Graser, N. Gujral, D. C. Han, D. N. Lam, R. McKay, J. Park, and M. Vanzin
Visual Odometry Using Commodity Optical Flow / 1008
Jason Campbell, Rahul Sukthankar, and Illah Nourbakhsh
Engineering Open Multi-Agent Systems as Electronic Institutions / 1010
M. Esteva, D. de la Cruz, B. Rosell, J. Ll. Arcos, J. A. Rodríguez-Aguilar, and G. Cuní
iBundler: An Agent-Based Decision Support Service for Combinatorial Negotiations / 1012
A. Giovannucci, J. A. Rodríguez-Aguilar, Jésus Cerquides, A. Reyes, and F. X. Noria
Domain-Independent Reason-Enhanced Controller for Task-ORiented Systems — DIRECTOR / 1014
Darsana P. Josyula, Michael L. Anderson, and Don Perlis
Agent-Based Modeling with Social Networks for Terrorist Recruitment / 1016
Teresa H. Ko and Nina M. Berry
Mobile Emergency Triage Support System / 1018
Wojtek Michalowski, Roman Slowinski, and Szymon Wilk
CMRadar: A Personal Assistant Agent for Calendar Management / 1020
Pragnesh Jay Modi, Manuela Veloso, Stephen F. Smith, and Jean Oh
Centibots: Very Large Scale Distributed Robotic Teams / 1022
Charlie Ortiz, Kurt Konolige, Regis Vincent, Benoit Morisset, Andrew Agno, Michael Eriksen, Dieter Fox, Benson Limketkai, Jonathan Ko, Benjamin Steward, and Dirk Schulz
WordNet::Similarity — Measuring the Relatedness of Concepts / 1024
Ted Pedersen, Siddharth Patwardhan, and Jason Michelizzi
PRECISE on ATIS: Semantic Tractability and Experimental Results / 1026
Ana-Maria Popescu, Alex Armanasu, Oren Etzioni, David Ko, and Alexander Yates
SEM-Ether: Semantic Web Based Pervasive Computing Framework — Integrating Web, Devices and People / 1028
Sushil Puradkar, Sachin Singh, Chintan Patel, Kartik Vishwanath, Rahul Gupta, and Yugyung Lee
SenseClusters — Finding Clusters that Represent Word Senses / 1030
Amruta Purandare and Ted Pedersen
CAMEO: Modeling Human Activity in Formal Meeting Situations / 1032
Paul E. Rybski, Fernando de la Torre, Raju Patil, Carlos Vallespi, Manuela Veloso, and Brett Browning
A Robotic Model of Human Reference Resolution / 1034
Matthias Scheutz, Virgil Andronache, and Kathleen Eberhard
SCoT: A Spoken Conversational Tutor / 1036
Karl Schultz, Brady Clark, Heather Pon-Barry, Elizabeth Owen Bratt, and Stanley Peters
Intelligent Agents for Coalition Search and Rescue Task Support / 1038
Austin Tate, Jeff Dalton, Clauirton de Siebra, Stuart Aitken, Jeffrey M. Bradshaw, and Andrzej Uszok
The Autonomous Sciencecraft Experiment Onboard the EO-1 Spacecraft / 1040
Daniel Tran, Steve Chien, Rob Sherwood, Rebecca Castano, Benjamin Cichy, Ashley Davies, and Gregg Rabideau
Online Semantic Extraction by Backpropagation Neural Network with Various
Syntactic Structure Representations / 1042
Heidi H. T. Yeung
Responsive Information Architect: A Context-Sensitive Multimedia Conversation Framework for Information Seeking / 1044
Michelle Zhou, Keith Houck, Rosario Uceda-Sosa, Shimei Pan, Min Chen, Vikram Aggarwal, and James Shaw
Index / 1046