IJCAI 2003  VOL

 

 

Al AND DATA INTEGRATION

Learning Value Predictors for the Speculative Execution of Information Gathering Plans

Greg Barish and Craig A. Knobbck................ 3

Logic Programs for Consistently Querying Data Integration Systems

Loreto Bravo and Leopoldo Bertossi............... 10

Query rewriting and answering under constraints in data integration systems

Andrea Caii, Domenico Lembo, and Riccardo Rosati.............................. 16

Integrating Multiple Internet Directories by Instance-based Learning

Ryutaro Jchise, Hiedeaki Takeda, and Shinichi Honiden............................ 22

Al AND THE INTERNET

A semantic framework for multimedia document adaptation

Jirome Euzenat, Nabil Layatda, and Victor Dias..... 31

An Ontology-based Architecture for Cooperative Information Agents

Frederico L G. Freitas and Guilherme Bittencourt.... 37

Web Page Cleaning for Web Mining through Feature Weighting

Lan Yi and Bing Liu.......................... 43

ART AND CREATIVITY

A Learning-Based Jam Session System that Imitates aPlayers Personality Model

Masatoshi Hamanaka, Masataka Goto, Hideki Asoh, and Nobuyuki Otsu........................... 51

Getting Serious about the Development of Computational Humor

Oliviero Stock and Carlo Strapparava.............. 59

Automated Generation of Graphic Sketches by Example

Michelle X. Zhou and Min Chen................. 65

AUTOMATED REASONING

Logical Filtering

EyalAmir and Stuart Russell.................... 75

A Tractability Result for Reasoning with Incomplete First-Order Knowledge Bases

Yongmei Liu and Hector J. Levesque.............. 83

Practical Partition-Based Theorem Proving for Large Knowledge Bases

BillMacCartney, Sheila Mcllraith, Eyal Amir, and Tomds E. Uribe..............................89

BELIEF REVISION AND UPDATE

On the Revision of Probabilistic Beliefs using Uncertain Evidence

Hei Chan and Adnan Darwiche..................99

Quantifying information and contradiction in propositional logic through test actions

Se'bastien Konieczny, Jerome Lang, and

Pierre Marquis..............................106

Minimal Change and Maximal Coherence for Epistemic Logic Program Updates

Yan Zhang.................................112

CASE-BASED REASONING

Increasing Dialogue Efficiency in Case-Based Reasoning Without Loss of Solution Quality

David McSherry............................. 121

The Power of Suggestion

Barry Smyth and Lorraine McGinty..............127

A Weighted Polynomial Information Gain Kernel for Resolving Prepositional Phrase Attachment Ambiguities with Support Vector Machines

Bram Vanschoenwinkel and Bernard Manderick.....133

CAUSALITY

A Logic For Causal Reasoning

Alexander Bochman.......................... 141

Responsibility and Blame: A Structural-Model Approach

Hana Chockler and Joseph Y Halpern............. 147

Causes and Explanations Revisited

James D. Park.............................. 154

COGNITIVE MODELING

GHOST: experimenting conflicts countermeasures in the pilots activity

Frediric Dehais, Catherine Tessier, and

Laurent Chaudron...........................163

Dynamic Bayesian modeling of the cerebral activity

Vincent Labatut, Josette Pastor, and Serge Ruff......169

COGNITIVE ROBOTICS

Body Movement Analysis of Human-Robot Interaction

Takayuki Kanda, Hiroshi Ishiguro, Michita Imai, and Tetsuo Ono................................ 177

Qualitative Map Learning Based on Co-visibility of Objects

Takehisa Yairi and Koichi Hori............... . 183

CONSTRAINTS

Propagate the Right Thing: How Preferences Can Speed-Up Constraint Solving

Christian Bessiere, Anai's Fabre, and Ulrich Junker. . . 191

Amalgams of Constraint Satisfaction Problems

Andrei A. Bulatov and Eugeny S. Skvortsov........ 197

On a generalization of triangulated graphs for domains decomposition of CSPs

Assef Chmeiss, Philippe Je'gou, and Lamia Keddar . . . 203

A Maximal Tractable Class of Soft Constraints

David Cohen, Martin Cooper, Peter Jeavons, and Andrei Krokhin............................. 209

Reasoning about soft constraints and conditional preferences: complexity results and approximation techniques

C Domshlak, E Rossi, K. B. Venable, and T Walsh.................................. 215

Multiset Ordering Constraints

Alan Frisch, Ian Miguel, Zeynep Kiziltan, Brahim Hnich, and Toby Walsh................. 221

Non-Binary Constraints and Optimal Dual-Graph Representations

Gianluigi Greco and Francesco Scarcello........... 227

Algorithms for Identifying Rigid Subsystems in Geometric Constraint Systems

Christophe Jermann, Bertrand Neveu, and Gilles Trombettoni........................... 233

In the quest of the best form of local consistency for Weighted CSP

Javier Larrosa and Thomas Schiex............... 239

A Fast and Simple Algorithm for Bounds Consistency of the All Different Constraint

Alejandro Ldpez-Ortiz, Claude-Guy Quimper, John Tromp, and Peter van Beek................ 245

Solving Constraint Optimization Problems in Anytime Contexts

