An LP-based heuristic for optimal planning

被引：0
|
作者：
van den Briel, Menkes [1 ]
Benton, J. [2 ]
Kambhampati, Subbarao [2 ]
Vossen, Thomas [3 ]
机构：
[1] Arizona State Univ, Dept Ind Engn, Tempe, AZ 85287 USA
[2] Dept Comp Sci & Engn, Tempe, AZ 85287 USA
[3] Univ Colorado, Leeds Sch Business, Boulder, CO 80309 USA
来源：
PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2007 | 2007年 / 4741卷
关键词：
automated planning; improving admissible heuristics; optimal relaxed planning;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
One of the most successful approaches in automated planning is to use heuristic state-space search. A popular heuristic that is used by a number of state-space planners is based on relaxing the planning task by ignoring the delete effects of the actions. In several planning domains, however, this relaxation produces rather weak estimates to guide search effectively. We present a relaxation using (integer) linear programming that respects delete effects but ignores action ordering, which in a number of problems provides better distance estimates. Moreover, our approach can be used as an admissible heuristic for optimal planning.
引用
收藏
页码：651 / +
页数：3
相关论文
共 50 条
  • [11] An LP-based heuristic for two-stage capacitated facility location problems
    Klose, A
    JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1999, 50 (02) : 157 - 166
  • [12] An LP-based heuristic procedure for the generalized assignment problem with special ordered sets
    French, Alan P.
    Wilson, John M.
    COMPUTERS & OPERATIONS RESEARCH, 2007, 34 (08) : 2359 - 2369
  • [13] An LP-based heuristic algorithm for the node capacitated in-tree packing problem
    Tanaka, Yuma
    Imahori, Shinji
    Sasaki, Mihiro
    Yagiura, Mutsunori
    COMPUTERS & OPERATIONS RESEARCH, 2012, 39 (03) : 637 - 646
  • [14] Solving the biobjective zero-one knapsack problem by an efficient LP-based heuristic
    Zhang, CW
    Ong, HL
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2004, 159 (03) : 545 - 557
  • [15] LP-based path planning method in acceleration space for mobile robot
    Robotics Laboratory, Shenyang Institute of Automation, Chinese Acad. of Sci., Shenyang 110016, China
    不详
    Zidonghua Xuebao, 2007, 10 (1036-1042):
  • [16] LP-Based Heuristic Algorithms for Interconnecting Token Rings via Source Routing Bridges
    V. Sridhar
    June S. Park
    Bezalel Gavish
    Journal of Heuristics, 2000, 6 : 149 - 166
  • [17] An LP-based hybrid heuristic procedure for the generalized assignment problem with special ordered sets
    French, AP
    Wilson, JM
    HYBRID METAHEURISTICS, PROCEEDINGS, 2005, 3636 : 12 - 20
  • [18] Transmission expansion planning using LP-based particle swarm optimization
    Kavitha, D.
    Swarup, K. Shanti
    2006 IEEE POWER INDIA CONFERENCE, VOLS 1 AND 2, 2006, : 143 - +
  • [19] Using Valid Inequalities and Different Grids in LP-Based Heuristic for Packing Circular Objects
    Litvinchev, Igor
    Infante, Luis
    Ozuna Espinosa, Edith Lucero
    INTELLIGENT INFORMATION AND DATABASE SYSTEMS, ACIIDS 2016, PT II, 2016, 9622 : 681 - 690
  • [20] LP-based heuristic algorithms for interconnecting token rings via source routing bridges
    Sridhar, V
    Park, JS
    Gavish, B
    JOURNAL OF HEURISTICS, 2000, 6 (01) : 149 - 166
12345