1,722,436 research outputs found
AI Planning for Hybrid Systems
No full textWhen planning the tasks of some physical entities that need to perform actions in the world (e.g., a Robot) it is necessary to take into account quite complex models for ensuring that the plan is actually executable. Indeed the state of these systems evolves according to potentially non-linear dynamics where interdependent discrete and continuous changes happen over the entire course of the task. Systems of this kind are typically compactly represented in planning using languages mixing propositional logic and mathematics. However, these languages are still poorly understood and exploited. What are the difficulties for planning in these settings? How can we build systems that can scale up over realistically sized problems? What are the domains which can benefit from these languages? This short paper shows the main two ingredients that are needed to build a heuristic search planner, outline the main impact that such techniques have on application, and provide some open challenges. These models and relative planners hold the promise to deliver explainable AI solutions that do not rely on large amounts of data
On the Compilability of Bounded Numeric Planning
No full textBounded numeric planning, where each numeric variable domain is bounded, is PSPACE-complete, but such a complexity result does not capture how hard it really is, since the same holds even for the practically much easier STRIPS fragment. A finer way to compare the difficulty of planning formalisms is through the notion of compilability, which has been however extensively studied only for classical planning by Nebel. This paper extends Nebel's framework to the setting of bounded numeric planning. First, we identify a variety of numeric fragments differing on the degree of the polynomials involved and the availability of features such as conditional effects and Boolean conditions; then we study the compilability of these fragments to each other and to the classical fragments. Surprisingly, numeric and classical planning with conditional effects and Boolean conditions can be compiled both ways preserving plan size exactly, while the same does not hold when targeting pure STRIPS. Our study reveals also that numeric fragments cluster into two equivalence classes separated by the availability of incomplete initial state specifications, a feature allowing to specify uncertainty in the initial state
Cost-Optimal FOND Planning as Bi-Objective Best-First Search
No full textIn this paper, we tackle the problem of finding cost-optimal solutions in Fully-Observable Non-Deterministic (FOND) planning problems. First, we introduce metrics for FOND problems by interpreting solution policies under both their best and worst possible scenarios, leading to a bi-objective optimization problem. We then propose BOAND*, a novel heuristic search algorithm designed to seek Pareto-optimal solutions by navigating the space of possible policies. We conduct an empirical evaluation of the algorithm, alongside a qualitative comparison with cost-optimal solutions that consider only one objective at a time. Our findings validate this approach, paving the way for new methods of reasoning over FOND problems
Range Proofs with Constant Size and Trustless Setup
No full textRange proofs are widely adopted in practice in many privacy-preserving cryptographic protocols in the public blockchain. The performances known in the literature for range proofs are logarithmic-sized proofs and linear verification time. In contexts where the proof verification is left to the ledger maintainers and proofs are stored in blocks, one might expect higher transaction fees and blockchain space when the size of the relation over the proof grows. With this paper, we improve Bulletproofs, a zero-knowledge argument of knowledge for range proofs, by modifying its Inner Product Argument (IPA) subroutine. In particular, we adopt a new relation from the polynomial commitment scheme of Halo, based on standard groups and assumptions (DLOG and RO) with a trustless setup. We design a two-step reduction algorithm and we obtain a constant number of two rounds in the IPA and a constant-sized proof composed of 5 G1 points and 2 Zp scalars
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Optimised Variants of Polynomial Compilation for Conditional Effects in Classical Planning
No full textConditional effects are a key feature in classical planning, enabling the description of actions whose outcomes are statedependent. It is well known that removing conditional effects in a polynomial way necessarily increases the size of a valid plan by a polynomial factor. However, preserving the exact plan size requires encoding the problem exponentially. The paper proposes and empirically evaluates optimisations for existing polynomial compilations. These optimisations aim to make the resulting compilations more suitable for planners while limiting the increase in plan size, which is inevitable if we want to keep the compilation polynomial. Specifically, the paper introduces a polynomial compilation technique that expands conditional effects when their number is below a certain threshold and sequentialises them otherwise. Additionally, the paper demonstrates that even straightforward optimisations can have a notable impact
- …
