اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدUsing Tabled Logic Programming to Solve the Petrobras Planning Problem
93
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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.
قيم البحث
اقرأ أيضاً
This paper describes Picats planner, its implementation, and planning models for several domains used in International Planning Competition (IPC) 2014. Picats planner is implemented by use of tabling. During search, every state encountered is tabled,
and tabled states are used to effectively perform resource-bounded search. In Picat, structured data can be used to avoid enumerating all possible permutations of objects, and term sharing is used to avoid duplication of common state data. This paper presents several modeling techniques through the example models, ranging from designing state representations to facilitate data sharing and symmetry breaking, encoding actions with operations for efficient precondition checking and state updating, to incorporating domain knowledge and heuristics. Broadly, this paper demonstrates the effectiveness of tabled logic programming for planning, and argues the importance of modeling despite recent significant progress in domain-independent PDDL planners.
We investigate the use of Answer Set Programming to solve variations of gossip problems, by modeling them as epistemic planning problems.
PDDL+ is an extension of PDDL that enables modelling planning domains with mixed discrete-continuous dynamics. In this paper we present a new approach to PDDL+ planning based on Constraint Answer Set Programming (CASP), i.e. ASP rules plus numerical
constraints. To the best of our knowledge, ours is the first attempt to link PDDL+ planning and logic programming. We provide an encoding of PDDL+ models into CASP problems. The encoding can handle non-linear hybrid domains, and represents a solid basis for applying logic programming to PDDL+ planning. As a case study, we consider the EZCSP CASP solver and obtain promising results on a set of PDDL+ benchmark problems.
We present a general approach to planning with incomplete information in Answer Set Programming (ASP). More precisely, we consider the problems of conformant and conditional planning with sensing actions and assumptions. We represent planning problem
s using a simple formalism where logic programs describe the transition function between states, the initial states and the goal states. For solving planning problems, we use Quantified Answer Set Programming (QASP), an extension of ASP with existential and universal quantifiers over atoms that is analogous to Quantified Boolean Formulas (QBFs). We define the language of quantified logic programs and use it to represent the solutions to different variants of conformant and conditional planning. On the practical side, we present a translation-based QASP solver that converts quantified logic programs into QBFs and then executes a QBF solver, and we evaluate experimentally the approach on conformant and conditional planning benchmarks. Under consideration for acceptance in TPLP.
In the generalized Russian cards problem, we have a card deck $X$ of $n$ cards and three participants, Alice, Bob, and Cathy, dealt $a$, $b$, and $c$ cards, respectively. Once the cards are dealt, Alice and Bob wish to privately communicate their han
ds to each other via public announcements, without the advantage of a shared secret or public key infrastructure. Cathy should remain ignorant of all but her own cards after Alice and Bob have made their announcements. Notions for Cathys ignorance in the literature range from Cathy not learning the fate of any individual card with certainty (weak $1$-security) to not gaining any probabilistic advantage in guessing the fate of some set of $delta$ cards (perfect $delta$-security). As we demonstrate, the generalized Russian cards problem has close ties to the field of combinatorial designs, on which we rely heavily, particularly for perfect security notions. Our main result establishes an equivalence between perfectly $delta$-secure strategies and $(c+delta)$-designs on $n$ points with block size $a$, when announcements are chosen uniformly at random from the set of possible announcements. We also provide construction methods and example solutions, including a construction that yields perfect $1$-security against Cathy when $c=2$. We leverage a known combinatorial design to construct a strategy with $a=8$, $b=13$, and $c=3$ that is perfectly $2$-secure. Finally, we consider a variant of the problem that yields solutions that are easy to construct and optimal with respect to both the number of announcements and level of security achieved. Moreover, this is the first method obtaining weak $delta$-security that allows Alice to hold an arbitrary number of cards and Cathy to hold a set of $c = lfloor frac{a-delta}{2} rfloor$ cards. Alternatively, the construction yields solutions for arbitrary $delta$, $c$ and any $a geq delta + 2c$.
الأسئلة المقترحة
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
