-
Generating consistent PDDL domains with Large Language Models
Authors:
Pavel Smirnov,
Frank Joublin,
Antonello Ceravola,
Michael Gienger
Abstract:
Large Language Models (LLMs) are capable of transforming natural language domain descriptions into plausibly looking PDDL markup. However, ensuring that actions are consistent within domains still remains a challenging task. In this paper we present a novel concept to significantly improve the quality of LLM-generated PDDL models by performing automated consistency checking during the generation p…
▽ More
Large Language Models (LLMs) are capable of transforming natural language domain descriptions into plausibly looking PDDL markup. However, ensuring that actions are consistent within domains still remains a challenging task. In this paper we present a novel concept to significantly improve the quality of LLM-generated PDDL models by performing automated consistency checking during the generation process. Although the proposed consistency checking strategies still can't guarantee absolute correctness of generated models, they can serve as valuable source of feedback reducing the amount of correction efforts expected from a human in the loop. We demonstrate the capabilities of our error detection approach on a number of classical and custom planning domains (logistics, gripper, tyreworld, household, pizza).
△ Less
Submitted 11 April, 2024;
originally announced April 2024.
-
CoPAL: Corrective Planning of Robot Actions with Large Language Models
Authors:
Frank Joublin,
Antonello Ceravola,
Pavel Smirnov,
Felix Ocker,
Joerg Deigmoeller,
Anna Belardinelli,
Chao Wang,
Stephan Hasler,
Daniel Tanneberg,
Michael Gienger
Abstract:
In the pursuit of fully autonomous robotic systems capable of taking over tasks traditionally performed by humans, the complexity of open-world environments poses a considerable challenge. Addressing this imperative, this study contributes to the field of Large Language Models (LLMs) applied to task and motion planning for robots. We propose a system architecture that orchestrates a seamless inter…
▽ More
In the pursuit of fully autonomous robotic systems capable of taking over tasks traditionally performed by humans, the complexity of open-world environments poses a considerable challenge. Addressing this imperative, this study contributes to the field of Large Language Models (LLMs) applied to task and motion planning for robots. We propose a system architecture that orchestrates a seamless interplay between multiple cognitive levels, encompassing reasoning, planning, and motion generation. At its core lies a novel replanning strategy that handles physically grounded, logical, and semantic errors in the generated plans. We demonstrate the efficacy of the proposed feedback architecture, particularly its impact on executability, correctness, and time complexity via empirical evaluation in the context of a simulation and two intricate real-world scenarios: blocks world, barman and pizza preparation.
△ Less
Submitted 11 October, 2023;
originally announced October 2023.
-
FastCPH: Efficient Survival Analysis for Neural Networks
Authors:
Xuelin Yang,
Louis Abraham,
Sejin Kim,
Petr Smirnov,
Feng Ruan,
Benjamin Haibe-Kains,
Robert Tibshirani
Abstract:
The Cox proportional hazards model is a canonical method in survival analysis for prediction of the life expectancy of a patient given clinical or genetic covariates -- it is a linear model in its original form. In recent years, several methods have been proposed to generalize the Cox model to neural networks, but none of these are both numerically correct and computationally efficient. We propose…
▽ More
The Cox proportional hazards model is a canonical method in survival analysis for prediction of the life expectancy of a patient given clinical or genetic covariates -- it is a linear model in its original form. In recent years, several methods have been proposed to generalize the Cox model to neural networks, but none of these are both numerically correct and computationally efficient. We propose FastCPH, a new method that runs in linear time and supports both the standard Breslow and Efron methods for tied events. We also demonstrate the performance of FastCPH combined with LassoNet, a neural network that provides interpretability through feature sparsity, on survival datasets. The final procedure is efficient, selects useful covariates and outperforms existing CoxPH approaches.
△ Less
Submitted 20 August, 2022;
originally announced August 2022.
-
On data reduction for dynamic vector bin packing
Authors:
René van Bevern,
Andrey Melnikov,
Pavel Smirnov,
Oxana Tsidulko
Abstract:
We study a dynamic vector bin packing (DVBP) problem. We show hardness for shrinking arbitrary DVBP instances to size polynomial in the number of request types or in the maximal number of requests overlapping in time. We also present a simple polynomial-time data reduction algorithm that allows to recover $(1 + {\varepsilon})$-approximate solutions for arbitrary ${\varepsilon} > 0$. It shrinks ins…
▽ More
We study a dynamic vector bin packing (DVBP) problem. We show hardness for shrinking arbitrary DVBP instances to size polynomial in the number of request types or in the maximal number of requests overlapping in time. We also present a simple polynomial-time data reduction algorithm that allows to recover $(1 + {\varepsilon})$-approximate solutions for arbitrary ${\varepsilon} > 0$. It shrinks instances from Microsoft Azure and Huawei Cloud by an order of magnitude for ${\varepsilon} = 0.02$.
△ Less
Submitted 6 July, 2023; v1 submitted 18 May, 2022;
originally announced May 2022.
-
Serial and parallel kernelization of Multiple Hitting Set parameterized by the Dilworth number, implemented on the GPU
Authors:
René van Bevern,
Artem M. Kirilin,
Daniel A. Skachkov,
Pavel V. Smirnov,
Oxana Yu. Tsidulko
Abstract:
The NP-hard Multiple Hitting Set problem is finding a minimum-cardinality set intersecting each of the sets in a given input collection a given number of times. Generalizing a well-known data reduction algorithm due to Weihe, we show a problem kernel for Multiple Hitting Set parameterized by the Dilworth number, a graph parameter introduced by Foldes and Hammer in 1978 yet seemingly so far unexplo…
▽ More
The NP-hard Multiple Hitting Set problem is finding a minimum-cardinality set intersecting each of the sets in a given input collection a given number of times. Generalizing a well-known data reduction algorithm due to Weihe, we show a problem kernel for Multiple Hitting Set parameterized by the Dilworth number, a graph parameter introduced by Foldes and Hammer in 1978 yet seemingly so far unexplored in the context of parameterized complexity theory. Using matrix multiplication, we speed up the algorithm to quadratic sequential time and logarithmic parallel time. We experimentally evaluate our algorithms. By implementing our algorithm on GPUs, we show the feasability of realizing kernelization algorithms on SIMD (Single Instruction, Multiple Date) architectures.
△ Less
Submitted 8 July, 2023; v1 submitted 13 September, 2021;
originally announced September 2021.
-
Smart Home Crawler: Towards a framework for semi-automatic IoT sensor integration
Authors:
Martin Strohbach,
Luis Adan Saavedra,
Pavel Smirnov,
Stefaniia Legostaieva
Abstract:
Sensor deployments in Smart Homes have long reached commercial relevance for applications such as home automation, home safety or energy consumption awareness and reduction. Nevertheless, due to the heterogeneity of sensor devices and gateways, data integration is still a costly and timeconsuming process. In this paper we propose the Smart Home Crawler Framework that (1) provides a common semantic…
▽ More
Sensor deployments in Smart Homes have long reached commercial relevance for applications such as home automation, home safety or energy consumption awareness and reduction. Nevertheless, due to the heterogeneity of sensor devices and gateways, data integration is still a costly and timeconsuming process. In this paper we propose the Smart Home Crawler Framework that (1) provides a common semantic abstraction from the underlying sensor and gateway technologies, and (2) accelerates the integration of new devices by applying machine learning techniques for linking discovered devices to a semantic data model. We present a first prototype that was demonstrated at ICT 2018. The prototype was built as a domainspecific crawling component for IoTCrawler, a secure and privacy-preserving search engine for the Internet of Things.
△ Less
Submitted 16 April, 2021;
originally announced April 2021.
-
Optimal-size problem kernels for $d$-Hitting Set in linear time and space
Authors:
René van Bevern,
Pavel V. Smirnov
Abstract:
The known linear-time kernelizations for $d$-Hitting Set guarantee linear worst-case running times using a quadratic-size data structure (that is not fully initialized). Getting rid of this data structure, we show that problem kernels of asymptotically optimal size $O(k^d)$ for $d$-Hitting Set are computable in linear time and space. Additionally, we experimentally compare the linear-time kerneliz…
▽ More
The known linear-time kernelizations for $d$-Hitting Set guarantee linear worst-case running times using a quadratic-size data structure (that is not fully initialized). Getting rid of this data structure, we show that problem kernels of asymptotically optimal size $O(k^d)$ for $d$-Hitting Set are computable in linear time and space. Additionally, we experimentally compare the linear-time kernelizations for $d$-Hitting Set to each other and to a classical data reduction algorithm due to Weihe.
△ Less
Submitted 4 June, 2020; v1 submitted 10 March, 2020;
originally announced March 2020.
-
Reducing Adversarial Example Transferability Using Gradient Regularization
Authors:
George Adam,
Petr Smirnov,
Benjamin Haibe-Kains,
Anna Goldenberg
Abstract:
Deep learning algorithms have increasingly been shown to lack robustness to simple adversarial examples (AdvX). An equally troubling observation is that these adversarial examples transfer between different architectures trained on different datasets. We investigate the transferability of adversarial examples between models using the angle between the input-output Jacobians of different models. To…
▽ More
Deep learning algorithms have increasingly been shown to lack robustness to simple adversarial examples (AdvX). An equally troubling observation is that these adversarial examples transfer between different architectures trained on different datasets. We investigate the transferability of adversarial examples between models using the angle between the input-output Jacobians of different models. To demonstrate the relevance of this approach, we perform case studies that involve jointly training pairs of models. These case studies empirically justify the theoretical intuitions for why the angle between gradients is a fundamental quantity in AdvX transferability. Furthermore, we consider the asymmetry of AdvX transferability between two models of the same architecture and explain it in terms of differences in gradient norms between the models. Lastly, we provide a simple modification to existing training setups that reduces transferability of adversarial examples between pairs of models.
△ Less
Submitted 16 April, 2019;
originally announced April 2019.
-
Stochastic Combinatorial Ensembles for Defending Against Adversarial Examples
Authors:
George A. Adam,
Petr Smirnov,
David Duvenaud,
Benjamin Haibe-Kains,
Anna Goldenberg
Abstract:
Many deep learning algorithms can be easily fooled with simple adversarial examples. To address the limitations of existing defenses, we devised a probabilistic framework that can generate an exponentially large ensemble of models from a single model with just a linear cost. This framework takes advantage of neural network depth and stochastically decides whether or not to insert noise removal ope…
▽ More
Many deep learning algorithms can be easily fooled with simple adversarial examples. To address the limitations of existing defenses, we devised a probabilistic framework that can generate an exponentially large ensemble of models from a single model with just a linear cost. This framework takes advantage of neural network depth and stochastically decides whether or not to insert noise removal operators such as VAEs between layers. We show empirically the important role that model gradients have when it comes to determining transferability of adversarial examples, and take advantage of this result to demonstrate that it is possible to train models with limited adversarial attack transferability. Additionally, we propose a detection method based on metric learning in order to detect adversarial examples that have no hope of being cleaned of maliciously engineered noise.
△ Less
Submitted 8 September, 2018; v1 submitted 20 August, 2018;
originally announced August 2018.
-
Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
Authors:
Matthias Bentert,
René van Bevern,
André Nichterlein,
Rolf Niedermeier,
Pavel V. Smirnov
Abstract:
We study an NP-hard problem motivated by energy-efficiently maintaining the connectivity of a symmetric wireless communication network: Given an edge-weighted $n$-vertex graph, find a connected spanning subgraph of minimum cost, where the cost is determined by letting each vertex pay the most expensive edge incident to it in the subgraph. On the negative side, we show that $o(\log n)$-approximatin…
▽ More
We study an NP-hard problem motivated by energy-efficiently maintaining the connectivity of a symmetric wireless communication network: Given an edge-weighted $n$-vertex graph, find a connected spanning subgraph of minimum cost, where the cost is determined by letting each vertex pay the most expensive edge incident to it in the subgraph. On the negative side, we show that $o(\log n)$-approximating the difference $d$ between the optimal solution cost and a natural lower bound is NP-hard and that, under the Exponential Time Hypothesis, there are no exact algorithms running in $2^{o(n)}$ time or in $f(d)\cdot n^{O(1)}$ time for any computable function $f$. Moreover, we show that the special case of connecting $c$ network components with minimum additional cost generally cannot be polynomial-time reduced to instances of size $c^{O(1)}$ unless the polynomial-time hierarchy collapses. On the positive side, we provide an algorithm that reconnects $O(\log n)$ connected components with minimum additional cost in polynomial time. These algorithms are motivated by application scenarios of monitoring areas or where an existing sensor network may fall apart into several connected components due to sensor faults. In experiments, the algorithm outperforms CPLEX with known ILP formulations when $n$ is sufficiently large compared to $c$.
△ Less
Submitted 3 September, 2020; v1 submitted 9 June, 2017;
originally announced June 2017.
-
Computer-assisted workflows composition based on Virtual Simulation Objects technology
Authors:
Pavel A. Smirnov,
Sergey V. Kovalchuk,
Alexander V. Boukhanovsky
Abstract:
The existing approaches for scientific workflows composition face the problems of domain knowledge integration. By this paper we summarize the results, which have been elaborated and implemented during the 2-year research concerning to Virtual Simulation Objects (VSO) concept and technology development. The contribution of this paper consists of formal models of the VSO internal structures and use…
▽ More
The existing approaches for scientific workflows composition face the problems of domain knowledge integration. By this paper we summarize the results, which have been elaborated and implemented during the 2-year research concerning to Virtual Simulation Objects (VSO) concept and technology development. The contribution of this paper consists of formal models of the VSO internal structures and user-assistance logic, which may be obtained as a result of the reasoning over knowledge base. (This paper was rejected to appear in "Recent Advances in Knowledge Based Technologies and Applications" by Hindawi in 2014, but was stolen and published by Ke Han under the name "The Study on Workflows Composition Based on Virtual Simulation Objects Technology")
△ Less
Submitted 27 June, 2016;
originally announced June 2016.
-
Knowledge-based Expressive Technologies within Cloud Computing Environments
Authors:
Sergey V. Kovalchuk,
Pavel A. Smirnov,
Konstantin V. Knyazkov,
Alexander S. Zagarskikh,
Alexander V. Boukhanovsky
Abstract:
Presented paper describes the development of comprehensive approach for knowledge processing within e-Sceince tasks. Considering the task solving within a simulation-driven approach a set of knowledge-based procedures for task definition and composite application processing can be identified. This procedures could be supported by the use of domain-specific knowledge being formalized and used for a…
▽ More
Presented paper describes the development of comprehensive approach for knowledge processing within e-Sceince tasks. Considering the task solving within a simulation-driven approach a set of knowledge-based procedures for task definition and composite application processing can be identified. This procedures could be supported by the use of domain-specific knowledge being formalized and used for automation purpose. Within this work the developed conceptual and technological knowledge-based toolbox for complex multidisciplinary task solv-ing support is proposed. Using CLAVIRE cloud computing environment as a core platform a set of interconnected expressive technologies were developed.
△ Less
Submitted 30 December, 2013;
originally announced December 2013.
-
Virtual Simulation Objects Concept as a Framework for System-Level Simulation
Authors:
Sergey V. Kovalchuk,
Pavel A. Smirnov,
Sergey S. Kosukhin,
Alexander V. Boukhanovsky
Abstract:
This paper presents Virtual Simulation Objects (VSO) concept which forms theoretical basis for building tools and framework that is developed for system-level simulations using existing software modules available within cyber-infrastructure. Presented concept is implemented by the software tool for building composite solutions using VSO-based GUI and running them using CLAVIRE simulation environme…
▽ More
This paper presents Virtual Simulation Objects (VSO) concept which forms theoretical basis for building tools and framework that is developed for system-level simulations using existing software modules available within cyber-infrastructure. Presented concept is implemented by the software tool for building composite solutions using VSO-based GUI and running them using CLAVIRE simulation environment.
△ Less
Submitted 29 November, 2012;
originally announced November 2012.
