HTN Planning with Preferences

Abstract

In this paper we address the problem of generating
preferred plans by combining the procedural
control knowledge specified by Hierarchical Task
Networks (HTNs) with rich user preferences. To
this end, we extend the popular Planning Domain
Definition Language, PDDL3, to support specification
of simple and temporally extended preferences
over HTN constructs. To compute preferred HTN
plans, we propose a branch-and-bound algorithm,
together with a set of heuristics that, leveraging
HTN structure, measure progress towards satisfaction
of preferences. Our preference-based planner,
HTNPLAN-P, is implemented as an extension of
the SHOP2 planner. We compared our planner with
SGPlan5 and HPLAN-P– the top performers in
the 2006 International Planning Competition preference
tracks. HTNPLAN-P generated plans that in
all but a few cases equalled or exceeded the quality
of plans returned by HPLAN-P and SGPlan5.
While our implementation builds on SHOP2, the
language and techniques proposed here are relevant
to a broad range of HTN planners.