An Experimental Study of Influence of Modeling and Solving Techniques on Performance of a Tabled Logic Programming Planner

• Autorzy: Barták R. , Vodrážka J.

Identyfikatory

DOI

10.3233/FI-2016-1442

• Konferencja: Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (22; 22.09.2015; Ferrara; Italy)
• Języki publikacji: EN

Abstrakty

EN

Logic programming provides a declarative framework for modeling and solving many combinatorial problems. Until recently, it was not competitive with state-of-the-art planning techniques partly due to search capabilities limited to backtracking. Recent development brought more advanced search techniques to logic programming such as tabling that simplifies implementation and exploitation of more sophisticated search algorithms. Together with rich modeling capabilities this progress brings tabled logic programing on a par with current best planners. This paper describes the planner module of the tabled logic programming language Picat, its modeling capabilities, and core search procedures behind the planner. The major contribution is an experimental comparison of the influence of various modeling techniques, namely factored vs. structured representations of states, control knowledge, and heuristics on the performance of two search procedures – iterative deepening and branch and bound-behind the planner. The paper also compares the Picat planner with winning automated planners both domain dependent and domain independent to demonstrate that the presented techniques are competitive with state-of-the-art.

Słowa kluczowe

EN

planning; modeling; tabling; search; iterative deepening; branch-and-bound

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 149, nr 1/2
• Strony: 35--60
• Opis fizyczny: Bibliogr. 36 poz., tab., wykr.

Twórcy

autor

Barták R.

• Charles University, Faculty of Mathematics and Physics, Malostranské náměstí 25, 118 00 Praha 1, Czech Republic

autor

Vodrážka J.

• Charles University, Faculty of Mathematics and Physics, Malostranské náměstí 25, 118 00 Praha 1, Czech Republic

Bibliografia

