|本期目录/Table of Contents|

[1]蔡敦波,徐胜,赵彤洲*.界标知识及其应用研究进展[J].武汉工程大学学报,2013,(10):74-80.[doi:103969/jissn16742869201310015]
　CAI Dun\|bo,XU Sheng,ZHAO Tong\|zhou*.Survey of recent progress of landmark and its application[J].Journal of Wuhan Institute of Technology,2013,(10):74-80.[doi:103969/jissn16742869201310015]
点击复制

界标知识及其应用研究进展(/HTML)
分享到：

《武汉工程大学学报》[ISSN:1674-2869/CN:42-1779/TQ]

卷:
期数:
2013年10期
页码:
74-80
栏目:
机电与信息工程
出版日期:
2013-11-10

文章信息/Info

Title:
Survey of recent progress of landmark and its application
文章编号:
16742869(2013)10007407
作者:
蔡敦波1; 2;  徐胜1;  赵彤洲3*
1.武汉工程大学智能机器人湖北省重点实验室， 湖北 武汉430205；2．吉林大学符号计算与知识工程教育部重点实验室， 吉林 长春130012；3．华中科技大学自动化学院，湖北 武汉430074
Author(s):
CAI Dun\|bo1; 2;  XU Sheng1;  ZHAO Tong\|zhou3*
1.Hubei Key Laboratory of Intelligent Robot, Wuhan Institute of Technology, Wuhan 430205, China;2.Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun 130012, China;3.School of Automation, Huazhong University of Science and Technology, Wuhan 430074, China
关键词:
智能规划; 界标知识; 问题结构; 启发函数; 领域约束
Keywords:
artificial intelligence planning;  landmark;  problem structure;  heuristic function;  domain constraints
分类号:
TP181
DOI:
103969/jissn16742869201310015
文献标志码:
A
摘要:
国内外相关研究表明界标知识的三种应用角度为：设计问题分解方法、设计启发函数和设计约束传播机制。利用界标知识设计的可纳启发函数与最优松弛估计的相对误差能降低到2.5%；利用界标知识设计的经典规划启发函数对搜索算法的引导能力优于之前的启发函数；利用界标知识设计的时态规划启发函数能使规划系统得到更高质量的规划解；将界标知识转化为命题逻辑子句能在大规模困难问题上提高可满足性判定算法的求解效率.因此，界标知识在时态规划启发函数设计和基于动作序列空间的规划方法上的应用值得深入研究.
Abstract:
Related studies show that there are mainly three aspects to exploit landmarks,including designing problem partition strategies, designing heuristic functions and designing constraint propagation strategies. For classical planning, landmarks based admissible heuristics are first ones that can make the relative error to the optimal relaxed plan heuristic decrease to 2.5%, and landmarks based non\|admissible heuristics can lead to better efficiency. For temporal planning, landmarks based heuristics can lead to better plan quality. Encoded as propositional clauses, landmarks can make a propositional satisfiability testing algorithm more efficient on many large scale problems. These results indicate the hopeful exploitations of landmarks in the design of new heuristic functions for temporal planning and search strategies for plan space based planning methods.

参考文献/References:

［1］Kilby P， Slaney J， Thiébaux S， et al. Backbones and backdoors in satisfiability［C］//Proceedings of the Twentieth National Conference on Artificial Intelligence and the Seventeenth Innovative Applications of Artificial Intelligence Conference. Pittsburgh， Pennsylvania， USA：AAAI，2005(5)： 1368\|1373.［2］Zhang W.Configuration landscape analysis and backbone guided local search：Part I：Satisfiability and maximum satisfiability［J］. Artificial Intelligence， 2004， 158(1)： 1\|26.［3］Cai S， Su K， Chen Q. Ewls： A new local search for minimum vertex cover［C］//Proceedings of the Twenty\|Fourth AAAI Conference on Artificial Intelligence. Atlanta， Georgia， USA ：AAAI，2010： 45\|50.［4］Cai S， Su K， Sattar A. Local search with edge weighting and configuration checking heuristics for minimum vertex cover［J］. Artificial Intelligence， 2011， 175(9)： 1672\|1696.［5］Cai S， Su K. Configuration checking with aspiration in local search for SAT［C］// Proceedings of the Twenty\|Sixth AAAI Conference on Artificial Intelligence. Toronto， Ontario， Canada ：AAAI，2012：434\|440.［6］Porteous J， Sebastia L， Hoffmann J. On the extraction， ordering， and usage of landmarks in planning［C］//Proceedings of 6th European Conference on Planning. Toledo， Spain：Springer\|Verlag. 2001：109\|120.［7］Hoffmann J， Porteous J， Sebastia L. Ordered landmarks in planning［J］. Journal of Artificial Intelligence Research， 2004(22)： 215\|278.［8］Richter S， Helmert M， Westphal M. Landmarks revisited［C］//Proceedings of the Twenty\|Third AAAI Conference on Artificial Intelligence. Chicago， Illinois， USA：AAAI， 2008(8)： 975\|982.［9］Cai D， Yin M. On the utility of landmarks in SAT based planning［J］. Knowledge\|Based Systems， 2012(36)：146\|154.［10］Bonet B， Castillo J. A complete algorithm for generating landmarks［C］//Proceedings of 21st International Conference on Automated Planning and Scheduling. Freiburg， Germany ：AAAI，2011：315\|318.［11］Karpas E， Domshlak C. Cost\|optimal planning with landmarks［C］//Proceedings of the 21st International Joint Conference on Artificial Intelligence， Pasadena， California， USA：AAAI，2009： 1728\|1733.［12］Hu Y， Yin M， Cai D. On the Discovery and Utility of Precedence Constraints in Temporal Planning［C］//Proceedings of the Twenty\|Fifth AAAI Conference on Artificial Intelligence. San Francisco， California， USA ：AAAI，2011：1788\|1789.［13］Nguyen H K， Tran D V， Son T C， et al. On improving conformant planners by analyzing domain\|structures［C］//Proceedings of the Twenty\|Fifth AAAI Conference on Artificial Intelligence. San Francisco， California， USA：AAAI，2011： 998\|1003.［14］Porteous J， Cresswell S. Extending landmarks analysis to reason about resources and repetition［C］//Proceedings of the 21st Workshop of the UK Planning and Scheduling Special Interest Group. Delft The Netherlands，2002： 45\|54.［15］Haslum P， Slaney J， Thiébaux S. Minimal landmarks for optimal delete\|free planning［C］//Proceedings of the Twenty\|Second International Conference on Automated Planning and Scheduling. Atibaia， Sáo Paulo， Brazil：AAAI，2012：353\|357.［16］Nebel B.The FF Planning System： Fast Plan Generation Through Heuristic Search［J］.Journal of Artificial Intelligence Research， 2001(14)：253\|302.［17］Helmert M，Domshlak C.Landmarks，Critical Paths and Abstractions：What’s the Difference Anyway［C］//Proceedings of the 19th International Conference on Automated Planning and Scheduling. Thessaloniki， Greece：AAAI，2009：162\|169.［18］Pommerening F， Helmert M. Optimal Planning for Delete\|Free Tasks with Incremental LM\|Cut［C］//Proceedings of the Twenty\|Second International Conference on Automated Planning and Scheduling.Atibaia， Sáo Paulo， Brazil： AAAI，2012：363\|367.［19］胡艳梅.时序规划问题中带优先约束的启发式方法研究［D］.长春：东北师范大学，2012.Hu Yan\|mei. Research on Heuristics with Precedence Constraints for Temporal Planning［D］.Changchun：Northeast Normal University，2012.（in Chinese）［20］李颖， 金芝. 目标间顺序关系的提取及其抽象方法［J］. 软件学报， 2006，17(3)： 349\|355.Li Y， Jin Z. Goal ordering extraction and abstract method. Journal of Software， 2006，17(3)：349?355.（in Chinese）［21］梁瑞仕， 姜云飞， 边芮， 等. 智能规划中的可纳子目标排序［J］. 软件学报， 2011， 22(5)： 914\|928.Liang R S， Jiang Y F， Bian R，et al.Admissible subgoal ordering for automated planning［J］. Journal of Software， 2011， 22(5)：914\|928.（in Chinese）［22］张彦铎， 李哲靖， 鲁统伟. 机器人世界杯足球锦标赛中多机器人对目标协同定位算法的改进［J］. 武汉工程大学学报， 2013， 35(2):69\|73.ZHANG Yan\|duo，LI Zhe\|jing，LU Tong\|wei.Improvements of collaborative localization algorithm of multi\|robot on target in ROBOCUP［J］. Journal of Wuhan Institute of Technology， 2013， 35(2):69\|73.（in Chinese）［23］鲁统伟， 林芹， 李熹， 等. 记忆运动方向的机器人避障算法［J］. 武汉工程大学学报， 2013， 35(4):66\|70.LU Tong\|wei， LIN Qin， LI Xi， et al. Obstacle avoidance algorithm of robot based on recording move direction［J］. Journal of Wuhan Institute of Technology， 2013， 35(4):66\|70.（in Chinese）

相似文献/References:

备注/Memo

备注/Memo:
收稿日期：20130917基金项目：国家自然科学基金(61103136)；武汉工程大学青年科学研究基金(12106022)作者简介：蔡敦波（1981\|），男，内蒙古通辽人，讲师，博士.研究方向：智能规划、自动推理.*通信联系人
更新日期/Last Update: 2013-11-11