IJCAI-03 Tutorials

The IJCAI tutorials program for 2003 features one invited tutorial and 20 four-hour tutorials, each covering a concentrated technical topic of current or emerging interest. Tutorials will be presented by experienced researchers and practicioners who are experts in the correspondig subject area. A separate registration fee applies to each four-hour tutorial. The invited tutorial is open to all registrants.

Sunday, August 10
	9:00 am - 1:00 pm		2:00 pm - 6:00 pm
	(SA1) AI Techniques for Personalized Recomendation. Joseph A. Konstan and John Riedl and Anthony Jameson		(SP1) Inmunological Computation - A new Paradigm in AI. Dipankar Dasgupta and Jonathan Timmis
	(SA2) Stochastic Search Algorithms. Holger H. Hoos and Thomas Stützle		(SP2) Genetic Algorithms in Search and AI. Darrell Whitley
	(SA3) Multiagent Learning: A Game Theoretic Perspective. Michael Bowling and Michael L. Littman		(SP3) Distributed Constraint Reasoning. Marius C. Silaghi, Jörg Denzinger, and Makoto Yokoo
	(SA4) Behavior-Based Programming of Robots and Multi-Robot Teams. Tucker Balch		(SP4) The State of the Art in Ant Robotics. Sven Koenig, Israel Wagner, Andrew Russell, Richard Vaughan, and David Payton
	(SA5) Ontologies: Representation, Engineering and Applications. Raphael Volz and Andreas Abecker		(SP5) Ontology-Based Information Integration. Ubbo Visser, Heiner Stuckenschmidt, and Holger Wache

Monday, August 11
	9:00 am - 1:00 pm		2:00 pm - 6:00 pm
	(MA1) Market Clearing Algorithms. Tuomas Sandholm		(MP1) Cancelled
	(MA2) SAT Beyond Propositional Satisfiability. Roberto Sebastiani		(MP2) Foundations of Constraint Satisfaction. Roman Barták
	(MA3) Web Services and Beyond. Munindar P. Singh and Michael N. Huhns		(MP3) Multi-Agent Modeling of Grounded Language Evolution. Luc Steels
	(MA4) Multiagent and Agent-Human Teamwork: Theory and Practice. Milind Tambe		(MP4) Recent developments in Qualitative Spatial and Temporal Reasoning. Frank Anger, Hans Guesgen, and Gerard Ligozat
	(MA5) Resource-Bounded and Time-Critical Reasoning. Lloyd Greenwald and Shlomo Zilberstein		(MP5) Case Based Reasoning for Industrial Knowledge Management. Ralph Bergmann and Mehmet H. Göker

Invited tutorial: Wednesday, August 13
	2:00 pm - 4:00 pm Intelligent Information Integration Maurizio Lenzerini Information integration is the problem of combining information residing at different sources, and providing the user with a unified view of these information. The problem of designing information integration systems is important in many current applications and contexts, e.g., the Semantic Web, and is characterized by a number of issues that are interesting both from the point of view of database research, and from the point of view of artificial intelligence.		An information integration system requires powerful languages for describing contents of information sources, and for specifying mappings between different sources. It also requires reasoning mechanisms both for the maintenance of the systems, and for answering queries posed to the integrated representation. It follows that, among the various areas of artificial intelligence, research on knowledge representation and reasoning is relevant to information integration. In this tutorial, special attention will be devoted to the following aspects: modeling an information integration application, including representing mappings between sources, processing queries posed to the integrated representation, and dealing with inconsistent information coming from independent sources.

Sunday, August 10

(SA1) AI Techniques for Personalized Recommendation John Riedl, Joseph Konstan, and Anthony Jameson

Personalized recommendation of products, documents, and collaborators has become an important way of meeting user needs in commerce, information provision, and community services, whether on the web, through mobile interfaces, or through traditional desktop interfaces. This tutorial first reviews the types of personalized recommendation that are being used commercially and in research systems. It then systematically presents and compares the underlying AI techniques, including recent variants and extensions of collaborative filtering, demographic and case-based approaches, decision-theoretic methods, methods based on the implicit or explicit elicitation of preferences, and various types of hybrid method. The techniques are discussed within a general integrative framework that allows participants to see how techniques can be selected and combined for particular applications. The presentation refers to concrete examples involving either commercially deployed systems or influential research prototypes. Special attention is paid to the implications of the practical aspects of deployment contexts--for example, issues of privacy and transparency--for the choice of AI recommendation techniques. The tutorial presupposes a general knowledge of AI. Some previous familiarity with issues of personalized recommendation is desirable but not essential.

