Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-09T23:02:33.552Z Has data issue: false hasContentIssue false
  • English
  • Français

Using Tabled Logic Programming to Solve the Petrobras Planning Problem

Published online by Cambridge University Press:  21 July 2014

ROMAN BARTÁK  and
NENG-FA ZHOU
ROMAN BARTÁK
Affiliation:
Charles University in Prague, Faculty of Mathematics and Physics, Prague, Czech Republic (e-mail: bartak@ktiml.mff.cuni.cz)
NENG-FA ZHOU
Affiliation:
The City University of New York, Brooklyn College, New York, USA (e-mail: nzhou@acm.org)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Tabling has been used for some time to improve efficiency of Prolog programs by memorizing answered queries. The same idea can be naturally used to memorize visited states during search for planning. In this paper we present a planner developed in the Picat language to solve the Petrobras planning problem. Picat is a novel Prolog-like language that provides pattern matching, deterministic and non-deterministic rules, and tabling as its core modelling and solving features. We demonstrate these capabilities using the Petrobras problem, where the goal is to plan transport of cargo items from ports to platforms using vessels with limited capacity. Monte Carlo Tree Search has been so far the best technique to tackle this problem and we will show that by using tabling we can achieve much better runtime efficiency and better plan quality.

Keywords

tablingresource-bounded searchsymmetry breakingplanninglogistics

Information

Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 14 , Special Issue 4-5: 30th International Conference on Logic Programming , July 2014 , pp. 697 - 710
Copyright
Copyright © Cambridge University Press 2014 

References

B-Prolog, http://www.probp.com Google Scholar
International Planning Competitions, http://ipc.icaps-conference.org Google Scholar
Picat, http://www.picat-lang.org Google Scholar
Barták, R. and Zhou, N.F. (2013), On Modeling Planning Problems: Experience From The Petrobras Challenge. Proceedings of MICAI 2013, Part II, LNAI 8266, pp. 466–477, Springer Verlag.Google Scholar
Dvořák, F. and Barták, R. (2010), Integrating time and resources into planning. Proceedings of ICTAI 2010, Volume 2, pp. 71–78, IEEE Computer Society.Google Scholar
Faber, W. (2013), Sokoban. https://www.mat.unical.it/aspcomp2013/Sokoban Google Scholar
Gerevini, A. and Long, D. (2005), BNF description of PDDL 3.0, http://cs-www.cs.yale.edu/homes/dvm/papers/pddl-bnf.pdf Google Scholar
Hewitt, C. (1969), Planner: A language for proving theorems in robots. In IJCAI, 295–302.Google Scholar
Hsu, C. and Wah, B.W. (2008), The SGPlan planning system in IPC-6, http://wah.cse.cuhk.edu.hk/wah/Wah/papers/C168/C168.pdf Google Scholar
Kovacs, D.L. (2011), BNF definition of PDDL 3.1, http://www.plg.inf.uc3m.es/ipc2011-deterministic/OtherContributions?action=AttachFile&do=view&target=kovacs-pddl-3.1-2011.pdf Google Scholar
Nakhost, H. and Hoffmann, J. (2013), Nomystery. https://www.mat.unical.it/aspcomp2013/Nomystery Google Scholar
Toropila, D., Dvořák, F., Trunda, O., Hanes, M., Barták, R. (2012), Three Approaches to Solve the Petrobras Challenge: Exploiting Planning Techniques for Solving Real-Life Logistics Problems. Proceedings of ICTAI 2012, pp. 191–198, IEEE Conference Publishing Services.Google Scholar
Vaquero, T. S., Costa, G., Tonidandel, F., Igreja, H., Silva, J. R. and Beck, C. (2012), Planning and scheduling ship operations on petroleum ports and platform. Proceedings of the Scheduling and Planning Applications Workshop, pp. 8–16.Google Scholar
Warren, D. H. D. (1974), WARPLAN: A system for generating plans. Technical Report DCL Memo 76, University of Edinburgh.Google Scholar
Warren, D.S. (1992), Memoing for Logic Programs, CACM, Vol. 35, No. 3, pp. 93–111.Google Scholar
Zhou, N.-F., Dovier, A. (2011), A Tabled Prolog Program for Solving Sokoban. Proceedings of the 26th Italian Conference on Computational Logic (CILC 2011), pp. 215–228.CrossRefGoogle Scholar