CRAFTING THE MIND OF PROSOCS AGENTS

PROSOCS agents are software agents that are built according to the KGP model of agency. KGP is used as a model for the mind of the agent, so that the agent can act autonomously using a collection of logic theories, providing the mind's reasoning functionalities. The behavior of the agent is controlled by a cycle theory that specifies the agent's preferred patterns of operation. The implementation of the mind's generic functionality in PROSOCS is worked out in such a way so it can be instantiated by the platform for different agents across applications. In this context, the development of a concrete example illustrates how an agent developer might program the generic functionality of the mind for a simple application.     

Parameterized algorithmics for d-Hitting Set

Based on the methodology we presented in earlier work on parameterized algorithms for 3-Hitting Set, we develop simple search tree-based algorithms for d-Hitting Set. We considerably improve on the bounds that were elsewhere derived for these problems.     

GpoSolver: a Matlab/C++ toolbox for global polynomial optimization

Global polynomial optimization can be a powerful tool when applied to engineering problems. One of the most successful methods for solving such problems is based on convex linear matrix inequality (LMI) relaxations. Software implementations of this approach can be found for example in Matlab toolboxes GloptiPoly and YALMIP. Matlab language makes it very easy when it comes to modelling polynomial problems. However, when using these toolboxes, Matlab is also required for the problem solving. GpoSolver aims at bridging this gap by providing a Matlab-based problem modelling toolbox supplemented by a problem-solving back end in a form of a C++ template library. Once a problem is conveniently modelled and parametrized in Matlab, a C++ class is automatically generated by GpoSolver. This class can be easily included into an existing codebase and used to solve different instances of the problem based on the supplied parameters.     

Prodigy bidirectional planning

The PRODIGY system is based on bidirectional planning, which is a combination of goal-directed reasoning with simulated execution. Researchers have implemented a series of planners that utilize this search strategy, and demonstrated that it is an efficient technique, a fair match to other successful planners; however, they have provided few formal results on the common principles underlying the developed algorithms. We formalize bidirectional planning, elucidate some techniques for improving its efficiency and show how different strategies for controlling search complexity give rise to different versions of PRODIGY. In particular, we demonstrate that PRODIGY is not complete and discuss advantages and drawbacks of its incompleteness. We then develop a complete bidirectional planner and compare it experimentally with PRODIGY. We show that the complete planner is almost as fast as PRODIGY and solves a wider range of problems.     

SOFTWARE AND PERFORMANCE MEASURES FOR EVALUATING MULTI-AGENT FRAMEWORKS

ABSTRACT

Nowadays, multi-agent frameworks allow to implement very complex systems by means of agent technology. However, this complexity makes it more difficult to evaluate software and runtime characteristics of multiagent systems (MAS). Our aim is to define and study some quantitative measures to measure MAS aspects like development time, reusability, scalability, etc. These measures could be used by engineers to guide the selection among several MAS frameworks. Our study has been carried out in several MAS frameworks like JADE, JATLite, SkeletonAgent, and ZEUS, which have been used to build a MAS application for news retrieval.     

Adaptive augmented Lagrangian methods: algorithms and practical numerical experience

In this paper, we consider augmented Lagrangian (AL) algorithms for solving large-scale nonlinear optimization problems that execute adaptive strategies for updating the penalty parameter. Our work is motivated by the recently proposed adaptive AL trust region method by Curtis et al. [An adaptive augmented Lagrangian method for large-scale constrained optimization, Math. Program. 152 (2015), pp. 201–245.]. The first focal point of this paper is a new variant of the approach that employs a line search rather than a trust region strategy, where a critical algorithmic feature for the line search strategy is the use of convexified piecewise quadratic models of the AL function for computing the search directions. We prove global convergence guarantees for our line search algorithm that are on par with those for the previously proposed trust region method. A second focal point of this paper is the practical performance of the line search and trust region algorithm variants in Matlab software, as well as that of an adaptive penalty parameter updating strategy incorporated into the Lancelot software. We test these methods on problems from the CUTEst and COPS collections, as well as on challenging test problems related to optimal power flow. Our numerical experience suggests that the adaptive algorithms outperform traditional AL methods in terms of efficiency and reliability. As with traditional AL algorithms, the adaptive methods are matrix-free and thus represent a viable option for solving large-scale problems.     

MACHINE LEARNING IN HYBRID HIERARCHICAL AND PARTIAL-ORDER PLANNERS FOR MANUFACTURING DOMAINS

