智能规划方法中启发式搜索策略的研究
|
摘要
基于启发式搜索的规划方法是当前智能规划研究的热点，本文针对搜索算法和剪枝策略这两个影响规划求解效率的关键因素进行了深入研究，为经典规划问题和不确定规划问题设计了更灵活的启发式搜索算法和剪枝策略，具体内容如下：
（1）提出一种利用路标信息隐式分解前向搜索过程的规划方法，根据路标计数启发式的估值将规划任务分解成多个规模更小的子任务，搜索过程在路标计数启发式的引导下快速向目标方向推进，实现搜索空间的大规模压缩。
（2）提出基于缩减信念状态的Conformant规划方法，搜索规划解之前先将初始信念状态转换为不确定性更低的状态，再搜索给定问题的目标。降低信念状态不确定性的方法能够减小问题的求解难度，改善规划系统的求解效率。
（3）提出一种Conformant规划下利用有利动作构造新型剪枝策略的方法，根据放松规划解的计算过程给出有利蕴含路径的概念，扩展信念状态时优先应用有利蕴含路径，对搜索空间的探索速度更快。
（4）提出Contingent规划下带有强制观察的剪枝策略，通过修改放松规划图的构造过程使得有利动作集合能够提取出观察当前不确定信息的动作，根据观察结果执行不同的求解动作，符合分支规划解的执行语义。
AI planning has been a main research field of Artificial Intelligence. In recent ten years,the research of AI planning has made a big breakthrough and obtained significantimprovement in both planning efficiency and quality of the plans. Heuristic search planninghas been a hot topic and one of the most powerful planning methods. The basic idea ofheuristic search framework is to guide the search procedure with some domain knowledge andmake the search direction going towards to the goal rapidly. The usage of heuristicinformation can mitigate the combination explosion of the search space effectively.
The main difficulty of heuristic search planning is the poor performance for problemswith complicated structure or big size. Researchers have introduced kinds of new searchalgorithms into the heuristic search planning framework, and it is still a huge challenge todesign an accurate and common heuristic function. Moreover, pruning is another importantstrategy to control the size of the search space.
This thesis mainly focuses on the search algorithm and pruning strategy, both of whichare crucial to performance of planning systems based on heuristic search. With theinformation provided by heuristic evaluation, the selected search algorithm determines theorder to explore the states in the search space. The difference of various search algorithms isthe tie-breaking rule in face of all the candidate states. Good decision can help to solve theplanning problem quickly and obtain a shorter solution, which would save the cost of thesearch procedure. Therefore, the rule of tie-breaking has a great influence on the behavior ofsearch algorithm. We proposed flexible heuristic search algorithms for classical andconformant planning tasks according to their structures, the main contributions include:
The idea of landmark-counting heuristic is to guide the search towards the states thatachieve more landmarks, which seems to be a segment heuristic of the search space. Weproposed a search algorithm that decomposes the planning task with the estimation of thelandmark-counting heuristic, where the original planning task is decomposed into severalsmaller sub-tasks implicitly. During the forward search, the decrease of thelandmark-counting heuristic value causes the task decomposition. Such sub-task procedure isrepeated until the estimation of the landmark-counting heuristic decreased to zero in the goalstate. The landmark-counting heuristic plays an assistant role in the whole search procedure,evaluating the computation that is necessary to reach the goal from each search state, whichmakes a better use of the landmark information. Experiment results on the representationalbenchmarks show the superiority of our algorithm. Compared to the multi-queue heuristicsearch and the task decomposition that treats the landmarks as mandatory intermediate subgoals, our planning algorithm based on the implicit task decomposition leads aconcentrated search direction, which could guide the forward search procedure towards thegoal faster and cut down the search space dramatically.
The planning system Conformant-FF translates conformant planning tasks into beliefspace search problems and adopts the enforced hill-climbing algorithm guided by the relaxedplan heuristic function. However, the helpful actions given by implications about theunknown propositions may make mistakes on domains that contain plenty of uncertaininformation, which makes Conformant-FF show bad performance on such domains. Withregard to this limitation, we propose a conformant planning algorithm that reduces thenondeterministic degree of belief states. The algorithm includes two phases of enforcedhill-climbing, which are used to reduce belief states and search for the goal respectively.Before searching for the given goal condition, the initial belief state is reduced furthest to anintermediate state which is much more deterministic. After that, the precision of heuristicevaluation is improved and the second normal enforced hill-climbing phase is executed fromthis intermediate state. We implement our idea based on Conformant-FF, design a planningsystem named CFF-Lite and experiment on a number of conformant benchmarks. The resultsshow that CFF-Lite can decrease the difficulty of conformant planning problems by reducingbelief states and our algorithm outperforms Conformant-FF in both planning efficiency andthe quality of plan.
Heuristic evaluation of the search states is one of the most time-consuming parts duringthe search procedure, thus the number of visited states affects the time efficiency directly.Pruning strategy controls the size of the search space when expanding the search states, whichcould decrease the states visited by the search algorithm. Excellent pruning strategy shouldkeep the states that are helpful to solve the problem faster and dump all the states that wouldget far away from the goal state or slow the search process down. Pruning is quite importantfor the performance of heuristic search algorithms. Heuristic function based on relaxed planprovides the helpful action pruning strategy, where the actions that may get closer to the goalare recognized as helpful. The helpful actions generate a set of promising successors to eachsearch state, bringing a compression of the search space. We propose to construct new pruningstrategies for conformant and contingent planning tasks on basis of helpful actions. Ourcontributions are as follows:
On analysis of the conformant relaxed plans, we get the “solving by cases” semantic ofthe implication paths for subgoals in the relaxed planning graph and introduce a furtherdefinition of helpful implication paths. We propose the novel pruning strategy of helpfulimplication paths for conformant planning tasks. A helpful implication path is usually madeup of several helpful actions. When expanding the belief states, executing all actions within ahelpful implication path can achieve some subgoal while executing an individual action cannot due to incomplete information. This strategy usually explores a much further range of thesearch space within one search iteration, and thus leads to the goal faster. We experiment on a number of conformant benchmarks to evaluate our idea. The results show that our pruningstrategy performs better than the old helpful action strategy for conformant planning tasks.The pruning strategy of helpful implication path can concentrate on the uncertainty of theestimated belief state when exploring the search space, reduce the number of visited states andbring an improvement of runtime efficiency.
To overcome the shortcoming that helpful actions under contingent planning fail to findbranching plans, a pruning strategy with enforced observations is presented. We change theway to treat the effects with unknown condition in the first level, making the uncertainty ofthe estimated belief state have opportunities to be observed. Then the adjusted relaxed plancan collect the observation actions that sense the truth value of the current unknownpropositions, and recognize them as helpful actions, which means to perform enforcedobservations to the uncertain information in the environment. The branching plan represents aconditional semantic that applies different actions according to the result of observation atruntime. With our revision, the unreasonable conformant actions can be excluded from the setof helpful actions and consequently we cut all the non-branching plans out of the solutionspace, which can improve the planning efficiency as well as the plan quality. Experimentresults on the representational contingent benchmarks have proven the superiority of ourpruning strategy in generating branching plans.
In conclusion, this thesis concerns the search algorithms and pruning strategies inheuristic search planning framework for classical planning and nondeterministic planning, thecontributions are significant for the improvement of planning efficiency and the plan quality.
（1）提出一种利用路标信息隐式分解前向搜索过程的规划方法，根据路标计数启发式的估值将规划任务分解成多个规模更小的子任务，搜索过程在路标计数启发式的引导下快速向目标方向推进，实现搜索空间的大规模压缩。
（2）提出基于缩减信念状态的Conformant规划方法，搜索规划解之前先将初始信念状态转换为不确定性更低的状态，再搜索给定问题的目标。降低信念状态不确定性的方法能够减小问题的求解难度，改善规划系统的求解效率。
（3）提出一种Conformant规划下利用有利动作构造新型剪枝策略的方法，根据放松规划解的计算过程给出有利蕴含路径的概念，扩展信念状态时优先应用有利蕴含路径，对搜索空间的探索速度更快。
（4）提出Contingent规划下带有强制观察的剪枝策略，通过修改放松规划图的构造过程使得有利动作集合能够提取出观察当前不确定信息的动作，根据观察结果执行不同的求解动作，符合分支规划解的执行语义。
AI planning has been a main research field of Artificial Intelligence. In recent ten years,the research of AI planning has made a big breakthrough and obtained significantimprovement in both planning efficiency and quality of the plans. Heuristic search planninghas been a hot topic and one of the most powerful planning methods. The basic idea ofheuristic search framework is to guide the search procedure with some domain knowledge andmake the search direction going towards to the goal rapidly. The usage of heuristicinformation can mitigate the combination explosion of the search space effectively.
The main difficulty of heuristic search planning is the poor performance for problemswith complicated structure or big size. Researchers have introduced kinds of new searchalgorithms into the heuristic search planning framework, and it is still a huge challenge todesign an accurate and common heuristic function. Moreover, pruning is another importantstrategy to control the size of the search space.
This thesis mainly focuses on the search algorithm and pruning strategy, both of whichare crucial to performance of planning systems based on heuristic search. With theinformation provided by heuristic evaluation, the selected search algorithm determines theorder to explore the states in the search space. The difference of various search algorithms isthe tie-breaking rule in face of all the candidate states. Good decision can help to solve theplanning problem quickly and obtain a shorter solution, which would save the cost of thesearch procedure. Therefore, the rule of tie-breaking has a great influence on the behavior ofsearch algorithm. We proposed flexible heuristic search algorithms for classical andconformant planning tasks according to their structures, the main contributions include:
The idea of landmark-counting heuristic is to guide the search towards the states thatachieve more landmarks, which seems to be a segment heuristic of the search space. Weproposed a search algorithm that decomposes the planning task with the estimation of thelandmark-counting heuristic, where the original planning task is decomposed into severalsmaller sub-tasks implicitly. During the forward search, the decrease of thelandmark-counting heuristic value causes the task decomposition. Such sub-task procedure isrepeated until the estimation of the landmark-counting heuristic decreased to zero in the goalstate. The landmark-counting heuristic plays an assistant role in the whole search procedure,evaluating the computation that is necessary to reach the goal from each search state, whichmakes a better use of the landmark information. Experiment results on the representationalbenchmarks show the superiority of our algorithm. Compared to the multi-queue heuristicsearch and the task decomposition that treats the landmarks as mandatory intermediate subgoals, our planning algorithm based on the implicit task decomposition leads aconcentrated search direction, which could guide the forward search procedure towards thegoal faster and cut down the search space dramatically.
The planning system Conformant-FF translates conformant planning tasks into beliefspace search problems and adopts the enforced hill-climbing algorithm guided by the relaxedplan heuristic function. However, the helpful actions given by implications about theunknown propositions may make mistakes on domains that contain plenty of uncertaininformation, which makes Conformant-FF show bad performance on such domains. Withregard to this limitation, we propose a conformant planning algorithm that reduces thenondeterministic degree of belief states. The algorithm includes two phases of enforcedhill-climbing, which are used to reduce belief states and search for the goal respectively.Before searching for the given goal condition, the initial belief state is reduced furthest to anintermediate state which is much more deterministic. After that, the precision of heuristicevaluation is improved and the second normal enforced hill-climbing phase is executed fromthis intermediate state. We implement our idea based on Conformant-FF, design a planningsystem named CFF-Lite and experiment on a number of conformant benchmarks. The resultsshow that CFF-Lite can decrease the difficulty of conformant planning problems by reducingbelief states and our algorithm outperforms Conformant-FF in both planning efficiency andthe quality of plan.
Heuristic evaluation of the search states is one of the most time-consuming parts duringthe search procedure, thus the number of visited states affects the time efficiency directly.Pruning strategy controls the size of the search space when expanding the search states, whichcould decrease the states visited by the search algorithm. Excellent pruning strategy shouldkeep the states that are helpful to solve the problem faster and dump all the states that wouldget far away from the goal state or slow the search process down. Pruning is quite importantfor the performance of heuristic search algorithms. Heuristic function based on relaxed planprovides the helpful action pruning strategy, where the actions that may get closer to the goalare recognized as helpful. The helpful actions generate a set of promising successors to eachsearch state, bringing a compression of the search space. We propose to construct new pruningstrategies for conformant and contingent planning tasks on basis of helpful actions. Ourcontributions are as follows:
On analysis of the conformant relaxed plans, we get the “solving by cases” semantic ofthe implication paths for subgoals in the relaxed planning graph and introduce a furtherdefinition of helpful implication paths. We propose the novel pruning strategy of helpfulimplication paths for conformant planning tasks. A helpful implication path is usually madeup of several helpful actions. When expanding the belief states, executing all actions within ahelpful implication path can achieve some subgoal while executing an individual action cannot due to incomplete information. This strategy usually explores a much further range of thesearch space within one search iteration, and thus leads to the goal faster. We experiment on a number of conformant benchmarks to evaluate our idea. The results show that our pruningstrategy performs better than the old helpful action strategy for conformant planning tasks.The pruning strategy of helpful implication path can concentrate on the uncertainty of theestimated belief state when exploring the search space, reduce the number of visited states andbring an improvement of runtime efficiency.
To overcome the shortcoming that helpful actions under contingent planning fail to findbranching plans, a pruning strategy with enforced observations is presented. We change theway to treat the effects with unknown condition in the first level, making the uncertainty ofthe estimated belief state have opportunities to be observed. Then the adjusted relaxed plancan collect the observation actions that sense the truth value of the current unknownpropositions, and recognize them as helpful actions, which means to perform enforcedobservations to the uncertain information in the environment. The branching plan represents aconditional semantic that applies different actions according to the result of observation atruntime. With our revision, the unreasonable conformant actions can be excluded from the setof helpful actions and consequently we cut all the non-branching plans out of the solutionspace, which can improve the planning efficiency as well as the plan quality. Experimentresults on the representational contingent benchmarks have proven the superiority of ourpruning strategy in generating branching plans.
In conclusion, this thesis concerns the search algorithms and pruning strategies inheuristic search planning framework for classical planning and nondeterministic planning, thecontributions are significant for the improvement of planning efficiency and the plan quality.
引文
[1]姜云飞,杨强,凌应标等译.自动规划:理论和事件[M].北京:清华大学出版社,2008.Ghallab M, Nau D, Traverso P, Wrote; Jiang Y F, Yang Q, Ling Y B, et al, Trans.Automated planning: Theory and Practice, Beijing: Tsinghua University Press,2008(inChinese).
[2] Newell A, Simon H A. GPS: A Program that Simulate Human Thought[J]. Computers andThought, New York: McGraw-Hill,1963,279-293.
[3] Green C. Theorem Proving by Resolution as a Basis for Question-Answering Systems[J].Machine Intelligence4, Edinburgh: Edinburgh University Press,1981:183-205.
[4] Fikes R, Nilsson N. STRIPS: A New Approach to the Application of Theorem Proving toProblem Solving[J]. Artificial Intelligence,1971,2(3):189-203.
[5] Barrett A, Weld D. Partial Order Planning: Evaluating Possible Efficiency Gains[J].Artificial Intelligence,1994:67(1):71-112.
[6] Penberthy J S, Weld D. UCPOP: A Sound, Complete, Partial-Order Planner for ADL[C]. In:Nebel B, Rich C, Swartout W, eds., Proceedings of the3rdInternational Conference onKnowledge Representation and Reasoning,1992:103-114.
[7] Weld D. An Introduction to Least-Commitment Planning[J]. AI Magazine,1994,15(4):27-61.
[8] Nebel B. On the Computational Complexity of Temporal Projection, Planning and PlanValidation[J]. Artificial Intelligence,1994,66(1):125-160.
[9] Selman B. Near-Optimal Plans, Tractability, and Reactivity[C]. In: Doyle J, Sandewall E,Torasso P, eds., Proceedings of the4thInternational Conference on Principles of KnowledgeRepresentation and Reasoning,1994,521-529.
[10] Blum A, Furst M. Fast Planning through Planning Graph Analysis[J]. Artificial Intelligence,1997,90(1-2):281-300.
[11] International Planning Competition2000. http://www.cs.toronto.edu/aips2000/
[12] International Planning Competition2002. http://planning.cis.strath.ac.uk/competition/
[13] International Planning Competition2006. http://zeus.ing.unibs.it/ipc-5/
[14] International Planning Competition2008. http://ipc.informatik.uni-freiburg.de/
[15] International Planning Competition2011.http://www.plg.inf.uc3m.es/ipc2011-deterministic/.
[16] Kautz H, Selman B. Planning as Satisfiability[C]. In: Neumann B, ed., Proceedings of the10thEuropean Conference on Artificial Intelligence, Vienna: John Wiley&Sons,1992,359-363.
[17] Kautz H, McAllester D, Selman B. Encoding Plans in Propositional Logic[C]. In: Aiello L C,Doyle J, Shapiro S C, eds., Proceedings of the5thInternational Conference on Principles ofKnowledge Representation and Reasoning, Boston, Morgan Kaufmann,1996,374-384.
[18]吕帅,刘磊,石莲,李莹.基于自动推理技术的智能规划方法[J].软件学报,2009,20(5):1226-1240.
[19] Kautz H, Selman B. Unifying SAT-based and Graph-based Planning[C]. In: Dean T, ed.,Proceedings of the16thInternational Joint Conference on Artificial Intelligence, MorganKaufmann,1999,318-325.
[20] Kautz H, Selman B, Hoffmann J. SATPLAN: Planning as Satisfiability[R]. The5thInternational Planning Competition Booklet,2006.
[21] Russel S, Norvig P. Artificial Intelligence: A Modern Approach[M]. Englewood Cliffs:Prentice Hall,2003.
[22]刘凤岐.人工智能[M].机械工业出版社,2011.
[23] Korf R E. Depth-first Iterative-deepening: An Optimal Admissible Tree Search[J]. ArtificialIntelligence,1985,27(1):97-109.
[24] Bonet B, Geffner H. Planning as Heuristic Search[J]. Artificial Intelligence,2001,129(1-2):5-33.
[25] Hoffmann J, Nebel B. The FF Planning System: Fast Plan Generation through HeuristicSearch[J]. Journal of Artificial Intelligence Research,2001,14:253-302.
[26] Helmert M. A Planning Heuristic Based on Causal Graph Analysis[C]. In: Zilberstein S,Koehler J, Koenig S, eds., Proceedings of the16thInternational Conference on AutomatedPlanning and Scheduling,2004:161-170.
[27] Helmert M, Geffner H. Unifying the Causal Graph and Additive Heuristics[C]. In: RintanenJ, Nebel B, Beck J C, Hansen E A, eds., Proceedings of the18thInternational Conference onAutomated Planning and Scheduling,2008:140-147.
[28] Helmert M. The Fast Downward Planning System[J]. Journal of Artificial IntelligentResearch,2006,26:194-246.
[29] Chen Y X, Wah B W, Hsu C W. Temporal Planning Using Subgoal Partitioning andResolution in SGPlan[J]. Journal of Artificial Intelligence Research,2006,26:323-369.
[30] Richter S, Westphal M. The LAMA Planner: Guiding Cost-based Anytime Planning withLandmarks[J]. Journal of Artificial Intelligence Research,2010,39:127-177.
[31] Muscettola N, Nayak P, Pell B, Williams B. Remote Agent: To Boldly go Where No AISystem has Gone Before[J]. Artificial Intelligence,1998,103(1-2):5-47.
[32] Smith S J J, Nau D S, Throop T. Computer Bridge: A Big Win for AI Planning[J]. AImagazine,1998,19(2):93-105.
[33] Laborie P. Algorithms for Propagating Resource Constraints in AI Planning and Scheduling:Existing Approaches and New Results[J]. Artificial Intelligence,2003,143(2):151-188.
[34] Smith D E, Weld D. Conformant Graphplan[C]. In: Mostow J, Rich C, eds., Proceedings ofthe15thNational Conference on Artificial Intelligence and10thInnovative Applications ofArtificial Intelligence Conference, AAAI press,1998:889-893.
[35] Haslum P, Jonsson P. Some Results on the Complexity of Planning with IncompleteInformation[C]. In: Biundo S, Fox M, eds., Recent Advances in AI Planning, Proceedings ofthe5thEuropean Conference on Planning, Lecture Notes in Computer Science1809, Springer,2000,308-318.
[36] Palacios H, Geffner H. Compiling Uncertainty Away in Conformant Planning Problems withBounded Width. Journal of Artificial Intelligence,2009,35:623-675.
[37]杨宇鹏,欧阳丹彤,蔡敦波,吕帅.基于Conformant Fast-Forward规划系统的析取目标处理方法[J].计算机研究与发展,2008,45(12):2120-2128.
[38] Bonet B. Conformant Plans and Beyond: Principles and Complexity[J]. ArtificialIntelligence,2010,174(3-4):245-269.
[39] Rintanen J. Complexity of Planning with Partial Observability[C]. In: Zilberstein S, KoehlerJ, Koenig S, eds., Proceeding of the14thInternational Conference on Automated Planningand Scheduling,2004,345-354.
[40] Bertoli P, Cimatti A, Roveri M, Traverso P. Strong Planning under Partial Observability[J].Artificial Intelligence,2006,170(4-5):337-384.
[41] Rintanen J. Constructing Conditional Plans by a Theorem-Prover[J]. Journal of ArtificialIntelligence Research,1999,10:323-352.
[42] Herzig A, Lang J, Marquic P. Action Representation and Partially Observable PlanningUsing Epistemic Logic[C]. In: Gottlob G, Walsh T, eds.,Proceedings of the18thInternationalJoint Conference on Artificial Intelligence, Morgan Kaufmann,2003,1067-1072.
[43] Albore A, Palacios H, Geffner H. Fast and Informed Action Selection for Planning withSensing[C]. In: Borrajo D, Castillo L A, Corchado J M, eds., Proceedings of12thConferenceof the Spanish Association for Artificial Intelligence,2007,1-10.
[44] Pednault E. ADL: Exploring the Middle Ground between STRIPS and the SituationCalculus[C]. In: Brachman R J, Levesque H J, Reiter R, eds., Proceedings of the1stInternational Conference on Principles of Knowledge Representation and Reasoning,Morgan Kaufmann,1989,324-332.
[45] Malik G, Howe A E, Knoblock C A, et al. PDDL—the Planning Domain DefinitionLanguage[R]. Yale Center for Computational Vision and Control, Technique Report CVCTR-98-003/DCS TR-1165,1998.
[46] Maria F, Long D. PDDL2.1: An Extension to PDDL for Expressing Temporal PlanningDomains[J]. Journal of Artificial Intelligence Research,2003,20:61-124.
[47] Edelkamp S, Hoffmann J. PDDL2.2: The Language for the Classical Part of the4thInternational Planning Competition[R],2004.
[48] Gerevini A, Long D. Plan Constraints and Preferences in PDDL3: The Language of the5thInternational Planning Competition[R],2005.
[49] Gerevini A E, Haslum P, Long D, et al. Deterministic Planning in the5thInternational Planning Competition: PDDL3and Experimental Evaluation of the Planners[J].Artificial Intelligence,2009,173(5-6):619-668.
[50] Geffner H. Functional Strips: A More Flexible Language for Planning and ProblemSolving[J]. Logic-based Artificial Intelligence,2001,188-209.
[51] Helmert M. Concise Finite-Domain Representations for PDDL Planning Tasks[J]. ArtificialIntelligence,2009,173(5-6):503-535.
[52] Younes H, Littman M. PPDDL1.0: An Extension to PDDL for Expressing Planning Domainswith Probabilistic Effects[R]. School of Computer Science, Carnegie Mellon University,2004.
[53] Jensen R M, Veloso M M. OBDD-based Universal Planning for Synchronized Agents inNon-Deterministic Domains[J]. Journal of Artificial Intelligence Research,2000,13:189-226.
[54] Edelkamp S, Helmert M. MIPS: The Model-Checking Integrated Planning System[J]. AIMagazine,2001,22(3):67-71.
[55]吴康恒,姜云飞.基于模型检测的领域约束规划[J].软件学报,2004,15(11):1629-1640.
[56] Koehler J. Planning under Resource Constraint[C]. In: Prade H, ed., Proceedings of the13thEuropean Conference on Artificial Intelligence,1998,489-493..
[57]伍丽华,陈蔼洋,姜云飞.规划问题编码为约束可满足问题的研究[J].计算机科学,2006,33(8):187-189,292.
[58] Sacerdoti E D. A Structure for Plans and Behavior[M]. Amsterdam: Elsevier-North Holland,1977.
[59] Tate A. Generating Project Networks[C]. In: Reddy R, ed. Proceedings of the5thInternational Joint Conference on Artificial Intelligence,1977,2:888-893.
[60] Oommen B J, Rueda L G. A Formal Analysis of Why Heuristic Functions Work[J]. ArtificialIntelligence,2005,164(1-2):1-22.
[61] Baier J A, Bacchus F, Mcllraith S A. A Heuristic Search Approach to Planning withTemporally Extended Preferences[J]. Artificial Intelligence,2009,173(5-6):593-618.
[62] Hoffmann J. A Heuristic for Domain Independent Planning and its Use in an EnforcedHill-climbing Algorithm[C]. In: Proceedings of the12thInternational Symposium onFoundations of Intelligent Systems,2000,216-227.
[63] Korf R E. Linear-Space Best-first search[J]. Artificial Intelligence,1993,62(1):41-78.
[64] Nilsson N. Problem-Solving Methods in Artificial Intelligence[M]. McGraw-Hill,1971.
[65] Korf R E, Felner A. Disjoint Pattern Database Heuristics[J]. Artificial Intelligence,2002,134(1-2):9-22.
[66] Korf R E, Felner A. Recent Progress in Heuristic Search: A Case Study of the Four-PegTowers of Hanoi Problem[C]. In: Veloso M. M. ed., Proceedings of International JointConference of Artificial Intelligence,2007,2324-2329.
[67] Felner A, Korf R E, Meshulam R, Holte R. Compressed Pattern Databases[J]. Journal ofArtificial Intelligence Research,2007,30:213-247.
[68] Haslum P, Geffner H. Admissible Heuristics for Optimal Planning[C]. In: Chien S,Kambhampati S, Knoblock C A, eds., Proceedings of the5thInternational Conference onArtificial Intelligence Planning Systems, AAAI,2000,140-149.
[69] Helmert M, Haslum P, Hoffmann J. Flexible Abstraction Heuristics for Optimal SequentialPlanning[C]. In: Boddy M S, Fox M, Thiebaux S, eds., Proceedings of the17thInternational Conference on Automated Planning and Scheduling, AAAI press,2007,176-183.
[70] Haslum P, Botea A, Helmert M, Bonet B, Koenig S. Domain-independent Construction ofPattern Database Heuristics for Cost-optimal Planning[C]. In: Proceedings of the22ndAAAIConference on Artificial Intelligence, AAAI press,2007,1007-1012.
[71] Bonet B, Geffner H. Planning as Heuristic Search: New results[C]. In: Biundo S, Fox M,eds., Recent Advances in AI Planning, Proceedings of the5thEuropean Conference onPlanning, Springer,2000,360-372.
[72] Bonet B, Geffner H. Heuristic Search Planner2.0[J]. AI Magazine,2001,22(3):77-80.
[73] Hoffmann J. Where “Ignoring Delete Lists” Works: Local Search Topology in PlanningBenchmarks[J]. Journal of Artificial Intelligence Research,2005,24:685-758.
[74] Keyder E, Geffner H. The FF(ha) Planner for Planning with Action Costs[C]. AAAI,2008.
[75] Hoffmann J. Where Ignoring Delete Lists Works, Part2: Causal Graphs[C]. In: Bacchus F,Domshlak C, Edelkamp S, Helmert M, eds., Proceedings of the21thInternational Conferenceon Automated Planning and Scheduling,2011,98-105.
[76] Gu W X, Jin L L, Yin M H, Wang J S, Wang J Y. A Novel Causal Graph Based Heuristic forSolving Planning Problem[J]. Machine Learning and Cybernetics,2008,4:2223-2228.
[77] Hoffmann J. Analyzing Search Topology Without Running Any Search: On the ConnectionBetween Causal Graphs and h+[J]. Journal of Artificial Intelligence Research,2011,41:155-229.
[78] Porteous J, Cresswell S. Extending Landmarks Analysis to Reason about Resources andRepetition[C]. In: Proceedings of the21stWorkshop of the UK Planning and SchedulingSpecial Interest Group,2002,45-54.
[79] Richter S, Helmert M, Westphal M. Landmarks Revisited[C]. In: Fox D, Gomes C P, eds.,Proceedings of23rdAAAI Conference on Artificial Intelligence,2008,975-982.
[80] Long D, Fox M. Efficient Implementation of the Plan Graph in STAN[J]. Journal ofArtificial Intelligence Research,1999,10,87-115.
[81] Gerevini A, Saetti A, Serina I. Planning through Stochastic Local Search and TemporalAction Graphs in LPG[J]. Journal of Artificial Intelligence Research,2003,20:239-290.
[82]陈蔼祥,姜云飞,张学农,刘国英. GP——基于规划图的遗传规划算法[J].计算机学报,2007,30(1):153-160.
[83] Meuleau N, Benazera E, Brafman R I, et al. A Heuristic Search Approach to Planning withContinuous Resources in Stochastic Domains[J]. Journal of Artificial Intelligence Research,2009,34:27-59.
[84] Rosa T D, Jimenez S, Fuentetaja, et al. Scaling up Heuristic Planning with RelationalDecision Trees[J]. Journal of Artificial Intelligence Research,2011,40:767-813.
[85] Do M B, Kambhampati S. Planning Graph-based Heuristics for Cost-sensitive TemporalPlanning[C]. In: Ghallab, Hertzberg J, Traverso P, eds., Proceedings of the6thInternationalConference on Artificial Intelligence Planning Systems, AAAI,2002,3-12.
[86] Briel M, Kambhampati S. Optiplan: Unifying IP-based and Graph-based Planning[J]. Journalof Artificial Intelligence Research,2005,24:919-931.
[87] Bryce D, Cushing W, Kambhampati S. State Agnostic Planning Graphs: Deterministic,Non-deterministic, and Probabilistic Planning[J]. Artificial Intelligence,2011,175(3-4):848-889.
[88] Rulitko V, Lee G. Learning in Real-time Search: a Unifying Framework[J]. Journal ofArtificial Intelligence Research,2006,25:119-157.
[89] Rayner D C, Davison K, Bulitko V, et al. Real-time Heuristic Search with a PriorityQueue[C]. In: Veloso M. M, ed., Proceedings of the20thInternational Conference onArtificial Intelligence,2007:2372-2377.
[90] Koenig S, Likhachev M, Liu Y X, et al. Incremental Heuristic Search in ArtificialIntelligence[J]. AI Magazine,2004,25(2):99-112.
[91] Koenig S, Likhachev M, Furcy D. Lifelong Planning A*[J]. Artificial Intelligence,2004,155(1-2):93-146.
[92] Korf R E, Zhang W, Thayer I, et al. Frontier Search[J]. Journal of the ACM,2005,52(5):715-748.
[93] Richter S, Helmert M. Preferred Operators and Deferred Evaluation in SatisficingPlanning[C]. In: Gerevini A, Howe A E, Cesta A, Refanidis I, eds., Proceedings of the19thInternational Conference on Automated Planning and Scheduling, AAAI,2009,273-280.
[94] Hoffmann J, Brafman R. Conformant Planning via Heuristic Forward Search: A NewApproach[J]. Artificial Intelligence,2006,170(6):507-541.
[95] Hoffmann J, Brafman R, Contingent Planning via Heuristic Forward Search with ImplicitBelief States[C]. In: Biundo S, Myers K, Rajan K, eds., Proceedings of the15thInternationalConference on Automated Planning and Scheduling, AAAI,2005,71-80.
[96] Karpas E, Domshlak C. Cost-optimal Planning with Landmarks[C]. In: Boutilier C, ed.,Proceedings of the21stInternational Joint Conference on Artificial Intelligence,2009,1728-1733.
[97] Bonet B, Helmert M. Strengthening Landmark Heuristics via Hitting Sets[C]. In: Coelho H,Studer R, Wooldridge M, eds., Proceedings of19thEuropean Conference on ArtificialIntelligence, Frontiers in Artificial Intelligence and Applications215IOS Press,2010,329-334.
[98] Richter S, Westphal M, Helmert M. LAMA2008-2011[R]. The7thInternational PlanningCompetition, Description of Participant Planners of the Deterministic Track,IPC2011-booklet,50-54.
[99] Helmert M, Domshlak C. Landmarks, Critical Paths and Abstractions: What’s the DifferenceAnyway?[C] In: Gerevini A, Howe A, Cesta A, Refanidis I, eds., Proceedings of the19thInternational Conference on Automated Planning and Scheduling, AAAI,2009,162-169.
[100] Keyder E, Richter S, Helmert M. Sound and Complete Landmarks for And/Or Graphs[C]. In:Coelho H, Studer R, Wooldridge M, eds., Proceedings of the19thEuropean Conference onArtificial Intelligence, Frontiers in Artificial Intelligence and Applications215IOS Press,2010,335-340.
[101] Helmert M, Roger G, Seipp J, et al. Fast Downward Stone Soup[R]. The7thInternationalPlanning Competition, Description of Participant Planners of the Deterministic Track,IPC2011-booklet,38-45.
[102] Roger G, Helmert M. The More, the Merrier: Combining Heuristic Estimators for SatisficingPlanning[C]. In: Brafman R, Geffner H, Hoffmann J, Kautz H, ets., Proceedings of the20thInternational Conference on Automated Planning and Scheduling, AAAI,2010,246-249.
[103] Bacchus F, Kabanza F. Using Temporal Logic to Express Search Control Knowledge forPlanning[J]. Artificial Intelligence,2000,116(1-2):123-191.
[104]吴向军,姜云飞,凌应标.智能规划器StepByStep的研究与开发[J].软件学报,2008,19(9):2243-2264.
[105]吴向军,姜云飞,凌应标. STRIPS规划领域中动作效果关系的研究[J].软件学报,2007,18(6):1328-1349.
[106] Huang Y C, Selman B, Kautz H. Learning Declarative Control Rules for Constraint-BasedPlanning[C]. In: Langley P, ed., Proceedings of the17thInternational Conference on MachineLearning, Morgan Kaufmann,2000:415-422.
[107] Yoon S W, Fern A, Givan R. Learning Heuristic Functions from Relaxed Plans[C]. In: LongD, Smith S F, Borrajo D, McCluskey L, eds., Proceedings of the16thInternationalConference on Automated Planning and Scheduling, AAAI,2006,162-171.
[108] Porteous J, Sebastia L, Hoffmann J. On the Extraction, Ordering, and Usage of Landmarks inPlanning[C]. In: Cesta A, Borrajo D, eds., Proceedings of6thEuropean Conference onPlanning,2001,37-48.
[109] Hoffmann J, Porteous J, Sebastia L. Ordered Landmarks in Planning[J]. Journal of ArtificialIntelligence Research,2004,22:215-278.
[110] Sebastia L, Onaindia E, Marzal E. Decomposition of Planning Problems[J]. AIcommunications,2006,19(1):49-81.
[111] Keyder E, Geffner H. Heuristics for Planning with Action Costs[C]. In: Borrajo D, Castillo LA, Corchado J M, eds., Current Topics in Artificial Intelligence, Proceedings of the12thConference of the Spanish Association for Artificial Intelligence, Springer,2007,140-149.
[112] Hansen E A, Zhou R. Anytime Heuristic Search[J]. Journal of Artificial IntelligenceResearch,2007,28:267-297.
[113] Richter S, Thayer J T, Ruml W. The Joy of Forgetting: Faster Anytime Search viaRestarting[C]. In: Brafman R, Geffner H, Hoffmann J, Kautz H, eds., Proceedings of the20thInternational Conference on Automated Planning and Scheduling, AAAI,2010,137-144.
[114] Pohl I. Heuristic Search Viewed as Path Finding in a Graph[J]. Artificial Intelligence,1970,1(3):193-204.
[115]魏唯,欧阳丹彤,吕帅,冯宇轩.动态不确定环境下多目标路径规划方法[J].计算机学报,2011,34(5):836-846.
[116]魏唯,欧阳丹彤,吕帅,殷明浩.结合增量与启发式搜索的多目标问题处理方法[J].计算机研究与发展,2010,47(11):1954-1961.
[117] Bertoli P, Cimatti A. Improving Heuristics for Planning as Search in Belief Space[C]. In:Ghallab M, Hertzberg J, Traverso P, eds., Proceedings of the6thInternational Conference onArtificial Intelligence Planning Systems, AAAI,2002,143-152.
[118] Bryce D, Kambhampati S, Smith D E. Planning Graph Heuristics for Belief Space Search[J].Journal of Artificial Intelligence Research,2006,22:1-62.
[119] Bonet B, Geffner H. Planning with Incomplete Information as Heuristic Search in BeliefSpace[C]. In: Chien S, Kambhampati S, Knoblock C A, eds., Proceedings of the5thInternational Conference on Artificial Intelligence Planning Systems, AAAI,2000,52-61.
[120] Cimatti A, Roveri M. Conformant Planning via Symbolic Model Checking[J]. Journal ofArtificial Intelligence Research,2000,13:305-338.
[121] Cimatti A, Roveri M, Bertoli P. Conformant Planning via Symbolic Model Checking andHeuristic Search[J]. Artificial Intelligence,2004,159(1-2):127-206.
[122] Jensen R M, Veloso M M, Bryant R E. State-set Branching: Leveraging BDDs for HeuristicSearch[J]. Artificial Intelligence,2008:172(2-3):103-139.
[123]周俊萍,殷明浩,谷文祥,孙吉贵.部分可观察强规划中约减观察变量的研究[J].软件学报,2009,20(2):290-304.
[124] Bertoli P, Cimatti A, Traverso P. Interleaving Execution and Planning for Nondeterministic,Partially Observable Domains[C]. In: Mantaras R L de, Saitta L, eds., Proceedings of the16thEuropean Conference on Artificial Intelligence, IOS press,2004,657-661.
[125] Brenner M, Nebel B. Continual Planning and Acting in Dynamic MultiagentEnvironments[J]. Autonomous Agent and Multi-Agent System,2009,19(3):297-331.
[2] Newell A, Simon H A. GPS: A Program that Simulate Human Thought[J]. Computers andThought, New York: McGraw-Hill,1963,279-293.
[3] Green C. Theorem Proving by Resolution as a Basis for Question-Answering Systems[J].Machine Intelligence4, Edinburgh: Edinburgh University Press,1981:183-205.
[4] Fikes R, Nilsson N. STRIPS: A New Approach to the Application of Theorem Proving toProblem Solving[J]. Artificial Intelligence,1971,2(3):189-203.
[5] Barrett A, Weld D. Partial Order Planning: Evaluating Possible Efficiency Gains[J].Artificial Intelligence,1994:67(1):71-112.
[6] Penberthy J S, Weld D. UCPOP: A Sound, Complete, Partial-Order Planner for ADL[C]. In:Nebel B, Rich C, Swartout W, eds., Proceedings of the3rdInternational Conference onKnowledge Representation and Reasoning,1992:103-114.
[7] Weld D. An Introduction to Least-Commitment Planning[J]. AI Magazine,1994,15(4):27-61.
[8] Nebel B. On the Computational Complexity of Temporal Projection, Planning and PlanValidation[J]. Artificial Intelligence,1994,66(1):125-160.
[9] Selman B. Near-Optimal Plans, Tractability, and Reactivity[C]. In: Doyle J, Sandewall E,Torasso P, eds., Proceedings of the4thInternational Conference on Principles of KnowledgeRepresentation and Reasoning,1994,521-529.
[10] Blum A, Furst M. Fast Planning through Planning Graph Analysis[J]. Artificial Intelligence,1997,90(1-2):281-300.
[11] International Planning Competition2000. http://www.cs.toronto.edu/aips2000/
[12] International Planning Competition2002. http://planning.cis.strath.ac.uk/competition/
[13] International Planning Competition2006. http://zeus.ing.unibs.it/ipc-5/
[14] International Planning Competition2008. http://ipc.informatik.uni-freiburg.de/
[15] International Planning Competition2011.http://www.plg.inf.uc3m.es/ipc2011-deterministic/.
[16] Kautz H, Selman B. Planning as Satisfiability[C]. In: Neumann B, ed., Proceedings of the10thEuropean Conference on Artificial Intelligence, Vienna: John Wiley&Sons,1992,359-363.
[17] Kautz H, McAllester D, Selman B. Encoding Plans in Propositional Logic[C]. In: Aiello L C,Doyle J, Shapiro S C, eds., Proceedings of the5thInternational Conference on Principles ofKnowledge Representation and Reasoning, Boston, Morgan Kaufmann,1996,374-384.
[18]吕帅,刘磊,石莲,李莹.基于自动推理技术的智能规划方法[J].软件学报,2009,20(5):1226-1240.
[19] Kautz H, Selman B. Unifying SAT-based and Graph-based Planning[C]. In: Dean T, ed.,Proceedings of the16thInternational Joint Conference on Artificial Intelligence, MorganKaufmann,1999,318-325.
[20] Kautz H, Selman B, Hoffmann J. SATPLAN: Planning as Satisfiability[R]. The5thInternational Planning Competition Booklet,2006.
[21] Russel S, Norvig P. Artificial Intelligence: A Modern Approach[M]. Englewood Cliffs:Prentice Hall,2003.
[22]刘凤岐.人工智能[M].机械工业出版社,2011.
[23] Korf R E. Depth-first Iterative-deepening: An Optimal Admissible Tree Search[J]. ArtificialIntelligence,1985,27(1):97-109.
[24] Bonet B, Geffner H. Planning as Heuristic Search[J]. Artificial Intelligence,2001,129(1-2):5-33.
[25] Hoffmann J, Nebel B. The FF Planning System: Fast Plan Generation through HeuristicSearch[J]. Journal of Artificial Intelligence Research,2001,14:253-302.
[26] Helmert M. A Planning Heuristic Based on Causal Graph Analysis[C]. In: Zilberstein S,Koehler J, Koenig S, eds., Proceedings of the16thInternational Conference on AutomatedPlanning and Scheduling,2004:161-170.
[27] Helmert M, Geffner H. Unifying the Causal Graph and Additive Heuristics[C]. In: RintanenJ, Nebel B, Beck J C, Hansen E A, eds., Proceedings of the18thInternational Conference onAutomated Planning and Scheduling,2008:140-147.
[28] Helmert M. The Fast Downward Planning System[J]. Journal of Artificial IntelligentResearch,2006,26:194-246.
[29] Chen Y X, Wah B W, Hsu C W. Temporal Planning Using Subgoal Partitioning andResolution in SGPlan[J]. Journal of Artificial Intelligence Research,2006,26:323-369.
[30] Richter S, Westphal M. The LAMA Planner: Guiding Cost-based Anytime Planning withLandmarks[J]. Journal of Artificial Intelligence Research,2010,39:127-177.
[31] Muscettola N, Nayak P, Pell B, Williams B. Remote Agent: To Boldly go Where No AISystem has Gone Before[J]. Artificial Intelligence,1998,103(1-2):5-47.
[32] Smith S J J, Nau D S, Throop T. Computer Bridge: A Big Win for AI Planning[J]. AImagazine,1998,19(2):93-105.
[33] Laborie P. Algorithms for Propagating Resource Constraints in AI Planning and Scheduling:Existing Approaches and New Results[J]. Artificial Intelligence,2003,143(2):151-188.
[34] Smith D E, Weld D. Conformant Graphplan[C]. In: Mostow J, Rich C, eds., Proceedings ofthe15thNational Conference on Artificial Intelligence and10thInnovative Applications ofArtificial Intelligence Conference, AAAI press,1998:889-893.
[35] Haslum P, Jonsson P. Some Results on the Complexity of Planning with IncompleteInformation[C]. In: Biundo S, Fox M, eds., Recent Advances in AI Planning, Proceedings ofthe5thEuropean Conference on Planning, Lecture Notes in Computer Science1809, Springer,2000,308-318.
[36] Palacios H, Geffner H. Compiling Uncertainty Away in Conformant Planning Problems withBounded Width. Journal of Artificial Intelligence,2009,35:623-675.
[37]杨宇鹏,欧阳丹彤,蔡敦波,吕帅.基于Conformant Fast-Forward规划系统的析取目标处理方法[J].计算机研究与发展,2008,45(12):2120-2128.
[38] Bonet B. Conformant Plans and Beyond: Principles and Complexity[J]. ArtificialIntelligence,2010,174(3-4):245-269.
[39] Rintanen J. Complexity of Planning with Partial Observability[C]. In: Zilberstein S, KoehlerJ, Koenig S, eds., Proceeding of the14thInternational Conference on Automated Planningand Scheduling,2004,345-354.
[40] Bertoli P, Cimatti A, Roveri M, Traverso P. Strong Planning under Partial Observability[J].Artificial Intelligence,2006,170(4-5):337-384.
[41] Rintanen J. Constructing Conditional Plans by a Theorem-Prover[J]. Journal of ArtificialIntelligence Research,1999,10:323-352.
[42] Herzig A, Lang J, Marquic P. Action Representation and Partially Observable PlanningUsing Epistemic Logic[C]. In: Gottlob G, Walsh T, eds.,Proceedings of the18thInternationalJoint Conference on Artificial Intelligence, Morgan Kaufmann,2003,1067-1072.
[43] Albore A, Palacios H, Geffner H. Fast and Informed Action Selection for Planning withSensing[C]. In: Borrajo D, Castillo L A, Corchado J M, eds., Proceedings of12thConferenceof the Spanish Association for Artificial Intelligence,2007,1-10.
[44] Pednault E. ADL: Exploring the Middle Ground between STRIPS and the SituationCalculus[C]. In: Brachman R J, Levesque H J, Reiter R, eds., Proceedings of the1stInternational Conference on Principles of Knowledge Representation and Reasoning,Morgan Kaufmann,1989,324-332.
[45] Malik G, Howe A E, Knoblock C A, et al. PDDL—the Planning Domain DefinitionLanguage[R]. Yale Center for Computational Vision and Control, Technique Report CVCTR-98-003/DCS TR-1165,1998.
[46] Maria F, Long D. PDDL2.1: An Extension to PDDL for Expressing Temporal PlanningDomains[J]. Journal of Artificial Intelligence Research,2003,20:61-124.
[47] Edelkamp S, Hoffmann J. PDDL2.2: The Language for the Classical Part of the4thInternational Planning Competition[R],2004.
[48] Gerevini A, Long D. Plan Constraints and Preferences in PDDL3: The Language of the5thInternational Planning Competition[R],2005.
[49] Gerevini A E, Haslum P, Long D, et al. Deterministic Planning in the5thInternational Planning Competition: PDDL3and Experimental Evaluation of the Planners[J].Artificial Intelligence,2009,173(5-6):619-668.
[50] Geffner H. Functional Strips: A More Flexible Language for Planning and ProblemSolving[J]. Logic-based Artificial Intelligence,2001,188-209.
[51] Helmert M. Concise Finite-Domain Representations for PDDL Planning Tasks[J]. ArtificialIntelligence,2009,173(5-6):503-535.
[52] Younes H, Littman M. PPDDL1.0: An Extension to PDDL for Expressing Planning Domainswith Probabilistic Effects[R]. School of Computer Science, Carnegie Mellon University,2004.
[53] Jensen R M, Veloso M M. OBDD-based Universal Planning for Synchronized Agents inNon-Deterministic Domains[J]. Journal of Artificial Intelligence Research,2000,13:189-226.
[54] Edelkamp S, Helmert M. MIPS: The Model-Checking Integrated Planning System[J]. AIMagazine,2001,22(3):67-71.
[55]吴康恒,姜云飞.基于模型检测的领域约束规划[J].软件学报,2004,15(11):1629-1640.
[56] Koehler J. Planning under Resource Constraint[C]. In: Prade H, ed., Proceedings of the13thEuropean Conference on Artificial Intelligence,1998,489-493..
[57]伍丽华,陈蔼洋,姜云飞.规划问题编码为约束可满足问题的研究[J].计算机科学,2006,33(8):187-189,292.
[58] Sacerdoti E D. A Structure for Plans and Behavior[M]. Amsterdam: Elsevier-North Holland,1977.
[59] Tate A. Generating Project Networks[C]. In: Reddy R, ed. Proceedings of the5thInternational Joint Conference on Artificial Intelligence,1977,2:888-893.
[60] Oommen B J, Rueda L G. A Formal Analysis of Why Heuristic Functions Work[J]. ArtificialIntelligence,2005,164(1-2):1-22.
[61] Baier J A, Bacchus F, Mcllraith S A. A Heuristic Search Approach to Planning withTemporally Extended Preferences[J]. Artificial Intelligence,2009,173(5-6):593-618.
[62] Hoffmann J. A Heuristic for Domain Independent Planning and its Use in an EnforcedHill-climbing Algorithm[C]. In: Proceedings of the12thInternational Symposium onFoundations of Intelligent Systems,2000,216-227.
[63] Korf R E. Linear-Space Best-first search[J]. Artificial Intelligence,1993,62(1):41-78.
[64] Nilsson N. Problem-Solving Methods in Artificial Intelligence[M]. McGraw-Hill,1971.
[65] Korf R E, Felner A. Disjoint Pattern Database Heuristics[J]. Artificial Intelligence,2002,134(1-2):9-22.
[66] Korf R E, Felner A. Recent Progress in Heuristic Search: A Case Study of the Four-PegTowers of Hanoi Problem[C]. In: Veloso M. M. ed., Proceedings of International JointConference of Artificial Intelligence,2007,2324-2329.
[67] Felner A, Korf R E, Meshulam R, Holte R. Compressed Pattern Databases[J]. Journal ofArtificial Intelligence Research,2007,30:213-247.
[68] Haslum P, Geffner H. Admissible Heuristics for Optimal Planning[C]. In: Chien S,Kambhampati S, Knoblock C A, eds., Proceedings of the5thInternational Conference onArtificial Intelligence Planning Systems, AAAI,2000,140-149.
[69] Helmert M, Haslum P, Hoffmann J. Flexible Abstraction Heuristics for Optimal SequentialPlanning[C]. In: Boddy M S, Fox M, Thiebaux S, eds., Proceedings of the17thInternational Conference on Automated Planning and Scheduling, AAAI press,2007,176-183.
[70] Haslum P, Botea A, Helmert M, Bonet B, Koenig S. Domain-independent Construction ofPattern Database Heuristics for Cost-optimal Planning[C]. In: Proceedings of the22ndAAAIConference on Artificial Intelligence, AAAI press,2007,1007-1012.
[71] Bonet B, Geffner H. Planning as Heuristic Search: New results[C]. In: Biundo S, Fox M,eds., Recent Advances in AI Planning, Proceedings of the5thEuropean Conference onPlanning, Springer,2000,360-372.
[72] Bonet B, Geffner H. Heuristic Search Planner2.0[J]. AI Magazine,2001,22(3):77-80.
[73] Hoffmann J. Where “Ignoring Delete Lists” Works: Local Search Topology in PlanningBenchmarks[J]. Journal of Artificial Intelligence Research,2005,24:685-758.
[74] Keyder E, Geffner H. The FF(ha) Planner for Planning with Action Costs[C]. AAAI,2008.
[75] Hoffmann J. Where Ignoring Delete Lists Works, Part2: Causal Graphs[C]. In: Bacchus F,Domshlak C, Edelkamp S, Helmert M, eds., Proceedings of the21thInternational Conferenceon Automated Planning and Scheduling,2011,98-105.
[76] Gu W X, Jin L L, Yin M H, Wang J S, Wang J Y. A Novel Causal Graph Based Heuristic forSolving Planning Problem[J]. Machine Learning and Cybernetics,2008,4:2223-2228.
[77] Hoffmann J. Analyzing Search Topology Without Running Any Search: On the ConnectionBetween Causal Graphs and h+[J]. Journal of Artificial Intelligence Research,2011,41:155-229.
[78] Porteous J, Cresswell S. Extending Landmarks Analysis to Reason about Resources andRepetition[C]. In: Proceedings of the21stWorkshop of the UK Planning and SchedulingSpecial Interest Group,2002,45-54.
[79] Richter S, Helmert M, Westphal M. Landmarks Revisited[C]. In: Fox D, Gomes C P, eds.,Proceedings of23rdAAAI Conference on Artificial Intelligence,2008,975-982.
[80] Long D, Fox M. Efficient Implementation of the Plan Graph in STAN[J]. Journal ofArtificial Intelligence Research,1999,10,87-115.
[81] Gerevini A, Saetti A, Serina I. Planning through Stochastic Local Search and TemporalAction Graphs in LPG[J]. Journal of Artificial Intelligence Research,2003,20:239-290.
[82]陈蔼祥,姜云飞,张学农,刘国英. GP——基于规划图的遗传规划算法[J].计算机学报,2007,30(1):153-160.
[83] Meuleau N, Benazera E, Brafman R I, et al. A Heuristic Search Approach to Planning withContinuous Resources in Stochastic Domains[J]. Journal of Artificial Intelligence Research,2009,34:27-59.
[84] Rosa T D, Jimenez S, Fuentetaja, et al. Scaling up Heuristic Planning with RelationalDecision Trees[J]. Journal of Artificial Intelligence Research,2011,40:767-813.
[85] Do M B, Kambhampati S. Planning Graph-based Heuristics for Cost-sensitive TemporalPlanning[C]. In: Ghallab, Hertzberg J, Traverso P, eds., Proceedings of the6thInternationalConference on Artificial Intelligence Planning Systems, AAAI,2002,3-12.
[86] Briel M, Kambhampati S. Optiplan: Unifying IP-based and Graph-based Planning[J]. Journalof Artificial Intelligence Research,2005,24:919-931.
[87] Bryce D, Cushing W, Kambhampati S. State Agnostic Planning Graphs: Deterministic,Non-deterministic, and Probabilistic Planning[J]. Artificial Intelligence,2011,175(3-4):848-889.
[88] Rulitko V, Lee G. Learning in Real-time Search: a Unifying Framework[J]. Journal ofArtificial Intelligence Research,2006,25:119-157.
[89] Rayner D C, Davison K, Bulitko V, et al. Real-time Heuristic Search with a PriorityQueue[C]. In: Veloso M. M, ed., Proceedings of the20thInternational Conference onArtificial Intelligence,2007:2372-2377.
[90] Koenig S, Likhachev M, Liu Y X, et al. Incremental Heuristic Search in ArtificialIntelligence[J]. AI Magazine,2004,25(2):99-112.
[91] Koenig S, Likhachev M, Furcy D. Lifelong Planning A*[J]. Artificial Intelligence,2004,155(1-2):93-146.
[92] Korf R E, Zhang W, Thayer I, et al. Frontier Search[J]. Journal of the ACM,2005,52(5):715-748.
[93] Richter S, Helmert M. Preferred Operators and Deferred Evaluation in SatisficingPlanning[C]. In: Gerevini A, Howe A E, Cesta A, Refanidis I, eds., Proceedings of the19thInternational Conference on Automated Planning and Scheduling, AAAI,2009,273-280.
[94] Hoffmann J, Brafman R. Conformant Planning via Heuristic Forward Search: A NewApproach[J]. Artificial Intelligence,2006,170(6):507-541.
[95] Hoffmann J, Brafman R, Contingent Planning via Heuristic Forward Search with ImplicitBelief States[C]. In: Biundo S, Myers K, Rajan K, eds., Proceedings of the15thInternationalConference on Automated Planning and Scheduling, AAAI,2005,71-80.
[96] Karpas E, Domshlak C. Cost-optimal Planning with Landmarks[C]. In: Boutilier C, ed.,Proceedings of the21stInternational Joint Conference on Artificial Intelligence,2009,1728-1733.
[97] Bonet B, Helmert M. Strengthening Landmark Heuristics via Hitting Sets[C]. In: Coelho H,Studer R, Wooldridge M, eds., Proceedings of19thEuropean Conference on ArtificialIntelligence, Frontiers in Artificial Intelligence and Applications215IOS Press,2010,329-334.
[98] Richter S, Westphal M, Helmert M. LAMA2008-2011[R]. The7thInternational PlanningCompetition, Description of Participant Planners of the Deterministic Track,IPC2011-booklet,50-54.
[99] Helmert M, Domshlak C. Landmarks, Critical Paths and Abstractions: What’s the DifferenceAnyway?[C] In: Gerevini A, Howe A, Cesta A, Refanidis I, eds., Proceedings of the19thInternational Conference on Automated Planning and Scheduling, AAAI,2009,162-169.
[100] Keyder E, Richter S, Helmert M. Sound and Complete Landmarks for And/Or Graphs[C]. In:Coelho H, Studer R, Wooldridge M, eds., Proceedings of the19thEuropean Conference onArtificial Intelligence, Frontiers in Artificial Intelligence and Applications215IOS Press,2010,335-340.
[101] Helmert M, Roger G, Seipp J, et al. Fast Downward Stone Soup[R]. The7thInternationalPlanning Competition, Description of Participant Planners of the Deterministic Track,IPC2011-booklet,38-45.
[102] Roger G, Helmert M. The More, the Merrier: Combining Heuristic Estimators for SatisficingPlanning[C]. In: Brafman R, Geffner H, Hoffmann J, Kautz H, ets., Proceedings of the20thInternational Conference on Automated Planning and Scheduling, AAAI,2010,246-249.
[103] Bacchus F, Kabanza F. Using Temporal Logic to Express Search Control Knowledge forPlanning[J]. Artificial Intelligence,2000,116(1-2):123-191.
[104]吴向军,姜云飞,凌应标.智能规划器StepByStep的研究与开发[J].软件学报,2008,19(9):2243-2264.
[105]吴向军,姜云飞,凌应标. STRIPS规划领域中动作效果关系的研究[J].软件学报,2007,18(6):1328-1349.
[106] Huang Y C, Selman B, Kautz H. Learning Declarative Control Rules for Constraint-BasedPlanning[C]. In: Langley P, ed., Proceedings of the17thInternational Conference on MachineLearning, Morgan Kaufmann,2000:415-422.
[107] Yoon S W, Fern A, Givan R. Learning Heuristic Functions from Relaxed Plans[C]. In: LongD, Smith S F, Borrajo D, McCluskey L, eds., Proceedings of the16thInternationalConference on Automated Planning and Scheduling, AAAI,2006,162-171.
[108] Porteous J, Sebastia L, Hoffmann J. On the Extraction, Ordering, and Usage of Landmarks inPlanning[C]. In: Cesta A, Borrajo D, eds., Proceedings of6thEuropean Conference onPlanning,2001,37-48.
[109] Hoffmann J, Porteous J, Sebastia L. Ordered Landmarks in Planning[J]. Journal of ArtificialIntelligence Research,2004,22:215-278.
[110] Sebastia L, Onaindia E, Marzal E. Decomposition of Planning Problems[J]. AIcommunications,2006,19(1):49-81.
[111] Keyder E, Geffner H. Heuristics for Planning with Action Costs[C]. In: Borrajo D, Castillo LA, Corchado J M, eds., Current Topics in Artificial Intelligence, Proceedings of the12thConference of the Spanish Association for Artificial Intelligence, Springer,2007,140-149.
[112] Hansen E A, Zhou R. Anytime Heuristic Search[J]. Journal of Artificial IntelligenceResearch,2007,28:267-297.
[113] Richter S, Thayer J T, Ruml W. The Joy of Forgetting: Faster Anytime Search viaRestarting[C]. In: Brafman R, Geffner H, Hoffmann J, Kautz H, eds., Proceedings of the20thInternational Conference on Automated Planning and Scheduling, AAAI,2010,137-144.
[114] Pohl I. Heuristic Search Viewed as Path Finding in a Graph[J]. Artificial Intelligence,1970,1(3):193-204.
[115]魏唯,欧阳丹彤,吕帅,冯宇轩.动态不确定环境下多目标路径规划方法[J].计算机学报,2011,34(5):836-846.
[116]魏唯,欧阳丹彤,吕帅,殷明浩.结合增量与启发式搜索的多目标问题处理方法[J].计算机研究与发展,2010,47(11):1954-1961.
[117] Bertoli P, Cimatti A. Improving Heuristics for Planning as Search in Belief Space[C]. In:Ghallab M, Hertzberg J, Traverso P, eds., Proceedings of the6thInternational Conference onArtificial Intelligence Planning Systems, AAAI,2002,143-152.
[118] Bryce D, Kambhampati S, Smith D E. Planning Graph Heuristics for Belief Space Search[J].Journal of Artificial Intelligence Research,2006,22:1-62.
[119] Bonet B, Geffner H. Planning with Incomplete Information as Heuristic Search in BeliefSpace[C]. In: Chien S, Kambhampati S, Knoblock C A, eds., Proceedings of the5thInternational Conference on Artificial Intelligence Planning Systems, AAAI,2000,52-61.
[120] Cimatti A, Roveri M. Conformant Planning via Symbolic Model Checking[J]. Journal ofArtificial Intelligence Research,2000,13:305-338.
[121] Cimatti A, Roveri M, Bertoli P. Conformant Planning via Symbolic Model Checking andHeuristic Search[J]. Artificial Intelligence,2004,159(1-2):127-206.
[122] Jensen R M, Veloso M M, Bryant R E. State-set Branching: Leveraging BDDs for HeuristicSearch[J]. Artificial Intelligence,2008:172(2-3):103-139.
[123]周俊萍,殷明浩,谷文祥,孙吉贵.部分可观察强规划中约减观察变量的研究[J].软件学报,2009,20(2):290-304.
[124] Bertoli P, Cimatti A, Traverso P. Interleaving Execution and Planning for Nondeterministic,Partially Observable Domains[C]. In: Mantaras R L de, Saitta L, eds., Proceedings of the16thEuropean Conference on Artificial Intelligence, IOS press,2004,657-661.
[125] Brenner M, Nebel B. Continual Planning and Acting in Dynamic MultiagentEnvironments[J]. Autonomous Agent and Multi-Agent System,2009,19(3):297-331.