Samir Loudni and Patrice Boizumault............ 251

Scenario-based Stochastic Constraint Programming

Suresh Manandhar, Armagan Tarim, and Toby Walsh................................ 257

Consistency and Set Intersection

Yuanlin Zhang and Roland H. C Yap............ 263

CONSTRAINTS AND SYMMETRY

Efficient Symmetry Breaking for Boolean Satisfiability

Fadi A. Aloul, Karem A. Sakallah, and Igor L Markov..............................271

Tractable Symmetry Breaking for CSPs with Interchangeable Values

P. Van Hentenryck, P Flener, J. Pearson, and M. Agren..................................277

DECISION THEORY

On the Foundations of Expected Expected Utility

Craig Boutilier..............................285

Great Expectations. Part I: On the Customizability of Generalized Expected Utility

Francis C Chu and Joseph Y Halpern............291

Great Expectations. Part II: Generalized Expected Utility as a Universal Decision Rule

Francis C Chu and Joseph Y Halpern............297

Qualitative Decision under Uncertainty: Back to Expected Utility

Htfene Fargier and Re'gis Sabbadin...............303

Incremental Utility Elicitation with the Minimax Regret Decision Criterion

Tianhan Wang and Craig Boutilier...............309

DESCRIPTION LOGICS

Least Common Subsumers and Most Specific Concepts in a Description Logic with Existential Restrictions and Terminological Cycles

Franz Baader...............................319

Terminological Cycles in a Description Logic with Existential Restrictions

Franz Baader...............................325

On the Undecidability of Description and Dynamic Logics with Recursion and Counting

Piero A. Bonatti.............................331

Abductive Matchmaking using Description Logics

Tommaso Di Noia, Eugenio Di Sciascio, Francesco M. Donini, and Marina Mongiello.......337

Decidability of SHIQ with Complex Role Inclusion Axioms

Ian Horrocks and Ulrike Sattler.................343

Keys, Nominals, and Concrete Domains

Carsten Lutz, Carlos Areces, Ian Horrocks, and Ulrike Sattler...............................349

Non-Standard Reasoning Services for the Debugging of Description Logic Terminologies

Stefan Schlobach and Ronald Cornet..............355

DIAGNOSIS

Formal Verification of Diagnosability via Symbolic Model Checking

Alessandro Cimatti, Charles Pecheur, and Roberto Cavada............................. 363

On the Design of Social Diagnosis Algorithms for Multi-Agent Teams

Meir Kalech and Gal A. Kaminka............... 370

Model-based Diagnosis of Hybrid Systems

Sriram Narasimhan and Gautam Biswas.......... 376

Automated Qualitative Domain Abstraction

Martin Sachenbacher and Peter Struss............ 382

Coupling CSP Decomposition Methods and Diagnosis Algorithms for Tree-Structured Systems

Markus Stumptner and Franz Wotawa............ 388

Automatic Abstraction in Component-Based Diagnosis Driven by System Observability

Gianluca Torta and Pietro Torasso............... 394

INFORMATION EXTRACTION

Information Extraction from Web Documents Based on Local Unranked Tree Automaton Inference

Raymond Kosala, Maurice Bruynooghe, Jan Van den Bussche, and Hendrik Blocked........ 403

Intelligent Multimedia Indexing and Retrieval through Multi-source Information Extraction and Merging

Jan Kuper, Horacio Saggion, Hamish Cunningham, Thierry Declerck, Franciska de Jong, Dennis Reidsma, Yorick Wilks, and Peter Wittenburg.......... 409

Active Learning with Strong and Weak Views: A Case Study on Wrapper Induction

Ion Muslea, Steven N Minton, and Craig A. Knoblock........................... 415

Bayesian Information Extraction Network

Leonid Peshkin andAvi Pfeffer.................. 421

Hierarchical Hidden Markov Models for Information Extraction

Marios Skounakis, Mark Craven, and Soumya Ray................................ 427

Coherent Keyphrase Extraction via Web Mining

Peter D. Turney............................. 434

KNOWLEDGE REPRESENTATION

From Logic Programming Semantics to the Consistency of Syntactical Treatments of Knowledge and Belief

Thomas Bolander............................ 443

Inverse Circumscription

Hubie Chen................................ 449

A Theory of Average-Case Compilability in Knowledge Representation

Hubie Chen................................455

LADDER: A Language to Describe Drawing, Display, and Editing in Sketch Recognition

Tracy Hammond and Randall Davis..............461

Evaluating Significance of Inconsistencies

Anthony Hunter.............................468

LEARNING

CLUSTERING AND BAYES NET LEARNING

Data Clustering: Principal Components, Hopfield and Self-Aggregation Networks

Chris H Q Ding............................479

Distributed Clustering Based on Sampling Local Density Estimates

Matthias Klusch, Stefano Lodi, and Gianluca Moro..............................485

When Discriminative Learning of Bayesian Network Parameters Is Easy

 Hannes Wettig, Peter Grunwald, Teemu Roos, Petri Myllymdki, and Henry Tirri................491

ENSEMBLES

Monte Carlo Theory as an Explanation of Bagging and Boosting

Roberto Esposito and Lorenza Saitta..............499

