Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence
Sponsored by the Association for the Advancement of Artificial Intelligence
Dieter Fox and Carla P. Gomes, Program Cochairs.
July 13–17, 2008, Chicago, Illinois. 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
AAAI Organization / xxvi
Conference Committees / xxix
Awards / lii
Sponsors / liii
AAAI Preface / liv
Dieter Fox and Carla Gomes
IAAI Preface / lvi
Mehmet Goker and Karen Haigh
Invited Talks / lvii
Eric Horvitz, Kenneth M. Ford, Alexei A. Efros, David Haussler, Lillian Lee, Mark Newman, Stuart Russell, Seth Copen Goldstein, Chris Urmson
Main Track Technical Papers
Agents, Game Theory, Auctions, and Mechanism Design
Memetic Networks: Analyzing the Effects of Network Properties in Multi-Agent Performance / 3
Ricardo M. Araujo, Luis C. Lamb
Physical Search Problems Applying Economic Search Models / 9
Yonatan Aumann, Noam Hazon, Sarit Kraus, David Sarne
A Theory of Expressiveness in Mechanisms / 17
Michael Benisch, Norman Sadeh, Tuomas Sandholm
Multiagent Graph Coloring: Pareto Efficiency, Fairness and Individual Rationality / 24
Yaad Blum, Jeffrey S. Rosenschein
Expressive Banner Ad Auctions and Model-Based Online Optimization for Clearing / 30
Craig Boutilier, David C. Parkes, Tuomas Sandholm, William E. Walsh
A Computational Analysis of the Tournament Equilibrium Set / 38
Felix Brandt, Felix Fischer, Paul Harrenstein, Maximilian Mair
Approximability of Manipulating Elections / 44
Eric Brelsford, Piotr Faliszewski, Edith Hemaspaandra, Henning Schnoor, Ilka Schnoor
Efficient Metadeliberation Auctions / 50
Ruggiero Cavallo, David C. Parkes
Achieving Cooperation in a Minimally Constrained Environment / 57
Steven Damer, Maria Gini
Generalized Point Based Value Iteration for Interactive POMDPs / 63
Prashant Doshi, Dennis Perez
On the Dimensionality of Voting Games / 69
Edith Elkind, Leslie Ann Goldberg, Paul Goldberg, Michael Wooldridge
First-Order Algorithm with O(ln(1/ε)) Convergence for ε-Equilibrium in Two-Person Zero-Sum Games / 75
Andrew Gilpin, Javier Peña, Tuomas Sandholm
Agent Organized Networks Redux / 83
Robin Glinton, Katia Sycara, Paul Scerri
Reasoning about the Appropriateness of Proponents for Arguments / 89
Anthony Hunter
Bayesian Coalitional Games / 95
Samuel Ieong, Yoav Shoham
Agent Coordination with Regret Clearing / 101
Sven Koenig, Xiaoming Zheng, Craig Tovey, Richard Borie, Philip Kilby, Vangelis Markakis, Pinar Keskinocak
An Expressive Auction Design for Online Display Advertising / 108
Sébastien Lahaie, David C. Parkes, David M. Pennock
Computer-Aided Proofs of Arrow’s and Other Impossibility Theorems / 114
Fangzhen Lin, Pingzhong Tang
Resource Constrained Distributed Constraint Optimization with Virtual Variables / 120
Toshihiro Matsui, Hiroshi Matsuo, Marius Silaghi, Katsutoshi Hirayama, Makoto Yokoo
Strategyproof Classification under Constant Hypotheses: A Tale of Two Functions / 126
Reshef Meir, Ariel D. Procaccia, Jeffrey S. Rosenschein
Argument Theory Change Applied to Defeasible Logic Programming / 132
Martín O. Moguillansky, Nicolás D. Rotstein, Marcelo A. Falappa, Alejandro J. García, Guillermo R. Simari
The Impact of Vertical Specialization on Hierarchical Multi-Agent Systems / 138
Steven Okamoto, Paul Scerri, Katia Sycara
Coordination and Multi-Tasking Using EMT / 144
Zinovi Rabinovich, Nir Pochter, Jeffrey S. Rosenschein
Pareto Optimality in Abstract Argumentation / 150
Iyad Rahwan, Kate Larson
Coalition Structure Generation: Dynamic Programming Meets Anytime Optimization / 156
Talal Rahwan, Nicholas R. Jennings
Partially Synchronized DEC-MDPs in Dynamic Mechanism Design / 162
Sven Seuken, Ruggiero Cavallo, David C. Parkes
Mathematical Modeling and Convergence Analysis of Trail Formation / 170
Sameena Shah, Ravi Kothari, Jayadeva, Suresh Chandra
Semantical Considerations on Dialectical and Practical Commitments / 176
Munindar P. Singh
Bidding Strategies for Realistic Multi-Unit Sealed-Bid Auctions / 182
Ioannis A. Vetsikas, Nicholas R. Jennings
Optimal False-Name-Proof Voting Rules with Costly Voting / 190
Liad Wagman, Vincent Conitzer
Determining Possible and Necessary Winners under Common Voting Rules Given Partial Orders / 196
Lirong Xia, Vincent Conitzer
Voting on Multiattribute Domains with Cyclic Preferential Dependencies / 202
Lirong Xia, Vincent Conitzer, Jérôme Lang
Value-Based Policy Teaching with Active Indirect Elicitation / 208
Haoqi Zhang, David Parkes
Manipulating the Quota in Weighted Voting Games / 215
Michael Zuckerman, Piotr Faliszewski, Yoram Bachrach, Edith Elkind
Constraints, Satisfiability, and Search
Measuring the Hardness of SAT Instances / 222
Carlos Ansótegui, María Luisa Bonet, Jordi Levy, Felip Manyà
A New Incomplete Method for CSP Inconsistency Checking / 229
Belaïd Benhamou, Mohamed Réda Saïdi
The Parameterized Complexity of Global Constraints / 235
C. Bessiere, E. Hebrard, B. Hnich, Z. Kiziltan, C-G. Quimper, T. Walsh
Protein Structure Prediction on the Face Centered Cubic Lattice by Local Search / 241
Manuel Cebrián, Ivan Dotú, Pascal Van Hentenryck, Peter Clote
Relaxed Survey Propagation: A Sum-Product Algorithm for Max-SAT / 247
Hai Leong Chieu, Wee Sun Lee
Virtual Arc Consistency for Weighted CSP / 253
M. Cooper, S. de Givry, M. Sanchez, T. Schiex, M. Zytnicki
Simulation-Based Approach to General Game Playing / 259
Hilmar Finnsson, Yngvi Björnsson
Phase Transitions and Complexity of Weighted Satisfiability and Other Intractable Parameterized Problems / 265
Yong Gao
Studies in Solution Sampling / 271
Vibhav Gogate, Rina Dechter
On Range of Skill / 277
Thomas Dueholm Hansen, Peter Bro Miltersen, Troels Bjerre Sørensen
Clause Learning Can Effectively P-Simulate General Propositional Resolution / 283
Philipp Hertel, Fahiem Bacchus, Toniann Pitassi, Allen Van Gelder
Piecewise Linear Dynamic Programming for Constrained POMDPs / 291
Joshua D. Isom, Sean P. Meyn, Richard D. Braatz
Efficient Memoization for Dynamic Programming with Ad-Hoc Constraints / 297
Joxan Jaffar, Andrew E. Santosa, Razvan Voicu
On the Power of Top-Down Branching Heuristics / 304
Matti Järvisalo, Tommi Junttila
Efficient Context-Free Grammar Constraints / 310
Serdar Kadioglu, Meinolf Sellmann
Minimizing Disk I/O in Two-Bit Breadth-First Search / 317
Richard E. Korf
H-DPOP: Using Hard Constraints for Search Space Pruning in DCOP / 325
Akshat Kumar, Adrian Petcu, Boi Faltings
Online Learning with Expert Advice and Finite-Horizon Constraints / 331
Branislav Kveton, Jia Yuan Yu, Georgios Theocharous, Shie Mannor
Exploiting Causal Independence Using Weighted Model Counting / 337
Wei Li, Pascal Poupart, Peter van Beek
R* Search / 344
Maxim Likhachev, Anthony Stentz
Within-problem Learning for Efficient Lower Bound Computation in Max-SAT Solving / 351
Han Lin, Kaile Su, Chu-Min Li
Learning from Multiple Heuristics / 357
Mehdi Samadi, Ariel Felner, Jonathan Schaeffer
Backdoor Trees / 363
Marko Samer, Stefan Szeider
A Global Constraint for Bin-Packing with Precedences: Application to the Assembly Line Balancing Problem / 369
Pierre Schaus, Yves Deville
Bound Consistency for Binary Length-Lex Set Constraints / 375
Pascal Van Hentenryck, Justin Yip, Carmen Gervet, Grégoire Dooms
Predicting the Performance of IDA* with Conditional Distributions / 381
Uzi Zahavi, Ariel Felner, Neil Burch, Robert C. Holte
Reasoning with Cardinal Directions: An Efficient Algorithm / 387
Xiaotong Zhang, Weiming Liu, Sanjiang Li, Mingsheng Ying
Anytime Local Search for Distributed Constraint Optimization / 393
Roie Zivan
Knowledge Representation, Logic, and Information Systems
On the Decidability of Role Mappings between Modular Ontologies / 400
Jie Bao, George Voutsadakis, Giora Slutzki, Vasant Honavar
Non-monotonic Temporal Logics that Facilitate Elaboration Tolerant Revision of Goals / 406
Chitta Baral, Jicheng Zhao
Prime Implicate Normal Form for ALC Concepts / 412
Meghyn Bienvenu
Credulous Resolution for Answer Set Programming / 418
Piero A. Bonatti, Enrico Pontelli, Tran Cao Son
Manifold Integration with Markov Random Walks / 424
Heeyoul Choi, Seungjin Choi, Yoonsuck Choe
Parallel Belief Revision / 430
James Delgrande, Yi Jin
Efficient Haplotype Inference with Answer Set Programming / 436
Esra Erdem, Ferhan Türe
Extending the Knowledge Compilation Map: Krom, Horn, Affine and Beyond / 442
Hélène Fargier, Pierre Marquis
A Meta-Programming Technique for Debugging Answer-Set Programs / 448
Martin Gebser, Jörg Pührer, Torsten Schaub, Hans Tompits
From Qualitative to Quantitative Proofs of Security Properties Using First-Order Conditional Logic / 454
Joseph Y. Halpern
Nonmonotonic Modes of Inference / 460
Victor Jauregui
Horn Complements: Towards Horn-to-Horn Belief Revision / 466
Marina Langlois, Robert H. Sloan, Balázs Szörényi, György Turán
A Reductive Semantics for Counting and Choice in Answer Set Programming / 472
Joohyung Lee, Vladimir Lifschitz, Ravi Palla
Abductive Logic Programming by Nonground Rewrite Systems / 480
Fangzhen Lin, Jia-Huai You
A Formalization of Program Debugging in the Situation Calculus / 486
Yongmei Liu
Minimal Contraction of Preference Relations / 492
Denis Mindolin, Jan Chomicki
A First-Order Theory of Stanislavskian Scene Analysis / 498
Leora Morgenstern
Worst-case Optimal Conjunctive Query Answering for an Expressive Description Logic without Inverses / 504
Magdalena Ortiz, Mantas Simkus, Thomas Eiter
An AGM-Based Belief Revision Mechanism for Probabilistic Spatio-Temporal Logics / 511
Austin Parker, Guillaume Infantes, V. S. Subrahmanian, John Grant
New Compilation Languages Based on Structured Decomposability / 517
Knot Pipatsrisawat, Adnan Darwiche
A Semantic Approach for Iterated Revision in Possibilistic Logic / 523
Guilin Qi
Terminological Reasoning in SHIQ with Ordered Binary Decision Diagrams / 529
Sebastian Rudolph, Markus Krötzsch, Pascal Hitzler
A Scalable Jointree Algorithm for Diagnosability / 535
Anika Schumann, Jinbo Huang
Factored Models for Probabilistic Modal Logic / 541
Afsaneh Shirazi, Eyal Amir
AnalogySpace: Reducing the Dimensionality of Common Sense Knowledge / 548
Robert Speer, Catherine Havasi, Henry Lieberman
An Extended Interpreted System Model for Epistemic Logics / 554
Kaile Su, Abdul Sattar
Hyperequivalence of Logic Programs with Respect to Supported Models / 560
Miroslaw Truszczynski, StefanWoltran
Generating Application-Specific Benchmark Models for Complex Systems / 566
Jun Wang, Gregory Provan
Grounding with Bounds / 572
Johan Wittocx, Maarten Mariën, Marc Denecker
Towards Automatic Animated Storyboarding / 578
Patrick Ye, Timothy Baldwin
Loop Formulas for Logic Programs with Arbitrary Constraint Atoms / 584
Jia-Huai You, Guohua Liu
Revising Imprecise Probabilistic Beliefs in the Framework of Probabilistic Logic Programming / 590
Anbu Yue, Weiru Liu
Machine Learning
Distance Metric Learning Versus Fisher Discriminant Analysis / 598
Babak Alipanahi, Michael Biggs, Ali Ghodsi
Potential-based Shaping in Model-based Reinforcement Learning / 604
John Asmuth, Michael L. Littman, Robert Zinkov
Sparse Projections over Graph / 610
Deng Cai, Xiaofei He, Jiawei Han
Clustering via Random Walk Hitting Time on Directed Graphs / 616
Mo Chen, Jianzhuang Liu, Xiaoou Tang
Integrating Multiple Learning Components through Markov Logic / 622
Thomas G. Dietterich, Xinlong Bao
A Case Study on the Critical Role of Geometric Regularity in Machine Learning / 628
Jason Gauci, Kenneth O. Stanley
Semi-Supervised Ensemble Ranking / 634
Steven C. H. Hoi, Rong Jin
Instance-level Semisupervised Multiple Instance Learning / 640
Yangqing Jia, Changshui Zhang
Zero-data Learning of New Tasks / 646
Hugo Larochelle, Dumitru Erhan, Yoshua Bengio
Dimension Amnesic Pyramid Match Kernel / 652
Yi Liu, Xu-Lei Wang, Hongbin Zha
Clustering on Complex Graphs / 659
Bo Long, Mark (Zhongfei) Zhang, Philip S. Yu, Tianbing Xu
From Comparing Clusterings to Combining Clusterings / 665
Zhiwu Lu, Yuxin Peng, Jianguo Xiao
Trace Ratio Criterion for Feature Selection / 671
Feiping Nie, Shiming Xiang, Yangqing Jia, Changshui Zhang, Shuicheng Yan
Transfer Learning via Dimensionality Reduction / 677
Sinno Jialin Pan, James T. Kwok, Qiang Yang
Active Learning for Pipeline Models / 683
Dan Roth, Kevin Small
Economic Hierarchical Q-Learning / 689
Erik G. Schultink, Ruggiero Cavallo, David C. Parkes
Markov Blanket Feature Selection for Support Vector Machines / 696
Jianqiang Shen, Lida Li, Weng-Keen Wong
On-Line Case-Based Plan Adaptation for Real-Time Strategy Games / 702
Neha Sugandh, Santiago Ontañón, Ashwin Ram
Adapting ADtrees for High Arity Features / 708
Robert Van Dam, Irene Langkilde-Geary, Dan Ventura
Efficient Learning of Action Schemas and Web-Service Descriptions / 714
Thomas J. Walsh, Michael L. Littman
On Discriminative Semi-Supervised Classification / 720
Fei Wang, Changshui Zhang
Semi-supervised Classification Using Local and Global Regularization / 726
Fei Wang, Tao Li, Gang Wang, Changshui Zhang
Learning Hidden Curved Exponential Family Models to Infer Face-to-Face Interaction Networks from Situated Speech Data / 732
Danny Wyatt, Tanzeem Choudhury, Jeff Bilmes
Hidden Dynamic Probabilistic Models for Labeling Sequence Data / 739
Xiaofeng Yu, Wai Lam
Classification by Discriminative Regularization / 746
Bin Zhang, Fei Wang, Ta-Hsin Li, Wen Jun Yin, Jin Dong
Multi-View Local Learning / 752
Dan Zhang, Fei Wang, Changshui Zhang, Tao Li
Constraint Projections for Ensemble Learning / 758
Daoqiang Zhang, Songcan Chen, Zhi-Hua Zhou, Qiang Yang
Multidisciplinary Topics and Applications
Automating To-Do Lists for Users: Interpretation of To-Dos for Selecting and Tasking Agents / 765
Yolanda Gil, Varun Ratnakar
Proactive Intrusion Detection / 772
Benjamin Liebald, Dan Roth, Neelay Shah, Vivek Srikumar
Speech-enabled Card Games for Language Learners / 778
Ian McGraw, Stephanie Seneff
Exposing Parameters of a Trained Dynamic Model for Interactive Music Creation / 784
Dan Morris, Ian Simon, Sumit Basu
Another Look at Search-Based Drama Management / 792
Mark J. Nelson, Michael Mateas
Learning to Analyze Binary Computer Code / 798
Nathan Rosenblum, Xiaojin Zhu, Barton Miller, Karen Hunt
Prediction and Change Detection in Sequential Data for Interactive Applications / 805
Jun Zhou, Li Cheng, Walter F. Bischof
Using Knowledge Driven Matrix Factorization to Reconstruct Modular Gene Regulatory Network / 811
Yang Zhou, Zheng Li, Xuerui Yang, Linxia Zhang, Shireesh Srivastava, Rong Jin, Christina Chan
Natural-Language Processing
Using Answer Set Programming and Lambda Calculus to Characterize Natural Language Sentences with Normatives and Exceptions / 818
Chitta Baral, Juraj Dzifcak, Tran Cao Son
Automatic Semantic Relation Extraction with Multiple Boundary Generation / 824
Brandon Beamer, Alla Rozovskaya, Roxana Girju
Importance of Semantic Representation: Dataless Classification / 830
Ming-Wei Chang, Lev Ratinov, Dan Roth, Vivek Srikumar
Discourse Topic and Gestural Form / 836
Jacob Eisenstein, Regina Barzilay, Randall Davis
Text Categorization with Knowledge Transfer from Heterogeneous Data Sources / 842
Rakesh Gupta, Lev Ratinov
Cross-lingual Propagation for Morphological Analysis / 848
Benjamin Snyder, Regina Barzilay
Single Document Keyphrase Extraction Using Neighborhood Knowledge / 855
Xiaojun Wan, Jianguo Xiao
Using Wiktionary for Computing Semantic Relatedness / 861
Torsten Zesch, Christof Müller, Iryna Gurevych
Reasoning about Plans, Processes, and Actions
Optimal Scheduling of Contract Algorithms with Soft Deadlines / 868
Spyros Angelopoulos, Alejandro López-Ortiz, Angèle M. Hamel
Optimal Metric Planning with State Sets in Automata Representation / 874
Björn Ulrich Borowsky, Stefan Edelkamp
PBA*: Using Proactive Search to Make A* Robust to Unplanned Deviations / 880
Paul Breimyer, Peter R. Wurman
Fast Planning by Search in Domain Transition Graph / 886
Yixin Chen, Ruoyun Huang, Weixiong Zhang
Planning with Problems Requiring Temporal Coordination / 892
Andrew Coles, Maria Fox, Derek Long, Amanda Smith
Partitioned External-Memory Value Iteration / 898
Peng Dai, Mausam, Daniel S. Weld
Error Classification in Action Descriptions: A Heuristic Approach / 905
Thomas Eiter, Michael Fink, Ján Senko
Computing Minimal Diagnoses by Greedy Stochastic Search / 911
Alexander Feldman, Gregory Provan, Arjan van Gemund
Computing Observation Vectors for Max-Fault Min-Cardinality Diagnoses / 919
Alexander Feldman, Gregory Provan, Arjan van Gemund
Finding State Similarities for Faster Planning / 925
Christian Fritz
Reasoning about Large Taxonomies of Actions / 931
Yilan Gu, Mikhail Soutchanski
Accuracy of Admissible Heuristic Functions in Selected Planning Domains / 938
Malte Helmert, Robert Mattmüller
How Good is Almost Perfect? / 944
Malte Helmert, Gabriele Röger
HTN-MAKER: Learning HTNs with Minimal Additional Knowledge Engineering Required / 950
Chad Hogg, Héctor Muñoz-Avila, Ugur Kuter
Generating Plans in Concurrent, Probabilistic, Over-Subscribed Domains / 957
Li Li, Nilufer Onder
Unknown Rewards in Finite-Horizon Domains / 963
Colin McMillen, Manuela Veloso
Route Planning under Uncertainty: The Canadian Traveller Problem / 969
Evdokia Nikolova, David R. Karger
Landmarks Revisited / 975
Silvia Richter, Malte Helmert, Matthias Westphal
Fusing Procedural and Declarative Planning Goals for Nondeterministic Domains / 983
Dzmitry Shaparau, Marco Pistore, Paolo Traverso
Learning Generalized Plans Using Abstract Counting / 991
Siddharth Srivastava, Neil Immerman, Shlomo Zilberstein
Hypothesis Pruning and Ranking for Large Plan Recognition Problems / 998
Gita Sukthankar, Katia Sycara
On the Progression of Situation Calculus Basic Action Theories: Resolving a 10-year-old Conjecture / 1004
Stavros Vassos, Hector J. Levesque
Probabilistic Planning via Determinization in Hindsight / 1010
Sungwook Yoon, Alan Fern, Robert Givan, Subbarao Kambhampati
Uncertainty in AI
CRF-OPT: An Efficient High-Quality Conditional Random Field Solver / 1018
Minmin Chen, Yixin Chen, Michael R. Brent
Focusing Generalizations of Belief Propagation on Targeted Queries / 1024
Arthur Choi, Adnan Darwiche
Many-Pairs Mutual Information for Adding Structure to Belief Propagation Approximations / 1031
Arthur Choi, Adnan Darwiche
Preference Aggregation with Graphical Utility Models / 1037
Christophe Gonzales, Patrice Perny, Sergio Queiroz
Exploiting Symmetries in POMDPs for Point-Based Algorithms / 1043
Kee-Eung Kim
Towards Faster Planning with Continuous Resources in Stochastic Domains / 1049
Janusz Marecki, Milind Tambe
A Variance Analysis for POMDP Policy Evaluation / 1056
Mahdi Milani Fard, Joelle Pineau, Peng Sun
Lifted Probabilistic Inference with Counting Formulas / 1062
Brian Milch, Luke S. Zettlemoyer, Kristian Kersting, Michael Haimes, Leslie Pack Kaelbling
Optimal Testing of Structured Knowledge / 1069
Michael Munie, Yoav Shoham
A General Method for Reducing the Complexity of Relational Inference and its Application to MCMC / 1075
Hoifung Poon, Pedro Domingos, Marc Sumner
Dormant Independence / 1081
Ilya Shpitser, Judea Pearl
Symbolic Heuristic Search Value Iteration for Factored POMDPs / 1088
Hyeong Seop Sim, Kee-Eung Kim, Jin Hyung Kim, Du-Seong Chang, Myoung-Wan Koo
Lifted First-Order Belief Propagation / 1094
Parag Singla, Pedro Domingos
Bounding the False Discovery Rate in Local Bayesian Network Learning / 1100
Ioannis Tsamardinos, Laura E. Brown
Hybrid Markov Logic Networks / 1106
Jue Wang, Pedro Domingos
Latent Tree Models and Approximate Inference in Bayesian Networks / 1112
Yi Wang, Nevin L. Zhang, Tao Chen
A General Framework for Generating Multivariate Explanations in Bayesian Networks / 1119
Changhe Yuan, Tsai-Ching Lu
Special Track on Artificial Intelligence and the Web
On the Enactability of Business Protocols / 1126
Nirmit Desai, Munindar P. Singh
Concept-Based Feature Generation and Selection for Information Retrieval / 1132
Ofer Egozi, Evgeniy Gabrilovich, Shaul Markovitch
Linking Social Networks on the Web with FOAF: A Semantic Web Case Study / 1138
Jennifer Golbeck, Matthew Rothstein
Mining Translations of Web Queries from Web Click-through Data / 1144
Rong Hu, Weizhu Chen, Jian Hu, Yansheng Lu, Zheng Chen, Qiang Yang
Hierarchical Location and Topic Based Query Expansion / 1150
Shu Huang, Qiankun Zhao, Prasenjit Mitra, C. Lee Giles
Semi-Supervised Learning for Blog Classification / 1156
Daisuke Ikeda, Hiroya Takamura, Manabu Okumura
Generating Useful Network-based Features for Analyzing Social Networks / 1162
Jun Karamon, Yutaka Matsuo, Mitsuru Ishizuka
Automatic Extraction of Data Points and Text Blocks from 2-Dimensional Plots in Digital Documents / 1169
Saurabh Kataria, William Browuer, Prasenjit Mitra, C. Lee Giles
Minimizing the Spread of Contamination by Blocking Links in a Network / 1175
Masahiro Kimura, Kazumi Saito, Hiroshi Motoda
A Utility-Theoretic Approach to Privacy and Personalization / 1181
Andreas Krause, Eric Horvitz
Query-URL Bipartite Based Approach to Personalized Query Recommendation / 1189
Lin Li, Zhenglu Yang, Ling Liu, Masaru Kitsuregawa
Extracting Relevant Snippets for Web Navigation / 1195
Qing Li, K. Selçuk Candan, Qi Yan
Intelligent Output Interface for Intelligent Medical Search Engine / 1201
Gang Luo
Neural Network based Constraint Satisfaction in Ontology Mapping / 1207
Ming Mao, Yefei Peng, Michael Spring
Supporting Manual Mapping Revision using Logical Reasoning / 1213
Christian Meilicke, Heiner Stuckenschmidt, Andrei Tamilin
Decoding Wikipedia Categories for Knowledge Acquisition / 1219
Vivi Nastase, Michael Strube
Turning Web Text and Search Queries into Factual Knowledge: Hierarchical Class Attribute Extraction / 1225
Marius Pasca
Question Utility: A Novel Static Ranking of Question Search / 1231
Young-In Song, Chin-Yew Lin, Yunbo Cao, Hae-Chang Rim
Metalevel Information in Ontology-Based Applications / 1237
Thanh Tran, Peter Haase, Boris Motik, Bernardo Cuenca Grau, Ian Horrocks
Finding Cars, Goddesses and Enzymes: Parametrizable Acquisition of Labeled Instances for Open-Domain Information Extraction / 1243
Benjamin Van Durme, Marius Pasca
An Unsupervised Approach for Product Record Normalization across Different Web Sites / 1249
Tak-Lam Wong, Tik-Shun Wong, Wai Lam
A User-Oriented Webpage Ranking Algorithm Based on User Attention Time / 1255
Songhua Xu, Yi Zhu, Hao Jiang, Francis C. M. Lau
Efficient Querying Relaxed Dominant Relationship between Product Items Based on Rank Aggregation / 1261
Zhenglu Yang, Lin Li, Masaru Kitsuregawa
Special Track on Integrated Intelligence
Spatial Scaffolding for Sociable Robot Learning / 1268
Cynthia Breazeal, Matt Berlin
POIROT — Integrated Learning of Web Service Procedures / 1274
Mark Burstein, Robert Laddaga, David McDonald, Michael Cox, Brett Benyo, Paul Robertson, Talib Hussain, Marshall Brinn, Drew McDermott
An Integrated Reasoning Approach to Moral Decision-Making / 1280
Morteza Dehghani, Emmett Tomai, Ken Forbus, Matthew Klenk
RADAR: A Personal Assistant that Learns to Reduce Email Overload / 1287
Michael Freed, Jaime Carbonell, Geoff Gordon, Jordan Hayes, Brad Myers, Daniel Siewiorek, Stephen Smith, Aaron Steinfeld, Anthony Tomasic
The PELA Architecture: Integrating Planning and Learning to Improve Execution / 1294
Sergio Jiménez, Fernando Fernández, Daniel Borrajo
Incorporating Mental Simulation for a More Effective Robotic Teammate / 1300
William G. Kennedy, Magdalena D. Bugajska, William Adams, Alan C. Schultz, J. Gregory Trafton
Pervasive Diagnosis: The Integration of Diagnostic Goals into Production Plans / 1306
Lukas Kuhn, Bob Price, Johan de Kleer, Minh Do, Rong Zhou
An Integrated Agent for Playing Real-Time Strategy Games / 1313
Josh McCoy, Michael Mateas
Adaptive Control for Autonomous Underwater Vehicles / 1319
Conor McGann, Frederic Py, Kanna Rajan, John Ryan, Richard Henthorn
Achieving Far Transfer in an Integrated Cognitive Architecture / 1325
Dan Shapiro, Tolga Könik, Paul O’Rorke
Bimodal Spatial Reasoning with Continuous Motion / 1331
Samuel Wintermute, John E. Laird
Special Track on Physically Grounded Artificial Intelligence
Planning for Human-Robot Interaction Using Time-State Aggregated POMDPs / 1339
Frank Broz, Illah Nourbakhsh, Reid Simmons
The Hidden Permutation Model and Location-Based Activity Recognition / 1345
Hung H. Bui, Dinh Phung, Svetha Venkatesh, Hai Phan
Adaptive Importance Sampling with Automatic Model Selection in Value Function Approximation / 1351
Hirotaka Hachiya, Takayuki Akiyama, Masashi Sugiyama, Jan Peters
Anticipatory Perceptual Simulation for Human-Robot Joint Practice: Theory and Application Study / 1357
Guy Hoffman, Cynthia Breazeal
CIGAR: Concurrent and Interleaving Goal and Activity Recognition / 1363
Derek Hao Hu, Qiang Yang
Efficient Optimization of Information-Theoretic Exploration in SLAM / 1369
Thomas Kollar, Nicholas Roy
An Efficient Motion Planning Algorithm for Stochastic Dynamic Systems with Constraints on Probability of Failure / 1376
Masahiro Ono, Brian C. Williams
Transferring Localization Models across Space / 1383
Sinno Jialin Pan, Dou Shen, Qiang Yang, James T. Kwok
Structure Learning on Large Scale Common Sense Statistical Models of Human State / 1389
William Pentney, Matthai Philipose, Jeff Bilmes
Reducing Particle Filtering Complexity for 3D Motion Capture using Dynamic Bayesian Networks / 1396
Cédric Rose, Jamal Saboune, François Charpillet
A Fast Data Collection and Augmentation Procedure for Object Recognition / 1402
Benjamin Sapp, Ashutosh Saxena, Andrew Y. Ng
Multimodal People Detection and Tracking in Crowded Scenes / 1409
Luciano Spinello, Rudolph Triebel, Roland Siegwart
Feature Selection for Activity Recognition in Multi-Robot Domains / 1415
Douglas L. Vail, Manuela M. Veloso
Transferring Localization Models over Time / 1421
Vincent Wenchen Zheng, Evan Wei Xiang, Qiang Yang, Dou Shen
Transferring Multi-device Localization Models using Latent Multi-task Learning / 1427
Vincent Wenchen Zheng, Sinno Jialin Pan, Qiang Yang, Jeffrey Junfeng Pan
Maximum Entropy Inverse Reinforcement Learning / 1433
Brian D. Ziebart, Andrew Maas, J. Andrew Bagnell, Anind K. Dey
Short Papers
Interaction Structure and Dimensionality Reduction in Decentralized MDPs / 1440
Martin Allen, Marek Petrik, Shlomo Zilberstein
Generating Hard SAT/CSP Instances Using Expander Graphs / 1442
Carlos Ansótegui, Ramón Béjar, Cèsar Fernández, Carles Mateu
An Effective and Robust Method for Short Text Classification / 1444
Victoria Bobicev, Marina Sokolova
Hybrid Constraint Tightening for Solving Hybrid Scheduling Problems / 1446
James C. Boerkoel Jr., Edmund H. Durfee
Data-Driven Programming and Behavior for Autonomous Virtual Characters / 1450
Jonathan Dinerstein, Parris K. Egbert, Dan Ventura, Michael Goodrich
Limits and Possibilities of BDDs in State Space Search / 1452
Stefan Edelkamp, Peter Kissmann
Expectation-Based Versus Potential-Aware Automated Abstraction in Imperfect Information Games: An Experimental Comparison Using Poker / 1454
Andrew Gilpin, Tuomas Sandholm
Learning to Identify Reduced Passive Verb Phrases with a Shallow Parser / 1458
Sean Igo, Ellen Riloff
The Re-Representation Problem in a Logic-Based Framework for Analogy Making / 1462
Ulf Krumnack, Helmar Gust, Kai-Uwe Kühnberger, Angela Schwering
A Bayesian Kernel Logistic Discriminant Model: An Improvement to the Kernel Fisher’s Discriminant / 1464
R. Ksantini, D. Ziou, B. Colin, F. dubeau
Dynamic Distributed Constraint Reasoning / 1466
Robert N. Lass, Evan A. Sultanik, William C. Regli
Ensemble Forecasting for Disease Outbreak Detection / 1470
Thomas H. Lotze, Galit Shmueli
Fast Spectral Learning using Lanczos Eigenspace Projections / 1472
Sridhar Mahadevan
Efficiently Exploiting Dependencies in Local Search for SAT / 1476
Duc Nghia Pham, John Thornton, Abdul Sattar
Towards Synthesizing Optimal Coordination Modules for Distributed Agents / 1479
Manh Tung Pham, Kiam Tian Seow
A New Clause Learning Scheme for Efficient Unsatisfiability Proofs / 1481
Knot Pipatsrisawat, Adnan Darwiche
Bayes-Relational Learning of Opponent Models from Incomplete Information in No-Limit Poker / 1485
Marc Ponsen, Jan Ramon, Tom Croonenborghs, Kurt Driessens, Karl Tuyls
Multi-HDP: A Non Parametric Bayesian Model for Tensor Factorization / 1487
Ian Porteous, Evgeniy Bart, Max Welling
Learning Grasp Strategies with Partial Shape Information / 1491
Ashutosh Saxena, Lawson L. S. Wong, Andrew Y. Ng
Incremental Algorithms for Approximate Compilation / 1495
Alberto Venturini, Gregory Provan
Computing Reserve Prices and Identifying the Value Distribution in Real-world Auctions with Market Disruptions / 1499
William E. Walsh, David C. Parkes, Tuomas Sandholm, Craig Boutilier
Multi-Label Dimensionality Reduction via Dependence Maximization / 1503
Yin Zhang, Zhi-Hua Zhou
Online Learning in Monkeys / 1506
Xiaojin Zhu, Michael Coen, Shelley Prudom, Ricki Colman, Joseph Kemnitz
Nectar Papers
Beyond Classical Planning: Procedural Control Knowledge and Preferences in State-of-the-Art Planners / 1509
Jorge A. Baier, Christian Fritz, Meghyn Bienvenu, Sheila A. McIlraith
Learning and Inference with Constraints / 1513
Ming-Wei Chang, Lev Ratinov, Nicholas Rizzolo, Dan Roth
On-line Planning and Scheduling: An Application to Controlling Modular Printers / 1519
Minh B. Do, Wheeler Ruml, Rong Zhou
Intelligent Email: Aiding Users with AI / 1524
Mark Dredze, Hanna M. Wallach, Danny Puller, Tova Brooks, Josh Carroll, Joshua Magarick, John Blitzer, Fernando Pereira
Magic Sets for Data Integration / 1528
Wolfgang Faber, Gianluigi Greco, Nicola Leone
Decision-Theoretic User Interface Generation / 1532
Krzysztof Z. Gajos, Daniel S. Weld, Jacob O. Wobbrock
Achieving Master Level Play in 9 x 9 Computer Go / 1537
Sylvain Gelly, David Silver
Abduction with Bounded Treewidth: From Theoretical Tractability to Practically Efficient Computation / 1541
Georg Gottlob, Reinhard Pichler, Fang Wei
Explicit-State Abstraction: A New Method for Generating Heuristic Functions / 1547
Malte Helmert, Patrik Haslum, Jörg Hoffmann
Video Activity Recognition in the Real World / 1551
Anthony Hoogs, A. G. Amitha Perera
An Analysis of Transformational Analogy: General Framework and Complexity / 1555
Vithal Kuchibatla, Héctor Muñoz-Avila
Efficient Algorithms to Solve Bayesian Stackelberg Games for Security Applications / 1559
Praveen Paruchuri, Jonathan P. Pearce, Janusz Marecki, Milind Tambe, Fernando Ordonez, Sarit Kraus
Examining Difficulties Software Developers Encounter in the Adoption of Statistical Machine Learning / 1563
Kayur Patel, James Fogarty, James A. Landay, Beverly Harrison
Decompositions of Grammar Constraints / 1567
Claude-Guy Quimper, Toby Walsh
Make3D: Depth Perception from a Single Still Image / 1571
Ashutosh Saxena, Min Sun, Andrew Y. Ng
Using Signals of Human Interest to Enhance Single-document Summarization / 1577
Krysta M. Svore, Lucy Vanderwende, Christopher J. C. Burges
Adaptive Management of Air Traffic Flow: A Multiagent Coordination Approach / 1581
Kagan Tumer, Adrian Agogino
Breaking Value Symmetry / 1585
Toby Walsh
Senior Member Papers
An Interaction-Based Approach to Computational Epidemiology / 1590
Christopher L. Barrett, Stephen Eubank, Madhav V. Marathe
What Is Answer Set Programming? / 1594
Vladimir Lifschitz
Learning to Connect Language and Perception / 1598
Raymond J. Mooney
Artificial Intelligence Needs Open-Access Knowledgebase Contents / 1602
Erik Sandewall
Game Theory Pragmatics: A Challenge for AI / 1606
Yoav Shoham
Intelligence in Wikipedia / 1609
Daniel S. Weld, Fei Wu, Eytan Adar, Saleema Amershi, James Fogarty, Raphael Hoffmann, Kayur Patel, Michael Skinner
Innovative Applications of Artificial Intelligence
Deployed Papers
Using AI for Olympic Equestrian Event Preparation / 1616
Andy Hon Wai Chun
A Case Study of AI Application on Language Instruction: CSIEC / 1624
Jiyou Jia
Tactical Language and Culture Training Systems: Using Artificial Intelligence to Teach Foreign Languages and Cultures / 1632
W. Lewis Johnson, Andre Valente
The Law of Choice and the Decision Not to Decide / 1640
David C. Wilson, Suzanne Leland, Kenneth Godwin, Andrew Baxter, Ashley Levy, Jamie Smart, Nadia Najjar, Jayakrishnan Andaparambil
Emerging Papers
Application of Artificial Intelligence to Operational Real-Time Clear-Air Turbulence Prediction / 1649
Jennifer Abernethy, Robert Sharman, Elizabeth Bradley
Reinforcement Learning for Vulnerability Assessment in Peer-to-Peer Networks / 1655
Scott Dejmal, Alan Fern, Thinh Nguyen
Learning Sparse Kernels from 3D Surfaces for Heart Wall Motion Abnormality Detection / 1663
Glenn Fung, Sriram Krishnan, R. Bharat Rao, Hui Chen
Adaptive Treatment of Epilepsy via Batch-mode Reinforcement Learning / 1671
Arthur Guez, Robert D. Vincent, Massimo Avoli, Joelle Pineau
Enabling the Interoperability of Large-Scale Legacy Systems / 1679
Kalyan Moy Gupta, Mike Zang, Adam Gray, David W. Aha, Joe Kriege
Finding Ontological Correspondences for a Domain-Independent Natural Language Dialog Agent / 1685
Hamid Haidarian Shahri, Donald Perlis
Personalisation of Telecommunications Services as Combinatorial Optimisation / 1693
David Lesaint, Deepak Mehta, Barry O’Sullivan, Luis Quesada, Nic Wilson
Diagnosing Faults in Electrical Power Systems of Spacecraft and Aircraft / 1699
Ole J. Mengshoel, Adnan Darwiche, Keith Cascio, Mark Chavira, Scott Poll, Serdar Uckun
Local Search for Optimal Global Map Generation Using Mid-Decadal Landsat Images / 1706
Robert A. Morris, John Gasch, Lina Khatib, Steven Covington
Learning to Improve Earth Observation Flight Planning / 1712
Robert A. Morris, Nikunj Oza, Leslie Keely, Elif Kürklü, Anthony Strawa
On-line Recognition of Surgical Activity for Monitoring in the Operating Room / 1718
N. Padoy, T. Blum, H. Feussner, M-O. Berger, N. Navab
COACH - Cumulative Online Algorithm for Classification of Handwriting Deficiencies / 1725
Ariella Richardson, Sarit Kraus, Patrice L. Weiss, Sara Rosenblum
Real-time Alert Correlation Using Stream Data Mining Techniques / 1731
Reza Sadoddin, Ali A. Ghorbani
A Hybrid Approach to Convoy Movement Planning in an Urban City / 1738
Ramesh Thangarajoo, Lucas Agussurja, Hoong Chuin Lau
In-the-Dark Network Traffic Classification Using Support Vector Machines / 1745
William H. Turkett, Jr., Andrew V. Karode, Errin W. Fulp
Crops Selection for Optimal Soil Planning using Multiobjective Evolutionary Algorithms / 1751
Christian Von Lücken, Ricardo Brunelli
Semantic Web Development for Traditional Chinese Medicine / 1757
Zhaohui Wu, Tong Yu, Huajun Chen, Xiaohong Jiang, Chunying Zhou, Yu Zhang, Yuxin Mao, Yi Feng, Meng Cui, Aining Yin
A Vehicle Routing System to Solve a Periodic Vehicle Routing Problem for a Food Chain in Hong Kong / 1763
Jianfeng Zhu, Wenbin Zhu, Chan Hou Che, Andrew Lim
Student Abstracts
Using Reasoning Patterns to Simplify Games / 1770
Dimitrios Antos, Avi Pfeffer
Lexical and Grammatical Inference / 1772
Tom Armstrong, Tim Oates
The Benefits of an Ontological Patient Model in Clinical Decision-Support / 1774
Mark Austin, Matthew Kelly, Sir Michael Brady
Using Clustering Methods for Discovering Event Structures / 1776
Cosmin Adrian Bejan, Sanda Harabagiu
Distributed Reasoning with Conflicts in a Multi-Context Framework / 1778
Antonis Bikakis, Grigoris Antoniou
Conformant Planning Heuristics Based on Plan Reuse in Belief States / 1780
Dunbo Cai, Jigui Sun, Minghao Yin
Personalized Reasoner Based on Belief Strengths of Information Sources / 1782
Shu-Bin Cai, Zhong Ming, Shi-Xian Li
A Neuro-Fuzzy Strategy for Web Personalization / 1784
G. Castellano, A. M. Fanelli, P. Plantamura, M. A. Torsello
Sketch Recognition Based on Manifold Learning / 1786
Heeyoul Choi, Tracy Hammond
GLADDER: Combining Gesture and Geometric Sketch Recognition / 1788
Paul Corey, Tracy Hammond
Distinguishing between Sketched Scribble Look Alikes / 1790
Katie Dahmen, Tracy Hammond
Perpetual Learning for Non-Cooperative Multiple Agents / 1792
Luke Dickens
User Identification by Means of Sketched Stroke Features / 1794
Brian David Eoff, Tracy Hammond
Unsupervised Categorization (Filtering) of Google Images Based on Visual Consistency / 1796
Pooyan Fazli, Ara Bedrosian
Existentially Quantified Values for Queries and Updates of Facts in Transaction Logic Programs / 1798
Paul Fodor
Querying Sequential and Concurrent Horn Transaction Logic Programs Using Tabling Techniques / 1800
Paul Fodor
Predicting Appropriate Semantic Web Terms from Words / 1802
Lushan Han, Tim Finin
Improving a Plan Library for Real-time Systems Using Nearly Orthogonal Latin Hypercube Sampling / 1804
Robert Holder
Text Beautifier: An Affective-Text Tool to Tailor Written Text / 1806
Fahim Kawsar, Mostafa Al Masum Shaikh, Mitsuru Ishizuka
A Self-organizing Multi-agent System for Adaptive Continuous Unsupervised Learning in Complex Uncertain Environments / 1808
Igor Kiselev, Reda Alhajj
Loop Calculus for Satisfiability / 1810
Lukas Kroc, Michael Chertkov
Constrained Classification on Structured Data / 1812
Chi-Hoon Lee, Matthew Brown, Russell Greiner, Shoajun Wang, Albert Murtha
Chatting Activity Recognition in Social Occasions Using Factorial Conditional Random Fields with Iterative Classification / 1814
Chia-chun Lian, Jane Yung-jen Hsu
Discover Relevant Environment Feature Using Concurrent Reinforcement Learning / 1816
Zhihui Luo, David Bell, Barry McCollum
2-Dimensional Cellular Automata Approach for Robot Grid Formations / 1818
Ross Mead, Jerry B. Weinberg
Hierarchical Voting Experts: An Unsupervised Algorithm for Segmenting Hierarchically Structured Sequences / 1820
Matthew Miller, Alexander Stoytchev
The Swarm Application Framework / 1822
Don Miner, Marie desJardins, Peter Hamilton
ADROIT: Automatic Discourse Relation Organizer of Internet-based Text / 1824
A. S. M. Mahbub Morshed, Mitsuru Ishizuka
NP-Completeness of Outcome Optimization for Partial CP-Nets / 1826
Keith Purrington, Edmund H. Durfee
Toward Autonomous Learning of an Ontology of Tool Affordances by a Robot / 1828
Jivko Sinapov, Alexander Stoytchev
The Validity of Providing Automated Hints in an ITS Using a MDP / 1830
John C. Stamper, Tiffany Barnes
Using a Geometric-Based Sketch Recognition Approach to Sketch Chinese Radicals / 1832
Paul Taele, Tracy Hammond
Efficient Haplotype Inference with Answer Set Programming / 1834
Ferhan Türe, Esra Erdem
Eliminating False Positives during Corner Finding by Merging Similar Segments / 1836
Aaron Wolin, Brandon Paulson, Tracy Hammond
Visualization of Large-Scale Weighted Clustered Graph: A Genetic Approach / 1838
Jiayu Zhou, Youfang Lin, Xi Wang
Doctoral Consortium Abstracts
The Relational Push-Pull Model: A Generative Model for Relational Data Clustering / 1841
Adam Anthony
Towards Answer Set Prolog Based Architectures for Intelligent Agents / 1843
Sandeep Chintabathina
Unstructured Audio Classification for Environment Recognition / 1845
Selina Chu
An Architecture and Formalism for Handling Modular Ontologies / 1847
Faezeh Ensan
Optimizations and Extensions for the Horn Transaction Logic Programs / 1849
Paul Fodor
Social Interaction under Uncertainty in Multi Agent Systems / 1851
Noam Hazon
Tightly Coupled Cooperation among Independent Agents / 1853
Daylond Hooper
Autonomous Robot Skill Acquisition / 1855
George Konidaris
Generating Plans in Concurrent, Probabilistic, Over-Subscribed Domains / 1857
Li Li
Adaptive Abstraction of Constraint-Based Models for Self-Diagnosis and Planning / 1859
Paul Maier
Distributed Robust Execution of Qualitative State Plan with Chance Constraints / 1861
Masahiro Ono
Combining Global Relevance Information with Local Contextual Clues for Event-Oriented Information Extraction / 1863
Siddharth Patwardhan
Computational Influence for Training and Entertainment / 1865
David L. Roberts
Integrative Construction and Analysis of Condition-specific Biological Networks / 1867
Sushmita Roy, Terran Lane, Margaret Werner-Washburne
Managing Quality of Service with Soft Constraints / 1869
Francesco Santini
Intelligent Systems Demonstrations
The Benefits of an Ontological Patient Model in Clinical Decision-Support / 1872
Mark Austin, Matthew Kelly, Sir Michael Brady
A Hybrid Approach to Domino Portrait Generation / 1874
Hadrien Cambazard, John Horan, Eoin O’Mahony, Barry O’Sullivan
A Demonstration of the RADAR Personal Assistant / 1876
Andrew Faulring, Brad Myers, Ken Mohnkern, Michael Freed
CogSketch / 1878
Ken Forbus, Andrew Lovett, Kate Lockwood, Jon Wetzel, Camillia Matuk, Ben Jee, Jeffrey Usher
Yoopick: A Combinatorial Sports Prediction Market / 1880
Sharad Goel, David Pennock, Daniel Reeves, Cong Yu
Prometheus Design Tool / 1882
Lin Padgham, John Thangarajah, Michael Winikoff
ARMOR Security for Los Angeles International Airport / 1884
James Pita, Manish Jain, Fernando Ordóñez, Christopher Portway, Milind Tambe, Craig Western, Praveen Paruchuri, Sarit Kraus
Human-Robot Collaboration for Remote Surveillance / 1886
Evan A. Sultanik, Ilya Braude, Peter Thai, Robert N. Lass, Duc N. Nguyen, Joseph B. Kopena, William C. Regli, Sean A. Lisse, Steven N. Furtwangler, Alan J. Vayda
Knowledge-Based Spatial Reasoning for Scene Generation from Text Descriptions / 1888
Dan Tappan
IMT: A Mixed-Initiative Data Mapping and Search Toolkit / 1890
Michael Zang, Adam Gray, Joe Kriege, Kalyan Moy Gupta, David W. Aha
Index
Index / 1892