Jonh Riedl	John Riedl and Joe Konstan are Associate Professors in the Department of Computer Science and Engineering at the University of Minnesota. John Riedl co-founded the pioneering GroupLens recommender system project with Paul Resnick in 1992, and he and Joe Konstan have been co-directing the project since 1995. Riedl and Konstan also cofounded Net Perceptions, a company that has commercialized the results of their research since 1996. They have published broadly in the area of recommender systems.	Joe Konstan
Anthony Jameson	Anthony Jameson is a principal researcher at DFKI (the German Research Center for Artificial Intelligence) and adjunct professor of computer science at the International University in Germany. He has published widely on personalized recommendation and user adaptation since the early 1980s. After having presented related tutorials in the conference series CHI, CSCW, EC, CHI, IJCAI, IUI, and UM, the three presenters first joined forces with a full-day version of the present tutorial at AAAI-02.

(SA2) Stochastic Search Algorithms Holger H. Hoos and Thomas Stützle

Stochastic search algorithms have been shown to outperform their deterministic counterparts in a number of interesting application domains. They are becoming increasingly important and popular for solving computationally hard combinatorial problems from various domains of AI and Operations Research, such as planning, scheduling, constraint satisfaction, satisfiability, or combinatorial auctions. In this tutorial we will introduce stochastic search algorithms and characterise them as instances of the more general class of Las Vegas algorithms. We will cover local search algorithms, including stochastic hill-climbing, simulated annealing, tabu search, evolutionary algorithms, and ant colony optimization, as well as randomised systematic search algorithms. For exemplifying these algorithms, we will mainly use the Satisfiability Problem in Propositional Logic (SAT) and the Travelling Salesperson Problem (TSP), which both play a central role in the design, implementation, and analysis of algorithmic ideas. We will also address the empirical analysis of Las Vegas algorithms and present case studies demonstrating the successful application of stochastic search algorithms to various problem domains. Prerequisite knowledge: The attendees should have an interest in computationally hard combinatorial problems. Basic knowledge in standard AI search problems as well as a basic knowledge of search methods would be an advantage but are not necessary prerequisites.
See http://www.cs.ubc.ca/~hoos/IJCAI-03-T/

Holger Hoos

Holger H. Hoos is an Assistant Professor at the Computer Science Department of the University of British Columbia (Canada), where he is a co-founder of the Bioinformatics, Empirical & Theoretical Algorithmics Laboratory (BETA-Lab) and a member of the Laboratory for Computational Intelligence (LCI). He received his PhD from the Computer Science Department at TU Darmstadt (Germany). His research interests include empirical algorithmics, artificial intelligence, bioinformatics, and computer music.

Thomas Stützle

Thomas Stützle is an Assistant Professor at the Computer Science Department of Darmstadt University of Technology, where he is local coordinator of the Metaheuristics Network. He received his PhD from the Computer Science Department at TU Darmstadt (Germany). His research interests include combinatorial optimization, multi-objective optimization, search space analysis, empirical analysis of algorithms, design of algorithms.

(SA3) Multiagent Learning: A Game Theoretic Perspective Michael Bowling and Michael L. Littman

With the explosion of networking and affordable robotics, multiagent learning has become a hot research topic, combining the mature fields of machine learning and multiagent systems. The problem of learning a goal-oriented course of action in the presence of other goal-oriented agents raises new problems for both learning and multiagent systems. Complicating the learning problem is that when other agents are adapting, traditional machine learning assumptions like stationarity are violated. This tutorial will explain the unique challenges that are being addressed and the importance of this still-emerging field. A large focus will be on the introduction of critical game-theoretic concepts that underlie much of the recent work. This will be followed by an overview of the current progress, detailing the varied approaches and algorithms. A common set of problems and examples will be carried throughout the tutorial to provide continuity and a uniform understanding of the various techniques' strengths and weaknesses.

There will also be a discussion of the future issues and open problems that still remain. No background in game theoretic concepts will be assumed. A basic understanding of Markov decision processes and reinforcement learning would be helpful, although the most relevant concepts will be briefly reviewed.

	Michael Bowling, Carnegie Mellon University, is finishing his Ph.D. on "Multiagent Learning in the Presence of Limited Agents". His research examines learning and planning in multiagent systems, specifically solutions inspired by game theoretic concepts. He has also been extensively involved in robot soccer as a testbed for his research.
Michael Littman	Michael L. Littman, Rutgers University, studies decision making and optimization under uncertainty. He is a recipient of an undergraduate teaching award from Duke and a best paper award from AAAI. His work on reinforcement learning in Markov games helped introduce game theory to the rapidly expanding field of multiagent learning.

(SA4) Behavior-Based Programming of Robots and Multi-Robot Teams Tucker Balch

This tutorial provides an introduction to the principles and practice of behavior-based mobile robot programming for individual robots and for multi-robot teams. We will survey the inspiration and motivation for behavior-based autonomous robot systems, the unique challenges in this field and the wide range of solutions developed thus far. In addition to learning about the applications of behavior-based techniques for programming individual robots, attendees will learn about the theoretical and algorithmic aspects of behavior-based multi-robot systems, including communication, coordination and cooperation. This tutorial is targeted at non-specialists who have a general background in AI or robotics. Robotics experience is not assumed.

