AAAI-07 Tutorial Forum
The AAAI-07 Tutorials will be held Sunday and Monday, July 22–23, 2007, in Vancouver, British Columbia. AAAI-07 technical registrants may attend up to four consecutive tutorials for an additional registration fee. All tutorials will be held on the second level of the Hyatt Regency Vancouver. The titles of the tutorials are as follows:
Session I: Sunday, July 22
9:00 AM – 1:00 PM
- SA1: Autonomous Bidding Agents
Georgia A
Michael P. Wellman, Amy Greenwald, and Peter Stone - SA2: Information Integration on the Web
Georgia B
Subbarao Kambhampati and Craig Knoblock - SA3: Domain Modeling for Planning
Plaza A
Mark Boddy and Robert P. Goldman - SA4: Algorithms for Satisfiability Testing
Plaza B
Anbulagan and Jussi Rintanen
Session II: Sunday, July 22
2:00 PM – 6:00 PM
- SP1: Human-Computer Interaction Based on Discourse Modeling: Theory from AI and Application in HCI
Georgia A
Hermann Kaindl - SP2: Constraint Processing for Planning and Scheduling
Georgia B
Roman Barták - SP3: Beyond Traditional SAT Reasoning: QBF, Model Counting, and Solution Sampling
Plaza A
Ashish Sabharwal and Bart Selman - SP4: General Game Playing
Plaza B
Michael Thielscher
Session III: Monday, July 23
9:00 AM – 1:00 PM
- MA1: New Frontiers in Representation Discovery
Georgia A
Sridhar Mahadevan - MA2: Automatic Semantic Role Labeling
Georgia B
Scott Wen-tau Yih and Kristina Toutanova - MA3: Constraint-based Local Search in Comet
Plaza A
Pascal Van Hentenryck and Laurent Michel - MA4: Topics in Automated Planning and Scheduling.
Part 1: Planning and Scheduling with Over-Subscribed Resources, Preferences, and Soft Constraints
Plaza B
Minh Do, Terry Zimmerman, and Subbarao Kambhampati
Session IV: Monday, July 23
2:00 PM – 6:00 PM
- MP1: Managing Uncertainty and Vagueness in Semantic Web Languages
Georgia A
Thomas Lukasiewicz and Umberto Straccia - MP2: Representing, Eliciting, and Reasoning with Preferences
Georgia B
Ronen Brafman and Carmel Domshlak - MP3: Practical Statistical Relational AI
Plaza A
Pedro Domingos - MP4: Topics in Automated Planning and Scheduling.
Part II: Coordinating Distributed Planning and Scheduling Agents
Plaza B
Stephen F. Smith, Brad Clement and Keith S. Decker
TUTORIAL DESCRIPTIONS
Sunday, July 22
9:00 AM – 1:00 PM
SA1: Autonomous Bidding Agents
Michael P. Wellman, Amy Greenwald, and Peter Stone
This tutorial frames and motivates the problem of developing automated trading strategies for electronic markets. E-commerce increasingly makes use of autonomous bidding agents, computer programs that bid in electronic markets without direct human intervention. Automated bidding strategies for an auction of a single good with a known valuation are fairly straightforward to design; designing strategies for simultaneous auctions with interdependent valuations is a more complex undertaking.
This tutorial presents algorithmic advances and bidding agent architectures that have emerged from recent work in this fast-growing area of research in academia and industry. It surveys the state-of-the-art in analyzing strategies for basic market games, covers examples of more complex (intractable) market scenarios, and presents a general methodology (empirical and game-theoretic) for trading agent design and analysis.
After attending the tutorial, attendees will be equipped to enter into start developing their own agents for participation in future Trading Agent Competitions (TAC), and to fully appreciate the 2007 competition that will take place at AAAI.
Michael P. Wellman received a Ph.D from the Massachusetts Institute of Technology in 1988 for his work in qualitative probabilistic reasoning and decision-theoretic planning. From 1988 to 1992, Wellman conducted research in these areas at the USAF’s Wright Laboratory. For the past 15 years, his research has focused on computational market mechanisms for distributed decision making and electronic commerce. As chief market technologist for TradingDynamics, Inc. (now part of Ariba), he designed configurable auction technology for dynamic business-to-business commerce. Wellman is chair of the ACM Special Interest Group on Electronic Commerce (SIGecom), and of the Association for Trading Agent Research — the organization that governs the annual Trading Agent Competition. He is a Fellow of AAAI and ACM.
Amy Greenwald is an Alfred P. Sloan Research Fellow and assistant professor of computer science at Brown University in Providence, Rhode Island. Her primary research area is the study of economic interactions among computational agents. Her primary methodologies are game-theoretic analysis and simulation. Her work is applicable in areas ranging from dynamic pricing to autonomous bidding to transportation planning and scheduling. She was awarded a Sloan Fellowship in 2006; she was nominated for the 2002 Presidential Early Career Award for Scientists and Engineers (PECASE); and she was named one of the Computing Research Association’s Digital Government Fellows in 2001. Before joining the faculty at Brown, Greenwald was employed by IBM’s T.J. Watson Research Center, where she researched information economies. Her paper entitled “Shopbots and Pricebots” (joint work with Jeff Kephart) was named Best Paper at IBM Research in 2000.
Peter Stone is an Alfred P. Sloan Research Fellow and assistant professor in the Department of Computer Sciences at the University of Texas at Austin. He received his Ph.D in computer science in 1998 from Carnegie Mellon University. From 1999 to 2002 he was a Senior Technical Staff Member in the Artificial Intelligence Principles Research Department at AT&T Labs – Research. Peter’s research interests include machine learning, multiagent systems, robotics, and e-commerce. In 2003, he won a CAREER award from the National Science Foundation for his research on learning agents in dynamic, collaborative, and adversarial multiagent environments. In 2004, he was named an ONR Young Investigator for his research on machine learning on physical robots. Most recently, he was awarded the prestigious IJCAI 2007 Computers and Thought award.
SA2: Information Integration on the Web
Subbarao Kambhampati and Craig Knoblock
The explosive growth of the web resulted in thousands of structured queryable information sources on the Internet, and the promise of unprecedented information-gathering capabilities to lay users. Unfortunately, the promise has not yet been transformed into reality. While there are sources relevant to virtually any user queries, the morass of sources presents a formidable hurdle to effectively accessing the information. One way of alleviating this problem is to develop web-based information integration agents, which take the user’s query, and access the relevant sources to answer the user’s query efficiently.
This tutorial will survey the research and systems for web-based information integration. There is a wide range of technical problems that must be addressed to integrate the diverse sources. We will describe approaches from both the Database and Artificial Intelligence communities that address these various issues. These topics include the relationship to database integration and information retrieval, languages for mediation and exchange, machine learning techniques for generating wrappers, terminology alignment for combining data across sources, query optimization, and query execution. We will also describe the various integration systems and where they fit in within the space of technical approaches. Finally, we will discuss important application areas — such as bioinformatics and geospatial data integration.
Subbarao Kambhampati is a professor of computer science in the School of Computing and Informatics at Arizona State University. His research interests are divided between artificial intelligence (automated planning, machine learning) and data bases (data and information integration). He is a 1994 NSF young investigator and a 2004 AAAI Fellow and cochaired the 2005 National Conference on Artificial Intelligence.
Craig Knoblock received his Ph.D. from Carnegie Mellon in 1991 and is currently a research professor in computer science at the University of Southern California. He has published extensively in the areas of information integration, planning, and machine learning. He is an AAAI fellow and currently serves as president of ICAPS.
SA3: Domain Modeling for Planning
Mark Boddy and Robert P. Goldman
In this tutorial, we will present examples of modeling challenges drawn from a broad range of practical applications, including computer security, manufacturing, UAV control, and space operations, as well as some of the domains used in the International Planning Competition. For each of these applications, we will discuss and illustrate the pros and cons of various modeling approaches, including PDDL, various HTN schema representations (for example, SHOP2, ACT, O-Plan) logical formalisms (TAL), and constraint-based representations such as NASA’s NDDL and LAAS’ IxTeT input language.
Prerequisite knowledge for this tutorial includes familiarity with planning at the level of an undergraduate course in AI, some knowledge of first-order logic, and at least a sketchy knowledge of search.
This tutorial is an updated version of a tutorial previously presented at ICAPS in 2005. In addition to incorporating results from the intervening two years, we are adding a “practicum” in which tutorial participants will be able to try their hands at using a variety of formal representations to model aspects of real-world planning and scheduling systems. Additional details on logistics for this will be forthcoming, but it is likely that participants will need to have their own computers.
Mark Boddy is an internationally recognized expert in the theory and practice of building planning and scheduling systems. Relevant research interests include planning under uncertainty, integrations of constraint programming and math programming, and distributed planning and scheduling. His applications experience spans a wide range of manufacturing and operations domains.
Robert Goldman is a senior scientist at SIFT, LLC, a small research company in Minneapolis that develops intelligent control systems. He is currently working on a planner-based systems for Uninhabited Aerial Vehicle (UAV) operations, having already built an extensive system for this purpose. He is also working on a planner for web services composition in DARPA’s Integrated Learning program. Goldman’s primary research focus is applications of planning systems for controlling autonomous systems, and interfaces between planning and control. Prior to joining SIFT, he was a Senior Principal Research Scientist at Honeywell Labs, where he worked on planning under uncertainty, manufacturing scheduling, and real-time controller synthesis, in applications including UAV control, manufacturing, and military logistics. Before working at Honeywell Labs, Goldman was a faculty member of the Computer Science department at Tulane University.
SA4: Algorithms for Satisfiability Testing
Anbulagan and Jussi Rintanen
The increased importance of SAT for AI during the last decade is due to rapid development of more powerful algorithms for SAT and the application of SAT in solving increasingly challenging problems in different areas of AI, paralleling applications in other areas of computer science such as automated deduction, bioinformatics, hardware and software verification, FPGA routing, planning, and knowledge discovery.
The tutorial presents fundamentals of SAT and a comprehensive survey of the state-of-the-art in algorithms for SAT. We will focus on the main approaches, including stochastic local search (SLS), clause learning, heuristics, look-ahead algorithms, and the use of resolution-based preprocessors. We will discuss the current and future research directions both on designing more efficient SAT solvers and applying them to large-scale real-world problems. The tutorial assumes a basic knowledge of classical propositional logic and search algorithms.
Anbulagan is a researcher in the logic and computation program at National ICT Australia (NICTA) in Canberra. He is involved in the NICTA’s G12-Constraint Programming Platform project. His research interests include SAT solving algorithms, search in AI, diagnosis and planning. He has more than 10 years of experience in SAT solving.
Jussi Rintanen earned his doctoral degree at the Helsinki University of Technology in 1997. Since then he has held research and academic positions at the universities of Ulm and Freiburg in Germany. Since January 2006 Rintanen is a senior researcher in the Knowledge Representation and Reasoning program at the National ICT Australia in Canberra where he does research on propositional reasoning techniques in planning, diagnosis and other applications.
Sunday, July 22
2:00 PM – 6:00 PM
SP1: Human-Computer Interaction Based on Discourse Modeling: Theory from AI and Application in HCI
Hermann Kaindl
This intermediate-level tutorial shows how human-computer interaction can be based on discourse modeling, even without employing speech or natural language. Communicative acts as abstractions from speech acts can model basic building blocks (“atoms”) of communication, like a question or an answer. When, for example, a question and an answer are glued together as a so-called adjacency pair, a simple “molecule” of a dialogue is modeled. Deliberately complex discourse structures can be modeled using relations from Rhetorical Structure Theory (RST). The content of a communicative act can refer to ontologies of the domain of discourse. Taking all this together, we created a new discourse metamodel that specifies what discourse models may look like. Such discourse models can specify an interaction design. This tutorial also sketches how such an interaction design can be used for automated user-interface generation. In effect, such user interfaces are generated from models underpinned through theories from artificial intelligence (AI), and these theories are applied in human-computer interaction (HCI).
There are no prerequisites such as knowledge about AI or HCI in general. This tutorial will consist of lectures, group exercises and discussions. Concrete examples of actual generated user interfaces will be presented as well.
Hermann Kaindl joined the Vienna University of Technology in Vienna, Austria, in early 2003 as a full professor. Prior to moving to academia, he was a senior consultant with the division of program and systems engineering at Siemens Austria. There he has gained more than 24 years of industrial experience.
SP2: Constraint Processing for Planning and Scheduling
Roman Barták
Constraint satisfaction emerged from AI research and nowadays it contributes to many fields such as planning, scheduling, and assignment problems, circuit design, network management and configuration, interactive graphics, molecular biology etc. The goal of the tutorial is to explain mainstream algorithms behind constraint satisfaction. The emphasis is put to modelling planning and scheduling problems with constraints and to special filtering and search techniques developed for these areas.
The tutorial is divided into two main parts. First, the constraint satisfaction technology is explained in general. The mainstream search and propagation algorithms are presented in an incremental nature showing how more advanced algorithms are built up on improvements of the simpler algorithms. The second part is specialised to planning and scheduling problems. The constraint models of these problems will be described together with several filtering and search techniques developed for these models.
The tutorial is targeted to a broad planning and scheduling community, in particular to those who are not familiar with details of constraint satisfaction. The audience will take away a basic understanding of how constraints work with more details on special constraints for planning and scheduling. No prior knowledge of constraint programming is required.
Roman Barták is an associate professor at Charles University in Prague (Czech Republic). His work focuses on constraint satisfaction techniques and their application to planning and scheduling. He was a main architect of the constraint-based scheduling engine developed by Visopt BV. Roman Barták is an author of the On-line Guide to Constraint Programming.
SP3: Beyond Traditional SAT Reasoning: QBF, Model Counting, and Solution Sampling
Ashish Sabharwal and Bart Selman
Since the early 1990s, algorithms for the Boolean satisfiability problem (SAT solvers) have made a very visible impact on the state of the art in automated reasoning, especially in application areas of planning, scheduling, and verification. While SAT methodologies still form an intriguiging research domain, this tutorial will address three problems that go beyond SAT and will lie at the heart of the next generation automated reasoning systems. These are, Quantified Boolean Formula (QBF) reasoning, counting the number of models (solutions) of a problem, and uniformly sampling the solutions. These problems present fascinating challenges and pose new research questions relevant to anyone interested in SAT methods.
This tutorial will provide students and researchers new to this area a basic understanding of the problems and solution techniques, and outline for those already familiar with SAT solvers the key challenges and bottlenecks involved in transitioning from SAT to problems beyond SAT. We will also address the theoretical hardness of these problems, the resulting scalability challenge, and promising recent techniques that trade off precision with efficiency in a controlled manner.
Prerequisite knowledge: Basic understanding of backtrack search and Boolean formulas. Familiarity with SAT techniques will be helpful but not essential. No prior knowledge of QBF, counting, or sampling will be assumed.
Ashish Sabharwal is a postdoctoral associate in computer science at Cornell University. He received his Ph.D. from the University of Washington in 2005. He has (co)authored nearly 20 publications, including two best paper awards. His research interests include artificial intelligence, automated reasoning, and theoretical computer science, with recent focus on SAT, QBF, and CP.
Bart Selman is a professor of computer science at Cornell University. He was previously at AT&T Bell Laboratories. His research interests include reasoning, planning, knowledge representation, and connections to statistical physics. He has (co)authored over 100 publications, including six best paper awards. He has received the Cornell Miles Excellence in Teaching Award, the Cornell Outstanding Educator Award, an NSF Career Award, and a Sloan Research Fellowship. He is a Fellow of AAAI and AAAS.
SP4: General Game Playing
Michael Thielscher
General game playing is concerned with the development of systems that can play well arbitrary games solely by being given the rules of a game. This raises a number of issues different from traditional research in game playing, where it is assumed that the rules of a game are known to the programmer. Systems able to play hitherto unknown games cannot be given game-specific knowledge. They rather need to be endowed with high-level cognitive abilities such as general strategic thinking and abstract reasoning. This is why general game playing has recently been proposed as one of the grand contemporary AI challenges, encompassing a variety of research areas such as knowledge representation and reasoning, heuristic search and planning, game playing, and learning. General game playing has a number of immediate potential applications, including game playing programs that can be adapted by their users and advice giving systems for negotiations, marketing strategies, pricing etc.
The tutorial is directed at every AI researcher who wants to gain an insight into general game playing as a method to formalize and solve general decision-making problems. The only required background is some basic knowledge of standard first-order logic.
Michael Thielscher is a professor at Dresden University and head of the Computational Logic Group. His research is mainly in knowledge representation, cognitive robotics, commonsense reasoning, game playing, and constraint logic programming. He is coauthor of the program FLUXPLAYER, which in 2006 was crowned the world champion at the Second General Game Playing Competition in Boston.
Monday, July 23
9:00 AM – 1:00 PM
MA1: New Frontiers in Representation Discovery
Sridhar Mahadevan
The problem of learning representations has long been considered a fundamental problem — some would say “the fundamental problem” — of AI. This tutorial provides a state-of-the-art overview of new emerging research directions in representation discovery for real-world stochastic environments, which build on recent developments in mathematics — principally harmonic analysis and spectral graph theory — as well as machine learning and statistics. Harmonic analysis is a field of mathematics including Fourier and wavelet analysis, which has played a central role in science and technology for two centuries. Spectral graph theory is the study of graphs using the tools of linear algebra. Recent advances in harmonic analysis have generalized the traditional analytic tools of Fourier and wavelet analysis from restricted Euclidean spaces to more general discrete and continuous state spaces with arbitrary topology. These advances yield a unified framework for jointly learning representation and behavior. The new insights can be used to design a new generation of AI planning and search agents that solve tasks in discrete and continuous real-world noisy state spaces by discovering novel representations. These developments may also profoundly influence research in other fields including activity modeling, computer graphics, information retrieval, perception, robotics, and sensor networks.
Sridhar Mahadevan of the University of Massachusetts, Amherst has published extensively in several areas, including machine learning, planning, robotics, Markov decision processes, and reinforcement learning. He was an invited speaker at AAAI 2005, and a tutorial speaker at ICML 2006 and IJCAI 2007.
MA2: Automatic Semantic Role Labeling
Scott Wen-tau Yih and Kristina Toutanova
The goal of the tutorial is to introduce the AI community to the new field of semantic role labeling. Semantic role labeling has recently received significant interest in the natural language processing community. The goal of semantic role labeling is to map natural language sentences to domain-independent semantic representations, which facilitate applications like information extraction, question answering and knowledge representation.
The tutorial will provide an introduction to the task of semantic role labeling and an in-depth presentation of existing approaches. We will first describe the problem and history of semantic role labeling, and introduce existing corpora and other related tasks. Next, we will provide a detailed survey of state-of-the-art machine learning approaches to building a semantic role labeling system. Finally, we will conclude the tutorial by discussing directions for improving semantic role labeling systems and the application to other problems, such as information extraction and textual reasoning.
The tutorial assumes basic knowledge of machine learning algorithms for independent and sequence classification, such as logistic regression, support vector machines, and conditional Markov models. Familiarity with basic linguistic syntax concepts will be helpful, but not required.
Scott Wen-tau Yih is a researcher in the machine learning and applied statistics group at Microsoft Research. His research focuses on different problems in natural language processing and machine learning. The semantic role labeling system he built at UIUC was the best system in the CoNLL-05 shared task.
Kristina Toutanova is a researcher in the natural language processing group at Microsoft Research. Her areas of expertise include semantic role labeling, syntactic parsing, machine learning, and machine translation. The semantic role labeling system she built at Stanford was the runner-up system in the CoNLL-05 shared task.
MA3: Constraint-based Local Search in Comet
Pascal Van Hentenryck and Laurent Michel
Constraint-based local search, the idea of using constraints to describe and control local search, combines the high-level modeling and control structures of constraint programming with the computational model of local search. Constraint-based local search enables combinatorial optimization applications to be expressed in terms of modeling and search components. The modeling component conveys the combinatorial structure of the applications, while the search component uses the model to drive the search toward high-quality solutions. As a result, constraint-based local search provides a number of fundamental benefits ranging from software engineering concerns such as expressiveness, modularity, and reuse to computational properties such as incrementality, efficiency, and scalability.
This tutorial is a comprehensive introduction to constraint-based local search and its implementation in the Comet programming language and system. It discusses the constraint-based architecture, its modeling concepts (for example, differentiable constraints and objectives), and its advanced control structures. The architecture is then illustrated on a number of realistic applications in resource allocation, combinatorial design, facility location, sequencing, and scheduling. The tutorial also reviews novel opportunities offered by constraint-based local search, including the synthesis of local search algorithms from high-level models.
Pascal Van Hentenryck is professor of computer science at Brown University. Before coming to Brown in 1990, he spent four years at the European Computer-Industry Research Center (ECRC), where he was the main designer and implementator of the CHIP programming system, one of the pioneering constraint programming systems. In the last decade, he has built a number of influential systems, including Numerica, OPL, and Comet. Pascal is the author of five books all published by The MIT Press and the recipient of an NSF National Young Investigator award, the 2002 INFORMS ICS Award for research excellence at the interface between computer science and operations research, and the 2006 ACP Research Excellence Award in constraint programming. He is on the board of directors of the INFORMS Computing Society.
Laurent Michel received his undergraduate degree from the FUNDP in Namur, Belgium. He later received an Sc.M. (’96) and a Ph.D. (’99) degree in computer science from Brown University. He joined the Computer Science and Engineering Department of the University of Connecticut in 2002. His research interests focus on the design and implementation of domain specific languages for combinatorial optimization. He coauthored two MIT Press books with Pascal Van Hentenryck focusing on constraint-based methodologies and associated systems. Over the last decade, he contributed to several influential systems and is the recipient of an NSF CAREER Award for his projects in Constraint Programming.
MA4: Topics in Automated Planning and Scheduling
Minh Do, Terry Zimmerman, and Subbarao Kambhampati
Part 1: Planning and Scheduling with Over-Subscribed Resources, Preferences, and Soft Constraints
This tutorial will focus on aspects of contemporary planning and scheduling problems that reside on common ground that is increasingly of interest to both communities; over-subscribed resources, preferences, and soft constraints. The term “over-subscribed” is applied to problems featuring more tasks to be performed over a given time frame (scheduling) or goals to be achieved (planning) than can be feasibly accommodated by available resources. Preferences, either user-specified or those that arise in the pursuit of maximizing quality/utility, are naturally associated with over-subscription problems as guides to selection of goal sets or action trajectories most likely to satisfy specified objectives.
We will discuss recent planning/scheduling evolutions that handle over-subscribed problems by modeling a subset of goals or tasks as soft constraints, in contrast to more traditional frameworks in which planning goals and scheduling tasks are hard constraints and all must be satisfied. Mixing soft and hard constraints motivates consideration of novel objective functions for choosing the “best” set of goals to achieve. Recent applications of soft constraints in modeling facilitating and hindering interactions between domain activities will also be covered. The material presented will be grounded in experience from ongoing programs such as the International Planning Competitions and the DARPA Coordinators program.
Minh B. Do is on the research staff of the Palo Alto Research Center (Xerox PARC), in the Embedded Reasoning Area. His research interests encompass issues related to planning in a dynamic environment with complex objectives and constraints. He will cochair the next International Planning Competition in 2008.
Terry Zimmerman’s current research focuses on scalable AI planning and scheduling in dynamic environments for both centralized and distributed, multiagent contexts. He has also published in the area of integrating planning and scheduling methodologies.
Subbarao Kambhampati is a professor of computer science in the School of Computing and Informatics at Arizona State University. His research interests are divided between artificial intelligence (automated planning, machine learning) and data bases (data and information integration). He is a 1994 NSF young investigator and a 2004 AAAI Fellow and cochaired the 2005 National Conference on Artificial Intelligence.
Monday, July 23
2:00 PM – 6:00 PM
MP1: Managing Uncertainty and Vagueness in Semantic Web Languages
Thomas Lukasiewicz and Umberto Straccia
There is currently a strong interest in using and extending AI techniques, systems, and concepts to the World Wide Web. In particular, managing uncertainty and/or vagueness is starting to play an important role in Semantic Web research.
The tutorial presents the state of the art in representing and reasoning with uncertain and/or vague knowledge in the semantic web. The goal of the tutorial is to make attendees familiar with the concepts and techniques for representing and reasoning with uncertain and vague knowledge in semantic web ontology and rule languages, such as OWL, RuleML, and SWRL, which will help the attendees to gain insights on the main features of the formalisms and tools proposed so far.
The tutorial requires no specific prerequisite knowledge, except for basic knowledge in first-order logic. It will start by introducing basic characteristics and observations on the semantic web, and the technical details will be self-contained.
Thomas Lukasiewicz holds a Heisenberg professorship by the DFG at the Department of Computer and System Sciences of the University of Rome “La Sapienza” and at the Institute of Information Systems of the Vienna University of Technology. His main research interests are in AI, the semantic web, and databases.
Umberto Straccia is a researcher at ISTI-CNR. His research interests include in the broad sense knowledge representation and reasoning (KRR), semantic web and information retrieval (IR), and, in particular, in logic programming, description logics, the management of uncertainty and imprecision within logic-based approaches to multimedia information retrieval.
MP2: Representing, Eliciting, and Reasoning with Preferences
Ronen Brafman and Carmel Domshlak
When we design an agent that automatically shops on the web or controls a rover on Mars, we don’t want it to buy any item or conduct any experiment. We want it to buy the best available item and conduct the most useful experiment. In short, we want it to act optimally. But acting optimally on behalf of a user requires understanding of that user’s goals and preferences. How can an agent obtain this information efficiently when acting on behalf of a lay user? How can this be done with a minimal effort on the part of the user? How does one represent preference information compactly and reasons with it effectively? These questions drive the research conducted in the area of preference modeling, elicitation, representation, and reasoning techniques. The tutorial will survey some of the major developments in this area, discussing the problems of decision-making under certainty and uncertainty, and explaining some practical applications of each of these settings and their characteristics. Much emphasis will be placed on graphical models of preference and models of qualitative preferences that are especially suitable for lay users, as well as on algorithmic techniques for preference elicitation and reasoning.
Ronen Brafman is a professor of computer science at Ben-Gurion University working in the area of automated planning and decision making. He is a coinventor of the CP-net model and served as consultant to NASA and Shopping.Com, among others. He coorganized the Dagstuhl’04 and IJCAI’05 workshops on preferences, presented tutorials on preferences in CP’03, UAI’04, and IJCAI’05, and is an associate editor of JAIR and member of the AI Journal editorial board.
Carmel Domshlak is a senior lecturer at the Faculty of Industrial Engineering and Management in Technion. His research interests are in modeling and reasoning about preferences, planning, and reasoning about action, and he is a member of the JAIR editorial board.
MP3: Practical Statistical Relational AI
Pedro Domingos
Most AI applications require a combination of logical and statistical techniques, but only recently has this become a practical option. This tutorial covers a sufficient subset of the relevant concepts and techniques. We begin with an introduction to the four foundational areas of statistical relational AI: logical inference, inductive logic programming, probabilistic inference, and statistical learning. We then show how to combine them in a principled and efficient way, with Markov logic as the foundation. Finally, we show how to apply these techniques to a wide variety of problems in AI, from natural language processing to planning, using the Alchemy open-source software as a concrete tool. The audience will gain the ability to efficiently develop challenging AI applications, and the background to do research in statistical relational AI. The tutorial assumes knowledge at the level of an introductory AI course, including basic logic, probability, and calculus.
Pedro Domingos is an associate professor at the University of Washington. He received his PhD from the University of California at Irvine, and has (co) authored over 100 technical publications. He was program cochair of KDD-2003, and has served on the program committees of six of the last nine AAAIs.
MP4: Topics in Automated Planning and Scheduling
Part II: Coordinating Distributed Planning and Scheduling Agents
Stephen F. Smith, Brad Clement and Keith S. Decker
Many practical problems in industry, space and the military require coordinated action by multiple independent agents. This general class of problem, which requires agents to jointly establish synchronized courses of action and then manage them in response to execution dynamics, is the focus of research in distributed planning and scheduling. Interest in this research area has been increasing in recent years with the emergence of sensing technologies and data processing infra-structure that are making execution status information readily available in a broad range of applications. The opportunity exists like never before to capitalize on techniques for coordinating distributed planning and scheduling agents.
This tutorial will survey work in the field of distributed planning and scheduling, emphasizing approaches and frameworks that are grounded in an executing environment. We consider formulations of this problem that have emerged from both planning and scheduling sub-disciplines, summarize basic multiagent design and use issues and tradeoffs, and examine several real-world distributed planning and scheduling applications. We then review the history of research contributions in this area, describe a number of notable frameworks and systems, and characterize the current state of the art. We conclude by identifying important open research questions in distributed planning and scheduling.
Prerequisite knowledge: Basic knowledge of artificial intelligence, planning and scheduling techniques will be helpful, but not necessary.
Brad Clement is a senior member of the Artificial Intelligence Group at the Jet Propulsion Laboratory. He leads projects on distributed continual planning applied to simulated spacecraft and rovers for Mars, on scheduling resource allocation for the Deep Space Network planning under uncertainty, and abstraction in planning and coordination.
Keith Decker is an associate professor in the Department of Computer and Information Sciences at the University of Delaware. His research interests include cooperative distributed problem solving, multiagent systems, computational organization design, real-time AI, parallel and distributed planning and scheduling, and distributed information gathering.
Stephen Smith is a research professor in the Robotics Institute at Carnegie Mellon University. Smith’s research focuses broadly on the theory and practice of next-generation planning and scheduling systems. His current interests include constraint-based search and optimization, execution-driven planning and scheduling, adaptive and self-organizing systems, and agent-based frameworks for distributed task and resource allocation.
AAAI-07 Tutorial Program Cochairs
- Carla Gomes
Department of Computer Science
5133 Upson Hall
Cornell University
Ithaca, NY 14853, USA
607-255-9189
607-255-4428 (fax)
gomes@cs.cornell.edu - Andrea Danyluk
Department of Computer Science
47 Lab Campus Drive
Williams College
Williamstown, MA 01267
413-597-2178
413-597-4250 (fax) andrea@cs.williams.edu