The following tutorials will be presented at ICAPS 2010:
- T1: Planning for the Future Internet of Services (Paolo Traverso) - slides
- T2: Planning and Scheduling for Traffic Control (Scott Sanner) - slides
- T3: Monte-Carlo Planning: Basic Principles and Recent Progress (Alan Fern) - slides
- T4: Landmarks in Heuristic-Search Planning (Erez Karpas and Silvia Richter) - slides
T1: Planning for Future Internet Services by Paolo Traverso
A lot of work has been done so far in the field of planning for web or software services. In this work, major tasks can be described in a planning framework: modeling of software services leads to a planning domain, their automated composition can be done by plan generation, their monitoring becomes monitoring of plan executions, and adaptation can done by re-planning.
Things change radically when we move to the framework envisioned by Future Internet. One of the major promises of the vision of Future Internet is the so called “Internet of Services”, where applications “live” in the network and are available to end users as “real services” are available today to consumers in everyday life. According to this vision, software services are just software components that provide electronic access to “real services” (e.g., a software service for travel booking allows us to access the actual service behind it, namely “the possibility of traveling”). “Real services” are however very different from the corresponding software services, since they differ in their main characteristics, such as their duration, their accessibility, their constraints and conflicts, and their connection with the real world, which makes them highly dynamic. This new vision requires a shift in the research approach, as well as in the corresponding planning framework: Modeling should describe how the use of real services affects their consumers; Composition does not consist anymore in the generation of a new composed service, it becomes a task that finds relations among services based on emergent needs, constraints, opportunities of the consumers; Monitoring should not check software executions but rather focus on properties of the physical environment where the real services operate; Adaptation should move from reaction to changes in software services to reaction to changes in real services, in the physical environment where they operate, and to users’ behaviors.
In this tutorial I will briefly summarize the traditional approaches to planning for software services, and I will then focus on the new research challenges for the future internet of services and how they are related to planning.
T2: Planning and Scheduling for Traffic Control by Scott Sanner
The ubiquity of urban traffic congestion and the fundamental impact that better traffic control can have on urban environments makes it an important research topic for the automated planning and scheduling community. To reduce traffic congestion by just 10% can have massive economic, environmental, and social benefits for urban communities. While a great deal of traffic theory has been developed over the years, the practical techniques utilized in most urban traffic control situations are surprisingly simple and rely on extensive manual tuning via trial and error; in a nutshell, there is a lot of room for improvement for automated traffic control techniques that can deal with the full complexities of traffic management in an online control setting. The purpose of this tutorial is to describe the theory of traffic simulation (basic modeling including micro- and macro-simulation) and control (single and multi-intersection control from both theoretical and practical perspectives) in order to expose the research topics (extremely large continuous state spaces, highly parallel continuous action spaces with nonlinear effects) that need to be addressed if the planning and scheduling community is to make progress in this challenging, but high-impact application domain.
T3: Monte-Carlo Planning: Basic Principles and Recent Progress by Alan Fern
Many planning applications are difficult to model in standard domain description languages. However, with out the limitations of a particular language, it is often possible to obtain or construct an exact or approximate simulator of the application domain. Monte-Carlo planning is an area that studies algorithms for sequential decision making when such a simulator is available. In recent years, advances in Monte-Carlo planning have lead to significant advances in applications ranging from computer networking, to real-time strategy games, to computer Go. This tutorial will cover the basic principles and theory underlying Monte-Carlo planning and also the recent advances. Emphasis will be placed on practical approaches with illustrating applications. The tutorial will start from first principles and will not assume prior knowledge of Monte-Carlo techniques.
T4: Landmarks in Heuristic-Search Planning by Erez Karpas and Silvia Richter
The recent past has seen a resurge of interest in landmarks for heuristic-search planning. Landmarks are subgoals that have to become true at some point during any plan for a given task. They can be used in various ways to assist the search for a plan. This tutorial will give an overview of how landmarks can be identified for a given task and how they may be exploited for planning. In detail, the following topics will be covered:
- Definitions of landmarks and orderings, including action landmarks.
- Landmark discovery procedures, including back-chaining from goals, path analysis in domain transition graphs, and forward propagation of information in the planning graph.
- Methods to exploit landmarks during planning, including as intermediate goals, in the LAMA heuristic, as admissible heuristic, and as problem enrichment via temporal formulas.