Refinement of Intentions

1 Background andMotivations

The mental attitudes of belief, desire, and intention play a central role in the design and implementation of autonomous agents. In 1987 [Bratman] proposed their integration into a belief-desire-intention (BDI) theory that was seminal in AI. Since then numerous approaches were built on the BDI paradigm, both practical (BDI architectures and BDI agents) and formal (BDI logics). The logical approaches that were the most influential are due to [Cohen and Levesque, 1990] and to [Rao and Georgeff, 1991]. However, the practical and logical approaches evolved separately and neither was fruitful for the other.

Bratman highlighted the fundamental role of an agent's future-directed intentions: they are high-level plans to which the agent is committed. Such high-level plans cannot be executed directly: they have to be refined, resulting in more and more elaborate plans. Taking the example of going to Melbourne, Figure 1 shows the process of refinement. The lower-level intentions that are inserted are instrumental for the high-level intention they refine [Bratman, 2009]. At the end of the refinement process plans only contain basic actions: actions the agent can perform intentionally. The operations of refinement of intentions are fundamental in the BDI model. As pointed out in [Rao and Georgeff, 1991], "the potential of non-primitive events for decomposition into primitive events can be used to model hierarchical plan development". However, the instrumentality relation between higher-level and lower-level intentions is not accounted for in the existing BDI logics, including Cohen&Leveques's and Rao&Georgeff's BDI theories and those inspired by their theories, where intentions are viewed as a basic attitude and in consequence there is no appropriate account of intention refinement. The aim of this research project is to provide a logical analysis of this hierarchical refinement process.

2 Progress

We first focus on establishing a logical formalism for highlevel intentions. We tackle the problem by pushing further Shoham's database perspective [Shoham, 2009]which is based on databases of time-indexed basic actions and beliefs. Shoham's database perspective is a much simpler starting point than the rather complex theories of intention due to [Cohen and Levesque, 1990] and to [Rao and Georgeff, 1991] and others, while being more suitable for a logical analysis than existing, heavily implementation-driven BDI agents. We believe it to be a promising basis for a logical analysis of beliefs and intentions.

We have presented a unified logical framework that generalizes Shoham's database perspective by introducing highlevel intentions with a flexible duration [Herzig et al., 2016b]. High-level actions differ from primitive actions in performing durations where high-level actions require more than one time unit while primitive actions cost one time unit; and in postconditions where the postconditions of high-level actions are arbitrary while primitive actions have explicit positive and negative effects in form of a conjunction of literals.

We then define the operation of refinement in a logical way: to refine an intention i means to introduce a minimal set of new intentions which, together with other intentions but i, suffice to guarantee satisfaction of i. Then we establish the instrumentality relation among intentions based on the refinement operation: the refined higher-level intention is supported by the lower-level intentions refining it where the checking-refienment problem is PSPACE-complete.

Refinement of intentions is closely related to Hierarchical Task Networks (HTN) planning [Erol et al., 1994]. The HTN solutions are generated by decomposing high-level actions step-by-step into lower-level actions where the decomposition process is nothing but the refinement process. However, the decomposition is based on syntax: all decomposition methods have to be defined by hand by the designer of the planning domain, and in consequence intention refinement has to be handled totally by an underlying predefined set of decomposition methods in a static way. HTN with task insertion [Geier and Bercher, 2011] (TIHTN), a variant of HTN, overcomes the restriction by allowing solutions generated by both decomposition and insertion of tasks from outside the hierarchy of decomposition. The plan existence problem for (propositional) TIHTN has been proved NEXPTIMEcomplete [Alford et al., 2015].

However, the original TIHTN only considers ordering constraints restricting some task has to be performed before another task. We have extended TIHTN with state constraints to capture the pre- and postcondition of compound tasks (highlevel intentions) [Xiao et al., 2017]. We also prove the extension by state constraints does not cause an increase on complexity, staying in NEXPTIME.

In addition, we have developed the first implementation of TIHTN planning via answer set programming which demonstrates that it is feasible to build up the TIHTN planner.

We also embedded propositional HTN planning with a restriction that all subtasks in the methods are total ordered into propositional dynamic logic [Herzig et al., 2016a].

3 FutureWork

We have presented a logical framework for intention refinement and presented a decidable variant of HTN planning with state constraints to capture high-level intentions. Indeed the decomposition process in HTN planning is analogous to the refinement process of intentions. However, it is a challenge to define all possible decomposition methods for all high-level actions. Comparing defining refinement of intentions in a predefined and syntax way, we are convinced that it is a good way to root refinement in a semantics level where the hierarchical decomposition is viewed as a kind of manmade heuristics. On the other way, the instrumentality relation from our logical framework can provide clues for designing and improving decomposition domains in HTN planning.

The proposed notion of instrumentality based on intention refinement paves the way for revision of intentions: when dropping a high-level intention we also drop the lower-level intentions that are instrumental for it. There is currently few work on linking intention revision with instrumentality, except for [Shapiro et al., 2012] which models intention revision by considering relations between a predefined library of plans and intentions. We believe that our logical framework, probably combined with [Zee et al., 2015] which proposed AGM-like revision postulates for belief about time and actions, provides a good starting point for an intention revision theory based on instrumentality relations among intentions.