More Web Proxy on the site http://driver.im/

article

An approach to efficient planning with numerical fluents and multi-criteria plan quality

Authors:

Alfonso E. Gerevini,

Alessandro Saetti,

Ivan SerinaAuthors Info & Claims

Artificial Intelligence, Volume 172, Issue 8-9

Pages 899 - 944

https://doi.org/10.1016/j.artint.2008.01.002

Published: 01 May 2008 Publication History

Abstract

Dealing with numerical information is practically important in many real-world planning domains where the executability of an action can depend on certain numerical conditions, and the action effects can consume or renew some critical continuous resources, which in pddl can be represented by numerical fluents. When a planning problem involves numerical fluents, the quality of the solutions can be expressed by an objective function that can take different plan quality criteria into account. We propose an incremental approach to automated planning with numerical fluents and multi-criteria objective functions for pddl numerical planning problems. The techniques in this paper significantly extend the framework of planning with action graphs and local search implemented in the lpg planner. We define the numerical action graph (NA-graph) representation for numerical plans and we propose some new local search techniques using this representation, including a heuristic search neighborhood for NA-graphs, a heuristic evaluation function based on relaxed numerical plans, and an incremental method for plan quality optimization based on particular search restarts. Moreover, we analyze our approach through an extensive experimental study aimed at evaluating the importance of some specific techniques for the performance of the approach, and at analyzing its effectiveness in terms of fast computation of a valid plan and quality of the best plan that can be generated within a given CPU-time limit. Overall, the results show that our planner performs quite well compared to other state-of-the-art planners handling numerical fluents.

References

[1]

F. Bacchus, M. Ady, Planning with resources and concurrency: A forward chaining approach, in: Proceedings 17th International Joint Conference on Artificial Intelligence (IJCAI-01), Seattle, WA, USA, 2001, pp. 417--424

Digital Library

[2]

J. Benton, M.B. Do, S. Kambhampati, Over-subscription planning with numeric goals, in: Proceedings 19th International Joint Conference on Artificial Intelligence (IJCAI-05), Edinburgh, Scotland, 2005, pp. 1207--1214

Digital Library

[3]

Blum, A. and Furst, M.L., Fast planning through planning graph analysis. Artificial Intelligence. v90. 281-300.

Digital Library

[4]

Chen, Y., Hsu, C. and Wah, B., Temporal planning using subgoal partitioning and resolution in SGPlan. Journal of Artificial Intelligence Research (JAIR). v26. 323-369.

Digital Library

[5]

Y. Chen, C. Hsu, W. Wha, SGPlan: Subgoal partitioning and resolution in planning, in: Abstract Booklet of the Competing Planners of ICAPS-04, 2004, pp. 30--32

[6]

Dechter, R., Meiri, I. and Pearl, J., Temporal constraint networks. Artificial Intelligence. v49. 61-95.

Digital Library

[7]

Y. Dimopoulos, A. Gerevini, P. Haslum, A. Saetti, The benchmark domains of the deterministic part of IPC-5, in: Abstract Booklet of the Competing Planners of ICAPS-06, 2006, pp. 14--19

[8]

Do, M. and Kambhampati, S., Sapa: A multi-objective metric temporal planner. Journal of Artificial Intelligence Research (JAIR). v20. 155-194.

Digital Library

[9]

Edelkamp, S., Taming numbers and duration in the model checking integrated planning system. Journal of Artificial Intelligence Research (JAIR). v20. 61-124.

[10]

M. Fox, D. Long, Utilizing automatically inferred invariants in graph construction and search, in: Proceedings 5th International Conference on Artificial Intelligence Planning and Scheduling (AIPS-00), Breckenridge, CO, USA, 2000, pp. 102--111

[11]

Fox, M. and Long, D., PDDL2.1: An extension to PDDL for expressing temporal planning domains. Journal of Artificial Intelligence Research (JAIR). v20. 61-124.

Digital Library

[12]

A. Garrido, D. Long, Planning with numeric variables in multi-objective planning, in: Proceedings 16th European Conference on Artificial Intelligence (ECAI-04), Valencia, Spain, 2004, pp. 662--666

