On Plans With Loops and Noise
Pages 1310 - 1317
Abstract
In an influential paper, Levesque proposed a formal specification for analysing the correctness of program-like plans, such as conditional plans, iterative plans, and knowledge-based plans. He motivated a logical characterisation within the situation calculus that included binary sensing actions. While the characterisation does not immediately yield a practical algorithm, the specification serves as a general skeleton to explore the synthesis of program-like plans for reasonable, tractable fragments. Increasingly, classical plan structures are being applied to stochastic environments such as robotics applications. This raises the question as to what the specification for correctness should look like, since Levesque's account makes the assumption that sensing is exact and actions are deterministic. Building on a situation calculus theory for reasoning about degrees of belief and noise, we revisit the execution semantics of generalised plans. The specification is then used to analyse the correctness of example plans.
References
[1]
H. J. Levesque. What is planning in the presence of sensing? In Proc. AAAI / IAAI, pages 1139--1146, 1996.
[2]
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.
[3]
B. Bonet, H. Palacios, and H. Geffner. Automatic derivation of memoryless policies and finite-state controllers using classical planners. In ICAPS, 2009.
[4]
Y. Hu and G. De Giacomo. A generic technique for synthesizing bounded finite-state controllers. In ICAPS, 2013.
[5]
S. Srivastava, S. Zilberstein, A. Gupta, P. Abbeel, and S. Russell. Tractability of planning with loops. In AAAI, 2015.
[6]
F. Kominis and H. Geffner. Beliefs in multiagent planning: From one agent to many. In ICAPS, pages 147--155, 2015.
[7]
C. Muise, V. Belle, P. Felli, S. McIlraith, T. Miller, A. Pearce, and L. Sonenberg. Planning over multi-agent epistemic states: A classical planning approach. In Proc. AAAI, 2015.
[8]
M. J. Matarić. The robotics primer. Mit Press, 2007.
[9]
R. B. Scherl and H. J. Levesque. Knowledge, action, and the frame problem. Artificial Intelligence, 144(1--2):1--39, 2003.
[10]
R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi. Reasoning About Knowledge. MIT Press, 1995.
[11]
F. Bacchus, J. Y. Halpern, and H. J. Levesque. Reasoning about noisy sensors and effectors in the situation calculus. Artificial Intelligence, 111(1--2):171 -- 208, 1999.
[12]
F. Bacchus. Representing and Reasoning with Probabilistic Knowledge. MIT Press, 1990.
[13]
R. Fagin and J. Y. Halpern. Reasoning about knowledge and probability. J. ACM, 41(2):340--367, 1994.
[14]
B.P. Kooi. Probabilistic dynamic epistemic logic. Journal of Logic, Language and Information, 12(4):381--408, 2003.
[15]
L. P. Kaelbling, M. L. Littman, and A. R. Cassandra. Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1--2):99 -- 134, 1998.
[16]
L. P. Kaelbling and T. Lozano-Pérez. Integrated task and motion planning in belief space. I. J. Robotic Res., 32(9--10):1194--1227, 2013.
[17]
J. McCarthy and P. J. Hayes. Some philosophical problems from the standpoint of artificial intelligence. In Machine Intelligence, pages 463--502, 1969.
[18]
R. Reiter. Knowledge in action: logical foundations for specifying and implementing dynamical systems. MIT Press, 2001.
[19]
Y. Hu and H. J. Levesque. A correctness result for reasoning about one-dimensional planning problems. In IJCAI, pages 2638--2643, 2011.
[20]
S. Thrun, W. Burgard, and D. Fox. Probabilistic Robotics. MIT Press, 2005.
[21]
S. Sardi na, G. De Giacomo, Y. Lespérance, and H. J. Levesque. On the limits of planning over belief states under strict uncertainty. In KR, pages 463--471, 2006.
[22]
T. Siméon, J. Laumond, J. Cortés, and A. Sahbani. Manipulation planning with probabilistic roadmaps. The International Journal of Robotics Research, 23(7--8):729--746, 2004.
[23]
R. A. Knepper and M. T. Mason. Realtime Informed Path Sampling for Motion Planning Search, pages 401--417. Springer International Publishing, Cham, 2017.
[24]
B. Bonet and H. Geffner. Planning with incomplete information as heuristic search in belief space. In AIPS, pages 52--61, 2000.
[25]
R.P.A. Petrick and F. Bacchus. Extending the knowledge-based approach to planning with incomplete information and sensing. In Proc. ICAPS, pages 2--11, 2004.
[26]
V. Belle and H. J. Levesque. Allegro: Belief-based programming in stochastic dynamical domains. In IJCAI, 2015.
[27]
R.E. Fikes, P.E. Hart, and N.J. Nilsson. Learning and executing generalized robot plans. Artificial intelligence, 3:251--288, 1972.
[28]
W. Stephan and S. Biundo. Deduction-based refinement planning. In AIPS, pages 213--220, 1996.
[29]
E. Winner and M. M. Veloso. LoopDISTILL: Learning domain-specific planners from example plans. In Workshop on AI Planning and Learning, ICAPS, 2007.
[30]
B. Bonet, H. Palacios, and H. Geffner. Automatic derivation of finite-state machines for behavior control. In AAAI, 2010.
[31]
S. Srivastava. Foundations and Applications of Generalized Planning. PhD thesis, Department of Computer Science, University of Massachusetts Amherst, 2010.
[32]
H.J. Levesque. Planning with loops. In Proc. IJCAI, pages 509--515, 2005.
[33]
B. Bonet, G. De Giacomo, H. Geffner, and S. Rubin. Generalized planning: Non-deterministic abstractions and trajectory constraints. In IJCAI, pages 873--879, 2017.
[34]
F. Lin and H. J. Levesque. What robots can do: Robot programs and effective achievability. Artif. Intell., 101(1--2):201--226, 1998.
[35]
V. Belle and H. Levesque. Foundations for generalized planning in unbounded stochastic domains. In KR, 2016.
[36]
R. Reiter. On knowledge-based programming with sensing in the situation calculus. ACM Trans. Comput. Log., 2(4):433--457, 2001.
[37]
Y. Lespérance, H. J. Levesque, F. Lin, and R. B. Scherl. Ability and knowing how in the situation calculus. Studia Logica, 66(1):165--186, 2000.
[38]
Y. Martin and M. Thielscher. Integrating reasoning about actions and Bayesian networks. In International Conference on Agents and Artificial Intelligence, Valencia, Spain, January 2009.
[39]
M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, USA, 1st edition, 1994.
[40]
H. Geffner and B. Bonet. A Concise Introduction to Models and Methods for Automated Planning. Morgan and Claypool Publishers, 2013.
[41]
P. Poupart and C. Boutilier. Bounded finite state controllers. In NIPS, pages 823--830, 2004.
[42]
S. Sanner and K. Kersting. Symbolic dynamic programming for first-order pomdps. In Proc. AAAI, pages 1140--1146, 2010.
Index Terms
- On Plans With Loops and Noise
Recommendations
Applicability conditions for plans with loops: Computability results and algorithms
The utility of including loops in plans has been long recognized by the planning community. Loops in a plan help increase both its applicability and the compactness of its representation. However, progress in finding such plans has been limited largely ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2018
2312 pages
- General Chairs:
- Elisabeth Andre,
- Sven Koenig,
- Program Chairs:
- Mehdi Dastani,
- Gita Sukthankar
Sponsors
In-Cooperation
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Richland, SC
Publication History
Published: 09 July 2018
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
AAMAS '18
Sponsor:
Acceptance Rates
AAMAS '18 Paper Acceptance Rate 149 of 607 submissions, 25%;
Overall Acceptance Rate 1,155 of 5,036 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 54Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in