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 条
  • [1] Cost Optimal Planning with LP-Based Multi-valued Landmark Heuristic
    Zhang, Lei
    Wang, Chong-Jun
    Xie, Jun-Yuan
    AAMAS'14: PROCEEDINGS OF THE 2014 INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS & MULTIAGENT SYSTEMS, 2014, : 509 - 516
  • [2] LP-Based Heuristics for Cost-Optimal Planning
    Pommerening, Florian
    Roger, Gabriele
    Helmert, Malte
    Bonet, Blai
    TWENTY-FOURTH INTERNATIONAL CONFERENCE ON AUTOMATED PLANNING AND SCHEDULING, 2014, : 226 - 234
  • [3] LP-based optimal path planning in acceleration space
    Zu, Di
    Han, Handa
    Tan, Dalong
    2006 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND BIOMIMETICS, VOLS 1-3, 2006, : 1340 - +
  • [4] An LP-Based Approach for Goal Recognition as Planning
    Santos, Luisa R. de A.
    Meneguzzi, Felipe
    Pereira, Ramon Fraga
    Pereira, Andre Grahl
    THIRTY-FIFTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, THIRTY-THIRD CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE AND THE ELEVENTH SYMPOSIUM ON EDUCATIONAL ADVANCES IN ARTIFICIAL INTELLIGENCE, 2021, 35 : 11939 - 11946
  • [5] A LP-based heuristic for a time-constrained routing problem
    Avella, P
    D'Auria, B
    Salerno, S
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2006, 173 (01) : 120 - 124
  • [6] An efficient LP-based admissible heuristic for cost-based abduction
    Abdelbar, AM
    Hefny, M
    JOURNAL OF EXPERIMENTAL & THEORETICAL ARTIFICIAL INTELLIGENCE, 2005, 17 (03) : 297 - 303
  • [7] A note on "A LP-based heuristic for a time-constrained routing problem"
    Muter, Ibrahim
    Birbil, S. Ilker
    Bulbul, Kerem
    Sahin, Guvenc
    EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2012, 221 (02) : 306 - 307
  • [8] FURTHER DEVELOPMENTS IN LP-BASED OPTIMAL POWER FLOW
    ALSAC, O
    BRIGHT, J
    PRAIS, M
    STOTT, B
    IEEE TRANSACTIONS ON POWER SYSTEMS, 1990, 5 (03) : 697 - 711
  • [9] Heuristic decomposition and LP-based scheduling in make-and-pack production
    Baumann, Philipp
    Trautmann, Norbert
    2011 IEEE INTERNATIONAL CONFERENCE ON INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT (IEEM), 2011, : 362 - 366
  • [10] Hybrid Flow Shop Scheduling: Heuristic Solutions and LP-Based Lower Bounds
    Gondek, Verena
    OPERATIONS RESEARCH PROCEEDINGS 2010, 2011, : 485 - 490
12345