Article

Planning with loops

Author:

Hector J. LevesqueAuthors Info & Claims

IJCAI'05: Proceedings of the 19th international joint conference on Artificial intelligence

Pages 509 - 515

Published: 30 July 2005 Publication History

Abstract

Unlike the case for sequential and conditional planning, much of the work on iterative planning (planning where loops may be needed) leans heavily on theorem-proving. This paper does the following: it proposes a different approach where generating plans is decoupled from verifying them; describes the implementation of an iterative planner based on the situation calculus; presents a few examples illustrating the sorts of plans that can be generated; shows some of the strengths and weaknesses of the approach; and finally sketches the beginnings of a theory, where validation of plans is done offline.

References

[1]

{Bacchus and Kabanza, 2000} F. Bacchus and F. Kabanza. Using temporal logics to express search control knowledge for planning. Artificial Intelligence, 116, 2000.

Digital Library

[2]

{Biundo, 1994} S. Biundo. Present-day deductive planning. In C. Bäckström and E. Sandewell, editors, Procs. of the 2nd European Workshop on Planning (EWSP-93), pages 1-5, Vadstena, Sweeden, 1994. IOS Press (Amsterdam).

[3]

{Bonet and Geffner, 2001} B. Bonet and H. Geffner. Gpt: a tool for planning with uncertainty and partial information. In Proc. IJCAI-01 Workshop on Planning with Uncertainty and Partial Information, pages 82-87, 2001.

[4]

{Cimatti et al., 2003} A. Cimatti, M. Pistore, M. Roveri, and P. Traverso. Weak, strong, and strong cyclic planning via symbolic model checking. Artificial Intelligence, 147(1- 2):35-84, 2003.

Digital Library

[5]

{de Giacomo and Levesque, 1999} G. de Giacomo and H. Levesque. An incremental interpreter for high-level programs with sensing. In H. Levesque and F. Pirri, editors, Logical Foundation for Cognitive Agents: Contributions in Honor of Ray Reiter, pages 86-102. Springer, Berlin, 1999.

[6]

{Demolombe and Parra, 2000} R. Demolombe and M. Pozos Parra. A simple and tractable extension of situation calculus to epistemic logic. Lecture Notes in Computer Science, 1932, 2000.

Digital Library

[7]

{Lespérance et al., 1999} Y. Lespérance, H. Levesque, and R. Reiter. A situation calculus approach to modeling and programming agents. In A. Rao and M. Wooldridge, editors, Foundations and Theories of Rational Agency. Kluwer, 1999.

[8]

{Levesque, 1996} H. Levesque. What is planning in the presence of sensing? In Procs. of the 13th National Conference, AAAI-96, pages 1139-1146, Portland, Oregon, 1996.

Digital Library

[9]

{Lin and Levesque, 1998} F. Lin and H. Levesque. What robots can do: Robot programs and effective achievability. Artificial Intelligence, 101:201-226, 1998.

[10]

{Manna and Waldinger, 1980} Z. Manna and R. Waldinger. A deductive approach to program synthesis. ACM Transactions on Programming Languages and Systems, 2(1):90-121, 1980.

Digital Library

[11]

{McCarthy and Hayes, 1981} J. McCarthy and P. J. Hayes. Some philosophical problems from the standpoint of artificial intelligence. In B. Webber and N. Nilsson, editors, Readings in Artificial Intelligence, pages 431-450. Kaufmann, Los Altos, 1981.

[12]

{Ngo and Haddawy, 1995} L. Ngo and P. Haddawy. Representing iterative loops for decision theoretic planning. In Extending Theories of Action: Papers from the 1995 AAAI Spring Symposium, pages 151-156. AAAI Press, Menlo Park, 1995.

[13]

{Petrick and Bacchus, 2004} R. Petrick and F. Bacchus. Extending the knowledge-based approach to planning with incomplete information and sensing. In Shlomo Zilberstein, Jana Koehler, and Sven Koenig, editors, Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS-04), pages 2-11, Menlo Park, CA, June 2004. AAAI Press.

[14]

{Reiter, 2001} R. Reiter. Knowledge in Action. Logical Foundations for Specifying and Implementing Dynamical Systems. MIT Press, 2001.

Digital Library

[15]

{Sardina et al., 2004} S. Sardina, G. de Giacomo, Y. Lespérance, and H. Levesque. On the semantics of deliberation in IndiGolog - from theory to implementation. Annals of Mathematics and Artificial Intelligence, 41(2-4):259-299, Aug 2004.

Digital Library

[16]

