Tutorial Programme

The tutorials will be held at the University of Edinburgh.

Tutorial Chair: Robert Givan

Click on the tutorial titles below to see details.

Saturday 30 July
0900 - 1230
T1   Grammar Induction: Techniques and Applications Adam Ferguson G19
T2   Automated Reasoning in First-Order Logic Adam Ferguson G17
T3   Techniques for Computing and Using Bounds for Combinatorial Optimization Problems Adam Ferguson G13
T4   Reductions for Machine Learning Adam Ferguson G10
1400 - 1730
T5   Constraint Processing Adam Ferguson G17
T6   Representation, Inference and Learning in Relational Probabilistic Languages Adam Ferguson G10
T7   Planning: Techniques for Efficient State-Space Traversal Adam Ferguson G13
T8   Preference Models and Applications Adam Ferguson G19
0900 - 1730
T9   Representation and Learning in Robots and Animals (day 1 of 2) David Hume Tower Faculty Room North

Sunday 31 July
0900 - 1730
T9   Representation and Learning in Robots and Animals (day 2 of 2) David Hume Tower Faculty Room North
T10   Principles of AI Problem Solving David Hume Tower Faculty Room South
0900 - 1230
T11   Text Analytics: Theory and Practice Adam Ferguson G19
T12   Multiagent Planning: a Survey of Research and Applications Adam Ferguson G10
T13   Models of Argumentation and Dialogue in AI Adam Ferguson G13
1400 - 1730
T14   Collaborative Multiagent Systems Adam Ferguson G10
T15   Modelling Language Origins and Evolution Adam Ferguson G13
T16   Market Clearing Algorithms Adam Ferguson G17
T17   Distributed Constraint Reasoning Adam Ferguson G19


Grammar Induction: Techniques and Applications

(Saturday 30 July - morning)

Colin de la Higuera & Tim Oates

The field of grammar induction is concerned with inferring grammatical models of the generative structure underlying sequential data. Both the theory and practice of grammar induction are well-developed and have found applications in a wide variety of domains: in bio-informatics, context-free grammars capture the hierarchical structure of the nucleotide sequences that comprise proteins; in natural language processing and speech recognition, stochastic grammars are used for language modeling. Other applications include wrapper induction for information extraction from documents marked up with XML, recognition and generation of musical scores, and inductive logic programming. This tutorial will provide an introduction to the theory, practice, and open problems in grammar induction. Among the topics that will be covered are models of learnability, inference of finite state automata and context-free grammars, learning from trees and structured data, stochastic finite automata and grammars, inference techniques, positive and negative learnability results, and applications.

[Tutorial web page]


Automated Reasoning in First-Order Logic

(Saturday 30 July - morning)

Andrei Voronkov

In the last fifteen years the area of automated reasoning in first-order logic witnessed several exciting developments. A new theory of inference systems with redundancy has been developed. New implementation techniques and heuristics have evolved. Systems based on the new theory and implementation techniques outperform the previous generation systems, often by orders of magnitude. New applications appeared in connection with the rapid growth in the use and acceptance of formal methods and development of ontologies and knowledge bases.

The tutorial is intended to overview the state-of-the-art automated reasoning, including theory, implementation, applications, and the use of theorem provers. Presentation will be accompanied by demos of the theorem prover Vampire, the winner of several world cups in theorem proving. For example, we will show how the modern theory influenced the design of Vampire and options available in it and how Vampire can be used for answering queries to large knowledge bases.

[Tutorial web page]


Techniques for Computing and Using Bounds for Combinatorial Optimization Problems

(Saturday 30 July - morning)

Sharlee Climer & Weixiong Zhang

Branch-and-bound is a search paradigm which uses bounds to prune large portions of a search space without compromising optimality. This paradigm is heavily utilized in AI, prompting substantial research of the derivation of bounds. We reflect on the history of the use of bounds and observe that, until recently, the focus has been on bounds derived from relaxations of constraints. We demonstrate how overlooked bounds can be systematically derived by tightening constraints, adding/removing variables, and modifying the objective function. Then a formalization of the use of bounds as a two-step procedure is presented. The use of this framework is conducive to eliciting methods that go beyond search-tree pruning. We demonstrate the use of this technique for devising novel search strategies and apply these strategies to several optimization problems.