(SA5) Ontologies: Representation, Engineering and Applications Raphael Volz and Andreas Abecker

Ontologies constitute the foundation for many intelligent systems today. They have gained popularity for very different needs of groups like the World Wide Web community, the database community and the machine learning community. They are applied to applications and infrastructures like the Semantic Web, information extraction, e-Commerce, or E-Learning applications. The goal of this tutorial is to acquaint the reader with the basics of ontologies that are used for applications:
1. How are they represented?
2. How are they engineered?
3. How can they be applied?

It is the objective of this tutorial to communicate to the audience a comprehensive picture in order to understand the role of ontologies in future information systems. Thus, AI researchers will learn about how their work (e.g. learning, knowledge acquisition) may contribute to the overall task of ontology-based systems. Furthermore, practitioners will learn how ontologies may help to solve some of their problems with AI's ontologies.

(SP1) Immunological Computation: A New Paradigm in AI Dipankar Dasgupta and Jonathan Timmis

This tutorial will be devoted to discussing different immunological mechanisms and their relation to information processing and problem solving. The natural immune system is an adaptive learning system which is highly distributive in nature. It employs several alternative and complementary mechanisms for defense against foreign pathogens. The tutorial will cover an overview and the latest advances in this emerging field -- the artificial immune systems, which include computational algorithms based on immunological principles:

• Immunogenetic approaches
• Immunity-based optimization and learning
• Autonomous decentralized/Self-Organizing systems
• Immunity-based design and scheduling
• Immunological approaches to computer & network security
• Artificial Immune systems and their applications

This tutorial will be interesting to the audience who would like to explore new and innovative techniques as problem solvers. The participants will gain an understanding of the field, be able to appreciate the application potential of this new technique, and gain better insights about how to engineer massively parallel adaptive complex systems.

Dipankar Dasgupta

Dipankar Dasgupta is an Associate Professor of Computer Science at the University of Memphis, Tennessee. His research interests are broadly in the area of Applied Artificial Intelligence, tracking real-world problems through interdisciplinary cooperation. His areas of special interests include Genetic Algorithms, Neural Networks, Artificial Immune Systems, and their applications. He published more than 90 papers in book chapters, journals, and international conferences. He edited the book Artificial Immune Systems and Their Applications published by Springer-Verlag, 1999 and this is the first book in the field. Dr. Dasgupta is a senior member of IEEE, ACM and regularly serves as program committee member in many International Conferences. He first started (in 1997) organizing special tracks and workshops on Artificial Immune Systems and offered tutorials on the topics at international conferences since then. Dr. Dasgupta recently edited a special issue (on Artificial Immune Systems) of IEEE Evolutionary Computation Journal, Volume 6, Number 3, June 2002.

Jonathan Timmis

Jonathan Timmis has been a lecturer in Computer Science in the Computing Laboratory, University of Kent at Canterbury (UKC) since June 2000. He spent two years working as a Research Associate on immune inspired machine learning at the University of Wales, Aberystwyth (UWA) before moving to UKC. His research interests primarily lie in biologically inspired techniques, particularly in the development and use of novel immune inspired algorithms in the data mining, fault tolerance and software engineering domains. He has given a number of tutorials on Artificial Immune Systems, was conference co-chair on the first international conference on Artificial Immune Systems (ICARIS) in September 2002 and again will be general chair of ICARIS 2003. He has authored some 28 papers in international conferences, journals and books on subjects relating to AIS and is guest co-editor of a special issue for Artificial Immune Systems in the journal Genetic Programming and Evolvable Machines. He is a member of the IEEE.

(SP2) Genetic Algorithms in Search and AI Darrell Whitley

The tutorial reviews genetic algorithms and related models of genetic and evolutionary computation. Markov models are used to understand stochastic heuristic search methods. Walsh Analysis is used as a tool for exactly characterizing problem complexity for problems such as NK-Landscapes and MAXSAT problems. Representations such as real valued encodings, permutations, Gray codes and binary encodings will be discussed. An easy to understand explanation of No Free Lunch theories and their implications for both search and representation will be presented, along with example applications related to the Traveling Salesman Problem, Scheduling, Machine Learning and Neurocontrol.

Written tutorials for genetic algorithms and for combining GAs with neural networks are found at: http://www.cs.colostate.edu/~whitley under Publications.

Darrell Whitley

Darrell Whitley developed some of the first genetic algorithm scheduling applications as well as systems combining genetic algorithms and neural networks. He chaired the Governing Board of the International Society for Genetic Algorithms from 1993-1997 and served as Editor of Evolutionary Computation from 1997-2002.

(SP3) Distributed Constraint Reasoning Marius C. Silaghi, Jörg Denzinger and Makoto Yokoo

Due to the expansion of the Internet, a change has occured in our life and habits. 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. Distributed Constraint Satisfaction aims to offer equal opportunities to participants in cooperative or semi-cooperative distributed resource allocation problems.

This tutorial will provide a unified view on Distributed Constraint Reasoning, introducing distributed constraint reasoning systems as semi-cooperative multi-agent systems and concentrating on the 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 will be discussed. Additional information is available at http://www.cs.fit.edu/~msilaghi/IJCAI03-DCR-TUTORIAL/.

Prerequisite knowledge: The tutorial is suitable for a general AI audience, both academic and industrial. Knowledge of some basic search algorithm schemes would be helpful, but it is not essential.

Jörg Denzinger	Jörg Denzinger is a professor for artificial intelligence and multi-agent systems at the University of Calgary. He received his PhD from the University of Kaiserslautern in 1993. His research interests include distributed knowledge-based search, learning in multi-agent systems and cooperation concepts in general.
Marius C. Silaghi	Marius C. Silaghi is a professor for artificial intelligence and cryptography at Florida Institute of Technology. He got his PhD in Computer Science from the Swiss Federal Institute of Technology at Lausanne (EPFL) in 2002. His thesis: "Asynchronously Solving Distributed Problems with Privacy Requirements" contributes to distributed constraint reasoning.
Makoto Yokoo	Makoto Yokoo is a distinguished technical member of NTT Communication Science Laboratories, Japan. He is a founder of the research on distributed CSPs. He published a book Distributed Constraint Satisfaction: Foundation of Cooperation in Multi-agent Systems (Springer, 2001).

(SP4) The State of the Art in Ant Robotics Sven Koenig, Israel Wagner, Andrew Russell, Richard Vaughan, and David Payton

Ants are fascinating social insects. They are only capable of short-range interactions, yet communities of ants are able to solve complex problems efficiently and reliably. Ants have therefore become a source of algorithmic ideas for distributed systems where a robot (or a computer) is the "individual" and a swarm of robots (or the network) plays the role of the "colony". This half-day tutorial gives an overview of the state of the art in ant robotics, an area of artificial intelligence that uses ants as inspiration. Ant robots are simple and cheap robots with limited sensing and computational capabilities. This makes it feasible to deploy teams of ant robots and take advantage of the resulting fault tolerance and parallelism. Ant robots cannot use conventional planning methods due to their limited sensing and computational capabilities. Rather, their behavior is driven by local interactions. For example, ant robots can use trails to follow other ant robots or cover terrain robustly, similar to ants that lay and follow pheromone trails. Ant robotics is a rapidly growing area in both artificial intelligence and robotics. In the past couple of years, researchers have developed ant robot hardware and software and demonstrated, both in simulation and on physical robots, that single ant robots or teams of ant robots solve robot-navigation tasks robustly. Researchers have also developed a theoretical foundation for ant robots, based on ideas from real-time heuristic search, stochastic analysis, and graph theory.

This half-day tutorial on the current state of the art in ant robotics is given by experts who will give an overview of this exciting area without assuming any prior knowledge on the topic. It will cover all important aspects of ant robotics, from theoretical foundations to videos of implemented systems. To this end, it will bring together the various research directions for the first time, including theoretical foundations, ant robot hardware, and ant robot software. Its primary objective is to give non-specialists a comprehensive overview of the state of the art of the field, for example, to allow researchers and students to do research in the area and to allow practitioners to evaluate the current state of the art in ant robotics. Consequently, it is of interest to anyone who is interested in multi-agent systems, distributed problem solving, search, mobile robotics, and artificial intelligence in general.

For additional information, see http://www.cc.gatech.edu/fac/Sven.Koenig/ijcai03-tutorial.html

Sven Koening	Sven Koenig (Georgia Institute of Technology, USA) became an assistant professor in the College of Computing at Georgia Institute of Technology after receiving his Ph.D. in computer science from Carnegie Mellon University. He is the recipient of an NSF CAREER award, an IBM Faculty Partnership Award, the Raytheon Faculty Fellowship Award from Georgia Tech, and a Fulbright Fellowship Award. He is currently on the editorial board of the Journal of Artificial Intelligence Research (JAIR) and will co-chair the International Conference on Automated Planning and Scheduling (ICAPS) in 2004. Sven's research centers around techniques for decision making (planning and learning) that enable situated agents to act intelligently in their environments and exhibit goal-directed behavior in real-time, even if they have only incomplete knowledge of their environment, limited or noisy perception, imperfect abilities to manipulate it, or insufficient reasoning speed. He has published over 60 papers on this topic in the artificial intelligence and robotics literature.
Israel Wagner	Israel Wagner (Technion and IBM Haifa Research Lab, Israel) received his B.Sc. degree in computer engineering from the Technion (Israel Institute of Technology), Haifa, in 1987, cum laude, an M.Sc. degree in computer science from Hebrew University, Jerusalem, in 1990, cum laude, and a Ph.D. degree in computer science from the Technion in 1999. He was a research engineer at General Microwave, Jerusalem, from 1987 until 1990, when he joined the IBM Haifa Laboratories as a member of the technical staff. Israel is currently an adjunct senior lecturer in the Computer Science Department at the Technion. His research interests include multi-agent robotics, manual and automatic VLSI design, computational geometry, and graph theory. He has published over 25 papers on these topics in the artificial intelligence, robotics, and VLSI literature and co-edited a special issue of the Annals of Mathematics and Artificial Intelligence on ant robotics in 2001.
Andrew Russell	Andrew Russell (Monash University, Australia) received his B. Eng. and Ph.D. degrees in 1972 and 1976, respectively, from the University of Liverpool, in the U.K. After a brief period in the computer industry he took a position as engineer working on robot design and applications in the Department of Artificial Intelligence at the University of Edinburgh, Scotland. For the past 19 years he has been a member of academic staff at the University of Wollongong and now at Monash University (both in Australia). Andy's research interests include robot tactile sensing, the design of robotic mechanisms and olfactory sensing for robots. He has written books on robot tactile sensing and odour sensing for mobile robots and published over 70 refereed conference papers and journal articles describing his work in intelligent robotics. Andrew will give a video presentation.
Richard Vaughan	Richard Vaughan (HRL Laboratories, USA) received a D.Phil. in Computation from Oxford University in 1999, and a B.A. (Hons.) in Computing with Artificial Intelligence from Sussex University in 1993. He was a postdoctoral research associate at the Robotics Laboratory of the University of Southern California from 1998 to 2001, and is currently a member of the technical staff at HRL Laboratories. Richard's research concerns the mechanisms of intelligent behavior in individuals and groups of people, animals, robots and software agents. His projects emphasize dynamic autonomy, scalability, interaction and simplicity. The majority of his more than 20 publications concern the functional analysis and recreation of aspects of animal behavior, a methodology he calls "constructive ethology". His other papers are on simulation, interfacing and networking for robotics applications. Richard is a founding member of the Player/Stage project, which creates tools for robotics and sensor network research. He has given over 30 invited talks, conference, workshop and tutorial presentations in the USA and Europe since 1993, including a tutorial on Animal Robotics at the International Conference on Simulation of Adaptive Behavior in 1998.
David Payton	David Payton (HRL Laboratories, USA) is principal research scientist and manager of the Cooperative and Distributed Systems Department at HRL Laboratories in Malibu, California. He received his B.S. degree from UCLA in 1979 and his M.S. degree from MIT in 1981. David is currently principal investigator for the DARPA Pheromone Robotics project and is also involved in development of agent-assisted multi-user collaboration tools. After joining HRL Laboratories in 1982, David has been involved in numerous projects for the development of intelligent autonomous agents. This includes work on the DARPA Autonomous Land Vehicle project, the Unmanned Ground Vehicle and the development of behavior-based robot control. David has over 25 publications in the area and holds six patents. David's material will be presented by Richard Vaughan.

(SP5) Ontology-Based Information Integration Ubbo Visser, Heiner Stuckenschmidt, and Holger Wache

Intelligent access and integration of information becomes more and more important with the Internet growing every day. In this tutorial we will discuss the relation between existing research in the area of intelligent information integration and new requirements and technologies that arise from the area of Semantic Web research. We would like to emphasize the importance of information integration on the World Wide Web in the context of providing intelligent access to heterogeneous and distributed information sources and intelligent services. Formal ontologies have been identified to be useful for this process because they provide means to describe the semantics of information explicitly. This is a prerequisite to use logical reasoning. We will start with a motivation why we should use ontologies and will discuss existing solutions to the problem of information integration. We compare these solutions and identify common features of architectures and technologies. Furthermore, we show how these common features relate to Semantic Web architectures and technologies, revealing similarities and differences. Finally, we discuss prospects and challenges for Semantic Web research. We assume that attendees have basic knowledge in the area of data and information modelling. Knowledge about Web-based information systems would be an advantage.

Heiner Stuckenschmidt	Heiner Stuckenschmidt is a post-doc researcher in the Knowledge Representation and Reasoning Group at the Vrije Universiteit Amsterdam. His research interests include the application of AI methods to the problem of representing, integrating and querying semantically rich information on the World Wide Web.
Ubbo Visser	Ubbo Visser is Assistant Professor in the AI Group of the Center for Computing Technologies at the University of Bremen, Germany. His research focus is twofold: knowledge representation and processing for the Semantic Web and Multiagent systems in dynamic and real time environments.
Holger Wache	Holger Wache is Managing Director in the Intelligent Systems area of the Center for Computing Technologies at the University of Bremen. His research focus is foundation of the area of intelligent information integration.

Monday, August 11

(MA1) Market Clearing Algorithms Tuomas Sandholm

The last three 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, reverse auctions, and exchanges (many-to-many auctions) 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 combinatorial bids. A new method for selective preference elicitation for combinatorial markets is presented.

Tuomas Sandholm

