¡¡Chinese Journal of Computers   Full Text
  TitleA Comparison of Semantics of Extended Goals Expressed in CTL and EAGLE
  AuthorsHUANG Wei1) JIANG Yun-Fei2) WEN Zhong-Hua3) PENG Hong1)
  Address1)(School of Computer Science & Engineering, South China University of Technology, Guangzhou 510641)
2)(Software Research Institute, Sun Yat-Sen University, Guangzhou 510275)
3)(College of Information Engineering, Xiangtan University, Xiangtan, Hunan 411105)
  Year2009
  IssueNo.1(86¡ª96)
  Abstract &
  Background 		Abstract In automated planning under uncertainty, extended goals are often expressed as temporal logic formulas, particularly as CTL(computation tree logic) formulas and EAGLE formulas. Though it is said that the capability of representing the ¡°intentional¡± aspects of goals and the possibility of dealing with failure are the main new features of EAGLE with respect to CTL, there is not enough work devoted to formal comparison of semantics of these two languages. According to the formal semantics of EAGLE and CTL goals on Kripke structures (i.e., execution structures induced by plans from initial states), it is proven that many EAGLE goals including some having been deemed to be unexpressive in CTL(e.g., some EAGLE goals in which TryReach operator and Fail operator appear) can be expressed in CTL in fact, and an analysis of the characters of these two languages in expressing extended goals and guiding the search for plans that satisfy them is given.
Keywords automated planning under uncertainty; extended goal; execution structure; CTL(computation tree logic); EAGLE
Background This work is an important component of the research on domain knowledge extraction, which is one of the main tasks of ¡°the Research on Domain Knowledge Extraction and Reasoning in Automated Planning¡± project. The project aims to propose an efficient planning algorithm that can make use of domain knowledge, and it includes three main tasks: (1) the research on domain knowledge extraction, (2) the research on domain knowledge reasoning and, (3) the study of strategies for domain knowledge utilization in automated planners. The project is supported by the National Natural Science Foundation of China under grant No.60773201, the Guangdong Natural Science Foundation under grant No.07006474, and the Guangdong Scientific and Technological Project Foundation under grant No.2007B01020044.
Some achievements of the planning group are reached by now: A formalism of planning with domain constraint based on model checking, a new SAT planner using genetic algorithm for solving SAT problems based on learning clause weights, a research on relations of effect of action for STRIPS domain, a strategy of extracting domain knowledge, and the first algorithm called STRONG-FO-PO for observation reduction of strong plans under full observability, which are presented by Wu Kang-Hen, Ling Ying-Biao, Wu Xiang-Jun, Jiang Yun-Fei and Huang Wei et al.