AI planning has recently made great advances. The evolution of the international planning competition over its four editions [1, 11, 19, 22] accurately reflects this. Successive editions introduced more and more complex and realistic benchmarks, or harder problem instances in the same domain. The top performers could successfully solve a large percentage of the problems each time. However, many hard domains, including benchmarks used in IPC-4, still pose great challenges for current automated planning systems.
The main claim of this paper is that in many domains, the performance of a planner can be improved by inferring and exploiting information about the domain structure that is not explicitly encoded in the initial PDDL formulation. The implicit structural information that a domain encodes is, arguably, proportional to how complex the domain is, and how realistically this models the world. For example, consider driving a truck between two locations. This operation is composed of many subtasks in the real world. To name just a few, the truck should be fueled and have a driver assigned. In a detailed planning formulation, we would define several operators such as FUEL, ASSIGN-DRIVER, and DRIVE. This representation already contains implicit information about the domain structure. It is quite obvious for a human that driving a truck between two remote locations would be a macro-action where we first fuel the truck and assign a driver (with no ordering constraints between these two actions) and next we apply the drive operator. In a simpler formulation, we can remove the operators FUEL and ASSIGN-DRIVER and consider that, in our model, a truck needs neither fuel nor a driver. Now driving a truck is modeled as a single action, and the details described above are removed from the model.
In this article we present and evaluate two automated methods that learn such implicit domain knowledge and use it to simplify planning for new problem instances. The learning uses several training problems from a domain. Our methods share a common four-step pattern: