Practical Aspects of Declarative Languages

While recent advances in machine learning have yielded impressive results, researchers, practitioners, and even companies are beginning to recognize that true artificial intelligence requires much more sophisticated reasoning capabilities. Knowledge representation and declarative programming are arguably in a premier position to aid in the achievement of such capabilities. In this paper, I reflect on people and ideas that have had a great influence on my view of knowledge representation and of declarative programming. Through these lenses, I will discuss what I consider to be some of the most important milestones in the evolution of the field over the past years. I will conclude my reflection with my take on what this may tell us about the path that lies ahead and about areas where research efforts may yield considerable benefits.

Motivated by autonomous warehouse applications in the real world, we study a variant of Multi-Agent Path Finding (MAPF) problem where robots also need to pick and deliver some items on their way to their destination. We call this variant the Multi-Agent Pick and Delivery with Capacities (MAPDC) problem. In addition to the challenges of MAPF (i.e., finding collision-free plans for each robot from an initial location to a destination while minimizing the maximum makespan), MAPDC asks also for the allocation of the pick and deliver tasks among robots while taking into account their capacities (i.e., the maximum number of items one robot can carry at a time). We study this problem with two different approaches, action planning vs path finding, using Answer Set Programming with two different computation modes, single-shot vs multi-shot.

In the field of automated planning, an action is called reversible when other actions can be applied in order to revert the effects of this action and return to the original state. In recent years, there has been renewed interest in this topic, which led to novel results in the widely known STRIPS formalism and the PDDL planning language.

In this paper, we aim to solve the computational problem of deciding action reversibility in a practical setting, applying recent advances in the field of logic programming. In particular, a quantified extension of Answer Set Programming (ASP) named ASP with Quantifiers (ASP(Q)) has been proposed by Amendola, Ricca, and Truszczynski, which allows for stacking logic programs by quantifying over answer sets of the previous layer. This language is well-suited to express encodings for the action reversibility problem, since this problem naturally contains a quantifier alternation. In addition, a prototype solver for ASP(Q) is currently developed. We make use of the ASP(Q) language to offer an encoding for action reversibility, and then report on preliminary benchmark results on how well this encoding performs compared to classical ASP.

Dataflow applications, such as machine learning algorithms, can run for days, making it desirable to have assurances that they will work correctly. Current tools are not good enough: too often the interactions between tasks are not type-safe, leading to undesirable runtime errors. This paper presents a new declarative Haskell Embedded DSL (eDSL) for dataflow programming: \(\textsf {CircuitFlow}\). Defined as a Symmetric Monoidal Preorder (SMP) on data that models dependencies in the workflow, it has a strong mathematical basis, refocusing on how data flows through an application, resulting in a more expressive solution that not only catches errors statically, but also achieves competitive run-time performance. In our preliminary evaluation, \(\textsf {CircuitFlow}\) outperforms the industry-leading Luigi library of Spotify by scaling better with the number of inputs. The innovative creation of \(\textsf {CircuitFlow}\) is also of note, exemplifying how to create a modular eDSL whose semantics necessitates effects, and where storing complex type information for program correctness is paramount.

Time is a crucial factor in modelling dynamic behaviours of intelligent agents: in a real-world environment, activities have a determined temporal duration and the behaviour of agents is influenced by the actions previously taken. In this paper, we propose a language for modelling concurrent interaction between agents that also allows the specification of temporal intervals in which particular actions occur. Such a language exploits a timed version of Abstract Argumentation Frameworks to realise a shared memory used by the agents both to communicate and to reason on the acceptability of their beliefs with respect to a given time interval. An interleaving model on a single processor is used for basic computation steps (with maximal parallelism for time elapsing). Following this approach, at each moment only one of the enabled agents is executed.

Goal-directed evaluation of Answer Set Programs is gaining traction thanks to its amenability to create AI systems that can, due to the evaluation mechanism used, generate explanations and justifications. s(CASP) is one of these systems and has been already used to write reasoning systems in several fields. It provides enhanced expressiveness w.r.t. other ASP systems due to its ability to use constraints, data structures, and unbound variables natively. However, the performance of existing s(CASP) implementations is not on par with other ASP systems: model consistency is checked once models have been generated, in keeping with the generate-and-test paradigm. In this work, we present a variation of the top-down evaluation strategy, termed Dynamic Consistency Checking, which interleaves model generation and consistency checking. This makes it possible to determine when a literal is not compatible with the denials associated to the global constraints in the program, prune the current execution branch, and choose a different alternative. This strategy is specially (but not exclusively) relevant in problems with a high combinatorial component. We have experimentally observed speedups of up to 90\(\times \) w.r.t. the standard versions of s(CASP).

