Synthesizing Robust Plans under Incomplete Domain Models
Most current planners assume complete domain models and focus on generating correct plans. Unfortunately, domain modeling is a laborious and error-prone task, thus real world agents have to plan with incomplete domain models. While domain experts cannot guarantee completeness, often they are able to circumscribe the incompleteness of the model by providing annotations as to which parts of the domain model may be incomplete. In such cases, the goal should be to synthesize plans that are robust with respect to any known incompleteness of the domain. In this paper, we first introduce annotations expressing the knowledge of the domain incompleteness and formalize the notion of plan robustness with respect to an incomplete domain model. We then show an approach to compiling the problem of finding robust plans to the conformant probabilistic planning problem, and present experimental results with Probabilistic-FF planner.
This paper considers the problem of planning under 
      incomplete domain models. The authors formalize domain incompleteness, 
      discuss how to generate robust plans using conformant probabilistic 
      planning, and compare robustness to solving time and plan quality in two 
      test domains. Clarity: The paper is very well written and the 
      authors do a great job at explaining all of the details both formally and 
      informally. Although I am mostly unfamiliar with planning research, I was 
      able to follow along fairly well and understand the contributions. 
      Organization is good and the example at the top of page 4 is great, but I 
      believe that on line 177, the "fifth candidate model" described is 
      actually the second candidate model given by the table in Figure 2. 
      Quality: What I like most about this paper is that the 
      incompleteness formulation is very intuitive and easy to understand. A 
      practioner should be able to read the paper and integrate the ideas into 
      their own planning problem without too much worry. Theorems of 
      completeness and correctness are also stated. However, perhaps the biggest 
      drawback is the lack of proofs, particularly for Theorem 1. While I agree 
      with the authors that there is no space in the main body of the paper to 
      include proofs, the authors really should have included them as 
      supplementary material. Originality: While there are some 
      similarities here to other work, the authors do discuss this in the 
      related work section and I believe that the proposed formulation for 
      incompleteness is adequately original and worthy of publication. The 
      authors clearly state how their work differs from previous contributions. 
      Significance: I believe the contributions of this paper are 
      important to the NIPS community. Robust planning is an under-studied 
      problem and the authors address this difficult challenge in a intuitive 
      manner. With that said, I am concerned with the applicability of their 
      formulation beyond toy problems. Their formulation results in an 
      exponential blow up in the size of the problem. In addition, experiments 
      are only performed in toy domains that appear to have been created by the 
      authors specifically for this paper. I presume that with the lack of 
      research into planning in incomplete models, there are no standard domains 
      to run experiments in. However, I am concerned that the approach will be 
      completely infeasible in large domains that arise in the wild. In very 
      large domains, can we ever hope to guarantee a high level of robustness, 
      or are we simply going to be satisfied in just finding a valid plan? How 
      badly do planners such as PFF suffer from such an exponential blowup 
      resulting from the set of all possible complete domain models? 
      Typos: - Line 113: "with respects to..." - Line 135: 
      "Makov Logic Networks" - Line 430 or 431: "constrasting" 
      COMMENTS AFTER AUTHOR RESPONSE: I am glad to hear that 
      proofs will be appearing in a later document. If the Ph.D. proposal will 
      not be accessible soon, I suggest attaching the proofs as supplementary 
      material to the camera-ready paper if this paper is accepted. While I am 
      still somewhat concerned about the applicability beyond toy problems, this 
      is a good first step and future work with heuristics could potentially 
      improve things.