Tutorial Program & Descriptions

The IJCAI tutorial program for 2001 features 20 four-hour tutorials, each covering a concentrated technical topic of current or emerging interest. Tutorials will be presented by experienced researchers and practitioners expert in the corresponding subject area. A separate registration fee applies to each tutorial. Tutorials designated (SA) will be held Sunday, August 5, from 9:00 am – 1:00 pm. (SP) tutorials will be held Sunday, August 5, from 2:00 – 6:00 pm. (MA) tutorials will be held Monday, August 6, from 9:00 am – 1:00 pm. (MP) tutorials will be held Monday, August 6, from 2:00 – 6:00 pm.

Tutorial Descriptions

SA1

AI Techniques for Knowledge Management

Stefan Decker and Steffen Staab 

Knowledge management (KM) is a discipline with the purpose of managing the knowledge assets of organizations. Though KM is deeply rooted in business management, IT support may add an enormous lever-age for the effortless creation, conservation, sharing, and exploitation of organizational knowledge. AI has a long tradition in creating, interacting with and managing of knowledge and has developed many techniques that may propel this knowledge management cycle inside an organization. In the tutorial, we will give an introduction in intelligent IT support for Knowledge Management that individual and communities of users in knowledge-intensive organizations may benefit from.

Prerequisites: Participants should have some general IT knowledge and basic knowledge about AI.

Stefan Decker is a postdoctoral fellow at the department of computer science at Stanford University, where he works on ontology articulation. His research interests include knowledge representation, and database systems for the Semantic Web, information integration and translation, and ontology articulation and merging.   See http://www-db.stanford.edu/~stefan and http://www.SemanticWeb.org.

Steffen Staab is assistant professor at the Univ. of Karlsruhe and working part-time at Ontoprise, a company he has co-founded. Steffen holds M.S.E. and Dr.rer.nat. degrees from the University of Pennsylvania and Freiburg University, respectively. He has been working and publishing on knowledge management, text mining, knowledge representation and the Semantic Web.  See http://www.aifb.uni-karlsruhe.de/~sst/.

SA2

Economically Founded Multiagent Systems

Tuomas Sandholm

In multiagent systems for agent-mediated electronic commerce, computational agents find contracts on behalf of the real-world parties that they represent. This saves human negotiation time, and computational agents are often better at finding beneficial deals in combinatorially and strategically complex settings. Applications include supply chain coordination, electricity markets, bandwidth allocation, vehicle routing among dispatch centers, and resource allocation in distributed operating systems, to name just a few.

A key goal is to design open distributed systems in a principled way that leads to globally desirable outcomes even though every participating agent only considers its own good and may act insincerely. The tutorial covers relevant AI and game theory topics in voting, auctions (also multi-unit, multi-item, and many-to-many exchanges), and automated contracting. Emphasis is given to fundamental results and algorithms. Effects of computational limitations (agents’ bounded rationality) are discussed as a key feature that has not received adequate attention. Implementation experiences will be shared, and real world applications presented.

No background is required in economics, game theory or multiagent systems.

Tuomas Sandholm is Associate Professor in the Computer Science Department at Carnegie Mellon University. He received the Ph.D. and M.S. degrees in computer science from UMass, 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 over ten years of experience building multiagent systems. He has co-developed two fielded AI systems, founded two companies in the area of electronic commerce, and published over 115 technical papers.  See http://www.cs.wustl.edu/~sandholm/.

SA3

Neural Networks for Pattern Recognition: The Impact of Architecture

Miroslav Kubat

Artificial neural networks rank among the most popular tools in pattern recognition. Their widespread use was boosted by algorithms for learning from examples. A challenging research issue is how to establish, for a given task, appropriate neural architecture: small networks are prone to get trapped in local minima, whereas large networks tend to overfit the training examples.