{Stephan and Biundo, 1996} W. Stephan and S. Biundo. Deduction based refinement planning. In B. Drabble, editor, Procs. of AIPS-96, pages 213-220. AAAI Press, 1996.

[17]

{Vassos, 2004} S. Vassos. A feasible approach to disjunctive knowledge in situation calculus. Master's thesis, Department of Computer Science, University of Toronto, 2004.

Cited By

Luo KLiu Y(2019)Automatic verification of FSA strategies via counterexample-guided local search for invariantsProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367243.3367290(1814-1821)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367243.3367290
Illanes LMcIlraith S(2019)Generalized planning via abstractionProceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v33i01.33017610(7610-7618)Online publication date: 27-Jan-2019
https://dl.acm.org/doi/10.1609/aaai.v33i01.33017610
Belle VAndre EKoenig SDastani MSukthankar G(2018)On Plans With Loops and NoiseProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237895(1310-1317)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237895
Show More Cited By

Index Terms

Planning with loops
1. Applied computing
  1. Enterprise computing

Recommendations

Using loops in decision-theoretic refinement planners
AIPS'96: Proceedings of the Third International Conference on Artificial Intelligence Planning Systems

Classical AI planners use loops over subgoals to move a stack of blocks by repeatedly moving the top block. Probabilistic planners and reactive systems repeatedly try to pick up a block to increase the probability of success in an uncertain environment. ...
Fast planning through planning graph analysis
IJCAI'95: Proceedings of the 14th international joint conference on Artificial intelligence - Volume 2

We introduce a new approach to planning in STRIPS-like domains based on constructing and analyzing a compact structure we call a Planning Graph. We describe a new planner, Graphplan, that uses this paradigm. Graphplan always returns a shortest-possible ...
Planning for contingencies: a decision-based approach

A fundamental assumption made by classical AI planners is that there is no uncertainty in the world: the planner has full knowledge of the conditions under which the plan will be executed and the outcome of every action is fully predictable. These ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

IJCAI'05: Proceedings of the 19th international joint conference on Artificial intelligence

July 2005

1775 pages

Sponsors

The International Joint Conferences on Artificial Intelligence, Inc.

Publisher

Morgan Kaufmann Publishers Inc.

San Francisco, CA, United States

Publication History

Published: 30 July 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Luo KLiu Y(2019)Automatic verification of FSA strategies via counterexample-guided local search for invariantsProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367243.3367290(1814-1821)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367243.3367290
Illanes LMcIlraith S(2019)Generalized planning via abstractionProceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence10.1609/aaai.v33i01.33017610(7610-7618)Online publication date: 27-Jan-2019
https://dl.acm.org/doi/10.1609/aaai.v33i01.33017610
Belle VAndre EKoenig SDastani MSukthankar G(2018)On Plans With Loops and NoiseProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems10.5555/3237383.3237895(1310-1317)Online publication date: 9-Jul-2018
https://dl.acm.org/doi/10.5555/3237383.3237895
Illanes LMcIlraith S(2017)Numeric planning via abstraction and policy guided searchProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171837.3171893(4338-4345)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171837.3171893
Bonet BDe Giacomo GGeffner HRubin S(2017)Generalized planningProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171642.3171767(873-879)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171642.3171767
De Giacomo GMurano ARubin SDi Stasio A(2016)Imperfect-information games and generalized planningProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060765(1037-1043)Online publication date: 9-Jul-2016
https://dl.acm.org/doi/10.5555/3060621.3060765
Xiong LLiu Y(2016)Strategy representation and reasoning in the situation calculusProceedings of the Twenty-second European Conference on Artificial Intelligence10.3233/978-1-61499-672-9-982(982-990)Online publication date: 29-Aug-2016
https://dl.acm.org/doi/10.3233/978-1-61499-672-9-982
He JZhao X(2016)Reasoning about actions with loops via Hoare logicFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-016-5158-610:5(870-888)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s11704-016-5158-6
Srivastava SImmerman NZilberstein S(2012)Applicability conditions for plans with loopsArtificial Intelligence10.1016/j.artint.2012.07.005191-192(1-19)Online publication date: 1-Nov-2012
https://dl.acm.org/doi/10.1016/j.artint.2012.07.005
Srivastava SImmerman NZilberstein SZhang T(2011)Directed search for generalized plans using classical plannersProceedings of the Twenty-First International Conference on International Conference on Automated Planning and Scheduling10.5555/3038485.3038515(226-233)Online publication date: 11-Jun-2011
https://dl.acm.org/doi/10.5555/3038485.3038515
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents