AI*IA 2015 Advances in Artificial Intelligence

Message broadcasting and topology discovery are classical problems for distributed systems, both of which are related to the concept of network exploration. Typical decentralized approaches assume that network nodes are provided with traditional routing tables. In this paper we propose a novel network exploration approach based on collective self-awareness and self-expression, resulting from the simultaneous application of two strategies, namely hierarchy and recursion, which imply the adoption of unusual routing tables. We show how the proposed approach may provide distributed systems with improved efficiency and scalability, with respect to traditional approaches.

This paper presents a Traffic Lights control system, inspired by Swarm intelligence methodologies, in which every intersection controller makes independent decisions to pursue common goals and is able to improve the global traffic performance. The solution is low cost and widely applicable to different urban scenarios. This work is developed within the COLOMBO european project. Control methods are divided into macroscopic and microscopic control levels: the former reacts to macroscopic key figures such as mean congestion length and mean traffic density and acts on the choice of the signal program or the development of the frame signal program; the latter includes changes at short notice based on changes in the traffic flow: they include methods for signal program adaptation and development. The developed system has been widely tested on synthetic benchmarks with promising results.

We apply Path Relinking to a real life constrained optimization problem concerning the scheduling of technicians due to activate on site devices located on a water distribution network in case of a contamination event, in order to reduce the amount of consumed contaminated water. Teams travel on the road network when moving from one device to the next, as in the Multiple Traveling Salesperson Problem. The objective, however, is not minimizing travel time but the minimization of consumed contaminated water. This is computed through a computationally demanding simulation given the devices activation times. We propose alternative Path Relinking search strategies exploiting time-based and precedence-based neighborhoods, and evaluate the improvement gained by coupling Path Relinking with state of the art, previously developed, hybrid Genetic Algorithms. Experimental results on a real network are provided to support the efficacy of the methodology.

In this work we investigate the dynamical properties of the Boolean networks (BN) that control a robot performing a composite task. Initially, the robot must perform phototaxis, i.e. move towards a light source located in the environment; upon perceiving a sharp sound, the robot must switch to antiphototaxis, i.e. move away from the light source. The network controlling the robot is subject to an adaptive walk and the process is subdivided in two sequential phases: in the first phase, the learning feedback is an evaluation of the robot’s performance in achieving only phototaxis; in the second phase, the learning feedback is composed of a performance measure accounting for both phototaxis and antiphototaxis. In this way, it is possible to study the properties of the evolution of the robot when its behaviour is adapted to a new operational requirement. We analyse the trajectories followed by the BNs in the state space and find that the best performing BNs (i.e. those able to maintaining the previous learned behaviour while adapting to the new task) are characterised by generalisation capabilities and the emergence of simple behaviours that are dynamically combined to attain the global task. In addition, we also observe a further remarkable property: the complexity of the best performing BNs increases during evolution. This result may provide useful indications for improving the automatic design of robot controllers and it may also help shed light on the relation and interplay among robustness, evolvability and complexity in evolving systems.

Tactical level decisions in pedestrian simulation are related to the choice of a route to follow in an environment comprising several rooms connected by gateways. Agents are supposed to be aware of the environmental structure, but they should also be aware of the level of congestion, at least for the gateways that are immediately in sight. This paper presents the tactical level component of a hybrid agent architecture in which these decisions are enacted at the operational level by mean of a floor-field based model, in a discrete simulation approach. The described model allows the agent taking decisions based on a static a-priori knowledge of the environment and dynamic perceivable information on the current level of crowdedness of visible path alternatives.

The popularity of mobile devices has fostered the emergence of plenty of new services, most of which rely on the use of their cameras. Among these, diet monitoring based on computer vision can be of particular interest. However, estimation of the amount of food portrayed in an image requires a size reference. A small checkerboard is a simple pattern which can be effectively used to that end. Unfortunately, most existing off-the-shelf checkerboard detection algorithms have problems detecting small patterns since they are used in tasks such as camera calibration, which require that the pattern cover most of the image area. This work presents a stochastic model-based approach, which relies on Differential Evolution (DE), to detecting small checkerboards. In the method we propose the checkerboard pattern is first roughly located within the image using DE. Then, the region detected in the first step is cropped in order to meet the requirements of off-the-shelf algorithms for checkerboard detection and let them work at their best. Experimental results show that, doing so, it is possible to achieve not only a significant increase of detection accuracy but also a relevant reduction of processing time.

Agent coordination based on Activity Theory postulates that agents control their own behavior from the outside by using and creating artifacts through which they interact. Based on this conception, we envisage social engagements as first-class resources that agents exploit in their deliberative cycle (as well as beliefs, goals, intentions), and propose to realize them as artifacts that agents create and manipulate along the interaction, and that drive the interaction itself. Consequently, agents will base their reasoning on their social engagement, instead of relying on event occurrence alone. Placing social engagement at the center of coordination promotes agent decoupling and also the decoupling of the agent specifications from the specification of their coordination. The paper also discusses JaCaMo+, a framework that implements this proposal.

Some of the most peculiar traits of socio-technical KIE (knowledge-intensive environments) – such as unpredictability of agents’ behaviour, ever-growing amount of information to manage, fast-paced production/consumption – tangle coordination of information, by affecting, e.g., reachability by knowledge prosumers and manageability by the IT infrastructure. Here, we propose a novel approach to coordination in KIE, by extending the

$${MoK}$$

model for knowledge self-organisation with key concepts from the cognitive theory of BIC (behavioural implicit communication).

In this paper we rephrase the problem of opinion formation from a physical viewpoint. We consider a multi-agent system where each agent is associated with an opinion and interacts with any other agent. Interpreting the agents as the molecules of a gas, we model the opinion evolution according to a kinetic model based on the analysis of interactions among agents. From a microscopic description of each interaction between pairs of agents, we derive the stationary profiles under given assumption. Results show that, depending on the average opinion and on the model parameters, different profiles can be found, with different properties. Each stationary profile is characterized by the presence of one or two maxima.

We experimentally analyze the performance of a heterogeneous population of agents playing the Iterated Prisoner’s Dilemma with a possible prior commitment ad a posterior punishment for defection. We argue that the presence of agents with a probabilistic strategy that depends on trust and reputation enforces a better performance of typically cooperative agents.

Sustainable energy policies are becoming of paramount importance for our future, shaping the environment around us, underpinning economic growth, and increasingly affecting the geopolitical considerations of governments world-wide. Renewable energy diffusion and energy efficiency measures are key for obtaining a transition toward low carbon energy systems.

A number of policy instruments have been devised to foster such a transition: feed-in-tariffs, tax exemptions, fiscal incentives, grants. The impact of such schemes on the actual adoption of renewable energy sources is affected by a number of economic and social factors.

In this paper, we propose a novel approach to model the diffusion of residential PV systems and assess the impact of incentives. We model the diffusion’s environment using an agent-based model and we study the emergent, global behaviour emerging from the interactions among the agents. While economic factors are easily modelled, social ones are much more difficult to extract and assess. For this reason, in the model we have inserted a large number of social parameters that have been automatically tuned on the basis of past data. The Emilia-Romagna region of Italy has been used as a case study for our approach.

We use methods based on ontology engineering to individuate the shortcomings of feature-based modelling approaches in product lifecycle data management, and propose an alternative view.

Our aim is to contribute to the development of information systems for the integrated management of product lifecycle knowledge. In particular, we are looking for suitable approaches to model the variety of engineering features as used in intensive knowledge-based product development tasks, in particular dealing with manufacturing and engineering design.

We describe

DysToPic

, a theorem prover for the preferential Description Logic

$$\mathcal {ALC}+\mathbf{T}_{min}$$

.This is a nonmonotonic extension of standard

$$\mathcal {ALC}$$

based on a typicality operator

$$\mathbf{T}$$

, which enjoys a preferential semantics.

DysToPic

is a multi-engine Prolog implementation of a labelled, two-phase tableaux calculus for

$$\mathcal {ALC}+\mathbf{T}_{min}$$

whose basic idea is that of performing these two phases by different machines. The performances of

DysToPic

are promising, and significantly better than the ones of its predecessor

PreDeLo 1.0

recently introduced.

Algorithm selection techniques are known to improve the performance of systems for several knowledge representation and reasoning frameworks.This holds also in the case of Answer Set Programming (ASP), which is a rule-based programming paradigm with roots in logic programming and non-monotonic reasoning. Indeed, the multi-engine approach to ASP solving implemented in

me-asp

was particularly effective on the instances of the third ASP competition. In this paper we report about the advances we made on

me-asp

in order to deal with the new standard language ASPCore 2.0, which substantially extends the previous version of the standard language.An experimental analysis conducted on the Fifth ASP Competition benchmarks and solvers confirms the effectiveness of our approach also in comparison to rival systems.

We revise some results in Argumentation-based Logic Programming under the umbrella of Satisfiability Modulo CHR (SMCHR), specifically considering Defeasible Logic Programming (DeLP). Strict and defeasible rules in DeLP can be cast to SMCHR rules, which act as conflict “disentanglers” and implement the Theory part. At the same time, we inherit several built-in theory solvers, as SAT, unification, or linear arithmetic ones, which implement the Satisfiability-modulo part. Moreover, we show how to deal with possibilistic extensions of DeLP, i.e., Possibilistic-DeLP, where certainty scores describing the possibility of some events are associated with rules.

Abstract solvers are a graph-based representation employed in many research areas, such as SAT, SMT and ASP, to model, analyze and compare search algorithms in place of pseudo-code-based representations. Such an uniform, formal way of presenting the solving algorithms proved effective for their understanding, for formalizing related formal properties and also for combining algorithms in order to design new solving procedures.

In this paper we present abstract solvers for Quantified Boolean Formulas (QBFs). They include a direct extension of the abstract solver describing the DPLL algorithm for SAT, and an alternative formulation inspired by the two-layers architecture employed for the analysis of disjunctive ASP solvers. We finally show how these abstract solvers can be directly employed for designing solving procedures for reasoning tasks which can be solved by means of reduction to a QBF.

The rising interest around tractable Probabilistic Graphical Models is due to the guarantees on inference feasibility they provide. Among them, Cutset Networks (CNets) have recently been introduced as models embedding Pearl’s cutset conditioning algorithm in the form of weighted probabilistic model trees with tree-structured models as leaves. Learning the structure of CNets has been tackled as a greedy search leveraging heuristics from decision tree learning. Even if efficient, the learned models are far from being accurate in terms of likelihood. Here, we exploit the decomposable score of CNets to learn their structure and parameters by directly maximizing the likelihood, including the BIC criterion and informative priors on smoothing parameters. In addition, we show how to create mixtures of CNets by adopting a well known bagging method from the discriminative framework as an effective and cheap alternative to the classical EM. We compare our algorithms against the original variants on a set of standard benchmarks for graphical model structure learning, empirically proving our claims.

Research in Computational Linguistics (CL) has been growing rapidly in recent years in terms of novel scientific challenges and commercial application opportunities. This is due to the fact that a very large part of the Web content is textual and written in many languages. A part from linguistic resources (e.g., WordNet), the research trend is moving towards the automatic extraction of semantic information from large corpora to support on-line understanding of textual data. An example of direct outcome is represented by common-sense semantic resources. The main example is ConceptNet, the final result of the Open Mind Common Sense project developed by MIT, which collected unstructured common-sense knowledge by asking people to contribute over the Web. In spite of being promising for its size and broad semantic coverage, few applications appeared in the literature so far, due to a number of issues such as inconsistency and sparseness. In this paper, we present the results of the application of this type of knowledge in two different (supervised and unsupervised) scenarios: the computation of semantic similarity (the keystone of most Computational Linguistics tasks), and the automatic identification of word meanings (Word Sense Induction) in simple syntactic structures.

Integrated Tourism can be defined as the kind of tourism which is explicitly linked to the localities in which it takes place and, in practical terms, has clear connections with local resources, activities, products, production and service industries, and a participatory local community. In this paper we report our experience in applying Artificial Intelligence techniques to Integrated Tourism planning in urban areas. In particular, we have modeled a domain ontology for Integrated Tourism and developed an Information Extraction tool for populating the ontology with data automatically retrieved from the Web. Also, we have defined several Semantic Web Services on top of the ontology and applied a Machine Learning tool to better adapt the automated composition of these services to user demands. Use cases of the resulting service infrastructure are illustrated for the Apulia Region, Italy.

Ensuring safe behaviors, i.e., minimizing the probability that a control strategy yields undesirable effects, becomes crucial when robots interact with humans in semi-structured environments through adaptive control strategies. In previous papers, we contributed to propose an approach that (

i

) computes control policies through reinforcement learning, (

ii

) verifies them against safety requirements with probabilistic model checking, and (

iii

) repairs them with greedy local methods until requirements are met. Such learn-verify-repair work-flow was shown effective in some — relatively simple and confined — test cases. In this paper, we frame human-robot interaction in light of such previous contributions, and we test the effectiveness of the learn-verify-repair approach in a more realistic factory-to-home deployment scenario. The purpose of our test is to assess whether we can verify that interaction patterns are carried out with negligible human-to-robot collision probability and whether, in the presence of user tuning, strategies which determine offending behaviors can be effectively repaired.

Predicate Invention is the branch of symbolic Machine Learning aimed at discovering new emerging concepts in the available knowledge. The outcome of this task may have important consequences on the efficiency and effectiveness of many kinds of exploitation of the available knowledge. Two fundamental problems in Predicate Invention are how to handle the combinatorial explosion of candidate concepts to be invented, and how to select only those that are really relevant. Due to the huge number of candidates, there is a need for automatic techniques to assign a degree of relevance to the various candidates and select the best ones. Purely logical approaches may be too rigid for this purpose, while statistical solutions may provide the required flexibility.

This paper proposes a new Statistical Relational Learning approach to Predicate Invention. The candidate predicates are identified in a logic theory, rather than in the background knowledge, and are used to restructure the theory itself. Specifically, the proposed approach exploits the Markov Logic Networks framework to assess the relevance of candidate predicate definitions. It was implemented and tested on a traditional problem in Inductive Logic Programming, yielding interesting results.

In symbolic Machine Learning, the incremental setting allows to refine/revise the available model when new evidence proves it is inadequate, instead of learning a new model from scratch. In particular,

specialization

operators allow to revise the model when it covers a negative example. While specialization can be obtained by introducing negated preconditions in concept definitions, the state-of-the-art in Inductive Logic Programming provides only for specialization operators that can negate single literals. This simplification makes the operator unable to find a solution in some interesting real-world cases.

This paper proposes an empowered specialization operator for Datalog Horn clauses. It allows to negate conjunctions of pre-conditions using a representational trick based on predicate invention. The proposed implementation of the operator is used to study its behavior on toy problems purposely developed to stress it. Experimental results obtained embedding this operator in an existing learning system prove that the proposed approach is correct and viable even under quite complex conditions.

Even though a few architectures exist to support the difficult ontology matching task, it happens often they are not reconfigurable (or just a little) related to both ontology features and applications needs.

We introduce GENOMA, an architecture supporting development of Ontology Matching (OM) tools with the aims to reuse, possibly, existing modules each of them dealing with a specific task/subtasks of the OM process. In GENOMA flexibility and extendibility are considered mandatory features along with the ability to parallelize and distribute the processing load on different systems. Thanks to a dedicated graphical user interface, GENOMA can be used by expert users, as well as novice, that can validate the resulting architecture.

We highlight as main features of developed architecture:

to select, combine and set different parameters

to evaluate the matching tool applied to big size ontologies

efficiency of the OM tool

automatic balancing of the processing load on different systems

Open Data initiatives from governments and public agencies in Europe have made large amounts of data available on the web. Linked Data principles can help to improve Open Data integration, disclosing the connections between datasets, leveraging a powerful usage of data and enabling innovative ways to improve citizens’ life. In this work we present a novel approach for Open Data integration, based on SPARQL federated queries formalized as SPIN rules. This methodology allows the interlinking and enrichment of heterogeneous Open Data, using the distributed knowledge of the Linked Open Data cloud. We present a case study on integrating and publishing, via enrichment and interlinking techniques, tourism domain datasets as Linked Open Data.

Recent interests in Sentiment Analysis brought the attention on effective methods to detect opinions and sentiments in texts. Many approaches in literature are based on hand-coded resources that model the

prior

polarity of words or multi-word expressions. The development of such resources is expensive and language dependent so that they cannot fully cover linguistic sentiment phenomena. This paper presents an automatic method for deriving large-scale polarity lexicons based on Distributional Models of Lexical Semantics. Given a set of heuristically annotated sentences from Twitter, we transfer the sentiment information from sentences to words. The approach is mostly unsupervised, and experiments on different Sentiment Analysis tasks in English and Italian show the benefits of the generated resources.

While robotic platforms are moving from industrial to consumer applications, the need of flexible and intuitive interfaces becomes more critical and the capability of governing the variability of human language a strict requirement. Grounding of lexical expressions, i.e. mapping words of a user utterance to the perceived entities of a robot operational scenario, is particularly critical. Usually, grounding proceeds by learning how to associate objects categorized in discrete classes (e.g. routes or sets of visual patterns) to linguistic expressions. In this work, we discuss how lexical mapping functions that integrate Distributional Semantics representations and phonetic metrics can be adopted to robustly automate the grounding of language expressions into the robotic semantic maps of a house environment. In this way, the pairing between words and objects into a semantic map facilitates the grounding without the need of an explicit categorization. Comparative measures demonstrate the viability of the proposed approach and the achievable robustness, quite crucial in operational robotic settings.

In this paper we present an automatic multilingual annotation of the Wikipedia dumps in two languages, with both word senses (i.e. concepts) and named entities. We use Babelfy 1.0, a state-of-the-art multilingual Word Sense Disambiguation and Entity Linking system. As its reference inventory, Babelfy draws upon BabelNet 3.0, a very large multilingual encyclopedic dictionary and semantic network which connects concepts and named entities in 271 languages from different inventories, such as WordNet, Open Multilingual WordNet, Wikipedia, OmegaWiki, Wiktionary and Wikidata. In addition, we perform both an automatic evaluation of the dataset and a language-specific statistical analysis. In detail, we investigate the word sense distributions by part-of-speech and language, together with the similarity of the annotated entities and concepts for a random sample of interlinked Wikipedia pages in different languages. The annotated corpora are available at

http://lcl.uniroma1.it/babelfied-wikipedia/

.

Semantic annotation aims at linking parts of rough data (

e.g.

, text, video, or image) to known entities in the Linked Open Data (LOD) space. When several entities could be linked to a given object, a Named-Entity Disambiguation (NED) problem must be solved. While disambiguation has been extensively studied in Natural Language Understanding (NLU), NED is less ambitious—it does not aim to the meaning of a whole phrase, just to correctly link objects to entities—and at the same time more peculiar since the target must be LOD-entities. Inspired by semantic similarity in NLU, this paper illustrates a way to solve disambiguation based on Common Subsumers of pairs of RDF resources related to entities recognized in the text. The inference process proposed for resolving ambiguities leverages on the DBpedia structured semantics. We apply it to a TV-program description enrichment use case, illustrating its potential in correcting errors produced by automatic text annotators (such as errors in assigning entity types and entity URIs), and in extracting a description of the main topics of a text in form of commonalities shared by its entities.

This paper presents and evaluates an integrated power-aware, model-based autonomous control architecture for managing the execution of rover actions in the context of planetary mission exploration. The proposed solution is embedded within an application scenario of reference which consists on a rover-based mission concept aimed at collecting Mars samples that may be returned to Earth at a later date for further investigation. This study elaborates on the exploitation of advanced decision-making capabilities within a flexible execution process targeted at generating and safely executing scheduling solutions representing mission plans, seamlessly supporting online plan optimization and dynamic management of new incoming activities. In this work, an experimental analysis on the performance of the control architecture’s capabilities is presented, throughout two representative cases of study running upon an integrated test-bed platform built on top of the 3DROV ESA planetary rover simulator.

In this paper, we consider an autonomous robot that persists over time performing tasks and the problem of providing one

additional

task to the robot’s task library. We present an approach to