Historically, researchers relied on trial-and-error procedures, experimenting with several topologies, and then selecting the one that best satisfied predefined criteria. In the 1990s, more systematic techniques emerged. They can roughly be divided into three categories. Search-based strategies that exploit AI-search techniques, including the genetic algorithm; logic-based strategies that utilize prior knowledge expressed as production rules or decision trees; and piecemeal strategies that focus on one neuron at a time.

The tutorial begins with a systematic introduction into networks consisting of mutually interconnected layers of neurons. Then, the techniques for their architectural design will be investigated. Due attention is devoted to experience from major projects.

No special prerequisite knowledge is required.

Miroslav Kubat is Associate Professor of Computer Science at the University of Louisiana at Lafayette. His research focuses primarily on Machine Learning and Neural Networks. Prior to coming to the U.S., he held positions in Austria, Canada, and the Czech Republic. He has published about 60 scientific papers and co-edited (with R. Michalski and I. Bratko) the book Machine Learning and Data Mining: Methods and Applications.

SA4

Phase Transitions and Structure in Combinatorial Problems

Carla P. Gomes, Tad Hogg, Toby Walsh, and Weixiong Zhang

This tutorial will present an exciting area combining concepts from theoretical physics and artificial intelligence. We will show how the study of phase transition, structure, and related phenomena is changing the way we characterize the computational complexity of combinatorial problems, beyond the notion of worst-case complexity. Furthermore, we will discuss how we can use tools from statistical physics to provide a much more detailed description of a problem’s complexity and how we can leverage such insights into the design of search algorithms.

We will describe phase transition behavior observed in a number of different decision problems such as SAT, graph coloring, and number partitioning, as well as optimization problems such as TSP and maximum SAT, and in other complexity classes like P and PSpace. The second part of the tutorial will cover recent work connecting structural features of problems with phase transition phenomena and computational complexity.  Topics covered will include constrainedness, backbone structure, and small world topology. We will also discuss how to exploit structure and randomness in problems using restart strategies and, more generally, portfolios of algorithms.

The tutorial is aimed at the general AI audience. Familiarity with some basic concepts of combinatorial optimization, probability theory, and computational complexity is desirable but not essential. Please visit http://www.cs.wustl.edu/~zhang/links/ijcai-phase-transitions. html.

Carla P. Gomes is the Director of the Intelligent Information Systems Institute at Cornell University. Her research has covered several areas in artificial intelligence and computer science, including planning and scheduling, integration of CSP and OR techniques for solving combinatorial problems, and algorithm portfolios.

Tad Hogg is on the research staff of Xerox PARC. His research interests include multiagent systems, smart matter, and the relation between physics and computation, including analogies with physical phase transitions found in combinatorial search.

Toby Walsh is an EPSRC Advanced Research Fellow at the Department of Computer Science (York). He has worked extensively on phase transition behavior in a number of different areas including: satisfiability, constraint satisfaction, traveling salesperson problems, and number partitioning.

Weixiong Zhang is an associate professor at Washington University in St. Louis. His primary research interests include multiagent systems, heuristic search and combinatorial optimization, especially phase transition phenomena and approximation methods that exploit phase transitions.

SA5

Question Answering

Dan Moldovan and Sanda Harabagiu 

Question Answering (QA) is a fast growing area of research with tremendous commercial potential. The problem of QA is to find answers to open-domain questions by searching a large collection of documents. Unlike Internet search engines, QA systems provide short, relevant answers to questions.

The recent explosion of information available on the World Wide Web makes question answering a compelling framework for finding information that closely matches user needs. Due to the fact that both questions and answers are expressed in natural language, QA methodologies deal with language ambiguities and incorporate NLP techniques.

The tutorial presents a survey of the most performant open-domain QA systems architectures and the basic techniques employed to build them. Topics include: answer taxonomies, answer processing, document retrieval, answer extraction and ranking, accuracy performance and speed performance.

