Proceedings of the Twentieth National Conference on Artificial Intelligence

July 9-13, 2005,
Pittsburgh, Pennsylvania
Published by The AAAI Press, Menlo Park, California

This proceedings is also available in book and CD format

Sample Citation

Ben-Eliyahu, Rachel. 2005. On Computing Minimal Models. In Proceedings of the Twentieh National Conference on Artificial Intelligence,2-8. Menlo Park, Calif.: AAAI Press.

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!

AAAI Organization / xvii

Conference Program Committees / xviii

Outstanding Paper Award / xxi

Sponsoring Organizations / xxii

Preface / xxiii

Invited Talks / xxv

Activity and Plan Recognition

Multiple-Goal Recognition from Low-Level Signals / 3
Xiaoyong Chai and Qiang Yang

A Variational Learning Algorithm for the Abstract Hidden Markov Model / 9
Jeffrey Johns and Sridhar Mahadevan

Large-Scale Localization from Wireless Signal Strength / 15
Julie Letchner, Dieter Fox, and Anthony LaMarca

Unsupervised Activity Recognition Using Automatically Mined Common Sense / 21
Danny Wyatt, Matthai Philipose, and Tanzeem Choudhury

Activity Recognition through Goal-Based Segmentation / 28
Jie Yin, Dou Shen, Qiang Yang, and Ze-Nian Li

Agents / Multiagent Systems

Team Member Reallocation via Tree Pruning / 35
Noa Agmon, Gal A. Kaminka, and Sarit Kraus

Efficient No-Regret Multiagent Learning / 41
Bikramjit Banerjee and Jing Peng

Solving DisCSPs with Penalty Driven Search / 47
Muhammed Basharu, Ines Arana, and Hatem Ahriz

Coordination and Adaptation in Impromptu Teams / 53
Michael Bowling and Peter McCracken

Robust and Self-Repairing Formation Control for Swarms of Mobile Agents / 59
Jimming Cheng, Winston Cheng, and Radhika Nagpal

An Extended Protocol for Multiple-Issue Concurrent Negotiation / 65
Jiangbo Dang and Michael N. Huhns

The Semantics of Potential Intentions / 71
Xiaocong Fan and John Yen

Agent-Organized Networks for Multi-Agent Production and Exchange / 77
Matthew E. Gaston and Marie desJardins

Supporting Collaborative Activity / 83
Meirav Hadad, Gilad Armon-Kest, Gal A. Kaminka, and Sarit Kraus

Multiple Agent Event Detection and Representation in Videos / 89
Asaad Hakeem and Mubarak Shah

Anyone but Him: The Complexity of Precluding an Alternative / 95
Edith Hemaspaandra, Lane A. Hemaspaandra, and Jörg Rothe

Towards Model-Based Diagnosis of Coordination Failures / 102
Meir Kalech and Gal A. Kaminka

Flexible Teamwork in Behavior-Based Robots / 108
Gal A. Kaminka and Inna Frenkel

Coordinating Agile Systems through the Model-based Execution of Temporal Plans / 114
Thomas Léauté and Brian C. Williams

Controversial Users Demand Local Trust Metrics: An Experimental Study on Epinions.com Community / 121
Paolo Massa and Paolo Avesani

Modeling Human Behavior for Virtual Training Systems / 127
Yohei Murakami, Yuki Sugimoto, and Toru Ishida

Networked Distributed POMDPs: A Synthesis of Distributed Constraint Optimization and POMDPs / 133
Ranjit Nair, Pradeep Varakantham, Milind Tambe, and Makoto Yokoo

New Approaches to Optimization and Utility Elicitation in Autonomic Computing / 140
Relu Patrascu, Craig Boutilier, Rajarshi Das, Jeffrey O. Kephart, Gerald Tesauro, and William E. Walsh

An Ecological Approach to Agent Population Management / 146
Maxim D. Peysakhov, Robert N. Lass, William C. Regli, and Moshe Kam

Distributing Coalitional Value Calculations among Cooperative Agents / 152
Talal Rahwan and Nicholas R. Jennings

Cooperative Exploration in the Electronic Marketplace / 158
David Sarne and Sarit Kraus

Solving the Auction-Based Task Allocation Problem in an Open Environment / 164
David Sarne and Sarit Kraus

Profit Sharing Auction / 170
Sandip Sen, Teddy Candale, and Susnata Basak

OAR: A Formal Framework for Multi-Agent Negotiation / 176
Jiaying Shen, Ingo Weber, and Victor Lesser

Tool Use for Autonomous Agents / 184
Robert St. Amant and Alexander B. Wood

Observation-based Model for BDI-Agents / 190
Kaile Su, Abdul Sattar, Kewen Wang, Xiangyu Luo, Guido Governatori, and Vineet Padmanabhan

Stable Service Placement on Dynamic Peer-to-Peer Networks: A Heuristic for the Distributed k-Center Problem / 196
Evan A. Sultanik and William C. Regli

Analogical and Case-Based Reasoning

Analogical Learning of Visual/Conceptual Relationships in Sketches / 202
Kenneth D. Forbus, Jeffrey Usher, and Emmett Tomai

Solving Everyday Physical Reasoning Problems by Analogy Using Sketches / 209
Matthew Klenk, Kenneth D. Forbus, Emmett Tomai, Hyeonkyeong Kim, and Brian Kyckelhahn

Complexity-Guided Case Discovery for Case Based Reasoning / 216
Stewart Massie, Susan Craw, and Nirmalie Wiratunga

