An Experimental Study of Influence of Modeling and Solving Techniques on Performance of a Tabled Logic Programming Planner
Issue title: Special issue of the 22nd RCRA International Workshop on “Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion”
Guest editors: Stefano Bistarelli, Andrea Formisano, Marco Maratea and Paolo Torroni
Affiliations: [a] Charles University, Faculty of Mathematics and Physics Malostranské náměstí 25, 118 00 Praha 1, Czech Republic [email protected], [email protected]
Correspondence:
[*]
Address for correspondence: Roman Barták, Charles University, Faculty of Mathematics and Physics, Malostranské náměstí 25, 118 00 Praha 1, Czech Republic. Supported by the Czech Science Foundation under the project P103-15-19877S.
Note: [†] Supported by the Grant Agency of Charles University under the project No. 241515.
Abstract: 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-ofthe- art.
