Hybrid STAN: Identifying and Managing Combinatorial Optimisation Sub- Problems in Planning

Abstract

It is well-known that planning is a hard combinatorial problem but it is less well-known how to approach the hard parts of a problem instance eectively. Generic search is not always the most appropriate problem-solving tool, but planners do not generally have a wide repertoire of alternative strategies to apply to combinatorial sub-problems within planning domains. Some such (NP-hard) sub-problems occur very commonly { for example, Travelling Salesman-like sub-problems arise when a planning problem involves accomplishing tasks at dierent locations in contexts where the ordering in which these locations are visited aects the eciency of the plan. Multiprocessor Scheduling-like problems occur when there are limited resources and tasks requiring the use of these resources. Again, the way in which restricted resources are allocated between processors can aect plan quality. Using static domain analysis techniques we have been able to identify certain combinatorial sub-problems...