Interactive Knowledge Validation and Query Refinement in CBR / 222
Monica H. Ou, Geoff A. W. West, Mihai Lazarescu, and Chris Clay

Competence Driven Case-Base Mining / 228
Rong Pan, Qiang Yang, Jeffrey Junfeng Pan, and Lei Li

A Domain-Independent System for Case-Based Task Decomposition without Domain Theories / 234
Ke Xu and Hector Muñoz-Avila

Auctions and Market-Based Systems

Mechanism Design for Single-Value Domains / 241
Moshe Babaioff, Ron Lavi, and Elan Pavlov

Combinatorial Auctions with k-wise Dependent Valuations / 248
Vincent Conitzer, Tuomas Sandholm, and Paolo Santi

Expressive Negotiation in Settings with Externalities / 255
Vincent Conitzer and Tuomas Sandholm

A New Strategy-Proof Greedy-Allocation Combinatorial Auction Protocol and Its Extension to Open Ascending Auction Protocol / 261
Takayuki Ito, Makoto Yokoo, Atsushi Iwasaki, and Shigeo Matsubara

Approximating Revenue-Maximizing Combinatorial Auctions / 267
Anton Likhodedov and Tuomas Sandholm

Automated Reasoning

The Achilles’ Heel of QBF / 275
Carlos Ansotegui, Carla P. Gomes, and Bart Selman

Combining Stochastic and Greedy Search in Hybrid Estimation / 282
Lars Blackmore, Stanislav Funiak, and Brian Williams

Propositional Fragments for Knowledge Compilation and Quantified Boolean Formulae / 288
Sylvie Coste-Marquis, Daniel Le Berre, Florian Letombe, and Pierre Marquis

Axiom Schemata as Metalevel Axioms: Model Theory / 294
Timothy L. Hinrichs and Michael R. Genesereth

On Compiling System Models for Faster and More Scalable Diagnosis / 300
Jinbo Huang and Adnan Darwiche

A Discourse Planning Approach to Cinematic Camera Control for Narratives in Virtual Environments / 307
Arnav Jhala and R. Michael Young

Dependency-Directed Reconsideration Belief Base Optimization for Truth Maintenance Systems / 313
Frances L. Johnson and Stuart C. Shapiro

Diagnosis as Approximate Belief State Enumeration for Probabilistic Concurrent Constraint Automata / 321
Oliver B. Martin, Brian C. Williams, and Michel D. Ingham

Model-Based Monitoring and Diagnosis of Systems with Software-Extended Behavior / 327
Tsoline Mikaelian, Brian C. Williams, and Martin Sachenbacher

Recommender Systems: Attack Types and Strategies / 334
Michael P. O'Mahony, Neil J. Hurley, and Guénolé C. M. Silvestre

Compact Propositional Encodings of First-Order Theories / 340
Deepak Ramachandran and Eyal Amir

Identifying Direct Causal Effects in Linear Models / 346
Jin Tian

Constraint Satisfaction and Satisfiability

Old Resolution Meets Modern SLS / 354
A. Anbulagan, Duc Nghia Pham, John Slaney, and Abdul Sattar

CSP Properties for Quantified Constraints: Definitions and Complexity / 360
Lucas Bordeaux, Marco Cadoli, and Toni Mancini

Constrained Decision Diagrams / 366
Kenil C. K. Cheng and Roland H. C. Yap

Finding Diverse and Similar Solutions in Constraint Programming / 372
Emmanuel Hebrard, Brahim Hnich, Barry O'Sullivan, and Toby Walsh

Weighted Super Solutions for Constraint Programs / 378
Alan Holland and Barry O'Sullivan

Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively / 384
Haixia Jia, Cristopher Moore, and Doug Strain

Generalized NoGoods in CSPs / 390
George Katsirelos and Fahiem Bacchus

Neighborhood Interchangeability and Dynamic Bundling for Non-Binary Finite CSPs / 397
Anagh Lal, Berthe Y. Choueiry, and Eugene C. Freuder

A Fast Arc Consistency Algorithm for n-ary Constraints / 405
Olivier Lhomme and Jean-Charles Régin

Quick Shaving / 411
Olivier Lhomme

DC-SSAT: A Divide-and-Conquer Approach to Solving Stochastic Satisfiability Problems Efficiently / 416
Stephen M. Majercik and Byron Boots

A Constraint Satisfaction Approach to Geospatial Reasoning / 423
Martin Michalowski and Craig A. Knoblock

A Framework for Representing and Solving NP Search Problems / 430
David G. Mitchell and Eugenia Ternovska

Generation of Hard Non-Clausal Random Satisfiability Problems / 436
Juan A. Navarro and Andrei Voronkov

Anytime, Complete Algorithm for Finding Utilitarian Optimal Solutions to STPPs / 443
Bart Peintner and Martha E. Pollack

Superstabilizing, Fault-Containing Multiagent Combinatorial Optimization / 449
Adrian Petcu, Boi Faltings

SAT-Based versus CSP-Based Constraint Weighting for Satisfiability / 455
Duc Nghia Pham, John Thornton, Abdul Sattar, and Abdelraouf Ishtaiwi

Constraint-Based Preferential Optimization / 461
Steve Prestwich, Francesca Rossi, Kristen Brent Venable, and Toby Walsh

SymChaff: A Structure-Aware Satisfiability Solver / 467
Ashish Sabharwal

Performing Bayesian Inference by Weighted Model Counting / 475
Tian Sang, Paul Beame, and Henry Kautz

Game Theory and Economic Models

A Generalized Strategy Eliminability Criterion and Computational Methods for Applying It / 483
Vincent Conitzer and Tuomas Sandholm

Fast and Compact: On A Simple Class of Congestion Games / 489
Samuel Ieong, Robert McGrew, Eugene Nudelman, Yoav Shoham, and Qixiang Sun

Mixed-Integer Programming Methods for Finding Nash Equilibria / 495
Tuomas Sandholm, Andrew Gilpin, and Vincent Conitzer

Approximate Strategic Reasoning through Hierarchical Reduction of Large Symmetric Games / 502
Michael P. Wellman, Daniel M. Reeves, Kevin M. Lochner, Shih-Fen Cheng, and Rahul Suri

Coalitional Games in Open Anonymous Environments / 509
Makoto Yokoo, Vincent Conitzer, Tuomas Sandholm, Naoki Ohta, and Atsushi Iwasaki

Human-Computer Interaction

Mathematical Domain Reasoning Tasks in Natural Language Tutorial Dialog on Proofs / 516
Christoph Benzmüller and Quoc Bao Vo

Real-Time Classification of Electromyographic Signals for Robotic Control / 523
Beau Crawford, Kai Miller, Pradeep Shenoy, and Rajesh Rao

A Decision Theoretic Model for Stress Recognition and User Assistance / 529
Wenhui Liao, Weihong Zhang, Zhiwei Zhu, and Qiang Ji

On the Evaluation of Dynamic Critiquing: A Large-Scale User Study / 535
Kevin McCarthy, Lorraine McGinty, Barry Smyth, and James Reilly

Optimal Recommendation Sets: Covering Uncertainty over User Preferences / 541
Robert Price and Paul R. Messinger

Goal-Directed Site-Independent Recommendations from Passive Observations / 549
Tingshao Zhu, Russ Greiner, Gerald Häubl, Kevin Jewell, and Robert Price

Knowledge Acquisition and Engineering

An Analysis of Procedure Learning by Instruction / 558
Jim Blythe

An Analysis of Knowledge Collected from Volunteer Contributors / 564
Timothy Chklovski and Yolanda Gil

Knowledge Representation and Reasoning

Integrating Description Logics and Action Formalisms: First Results / 572
Franz Baader, Carsten Lutz, Maja Milicic, Ulrike Sattler, and Frank Wolter

Using SAT and Logic Programming to Design Polynomial-Time Algorithms for Planning in Non-Deterministic Domains / 578
Chitta Baral, Thomas Eiter, and Jicheng Zhao

Hybrid Possibilistic Networks / 584
Salem Benferhat and Salma Smaoui

Practical First-Order Argumentation / 590
Philippe Besnard and Anthony Hunter

Prioritized Component Systems / 596
Gerhard Brewka, Ilkka Niemelä, and Mirek Truszczynski

DL-Lite: Tractable Description Logics for Ontologies / 602
Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, and Riccardo Rosati

An Axiomatic Account of Formal Argumentation / 608
Martin Caminada and Leila Amgoud

Merging Argumentation Systems / 614
Sylvie Coste-Marquis, Caroline Devred, Sébastien Konieczny, Marie-Christine Lagasquie-Schiex, and Pierre Marquis

DD-PREF: A Language for Expressing Preferences over Sets / 620
Marie desJardins and Kiri L. Wagstaff

Cumulative Effects of Concurrent Actions on Numeric-Valued Fluents / 627
Esra Erdem and Alfredo Gabaldon

Only-Knowing: Taking It Beyond Autoepistemic Reasoning / 633
Gerhard Lakemeyer and Hector J. Levesque

Tractable Reasoning in First-Order Knowledge Bases with Disjunctive Information / 639
Yongmei Liu and Héctor J. Levesque

Knowledge Integration for Description Logics / 645
Thomas Meyer, Kevin Lee, and Richard Booth

Analysis of Strategic Knowledge in Back of the Envelope Reasoning / 651
Praveen K. Paritosh and Kenneth D. Forbus

Generalized Link Properties for Expressive ε-Connections of Description Logics / 657
Bijan Parsia and Bernardo Cuenca Grau

Functional Specification of Probabilistic Process Models / 663
Avi Pfeffer

Diagnosing Terminologies / 670
Stefan Schlobach

Issues in Reasoning about Interaction Networks in Cells: Necessity of Event Ordering Knowledge / 676
Nam Tran, Chitta Baral, and Carran Shankland

A Theory of Forgetting in Logic Programming / 682
Kewen Wang, Abdul Sattar, and Kaile Su

Logic Programming

Reasoning about Intended Actions / 689
Chitta Baral and Michael Gelfond

Strong and Uniform Equivalence in Answer-Set Programming: Characterizations and Complexity Results for the Non-Ground Case / 695
Thomas Eiter, Michael Fink, Hans Tompits, and Stefan Woltran

Properties of Programs with Monotone and Convex Constraints / 701
Lengning Liu and Miroslaw Truszczynski

A Unified Framework for Representing Logic Program Updates / 707
Yan Zhang and Norman Foo

Machine Learning

Robust Supervised Learning / 714
J. Andrew Bagnell

Weighted One-Against-All / 720
Alina Beygelzimer, John Langford, and Bianca Zadrozny

Optimal Efficient Learning Equilibrium: Imperfect Monitoring in Symmetric Games / 726
Ronen I. Brafman and Moshe Tennenholtz

Discovering Domain-Specific Composite Kernels / 732
Thomas Briggs and Tim Oates

A Comparison of Novel and State-of-the-Art Polynomial Bayesian Network Learning Algorithms / 739
Laura E. Brown, Ioannis Tsamardinos, and Constantin F. Aliferis

Reducing Labeling Effort for Structured Prediction Tasks / 746
Aron Culotta and Andrew McCallum

Towards Learning Stochastic Logic Programs from Proof-Banks / 752
Luc De Raedt, Kristian Kersting, and Sunna Torge

Incremental Estimation of Discrete Hidden Markov Models Based on a New Backward Procedure / 758
German Florez-Larrahondo, Susan Bridges, and Eric A. Hansen

A Hybrid Generative/Discriminative Approach to Semi-Supervised Classifier Design / 764
Akinori Fujino, Naonori Ueda, and Kazumi Saito

Discriminative Model Selection for Belief Net Structures / 770
Yuhong Guo and Russ Greiner

Transforming between Propositions and Features: Bridging the Gap / 777
Daniel T. Halstead and Kenneth D. Forbus

Effective Short-Term Opponent Exploitation in Simplified Poker / 783
Bret Hoehn, Finnegan Southey, Robert C. Holte, and Valeriy Bulitko

Non-Stationary Policy Learning in 2-Player Zero Sum Games / 789
Steven Jensen, Daniel Boley, Maria Gini, and Paul Schrater

nFOIL: Integrating Naïve Bayes and FOIL / 795
Niels Landwehr, Kristian Kersting, and Luc De Raedt

Using Modified Lasso Regression to Learn Large Undirected Graphs in a Probabilistic Framework / 801
Fan Li and Yiming Yang

The Regularized EM Algorithm / 807
Haifeng Li, Keshu Zhang, and Tao Jiang

Semi-Supervised Sequence Modeling with Syntactic Topic Models / 813
Wei Li and Andrew McCallum

Giving Advice about Preferred Actions to Reinforcement Learners Via Knowledge-Based Kernel Regression / 819
Richard Maclin, Jude Shavlik, Lisa Torrey, Trevor Walker, and Edward Wild

Distribution-Free Learning of Bayesian Network Structure in Continuous Domains / 825
Dimitris Margaritis

Online Query Relaxation via Bayesian Causal Structures Discovery / 831
Ion Muslea and Thomas J. Lee

Redescription Mining: Structure Theory and Algorithms / 837
Laxmi Parida and Naren Ramakrishnan

Spectral Clustering of Biological Sequence Data / 845
William Pentney and Marina Meila

Enhanced Direct Linear Discriminant Analysis for Feature Extraction on High Dimensional Data / 851
A. K. Qin, S. Y. M. Shi, P. N. Suganthan, and Marco Loog

A Maximum Likelihood Framework for Integrating Taxonomies / 856
Suju Rajan, Kunal Punera, and Joydeep Ghosh

Constraint-Based Entity Matching / 862
Warren Shen, Xin Li, and AnHai Doan

Discriminative Training of Markov Logic Networks / 868
Parag Singla and Pedro Domingos

Representing Conditional Independence Using Decision Trees / 874
Jiang Su and Harry Zhang

Value Functions for RL-Based Behavior Transfer: A Comparative Study / 880
Matthew E. Taylor, Peter Stone, and Yaxin Liu

Online Resource Allocation Using Decompositional Reinforcement Learning / 886
Gerald Tesauro

Inducing Hierarchical Process Models in Dynamic Domains / 892
Ljupco Todorovski, Will Bridewell, Oren Shiran, and Pat Langley

Software Testing by Active Learning for Commercial Games / 898
Gang Xiao, Finnegan Southey, Robert C. Holte, and Dana Wilkinson

Unsupervised and Semi-Supervised Multi-Class Support Vector Machines / 904
Linli Xu and Dale Schuurmans

Learning Planning Rules in Noisy Stochastic Worlds / 911
Luke S. Zettlemoyer, Hanna M. Pasula, and Leslie Pack Kaelbling

Hidden Naive Bayes / 919
Harry Zhang, Liangxiao Jiang, and Jiang Su

Finite Sample Error Bound for Parzen Windows / 925
Peng Zhang, Jing Peng, and Norbert Riedel

Machine Perception

Cross-Modal Clustering / 932
Michael H. Coen

A Computational Model of the Cerebral Cortex / 938
Thomas Dean

Data-Driven MCMC for Learning and Inference in Switching Linear Dynamic Systems / 944
Sang Min Oh, James M. Rehg, Tucker Balch, and Frank Dellaert

Function-Based Classification from 3D Data via Generic and Symbolic Models / 950
Michael Pechuk, Octavian Soldea, and Ehud Rivlin

Learning Static Object Segmentation from Motion Segmentation / 956
Michael G. Ross and Leslie Pack Kaelbling

Semantic Scene Concept Learning by an Autonomous Agent / 962
Weiyu Zhu

Markov Decision Processes and Uncertainty

A Particle Filtering Based Approach to Approximating Interactive POMDPs / 969
Prashant Doshi and Piotr J. Gmytrasiewicz

Efficient Maximization in Solving POMDPs / 975
Zhengzhu Feng and Shlomo Zilberstein

Extending Continuous Time Bayesian Networks / 981
Karthik Gopalratnam, Henry Kautz, and Daniel S. Weld

Planning in Models that Combine Memory with Predictive Representations of State / 987
Michael R. James and Satinder Singh

Risk-Sensitive Planning with One-Switch Utility Functions: Value Iteration / 993
Yaxin Liu and Sven Koenig

Samuel Meets Amarel: Automating Value Function Approximation Using Global State Space Analysis / 1000
Sridhar Mahadevan

