目标间顺序关系的提取及其抽象方法
作者:
基金项目:

Supported by the National Natural Science Foundation of China under Grant Nos.60233010, 60496324 (国家自然科学基金); the National Grand Fundamental Research 973 Program of China under Grant No.2002CB312004 (国家重点基础研究发展规划(973)); the Knowledge Innovation Program of the Chinese Academy of Sciences(中国科学院知识创新工程)


Goal Ordering Extraction and Abstract Method
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [21]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    规划问题是一类复杂的问题.由于规划问题中各个目标之间往往存在着实现上的顺序关系,发掘这种顺序关系并加以利用是提高规划算法效率的一种途径.由于判定目标间的顺序关系同样是PSPACE完全的,因而为利用目标间的顺序关系首先需要有效地提取目标间的顺序关系.给出了一种利用状态不变式来提取目标间顺序关系的GOWN(goal ordering with invariants)方法,并在比较目标间的顺序关系时,通过抽象和合一的手段,有效地控制了问题的增长规模,提高了处理效率.

    Abstract:

    Planning is a class of complex problem. It is a way to improve the efficiency of planning algorithm in extracting and using goal orderings. Because deciding goal orderings is also PSPACE-complete, it is necessary to extract goal orderings efficiently when using goal orderings. The paper presents a method, called GOWN (goal ordering with invariants) and uses state invariants to extract goal orderings. During the process of ordering, abstraction and unification are utilized to control the increase of problem size that improves the efficiency of ordering.

    参考文献
    [1]Russell S,Norvig P.Artificial Intelligence:A Modern Approach.Beijing:Posts & Telecommunications Press,
    [2]Weld DS.Recent advances in AI planning.AI Magazine,1999,20(2):93-123.
    [3]Lu RQ.Artificial Intelligence.Beijing:Science Press,2000 (in Chinese).
    [4]Ding DL,Jiang YF.Research on intelligent planning and application.Computer Science,2002,29(3):100-103 (in Chinese with English abstract).
    [5]Wu KH,Jiang YF.Planning with domain constraints based on model-checking.Journal of Software,2004,15(11):1629-1640 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/15/1629.htm
    [6]Fikes RE,Nilsson NJ.STRIPS:A new approach to the application of theorem proving to problem solving.Artificial Intelligence,1971,2(3-4):189-208.
    [7]Erol K,Nau DS,Subrahmanian VS.On the complexity of domain-independent planning.In:Swartout WR,ed.Proc.of the 10th AAAI National Conf.San Jose:AAAI Press/The MIT Press,1992.381-386.
    [8]KoehlerJ,Hoffmann J.On reasonable and forced goal orderings and their use in an agenda-driven planning algorithm.Journal of Artificial Intelligence Research,2000,12:338-386.
    [9]Hoffmann J.Utilizing problem structure in planning:A local search approach.LNAI2854,Springer-Verlag,2003.
    [10]Chen YX,Hsu CW,Wah BW.SGPlan:Subgoal partitioning and resolution in planning.In:Proc.of the 4th Int'l Planning Competition,Int'l Conf.on Automated Planning and Scheduling.2004.30-32.
    [11]Knoblock CA.Automatically generating abstractions for planning.Artificial Intelligence,1994,68(2):243-302.
    [12]Fink E,Veloso M.Prodigy planning algorithm.Technical Report,CMU-94-123,Carnegie Mellon University,1994.
    [13]Porteous J,Sebastia L,Hoffmann J.On the extraction,ordering,and usage of landmarks in planning.In:Proc.of the 6th European Conf.on Planning (ECP 01).2001.37-48.
    [14]Gerevini A,Schubert L.Inferring state constraints for domain-independent planning.In:Proc.of the 15th National Conf.on AI and the 10th Conf.on Innovative Applications of AI.AAAI Press/The MIT Press,1998.905-912.
    [15]Fox M,Long D.The automatic inference of state invariants in TIM.Journal of Artificial Intelligence,1998,9:367-421.
    [16]Rintanen J.An iterative algorithm for synthesizing invariants.In:Proc.of the 17th National Conf.on AI and the 12th Innovative Application of AI.AAAI Press/The MIT Press,2000.806-811.
    [17]The Int'l Conf.on Automated Planning and Scheduling.http://www.icaps.org/
    [18]Blum A,Langford JC.Fast planning through planning graph analysis.Journal of Artificial Intelligence,1997,90(1-2):281-300.
    [3]陆汝钤.人工智能北京:科学出版社,2000.
    [4]丁德路,姜云飞智能规划及其应用的研究.计算机科学,2002,29(3):100-103.
    [5]吴康恒,姜云飞.基于模型检测的领域约束规划.软件学报,2004,15(11):1629-1640.http://wwwjos.org.cn/1000-9825/15/1629.htm
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

李颖,金芝.目标间顺序关系的提取及其抽象方法.软件学报,2006,17(2):349-355

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

京公网安备 11040202500063号