Dan Moldovan is a Professor of Computer Science and Engineering at Southern Methodist University, Dallas, Texas. Prior to this he was a faculty at the University of Southern California, Member of Technical Staff at Bell Laboratories, and a Program Director at the National Science Foundation. Dr. Moldovan received a PhD from Columbia University in 1978.

Sanda Harabagiu is an Assistant Professor in the Department of Computer Science and Engineering at Southern Methodist University, Dallas, Texas. She received a PhD in Computer Engineering from the University of Southern California, Los Angeles in 1997 and a Doctorate in Computer Science form the University of Rome "Tor Vergata", Italy in 1994. Dr. Harabagiu is a recipient of the National Science Foundation CAREER award.

SP1

Agent Communication in Knowledge Based Electronic Markets

Benjamin Grosof and Yannis Labrou

Background: Electronic markets (e-markets) for the buying and selling of goods and services over the Web are a fast-growing, multi-billion-dollar segment of the world economy. Relevant knowledge-based techniques draw on several areas of AI: knowledge representation and reasoning, learning, and communication. As more knowledge-based pieces of e-commerce have developed, issues are arising of how to put them together into overall functioning markets — largely, via forms of agent communication. E-markets include infrastructural and intermediary services, e.g., for yellow pages, catalogs, shopping search, advertising, sales assistants, brokers/aggregators, infomediaries, reputation/trust, authentication, and payments. Intelligent software agents in this context are autonomous, cooperating processes that use rich agent communication languages to exchange information and knowledge and to coordinate their activities.

This tutorial will discuss existing techniques and their theory, currently identified challenges, standardization efforts and near-future opportunities for practical applications of agent communication in knowledge-based e-markets. Here, knowledge-based techniques for agent communication, ontologies, business rules, and information integration are of rising interest, in part due to the rise of XML, and have started having practical impact on real e-markets. The tutorial includes a brief review of several agent-based projects that are using these emerging standards. 

Prerequisites: Basic general AI knowledge, in particular especially the basics of rule-based knowledge representation, is assumed.

Benjamin Grosof is Assistant Professor in Information Technology at the MIT Sloan School of Management. His research addresses e-commerce and Web technology, combining agent communication, XML, and knowledge representation for applications in contracting, negotiation, and business policies. He is PI currently for a project in the DARPA Agent Markup Language (DAML) initiative, designing knowledge-level techniques to realize the vision of the Semantic Web. Previously, he was a senior research scientist at IBM T.J. Watson Research Center. While at IBM, most recently he founded and led a project on Business Rules for E-Commerce. This produced IBM CommonRules (V2.1 currently on IBM alphaWorks), which pioneered XML agent communication of inter-operable business rules with conflict handling. He co-led its application piloting for rule-based XML agent contracting in EECOMS, a $29Million NIST industry consortium project on manufacturing supply chain management. He holds a PhD from Stanford University in Computer Science, with specialty AI, and a BA from Harvard University in Applied Mathematics, with specialty economics and management science. He is author of over 30 refereed publications, two major software releases, and one patent; and co-chaired the AAAI Conference Workshops on AI in E-Commerce (1999) and Knowledge-Based E-Markets (2000). Email: bgrosof@mit.edu. Home Page: http://www.mit.edu/~bgrosof

SP2

Computer Games

 John E. Laird and Michael van Lent

Computer games are becoming a major application area of AI.  Although games have traditionally used very simple AI, the computer game industry is seeing a significant increase in available CPU power as graphics processing has moved into special purpose processors. We can expect a significant increase in the complexity and importance of AI with computer games.

This tutorial provides a broad overview of computer and video games for the AI researcher interested in learning more about the business and technology of computer games. The major topics that are covered include:

• The history of computer games from early time-sharing up through today’s consoles.
• The business of computer games including the major market forces and industry trends.
• Current computer game technology, including the hardware and software systems used in developing and delivering computer games.
• The design and development of computer games and a discussion of good gameplay: what makes a game fun to play.
• The fundamentals and theory of computer games including graphics, physics, AI, sound, and networking.
• An example of AI research in computer games.