Error Bounds for Approximate Value Iteration / 1006
Rémi Munos

Geometric Variance Reduction in Markov Chains. Application to Value Function and Gradient Estimation / 1012
Rémi Munos

Modeling Form for On-line Following of Musical Performances / 1018
Bryan Pardo and William Birmingham

Improving Action Selection in MDP’s via Knowledge Transfer / 1024
Alexander A. Sherstov and Peter Stone

Planning and Execution with Phase Transitions / 1030
Håkan L. S. Younes

Natural Language Processing and Speech Recognition

Scaling Up Word Sense Disambiguation via Parallel Texts / 1037
Yee Seng Chan and Hwee Tou Ng

An Inference Model for Semantic Entailment in Natural Language / 1043
Rodrigo de Salvo Braz, Roxana Girju, Vasin Punyakanok, Dan Roth, and Mark Sammons

A Probabilistic Classification Approach for Lexical Textual Entailment / 1050
Oren Glickman, Ido Dagan, and Moshe Koppel

Clustering and Classifying Person Names by Origin / 1056
Fei Huang, Stephan Vogel, and Alex Waibel

Learning to Transform Natural to Formal Languages / 1062
Rohit J. Kate, Yuk Wah Wong, and Raymond J. Mooney

Impact of Linguistic Analysis on the Semantic Graph Coverage and Learning of Document Extracts / 1069
Jure Leskovec, Natasa Milic-Frayling, Marko Grobelnik

Unsupervised Multilingual Word Sense Disambiguation via an Interlingua / 1075
Kornél Markó, Stefan Schulz, and Udo Hahn

Supervised Ranking for Pronoun Resolution: Some Recent Improvements / 1081
Vincent Ng

Cross-Lingual Bootstrapping of Semantic Lexicons: The Case of FrameNet / 1087
Sebastian Padó and Mirella Lapata

Word Sense Disambiguation with Semi-Supervised Learning / 1093
Thanh Phong Pham, Hwee Tou Ng, and Wee Sun Lee

Robust Textual Inference Via Learning and Abductive Reasoning / 1099
Rajat Raina, Andrew Y. Ng, and Christopher D. Manning

Exploiting Subjectivity Classification to Improve Information Extraction / 1106
Ellen Riloff, Janyce Wiebe, and William Phillips

Dependency Parsing with Dynamic Bayesian Network / 1112
Virginia Savova and Leonid Peshkin

Spotting Subsequences Matching an HMM Using the Average Observation Probability Criteria with Application to Keyword Spotting / 1118
Marius Calin Silaghi

Capturing Expression Using Linguistic Information / 1124
Özlem Uzuner and Boris Katz

Planning and Scheduling

State Agnostic Planning Graphs and the Application to Belief-Space Planning / 1131
William Cushing and Daniel Bryce

Genome Rearrangement and Planning / 1139
Esra Erdem and Elisabeth Tillier

Quasi-Monotonic Segmentation of State Variable Behavior for Reactive Control / 1145
Will Fitzgerald, Daniel Lemire, and Martin Brooks

Validating Plans in the Context of Processes and Exogenous Events / 1151
Maria Fox, Richard Howey, and Derek Long

Fast Planning in Domains with Derived Predicates: An Approach Based on Rule-Action Graphs and Local Search / 1157
Alfonso Gerevini, Alessandro Saetti, Ivan Serina, and Paolo Toninelli

New Admissible Heuristics for Domain-Independent Planning / 1163
Patrik Haslum, Blai Bonet, and Héctor Geffner

Using Domain-Configurable Search Control for Probabilistic Planning / 1169
Ugur Kuter and Dana Nau

Lazy Approximation for Solving Continuous Finite-Horizon MDPs / 1175
Lihong Li and Michael L. Littman

Prottle: A Probabilistic Temporal Planner / 1181
Iain Little, Douglas Aberdeen, and Sylvie Thiébaux

Augmenting Disjunctive Temporal Problems with Finite-Domain Constraints / 1187
Michael D. Moffitt, Bart Peintner, and Martha E. Pollack

Temporal Dynamic Controllability Revisited / 1193
Paul Morris and Nicola Muscettola

Exploiting Temporal Flexibility to Obtain High Quality Schedules / 1199
Nicola Policella, Xiaofang Wang, Stephen F. Smith, and Angelo Oddi

Planning for Stream Processing Systems / 1205
Anton Riabov and Zhen Liu

Conformant Planning for Domains with Constraints—A New Approach / 1211
Tran Cao Son, Phan Huy Tu, Michael Gelfond, and A. Ricardo Morales

Learning Measures of Progress for Planning Domains / 1217
SungWook Yoon, Alan Fern,and Robert Givan

Exploiting the Structure of Hierarchical Plans in Temporal Constraint Propagation / 1223
Neil Yorke-Smith

Sensor Selection for Active Information Fusion / 1229
Yongmian Zhang and Qiang Ji

Simultaneous Heuristic Search for Conjunctive Subgoals / 1235
Lin Zhu and Robert Givan

Robotics

Reactive Planning in a Motivated Behavioral Architecture / 1242
Éric Beaudry, Yannick Brosseau, Carle Côté, Clément Raïevsky, Dominic Létourneau, Froduald Kabanza, and François Michaud

A Distributed Approach to Passive Localization for Sensor Networks / 1248
Rahul Biswas and Sebastian Thrun

Recovery Planning for Ambiguous Cases in Perceptual Anchoring / 1254
Mathias Broxvall, Silvia Cordeschi, Lars Karlsson, and Alessandro Saffiotti