• [1] Fahiem Bacchus and Froduald Kabanza. Using temporal logics to express search control knowledge for planning. Artificial Intelligence, 2000;116(1-2):123–191. doi:10.1016/S0004-3702(99)00071-5.
• [2] Christer Bäckström and Bernhard Nebel. Complexity results for SAS+ planning. Computational Intelligence, 1995;11(4):625–655. doi: 10.1111/j.1467-8640.1995.tb00052.x.
• [3] Jorge A. Baier, Christian Fritz, and Sheila McIlraith. Exploiting procedural domain control knowledge in state-of-the-art planners. in: Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling, ICAPS 2007, Providence, Rhode Island, USA, 2007 p. 26–33. Available from: bai-fri-mci-icaps07.pdf.
• [4] Roman Barták and Neng-Fa Zhou. Using tabled logic programming to solve the Petrobras planning problem. Theory and Practice of Logic Programming, 2014;14(4-5):697–710. Available from: https://doi.org/10.1017/S1471068414000295.
• [5] Roman Barták, Agostino Dovier, Neng-Fa Zhou. On modeling planning problems in tabled logic programming. in: Proceedings of the 17th International Symposium on Principles and Practice of Declarative Programming – PPDP’15, 2015 p. 32–42. doi:10.1145/2790449.2790521.
• [6] Agostino Dovier, Andrea Formisano, and Enrico Pontelli. Multi-valued Action Languages with Constraints in CLP(FD), Theory and Practice of Logic Programming, 2010;10(2):167–235. doi:10.1017/S1471068410000013.
• [7] Richard E. Fikes and Nils J. Nilsson. STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving. Artificial Intelligence, 1971;2(3-4):189–208. Available from: http://dl.acm.org/citation.cfm?id=1622876.1622939.
• [8] Michael Gelfond and Vladimir Lifschitz. Action Languages, Electronic Transactions on Artificial Intelligence, 1998;3(26):195–210.
• [9] Malik Ghallab; Dana S. Nau; and Paolo Traverso. Automated Planning: Theory and Practice, Elsevier, 2004. ISBN:1558608567.
• [10] Hai-Feng Guo and Gopal Gupta. Simplifying dynamic programming via mode-directed tabling. Software: Practice and Experience, 2008;38(1):75–94. doi:10.1002/spe.v38:1.
• [11] Patrik Haslum and Ulrich Scholz. Domain knowledge in planning: Representation and use. in: ICAPS Workshop on PDDL. Proceedings, 2003.
• [12] Carl Hewitt. Planner: A language for proving theorems in robots. in: Proceedings of IJCAI, 1969 p. 295–302. Available from: http://dl.acm.org/citation.cfm?id=1624562.1624592.
• [13] International Planning Competitions web site, http://ipc.icaps-conference.org/, Accessed April 5, 2015.
• [14] Henry Kautz and Bart Selman. Planning as satisfiability. in: Proceedings of ECAI, 1992 p. 359–363. ISBN:0-471-93608-1.
• [15] Richard E. Korf. Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence, 1985;27(1):97–109. doi:10.1016/0004-3702(85)90084-0.
• [16] Jonas Kvarnström and Martin Magnusson. Talplanner in the third international planning competition: Extensions and control rules. J. Artificial Intelligence Research (JAIR), 2003;20(1):343–377. Available from: http://dl.acm.org/citation.cfm?id=1622452.1622464.
• [17] Ailsa H. Land and Alison G. Doig. An automatic method of solving discrete programming problems. Econometrica 1960;28(3):497–520. Available from: http://jmvidal.cse.sc.edu/library/land60a.pdf.
• [18] Derek Long and Maria Fox. The 3rd International Planning Competition: Results and Analysis, Journal of Artificial Intelligence Research 2003;20(1):1–59. Available from: http://dl.acm.org/citation.cfm?id=1622452.1622453.
• [19] Drew McDermott. The planning domain definition language manual. CVC Report 98-003, Yale Computer Science Report 1165, 1998.
• [20] Dana S. Nau, Tsz-Chiu Au, Okhtay Ilghami, Ugur Kuter, J. William Murdock, Dan Wu, and Fusun Yaman. SHOP2: an HTN planning system. J. Artificial Intelligence Research (JAIR), 2003;20(1):379–404. Available from: http://dl.acm.org/citation.cfm?id=1622452.1622465.
• [21] Nils J. Nilsson. Shakey The Robot, Technical Note 323. AI Center, SRI International, 333 Ravenswood Ave., Menlo Park, CA 94025, Apr 1984.
• [22] Picat web site, http://picat-lang.org/, Accessed July 3, 2015.
• [23] Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. Pearson, 2009.
• [24] Pat Riddle, Mike Barley, Santiago Franco, and Jordan Douglas. Automated Transformation of Problem Representations. in: Proceedings of the Eighth International Symposium on Combinatorial Search (SoCS-2015). AAAI Press, 2015 p. 214–215.
• [25] SHOP2 web site, https://sourceforge.net/projects/shop/, Accessed June 16, 2016.
• [26] Ole Tange. GNU Parallel - The Command-Line Power Tool, The USENIX Magazine 2011;36(1):42–47. Available from: 105438-Tange.pdf.
• [27] TLPlan web site, http://www.cs.toronto.edu/tlplan/, Accessed April 5, 2015.
• [28] Alvaro Torralba, Vidal Alcazar, and Daniel Borrajo. SymBA*: A symbolic bidirectional a planner. in: The 2014 International Planning Competition, 2014 p. 105–109.
• [29] Mauro Vallati, Lukáš Chrpa, Marek Grześ, Thomas Leo McCluskey, Mark Roberts, Scott Sanner. The 2014 International Planning Competition: Progress and Trends, AI Magazine 2015;36(3):90–98. Available from: http://dx.doi.org/10.1609/aimag.v36i3.2571.
• [30] Neng-Fa Zhou and Christian Theil Have. Efficient tabling of structured data with enhanced hash-consing. Theory and Practice of Logic Programming, 2012;12(4-5):547–563. doi:10.1017/S1471068412000178.
• [31] Neng-Fa Zhou and Agostino Dovier. A tabled Prolog program for solving Sokoban. Fundamenta Informaticae, 2013;124(4):561–575. doi:10.3233/FI-2013-849.
• [32] Neng-Fa Zhou, T. Sato, and Y.-D. Shen. Linear tabling strategies and optimizations. Theory and Practice of Logic Programming, 2008;8(1):81–109. Available from: https://doi.org/10.1017/S147106840700316X.
• [33] Neng-Fa Zhou, Y. Kameya, and T. Sato. Mode-directed tabling for dynamic programming, machine learning, and constraint solving. in: Proceedings of 22nd IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 2010 p. 213–218. doi:10.1109/ICTAI.2010.103.
• [34] Neng-Fa Zhou. Combinatorial Search With Picat. 2014. Available from: http://arxiv.org/abs/1405.2538.
• [35] Neng-Fa Zhou, Roman Barták, Agostino Dovier. Planning as Tabled Logic Programming. Theory and Practice of Logic Programming, 2015;15(4-5):543–558. Available from: https://doi.org/10.1017/S1471068415000216.
• [36] Neng-Fa Zhou, Håkan Kjellerstrand, and Jonathan Fruhman. Constraint Solving and Planning with Picat. Springer, 2015. ISBN:978-3-319-25881-2.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).