ABSTRACT

The application of AI planning techniques to manufacturing systems is being widely deployed for all the tasks involved in the process, from product design to production planning and control. One of these problems is the automatic generation of control sequences for the entire manufacturing system in such a way that final plans can be directly used as the sequential control programs which drive the operation of manufacturing systems. HYBIS is a hierarchical and nonlinear planner whose goal is to obtain partially ordered plans at such a level of detail that they can be used as sequential control programs for manufacturing systems. Currently, those sequential control programs are being generated by hand using modeling tools. This document describes a work aimed to improve the efficiency of solving problems with HYBIS by using machine learning techniques. It implements a deductive learning method that is able to automatically acquire control knowledge (heuristics) by generating bounded explanations of the problem-solving episodes. The learning approach builds on HAMLET, a system that learns control knowledge in the form of control rules.     

An evolutionary algorithm for abductive reasoning

Abductive reasoning (or abduction) is the process of inferring hypotheses from observed data using a certain ‘knowledge’ encoded in the form of inference rules (or causal relations). Many important kinds of intellectual tasks, including medical diagnosis, fault diagnosis, scientific discovery, legal reasoning, and natural language understanding have been characterised as abduction. Unfortunately, abduction is 𝒩𝒫-hard. Genetic algorithms and biologically motivated computational paradigms inspired by the natural evolution turned out to be efficient in solving many hard problems while other existing approaches failed to solve in general. In this article, we present a genetic algorithm called HAKIM, for solving abduction problems. We encode an explanation in a chromosome-like structure, where every gene models a possible single hypothesis. Thereafter, we develop a fitness function that characterises the overall ‘quality’ of a chromosome representing an explanation; and then use standard genetic operators to compute a set of hypotheses that best explains the observed data. Simulation results on large-scale medical problems reveal the good performance of our model HAKIM.     

An Efficient Scalable Runtime System for Macro Data Flow Processing Using S-Net

S-Net is a declarative coordination language and component technology aimed at radically facilitating software engineering for modern parallel compute systems by near-complete separation of concerns between application (component) engineering and concurrency orchestration. S-Net builds on the concept of stream processing to structure networks of communicating asynchronous components implemented in a conventional (sequential) language. In this paper we present the design, implementation and evaluation of a new and innovative runtime system for S-Net streaming networks. The Front runtime system outperforms the existing implementations of S-Net by orders of magnitude for stress-test benchmarks, significantly reduces runtimes of fully-fledged parallel applications with compute-intensive components and achieves good scalability on our 48-core test system.     

On logical universality of Belousov-Zhabotinsky vesicles

Belousov-Zhabotinsky (BZ) excitable chemical medium exhibits a rich variety of spatial patterns of excitation. In a sub-excitable light-sensitive chemical medium, an asymmetric disturbing or excitation, causes formation of localized travelling excitation wave-fragments. When two or more wave-fragments collide, they annihilate or merge into new wave-fragment. The wave-fragments can be thought as elementary units of information and their interaction sites as a logical gates. Size and life span of a wave-fragment depends on a level of medium’s illumination. By encapsulating BZ reaction into a lipid vesicle, we can manipulate the BZ-derived logical gates. By interpreting wave-fragments as values of Boolean variables, we design a collision-based polymorphic logical gate in BZ vesicles. The gate implements operation xnor for low illumination, and it acts as nor gate for high illumination.     

Hard constraint satisfaction problems have hard gaps at location 1

An instance of the maximum constraint satisfaction problem (Max CSP) is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constraints. Max CSP captures many well-known problems (such as Maxk-SAT and Max Cut) and is consequently NP-hard. Thus, it is natural to study how restrictions on the allowed constraint types (or constraint language) affect the complexity and approximability of Max CSP. The PCP theorem is equivalent to the existence of a constraint language for which Max CSP has a hard gap at location 1; i.e. it is NP-hard to distinguish between satisfiable instances and instances where at most some constant fraction of the constraints are satisfiable. All constraint languages, for which the CSP problem (i.e., the problem of deciding whether all constraints can be satisfied) is currently known to be NP-hard, have a certain algebraic property. We prove that any constraint language with this algebraic property makes Max CSP have a hard gap at location 1 which, in particular, implies that such problems cannot have a PTAS unless P=NP. We then apply this result to Max CSP restricted to a single constraint type; this class of problems contains, for instance, Max Cut and Max DiCut. Assuming P≠NP, we show that such problems do not admit PTAS except in some trivial cases. Our results hold even if the number of occurrences of each variable is bounded by a constant. Finally, we give some applications of our results.     