Constructing Diverse Classifier Ensembles using Artificial Training Examples

Prem Melville and Raymond J. Mooney...........505

EVALUATING CLASSIFIERS

Evaluating Classifiers by Means of Test Data with Noisy Labels

Chuck P. Lam and David G. Stork............... 513

AUC: a Statistically Consistent and more Discriminating Measure than Accuracy

Charles X. Ling, Jin Huang, and Harry Zhang......519

INDUCTIVE LOGIC PROGRAMMING

Spaces of Theories with Ideal Refinement Operators

Nicola Fanizzi, Stefano Ferilli, Nicola Di Mauro, and Teresa M. A. Basile.......................527

Learning Minesweeper with Multinational Learning

Lourdes Pena Castillo and Stefan Wrobel...........533

KERNEL METHODS

Multi-prototype Support Vector Machine

Fabio Aiolli and Alessandro Sperduti..............541

Continuous nonlinear dimensionality reduction by kernel eigenmaps

Matthew Brand.............................547

PARTIALLY LABELED DATA

Semi-Supervised Learning with Explicit Misclassification Modeling

Massih-Reza Amini and Patrick Gallinari......... 555

Spectral Learning

Sepandar D. Kamvar, Dan Klein, and Christopher D. Manning...................... 561

SVMC: Single-Class Classification With Support Vector Machines

Hwanjo Yu................................ 567

TEXT AND WEB

A Learning Algorithm for Web Page Scoring Systems

Michelangelo Diligenti, Marco Gori, and Marco Maggini............................. 575

Does a New Simple Gaussian Weighting Approach Perform Well in Text Categorization?

Giorgio Maria Di Nunzio and Alessandro Micarelli.......................... 581

Learning to Classify Texts Using Positive and Unlabeled Data

Xiaoli Li and Bing Liu....................... 587

TREE LEARNING

Inductive Learning in Less Than One Sequential Data Scan

Wei Fan, Haixun Wang, Philip S. Yu, and Shaw-Hwa Lo.............................. 595

Skewing: An Efficient Alternative to Lookahead for Decision Tree Induction

David Page and Soumya Ray................... 601

MULTIAGENT SYSTEMS

COALITION FORMATION

Complexity of Determining Nonemptiness of the Core

Vincent Conitzer and Tuomas Sandholm.......... 613

An Integrated Multilevel Learning Approach to Multiagent Coalition Formation

Leen-Kiat Soh andXin Li..................... 619

Dynamics of Coalition Formation in Combinatorial Trading

Yiming Ye and Yuhai Tu...................... 625

EMERGENT BEHAVIOR

Biologically-Inspired Self-Assembly of Two-Dimensional Shapes Using Global-to-Local Compilation

Attila Kondacs.............................. 633

Emergence of Cooperation in a Pursuit-Evasion Game

Geoff Nitschke.............................. 639

EVOLUTION AND GENETIC ALGORITHMS

When Evolving Populations is Better than Coevolving Individuals: The Blind Mice Problem

Thomas Miconi.............................647

Improving Coevolutionary Search for Optimal Multiagent Behaviors

Liviu Panait, R. Paul Wiegand, and Sean Luke.....653

GAME PLAYING

Approximating Game-Theoretic Optimal Strategies for Full-scale Poker

D. Billings, N Burch, A. Davidson, R. Holte, J. Schaeffer, T. Schauenberg, and D. Szafron........661

Last-Branch and Speculative Pruning Algorithms for Max

Nathan Sturtevant...........................669

LOGIC-BASED MAS AND COMMUNICATION LANGUAGES

Protocol Conformance for Logic-based Agents

Ulrich Endriss, Nicolas Maudet, Fariba Sadri, and Francesca Toni..............................679

Hidden Uncertainty in the Logical Representation of Desires

Jerome Lang, Leendert van der Torre, and Emil Weydert...............................685

Constitutive Rules for Agent Communication Languages

Jeremy Pitt.................................691

MULTIAGENT REINFORCEMENT LEARNING AND POMDPs

Simultaneous Adversarial Multi-Robot Learning

Michael Bowling and Manuela Veloso.............699

Taming Decentralized POMDPs: Towards Efficient Policy Computation for Multiagent Settings

R. Nair, M. Tambe, M. Yokoo, D. Pynadath, and S. Marsella.................................705

A Bayesian Approach to Imitation in Reinforcement Learning

Bob Price and Craig Boutilier...................712

MULTIAGENT SYSTEMS

Detecting & Avoiding Interference Between Goals in Intelligent Agents

John Thangarajah, Lin Padgham, and Michael Winikoff............................721

Behavior Bounding: Toward Effective Comparisons of Agents & Humans

Scott A. Wallace and John E. Laird...............727

Characterization of Strategy/False-name Proof Combinatorial Auction Protocols: Price-oriented, Rationing-free Protocol

Makoto Yokoo...............................733

MULTIAGENT TRACKING

On Identifying and Managing Relationships in Multi-Agent Systems

Ronald Ashri, Michael Luck, and Mark d'Inverno . . . 743

OD1SET: On-line Distributed Session Tracing using Agents

Salvador Mandujano andArturo Galvdn.......... 749

NASH EQUILIBRIA

A Continuation Method for Nash Equilibria in Structured Games

Ben Blum, Christian R. Shelton, and Daphne Koller.............................. 757

Complexity Results about Nash Equilibria

Vincent Conitzer and Tuomas Sandholm.......... 765

Local-Effect Games

Kevin Leyton-Brown andMoshe Tennenholtz....... 772

NONMANIPULABILITY AND FAULT-TOLERANCE

Universal Voting Protocol Tweaks to Make Manipulation Hard

Vincent Conitzer and Tuomas Sandholm.......... 781

Probabilistically Survivable MASs

Sarit Kraus, V. S. Subrahmanian, and N. Cihan Tas............................... 789

Minimally intrusive negotiating agents for resource sharing

Fariba Sadri, Francesca Toni, and Paolo Torroni..... 796

NATURAL LANGUAGE

Extended Gloss Overlaps as a Measure of Semantic Relatedness

Satanjeev Banerjee and Ted Pedersen............. 805

Evaluating Coverage for Large Symbolic NLG Grammars

Charles B. Callaway......................... 811

Hierarchical Semantic Classification: Word Sense Disambiguation with World Knowledge

Massimiliano Ciaramita, Thomas Hofmann, and Mark Johnson.............................. 817

GRAEL: an agent-based evolutionary computing approach for natural language grammar development

Guy De Pauw.............................. 823

NONMONOTONIC REASONING

DEFAULT LOGIC

Outlier Detection Using Default Logic

Angiulli Fabrizio, Rachel Ben-Eliyahu-Zohary, and Luigi Palopoli.............................. 833

Ordering Default Theories

Chiaki Sakama............................. 839

LOGIC PROGRAMMING

Aggregate Functions in Disjunctive Logic Programming: Semantics, Complexity, and Implementation in DLV

Tina DelVArmi, Wolfgang Faber, Giuseppe Ielpa, Nicola Leone, and Gerald Pfeifer................847

On Tight Logic Programs and Yet Another Translation from Normal Logic Programs to Propositional Logic

Fangzhen Lin andjicheng Zhao.................853

On the Equivalence between Answer Sets and Models of Completion for Nested Logic Programs

Jia-Huai You, Li-Yan Yuan, and Mingyi Zhang.....859

NONMONOTONIC REASONING

Answer Set Optimization

Gerhard Brewka, Ilkka Niemela, and Miroslaw Truszczynski........................867

Weak Conditional Logics of Normality

James P. Delgrande...........................873

Recycling Computed Answers in Rewrite Systems for Abduction

Fangzhen Lin and Jia-Huai You.................879

ONTOLOGIES AND FOUNDATIONS

What is Artificial Intelligence? Psychometric AI as an Answer

Selmer Bringsjord and Bettina Schimanski.........887

Tucking RCC in Cycs Ontological Bed

Pierre Grenon...............................894

Integrity and Change in Modular Ontologies

Heiner Stuckenschmidt and Michel Klein..........900

PERCEPTION

Where is ...? Learning and Utilizing Motion Patterns of Persons with Mobile Robots

Grzegorz Cielniak, Maren Bennewitz, and Wolfram Burgard............................909

An Extension of the ICP Algorithm for Modeling Nonrigid Objects with Mobile Robots

Dirk H&hnel, Sebastian Thrun, and Wolfram Burgard............................915

People Tracking with Anonymous and ID-Sensors Using Rao-Blackwellised Particle Filters

Dirk Schulz, Dieter Fox, and Jeffrey Hightower......921

PLANNING

Factored Planning

EyalAmir and Barbara Engelhardt...............929

A Parametric Hierarchical Planner for Experimenting Abstraction Techniques

Giuliano Armano, Giancarlo Cherchi, and Eloisa Vargiu...............................936

On the application of least-commitment and heuristic search in temporal planning

Antonio Garrido and Eva Onaindia.............. 942

Resource Temporal Networks: Definition and Complexity

Philippe Laborie............................ 948

Generalizing GraphPlan by Formulating Planning as a CSP

Adriana Lopez and Fa hi em Bacchus.............. 954

In Defense of PDDL Axioms

Sylvie Thiibaux, Jorg Hoffmann, and Bernhard Nebel............................. 961

PROBABILISTIC INFERENCE

Optimal Time-Space Tradeoff in Probabilistic Inference

David Allen and Adnan Darwiche............... 969

Variable Resolution Particle Filter

Vandi Verma, Sebastian Thrun, and Reid Simmons.............................. 976

PROBABILISTIC INFERENCE: FIRST ORDER

First-order probabilistic inference

David Poole................................ 985

Dynamic Probabilistic Relational Models

Sumit Sanghai, Pedro Domingos, and Daniel Weld................................ 992

PROBABILISTIC PLANNING

ABSTRACTION, TRANSFER

Generalizing Plans to New Environments in Relational MDPs

Carlos Guestrin, Daphne Roller, Chris Gearhart, and Neal Kanodia.......................... 1003

SMDP Homomorphisms: An Algebraic Approach to Abstraction in Semi-Markov Decision Processes

Balaraman Ravindran and Andrew G. Barto...... 1011

PROBABILISTIC PLANNING

Covariant Policy Search

