Foundations of Model-Lite Planning

Supported by ONR grant N00014-09-1-0017

Executive Summary

The automated planning community has traditionally focused on the efficient synthesis of plans given a complete model of the domain and user preferences. In the past several years, this line of work met with significant successes, and the future course of the community seems to be set on efficient planning with even richer domain and preference models. While this line of research has its applications, there are also many domains, including, perhaps most prominently, military planning scenarios, where the first bottleneck is getting the domain and user preference model at any level of completeness. This incompleteness is caused both because of domain modeling burden, and also because of lack of full knowledge (e.g. commanders often do not know or are unable to specify full details of their own objectives).

To support planning in such scenarios, recently, the PI has argued for a model-lite planning technology aimed at handling incompletely specified domain and user preference models. This view was first presented as a senior member track paper at the National Conference on Artificial Intelligence in 2007 (1), and has since been fleshed out in several conference and workshop papers (c.f. (10; 40; 34; 18)).

Based on the promising preliminary results, in this research, the PI proposes to develop a comprehensive framework for model-lite planning under incomplete domain and user preference models. The proposed research tasks can be broadly split into three categories, aimed respectively at planning techniques to handle incompleteness in preference models, planning techniques to handle incompleteness in domain models, and learning techniques to refine both preference and domain models (the former through elicitation and the latter through execution and replanning).

Model-lite planning technology developed in this research is expected to significantly increase the reach and application of automated planning techniques. It will be especially useful in many military planning domains, where the modeling burden and dynamically changing and/or partially articulated planning objectives make traditional planning technology unsuitable. It will also be useful in web-service composition and workflow management scenarios.

The URL http://rakaposhi.eas.asu.edu/onr-model-lite contains additional details of the proposal as well as latest developments in the project.

A talk on the recent progress in this direction (Streaming video available)

Relevant publications (containing preliminary work)

1. Model-lite Planning for the Web Age Masses: The Challenges of Planning with Incomplete and Evolving Domain Theories
   Subbarao Kambhampati.
   AAAI 2007. (Slides and Talk audio)
   A sneaky reprise at Festivus@ICAPS 2007 ( slides and audio)

2. Model-Lite Case-Based Planning
   Hankz Hankui Zhuo, Subbarao Kambhampati, Tuan Nguyen.
   AAAI 2013.

3. Refining Incomplete Domain Models through Plan Traces.
   Hankz Hankui Zhuo, Tuan Nguyen and Subbarao Kambhampati.
   IJCAI 2013.

4. Action Model Acquisition from Noisy Plan Traces.
   Hankz Hankui Zhuo, Subbarao Kambhampati.
   IJCAI 2013.

5. Planning for Human-Robot Teaming in Open Worlds.
   Kartik Talamadupula, J. Benton, Subbarao Kambhampati, Paul Schermerhorn, and Matthias Scheutz.
   ACM Transactions on Intelligent Systems and Technology. (Special Issue on Applications of Automated Planning). Vol 1. No. 2. 2010.

6. Generating diverse plans to handle unknown and partially known user preferences
   Tuan Nguyen, Minh Do, Alfonso Gerevini, Ivan Serina, Biplav Srivastava and Subbara Kambhampati.
   Artificial Intelligence Journal. Vol 190. Pages 1-31. Oct 2012.

7. Integrating a closed-world planner with an open-world robot: A case study.
   Kartik Talamadupula, J. Benton, Paul Schermerhorn, Matthias Scheutz and Subbarao Kambhampati
   AAAI 2010

8. Assessing and Generating Robust Plans with Partial Domain Models
   Tuan A. Nguyen  and Subbarao Kambhampati  and Minh B. Do.
   ICAPS 2010 Workshop on Planning under Uncertainty. 2010.

9. Learning Probabilistic Hierarchical Task Networks to Capture User Preferences.
   Nan Li, Subbarao Kambhampati & Sungwook Yoon. IJCAI 2009. (To appear)

10. Planning with Partial Preference Models.
    Tuan Nguyen, Minh Do, Biplav Srivastava and Subbarao Kambhampati. IJCAI 2009. (To appear)

11. Domain Independent Approaches for Finding Diverse Plans
    Biplav Srivastava, Subbarao Kambhampati, Tuan Nguyen, Minh Do, Alfonso Gerevini, Ivan Serina. IJCAI 2007. (Talk slides)

12. Towards Model-lite Planning: A Proposal For Learning & Planning with Incomplete Domain Models Sungwook Yoon and Subbarao Kambhampati
    ICAPS 2007 Workshop on AI Planning and Learning.
    (Talk Slides)

13. Model-Lite Planning: Diverse Multi-option plans & Dynamic Objective Functions. Daniel Bryce, William Cushing & Subbarao Kambhampati
    ICAPS 2007 Workshop on Planning and Plan Execution for Real World Systems.
    (Talk Slides) (Audio)

14. Hierarchical Strategy Learning with Hybrid Representations
    Sungwook Yoon and Subbarao Kambhampati
    AAAI 2007 Workshop on Acquiring Planning Knowledge via Demonstration. 2007.