Michael van Lent received his PhD from the University of Michigan in 2000. His research interests include machine learning and artificial intelligence in computer games. His game-related activities include the development of a senior-level class titled "Computer Game Design and Implementation", helping to organize the 1999, 2000 and 2001 AAAI Spring Symposia on AI and Interactive Entertainment, and speaking at the 1999 Game Developer's Conference.

John E. Laird is a Professor of Electrical Engineering and Computer Science at the University of Michigan. He received his PhD in Computer Science from Carnegie Mellon University in 1983. He is one of the creators of the Soar architecture and leads its continued development and evolution. He was elected as a Fellow of AAAI in 1995.

SP3

Philosophical Foundations:  Some Key Questions

Aaron Sloman and Matthias Scheutz

This tutorial, presented by tutors with considerable experience in both philosophy and AI, will introduce philosophical problems relevant to the goals and methodology of AI as science and AI as engineering, including the contribution of AI to the study of mind. The mode of presentation will be a mixture of lectures and interactive discussions, addressing the following topics:

• What are virtual machines and how are they related to physical machines?
• Can the relations between virtual and physical machines as understood by software engineers shed light on philosophical questions about relations between minds and brains?
• Can mental events, or events in virtual machines, have causal powers?
• What sorts of virtual machines can biological evolution produce?
• What sorts of VM architectures can support ontologies including beliefs, desires, pleasures, pains, decisions and other mental events and processes?
• Under what conditions might it be reasonable to describe a machine as conscious, or as having emotions, or as using representations?
• Can animals or robots, with different information processing architectures be describable using similar mental concepts?

 A more detailed overview of the tutorial will be available online at http://www.cs.bham.ac.uk/~axs/ijcai01/.

 Prerequisite knowledge: Knowledge of AI and experience of software development will help.

