Planning with preferences, specification and search

Planning is one of the fundamental problems of artificial intelligence. A classic planning problem consists of an initial world state, a set of goal conditions, and a set of actions. The solution to the problem is a sequence of actions, a plan, that when applied to the initial state, leads to a final goal state that satisfies all goal conditions. In many cases, it makes sense to add preferences to a planning problem. A preference can be viewed as a 'soft' goal. Ideally, all preferences will be satisfied by a plan, but this is not necessary, and not necessarily possible. There are two basic components to planning with preferences, specifying the preferences and the search for a high quality plan. For the former, we present a rich language for specifying preferences for planning problems. For the latter, we use heuristic guided search, a successful approach to classic planning, for planning with preferences. Landmark based heuristics have been successful in classic planning, so we examine how they can be used for preferences. Finally, we present an adaptation to the greedy best-first search algorithm, Cascading Search, that diversifies the search space and examine how effectively it speeds the search process and ensure discovery of quality plans.