Tuomas Sandholm is Associate Professor of computer science at Carnegie Mellon University. He received the Ph.D. and M.S. degrees in computer science from the University of Massachusetts at Amherst in 1996 and 1994. He earned an M.S. (B.S. included) with distinction in Industrial Engineering and Management Science from the Helsinki University of Technology, Finland, in 1991. He has twelve years of experience building electronic marketplaces. Several of his systems have been commercially fielded. He has published over 130 technical papers, and received numerous academic awards including the inaugural ACM Autonomous Agents Research Award and the NSF Career award.

(MA2) SAT Beyond Propositional Satisfiability Roberto Sebastiani

The last decade has witnessed an increasing interest in Propositional Satisfiability (SAT), with a boost in the performances of SAT solvers. Unfortunately, simple propositional logic is often not expressive enough to solve complex real-world problems. More recently, SAT procedures have been successfully used also as basic inference engines of decision procedures for much more expressive problems, like reasoning in modal and description logics, resource planning, temporal reasoning, formal verification of timed systems, formal verification of circuits at an abstract level.

In this tutorial we focus on the latter aspect, and we show how SAT solvers can be correctly and efficiently extended to work with more expressive domains by integrating them with domain-specific procedures. The tutorial is directed to a rather general AI audience, in particular to people interested in various domains of Automated Reasoning and Knowledge Representation, like SAT, decision procedures, reasoning in modal and description logics, planning, temporal reasoning, and also to those people interested in applications of automated reasoning techniques to formal verification. The tutorial assumes only a basic knowledge of logic and AI topics. A background on SAT is of help, but not strictly necessary.

Roberto Sebastiani

Roberto Sebastiani is a researcher at University of Trento, Italy. He got his PhD in Computer Science Engineering from University of Genova, Italy (1997). His research interests are Formal Verification, SAT, non-CNF SAT, SAT-based Planning and Model Checking, Decision procedures for modal logics, Integration of Automated Reasoning and Computer Algebra.

(MA3) Web Services and Beyond Munindar P. Singh and Michael N. Huhns

Web services have been gathering much attention lately. Everyone agrees about their fundamental importance to information technology architectures and applications. The main advantage of Web services arises when we can compose them to create new services. Unfortunately, much of the attention on Web services has been focused on the lower-level, infrastructural matters, often down to encoding syntaxes and unnecessarily narrow means of invoking services. This tutorial will present the necessary concepts, architectures, theories, techniques, and infrastructure to use and compose Web services. It will include an overview of the state of the art in selected application areas. This tutorial gives the essential background for anyone planning to learn about and contribute to the principles and applications of service composition. It will guide practitioners by highlighting best practices in service composition and introduce students and advanced developers to the key trade-offs as well as the limitations of current approaches. Some of the key techniques for service composition (e.g., dealing with their discovery and engagement) were developed in the areas of databases, distributed computing, artificial intelligence, and multiagent systems. These are generally established bodies of work that can be readily adapted for service composition. Some additional techniques, although inspired by these areas, must be developed from scratch. This is because for Web services, we must address the essential openness and scale of Web applications that previous work did not need to address. Both classes of key techniques should be incorporated into our best practices for service design and composition. In many cases, they can be applied on top of the existing approaches.

Prerequisites: Some experience with Web programming; basic concepts of artificial intelligence.

Munindar P. Singh

Munindar P. Singh is an associate professor in computer science at North Carolina State University. From 1989 through 1995, he was with the Microelectronics and Computer Technology Corporation (MCC). Munindar's research interests include multiagent systems and Web services. He focuses on applications in e-commerce and personal technologies. Munindar's 1994 book Multiagent Systems, was published by Springer-Verlag. He coedited Readings in Agents, which was published by Morgan Kaufmann in 1998. Munindar's research has been recognized with awards and sponsorship by the National Science Foundation, IBM, Cisco Systems, and Ericsson. Munindar was the editor-in-chief of IEEE Internet Computing from 1999 to 2002 and serves on its editorial board. He is a member of the editorial board of the Journal of Autonomous Agents and Multiagent Systems. Munindar serves on the steering committee for the IEEE Transactions on Mobile Computing.

Michael N. Huhns

Michael N. Huhns is a professor in computer science and engineering at the University of South Carolina, where he also directs the Center for Information Technology. Previously he was a Senior Member of the Research Division at the Microelectronics and Computer Technology Corporation. Prior to joining MCC in 1985, he was an associate professor of electrical and computer engineering at the University of South Carolina, where he also directed the Center for Machine Intelligence. Mike has been an adjunct professor in computer sciences at the University of Texas. Mike is a member of Sigma Xi, Tau Beta Pi, Eta Kappa Nu, ACM, IEEE, and AAAI. He is the author of over a hundred technical papers in machine intelligence and an editor of the books "Distributed Artificial Intelligence," Volumes I and II, and "Readings in Agents." His research interests are in the areas of distributed artificial intelligence, machine learning, enterprise modeling and integration, and software engineering. He writes a column "Agents on the Web" for IEEE Internet Computing. Mike is an associate editor for the Journal of Autonomous Agents and Multiagent Systems. He is on the editorial boards of IEEE Transactions on Mobile Computing, IEEE Internet Computing, International Journal on Intelligent and Cooperative Information Systems, and Journal of Intelligent Manufacturing. Previously, Mike was an associate editor for IEEE Expert and the ACM Transactions on Information Systems. He is on the Advisory Board for the First International Conference on Multiagent Systems, 1995, and has been on the Advisory Boards for several of the International Workshops on Distributed Artificial Intelligence.