Digital Library

[13]

A. Gerevini, D. Long, Plan constraints and preferences in PDDL3, Technical Report 2005-08-47, Università degli Studi di Brescia, Dipartimento di Elettronica per l'Automazione, 2005

[14]

Gerevini, A., Saetti, A. and Serina, I., On managing temporal information for handling durative actions in LPG. In: AI*IA 2003: Advances in Artificial Intelligence, Springer-Verlag, Berlin, Heidelberg, New York. pp. 91-104.

[15]

Gerevini, A., Saetti, A. and Serina, I., Planning through stochastic local search and temporal action graphs. Journal of Artificial Intelligence Research (JAIR). v20. 239-290.

Digital Library

[16]

A. Gerevini, A. Saetti, I. Serina, An empirical analysis of some heuristic features for local search in LPG, in: Proceedings 14th International Conference on Automated Planning and Scheduling (ICAPS-04), Whistler, Canada, 2004, pp. 171--180

[17]

Gerevini, A., Saetti, A. and Serina, I., An approach to temporal planning and scheduling in domains with predictable exogenous events. Journal of Artificial Intelligence Research (JAIR). v25. 187-231.

Digital Library

[18]

A. Gerevini, A. Saetti, I. Serina, An approach to efficient planning with numerical fluents and multi-criteria plan quality (preliminary report), Technical Report 2007-01-53, Università degli Studi di Brescia, Dip. di Elettronica per l'Automazione, 2007

[19]

A. Gerevini, I. Serina, Fast planning through greedy action graphs, in: Proceedings 16th National Conference on Artificial Intelligence (AAAI-99), Orlando, FL, USA, 1999, pp. 503--510

Digital Library

[20]

M. Ghallab, A. Howe, C. Knoblock, D. McDermott, A. Ram, M. Veloso, D. Weld, D. Wilkins, PDDL---the planning domain definition language, Technical Report CVC TR98-003/DCS TR-1165, Yale Center for Computational Vision and Control, 1998

[21]

Ghallab, M., Nau, D. and Traverso, P., Automated Planning: Theory and Practice. 2003. Morgan Kaufmann Publishers, San Francisco, CA, USA.

Digital Library

[22]

Glover, F. and Laguna, M., Tabu Search. 1997. Kluwer Academic Publishers, Boston, MA, USA.

Digital Library

[23]

Goldberg, D.E., Genetic Algorithms in Search, Optimization and Machine Learning. 1989. Addison-Wesley, Boston, MA, USA.

Digital Library

[24]

P. Haslum, H. Geffner, Heuristic planning with time and resources, in: Proceedings 6th European Conference on Planning (ECP-01), Toledo, Spain, 2001

[25]

M. Helmert, Decidability and undecidability results for planning with numerical state variables, in: Proceedings 6th International Conference on Artificial Intelligence Planning and Scheduling (AIPS-02), Toulouse, France, 2002, pp. 303--312

[26]

Helmert, M., The Fast Downward planning system. Journal of Artificial Intelligence Research (JAIR). v26. 191-246.

[27]

Hoffmann, J., The Metric-FF planning system: Translating “ignoring delete lists”, to numeric state variables. Journal of Artificial Intelligence Research (JAIR). v20. 291-341.

Digital Library

[28]

Hoffmann, J. and Edelkamp, S., The deterministic part of IPC-4: An overview. Journal of Artificial Intelligence Research (JAIR). v24. 519-579.

[29]

Hoffmann, J., Edelkamp, S., Thièbaux, S., Englert, R., Liporace, F. and Trueg, S., Engineering benchmarks for planning: the domains used in the deterministic part of IPC-4. Journal of Artificial Intelligence Research (JAIR). v26. 453-541.

Digital Library

[30]

J. Hoffmann, H. Kautz, C. Gomes, B. Selman, SAT encodings of state-space reachability problems in numeric domains, in: Proceedings 20th International Joint Conference on Artificial Intelligence (IJCAI-07), Hyderabad, India, 2007

Digital Library

[31]

Hoffmann, J. and Nebel, B., The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research (JAIR). v14. 253-302.

Digital Library

[32]

