LinGraph: a graph-based automated planner for concurrent task planning based on linear logic

Date

2017-10-01

Author

Kortik, Sitar
Saranlı, Uluç

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

270
views

0
downloads

In this paper, we introduce an automated planner for deterministic, concurrent domains, formulated as a graph-based theorem prover for a propositional fragment of intuitionistic linear logic, relying on the previously established connection between intuitionistic linear logic and planning problems. The new graph-based theorem prover we introduce improves planning performance by reducing proof permutations that are irrelevant to planning problems particularly in the presence of large numbers of objects and agents with identical properties (e.g. robots within a swarm, or parts in a large factory). We first present our graph-based automated planner, the Linear Logic Graph Planner (LinGraph). Subsequently we illustrate its application for planning within a concurrent manufacturing domain and provide comparisons with four existing automated planners, BlackBox, Symba-2, Metis and the Temporal Fast Downward (TFD), covering a wide range of state-of-the-art automated planning techniques and implementations. We show that even though LinGraph does not rely on any heuristics, it still outperforms these systems for concurrent domains with large numbers of identical objects and agents. These gains persist even when existing methods on symmetry reduction and numerical fluents are used, with LinGraph capable of handling problems with thousands of objects. Following these results, we also show that plan construction with LinGraph is equivalent to multiset rewriting systems, formally relating LinGraph to intuitionistic linear logic.

Subject Keywords

Artificial Intelligence

URI

https://hdl.handle.net/11511/38671

Journal

APPLIED INTELLIGENCE

DOI

https://doi.org/10.1007/s10489-017-0936-x

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

Improving reinforcement learning by using sequence trees Girgin, Sertan; Polat, Faruk; Alhajj, Reda (Springer Science and Business Media LLC, 2010-12-01) This paper proposes a novel approach to discover options in the form of stochastic conditionally terminating sequences; it shows how such sequences can be integrated into the reinforcement learning framework to improve the learning performance. The method utilizes stored histories of possible optimal policies and constructs a specialized tree structure during the learning process. The constructed tree facilitates the process of identifying frequently used action sequences together with states that are visit...
Multi-objective multi-item fixed-charge solid transportation problem under twofold uncertainty Roy, Sankar Kumar; Midya, Sudipta; Weber, Gerhard Wilhelm (Springer Science and Business Media LLC, 2019-12-01) In this paper, we investigate a multi-objective multi-item fixed-charge solid transportation problem (MOMIFCSTP) with fuzzy-rough variables as coefficients of the objective functions and of the constraints. The main focus of the paper is to analyze MOMIFCSTP under a fuzzy-rough environment for a transporting system. In practical situations, the parameters of a MOMIFCSTP are imprecise in nature, due to several uncontrollable factors. For these reasons, we introduce the fuzzy-rough variables in MOMIFCSTP to t...
Stable controller design for T-S fuzzy systems based on Lie algebras Banks, SP; Gurkan, E; Erkmen, İsmet (Elsevier BV, 2005-12-01) In this paper, we study the stability of fuzzy control systems of Takagi-Sugeno-(T-S) type based on the classical theory of Lie algebras. T-S fuzzy systems are used to model nonlinear systems as a set of rules with consequents of the type x(t) = A(l)x (t) + B(l)u (t). We conduct the stability analysis of such T-S fuzzy models using the Lie algebra LA generated by the A(l) matrices of these subsystems for each rule in the rule base. We first develop our approach of stability analysis for a commuting algebra ...
RTTES: Real-time search in dynamic environments Undeger, Cagatay; Polat, Faruk (Springer Science and Business Media LLC, 2007-10-01) In this paper we propose a real-time search algorithm called Real-Time Target Evaluation Search (RTTES) for the problem of searching a route in grid worlds from a starting point to a static or dynamic target point in real-time. The algorithm makes use of a new effective heuristic method which utilizes environmental information to successfully find solution paths to the target in dynamic and partially observable environments. The method requires analysis of nearby obstacles to determine closed directions and...
Two approaches for collective learning with language games Gülçehre, Çağlar; Bozşahin, Hüseyin Cem; Department of Cognitive Sciences (2011) This thesis presents a defense of the view that externalism cannot be a theoretical basis of a mentalistic causal-explanatory science, even though such a theoretical basis is implicitly or explicitly adopted by many cognitive scientists. Externalism is a theory in philosophy of mind which states that mental properties are relations between the core realizers of an individual’s mental states (such as brain states) and certain things that exist outside those realizers (such as what the content of a mental sta...

Citation Formats

S. Kortik and U. Saranlı, “LinGraph: a graph-based automated planner for concurrent task planning based on linear logic,” APPLIED INTELLIGENCE, pp. 914–934, 2017, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/38671.