Can i really do that? verification of meta-operators via stackelberg planning
Article No.: 602, Pages 5420 - 5428
Abstract
Macro-operators are a common reformulation method in planning that adds high-level operators corresponding to a fixed sequence of primitive operators. We introduce meta-operators, which allow using different sequences of actions in each state. We show how to automatically verify whether a meta-operator is valid, i.e., the represented behavior is always doable. This can be checked at once for all instantiations of the meta-operator and all reachable states via a compilation into Stackelberg planning, a form of adversarial planning. Our results show that meta-operators learned for multiple domains can often express useful high-level behaviors very compactly, improving planners' performance.
References
[1]
Adi Botea, Markus Enzenberger, Martin Müller, and Jonathan Schaeffer. Macro-FF: Improving AI planning with automatically learned macro-operators. Journal of Artificial Intelligence Research, 24:581-621, 2005.
[2]
Tom Bylander. The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69(1-2):165-204, 1994.
[3]
Lukás Chrpa and Mauro Vallati. Planning with critical section macros: Theory and practice. Journal of Artificial Intelligence Research, 74:691- 732, 2022.
[4]
Lukás Chrpa, Mauro Vallati, and Thomas Leo McCluskey. MUM: A technique for maximising the utility of macro-operators by constrained generation and use. In Steve Chien, Alan Fern, Wheeler Ruml, and Minh Do, editors, Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2014). AAAI Press, 2014.
[5]
Lukás Chrpa, Mauro Vallati, and Thomas Leo McCluskey. Outer entanglements: a general heuristic technique for improving the efficiency of planning algorithms. J. Exp. Theor. Artif. Intell., 30(6):831- 856, 2018.
[6]
Lukás Chrpa, Mauro Vallati, and Thomas Leo McCluskey. Inner entanglements: Narrowing the search in classical planning by problem reformulation. Computational Intelligence, 35(2):395-429, 2019.
[7]
Lukás Chrpa. Generation of macro-operators via investigation of action dependencies in plans. The Knowledge Engineering Review, 25(3):281-297, 2010.
[8]
Andrew Coles and Amanda Smith. Marvin: A heuristic search planner with online macroaction learning. Journal of Artificial Intelligence Research, 28:119-156, 2007.
[9]
Jeanette Daum, Álvaro Torralba, Jörg Hoffmann, Patrik Haslum, and Ingo Weber. Practical undoability checking via contingent planning. In Amanda Coles, Andrew Coles, Stefan Edelkamp, Daniele Magazzeni, and Scott Sanner, editors, Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling, ICAPS 2016, London, UK, June 12-17, 2016, pages 106-114. AAAI Press, 2016.
[10]
Thomas Eiter, Esra Erdem, and Wolfgang Faber. On reversing actions: Algorithms and complexity. In Manuela M. Veloso, editor, Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI 2007), pages 336-341, 2007.
[11]
Thomas Eiter, Esra Erdem, and Wolfgang Faber. Undoing the effects of action sequences. Journal of Applied Logic, 6(3):380-415, 2008.
[12]
Richard E. Fikes and Nils J. Nilsson. STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2:189-208, 1971.
[13]
Richard Fikes, Peter E. Hart, and Nils J. Nilsson. Learning and executing generalized robot plans. Artificial Intelligence, 3(1-3):251-288, 1972.
[14]
Daniel Fišer. Lifted fact-alternating mutex groups and pruned grounding of classical planning problems. In Vincent Conitzer and Fei Sha, editors, Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2020), pages 9835-9842. AAAI Press, 2020.
[15]
B. Cenk Gazen and Craig A. Knoblock. Combining the expressivity of UCPOP with the efficiency of Graphplan. In Sam Steel and Rachid Alami, editors, Recent Advances in AI Planning. 4th European Conference on Planning (ECP 1997), volume 1348 of Lecture Notes in Artificial Intelligence, pages 221-233. Springer-Verlag, 1997.
[16]
Alfonso E. Gerevini, Alessandro Saetti, and Mauro Vallati. An automatically configurable portfolio-based planner with macro-actions: PbP. In Alfonso Gerevini, Adele Howe, Amedeo Cesta, and Ioannis Refanidis, editors, Proceedings of the Nineteenth International Conference on Automated Planning and Scheduling (ICAPS 2009), pages 350-353. AAAI Press, 2009.
[17]
Malte Helmert. The Fast Downward planning system. Journal of Artificial Intelligence Research, 26:191-246, 2006.
[18]
Malte Helmert. Concise finite-domain representations for PDDL planning tasks. Artificial Intelligence, 173:503-535, 2009.
[19]
Jörg Hoffmann and Bernhard Nebel. The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14:253-302, 2001.
[20]
Richard E. Korf. Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence, 27(1):97-109, 1985.
[21]
Derek Long and Maria Fox. The 3rd International Planning Competition: Results and analysis. Journal of Artificial Intelligence Research, 20:1-59, 2003.
[22]
Drew McDermott. The 1998 AI Planning Systems competition. AI Magazine, 21(2):35-55, 2000.
[23]
Michael Morak, Lukas Chrpa, Wolfgang Faber, and Daniel Fišer. On the reversibility of actions in planning. In Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, pages 652-661, 9 2020.
[24]
Bernhard Nebel. On the compilability and expressive power of propositional planning formalisms. Journal of Artificial Intelligence Research, 12:271-315, 2000.
[25]
Florian Pham and Álvaro Torralba. Code, benchmarks, and experimental data for the IJCAI 2023 paper "can i really do that? verification of meta-operators via stackelberg planning"., 2023.
[26]
Silvia Richter and Matthias Westphal. The LAMA planner -- Using landmark counting in heuristic search. IPC 2008 short papers, http://ipc.informatik.uni-freiburg.de/Planners, 2008.
[27]
Philipp Sauer, Marcel Steinmetz, Robert Künnemann, and Jörg Hoffmann. Lifted stackelberg planning. In Proceedings of the 33rd International Conference on Automated Planning and Scheduling, ICAPS 2023, 2023.
[28]
Jendrik Seipp, Florian Pommerening, Silvan Sievers, and Malte Helmert. Downward Lab., 2017.
[29]
Patrick Speicher, Marcel Steinmetz, Michael Backes, Jörg Hoffmann, and Robert Künnemann. Stackelberg planning: Towards effective leader-follower state space search. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence (AAAI 2018), pages 6286-6293. AAAI Press, 2018.
[30]
Milind Tambe. Security and game theory: Algorithms, deployed systems, lessons learned. Cambridge University Press, 2011.
[31]
Álvaro Torralba, Vidal Alcázar, Peter Kissmann, and Stefan Edelkamp. Efficient symbolic search for cost-optimal planning. Artificial Intelligence, 242:52-79, 2017.
[32]
Álvaro Torralba, Patrick Speicher, Robert Künnemann, Marcel Steinmetz, and Jörg Hoffmann. Faster stackelberg planning via symbolic search and information sharing. In Kevin Leyton-Brown and Mausam, editors, Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI 2021), pages 11998-12006. AAAI Press, 2021.
Index Terms
- Can i really do that? verification of meta-operators via stackelberg planning
Index terms have been assigned to the content through auto-classification.
Recommendations
On the computational complexity of stackelberg planning and meta-operator verification
ICAPS '24: Proceedings of the Thirty-Fourth International Conference on Automated Planning and SchedulingStackelberg planning is a recently introduced single-turn two-player adversarial planning model, where two players are acting in a joint classical planning task, the objective of the first player being hampering the second player from achieving its goal. ...
SUOWA operators
SUOWA operators are a new family of aggregation functions that simultaneously generalize weighted means and OWA operators. Semi-uninorms, which are an extension of uninorms by dispensing with the symmetry and associativity properties, play a fundamental ...
Distributivity between semi-t-operators and Mayor's aggregation operators
The problem of distributivity was first posed over forty years ago and it has been investigated for families of certain operations such as t-norms, t-conorms, uninorms, and nullnorms. In this paper, we investigate this topic further by focusing on Mayor'...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2023 International Joint Conferences on Artificial Intelligence.
Sponsors
- International Joint Conferences on Artifical Intelligence (IJCAI)
Publisher
Unknown publishers
Publication History
Published: 19 August 2023
Qualifiers
- Research-article
- Research
- Refereed limited
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 05 Mar 2025