Domain Recompilation-based Approach towards Hierarchical Task Network Planning with Constraints Plaban Kr Bhowmick, Debnath Mukherjee, Prateep Misra1, and Anupam Basu2 Abstract. In this paper, we present a domain recompilation- made progress towards handling constraints imposed on goal states based approach towards specifying and handling state-trajectory con- as well as entire set of states visited by a plan. The primary chal- straints in Hierarchical Task Network (HTN) planning paradigm. lenges in planning with constraints are The proposed constraint specification language is inspired by the PDDL3.0 constructs. The domain-recompilation technique is based • processing of the constraint expressions for the consumption by on automata templates for the PDDL modal operators. To implement the planning algorithm, and automata embedding we have introduced conditional effect construct • designing planning algorithm to handle constraints. in HTN. Introduction of dead automata state has helped in reducing amount of backtracking that was required originally. The constraint One of the popular ways to handle constraints is to model plan- specification and handling strategy has been tested with a city tour ning as a model checking problem [3]. The plan-space defines the and travel domain modelled using HTN. model which needs to be validated against the stated constraints. One important decision here is the use of external model checkers which in turn may call for the adaptation of the planning algorithm 1 INTRODUCTION that does not handle constraints. Another approach that avoids ex- Design of intelligent environment rests upon three important activ- ternal model checkers and adaptation of planning algorithm is do- ities: sense, analyze and respond. The sensors acquire relevant data main recompilation-based technique. In this approach, the effects from the environment, the analyze phase processes the sensor data to of constraints are simulated by including them in the planning do- generate some contextual information and the respond phase needs main with no changes in the planning algorithm. The external model to plan the actions for some assigned task given the context informa- checker based approaches can handle complex and large number of tion. Thus planning is an important component of intelligent environ- constraints. However, model checking is expensive in terms of time ment as far as the actuation part is concerned. Below we present an and space. On the other hand, domain recompilation-based technique example scenario that points out the role of planners in the context is efficient by limiting the scope in terms of complexity and number of intelligent environment. of constraints. As compared to its classical counterpart, efforts towards constraint Example 1 City tour and travel specification and handling in HTN planning is sparse. Thus the con- A city tour and travel planner provides the travellers with smart plan straint or preference specification scheme, the constructs required to based on the traveller specified intents and state of the environment. implement them and corresponding planning algorithm have not re- The state of the environment may be described with information re- ceived the required level of attention. lated to the Points of Interests (PoIs), traffic updates, weather update In this work, we aim at incorporating constraint processing fea- and others. The state information can be obtained or updated by im- ture in HTN planner. This is achieved through extending a state-of- planting related sensors (traffic sensors, rss feeds, twitter feeds etc.) the-art open-source HTN planner, namely, JSHOP23 [7]. We have and extracting contexts (blocked road segment, accident, inclement adopted the constraint specification syntax and semantics provided in weather etc.) out of the sensor data. PDDL3.0. A domain recompilation-based strategy has been adopted to transform state-trajectory constraints into goal constraints. The To deploy planners in practical settings, they need to be scalable a specific contributions of this paper are as follows: feature that is lacking in most of the “first principle” planners [9]. Hi- erarchical Task Network (HTN) planning [4] paradigm handles the • Constraint specification language scalability issue by consuming knowledge regarding plan search pro- • Automata template-based approach for conversion of constraint cess. This indicates that HTN paradigm is a natural fit to the domains expression to automata where a planning task can be achieved through some standard pro- • Constructs required to embed constraint automata into planing do- cess modules. main With the constraint specification standard set in PDDL3.0 [5], re- • Reduction of backtracking effort search in constraint-based planning has gained a considerable mo- mentum. The classical planners that follow PDDL standard have The paper is organized as follows: Section 2 provides background on HTN planning and related works in constraint-based HTN plan- 1 Innovation Labs, Tata Consultancy Services, Kolkata, India, email: {plaban.bhowmick,debnath.mukherjee,prateep.misra}@tcs.com ning. Section 3 presents the constraint specification issues in HTN. 2 Department of Computer Science & Engoneering, Indian Institute of Tech- nology Kharagpur, India, email: anupambas@gmail.com 3 http://www.cs.umd.edu/projects/shop/ Workshop on AI Problems and Approaches for Intelligent Environments (AI@IE 2012) 15 The constraint compilation technique for HTN is described in sec- 2.3 Constraints in HTN Planning tion 4. Section 5 describes the implementation details and some re- sults with respect to a city tour and travel domain developed by us. As compared to classical planning, efforts towards specifying con- straints or preferences have been started recently. A constraint-based HTN planning is defined as follows 2 BACKGROUND & RELATED WORKS Definition 1 A constraint-based planning problem is defined as Since our primary objective is to incorporate constraint specification P = (S0 , T0 , D, C) where C is the set of constraints. The plan π in HTN planning paradigm, brief backgrounds on PDDL3.0 con- generated for P is valid if all constraints in C are satisfied by state straint specification and HTN planning paradigm are provided in trajectory generated by π. this section followed by some previous efforts towards constraint and preference-based planning. There have been few efforts towards incorporating PDDL con- straint specification in HTN. HTNPLAN-P [11] is an HTN-based planner that can plan with soft constraints or preferences. A best- 2.1 PDDL3.0 Constraint Specification first search technique and different heuristics have been used in or- Among other features introduced in PDDL3.0, constraint specifica- der to generate preferred plans. SCUP [8] is an algorithm to per- tion language perhaps is the most important one. Through this lan- form web service composition by modelling it as a preference-based guage, both the soft and hard constraints can be specified over the HTN planning problem. Other notable non-HTN planning algorithm goal state as well as entire state trajectory generated by a plan. To that can handle PDDL constraint constructs are HPlan-P [1] and SG- represent the state-trajectory constraints, some modal operators were PLAN [6]. introduced in PDDL3.0. The modal operators are of two types: rel- ative temporal and metric temporal. The relative temporal operators 3 PROPOSED CONSTRAINT SPECIFICATION are those that do not have any explicit mention of time unlike the FOR HTN metric temporal operators. In order to keep the constraint specification compliant to PDDL In this paper, we deal with constraints that can be specified standard, the proposed constraint specification borrows PDDL with relative temporal modal operators. PDDL3.0 supported constructs with minor modifications. The constraints are specified in relative temporal modal operators are at end, always, problem description in a separate block. The syntax for constraint sometimes, at most once, sometime after and specification is as follows sometime before. The semantics of the relative temporal (:constraint constraint name (:modal operator modal operators are captured through Linear Temporal Logic (LTL). operands)) PDDL3.0 does not support nested modal operators as the nested A constraint expression starts with a :constraint tag followed construct in a constraint may contribute to the exponential growth of by the constraint name. The modal operator used to encode the the corresponding automata required to process the constraint. temporal modality is specified followed by the list of arguments required by the modal operator. The modal operators can be anyone 2.2 HTN Planning of the relative temporal modal operators proposed in PDDL. Some examples of constrains are as follows: The HTN planners differ from the classical notion of planning in various aspects. Firstly, apart from standard classical operators or Example 2 There should always 3000 amount of cash available to primitive tasks, HTN makes use of methods for specifying domain the traveller. specific plan search knowledge. Secondly, the goal in HTN is pre- (:constraint c1 (:always ((call > avail-cash sented as a complex task whereas classical planning specify goal as 3000)))) a set of propositions. A task network is defined by a set of task nodes (T ) and set of Example 3 Sometime in the plan poi1 has to be visited precedence relations (P ). Each of the task nodes contains a task and (:constraint c2 (:eventually (visited poi1))) a precedence relation establishes a precedence constraint between Example 4 Payment by credit card will be done at most once two tasks. If all the tasks in the task network are primitive then the (:constraint c3 (:at-most-once (pay-via task network is called primitive. creditCard))) An HTN domain (D = (O, M )) consists of primitive tasks or op- erators (O) and methods (M ). The primitive tasks are executable and Example 5 poi7 has to be visited sometime before poi2 has precondition, add list and delete list. The complex tasks are de- (:constraint c4 (:s-before(visited composed by their corresponding methods. Depending upon differ- poi2)(visited poi7)) ent preconditions different branches of decomposition are followed. The decomposed tasks are more simpler than the original one and Example 6 poi7 has to be visited sometime after poi2 they again form a network depicting the precedence relations among (:constraint c5 (:s-after(visited them. poi2)(visited poi7)) For a given task, there exists a plan plan π = o1 o2 . . . on if there is a primitive decomposition (Tp ) of the initial task network T0 of the 4 COMPILATION OF CONSTRAINTS planning problem P = (So , To , D) and π is an instance of Tp . The planning process starts by solving the initial task network After specification, the next step is constraint processing. In this which in turn is decomposed into more basic task network until the work, we adopted a domain recompilation based technique for pro- whole task network becomes primitive (existence of plan) or no more cessing constraints. A fully automated domain recompilation tech- decomposition is possible (non-existence of plan). nique has the following steps. 16 Workshop on AI Problems and Approaches for Intelligent Environments (AI@IE 2012) • Conversion of the constraint expressions into LTL formulae. ) (:when (!cond c3 1) • Generating Büchi automata for LTL formulae. ((state-c3 S1)(avail-cash ?VARC0)(call > • Embedding the automata into planning problem by changing the ?VARC0 3000.0 )) problem and domain description. ((state-c3 S1)) ((state-c3 S1)(accepting-c3)) As modal operator set in PDDL is a closed one and PDDL does not ) support nesting of operators, the generation of automata from a con- (:when (!cond c3 2) straint expression can be simplified by defining automata templates ((state-c3 S1)(avail-cash ?VARC0)(not for the modal operators. Thus the conversion process is adapted into (call > ?VARC0 3000.0 ))) the following steps. ((state-c3 S1)(accepting-c3)) ((state-c3 S2)(dead-c3)) • Defining automata templates for modal operators. ) • Instantiating transition labels of the automata by operands of the (:when (!cond c3 3) modal operators in the specified constraints. ((state-c3 S0)(avail-cash ?VARC0)(not (call > ?VARC0 3000.0 ))) 4.1 Automata Templates ((state-c3 S0)(accepting-c3)) ((state-c3 S2)(dead-c3)) The automata templates are generic representation of the modal op- ) erators. An automata template consists of start state, set of tran- sitions and set of accepting states. A transition is described by a source-destination state pair and a transition label. The automata 4.3 Automata Simulation templates are stored as xml specification. An example automata for at-most-once is shown in Figure 1. After representing the automata into required construct, one needs to On encountering a constraint expression, the corresponding au- simulate the automata correctly to test the validity of the constraints. tomata template is retrieved and the labels of the transitions are in- This is achieved through the following changes in the original plan- stantiated with the logical expressions formed out of the operands in ning problem. constraint expression. • Start state initialization: The start states of the automata have to be initialized and the corresponding state predicates have 4.2 Conditional Effects (CE) to be inserted in the plan state prior to start solving the actual task network. This is achieved through the inclusion of a new After instantiation of automata, the next task is to embed it into plan- operators !start in the compiled domain description. The ning problem. Thus the transitions has to be translated into a form !start operator for two constraints is shown below. which the original planner can process. Conditional effect is a con- struct that supports switch-case like syntax in operator definition. (:operator (!start) Apart from the standard effects, the application of an operator may () impose one of multiple effects depending on the branch of precondi- () tion that is being satisfied. ((state-c1 S0)(state-c2 S0)) Conditional effects are like operators as they have similar com- ) ponents like precondition, delete list and add list. The automata states are represented by state predicates like (state-C S0), It is to be noted that the operator has empty precondition and (state-C S1) . . . (state-C Sn). The plan state and the au- delete list. The add list consists of the predicates stating that the tomata states are synchronized by adding automata state predicate to automata are in start state. the current plan state. Thus for a constraint C, a plan state will con- • Probing plan validity: A constraint is satisfied if the correspond- tain no more than one of the automata state predicates. A transition ing automata is in an accepting state at the end of the plan. from one state Sm to another state Sn with label φ can be modelled For a constraint C, the !finish operator performs this task by a CE having by checking whether (accepting-C) is there in the final • Precondition: logical conjunction of (state-C Sm) and φ plan state. If so the plan satisfies C; otherwise it is violated. An • Delete list: current automata state i.e., (state-C Sm), example finish operator is shown below. (accepting-C) if Sn is not an accepting state. • Add list: next automata state i.e., (state-C Sn), (:operator (!finish) (accepting-C) if Sn is an accepting state. (accepting-c1)(accepting-c2) () The conditional effect form for automata representing the constraint () always (call > avail-cash 3000) (available cash ) should be greater than 3000) is presented below. • Changes in operators: After applying an operator, some state pred- (:when (!cond c3 0) icates will be changed which in turn ask for changes in the current ((state-c3 S0)(avail-cash ?VARC0)(call > states of some automata. As discussed earlier, the transitions can ?VARC0 3000.0 )) be modelled with CEs. The union of the set of CEs correspond- ((state-c3 S0)) ing to the automata for all the constraints will decide the next au- ((state-c3 S1)(accepting-c3)) tomata state after applying one action. Thus the union of the CEs Workshop on AI Problems and Approaches for Intelligent Environments (AI@IE 2012) 17 Figure 1. Automata template for at-most-once modal operator are added to the domain operators in compiled domain descrip- 5.2 City Tour and Travel Domain tion. • Modified initial task network: Apart from the tasks in the original City tour and travel is a service provided by the city authority to initial task network, two additional tasks !start and !finish aid the prospective tourists with smart travel plans. The travellers have to be performed. The modified initial task network in may specify their travel intents in terms of points of interest to be the compiled problem description is (!start)(original visited, other activities. The application in response generates valid initial task network)(!finish). plans with respect to the traveller’s intents and constraints imposed • Removal of constraint block: As the constraints have already been by him/her. Here, we briefly describe the domain the detail of which taken care of by the automata, they are removed in the compiled is given in [2]. problem description. The operators and the methods in the domain description are given in Table 1 and Table 2 respectively. 5 IMPLEMENTATION AND RESULTS In this section, we describe the implementing details of constraint Table 1. Operators in city tour and travel domain processing in existing HTN framework. We study different aspects Operators Synopsis of constraint-based HTN planning in the purview of a domain called !load-pref This is used in loading a traveller intent city tour and travel. !set-cost This is used to set the tour cost based on avail- able amount and estimated cost !mark-stay-hotel Marking one hotel of traveller’s choice and 5.1 Constraints in JSHOP2 updates time of day !lunch This is used to represent the fact that the user JSHOP2 is a java implementation of Simple Hierarchical Ordered has taken lunch Planner (SHOP2) [10]. It is an open source tool for generating prob- !dinner Mark the fact that the traveller has taken din- lem specific planner. Current implementation does not have the fa- ner cility to specify and process constraints. In this work, we have ex- !set-loc The traveller has visited a particular location tended JSHOP2 to incorporate PDDL3.0 supported relative temporal !end-day Marks the end of day and reset time of day for the next day operators. Here we describe the implementation details of the said extension. The modifications are as follows: • Constraint block: A constraint block has been added in the prob- lem description to specify constraints. The constraints are ex- pressed by using modal operators. The original ANTLR4 JSHOP2 Table 2. Methods in city tour and travel domain grammar has been modified to add rules for parsing constraint ex- Methods Synopsis pressions. ini-pref a generic method that loads all the traveller • Conditional Effect: JSHOP2 does not support conditional effect intents construct. Looking at the similarity of the constructs, the CE ex- end-day To probe the end of day condition tension has been implemented by modelling CEs as operators. find-hotel-go To find the hotel that matches traveller speci- fied features • Translation of CEs: The CEs are automatically translated into travel To visit the traveller provided points of inter- JSHOP2 operator format and appended into the original operators. est • Inserting !start and !finish: Depending on the expressed find-rest To find the restaurant that matches traveller constraints, the !start and !finish operators are constructed specified features and added to the operator list in domain description. Next we provide a brief description of HTN domain developed for The state information consists of facts related to hotels and their city tour and travel application and this domain is used to test the services, restaurants and information about points of interest. The ini- proposed extension of JSHOP2. tial task network consists of one task that specifies choices regarding 4 http://www.antlr.org/ hotels, restaurants and points of interest as arguments. 18 Workshop on AI Problems and Approaches for Intelligent Environments (AI@IE 2012) 5.3 Experimental Setup & Results Experiment II: In this experiment, we study the effect of initial cash on the number of plan steps. The planner was asked to generate plan The results presented in [2] were based on original JSHOP2. Here, for two-day trip with constraint on one particular PoI to be visited. we modify the experimental setup in order to test the implemented Figure 3 presents the variation of number of plan steps with initial extension over JSHOP2. The experiments have been performed on a cash available to the traveller. 2.99 GHz core 2 duo Intel processor with 2GB RAM machine. The problem description consists of 6 hotels having 7 different services (total 15 facts), information about 17 restaurants (17 facts) and infor- mation about 28 locations (28 facts). In experimental study, we have considered the following test scenarios. • Experiment I: Order of PoIs and constraint • Experiment II: The effect of initial available cash with constraint on PoIs. • Experiment III: The effect of constraint over traveller’s wallet. Experiment I: In this experiment, we test the performance of the planner based on the setup where the traveller has specified the POIs in some order and placed constraint on a particular PoI that needs to be visited. All the PoIs are placed in order in the initial task net- work description. Figure 2 depicts the effect of selecting different Figure 3. Effect of initial cash and constrained PoI PoIs and number of days to be planned. The x-axis plots the values of the position of the constrained PoI in the PoI list specified in the initial task network and y-axis plots the number of plan steps5 for each constrained PoI. This experiment also presents the comparison Similar experiment has been performed on the planner without any of planner performance in case of one-day and two-day travel plan- constraints. The variation was similar as in Figure 3 with minor de- ning. crease in number of plan steps. In both the cases, no plan was getting generated below a certain limit on initial cash. After that the number of plan steps was increasing in rapid rate with increasing initial cash upto a certain limit and was decreasing again with increasing cash. Experiment III: In this experiment, we put constraint like ‘the traveller should always have greater than 3000 amount of cash available’. With this constraint, the variation in the number of plan steps with initial cash has been studied and presented in Figure 4. Figure 2. Effect of position of constrained PoI From the specified list, the number of PoIs selected by the planner is limited by the number of days to be visited and available cash. It is to be noted that in both one-day and two-day plan the number of plan steps increases linearly with the relative position of the constrained PoI with notable spikes in two-day plan. The explanations behind the observations are as follows. Figure 4. Effect of constraint over traveller’s wallet with ‘always’ modal operator • Linearity: To include the constrained PoI in the plan, the planner needs to backtrack, remove the PoI that was selected last and in- clude the constrained PoI. This takes same amount of steps to be It is noticed that for smaller and larger amount of cash the planner performed for each PoI preceding the constrained PoI. This at- has been able to generate plan within reasonable time. However, for tributes to the linearity of the plan step size growth. moderate amount of cash (900 – 4000) planner failed to generate • Spikes: A spike is observed when a PoI with high cost is selected plan with the given computing power. This is due to huge amount of as constrained PoI. To satisfy the budget, the planner needs to backtracking in case moderate initial cash. remove more than one PoIs or select some other PoIs to make room for the constrained PoI. Hence the amount of backtracking increases non-linearly. 5.4 Avoiding some Pitfalls 5 The total number of steps including backtracking steps required by the plan- In experiment III, the planner should indicate that the constraint is ner violated for initial cash less than 3000. Instead, the planner back- Workshop on AI Problems and Approaches for Intelligent Environments (AI@IE 2012) 19 tracks enormously with different available options. A close look at • The automata for the modal operators have been specified through the automata for the modal operators reveals an interesting state of generic templates. This limits the scope of expressive power of the automata which we call as dead state. A dead state is defined as the constraint specification. The inclusion of expressions involv- the run phase of the automata in which the automata is in a state that ing nested modal constructs calls for automatic translation of con- does not have any outgoing transition. For example, S2 is a dead state straint expressions into automata. of the automata for always operator (Figure 5). • The present extension deals with only untimed (LTL) category of the modal operators where the automata template-based constraint processing is feasible. However, the constraint expression involv- ing the timed modal operators cannot be captured through the cur- rent scheme. We will take up the above mentioned issues as our future research challenges. REFERENCES Figure 5. Dead state of always automata [1] Jorge A. Baier, Fahiem Bacchus, and Sheila A. McIlraith, ‘A heuris- tic search approach to planning with temporally extended preferences’, Artificial Intelligence, 173(5-6), 593–618, (April 2009). [2] Plaban Kumar Bhowmick, Debnath Mukherjee, Prateep Misra, and Arunasish Sen, ‘A study on applicability of hierarchical task network For any value less than 3000 the automata will be in a dead state planner in smart city scenario: A smart city tour and travel planning use and will never reach the accepting state. Consequently, the accep- case’, in 27th International Conference on Computers and their Appli- tance check operator !finish will fail and the planner will back- cations (CATA-2012), pp. 252–257, (2012). track with other instantiations of variables, operators and methods. [3] Stefan Edelkamp, Shahid Jabbar, and Mohmmed Nazih, ‘Cost-Optimal Planning with Constraints and Preferences in Large State Spaces’, in This huge amount of backtracking can be avoided by making the In International Conference on Automated Planning and Scheduling planner aware of the dead state. Whenever an automata is in a dead (ICAPS) Workshop on Preferences and Soft Constraints in Planning, state (dead-C) predicate is added to the aggregated state informa- pp. 38–45, (2006). tion. The precondition of the !finish operator for a constraint C is [4] Kutluhan Erol, James Hendler, and Dana S. Nau, ‘UMCP: A sound and changed to (or (accepting-C)(dead-C)). complete procedure for hierarchical task-network planning’, in Interna- tional Conference on AI Planning Systems (AIPS), pp. 249–254, (June The improvement in performance of the planner after the inclusion 1994). of dead state is shown in Figure 6. [5] Alfonso E. Gerevini, Patrik Haslum, Derek Long, Alessandro Saetti, and Yannis Dimopoulos, ‘Deterministic planning in the fifth interna- tional planning competition: Pddl3 and experimental evaluation of the planners’, Artificial Intelligence, 173(5-6), 619–668, (April 2009). [6] Chih-Wei Hsu, Benjamin W. Wah, Ruoyun Huang, and Yixin Chen, ‘Constraint partitioning for solving planning problems with trajectory constraints and goal preferences’, in Proceedings of the 20th interna- tional joint conference on Artifical intelligence, IJCAI’07, pp. 1924– 1929, San Francisco, CA, USA, (2007). Morgan Kaufmann Publishers Inc. [7] Okhtay Ilghami and Dana S. Nau, ‘A General Approach to Synthesize Problem-Specific Planners’, Technical Report CS-TR-4597, UMIACS- TR-2004-40, University of Maryland, (2003). [8] Naiwen Lin, Ugur Kuter, and Evren Sirin, ‘Web service composition with user preferences’, in Proceedings of the 5th European seman- tic web conference on The semantic web: research and applications, ESWC’08, pp. 629–643, Berlin, Heidelberg, (2008). Springer-Verlag. [9] Alexander Nareyek, Eugene C. Freuder, Robert Fourer, Enrico Figure 6. Performance improvement due to inclusion of dead state Giunchiglia, Robert P. Goldman, Henry Kautz, Jussi Rintanen, and Austin Tate, ‘Constraints and ai planning’, IEEE Intelligent Systems, 20(2), 62–72, (March 2005). [10] Dana Nau, Tsz-Chiu Au, Okhtay Ilghami, Ugur Kuter, J. William Mur- dock, Dan Wu, and Fusun Yaman, ‘Shop2: an htn planning system’, J. Artif. Int. Res., 20(1), 379–404, (December 2003). 6 Discussion [11] Shirin Sohrabi, Jorge A. Baier, and Sheila A. McIlraith, ‘Htn planning with preferences’, in Proceedings of the 21st international jont confer- In this paper, we have adopted a domain recompilation-based tech- ence on Artifical intelligence, IJCAI’09, pp. 1790–1797, San Francisco, nique towards extending HTN planner for handling temporal con- CA, USA, (2009). Morgan Kaufmann Publishers Inc. straints. The constraints are processed by representing them into au- tomata corresponding to the modal operators used to express them. The resulting automata have been embedded into the original plan- ning domain thus generating new domain and problem descriptions that the original planner can consume without the knowledge of the existence of any constraints. We have tested different aspects of the constraint-based HTN planner with a city tour and travel domain. Different issues and limitations of the proposed extension are dis- cussed below. 20 Workshop on AI Problems and Approaches for Intelligent Environments (AI@IE 2012)