利用派生谓词和偏好处理OSP 问题的目标效益依赖
作者:
基金项目:

国家自然科学基金(61100134, 61003179, 60903178); 广东省自然科学基金(S2011040001427)


Handling Goal Utility Dependencies in OSP Problems with Derived Predicates and Preferences
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [28]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    在过度规划问题(over-subscribed planning,简称OSP)研究中,如果目标之间不是相互独立的,那么目标间的效益依赖比单个目标效益更能提高规划解的质量.但是已有的描述模型不符合标准规划描述语言(planning domain description language,简称PDDL)的语法规范,不能在一般的OSP 规划系统上进行推广.提出了用派生谓词规则和目标偏好描述效益依赖的方法,这二者均为PDDL 语言的基本要素.实质上,将已有的GAI 模型转换为派生谓词规则和目标偏好,其中派生谓词规则显式描述目标子集的存在条件,偏好机制用来表示目标子集的效益,二者缺一不可.该转换算法既可以保持在描述依赖关系时GAI 模型的易用性和直观性上,又可以扩展一般的OSP 规划系统处理目标效益依赖的能力.从理论上可以证明该算法在转换过程中的语义不变性,在基准领域的实验结果表明其可行性和对规划解质量的改善能力.提出符合PDDL 语言规范的目标效益依赖关系的描述形式,克服了已有模型不通用的缺点.

    Abstract:

    In the field of over-subscribed planning (OSP), goal utility dependencies are more useful than a single goal utility used to improve the plan quality, if goals are not independent. However, existing description models do not follow the grammatical specification of standard planning domain description language (PDDL), so they cannot be used in other OSP planning systems yet. To solve this, this paper presents a new way of describing goal utility dependencies with derived predicate rules and goal preferences, both of which are essential elements of PDDL. The goal of the process is to transform GAI (general additive independence) models into these two elements, where a derived predicate rule is used to describe the explicitly triggering conditions of a goal sub-set. A preference is used to depict explicitly its utility or value and both are indispensable. This compilation mechanism can not only maintain the characteristic of ease-of-use and straightness of GAI models in describing utility dependencies, but can also expend the ability of handling utility dependencies for general OSP planning systems. Also, this paper proves the semantic conservation in the compilation process. Experimental results in some OSP benchmark domains show that the algorithm is feasible and useful for improving the plan quality. It is the first time to describe goal utility dependency with PDDL elements in order to overcome the limitations of existing models.

    参考文献
    [1] Smith DE. Choosing objectives in oversubscription planning. In: Zilberstein S, Koehler J, Koenig S, eds. Proc. of the 14th Int’l Conf. on Automated Planning and Scheduling. Menlo Park: AAAI, 2004. 393-401.
    [2] Ghallab M, Nau D, Traverso P. Automated Planning: Theory and Practice. San Fransisco: Morgan Kaufmann Publishers, 2004. 1-663.
    [3] Do MB, Benton J, Van den Briel MHL, Kambhampati S. Planning with goal utility dependencies. In: Veloso MM, ed. Proc. of the 20th Int’l Joint Conf. on Artificial Intelligence. Menlo Park: AAAI, 2007. 1872-1878.
    [4] Benton J. Solving goal utility dependencies and simple preferences in partial satisfaction planning. In: Proc. of the Int’l Conf. on Automated Planning and Scheduling—Doctoral Consortium. 2006. 1-3. http://www.plg.inf.uc3m.es/icaps06/doctoral.htm
    [5] Russell R, Holden S. Handling goal utility dependencies in a satisfiability framework. In: Brafman RI, Geffner H, Hoffmann J, Kautz HA, eds. Proc. of the 20th Int’l Conf. on Automated Planning and Scheduling. Menlo Park: AAAI, 2010. 145-152.
    [6] Benton J, Do MB, Kambhampati S. Over-Subscription planning with numeric goals. In: Kaelbling LP, Saffiotti A, eds. Proc. of the 19th Int’l Joint Conf. on Artificial Intelligence. Menlo Park: AAAI, 2005. 1207.1213.
    [7] Li L, Onder N. Generating plans in concurrent, probabilistic, over-subscribed domains. In: Fox D, Gomes CP, eds. Proc. of the 23rd National Conf. on Artificial Intelligence. Menlo Park: AAAI, 2008. 1857.1858.
    [8] Nigenda RS, Kambhampati S. Planning graph heuristics for selecting objectives in over-subscription planning problems. In: Biundo S, Myers KL, Rajan K, eds. Proc. of the 15th Int’l Conf. on Automated Planning and Scheduling. Menlo Park: AAAI, 2005. 192.201.
    [9] Edelkamp S, Hoffmann J. PDDL2.2: The language for the classical part of the 4th Int’l planning competition. Technical Report, 195, Freiburg, 2004. 1.21.
    [10] Thielscher M. Ramification and causality. Artificial Intelligence, 1997,89(1-2):317.364. [doi: 10.1016/S0004-3702(96)00033-1]
    [11] Meuleau N, Brafmany R, Benazeray E. Stochastic over-subscription planning using hierarchies of MDPs. In: Long D, Smith SF, Borrajo D, McCluskey L, eds. Proc. of the 16th Int’l Conf. on Automated Planning and Scheduling. Menlo Park: AAAI, 2006. 121.130.
    [12] Benton J, Kambhampati S, Do MB. YochanPS: PDDL3 simple preferences as partial satisfaction planning. In: Proc. of the 16th Int’l Conf. on Automated Planning and Scheduling—IPC5 Booklet. 2006. 1.3. http://zeus.ing.unibs.it/ipc-5/
    [13] Gerevini A, Saetti A, Serina I, Toninelli P. Fast planning in domains with derived predicates: An approach based on rule-action graphs and local search. In: Veloso MM, Kambhampati S, eds. Proc. of the 20th National Conf. on Artificial Intelligence. Menlo Park: AAAI, 2005. 1157.1162.
    [14] Coles AI, Smith AJ. Marvin: Macroactions from reduced versions of the instance. In: Booklet of the 4th Int’l Planning Competition. 2004. 24.26. http://www.tzi.de/~edelkamp/ipc-4/publication.html
    [15] Hsu CW, Wah BW. The SGPlan planning system in IPC-6. In: Booklet of the Deterministic Part of the 6th Int’l Planning Competition. 2008. 1.3. http://ipc.informatik.uni-freiburg.de/Planners
    [16] Thiébaux S, Hoffmann J, Nebel B. In defense of PDDL axioms. Artificial Intelligence, 2005,168(1-2):38.69. [doi: 10.1016/j.artint.2005.05.004]
    [17] Jiang ZH, Jiang YF. An improved method for calculating activation sets of action derived preconditions. Chinese Journal of Computers, 2007,29(12):2061.2073 (in Chinese with English abstract).
    [18] Jiang ZH, Jiang YF. Planning with derived predicates based on their state-independent activation sets. Computer Science, 2007, 34(3):176.180 (in Chinese with English abstract).
    [19] Rao DN, Jiang ZH, Jiang YF, Liu Q. Learning first-order rules for derived predicates from plan examples. Chinese Journal of Computers, 2009,33(2):251.266 (in Chinese with English abstract). [doi: 10.3724/SP.J.1016.2009.00251]
    [20] Gerevini A, Long D. Bnf description of pddl3.0. 2005. 1.7. http://ipc5.ing.unibs.it
    [21] Gerevini A, Long D. Plan constraints and preferences in PDDL3. Technical Report, 2005-08-07/, Brescia, 2005. 1.12.
    [22] Edelkamp S, Kissmann P. Optimal symbolic planning with action costs and preferences. In: Boutilier C, ed. Proc. of the 21st Int’l Joint Conf. on Artificial Intelligence. Menlo Park: AAAI, 2009. 1690.1695.
    [23] Sohrabi S, Baier JA, McIlraith SA. HTN planning with preferences. In: Boutilier C, ed. Proc. of the 21st Int’l Joint Conf. on Artificial Intelligence. Menlo Park: AAAI, 2009. 1790.1797.
    [24] Davidson M, Garagnani M. Pre-Processing planning domains containing language axioms. In: Grant T, Witteveen C, eds. Proc. of the 21st Workshop of the UK Planning and Scheduling SIG. 2002. 23.34.
    [25] Edelkamp S, Jabbar S. Cost-Optimal external planning. In: Proc. of the 21st National Conf. on Artificial Intelligence. Menlo Park: AAAI, 2006. 821.826.
    [26] Haslum P, Bonet B, Geffner H. New admissible heuristics for domain-independent planning. In: Veloso MM, Kambhampati S, eds. Proc. of the 20th National Conf. on Artificial Intelligence. Menlo Park: AAAI, 2005. 1163.1168.
    [27] Edelkamp S, Jabbar S, Nazih M. Large-Scale optimal PDDL3 planning with MIPS-XXL. In: Long D, Smith SF, Borrajo D, McCluskey L, eds. Proc. of the 16th Int’l Conf. on Automated Planning and Scheduling. Menlo Park: AAAI, 2006. 81.92.
    [28] Bacchus F, Grove A. Graphical models for preference and utility. In: Besnard P, Hanks S, eds. Proc. of the 11th Annual Conf. on Uncertainty in Artificial Intelligence. San Francisco: Morgan Kaufmann Publishers, 1995. 3.10.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

蒋志华,饶东宁,姜云飞,翁健.利用派生谓词和偏好处理OSP 问题的目标效益依赖.软件学报,2012,23(3):439-450

复制
分享
文章指标
  • 点击次数:4452
  • 下载次数: 5674
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2010-11-09
  • 最后修改日期:2011-01-06
  • 在线发布日期: 2012-03-05
文章二维码
您是第19781238位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号