(MA4) Multiagent and Agent-Human Teamwork: Theory and Practice Milind Tambe

Teamwork is a fundamental area of multiagents research, with a large number of applications, such as synthetic agent teams in virtual environments for training, software assistant teams to support human organizations, robot-agent-person teams for disaster rescue, etc. This tutorial will survey the state of the art of both the theory and practice of multiagent and agent-human teamwork. We will discuss two key aspects of teamwork theory. The first aspect, based on belief-desire-intention models, will cover the joint intentions theory, SharedPlans theory and others. The second, founded on a decision-theoretic perspective, will cover decentralized partially observable markov decision process (POMDP) models and their applications in analysis of multiagent systems. Half of the tutorial will be devoted to practical systems constructed by exploiting teamwork theory as the basis. Indeed, one key lesson learned in practical systems is that in complex, dynamic environments, creating fixed and domain-specific coordination plans is highly problematic: these plans are not reusable across domains and their lack of flexibility can lead to severe failures. Instead, a new approach based on developing general teamwork models, i.e., domain-independent, reusable team coordination algorithms, appears to provide more promise. We will discuss research on general team coordination algorithms and cover their applications. The last part of the tutorial will cover agent-human teamwork, and key issues in such teamwork, in particular, mixed-initiative and adjustable autonomy.

Milind Tambe

Milind Tambe obtained his PhD in Computer Science from Carnegie Mellon University. He is currently an Associate Professor of Computer Science at the University of Southern California and a project leader at USC's Information Sciences Institute. He will be the general co-chair for the International Conference on Autonomous Agents and Multiagent Systems in 2004.

(MA5) Resource-Bounded and Time-Critical Reasoning Lloyd Greenwald and Shlomo Zilberstein

A central problem in artificial intelligence is how to develop computational models that allow decision-support systems or autonomous agents to react to a situation after performing the right amount of deliberation. Frequently, the complexity of problem solving makes it beneficial to use approximate solutions rather than try to compute the optimal answer. This issue arises in a wide range of application domains including medical trauma management, Bayesian inference, sequence alignment, graphics rendering, web page prefetching, autonomous space exploration, real-time avionics, and robot navigation. This tutorial explores the theory and practice of building intelligent systems that reason explicitly about employing limited computational resources to generate timely solutions to difficult combinatorial optimization, planning and scheduling problems. Solution techniques go beyond simple greedy or reactive algorithms to achieve high-quality solutions while meeting both hard and soft real-time deadlines. We will explore over fifteen years of progress in this area, covering historical perspectives, state of-the-art solution techniques, and current and future challenges.

Topics include: Computational tradeoffs in inference, planning, and search; representation and measurement of computational tradeoffs; dependency of performance on problem instances; anytime algorithms and flexible computation; strategies for allocating resources among reasoning subproblems; myopic and non-myopic control; partitioning resources between meta-level and object-level reasoning; applications of resource-bounded systems; and current research challenges.

See http://anytime.cs.umass.edu/ijcai-03-tutorial.html Participants should be familiar with introductory artificial intelligence, algorithm design and analysis, and introductory probability and statistics.

Lloyd Greenwald	Lloyd Greenwald is an Assistant Professor of Computer Science and Director of the Intelligent Time-Critical Systems Lab at Drexel University. He received his Ph.D. in Computer Science from Brown University. His research interests include time-critical planning and scheduling, mobile robotics, machine learning, ad hoc and sensor networks, and medical decision-making.
Shlomo Zilberstein (c)MFPhotography	Shlomo Zilberstein is an Associate Professor of Computer Science and Director of the Resource-Bounded Reasoning Lab at the University of Massachusetts, Amherst. He received his Ph.D. in Computer Science from the University of California, Berkeley. His research interests include approximate reasoning, decision theory, heuristic search, planning and scheduling, and resource-bounded reasoning.

(MP1) Automated Reasoning for Security Protocol Verification* Alessandro Armando and Fabio Massacci

*Cancelled

(MP2) Foundations of Constraint Satisfaction Roman Barták

