ICAPS 2007 Tutorials
September 22, afternoon
- T5. Fuzzy Temporal Reasoning
Massimiliano Giacomin and Marco Falda
More...
September 23, morning
-
T1. Approximation Based Reasoning and Conformant/Conditional Planning -
Bridging Reasoning About Actions & Changes and Planning
Son Cao Tran
More... - T3. Probabilistic Temporal Planning
Mausam, David E. Smith, and Sylvie Thiébaux
More...
September 23, afternoon
- T2. Advances in Search and Inference for Combinatorial Optimisation
Rina Dechter, Radu Marinescu, Robert Mateescu
More... - T4. Learning Techniques in Planning
Sungwook Yoon and Subbarao Kambhampati
More...
T1. Approximation Based Reasoning and Conformant/Conditional Planning ---
Bridging Reasoning About Actions & Changes and Planning
Goal:
This tutorial introduces a new approach to conformant planning. Instead of searching through the belief-state space (2^2^n belief- states for problems with n state variables) for conformant plan, we show that it is possible to limit the search in the space of approximation states (3^n states). Its goal is to provide the audience with the recent advancements in reasoning about actions and changes that are directly related to the development of conformant planning systems and can be applied in other planning systems.Targeted Audience:
Researchers interested in reasoning about ations and changes in the presence of incomplete information and the development of conformant planning systems. Developers interested in new ways of finding plans.Abstract:
The thesis of this tutorial is that the study in reasoning about actions and changes can significant contributions to the development of conformant planning systems in particular and planning systems in general.Over the years, several conformant planning systems employing different representation languages and different methods of reasoning have been developed. On the one hand, we can find many planning systems (e.g. CFF and POND) employ PDDL, a simple representation language with limited expressive power, and use sophisticated heuristics in the search for plans in the space of belief-states. On the other hand, we can find other systems which use a specialized representation language (e.g. the language used by the systems PKS and KACMBP) and employ sophisticated reasoning algorithms in the search for conformant plans. While the first approach relies on heuristic, the second one seems to gain performance through specialized algorithms. Yet, there is no documentation on the impact of reasoning method on the performance of planning systems.
It is also interesting to observe that theoretical results in reasoning about actions and changes do not often find their ways to be implemented in planning systems. As an example, several solutions to the ramification problem have been discussed and many languages allowing the representation and reasoning with arbitrary state constraints have been developed. Furthermore, reports on the usefulness of being able to deal directly with state constraints in planning have been published. Yet, the majority of top planning systems do not accept inputs containing arbitrary constraints. This raised the question of how theoretical studies in reasoning about actions and changes can be useful for the development of planning systems.
This tutorial addresses the above issue by presenting the development of several conformant planners. The key reasoning modules of these planners are based on the approximations obtained during our study on reasoning about actions and changes. As such, these planners are the "by-product" of our investigation of the problem in reasoning with incomplete information. We will discuss possible improvments for existing conformant planners.
The tutorial will include a discussion on the different problems in reasoning about actions and changes (frame problem, qualification problem, and ramification problem) and their well-known solutions.
The tutorial will be continued with the various reasoning methods in the presence of incomplete information and sensing actions. Possible world semantics and approximation based reasoning will be discussed.
The tutorial will also include a discussion of methods for complete reasoning based on approximation and its application to conformant planning. Experimental evaluation will be provided. Applications to classical planners will also be dicussed. In each of the above discussions, complexity results for the planning problems will be provided, whenever it is appropriate.
Detailed outline:
- Reasoning about actions and changes
- Fundamental problems
- Action language A (Syntax & Semantics) How the fundamental problems are solved?
- Planning and its complexity (the case with complete information) (brief)
- Reasoning with state constraints and incomplete information
- Possible world semantics
- Approximations
- Planning and its complexity (brief)
- Reasoning with disjunctive information
- Approaches to conformant planning as search in the space of belief space
- Conformant planning as seach in the space of approximation states
- Completeness results for reasoning using the approximation
- Theories without state constraints
- Theories with state constraints
- Experemental results (brief)
- Possible applications of the results in planning problem simplification
- Outlook
Brief Resume:
Tran Cao Son received his PhD in Spring 2000 from the University of Texas at El Paso. He worked as Postdoctoral for almost a year at Stanford University before joining New Mexico State University in Spring 2001, where he is now an associate professor in Computer Science. His main research interests are in logic programming, commonsense reasoning, knowledge representation, and intelligent agents. He has papers accepted for/in AI/KR-conferences/journals (IJCAI, AAAI, KR, AIJ, JAIR, ETAI) and in logic programming and nonmonotonic reasoning conferences/journals (TPLP, TOCL, ICLP, ILPS, JELIA, LPNMR). He has given several talks at major conferences such as AAAI, KR, and LPNMR. He has prepared and delivered a tutorial on answer set programming at the conference ICTAC 2005. While visiting the University of Western Sydney in Summer 2006, he has given an invited talk.Back to top
T2. Advances in Search and Inference for Combinatorial Optimisation
Presenters:
Rina Dechter, Radu Marinescu, Robert MateescuAbstract:
Graphical models, including constraint networks, belief networks, Markov random fields and influence diagrams, are knowledge representation schemes that capture independencies in the knowledge base and support efficient, graph-based algorithms for a variety of optimization tasks, including scheduling, planning, diagnosis and situation assessment, design, and hardware and software verification. The relevance of such algorithms to planning is either direct (e.g., scheduling, design) or indirect, via certain translation of finite horizon state-based planning problems into constraint expressions, (for classical planning), or into probabilistic expressions such as probabilistic conformant planning.Algorithms for processing graphical models are of two primary types: inference-based and search-based. Inference-based algorithms (e.g., variable-elimination, join-tree clustering) are time and space exponentially bounded by the tree-width of the problem's graph. Search-based algorithms (e.g., branch and bound) can be executed in linear space and often outperform their worst-case predictions. The thrust of advanced schemes is in combining inference and search yielding a spectrum of memory-sensitive algorithms applicable to numerous optimization tasks across variety of graph-based knowledge bases such as constraint optimization, Bayesian networks and Markov decision processes.
The goal of this talk is to present the algorithmic principles behind the progress that has been made in the past decade in this area in the graphical models communities such as Constraint networks and Probabilistic networks. It will focus on 1. how bounded-inference (e.g., mini-bucket and mini-clustering scheme) can be used to generate lower-bound heuristics for search, be it depth-first branch and Bound, or Best-first. 2. How these heuristics are contrasted and compare with Those based on linear programming and on soft arc-consistency, 3. on the role of caching goods during branch and bound search, and 4. on how problem decomposition can be incorporated into search using AND/OR search spaces. All these enhancement yield a new generation of branch and bound and Best-first algorithms that can trade-off time and space using a few controlling parameters.
Complexity analysis and empirical demonstration of all algorithms will be presented on variety of benchmarks for Max-CSP, for the Most Probable Explanation tasks (MPE) for probabilistic reasoning, for Integer programming and for general constraint optimization tasks. Example benchmarks include Radio-frequency problems (for MAX-CSPs), linkage analysis, combinatorial auctions, and coding networks.
Presenters' Bios:
- Rina Dechter is a professor of Computer Science at the University of California, Irvine. She received her PhD in Computer Science at UCLA in 1985, a MS degree in Applied Mathematics from the Weizmann Institute and a B.S in Mathematics and Statistics from the Hebrew University, Jerusalem. Her research centers on computational aspects of automated reasoning and knowledge representation including search, constraint processing and probabilistic reasoning. Professor Dechter is an author of the book "Constraint Processing" published by Morgan Kaufmann, 2003, and has authored over 100 research papers, and has served on the the editorial boards of: Artificial Intelligence, the Constraint Journal, Journal of Artificial Intelligence Research and the Encyclopedia of AI. She was awarded the Presidential Young investigator award in 1991 and is a fellow of the American association of Artificial Intelligence. She was a Radcliffe fellow 2005-2006.
- Radu Marinescu is a PhD candidate at University of California Irvine advised by Professor Rina Dechter. He received a BS degree in Computer Science from University "Politehnica" of Bucharest and a MS degree in Computer Science from University of California Irvine. Radu's research is focused on automated reasoning, in particular on combinatorial optimization tasks in graphical models. His thesis centers on search algorithms that explore the AND/OR search spaces, for graphical models, and use the Mini-Bucket approach the generate heuristic functions automatically. During the past years he worked within several optimization frameworks that arise in the areas of constraint based reasoning (constraint networks) and reasoning under uncertainty (belief networks). He has authored 9 research papers published in the most prestigious conferences on Artificial Intelligence, including AAAI, IJCAI, ECAI, UAI and CP, showing the power of these new algorithms compared with competitive approaches.
- Robert Mateescu is a postdoctoral scholar at Caltech working with Professor Shuki Bruck. He received Ph.D. and M.S. degrees in Computer Science from the University of California Irvine (in 2007 and 2003, respectively), working with Professor Rina Dechter, and a B.S. in Computer Science and Mathematics from the University of Bucharest. His research concentrates on high performance methods for probabilistic inference and for decision making under uncertainty focusing on graphical models. He worked on generalized belief propagation algorithms, mixtures of deterministic-probabilistic networks, AND/OR Search Spaces for graphical models and compilation schemes for graphical models. He co-authored papers appearing in the AI Journal, AAAI, IJCAI, UAI and CP. Robert had maintained a personal interest in the game of Go for over twenty years, during which he had an eighteen-months fellowship at the Japanese Professional Go Association, and was the European Go Champion in 1998.
Back to top
T3. Probabilistic Temporal Planning
Presenters:
Mausam, David E. Smith, Sylvie ThiébauxGoals and intended audience:
Most real world domains feature significant uncertainty that cannot be ignored when planning for a reliable, autonomous agent. Until relatively recently, methods for planning under uncertainty were limited to sequential decision-making for instantaneous actions with discrete uncertain outcomes. In this tutorial we review new advances in dealing with stochastic domains involving concurrency and durative actions. Some of these approaches extend the traditional MDP model and algorithms (leading to e.g. time-dependent MDPs, concurrent MDPs, the DUR family of algorithms, or factored policy gradient), while others (Prottle, Paragraph, Hybrid AO*, incremental contingency planning) build upon the classical planning framework. We also address the practical considerations when applying these algorithms and describe approaches that avoid modeling full-blown stochastic uncertainty to gain speed and scalability.This tutorial is intended both for planning researchers as well as other AI researchers who are interested in applying automated planning in domains involving uncertainty. We do not assume any knowledge of planning under uncertainty and will review the basics before discussing the advanced techniques.
Outline of the tutorial:
- Introduction
- Dimensions of planning problems
- Dimensions of stochastic uncertainty
- Alternative approaches to uncertainty
- The complete information ideal model
- Basics of Probabilistic Planning
- Classically derived approaches: CNLP, C-Buridan, Cassandra
- Markov Decision Processes
- Value/Policy Iteration
- Forward State Space Exploration: RTDP, LAO*
- Recent advances: LRTDP, Bounded RTDP, LDFS
- Challenges of Concurrency & Time
- Durative actions w/o concurrency
- Semi MDP
- Time Dependent MDP
- Hybrid AO*
- Incremental Contingency Planning
- Concurrency w/o Durative actions
- Factorial MDP
- Concurrent MDP
- Paragraph
- Durative actions w/ concurrency
- Prottle
- DUR and \Delta DUR
- Generalized Semi MDPs
- FPG
- Practical Considerations
- Weaknesses of above methods
- When is contingency planning needed?
- Incremental approaches Tempastic < Generate Test and Debug > Incremental Contingency Planning
- ombining replanning with contingency planning Precautionary Planning
- Applications Military Operations NASA Rovers
Bios of presenters:
- Mausam is a Ph.D. candidate (expected June 2007) at the University of Washington, Seattle advised by Dan Weld. His research interests include Automated Planning, Markov Decision Processes, Machine Learning and Heuristic Search. His thesis is on the extending the expressiveness of Markov Decision Processes to formulate complex planning problems involving concurrent, stochastic, durative actions. He has developed a range of algorithms that span the spectrum from optimal to near-optimal to fast but approximate. He has presented his work at several invited colloquia, for example, Microsoft Research, NASA Ames, and Intel Research.
- David E. Smith is a member of the Planning and Scheduling Group at NASA Ames Research Center. He has been involved in the development of several influential planning systems, including CNLP, CGP, SGP, TGP, and Fragplan, which have pushed the envelope of automated planning technology in the areas of uncertainty, continuous time, and over-subscription. Smith lead the effort to develop and demonstrate contingency planning for the K9 rover at NASA. He has over 40 publications in refereed conferences and journals, served as an Associate Editor for JAIR, and was Editor for the JAIR special issue on the 3rd International Planning Competition, and co-Editor for the JAIR special track on the 4th International Planning Competition. He currently serves on the JAIR Advisory Board, and on the International Planning Competition Committee. He was an invited speaker at AIPS-2000, where his talk focused on issues of incorporating time and resources into classical planning.
- Sylvie Thiébaux is an associate professor at the Australian National University where she leads the Diagnosis, Planning, and Optimisation Group. She is also a principal researcher in National ICT Australia's Knowledge Representation & Reasoning Program. She has over 40 publications in refereed conferences and journals and is one of the co-chairs of ICAPS-07. Her research interests in artificial intelligence include planning, reasoning under uncertainty, model-based diagnosis, and search. In the past few years, she and her colleagues have developed a range of approaches for handling concurrency and time in planning under uncertainty, leading to planners such as Prottle, Paragraph, and FPG. She was an invited speaker at the International Workshop on Planning and Scheduling for Space (IWPSS-06), where her talk focused on probabilistic temporal planning.
Summary:
Most real world domains feature significant uncertainty that cannot be ignored when planning for a reliable, autonomous agent. Until relatively recently, methods for planning under uncertainty were limited to sequential decision-making for instantaneous actions with discrete uncertain outcomes. In this tutorial we review new advances in dealing with stochastic domains involving concurrency and durative actions. Some of these approaches extend the traditional MDP model and algorithms (leading to e.g. time-dependent MDPs, concurrent MDPs, the DUR family of algorithms, or factored policy gradient), while others (Prottle, Paragraph, Hybrid AO*, incremental contingency planning) build upon the classical planning framework. We also address the practical considerations when applying these algorithms and describe approaches that avoid modeling full-blown stochastic uncertainty to gain speed and scalability.Back to top
T4. Learning Techniques in Planning
Presenters:
Sungwook Yoon and Subbarao KambhampatiSchool of Computing & Informatics
Arizona State University
Tutorial website:
http://rakaposhi.eas.asu.edu/learn-plan.htmlAbstract:
This tutorial aims to provide an overview of learning techniques for planning--an area with significant past as well as a substantial current interest. From planning perspective, learning techniques can be seen as (i) a way to "speed-up" planners or (ii) as a way to reduce domain-modeling burden. Early interest in this area was driven almost exclusively by the first, while the recent resurgence is motivated by the second consideration. From the learning perspective, focus on planning necessitates a welcome diversion from the dominant tabula-rasa paradigms. Specifically, it encourages handling relational and first order representations, and foregrounds the need for knowledge-intensive learning techniques (such as explanation-based and relevance-based learning).We will survey both the history as well as promising current trends, and make connections to DARPA Integrated Learning program, Model-lite planning.
Bios of presenters:
- Sungwook Yoon is a postdoctoral research associate of Computer Science at Arizona State University where he is working on the DARPA Integrated Learning project. He received his doctoral degree from Purdue University working with Professor Robert Givan and Professor Alan Fern. His primary research interests are in learning for planning and he has published several papers at AAAI, NIPS, ICAPS and JAIR on this topic. His research also resulted in a stochastic planner that won the first international planning competition in the stochastic planning track.
- Subbarao Kambhampati is a professor of Computer Science at Arizona State University. His interest in learning techniques for planning dates back to his thesis work on plan reuse, and early work on combining case-based and explanation-based learning techniques for planning performance. He co-authored a survey on learning techniques for planning (which appeared in a 2003 AI Magazine article), and delivered two lectures on the topic at the 2006 Machine Learning Summer School at Canberra. Kambhampati received an NSF Young Investigator in 1994 and was elected a fellow of AAAI in 2004. In 2005 he co-chaired AAAI, and also organized the first ever Festivus at ICAPS. He avoids having any spare time by signing up to teach tutorials at major AI conferences-- at the last count, he is doing four of them in 2007.
Back to top
T5. Fuzzy Temporal Reasoning
Presenters:
Marco Falda and Massimiliano GiacominAbstract:
This tutorial aims at providing a survey of temporal constraint-based formalisms that can model uncertain information. In the first part a review of the existing formalisms will be presented and the typology of imperfect information will be discussed, with a special attention to Fuzzy Logic and Possibility Theory. The second part of the tutorial will consider the problem of generalizing specific instances of the Constraint Satisfaction Problem framework (CSP), such as temporal reasoning formalisms, in order to handle fuzzy constraints. In particular, standing at a high level of abstraction it will be shown that several definitions and results handling in the crisp context can be directly generalized to the fuzzy case. In the third part we will discuss how qualitative and metric temporal information can be integrated together. Some examples of application in the field of temporal reasoning will then be provided, considering in particular the qualitative algebra IAfuz which extends Allen's Interval Algebra.Bios of presenters:
- Marco Falda received a Master degree and a Ph.D. in Information Engineering at the University of Padova (2006). His area of interest includes Temporal Reasoning, Fuzzy Logic and Constraint Programming; he has published papers about these topics in conferences (IJCAI, IPMU, AIME) and journals (AI Communications). In the last year he worked with F. Rossi at the Department of Pure and Applied Mathematics of the University of Padova on Conditional Temporal Reasoning with Uncertainty.
- Massimiliano Giacomin is assistant professor in Information Processing Systems at the Department of Electronics for Automation (DEA) of the University of Brescia (Italy). He received a Master degree from the University of Padova in 1998, and a PhD degree in Information Engineering from the University of Brescia in 2002. His main research interests are in the fields of argumentation theory, agent and multi-agent systems, fuzzy constraints and temporal reasoning. He is author of over 30 scientific papers in refereed conferences (including ECAI, ECSQARU, COMMA, and TIME) and journals (including AIJ, AICOM, and JETAI).
Back to top
Ome © Marjorie Mikasen 2005