J. Andrew Bagnell and Jeff Schneider............ 1019

Point-based value iteration: An anytime algorithm for POMDPs

Joelle Pineau, Geoff Gordon, and Sebastian Thrun........................... 1025

QUALITATIVE REASONING

A New Look at the Semantics and Optimization Methods of CP-Networks

Ronen I. Brafman and Yannis Dimopoulos........ 1033

Categorizing classes of signals by means of fuzzy gradual rules

Sylvie Galichet, Didier Dubois, and Henri Prade . . . 1039

Gaussian Process Models of Spatial Aggregation Algorithms

Naren Ramakrishnan and Chris Bailey-Kellogg.....1045

Qualitatively Faithful Quantitative Prediction

Dorian Sue, Daniel Vladusic, and Ivan Bratko.....1052

REASONING ABOUT ACTIONS AND CHANGE

Compiling Control Knowledge into Preconditions for Planning in the Situation Calculus

Alfredo Gabaldon...........................1061

Action representation and partially observable planning using epistemic logic

Andreas Herzig Jerome Lang, and Pierre Marquis.............................1067

Causal Theories of Action: A Computational Core

Jerome Lang, Fangzhen Lin, and Pierre Marquis . . . 1073

Describing Additive Fluents in Action Language C+

Joohyung Lee and Vladimir Lifischitz.............1079

The Concurrent, Continuous FLUX

Yves Martin...............................1085

Reasoning about the Interaction of Knowledge, Time and Concurrent Actions in the Situation Calculus

Richard B. Scherl...........................1091

RESOURCE-BOUNDED REASONING

Definition and Complexity of Some Basic Metareasoning Problems

Vincent Conitzer and Tuomas Sandholm..........1099

Approximating Optimal Policies for Agents with Limited Execution Resources

Dmitri A. Dolgov and Edmund H. Durfee........1107

Belief, Awareness, and Two-Dimensional Logic

Hu Liu and Shier Ju........................1113

ROBOTICS

Non-Invasive Brain-Actuated Control of a Mobile Robot

Jose del R Milldn, Fridtric Renkens, Josep Mourino, and Wulfram Gerstner.......................1121

Exploring Unknown Environments with Mobile Robots using Coverage Maps

Cyrill Stachniss and Wolfram Burgard............1127

SIMULTANEOUS LOCALIZATION AND MAPPING

DP-SLAM: Fast, Robust Simultaneous Localization and Mapping Without Predetermined Landmarks

Austin Eliazar and Ronald Parr................ 1135

Consistent, Convergent, and Constant-Time SLAM

J.Leonard and P Newman................... 1143

FastSLAM 2.0: An Improved Particle Filtering Algorithm for Simultaneous Localization and Mapping that Provably Converges

Mike Montemerlo, Sebastian Thrun, Daphne Koller, and Ben Wegbreit........................... 1151

Thin Junction Tree Filters for Simultaneous Localization and Mapping

Mark A. Paskin............................ 1157

SATISFIABILITY

A Structure-Based Variable Ordering Heuristic for SAT

Jinbo Huang and Adnan Darwiche............. 1167

Backdoors To Typical Case Complexity

Ryan Williams, Carla P. Gomes, and Bart Selman.............................. 1173

Backbone Guided Local Search for Maximum Satisfiability

Weixiong Zhang, Ananda Rangan, and Moshe Looks.............................. 1179

SATISFIABILITY AND PHASE TRANSITIONS

Phase Transitions of Bounded Satisfiability Problems

Delbert D. Bailey and Phokion G Kolaitis........ 1187

Understanding the Power of Clause Learning

Paul Beame, Henry Kautz, and Ashish Sabharwal.......................... 1194

Phase Transitions of the Asymmetric Traveling Salesman

Weixiong Zhang............................ 1202

SCHEDULING

Contract Algorithms and Robots on Rays: Unifying Two Scheduling Problems

Daniel S. Bernstein, Lev Finkebtein, and Shlomo Zilberstein.......................... 1211

Maximizing Flexibility: A Retraction Heuristic for Oversubscribed Scheduling Problems

Laurence A. Kramer and Stephen E Smith........ 1218

Distributed Patient Scheduling in Hospitals

Poulussen, N R. Jennings, K. S. Decker, and

A. Heinzl................................ 1224

SEARCH

Faster Heuristic Search Algorithms for Planning with Uncertainty and Full Feedback

Blai Bonet and Hetor Geffner................. 1233

Comparing Best-First Search and Dynamic Programming for Optimal Multiple Sequence Alignment

Heath Hohwald, Ignacio Thayer, and Richard E Korf............................1239

Factored A* Search for Models over Sequences and Trees

Dan Klein and Christopher D. Manning.........1246

An Improved Algorithm for Optimal Bin Packing

Richard E Korf............................1252

Sparse-Memory Graph Search

Rong Zhou and Eric A. Hansen................ 1259

SPATIAL REASONING

Layered Mereotopology

Maureen Donnelly..........................1269

Reasoning about distances

Frank Whiter and Michael Zakharyaschev.........1275

TEMPORAL REASONING

Incremental Tractable Reasoning about Qualitative Temporal Constraints

Alfonso Gerevini............................ 1283