C. Hsu, B.W. Wah, R. Huang, Y. Chen, New features in SGPlan for handling preferences and constraints in PDDL3.0, in: Abstract Booklet of the competing planners of IPC-5, 2006, pp. 39--41

[33]

H. Kautz, J.P. Walser, State-space planning by integer optimization, in: Proceedings 16th National Conference on Artificial Intelligence (AAAI-98), Madison, WI, USA, 1998, pp. 526--533

Digital Library

[34]

J. Koehler, Planning under resource constraints, in: Proceedings 13th European Conference on Artificial Intelligence (ECAI-98), Brighton, UK, 1998, pp. 489--493

[35]

J. Koehler, B. Nebel, J. Hoffmann, Y. Dimopoulos. Extending planning graphs to an ADL subset, Technical Report 88, Institut für Informatik, Freiburg, Germany, 1997

Digital Library

[36]

Long, D. and Fox, M., The 3rd international planning competition: Results and analysis. Journal of Artificial Intelligence Research (JAIR). v20. 1-59.

Digital Library

[37]

D. Nau, Y. Cao, A. Lotem, H. Muòoz Avila, SHOP: Simple hierarchical ordered planner, in: Proceedings 16th International Joint Conference on Artificial Intelligence (IJCAI-99), Stockholm, Sweden, 1999, pp. 968--973

Digital Library

[38]

J.S. Penberthy, D.S. Weld, Temporal planning with continuous change, in: Proceedings 12th National Conference on Artificial Intelligence (AAAI-94), Seattle, WA, USA, 1994, pp. 1010--1015

Digital Library

[39]

S.J. Penberthy, Planning with continuous change, PhD thesis, University of Washington, 1993. Available as technical report UW-CSE-93-12-01

Digital Library

[40]

Ramesh, T., Traveling purchaser problem. Opsearch. v18. 78-91.

[41]

I. Refanidis, I. Vlahavas, GRT: A domain independent heuristic for STRIPS worlds based on greedy regression tables, in: Proceedings 5th European Conference on Planning (ECP-99), Durham, UK, 1999, pp. 346--358

Digital Library

[42]

I. Refanidis, I. Vlahavas, Heuristic planning with resources, in: Proceedings 14th European Conference on Artificial Intelligence (ECAI-00), Berlin, Germany, 2000, pp. 521--525

Digital Library

[43]

Refanidis, I. and Vlahavas, I., Multiobjective heuristic state-space planning. Artificial Intelligence Journal. v145 i1--2. 1-32.

Digital Library

[44]

B. Selman, H.A. Kautz, B. Cohen, Noise strategies for improving local search, in: Proceedings 12th National Conference on Artificial Intelligence (AAAI-94), Seattle, WA, USA, 1994, pp. 337--343

Digital Library

[45]

Simon, A.H., Models of Man. 1957. John Wiley & Sons Inc., New York, USA.

[46]

D. Smith, Choosing objectives in over-subscription planning, in: Proceedings 14th International Conference on Automated Planning and Scheduling (ICAPS-04), Whistler, Canada, 2004

[47]

Wilcoxon, F. and Wilcox, R.A., Some Rapid Approximate Statistical Procedures. 1964. Lederle Laboratories, Pearl River, New York, USA.

[48]

M. Williamson, S. Hanks, Optimal planning with a goal-directed utility model, in: Proceedings 2nd International Conference on Artificial Intelligence Planning and Scheduling (AIPS-94), Chicago, IL, USA, 1994, pp. 176--181

[49]

S. Wolfman, D. Weld, The LPSAT system and its applications to resource planning, in: Proceedings 16th International Joint Conference on Artificial Intelligence (IJCAI-99), Stockholm, Sweden, 1999

Digital Library

Cited By

Helal HLakemeyer GBernardini SMuise C(2024)An analysis of the decidability and complexity of numeric additive planningProceedings of the Thirty-Fourth International Conference on Automated Planning and Scheduling10.1609/icaps.v34i1.31484(267-275)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1609/icaps.v34i1.31484
Ghilardi SGianola AMontali MRivkin AElkind E(2023)Safety verification and universal invariants for relational action basesProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/362(3248-3257)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/362
Shleyfman AGnad DJonsson PWilliams BChen YNeville J(2023)Structurally restricted fragments of numeric planning - a complexity analysisProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i10.26428(12112-12119)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i10.26428
Show More Cited By

Index Terms

An approach to efficient planning with numerical fluents and multi-criteria plan quality
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Planning in domains with derived predicates through rule-action graphs and local search

The ability to express derived predicates in the formalization of a planning domain is both practically and theoretically important. In this paper, we propose an approach to planning with derived predicates where the search space consists of "Rule-...
An Empirical Analysis of Some Heuristic Features for Planning through Local Search and Action Graphs
RCRA 2009 Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion

Planning through local search and action graphs is a powerful approach to fully-automated planning which is implemented in the well-known LPG planner. The approach is based on a stochastic local search procedure exploring a space of partial plans and ...
Kernel functions for case-based planning

Case-based planning can take advantage of former problem-solving experiences by storing in a plan library previously generated plans that can be reused to solve similar planning problems in the future. Although comparative worst-case complexity analyses ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Artificial Intelligence

Artificial Intelligence Volume 172, Issue 8-9

May, 2008

296 pages

ISSN:0004-3702

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2008.

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 01 May 2008

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

36
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Helal HLakemeyer GBernardini SMuise C(2024)An analysis of the decidability and complexity of numeric additive planningProceedings of the Thirty-Fourth International Conference on Automated Planning and Scheduling10.1609/icaps.v34i1.31484(267-275)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1609/icaps.v34i1.31484
Ghilardi SGianola AMontali MRivkin AElkind E(2023)Safety verification and universal invariants for relational action basesProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/362(3248-3257)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/362
Shleyfman AGnad DJonsson PWilliams BChen YNeville J(2023)Structurally restricted fragments of numeric planning - a complexity analysisProceedings of the Thirty-Seventh AAAI Conference on Artificial Intelligence and Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence and Thirteenth Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v37i10.26428(12112-12119)Online publication date: 7-Feb-2023
https://dl.acm.org/doi/10.1609/aaai.v37i10.26428
Anastacio MHoos H(2020)Model-Based Algorithm Configuration with Default-Guided Probabilistic SamplingParallel Problem Solving from Nature – PPSN XVI10.1007/978-3-030-58112-1_7(95-110)Online publication date: 5-Sep-2020
https://dl.acm.org/doi/10.1007/978-3-030-58112-1_7
Mittelmann MPerrussel L(2020)Game Description Logic with Integers: A GDL Numerical ExtensionFoundations of Information and Knowledge Systems10.1007/978-3-030-39951-1_12(191-210)Online publication date: 17-Feb-2020
https://dl.acm.org/doi/10.1007/978-3-030-39951-1_12
Cohen EBeck JMcIlraith SWeinberger K(2018)Fat- and heavy-tailed behavior in satisficing planningProceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence10.5555/3504035.3504788(6136-6143)Online publication date: 2-Feb-2018
https://dl.acm.org/doi/10.5555/3504035.3504788
Farrell RWare SMagerko BRowe J(2017)Causal link semantics for narrative planning using numeric fluentsProceedings of the Thirteenth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment10.5555/3505326.3505354(193-199)Online publication date: 5-Oct-2017
https://dl.acm.org/doi/10.5555/3505326.3505354
Scala EHaslum PMagazzeni DThiébaux S(2017)Landmarks for numeric planning problemsProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171837.3171899(4384-4390)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171837.3171899
Scala EHaslum PThiébaux S(2016)Heuristics for numeric planning via subgoalingProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3061053.3061073(3228-3234)Online publication date: 9-Jul-2016
https://dl.acm.org/doi/10.5555/3061053.3061073
Scala EHaslum PThiebaux SRamirez M(2016)Interval-based relaxation for general numeric planningProceedings of the Twenty-second European Conference on Artificial Intelligence10.3233/978-1-61499-672-9-655(655-663)Online publication date: 29-Aug-2016
https://dl.acm.org/doi/10.3233/978-1-61499-672-9-655
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents