A Correctness Result for Reasoning about One-Dimensional Planning Problems

Hu, Yuxiao; Levesque, Hector J.

doi:10.5591/978-1-57735-516-8/IJCAI11-439

A Correctness Result for Reasoning about One-Dimensional Planning Problems

Yuxiao Hu, Hector J. Levesque

Download BibTeX Cite

Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2638-2642.

https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-439

Abstract

A plan with rich control structures like branches and loops can usually serve as a general solution that solves multiple planning instances in a domain. However, the correctness of such generalized plans is non-trivial to define and verify, especially when it comes to whether or not a plan works for all of the infinitely many instances of the problem. In this paper, we give a precise definition of a generalized plan representation called an FSA plan, with its semantics defined in the situation calculus. Based on this, we identify a class of infinite planning problems, which we call one-dimensional (1d), and prove a correctness result that 1d problems can be verified by finite means. We show that this theoretical result leads to an algorithm that does this verification practically, and a planner based on this verification algorithm efficiently generates provably correct plans for 1d problems.

Yuxiao Hu, and Hector J. Levesque. 2011. A Correctness Result for Reasoning about One-Dimensional Planning Problems. In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11. IJCAI, 2638–2642. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-439

@inproceedings{ijcai2011p439,
  title     = {A Correctness Result for Reasoning about One-Dimensional Planning Problems},
  author    = {Hu, Yuxiao and Levesque, Hector J.},
  booktitle = {Proceedings of the Twenty-Second International Joint Conference on
               Artificial Intelligence, {IJCAI-11}},
  publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
  editor    = {Toby Walsh},
  pages     = {2638--2642},
  year      = {2011},
  month     = {7},
  doi       = {10.5591/978-1-57735-516-8/IJCAI11-439},
  url       = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-439},
}

TY  - CPAPER
TI  - A Correctness Result for Reasoning about One-Dimensional Planning Problems
AU  - Hu, Yuxiao
AU  - Levesque, Hector J.
T2  - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11
PB  - AAAI Press/International Joint Conferences on Artificial Intelligence
PY  - 2011
SP  - 2638
EP  - 2642
DO  - 10.5591/978-1-57735-516-8/IJCAI11-439
UR  - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-439
ER  -