Automated Modeling Support for Automated Planning

Abstract

Automated planning is concerned with the task of finding a sequence of actions to achieve a certain goal. Theoretical investigations have shown that many practical scenarios, e.g., logistics, factories, and Mars rovers, can be modeled using planning frameworks. In spite of that, Automated Planning is not widely deployed in practice, especially outside academia. One major reason for this is the complexity of modeling a practical problem as a planning problem, which necessitates techniques for automated modeling support. In this talk, I would like to address two critical problems in this direction, namely, how to check whether a planning model is constructed correctly and how to repair a flawed planning model. Our approaches for solving these two problems are originated from the common debugging paradigm in programming, i.e., by providing test cases. In our context, a test case is an action sequence that must be a solution (i.e., is feasible and can achieve the goal) if the planning model is flawless. More concretely, we could validate a planning model by checking whether all test cases we provide pass, i.e., whether all provided action sequences are indeed solutions. If some test cases fail, then we know that there are some issues in the planning model, and we call these failed test cases counter-example action sequences (because they are supposed to be solutions but are actually not due to the errors in the model). The repairs can then be made to the planning model which turn all counter-example action sequences into solutions. In my dissertation, I will discuss the computational complexity of verifying whether an action sequence is a solution to a planning problem (i.e., the plan verification problem) and of correcting a planning model by turning counter-example action sequences into solutions. On top of that, I will also introduce some practical approaches we developed for solving those two problems. Lastly, some alternative frameworks for modeling support will also be discussed. Show more