Tractable Pareto Optimization of Temporal Preferences

Lina Khatib, Paul Morris, Robert Morris, and Kristen Brent Venable........................ 1289

Automatic Video Interpretation: A Novel Algorithm for Temporal Scenario Recognition

Van-Thinh Vu, Francois Bremond, and Monique Thonnat..........................1295

USER MODELING

Corpus-based, Statistical Goal Recognition

Nate Blaylock and James Allen.................1303

A General Model for Online Probabilistic Plan Recognition

Hung H Bui.............................. 1309

VISION

Use of Off-line Dynamic Programming for Efficient Image Interpretation

Ramana Isukapalli and Russell Greiner...........1319

Switching Hypothesized Measurements: A Dynamic Model with Applications to Occlusion Adaptive Joint Tracking

Yang Wang, Tele Tan, and Kia-Fock Loe..........1326

POSTER PAPERS

AUTOMATED REASONING

Active Probing Strategies for Problem Diagnosis in Distributed Systems

Mark Brodie, Irina Rish, Sheng Ma, and Natalia Odintsova.......................... 1337

A Resolution Theorem for Algebraic Domains

Pascal Hitzler............................. 1339

A Novel Framework for Integrating Discrete Event System Control and Diagnosis

Gregory Provan............................ 1341

Assertion Application in Theorem Proving and Proof Planning

Quoc Bao Vo, Christoph Benzmuller, and Serge Autexier............................. 1343

CASE-BASED REASONING

Case Base Adaptation Using Solution-Space Metrics

Brian Knight and Fei Ling Woon............... 1347

Coverage-Optimized Retrieval

David McSherry........................... 1349

Explicit vs Implicit Profiling - A Case-Study in Electronic Programme Guides

Derry O'Sullivan, Barry Smyth, and David Wilson............................. 1351

CONSTRAINTS

A Simulated Annealing Approach to the Travelling Tournament Problem

A. Anagnostopoulos, L. Michel, P. Van Hentenryck, and Y Vergados............................ 1357

Grid-based SensorDCSP

R. Bejar, C. Domshlak, C. Fernandez, C. Gomes, B. Selman, and M. Valls..................... 1359

Dynamic Vehicle Routing with Stochastic Requests

Russell Bent and Pascal Van Hentenryck.......... 1362

Solving Finite Domain Constraint Hierarchies by Local Consistency and Tree Search

Stefano Bistarelli, Philippe Codognet, H K C Hui, and J. H.M.Lee............... 1364

Splitting the atom: A new approach to Neighbourhood Interchangeability in Constraint Satisfaction Problems

James Bowen and Chavalit Likiwivatanavong..... 1366

Efficient Representation of Adhoc Constraints

KeniI C. K Cheng, jimmy H. M. Lee, and Peter J. Stuckey............................ 1368

Propagation Redundancy for Permutation Channels

C W Choi, J. H. M. Lee, and P J. Stuckey....... 1370

Channeling Constraints and Value Ordering in the Quasi Group Completion Problem

Ivan Dotu, Alvaro del Val, and Manuel Cebrian. ... 1372

Making the Breakout Algorithm Complete Using Systematic Search

Carlos Eisenberg and Boi Faltings...............1374

Sampling Combinatorial Spaces Using Biased Random Walks

Jordan Erenrich and Bart Selman...............1376

Finite Domain Constraint Solver Learning

Arnaud Lallouet, Thi-Bich-Hanh Dao, Andrei Legtchenko, and AbdelAli Ed-Dbali........1379

Applying interchangeability techniques to the distributed breakout algorithm

Adrian Petcu and Boi Faltings.................1381

EVOC: A Music Generating System using Genetic Algorithms

Timothy Weale and Jennifer Seitzer..............1383

Temporal Reasoning with Preferences and Uncertainty

N Yorke-Smith, K B. Venable, and F Rossi.......1385

KNOWLEDGE REPRESENTATION

BDIO; Obligations and the Specification of Agent Behavior

Jan Broersen, Mehdi Dastani, and Leendert van der Torre.......................1389

Prolegomenon to a Theory of Conservative Belief Revision

James P Delgrande, Abhaya C. Nayak, and Maurice Pagnucco...........................1391

Extending DTGOLOG with Options

A. Ferrein, Ch. Fritz, and G. Lakemeyer..........1394

Indirect and Conditional Sensing in the Event Calculus

Jeremy Forth............................... 1396

Proactive Dialogue for Interactive Knowledge Capture

Jihie Kim and Yolanda Gil....................1398

Coherence of Laws

Rex Kwok, Norman Y Foo, and Abhaya C Nayak...........................1400

An Epistemic Logic for Arbitration (Extended Abstract)

Churn-Jung Liau...........................1402

Constructing utility models from observed negotiation actions

Angelo Restijicar and Peter Haddawy............1404

Engineering a complex ontology with time

Jorge Santos and Steffen Staab..................1406

A Logic-based Algorithm for Image Sequence Interpretation and Anchoring

Paulo Santos and Murray Shanahan.............1408

INFORMATION RETRIEVAL AND DATA MINING

Learning Consumer Photo Categories for Semantic Retrieval

Joo-Hwee Lim and Jesse S. Jin................. 1413

Intelligent Multimodal Stream Processing

Mark Maybury............................ 1415

Collaborative Web Search

Barry Smyth, Evelyn Balfe, Peter Briggs, Maurice Coyle, and Jill Freyne................. 1417

A Statistical Model for Flexible String Similarity

Atsuhiro Takasu............................ 1420

Mining Video Associations for Efficient Database Management

Xingquan Zhu and Xindong Wu............... 1422

MACHINE LEARNING

A Learning Algorithm for Localizing People Based on Wireless Signal Strength that Uses Labeled and Unlabeled Data

Mary Berna, Brennan Sellner, Brad Lisien, Sebastian Thrun, Geoffrey Gordon, and Frank Pfenning............................ 1427

Learning to Compete in Heterogeneous Web Search Environments

Rinat Khoussainov and Nicholas Kushmerick...... 1429

Approximate Policy Iteration using Large-Margin Classifiers

Michail G. Lagoudakis and Ronald Parr......... 1432

Active Learning with Ensembles for Image Classification

H. Liu, A. Mandvikar, P. Foschi, and K Torkkola............................... 1435

Item Selection Strategies for Collaborative Filtering

Rachael Rafter and Barry Smyth............... 1437

Modular self-organization for a long-living autonomous agent

Bruno Scherrer............................. 1440

Towards a Theoretical Framework for Ensemble Classification

Alexander K. Seewald....................... 1443

Multiple-Goal Reinforcement Learning with Modular Sarsa(O)

Nathan Sprague and Dana Ballard............. 1445

Integrating Background Knowledge Into Text Classification

Sarah Zelikovitz and Haym Hirsh.............. 1448

Parametric Distance Metric Learning with Label Information

Zhihua Zhang, James T Kwok, and Dit-Yan Yeung............................. 1450

MULTIAGENTS

Network Meta-Reasoning for Information Assurance in Mobile Agent Systems

Donovan Artz, Max Peysakhov, and William Regli..............................1455

Towards Cooperative Negotiation for Decentralized Resource Allocation in Autonomic Computing Systems

Craig Boutilier, Rajarshi Das, Jeffrey O. Kephart, and William E. Walsh.......................1458

A Formalization of Equilibria for Multiagent Planning

Michael Bowling, Rune Jensen, and Manuela Veloso............................. 1460

Bidding Marginal Utility in Simultaneous Auctions

Amy Greenwald............................1463

NoA - A Normative Agent Architecture

Martin J. Kollingbaum and Timothy). Norman. . . . 1465

A heuristic model for concurrent bi-lateral negotiations in incomplete information settings

Thuc Duong Nguyen and Nicholas R. Jennings.....1467

Imitation Learning of Team-play in Multiagent System based on Hidden Markov Modeling

Itsuki Noda..............................1470

Virtual World as Interface for Human-Robot Interaction

Eric Normand and Sheila Tejada...............1473

Learning Algorithms for Software Agents in Uncertain and Untrusted Market Environments

Thomas Tran and Robin Cohen................1475

A Multi-Agent Computational Linguistic Approach to Speech Recognition

Michael Walsh, Robert Kelly, Gregory M. P O'Hare, Julie Carson-Berndsen, and Tarek Abu-Amer.......1477

NATURAL LANGUAGE

The Knowledge Required to Interpret Noun Compounds

James Fan, Ken Barker, and Bruce Porter.........1483

Improving Word Sense Disambiguation in Lexical Chaining

Michel Galley and Kathleen McKeown...........1486

A Revised Algorithm for Latent Semantic Analysis

Xiangen Hu, Zhiqiang Cai, Max Louwerse, Andrew Olney, Phanni Penumatsa, Art Graesser, andTRG............ 1489

Identifying Synonyms among Distributionally Similar Words

Dekang Lin, Shaojun Zhao, Lijuan Qin, and MingZhou................................1492

A Logic Prover for Text Processing

Dan Moldovan and Christine Clark.............1494

Inducing criteria for lexicalization parts of speech using the Cyc KB

Tom O'Hara, Michael Witbrock, Bjern Aldag, Stefano Bertolo, Nancy Salay, Jon Curtis, and Kathy Panton................ 1496

NEURAL NETWORKS

Neural Executive Attentional Control in Robots

Jason Garforth, Sue Mcliale, and Anthony Meehan........................... 1501

Boosting Face Identification in Airports

Liu Jiang Jimmy and Kia-Fock Loe............. 1503

Action Selection for Single- and Multi-Robot Tasks Using Cooperative Extended Kohonen Maps

Kian Hsiang Low, Wee Kheng Leow, and Marcelo H. Ang, Jr.......................... 1505

Artificial Neural Network for Sequence Learning

Sorin Moga and Philippe Gaussier.............. 1507

PLANNING

Comparison of Different Grid Abstractions for Pathfinding on Maps

Yngvi Bjornsson, Markus Enzenberger, Robert Holte, Jonathan Schaejfer, and Peter Yap............... 1511

Multiagent Planning with Partially Ordered Temporal Plans

Michael Brenner........................... 1513

Recognizing Plan/Goal Abandonment

Christopher W Geib and Robert P Goldman...... 1515

Automated Generation of Understandable Contingency Plans

Max Horstmann and Shlomo Zilberstein......... 1518

A Planning Algorithm for Predictive State Representations

Masoumeh T. Izadi and Doina Precup........... 1520

Parallelizing State Space Plans Online

Romeo Sanchez Nigenda and Subbarao Kambhampati..................... 1522

A lookahead strategy for solving large planning problems

Vincent Vidal............................. 1524

Using Available Memory to Transform Graphplans Search

Terry Zimmerman and Subbarao Kambhampati . . . 1526

SEARCH

Lookahead Pathologies for Single Agent Search

Vadim Bulitko, Lihong Li, Russ Greiner, and Ilya Levner............................... 1531

Real-Time Strategy Games: A New AI Research Challenge

Michael Buro.............................. 1534

Multiple Agents Moving Target Search

Mark Goldenberg, Alexander Kovarsky, Xiaomeng Wu, and Jonathan Schaejfer.......................1536

Delayed Duplicate Detection: Extended Abstract

Richard E. Korf............................1539

A Portfolio Approach to Algorithm Selection

Kevin Leyton-Brown, Eugene Nudelman, Galen Andrew, Jim McFadden, and Yoav Shoham. . . 1542

A New Node Centroid Algorithm for Bandwidth Minimization

Andrew Lim, Brian Rodrigues, and Fei Xiao.......1544

Combining Two Local Search Approaches to Hypergraph Partitioning

Arathi Ramani and Igor Markov...............1546

VISION AND ROBOTICS

A New Content Based Image Retrieval Method Based on a Sketch-Driven Interpretation of Line Segments

Marco Anelli, Alessandro Micarelli, and Enver Sangineto............................1551

Towards Pervasive Robotics

Artur M. Arsenio........................... 1553

A Visual-Sensor Model for Mobile Robot Localisation

Matthias Fichtner and Axel GroBmann...........1555

Improving Speech Recognition on a Mobile Robot Platform through the use of Top-Down Visual Queues

Robert J. Ross, R. P S. O'Donoghue, and G M. P O'Hare............................1557

Comparing image-based localization methods

Robert Sim and Gregory Dudek................1560

Quantum Computation and Image Processing: New Trends in Artificial Intelligence

S. E. Venegas-Andraca and S. Bose..............1563

INVITED SPEAKERS

Corpus-Based Knowledge Representation

Alon Y. Halevy andjayant Madhavan........... 1567

Challenges in Web Search Engines

Monika R. Henzinger, Rajeev Motwani, and Craig Silverstein............................1573

Deploying Information Agents on the Web

Craig A. Knoblock..........................1580

Constraint Satisfaction, Databases, and Logic

Phokion G Kolaitis.........................1587

Web Intelligence (WI): What Makes Wisdom Web}

Jiming Liu................................1596

Self-reconfiguring Robots: Successes and Challenges

Daniela Rus...............................1602

Automated Verification: Graphs, Logic, and Automata

Moshe Y Vardi.............................1603

Automated Reasoning: Past Story and New Trends

Andrei Voronkov........................... 1607

Automatically Personalizing User Interfaces

Daniel S. Weld, Corin Anderson, Pedro Domingos, Oren Etzioni, Krzysztof Gajos, Tessa Lau, and Steve Wolfinan........... 1613

Intelligent Systems in Travel and Tourism

Hannes Werthner........................... 1620

INTELLIGENT SYSTEMS DEMONSTRATIONS

Writers Aid: Using a Planner in a Collaborative Interface

Tamara Babaian, Barbara J. Grosz, and Stuart M. Shieber.......................... 1629

Sensible Agent Technology Improving Coordination and Communication in Biosurveillance Domains

K S Barber, D. Faith, K Fullam, T Graser, D. C Han, J. Jeong, J. Kim, D. Lam, R. McKay, M. Pal, j Park, and M. Vanzin................ 1631

GSTP: A Temporal Reasoning System Supporting Multi-Granularity Temporal Constraints

Claudio Bettini, Sergio Mascetti, and Vincenzo Pupillo........................... 1633

Comparing Different Cognitive Paradigms with a Virtual Laboratory

Carlos Gershenson.......................... 1635

Towards domain-independent, task-oriented, conversational adequacy

Darsana P. Josyula, Michael L. Anderson, and Don Perlis................................1637

Broadcast News Navigator (BNN) Demonstration

Mark Maybury.............................1639

Demonstration: Liaison Agents for Distributed Space Operations

D. Schreckenghost, P. Bonasso, D. Kortenkamp, C. Martin, T. Milam, and C. Thronesbery........1641

Interactive Spoken Simulation Control and Conversational Tutoring

Karl Schultz, Brady Clark, Elizabeth Owen Bratt, Stanley Peters, Heather Pon-Barry, Pucktada Treeratpituk, and Zack Thomsen-Gray. . . . 1643

TAGA: Travel Market Framework in Agentcities

Youyong Zou, Tim Finin, Li Ding, Harry Chen, and Rong Pan..............................1645

COMPUTERS AND THOUGHT AWARD PAPER

Making Markets and Democracy Work: A Story of Incentives and Computing

Tuomas Sandholm.......................... 1649

Author Index  .................................1673