Refinement of intentions

  • Zhanhao Xiao

Western Sydney University thesis: Doctoral thesis

Abstract

The mental attitudes, such as belief, desire, and intention, play a central role in the design and implementation of autonomous agents. In 1987, Bratman proposed a so-called belief-desire-intention (BDI) theory which inspired a multitude of BDI logics and BDI architectures. 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 stepwise refined into more elaborated plans. Ideally the plans at the end of the refinement process contain only basic actions which the agent can perform directly. The process of intention refinement is crucial to the BDI theory and every step of refinement establishes a means-end relation between the refined intentions and the intentions refining it. However, there are very few accounts of hierarchical intention refinement in the existing BDI logics. The concept of automated planning is central in Bratman's theory. As a traditional research community of artificial intelligence, automated planning has attracted numerous attentions and it has already been integrated into BDI architectures. In particular, the way of generating solutions in hierarchical task network (HTN) planning is refining high-level actions step-by-step until basic actions. Thus, the idea of HTN planning should be revelent for BDI agents. However, except for the line of work of de Silva and Sardina et al., hierarchical intention refinement has been scarcely considered in the existing BDI agents. The aim of this thesis is to provide a logic-based comprehensive analysis of the hierarchical refinement process. In this thesis, intention refinement is considered from two perspectives: the entailment and the primitive. From the former, intentions are managed in a co-called belief-intention database where refinement is addressed via the logical entailment based on the action law; while from the latter, refinement is defined in an explicit and static way, just as in HTN planning. From the entailment perspective, this thesis starts with an extension of Shoham's database framework on beliefs and intentions by introducing the notions of high-level intentions and environmental events. In a belief-intention database, a set of intentions can refine an intention if the set is minimal and suffices to guarantee the satisfaction of the intention. This thesis also investigates the complexity of the decision problems of satisfiability, consequence, refinement, instrumentality in the proposed database framework, which are all PSPACE-complete. Furthermore, this thesis explores the relations between the database framework and two logics: propositional linear temporal logic and dynamic logic with propositional assignment. The reductions to these two logics contribute to finding a set of intentions to refine a high-level intention via invoking the automated tools for these two logics. From the primitive perspective, this thesis provides a logical semantics for HTN planning based on propositional dynamic logic. In the dynamic framework, refinement is captured by the program inclusion operator. By equipping high-level actions with pre- and post-condition, a coherence condition for HTN domains is proposed to evaluate the correctness of the predefined refinement methods. Moreover, the postulates of soundness and completeness for high-level actions are given under the dynamic semantics. When it comes to the completeness, it is usually a big challenge to define all possible refinement methods in HTN planning. It is promising to relax some restrictions on solutions: Geier & Bercher's HTN planning with task insertion (TIHTN) allows solutions obtained by inserting actions. To capture the pre- and post-condition of actions, this thesis further extends TIHTN by introducing state constraints and calls the extension TIHTNS planning. It has been shown that the property of acyclic decomposition still holds in TIHTNS planning and then an acyclic progression operator for finding a plan is proposed. Based on the progression operator, it is proved that the additional consideration of state constraints does not increase the complexity of the plan-existence problem, staying in 2-NEXPTIME-complete.
Date of Award2018
Original languageEnglish

Keywords

  • intelligent agents (computer software)
  • databases
  • logic programming
  • artificial intelligence
  • linear temporal logic
  • problem solving

Cite this

'