CSP-CASL-Prover: A Generic Tool for Process and Data Refinement

The specification language Csp-Casl allows one to model processes as well as data of distributed systems within one framework. In our paper, we describe how a combination of the existing tools Hets and Csp-Prover can solve the challenges that Csp-Casl raises on integrated theorem proving for processes and data. For building this new tool, the automated generation of theorems and their proofs in Isabelle/HOL plays a fundamental role. A case study of industrial strength demonstrates that our approach scales up to complex problems.     

PMaude: Rewrite-based Specification Language for Probabilistic Object Systems

We introduce a rewrite-based specification language for modelling probabilistic concurrent and distributed systems. The language, based on PMaude, has both a rigorous formal basis and the characteristics of a high-level rule-based programming language. Furthermore, we provide tool support for performing discrete-event simulations of models written in PMaude, and for statistically analyzing various quantitative aspects of such models based on the samples that are generated through discrete-event simulation. Because distributed and concurrent communication protocols can be modelled using actors (concurrent objects with asynchronous message passing), we provide an actor PMaude module. The module aids writing specifications in a probabilistic actor formalism. This allows us to easily write specifications that are purely probabilistic – and not just non-deterministic. The absence of such (un-quantified) non-determinism in a probabilistic system is necessary for a form of statistical analysis that we also discuss. Specifically, we introduce a query language called Quantitative Temporal Expressions (or QuaTEx in short), to query various quantitative aspects of a probabilistic model. We also describe a statistical technique to evaluate QuaTEx expressions for a probabilistic model.     

Collision-based computing implemented by soldier crab swarms

Collision-based computing schemes are implemented using propagating and interacting localisations. When two or more travelling localisations collide, they may reflect or merge into a new localisation. Presence/absence of a localisation in a specified site of a physical space represents True/False values of Boolean variables. Incoming trajectories symbolise inputs and outgoing trajectories are outputs. Logical gates are implemented by collisions between the localisations. We demonstrate how primitives of the collision-based computing can be implemented using swarms of soldier crabs in laboratory experiments. Soldier crabs, Mictyris guinotae, exhibit coherent collective behaviour on an intertidal flat at a daytime low-tide period. The soldier crabs' swarm often moves as a single entity with definite yet dynamically changing boundary. We utilise swarms of soldier crabs to implement a Boolean logic gate. The gate has two inputs and three outputs. Values of the inputs and outputs are represented by crab swarm size or a proportion of crabs in the input and output channels. We demonstrate that the gate performs logical conjunction and negation.     

PATTERN RECOGNITION APPROACHES FOR SPEECH-TO-SPEECH TRANSLATION

We propose a statistical approach to speech-to-speech translation that uses finite-state models in all levels. Acoustic hidden Markov models (HMMs) model the pronunciation of the input-language phonemes and words, while the input–output word mapping, along with the syntax of the output language, are jointly modeled by means a large stochastic finite-state transducer. This allows for a complete integration of all the models so that the translation process can be performed by searching for an optimal path of states through the integrated network. As in speech recognition, HMMs can be trained from an input-language speech corpus, and the translation model is learned automatically from a parallel (text) training corpus. This approach has been assessed in the framework of the EuTrans project, funded by the European Union. Extensive experiments have been carried out with speech-input translations from Spanish to English and from Italian to English in applications involving the interaction (by telephone) of a customer with the front desk of a hotel. A summary of the most relevant results is presented.     

Verification of $${{EB}^3}$$ specifications using CADP

\({{\small {EB}}^3}\) is a specification language for information systems. The core of the \({{\small {EB}}^3}\) language consists of process algebraic specifications describing the behaviour of the entities in a system, and attribute function definitions describing the entity attributes. The verification of \({{\small {EB}}^3}\) specifications against temporal properties is of great interest to users of \({{\small {EB}}^3}\). In this paper, we propose a translation from \({{\small {EB}}^3}\) to LOTOS NT (LNT for short), a value-passing concurrent language with classical process algebra features. Our translation ensures the one-to-one correspondence between states and transitions of the labelled transition systems corresponding to the \({{\small {EB}}^3}\) and LNT specifications. We automated this translation with the \({{{\small {EB}}^3}2{\small {LNT}}}\) tool, thus equipping the \({{\small {EB}}^3}\) method with the functional verification features available in the CADP toolbox.