Approximation of action theories and its application to conformant planning
Approximation of action theories and its application to conformant planning
复制标题
DOI：
10.1016/j.artint.2010.04.007
复制
发表时间：
2005-09
期刊：
影响因子：
--
通讯作者：
Tran Cao Son;P. Tu;M. Gelfond;A. Morales
中科院分区：
文献类型：
--
作者：
Tran Cao Son;P. Tu;M. Gelfond;A. Morales
本文介绍了我们的方法，建设符合规划师，这是基于最近的进展，在理论的行动和变化和答案集编程。一个给定的动态域的规划器的发展开始与编码的流畅性和域的动作作为一些动作语言的动作理论D的知识。我们在本文中的选择是AL -一个动作语言的动态和静态的因果规律和可执行性条件。AL的行动理论D定义了包含域的所有可能轨迹的转移图T（D）。一个转移s，a，s′ n属于T（D）当且仅当在状态s中执行动作a可以将域移动到状态s′。规划器开发的第二步是找到一个确定性转移图Tlp（D），使得Tlp（D）的节点是D的部分状态，其弧由动作标记，并且Tlp（D）中从初始部分状态δ 0到满足目标δ f的部分状态的路径对应于δ 0和δfin T（D）的一致规划。过渡图Tlp（D）被称为T（D）的“近似”。我们认为，在回答集语义下，逻辑程序π（D）往往可以给出T（D）的一个近似的简洁描述.此外，复杂的初始情况和计划约束也可以用逻辑规划规则表示，并包含在π（D）中。如果这是可能的，那么找到并行或顺序一致计划的问题可以简化为计算π（D）的答案集。这可以通过通用答案集求解器来完成。如果计划是连续的和长的，那么这种方法可能太耗时。在这种情况下，π（D）被用作过程图搜索一致规划算法的规范。本文阐述了这种方法，通过建立几个一致的规划工作的领域与复杂的关系之间的流畅。规划者的效率进行了实验评估的一些新的和旧的基准。此外，我们表明，对于一个子类的行动理论的AL我们的计划是完整的，即，如果在Tlp（D）中我们不能从δ 0到达满足目标δ f的状态，则对于δ 0和δfin T（D）没有一致的计划。
This paper describes our methodology for building conformant planners, which is based on recent advances in the theory of action and change and answer set programming. The development of a planner for a given dynamic domain starts with encoding the knowledge about fluents and actions of the domain as an action theory D of some action language. Our choice in this paper is AL – an action language with dynamic and static causal laws and executability conditions. An action theory D of AL defines a transition diagram T(D) containing all the possible trajectories of the domain. A transition 〈s,a,s′〉 belongs to T(D) iff the execution of the action a in the state s may move the domain to the state s′. The second step in the planner development consists in finding a deterministic transition diagram Tlp(D) such that nodes of Tlp(D) are partial states of D, its arcs are labeled by actions, and a path in Tlp(D) from an initial partial state δ0to a partial state satisfying the goal δfcorresponds to a conformant plan for δ0and δfin T(D). The transition diagram Tlp(D) is called an ‘approximation’ of T(D). We claim that a concise description of an approximation of T(D) can often be given by a logic program π(D) under the answer sets semantics. Moreover, complex initial situations and constraints on plans can be also expressed by logic programming rules and included in π(D). If this is possible then the problem of finding a parallel or sequential conformant plan can be reduced to computing answer sets of π(D). This can be done by general purpose answer set solvers. If plans are sequential and long then this method can be too time consuming. In this case, π(D) is used as a specification for a procedural graph searching conformant planning algorithm. The paper illustrates this methodology by building several conformant planners which work for domains with complex relationship between the fluents. The efficiency of the planners is experimentally evaluated on a number of new and old benchmarks. In addition we show that for a subclass of action theories of AL our planners are complete, i.e., if in Tlp(D) we cannot get from δ0to a state satisfying the goal δfthen there is no conformant plan for δ0and δfin T(D).