generalize tasks

, represented as parameterized graphs with sequences, conditionals, and looping constructs of sensing and actuation primitives. Our approach performs graph-structure task generalization, while maintaining task executability and parameter value distributions. We present an algorithm that, given the initial steps of a new task, proposes an autocompletion based on a recognized past similar task. Our generalization and autocompletion contributions are effective on different real robots. We show concrete examples of the robot primitives and task graphs, as well as results, with Baxter. In experiments with multiple tasks, we show a significant reduction in the number of new task steps to be provided.

A key enabling feature to deploy a plan-based application for solving real world problems is the capability to integrate Planning and Scheduling (

P&S

) in the solving approach.

Flexible Timeline-based Planning

has been successfully applied in several real contexts to solve

P&S

problems. In this regard, we developed the

Extensible Planning and Scheduling Library

(

Epsl

) aiming at supporting the design of

P&S

applications. This paper describes some recent advancements in extending the

Epsl

framework by introducing the capability to reason about different types of “components”, i.e.,

state variables

and

renewable resources

, and allowing a tight integration of Planning and Scheduling techniques. Moreover, we present a domain independent

heuristic

function supporting the solving process by exploiting the hierarchical structure of the set of timelines making up the flexible plan. Some empirical results are reported to show the feasibility of deploying an

Epsl

-based

P&S

application in a real-world manufacturing case study.

This paper introduces the ongoing work for a novel domain-independent planning system which takes inspiration from both Constraint Programming (CP) and Logic Programming (LP), flavouring it all with Object Oriented features. We will see a specific customization of our environment to the particular kind of automated planning referred to as timeline-based. By allowing for the interesting ability of solving both planning and scheduling problems in a uniform schema, the resulting system is particularly suitable for complex domains arising from real dynamic scenarios. The paper proposes a resolution algorithm and enhances it with some (static and dynamic) heuristics to help the solving process. The system is tested on different benchmark problems from classical planning domains like the Blocks World to more challenging temporally expressive problems like the Temporal Machine Shop and the Cooking Carbonara problems demonstrating how the new planner, named iLoC, compares with respect to other state-of-the-art planners.

Intelligent agents solving problems in the real world require domain models containing widespread knowledge of the world.

AI Planning requires domain models. Synthesising operator descriptions and domain specific constraints by hand for AI planning domain models is time intense, error-prone and challenging. To alleviate this, automatic domain model acquisition techniques have been introduced. Amongst others, the LOCM and LOCM2 systems require as input some plan traces only, and are effectively able to automatically encode a large part of the domain knowledge. In particular, LOCM effectively determines the dynamic part of the domain model. On the other hand, the static part of the domain – i.e., the underlying structure of the domain that can not be dynamically changed, but that affects the way in which actions can be performed – is usually missed, since it can hardly be derived by observing transitions only.

In this paper we introduce ASCoL, a tool that exploits graph analysis for automatically identifying static relations, in order to enhance planning domain models. ASCoL has been evaluated on domain models generated by LOCM for international planning competition domains, and has been shown to be effective.

One of the long-term goals of our society is to build robots able to live side by side with humans. In order to do so, robots need to be able to reason in a qualitative way. To this end, over the last years, the Artificial Intelligence research community has developed a considerable amount of qualitative reasoners. The majority of such approaches, however, has been developed under the assumption that suitable representations of the world were available. In this paper, we propose a method for performing qualitative spatial reasoning in robotics on abstract representations of environments, automatically extracted from metric maps. Both the representation and the reasoner are used to perform the grounding of commands vocally given by the user. The approach has been verified on a real robot interacting with several non-expert users.

The deployment of robots in dynamic, complex and uncertain environments populated by people is gaining more and more attention, from both research and application perspectives. The new challenge for the near future is to deploy intelligent social robots in public spaces to make easier and safer the use of these spaces. In this paper, we provide an overview of the

COACHES

project which addresses fundamental issues related to the design and development of autonomous robots to be deployed in public spaces. In particular, we describe the main components in which Artificial Intelligence techniques are used and integrated with the robotic system, as well as implementation details and some preliminary tests of these components.