This tutorial is aimed at the general AI audience. Familiarity with basic concepts of combinatorial optimization is desirable but not essential.


Reductions for Machine Learning

(Saturday 30 July - morning)

Alina Beygelzimer, John Langford, & Bianca Zadrozny

Reductions allow us to reuse classification algorithms in new settings such as multiclass classification, cost sensitive classification, and reinforcement learning. This approach to solving prediction problems can often yield comparable or superior performance with minimal (human) effort. We present several algorithms exhibiting this design pattern along with the mathematical tools used to analyze and develop new reduction algorithms.

At the end of this tutorial, you should understand several reduction algorithms, how to use them and how to analyze and optimize them.

[Tutorial web page]


Constraint Processing

(Saturday 30 July - afternoon)

Pedro Meseguer & Thomas Schiex

This tutorial will provide participants with a firm understanding of the essential techniques for constraint processing. Presenters will summarize the huge amount of results published in the last years in a few lines of research, allowing attenders to get a clear and structured view of the field. The presentation will be focused on the algorithmic methods for constraint processing, without forgetting theoretical aspects and successful constraint applications. Algorithms will be described in terms of search, inference and hybrids.

The tutorial will cover both types of constraint processing: hard constraints (classical constraint satisfaction) and soft constraints (constrained optimization). Modelling guidelines and environments for constraint processing will be discussed. To know more after the tutorial, a detailed list of references will be presented.


Representation, Inference and Learning in Relational Probabilistic Languages

(Saturday 30 July - afternoon)

Lise Getoor & Avi Pfeffer

Recently there has been a surge of interest in methods which combine first-order and relational languages with probabilistic models. In this tutorial, we will survey several recent approaches. We will describe logic and rule-based approaches (such as Probabilistic Logic Programming, Bayesian Logic Programs, and Stochastic Logic Programs), frame and object-oriented approaches (such as Probabilistic Relational Models, Markov Relational Networks and Probabilistic Entity Relationship Models), and methods based on functional programming (such as Stochastic Lambda Calculus and IBAL).

We will describe the representations and representational issues, beginning with attribute uncertainty, and then describing more complex types of uncertainty such as structural uncertainty and identity uncertainty. We will describe several inference algorithms and learning techniques, including statistical approaches to parameter and structure learning and inductive logic programming approaches. We will conclude by discussing a number of application areas that can be modeled, for instance collaborative filtering, entity resolution, information extraction, social network analysis, and web mining.

[Tutorial web page]


Planning: Techniques for Efficient State-Space Traversal

(Saturday 30 July - afternoon)

Jussi Rintanen

During the last decade a number of breakthroughs have lifted the efficiency of domain-independent planning to a level required in many challenging applications. The tutorial presents the most important approaches to state space traversal as applied in algorithms for classical (deterministic) planning and in implementations of algorithms for more general forms of planning, including techniques based on propositional satisfiability testing, heuristic state-space search, and on logic-based data structures like binary decision diagrams.

The presentation is based on general and uniform concepts that allow the description of the most central notions concisely and makes the essential differences and similarities between the different approaches more apparent. Unlike in most research papers which use restricted STRIPS operators, the presentation is based on an expressive language similar to ADL/PDDL used by many recent planner implementations.

[Tutorial web page]


Preference Models and Applications

(Saturday 30 July - afternoon)

Ronen Brafman, Jon Doyle, Ulrich Junker, & Pearl Pu

Explicit preference modelling provides declarative means for choosing among alternatives, including alternative solutions of problems to solve, answers of data-base queries, decisions of a computational agent, or plans of a robot. Explicit preference models allow finer-grained control over computation and new ways of interactivity, and therefore provide more satisfactory results and outcomes than other choice mechanisms.

The tutorial addresses a broad AI audience, giving an overview on preferences in four parts starting with traditional decision theory and ending with highly advanced issues:

  1. Foundations: from economic preferences to preferences for intelligence by analysing roles, representations, and structure.
  2. Formalisms: CP-nets and other AI-based formalisms for preference handling.
  3. Algorithms for preference handling and their applications to diagnosis, configuration, constraint programming, scheduling and other problem solving tasks.
  4. Elicitation of User Preference Models: performance analysis of online decision guides and preference-based search tools, and best practice principles for constructing interfaces for preference elicitation.

[Tutorial web page]


Principles of AI Problem Solving

(Sunday 31 July - all day)

Adnan Darwiche, Rina Dechter, & Hector Geffner

Most of the AI techniques that have been found useful in a wide range of areas including Search, Planning, SAT, Constraints, Bayesian Neworks, and Markov Decision Processes, can be understood along a few dimensions, and are expressions of a small core of concepts and principles. In this tutorial, we articulate this basic core of ideas aiming at a coherent, comprehensive, and modern view of AI Problem Solving.

We focus on optimal problem solving over various state and variable-based (graphical) models used in AI, and classify current techniques in two classes: those based on search and inference, and those based on pure inference and no search. In the former class, we analyze the notions of branching and pruning (either with lower bounds or constraint propagation), along with the notions of learning (in both SAT/CSPs and State Models), decomposition, and caching. In the latter class, we consider the concepts of variable elimination, join tree decomposition, and compilation. We also analyze the relation among these notions, their time and space complexity, and how they are currently used for solving various tasks of interest in AI.

[Tutorial web page]


Text Analytics: Theory and Practice

(Sunday 31 July - morning)

Ronen Feldman

The information age has made it easy to store large amounts of data. The proliferation of documents available on the Web, on corporate intranets, on news wires, and elsewhere is overwhelming. However, while the amount of data available to us is constantly increasing, our ability to absorb and process this information remains constant. Search engines only exacerbate the problem by making more and more documents available in a matter of a few key strokes. Text Analytics is a new and exciting research area that tries to solve the information overload problem by using techniques from data mining, machine learning, NLP, IR and knowledge management. Text analytics involves the preprocessing of document collections (text categorization, information extraction, term extraction), the storage of the intermediate representations, the techniques to analyze these intermediate representations (distribution analysis, clustering, trend analysis, association rules etc) and visualization of the results.

In this tutorial we will present the general theory of Text analytics and will demonstrate several systems that use these principles to enable interactive exploration of large textual collections. We will present a general architecture for text analytics and will outline the algorithms and data structures behind the systems. Special emphasis will be given to efficient algorithms for very large document collections, tools for visualizing such document collections, the use of intelligent agents to perform text analytics on the internet, and the use information extraction to better capture the major themes of the documents. The tutorial will cover the state of the art in this rapidly growing area of research. Several real world applications of text analytics will be presented.


Multiagent Planning: a Survey of Research and Applications

(Sunday 31 July - morning)

Bradley J Clement and Keith S Decker

Multiagent planning is concerned with planning by (and for) multiple agents. It can involve agents planning for a common goal, an agent coordinating the plans or planning of others, or agents refining their own plans while negotiating over tasks or resources. Distributed continual planning addresses these problems when further complicated with interleaved execution. More than ever industry, space, and the military are seeking systems that can solve these problems.

This tutorial will describe variations of the multiagent planning problem, discuss issues in the applicability and design of multiagent planning systems, and describe some real-world multiagent planning problems. We will also review the history of research contributions to this sub-field and describe frameworks and systems such as Distributed NOAH, GPGP, DSIPE, and SHAC. In addition, we will describe open research issues in multiagent planning and its overlap and relation to other fields, such as market-based AI and game theory.

[Tutorial web page]


Models of Argumentation and Dialogue in AI

(Sunday 31 July - morning)

Trevor J M Bench-Capon & Paul E Dunne

In many areas of human reasoning, such as law, ethics, medicine, the social sciences, proof is not possible, and so instead rationality must be based on some more or less persuasive argument. Argumentation has long been of interest to informal logicians, but increasingly attempts are being made to make the notions involved sufficiently precise to be amenable to embodiment in computer systems. Additionally, argumentation can be modelled as a dialogue between supporters and opponents of the proposition under consideration. Both practical reasoning and dialogue have particular significance for multi-agent systems.

In this tutorial we will look at the characteristics of argument that distinguish it from proof; at ways in which a formal framework for reasoning about systems of argument can be provided; at dialogues based on such frameworks; at representations of the structure of individual arguments; and at some example applications of these


Collaborative Multiagent Systems

(Sunday 31 July - afternoon)

Barbara Grosz, Charles Ortiz, & Milind Tambe

Collaborative agent systems are critical in a vast range of applications, in virtual environments for training and education, in improving human-computer interaction and organizational productivity, in applications in disaster rescue, space, military, and other spheres. Such collaborative systems are within reach thanks to progress in our understanding of rationality, both collective and individual. This tutorial will describe the major theoretical advances that can support principled designs and analyses of such systems as well as describe implementations based on those theories. The tutorial will begin with an overview of rationality: what it means for an agent to be rational and how this can be reflected in agent designs. This will include a brief review of models of mental state as well as rational agent architectures, emphasizing considerations of resource-boundedness and the ways this affects formalizations and system designs.


Modelling Language Origins and Evolution

(Sunday 31 July - afternoon)

Bart de Boer, Paul Vogt, & Tony Belpaeme

Evolutionary Linguistics is a new and rapidly growing field that has emerged from the field of artificial intelligence and that is concerned with modelling the origins and evolution of language. It addresses questions such as the origins of grammar, the prerequisites for human language, and origins of symbolic communication. This tutorial offers an introduction for artificial intelligence researchers who are new to evolutionary linguistics and is aimed at understanding the field and helping them set up computational experiments that address open issues. We do this by presenting a thorough overview of the field and by discussing how established AI techniques can be used to investigate the evolution of language. To illustrate this we present a number of case studies. In addition, we aim to provide suggestions of how to disseminate the research to a multidisciplinary audience, which often include linguists, anthropologists, archeologists, psychologists and biologists.

[Tutorial web page]


Market Clearing Algorithms

(Sunday 31 July - afternoon)

Tuomas Sandholm

Markets are important mechanisms for allocating goods, services, tasks, and resources among multiple agents, be they human or software. The market clearing problem is that of deciding how to allocate the items among the agents. The last four years have witnessed a leap of improvement in market clearing algorithms both for traditional market designs and entirely new market designs enabled by advanced clearing technology. This tutorial covers the computational implications of different market designs and presents algorithms for clearing markets optimally and approximately. Auctions (one seller, multiple buyers), reverse auctions (one buyer, multiple sellers), and exchanges (multiple buyers and multiple sellers) are covered. Both theoretical and experimental results are presented. Multi-item and multi-unit markets will be a key focus. Computational implications of different classes of side constraints will be presented. Bid types covered include price-quantity bids, different shapes of supply/demand curves, and package bids. Methods for selective incremental preference elicitation for combinatorial markets are presented, with which the market can be cleared optimally using only a small portion of the agents' preferences as input.

A basic understanding of algorithms, search, and NP-completeness is necessary. No background on markets is assumed.


Distributed Constraint Reasoning

(Sunday 31 July - afternoon)

Joerg Denzinger, Marius Silaghi, & Makoto Yokoo

We can expect that some software agents would work on our behalf, representing our interests and defending our privacy. A principled approach to the achievement of this dream is proposed by the Distributed Constraint Reasoning community which offers a general framework and powerful competitive techniques to approach these important applications. We will introduce the two major approach families, secure multi-party computations and search-based algorithms. This tutorial will provide an unified view on Distributed Constraint Reasoning, introducing distributed constraint reasoning systems as semi-cooperative multi-agent systems and concentrating on the privacy, communication and organization requirements of such systems. The general ideas behind the known distributed constraint reasoning systems are presented within this multi-agent framework. For each approach, the requirements, limitations, advantages and disadvantages of the different categories will be discussed.

[Tutorial web page]

Representation and Learning in Robots and Animals

(Saturday 30 July & Sunday 31 July - 2 days)

Aaron Sloman (organiser)

A two day advanced tutorial supported by the European Commission's Cognitive Systems initiative, at which tutorials will be presented by seven leading researchers on problems of learning and representation in integrated natural and artificial systems combining multiple functions using different forms of representation and learning. The presentations will illustrate the state of the art and unsolved problems. The tutorial will end with a two hour panel discussion on what the major unsolved problems are and how we can make progress towards solving them.

[Tutorial web page]


Please send inquiries regarding the IJCAI-05 tutorial programme to:

Bob Givan
School of Electrical and Computer Engineering
Purdue University, West Lafayette, Indiana 47907

Information for Tutorial Organisers (was: call for proposals)