Constraint programming is a technology for declarative description and solving of hard combinatorial problems. The tutorial gives a broad and deep survey of major constraint satisfaction algorithms. First, the notion of a constraint is explained and some examples of practical applications of constraint technology are given. Then we survey the basic search algorithms for solving constraints; both local search and depth-first search methods are presented. The algorithms are explained in an incremental nature showing how the more advanced algorithms are built up on improvements of the simpler algorithms. In the next part we concentrate on the core of constraint satisfaction technology consistency techniques. We explain the main consistency levels like arc and path consistency and we present several algorithms to achieve them. We also describe how the consistency techniques reduce the search space in the depth-first search. The tutorial is concluded with examples of modeling problems using constraints. The tutorial is targeted to a broad AI community, in particular to everyone who is not familiar with the details of constraint satisfaction technology. It introduces novices as well as expert non-specialists to one of the major topics of AI. No prior knowledge of constraint satisfaction is required.

Roman Barták is an assistant professor at Charles University, Prague (Czech Republic) and he leads research activities of Visopt B.V., a company developing Advanced Planning and Scheduling systems. His work covers several areas of constraint satisfaction, namely constraint hierarchies, filtering algorithms, and applying constraints to planning and scheduling.

(MP3) Multi-Agent Modeling of Grounded Language Evolution Luc Steels

The computational and robotic modeling of language evolution is emerging as a new subfield in AI, and is generating great interest from the many other disciplines interested in this question. The objective is to come up with precise operational models how communities of agents equipped with a cognitive apparatus, a sensori-motor system, and a body, can arrive at shared communication systems that have similar characteristics as human languages. This enormous challenge requires the integration of work in vision and robotics, computational linguistics, and machine learning, but pushes each of these disciplines in new directions. The tutorial reviews work in this area, focusing on all aspects of language: the origins of sound systems, the origins of lexicons, the origins of grammar, and the co-evolution of language and (grounded) meaning. It presents in detail a key experiment for each topic, and surveys the many remaining open problems.

(MP4) Recent developments in Qualitative Spatial and Temporal Reasoning Frank Anger, Hans Guesgen, and Gerard Ligozat

Space and time are ubiquitous parameters of our knowledge about the world. Qualitative spatial and temporal reasoning methods have evolved in order to reason about space and time when precise quantitative information is either superfluous or unavailable. The potential applications of the field include natural language understanding, planning, GIS, robotics, and human-machine communication. This tutorial will guide practitioners by describing the main methods and results in the field, including: basic formalisms for various models of time (including non-linear ones) and space; tractability results in qualitative spatial and temporal calculi; fuzzy extensions of the calculi and applications; spatio-temporal reasoning. The tutorial is suitable for all researchers interested in an overview of the current state of the art in the domain. It assumes only a basic knowledge of AI and Knowledge Representation techniques. The logical notions will be introduced when required.

Frank Anger	Frank Anger is Program Director and Acting Deputy Division Director at NSF. He holds degrees from Princeton, Cornell and Florida and held professorships at several universities before joining NSF. He has published over 50 papers covering a wide range of topics and is a founding member of three professional organizations.
Hans Guesgen	Hans Guesgen is an associate professor in computer science at the University of Auckland, New Zealand. His areas of research include spatio-temporal reasoning and constraint satisfaction, with more than 50 publications in these areas. He co-organized and co-chaired various workshops on spatial and temporal reasoning.
Gerard Ligozat	Gerard Ligozat is a professor in computer science at the University of Paris at Orsay, France. His fields of interest include temporal and spatial representation and reasoning in connection with formal and natural language issues. Along with many publications, he authored or co-authored two books on knowledge representation.

(MP5) Case Based Reasoning for Industrial Knowledge Management Ralph Bergmann and Mehmet H. Göker

The most valuable asset of a company is knowledge. The ability to capture, cumulate and re-use knowledge and experience in an effective and efficient manner, gives companies major competitive advantages. Case-Based Reasoning (CBR) allows developing computer systems that store corporate experience in a case-base and enable users to access, re-use and extend this knowledge in a natural and straightforward manner. A CBR system solves new problems by adapting and re-using solutions to previous, similar problems, issues of and solutions for real world knowledge management. It will provide a technical introduction to industrial knowledge management using CBR and illustrate the introduced concepts and issues with examples from deployed industrial applications. Criteria for successful deployment and long-term maintenance and utilization of knowledge management systems will be pointed out and directions for future research will be highlighted. The examples given throughout the tutorial will provide guidelines for the specification, design, implementation, and deployment, as well as the continuous usage of a CBR system.

Prerequisite knowledge: The tutorial is suitable for participants with some basic AI knowledge, coming either from an academic or industrial background.

Ralph Bergmann	Ralph Bergmann is professor for computer science at the University of Hildesheim (Germany) where he is directing a research group on data- and knowledge management. He is project leader of several national and European projects and author of three books and more than 100 scientific papers.
Mehmet H. Göker	Mehmet H. Göker is Vice President of Professional Services of Kaidara Software and implements case-based knowledge management systems in industry. He has been the chair and co-organizer of the industrial day of the last four CBR conferences and is author of two books and more than thirty scientific papers on case based reasoning and knowledge management.