Aaron Sloman (http://www.cs.bham.ac.uk/~axs/) is a professor of AI & Cognitive Science, University of Birmingham. BSc Physics, mathematics, 1956; DPhil Philosophy, 1962. Rhodes Scholar. Fellow of AAAI, AISB and ECCAI. Research: vision, spatial reasoning, architectures for human-like agents, emotions and related philosophical topics. Toolkit for cognitively rich agents. Author: The Computer Revolution in Philosophy (Harvester Press, 1978) and many papers on AI, Cognitive Science and Philosophy. 

Matthias Scheutz  (http://www.cs.bham.ac.uk/~mxs/) is a research Fellow in AI, University of Birmingham, Assistant Professor in AI, University of Notre Dame (on leave). Ph.D. Philosophy, 1995; Ph.D. Cognitive Science and Computer Science, 1999 Organizer NTCS'99:  "Computationalism - The Next Generation" ( http://www.univie.ac.at/cognition/conf/ntcs99/) Co-founder of Austrian Society for Cognitive Science. Research: philosophy of cognitive science and AI (the nature of implementation), behavior based robotics, evolvable agent architectures. Author of several conference and journal papers on AI and the philosophy of cognitive science.

SP4

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, and satisfiability.

In this tutorial we will introduce stochastic search algorithms and characterize 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 randomized systematic search algorithms. For exemplifying these algorithms, we will mainly use the satisfiability problem in propositional logic (SAT) and the Traveling Salesman 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 is not a necessary prerequisite.

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).

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 holds a MSc in Economics and Industrial Engineering from TU Karlsruhe and a PhD in Computer Science from TU Darmstadt and has been a Marie-Curie fellow at IRIDIA (Brussels, Belgium).

SP5

Systems that Adapt to their Users

Anthony Jameson

Interactive systems that adapt to their users have been gaining rapidly in practical importance, for example in the areas of e-commerce and web-based information access. Relevant terms include personalization, personal assistants, adaptive interfaces, user modeling, and student modeling. The AI techniques employed include machine learning techniques, probabilistic and decision-theoretic approaches, and logic-based methods.

Although user-adaptive systems take many different forms, there are a number of questions that must be addressed in the design of any such system:

1. What functions are to be served by the adaptation?

2. What properties of the user should be modeled?

3. What input data about the user should be obtained, and how?

4. What techniques should be employed to make inferences about the user?

5. How should decisions about appropriate adaptive system behavior be made?

6. What empirical studies should be conducted?

For each of these questions, we will systematically examine the main answers that have been worked out so far in research and practice. The discussion will integrate the results of previous experience in many different domains from an AI perspective, and it will refer throughout to concrete system examples.

Prerequisite Knowledge: This tutorial will be accessible to all IJCAI-01 attendees.

Anthony Jameson is a senior researcher at the German Research Institute for Artificial Intelligence (DFKI) and adjunct professor at the International University in Germany. He has published widely on user-adaptive systems since the early 1980s. He was program co-chair of the Sixth International Conference on User Modeling. Email: jameson@cs.uni-sb.de, Homepage: http://www.cs.uni-sb.de/users/jameson/.

MA1

Search Algorithms for Quantum Computers

Tad Hogg

Quantum computers factor integers in polynomial time, a problem thought to be intractable for conventional machines. More relevant for AI is how rapidly they solve NP-hard combinatorial searches. Although unlikely to efficiently solve all NP problems, heuristic algorithms for quantum computers may offer substantial improvement for many searches that arise in practice by operating on the entire search space at once. Furthermore, heuristics pose less stringent hardware requirements than algorithms ignoring problem structure, thereby reducing the formidable challenge of building these machines.

This tutorial will describe the capabilities of quantum computers, e.g., testing exponentially many search states in about the same time conventional machines test just one.  Attendees will learn how to use these capabilities for search through a variety of examples including a heuristic for random 3-SAT near a phase transition in typical search cost. The tutorial will also cover theoretical and empirical techniques for evaluating such algorithms and a variety of open research questions that the AI community is well positioned to address.

The tutorial will assume some knowledge of combinatorial searches, such as SAT, and heuristic methods, such as hill-climbing and GSAT. Familiarity with quantum mechanics is not required. For further information see http://www.parc.xerox.com/hogg/ijcai01.html.

Tad Hogg is a member of the research staff at Xerox PARC. His research interests include distributed control with multiagent systems, ecommerce privacy mechanisms, search algorithms for quantum computers, and analogies with physical phase transitions found in combinatorial search problems. He holds a physics PhD from Stanford University.

MA2

Distributed Knowledge-Based Search

Jörg Denzinger

With the increasing availability of multiprocessor computers and networks of computers the wish to use the massive computing power provided by them has become stronger and stronger. With the maturity of the field multi-agent systems, we now have the conceptual and modeling tools to adequately describe and compare different approaches to solve AI problems while employing the additional “dimension”of teams of computers. Knowledge-based search is at the core of many AI systems and even a number of systems that have found their way into “mainstream” computer science, such as scheduling systems and many standard optimization systems.

This tutorial will provide a unified view on different concepts used to distribute knowledge-based search. We will introduce distributed search systems as cooperative multi-agent systems and concentrate on the communication and organization requirements of such systems. The general ideas behind the known distributed search systems will be presented within this multi-agent framework, and the systems will be classified into different categories.  For each category, we will present its basic idea independent from a particular application. We will present one typical homogeneous and one typical heterogeneous distribution concept for each category. Finally, we will discuss and compare the requirements, limitations, advantages and disadvantages of the different categories.

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 is a professor for AI and multi-agent systems at the University of Calgary. He was head of several DFG projects on distributed knowledge-based search and on the use of previous experiences to improve search controls. His research interests also include learning cooperative behavior of agents. Homepage: http://www.cpsc.ucalgary.ca/~denzinge/.

MA3

Empirical Methods in CS and AI

Paul Cohen, Ian Gent, and Toby Walsh

This tutorial will cover the basic principles of empirical studies, and methods for exploratory data analysis, experiment design, hypothesis testing, and modeling. We will cover the entire lifecycle of empirical studies, including the exploratory phase, which is usually not reported, and the phase in which a research question (why you are running the study in the first place) is turned into an experiment design. While this is not a crash course in statistical methods, we will introduce hypothesis testing and computer intensive statistical methods — a new family of tools particularly appropriate for AI research. Finally we will address questions that arise when trying to publish empirical work. Throughout, we will use examples from our own research: positive examples of good practice, and negative examples to demonstrate what not to do!

The tutorial will be suitable to a general AI audience, as very little background knowledge is assumed and the empirical methods discussed are generally useful. It builds upon the successful tutorial of the same theme presented at AAAI-2000.

Paul Cohen is a professor of computer Science at the University of Massachusetts, where he works on planning, simulation, and learning. Cohen's Empirical Methods for Artificial Intelligence, (The MIT Press) is a textbook on experiment design, data analysis, statistical modeling, and other empirical tools. Cohen is a Fellow of the American Association for Artificial Intelligence.

Ian Gent is a lecturer in computer science at the University of St. Andrews. His research has mainly been in combinatorial search in AI, in domains such as satisfiability and constraint satisfaction. He has done much empirical work, both with Toby Walsh and as part of the APES research group, http://apes.cs.strath.ac.uk.

Toby Walsh is an EPSRC Advanced Research Fellow at the Department of Computer Science (York). He has previously held postdoctoral posts at the Department of AI (Edinburgh), INRIA (Nancy), DIST (Genova), IRST (Trento), and the Department of Computer Science (Strathclyde). He too has done much empirical work with Ian Gent and as part of the APES research group, http://apes.cs.strath.ac.uk.

MA4

Integrating Lisp with the World

Vladimir A. Kulyukin

The rapid growth of diverse software technologies has made it hard and oftentimes impossible to develop sophisticated systems in one programming language. Lisp has been the language of choice for AI researchers and practitioners for over two decades. Yet the AI community has paid little to the integration of Lisp with mainstream development tools. As a consequence, these tools have started claiming the Lisp territory.

The purpose of this tutorial is to show that AI researchers and developers can and should use Lisp in conjunction with such mainstream languages as Java and C++. The tutorial will demonstrate how Lisp can utilize specific functionalities available through C++ and Java, and how C++ and Java can utilize software components written in Lisp. A special emphasis will be placed on CORBA, COM, and foreign function interfaces. Examples will include information retrieval, natural language processing, and robot control.

The tutorial will be of interest to researchers and developers who want to integrate Lisp-based solutions into applications written in mainstream languages. The tutorial will also be relevant to researchers and practitioners who want to master distributed computing with COM and CORBA.

Prerequisite Knowledge : Familiarity with Common Lisp. Knowledge of the Allegro Common Lisp IDE is helpful but not essential.

Vladimir A. Kulyukin is an Assistant Professor of Computer Science at DePaul University. He has a Ph.D. in Computer Science from the University of Chicago. His research interests are robotics, information retrieval, and computer vision.

MA5

Machine Learning for Categorization of Text Documents and Web Pages

Fabrizio Sebastiani & Alessandro Sperduti

In this tutorial we look at the main approaches that have been taken towards automatic text categorization within the general machine learning paradigm. A general presentation of the basic issues in document categorization will be followed by the presentation of basic (such as linear separators, decision trees, etc.) and advanced machine learning concepts and techniques (such as boosting, support vector machines, etc.). Then issues pertaining to document indexing, classifier construction, and classifier evaluation, will be discussed in detail, and a review of the current most relevant research in text categorization by machine learning tools will be presented. Finally, the special case of automatic classification of Web pages is considered and the concepts and techniques specifically devised for this case are discussed.

We assume that attendees will be familiar with basic knowledge of linear algebra, calculus, and probability.

Fabrizio Sebastiani has been a research associate of the Italian National Council of Research since 1988. He has published several papers in international journals and conferences in the areas of natural language processing, logic-based knowledge representation, information retrieval, and automated text categorization. On these two last topics he has taught several tutorials at international conferences and summer schools. His research interests concern information retrieval, machine learning, and automated text categorization.

Alessandro Sperduti is Associate Professor at the Computer Science Department, University of Pisa. His research interests include pattern recognition, machine learning, neural networks. He co-organized several workshops in these areas and served in the PC of neural networks conferences. More recently his research has focused on machine learning for the Web.

MP1

Ant Algorithms and Swarm Intelligence

Marco Dorigo

Ant colonies, and more generally social insect societies, are distributed systems that in spite of the simplicity of their individuals present a highly structured social organization. As a result of this organization, ant colonies can accomplish astonishingly complex tasks that in some cases far exceed the individual capacities of a single ant. The study of ant colonies behavior and of their self-organizing capacities is interesting for computer scientists because it provides models of distributed organization which are useful to solve difficult optimization and distributed control problems. This is particularly true in application environments in which rapid and autonomous adaptation to environmental changes, as well as robustness to system failures, are important features.

In this tutorial I will present some models derived from the observation of real ants and other insect societies, and I will explain how these models can be used to design multi-agent systems for the solution of problems like distributed and adaptive routing in Internet-like networks, combinatorial optimization, optimal allocation of resources, and distributed task allocation in a fleet of autonomous robots.

Marco Dorigo is a Senior Researcher for the Belgian FNRS. He is the inventor of the Ant Colony Optimization metaheuristic and author of the book Swarm Intelligence (Oxford University Press, 1999). He published more than twenty papers in international journals and conferences in the last five years on the tutorial subject.

MP2

Integration of Operations Research and AI Constraint- Based Techniques for Combinatorial Optimization

Michela Milano

The tutorial provides an overview of recent directions in the integration of Mathematical Programming (MP) techniques, used in Operations Research (OR), and Artificial Intelligence Constraint Satisfaction (CS) techniques for facing Combinatorial Optimization Problems (COPs).  The tutorial starts by reviewing basic concepts in COPs, CS, and Constraint Programming (CP). Participants are assumed to have some familiarity with these preliminaries.  OR concepts are described in more detail since we do not require any prerequisite knowledge of the field.  We describe (Mixed) Integer Programming and Linear Programming, their geometrical properties, and solving algorithms; cutting planes generation techniques are presented, branch-and-bound and branch-and-cut frameworks discussed; finally column generation approaches are introduced.  The aim of this introduction is not to provide details on how these techniques are implemented, but rather to explain how results can be exploited from a software engineering viewpoint.

In the second part, we compare Constraint Satisfaction and Optimization Problems, underlining differences and similarities from a modeling and solving perspective.  In the third part, we describe approaches toward integration that have been investigated to date, again from a modeling and solving viewpoint. Finally, we discuss open problems and research directions. We provide references to recent literature throughout.

Michela Milano received a PhD in 1998 from the University of Bologna, based on a thesis entitled Reasoning on Constraints in Constraint Logic Programming. Currently, she is a researcher in the same University. Her primary research interests are Constraint Programming, Constraint Satisfaction, and Optimization.

MP3

Knowledge Markup and Resource Semantics

Harold Boley, Stefan Decker, and Michael Sintek

Semi-formal and formal knowledge on the Web attracts increasing numbers of content providers, and much of the ongoing formalization can be done with AI knowledge representation techniques and by AI people. This tutorial introduces techniques for _knowledge markup_: how to map formal AI representations (e.g., logics and frames) to XML. It also explains _resource semantics_: how to describe heterogeneous Web resources using AI-inspired semantic RDF metadata.

We survey existing XML and RDF applications for knowledge bases/ontologies, deal with the acquisition and processing of these representations, go into agent architectures built around XML or RDF, and detail selected applications. A special emphasis will be on current efforts to define a shared markup language for realizing Tim Berners-Lee’s “Semantic Web” vision (e.g., DAML and OIL).

After the tutorial, participants will have absorbed the theoretical foundations as well as the practical use of knowledge markup and resource semantics; they will also be able to assess proposed XML and RDF applications for AI and to identify further applications of these techniques.

Participants should have some previous experience with knowledge representations (logics or frames) and markup languages (e.g., HTML).

Harold Boley has used markup techniques for knowledge representation and KR for resource semantics. He developed the Relational-Functional Markup Language (RFML) and started the Rule Markup Initiative (RuleML). He wrote invited papers explaining relationships between Logic Programming and XML as well as RDF. He has developed AI-oriented XML and RDF courses.  See http://www.dfki.uni-kl.de/~boley/.

Stefan Decker is a postdoctoral fellow at the department of computer science at Stanford University, where he leads the OntoAgents project in the DARPA DAML program. His research interests include knowledge representation, database systems for the Semantic Web, information integration and translation, and ontology articulation and merging.  See http://www-db.stanford.edu/~stefan and http://www.SemanticWeb.org.

Michael Sintek is the project leader of the FRODO (http://www.dfki.uni-kl.de/frodo/) project at DFKI Kaiserslautern where an XML/RDF-based framework for building distributed organizational memories is developed. His research interests include logic programming, knowledge representation, ontologies, and web technologies.  See http://www.dfki.uni-kl.de/~sintek/.

MP4

Practical Machine Learning for Software

Tim Menzies

Machine learning (ML) is not hard and should be a standard part of any software engineer’s toolkit. Software engineers can use machine learners to simplify systems development. This tutorial explains how to use ML to assist in the construction of systems that support classification, prediction, diagnosis, planning, monitoring, requirements engineering, validation, and maintenance. Case study material will be presented using examples from software fault estimation, software time estimation, software risk reduction, decision support systems for geologists, medical diagnostic systems, electrical diagnosis systems, and reverse engineering.

This tutorial is industrial practitioner-oriented. For example, most of its material is suitable for the AI-novice or the technical manager of software engineering projects. Also, the tutorial explores how to use machine learning in {\em data-starved} domains; lacks the large data sets needed traditional machine learning. Many software engineering companies operate in such data-starved domains, particularly the newer, smaller dot-com software companies. In such data-starved domains, learning must be preceded by a modeling process to generate a model we can use to generate data sets. Machine learning for software engineering is practical when both the modeling and learning stages are simple and inexpensive. This tutorial presents such simple and inexpensive techniques.

Dr. Tim Menzies developed this tutorial while working with NASA on using machine learning for software engineering. He holds a Ph.D. in AI, and has worked for many years as an OO and expert systems consultant. Dr. Menzies is an assistant professor at Electrical and Computer Engineering, University of British Columbia.

MP5

Tractability in Qualitative Spatial and Temporal Reasoning

Frank Anger, Hans Guesgen, & Gerard Ligozat

The field of qualitative temporal reasoning has been around in AI at least since Allen’s pioneering work 20 years ago. More recently, similar approaches have been introduced for reasoning about space. Some general threads have emerged, especially as far as complexity problems are concerned; hence an integrated presentation of the basic results becomes feasible in a systematic way.  The potential applications of the field include natural language understanding, planning, GIS, robotics, automatic mail processing, and human-machine communication, among others.

This tutorial will guide practitioners by describing the main methods and results in the field. It will introduce researchers and graduate students to an area with exciting open problems and perspectives.

Prerequisite knowledge: The tutorial assumes only a basic knowledge of AI and Knowledge Representation techniques. The logical notions will be introduced when required.

Dr. 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.

Dr. Hans Guesgen is an associate professor in computer science at the University of Auckland, NZ. 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.

Dr. Gerard Ligozat is a professor of 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.