Normal logic programs subject to stable model semantics cover reasoning problems from the first level of polynomial time hierarchy (PH) in a natural way. Disjunctive programs reach one level beyond this, but the access to the underlying NP oracle(s) is somewhat implicit and available for the programmer using the so-called saturation technique. To address this shortcoming, stable-unstable semantics was proposed, making oracles explicit as subprograms having no stable models. If this idea is applied recursively, any level of PH can be reached with normal programs only, in analogy to quantified Boolean formulas (QBFs). However, for the moment, no native implementations of stable-unstable semantics have emerged except via translations toward QBFs. In this work, we alleviate this situation with a translation of (effectively) normal programs that combines a main program with any fixed number of oracles subject to stable-unstable semantics. The result is a disjunctive program that can be fed as input for answer set solvers supporting disjunctive programs. The idea is to hide saturation from the programmer altogether, although it is exploited by the translation internally. The translation of oracles is performed using translators and linkers from the ASPTOOLS collection while Clingo is used as the back-end solver.

In the last few years, we have been witnessing the spread of computing devices getting smaller and smaller (e.g., Smartphones, Smart Devices, Raspberry, etc.), and the production and availability of data getting bigger and bigger. In this work we introduce DLV Large Scale (DLV-LS), a framework based on Answer Set Programming (ASP) for performing declarative-based reasoning tasks over data-intensive applications, possibly on Smart Devices. The framework encompasses DLV Mobile Edition (DLV-ME), an ASP based solver for Android systems and Raspberry devices, and DLV Enterprise Edition (DLV-EE), an ASP-based platform, accessible by REST interfaces, for large-scale reasoning over Big Data, classical relational database systems, and NoSQL databases. DLV-LS enables Smart Devices to both locally perform reasoning over data generated by their own sensors and properly interact with DLV-EE when more computational power is needed for harder tasks, possibly over bigger centralized data. We present also a real-world application of DLV-LS; the use case consists of a tourist navigator that calculates the best routes and optimizes a tour of a tourist under custom-defined time constraints.

Scheduling is a crucial problem appearing in various domains, such as manufacturing, transportation, or healthcare, where the goal is to schedule given operations on available resources such that the operations are completed as soon as possible. Unfortunately, most scheduling problems cannot be solved efficiently, so that research on suitable approximation methods is of primary importance. This work introduces a novel approximation approach based on problem decomposition with data mining methodologies. We propose a constrained clustering algorithm to group operations into clusters, corresponding to time windows in which the operations must be scheduled. The decomposition process consists of two main phases. First, features are extracted, either from the problem itself or from solutions obtained by heuristic methods, to predict the execution sequence of operations on each resource. The second phase deploys our constrained clustering algorithm to assign each operation into a time window. We then schedule the operations by time windows using Answer Set Programming. Evaluation results show that our proposed approach outperforms other heuristic schedulers in most cases, where incorporating features like Remaining Processing Time, Machine Load, and Earliest Starting Time significantly improves the solution quality.

Modeling a cyber-physical system’s requirement specifications makes it possible to verify its properties w.r.t. the expected behavior. Standard modeling approaches based on automata theory model these systems at the system architecture level, as they have to explicitly encode the notion of states and define explicit transitions between these states. Event Calculus encoding using Answer Set Programming (ASP) allows for elegant and succinct modeling of these dynamic systems at the requirements specification level, thanks to the near-zero semantics gap between the system’s requirement specifications and the Event Calculus encoding. In this work we propose a framework that uses the EARS notation to describe the system requirements, and an Event Calculus reasoner based on s(CASP), a goal-directed Constraint Answer Set Programming reasoner over the rationals/reals, to directly model these requirements. We evaluate our proposal by (i) modeling the well-known Train-Gate-Controller system, a railroad crossing problem, using the EARS notation and Event Calculus, (ii) translating the specifications into s(CASP), and (iii) checking safety and liveness of the system.

This paper explores the opportunities that the transitional semantics of Multi-valued Decision Diagrams (MDDs) offers in terms of modeling and efficiency. The paper explores the combination of MDDs with Large Neighborhood Search (LNS), as an effective local search strategy. The paper also demonstrates the use of GPU-based parallelism to enhance efficiency in the exploration of the search space. The paper describes the integration of these techniques within a solver, focused on a time-bounded search for high-quality solutions. The solver is evaluated on several classes of benchmarks, with positive outcomes in terms of time and solution quality compared to state-of-the-art constraint-based solvers.

Green software engineering aims at reducing the environmental impact due to developing, deploying, and managing software systems. Meanwhile, Cloud-IoT paradigms can contribute to improving energy and carbon efficiency of application deployments by (i) reducing the amount of data and the distance they must travel across the network, (ii) by exploiting idle edge devices to support application deployment. In this article, we propose a declarative methodology and its Prolog prototype for determining placements of application services onto Cloud-IoT infrastructures so as to optimise energy and carbon efficiency, also considering different infrastructure power sources and operational costs. The proposal is assessed over a motivating example.