A Multifrontal QR Factorization Approach to Distributed Inference Applied to Multirobot Localization and Mapping / 1261
Frank Dellaert, Alexander Kipp, and Peter Krauthausen

Learning CPG Sensory Feedback with Policy Gradient for Biped Locomotion for a Full-Body Humanoid / 1267
Gen Endo, Jun Morimoto, Takamitsu Matsubara, Jun Nakanishi, and Gordon Cheng

Tactic-Based Motion Modeling and Multi-Sensor Tracking / 1274
Yang Gu

A Relational Representation for Procedural Task Knowledge / 1280
Stephen Hart, Roderic Grupen, and David Jensen

Controlling Tiny Multi-Scale Robots for Nerve Repair / 1286
Tad Hogg and David W. Sretavan

Heterogeneous Multirobot Coordination with Spatial and Temporal Constraints / 1292
Mary Koes, Illah Nourbakhsh, and Katia Sycara

Consciousness: Drinking from the Firehose of Experience / 1298
Benjamin Kuipers

Semantic Place Classification of Indoor Environments with Mobile Robots Using Boosting / 1306
Axel Rottmann, Óscar Martínez Mozos, Cyrill Stachniss, and Wolfram Burgard

Learning to Prevent Failure States for a Dynamically Balancing Robot / 1312
Jeremy Searock and Brett Browning

Autonomous Color Learning on a Mobile Robot / 1318
Mohan Sridharan and Peter Stone

Mobile Robot Mapping and Localization in Non-Static Environments / 1324
Cyrill Stachniss and Wolfram Burgard

Improving Simultaneous Mapping and Localization in 3D Using Global Constraints / 1330
Rudolph Triebel and Wolfram Burgard

Bitbots: Simple Robots Solving Complex Tasks / 1336
Anna Yershova, Benjamín Tovar, Robert Ghrist, and Steven M. LaValle

Search

An Algorithm Better than AO*? / 1343
Blai Bonet and Héctor Geffner

Speeding Up Learning in Real-time Search via Automatic State Abstraction / 1349
Vadim Bulitko, Nathan Sturtevant, and Maryia Kazakevich

The Max K-Armed Bandit: A New Model of Exploration Applied to Search Heuristic Selection / 1355
Vincent A. Cicirello and Stephen F. Smith

Cost-Algebraic Heuristic Search / 1362
Stefan Edelkamp, Shahid Jabbar, and Alberto Lluch Lafuente

Backbones and Backdoors in Satisfiability / 1368
Philip Kilby, John Slaney, Sylvie Thiébaux, and Toby Walsh

Search versus Knowledge for Solving Life and Death Problems in Go / 1374
Akihiro Kishimoto and Martin Müller

Large-Scale Parallel Breadth-First Search / 1380
Richard E. Korf and Peter Schultze

Domain-Dependent Parameter Selection of Search-based Algorithms Compatible with User Performance Criteria / 1386
Biplav Srivastava and Anupam Mediratta

Partial Pathfinding Using Map Abstraction and Refinement / 1392
Nathan Sturtevant and Michael Buro

External-Memory Pattern Databases Using Structured Duplicate Detection / 1398
Rong Zhou and Eric A. Hansen

Semantic Web, Information Retrieval, and Extraction

Selection and Ranking of Propositional Formulas for Large-Scale Service Directories / 1406
Ion Constantinescu, Walter Binder, and Boi Faltings

WebCrow: A Web-Based System for Crossword Solving / 1412
Marco Ernandes, Giovanni Angelini, and Marco Gori

A Learning-Based Term-Weighting Approach for Information Retrieval / 1418
GuangCan Liu, Yong Yu, and Xing Zhu

Query Translation Disambiguation as Graph Partitioning / 1424
Yi Liu and Rong Jin

Searching for Common Sense: Populating Cyc™ from the Web / 1430
Cynthia Matuszek, Michael Witbrock, Robert C. Kahlert, John Cabral, David Schneider, Purvesh Shah, and Doug Lenat

Automatic Text Summarization of Newswire: Lessons Learned from the Document Understanding Conference / 1436
Ani Nenkova

A Graph Theoretical Foundation for Integrating RDF Ontologies / 1442
Octavian Udrea, Yu Deng, Edna Ruckhaus, V.S. Subrahmanian

Student Abstracts

Machine Learning and Its Application at Nooksack Falls Hydroelectric Station / 1584
Scott Alexander and Jianna Zhang

Helicopter Routing for Maintaining Remote Sites in Alaska using a Genetic Algorithm / 1586
Nicholas Armstrong-Crews and Kenrick Mock

Autonomous Subgoal Discovery and Hierarchical Abstraction for Reinforcement Learning Using Monte Carlo Method / 1588
Mehran Asadi and Manfred Huber

Mixed-Initiative Approach to Collaboration in the Mathematical Domain / 1590
Nadya Belov and Joshua Shaffer

On Predicting User Intent / 1592
Nadya Belov

DR-Prolog:A System for Reasoning with Rules and Ontologies on the Semantic Web / 1594
Antonis Bikakis and Grigoris Antoniou

Genre Classification of Web Documents / 1596
Elizabeth Sugar Boese and Adele Howe

Rule Refinement by Domain Experts in Complex Knowledge Bases / 1598
Cristina Boicu, Gheorghe Tecuci, and Mihai Boicu

Use of Expert Knowledge for Decision Tree Pruning / 1600
Jingfeng Cai and John Durkin

Learning Support Vector Machines from Distributed Data Sources / 1602
Cornelia Caragea, Doina Caragea, and Vasant Honavar

Boosting Semantic Web Data Access Using Swoogle / 1604
Li Ding and Tim Finin

Towards Exploiting Duality in Approximate Linear Programming for MDPs / 1606
Dmitri Dolgov and Edmund Durfee

Manufacturing Processes Recognition of Machined Mechanical Parts using SVMs / 1608
Cheuk Yiu Ip and William C. Regli

An Automated Distributed Meeting Scheduler for FCVW Plug-in / 1610
Hsiang-Hwa Koo and Elhadi Shakshuki

Description Logic-Ground Knowledge Integration and Management / 1612
Joseph Kopena

Continuous Speech Recognition Using Modified Stack Decoding Algorithm / 1614
David Lee

Qualitative Dimensions in Question Answering: Extending the Definitional QA Task / 1616
Lucian Vlad Lita, Andrew Hazen Schlaikjer, WeiChang Hong, and Eric Nyberg

A Learning Support Method in Qualitative Simulation-Based Economic Education / 1618
Tokuro Matsuo, Takayuki Ito, and Toramatsu Shintani

Evolving AI Opponents in a First-Person-Shooter Video Game / 1620
C. Adam Overholtzer and Simon D. Levy

A Framework for Bayesian Network Mapping / 1622
Rong Pan and Yun Peng

Minimizing Environmental Swings with a Recurrent Neural Network Control System / 1624
Sam Skrivan, Jianna Zhang, and Debra Jusak

Autonomous Learning of Tool Affordances by a Robot / 1626
Alexander Stoytchev

Doctoral Consortium

Leveraging Language into Learning / 1636
Jacob Beal

Dissertation in Progress: An Empirical Analysis of the Costs and Benefits of Naturalness in Spoken Dialog Systems / 1638
Ellen Campana

Learning Source Descriptions for Web Services / 1640
Mark James Carman

Computational Aspects of Mechanism Design / 1642
Vincent Conitzer

On Boosting Semantic Web Data Access / 1644
Li Ding

Dynamic Regime Identification and Prediction Based on Observed Behavior in Electronic Marketplaces / 1646
Wolfgang Ketter

Adaptive Modeling and Planning for Reactive Agents / 1648
Mykel J. Kochenderfer

Self-Emergence of Structures in Gene Expression Programming / 1650
Xin Li

Concurrent Hierarchical Reinforcement Learning / 1652
Bhaskara Marthi

Discourse Factors in Multi-Document Summarization / 1654
Ani Nenkova

Structure Learning for Statistical Relational Models / 1656
Jennifer Neville

Towards Competence in Autonomous Agents / 1658
Özgür Simsek

Rover Science Autonomy: Probabilistic Planning for Science-Aware Exploration / 1660
Trey Smith

Natural Language Generation for Text-to-Text Applications Using an Information-Slim Representation / 1662
Radu Soricut

Planning for Geospatial Data Integration / 1664
Snehal Thakkar

Improving Reinforcement Learning Function Approximators via Neuroevolution / 1666
Shimon Whiteson

Index / 1046

Intelligent Systems Demonstrations

QuOnto: Querying Ontologies
Andrea Acciarri, Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini, Mattia Palmieri, and Riccardo Rosati

Building Applications Using End to End Composition of Web Services
Vikas Agarwal, Girish Chafle, Koustuv Dasgupta, Neeran Karnik, Arun Kumar, Ashish Kundu, Anupam Mediratta, Sumit Mittal, and Biplav Srivastava

The AI Technologies of the Philadelphia Area Urban Wireless Network Testbed
Gustave Anderson, Andrew Burnheimer, Vincent Cicirello, David Dorsey, Chris Dugan, Iris Howley, Moshe Kam, Joseph Kopena, Rob Lass, Kris Malfettone, Andy Mroczkowski, Gaurav Naik, Max Peysakhov, Brian Pyles, William Regli, Evan Sultanik, James Thiel, Kyle Usbeck, Dan Venutolo, and Marc Winners

Proving Theorems of Type Theory Automatically with TPS
Peter B. Andrews

A Learning and Reasoning System for Intelligence Analysis
Mihai Boicu, Gheorghe Tecuci, Cindy Ayers, Dorin Marcu, Cristina Boicu, Marcel Barbulescu, Bogdan Stanescu, William Wagner, Vu Le, Denitsa Apostolova, and Adrian Ciubotariu

MADbot: A Motivated and Goal Directed Robot
A. Coddington, M. Fox, J. Gough, D. Long, and I. Serina

Swoogle: Searching for Knowledge on the Semantic Web
Tim Finin, Li Ding, Rong Pan, Anupam Joshi, Pranam Kolari, Akshay Java, and Yun Peng

Optimal Rhode Island Hold'em Poker
Andrew Gilpin and Tuomas Sandholm

Evolution of an Empathetic Digital Entity: Phase One
Margaret Manella Kozak

Language Independent Extractive Summarization
Rada Mihalcea

TIELT: A Testbed for Gaming Environments
Matthew Molineaux and David W. Aha

SenseRelate::TargetWord-A Generalized Framework for Word Sense Disambiguation
Siddharth Patwardhan, Satanjeev Banerjee, and Ted Pedersen

Identifying Similar Words and Contexts in Natural Language with SenseClusters
Ted Pedersen and Anagha Kulkarni

Song Search and Retrieval by Tapping
Geoffrey Peters, Caroline Anthony, and Michael Schwartz

The Proteome Analyst Suite of Automated Function Prediction Tools
Brett Poulin, Duane Szafron, Paul Lu, Russell Greiner, David Wishart, Roman Eisner, Alona Fyshe, Brandon Pearcy, Luca Pireddu

DiamondHelp: A Collaborative Task Guidance Framework for Complex Devices
Charles Rich, Candy Sidner, Neal Lesh, Andrew Garland, Shane Booth, and Markus Chimani

Remote Supervisory Control of a Humanoid Robot
Michael T. Rosenstein , Andrew H. Fagg, Robert Platt Jr., John D. Sweeney, and Roderic A. Grupen

MGLAIR Agents in Virtual and Other Graphical Environments
Stuart C. Shapiro, Josephine Anstey, David E. Pape, Trupti Devdas Nayak, Michael Kandefer, and Orkan Telhany

Solo: A Cognitive Orthosis
Richard Simpson, Edmund LoPresti, Debra Schreckenghost, Ned Kirsch, and Steve Hayashi

SAGA-ML: An Active Learning System for Semiautomated Gameplay Analysis
Finnegan Southey and Robert C. Holte

Using the GEMS System for Cancer Diagnosis and Biomarker Discovery from Microarray Gene Expression Data
Alexander Statnikov, Ioannis Tsamardinos, and Constantin F. Aliferis

The TaskTracker System
Simone Stumpf, Xinlong Bao, Anton Dragunov, Thomas G. Dietterich, Jon Herlocker, Kevin Johnsrude, Lida Li, and JianQiang Shen

Mobile Robot Competition and Exhibition

Low-cost Outdoor Robot Platform for the Penn State Abington Mini Grand Challenge
Robert Avanzato

Pyro: An Integrated Environment for Robotics Education
Douglas Blank, Deepak Kumar, Lisa Meeden, and Holly Yanco

Ready or Not, Here I Come ...
Magdalena Bugajska, William Adams, Scott Thomas, J. Gregory Trafton, and Alan C. Schultz

Robots in an Intelligent Systems Course
Debra Burhans, Andre Nelson, and Victoria Steck

Scavenging with a Laptop Robot
Alan Davidson, Mac Mason, Susanna Ricco, Ben Tribelhorn, and Zachary Dodds

Social Tag: Finding the Person with the Pink Hat
Carl DiSalvo, Didac Font, Laura Hiatt, Nik Melchior, Marek Michalowski, and Reid Simmons

Upending the Uncanny Valley
David Hanson, Andrew Olney, Steve Prilliman, Eric Mathews, Marge Zielke, Derek Hammons, Raul Fernandez, and Harry Stephanou

Catoms: Moving Robots Without Moving Parts
Brian Kirby, Jason Campbell, Burak Aksak, Padmanabhan Pillai, James Hoburg, Todd Mowry, and Seth Copen Goldstein

NavBot: The Navigational Search-and-Rescue Robot
Matthew Marge, Ayman Sawas, Juan Carlos Liberato, Murtaza M. Karim, Manish Muttreja, Nader Alrawahi, and Brian Fink

A Brochette of Socially Interactive Robots
F. Michaud, D. Létourneau, P. Lepage, Y. Morin, F. Gagnon, P. Giguère, É. Beaudry, Y. Brosseau, C. Côté, A. Duquette, J.-F. Laplante, M.-A. Legault, P. Moisan, A. Ponchon, C. Raüevsky, M.-A. Roux, T. Salter, J.-M. Valin, S. Caron, P. Masson, F. Kabanza, and M. Lauria

Indoor Aerial Robot Competition: Challenges in Search and Rescue Applications
Paul Y. Oh, William E. Green, and Keith W. Sevcik

Toward Affective Cognitive Robots for Human-Robot Interaction
M. Scheutz, J. Kramer, C. Middendorff, P. Schermerhorn, M. Heilman, D. Anderson, and P. Bui

Using a Sketch Pad Interface for Interacting with a Robot Team
Marjorie Skubic, Derek Anderson, Samuel Blisard, Dennis Perzanowski, William Adams, J. Gregory Trafton, and Alan C. Schultz

Tekkotsu: A Framework for AIBO Cognitive Robotics
David S. Touretzky and Ethan J. Tira-Thompson

Improving Human-Robot Interaction for Remote Robot Operation
Holly A. Yanco, Michael Baker, Robert Casey, Andrew Chanler, Munjal Desai, Dan Hestand, Brenden Keyes, and Philip Thoren

Invited Talks

(Links are to slides.)

Tucker Balch, Georgia Institute of Technology

Amy Greenwald, Brown University

Marti Hearst, University of California, Berkeley

Sridhar Mahadevan, University of Massachusetts

Dana Nau, University of Maryland

Sister Conference Highlights

(Links are to slides.)

ACL-2003: The Forty-first Annual Meeting of the Association for Computational Linguistics

AIIDE 2005: The First Artificial Intelligence and Interactive Digital Entertainment Conference

CogSci 2004: The Twenty-Sixth Annual Meeting of the Cognitive Science Society

CP 2004: The Tenth International Conference on Principles and Practice of Constraint Programming

ICAPS-2005: The International Conference on Automated Planning and Scheduling

ICCBR 2003: The Fifth International Conference on Case-Based Reasoning

ICML-2004: The Twenty-First International Conference on Machine Learning

ISWC-2004: The Third International Semantic Web Conference

KCAP-2003: The Second International Conference on Knowledge Capture

KDD-2004: The Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

KR-2004: The Ninth International Conference on the Principles of Knowledge Representation and Reasoning

UAI-2004: The Twentieth Conference on Uncertainty in Artificial Intelligence