Advances in Artificial Intelligence – SBIA 2010

In the last few years, we have analyzed the best alternatives for acquiring and processing visual knowledge with the goal of supporting problem solving. We call

visual knowledge

the set of mental models that support the process of reasoning over information that comes from the spatial arrangement and visual aspects of entities. Also, visual knowledge is implicit, meaning that it is difficult to be explicitly represented solely with propositional constructs. In this paper, we describe a representational approach that helps geologists in capturing and applying this kind of knowledge, in order to support software development applied to interpretation tasks in Petroleum Geology applications. Our approach combines propositional constructs with visual pictorial constructs in order to model visual knowledge of geologists. These constructs are proposed in a strong formal model, founded by Formal Ontology concepts. Based on these constructs, we develop a full ontology for stratigraphic description of sedimentary facies. The Formal Ontology background and the approach are detailed and evaluated through the paper.

The increasing need for ontologies and the difficulties of manual construction give place to initiatives proposing methods for automatic and semi-automatic ontology learning. In this work we present a semi-automatic method for domain ontologies extraction from Wikipedia’s categories. In order to validate the method, we have conducted a case study in which we implemented a prototype generating a Tourism ontology. The results are evaluated against a manually built Golden Standard reporting 79.51% Precision and 91.95% Recall, comparable to those found in the literature for other languages.

DL-Lite is being regarded as an effective logic for ontology reasoning due both to its expressive power and its computational properties. Considering that ontologies are important constructs for multi-agent system, in this paper we propose the integration of ontology reasoning and agent-oriented programming. More specifically, we consider an agent-oriented programming language based on DL-Lite with belief bases consisting of an immutable TBox, with the characterization of concepts and roles, and of an ABox with factual knowledge, which can change as the result of perception of the environment, internal actions, and inter-agent communication. We discuss the benefits of ontological reasoning and we give algorithms for belief base querying, plan selection, and for a principled approach for belief base update. The language we propose, AgentSpeak-DL, is a subset of AgentSpeak, a well known BDI multi-agent oriented programming language.

System designers are expected to use error-detecting and correcting techniques. Although, model checking approaches have been used for verification of errors in large complex systems, they can only detect the error. the task of correcting the system design (called

model update

) is completely left to the system designer. Recent works on model update can suggest changes in the system model which do not consider domain contingencies and constraints. In this paper, we present a model update approach that can be used to automatically suggest modifications in a system based on the actions that are behind state transitions and a set of domain constraints. We claim that with this approach we can develop more realistic system error-correcting tools.

This paper investigates learning methods where the target language is the recently proposed probabilistic description logic

cr

$\mathcal{ALC}$

. We start with an inductive logic programming algorithm that learns logical constructs; we then develop an algorithm that learns probabilistic constructs by searching for conditioning concepts, using examples given as interpretations. Issues on learning from entailments are also examined, and practical examples are discussed.

This paper highlights the importance of software maintenance, specifically the UML (Unified Modeling Language) diagrams, created and changed, especially during the tasks of analysis and design of software. The main idea of this paper is to formalize the software maintenance phase in order to motivate the maintenance documentation of these diagrams taking into account a knowledge base which represents the consistency among UML diagrams. The consistency among the diagrams is done through a semantic network, and also formalized by the OCL (Object Constraint Language). Finally, the domain knowledge is represented by production rules which form the knowledge base. This knowledge base is the center of the knowledge-based system whose goal is guiding the developer in the maintenance of UML diagrams by recording and making the consistency of these diagrams. Thus the system has two contributions: storage of the maintenance of UML diagrams and diagnosis of consistencies among the diagrams participating in the maintenance phase.

Semantic mapping employs explicit labels to deal with sensor data in robotic mapping processes. In this paper we present a method for boosting performance of spatial mapping, through the use of a probabilistic ontology, expressed with a probabilistic description logic. Reasoning with this ontology allows segmentation and tagging of sensor data acquired by a robot during navigation; hence a robot can construct metric maps topologically. We report experiments with a real robot to validate our approach, thus moving closer to the goal of integrating mapping and semantic labeling processes.

Models that are suitable for planning are not always easy to specify. In this paper we investigate the conversion of Petri nets into factored Markov decision processes: the former are relatively easy to build while the latter are adequate for policy generation. To represent probabilities that are needed when planning under uncertainty, we introduce factored Petri nets; we then describe the conversion of factored Petri nets in Markov decision processes.

This paper presents a new algorithm for unsupervised incremental learning based on a Bayesian framework. The algorithm, called IGMM (for Incremental Gaussian Mixture Model), creates and continually adjusts a Gaussian Mixture Model consistent to all sequentially presented data. IGMM is particularly useful for on-line incremental clustering of data streams, as encountered in the domain of mobile robotics and animats. It creates an incremental knowledge model of the domain consisting of primitive concepts involving all observed variables. We present some preliminary results obtained using synthetic data and also consider practical issues as convergence properties discuss future developments.

Bayesian Networks (BNs) are applied to a wide range of applications. In the past few years great interest is dedicated to the problem of inferring the structure of BNs solely from the data. In this work we explore a probabilistic method which enables the inclusion of extra knowledge in the inference of BNs. We briefly present the theory of BNs and introduce our probabilistic model. We also present the method of Markov Chain Monte Carlo (MCMC) which is used to sample network structures and hyper-parameters of our probabilistic model. Finally we present and discuss the results focusing on aspects related with the accuracy of the reconstructed networks and how the proposed method behaves when provided with sources of knowledge of different quality.

An important challenge in the development of interactive systems for digital entertainment is to build immersive virtual environments inhabited by synthetic characters that feature an illusion of life. Such characters should be adaptive to unforeseen situations, and therefore less predictable than deterministically scripted characters. In many cases, the adaptive behavior can be based on models of personality and emotion. In this paper we introduce an architecture for the construction of synthetic characters with personality and emotion based on the BDI model, to which is added an Affective Module. This module consists of three sub-modules, namely Personality, Mood and Emotion, and is used to characterize and influence the cognitive activities of perception, memory and decision making of characters. Our goal is to contribute to the design and implementation of believable synthetic characters for digital entertainment.

Autonomous trading is often seen as artificial intelligence applied to finance by AI researchers, but it may also be a way to motivate the development of autonomous agents, just like robot soccer competitions are used to motivate the research in mobile robots. In fact, some initiatives could be observed in recent years, for instance [1] and [2]. In this paper, we present a multiagent system composed by several autonomous analysts that use fundamentalist information in their reasoning process. These fundamentalist information are composed by company profit, dividends, data related to the company economic sector among others. This kind of information is rarely used on autonomous trading, because most of the agents deal only with technical information, which is composed by price and volume time series. Furthermore, we do not find a open source stock market simulator with support to fundamentalist trader agents. We then created a significantly extended version of the open source financial market simulation tool, called AgEx. This designed version provides also fundamentalist information about the trader’s assets. As well as, makes more efficient the exchange of messages within AgEx. This efficiency allows traders that may submit orders in very short intervals of just some seconds or even some fraction of second, to use AgEx as a test platform. Using this new version of AgEx, we implemented and tested the multiagent system based on fundamentalist agents, that we call FAS. The achieved results are presented and analyzed.

This work describes the application of the Baars-Franklin Architecture (BFA), an artificial consciousness approach, to synthesize a mind (a control system) for an artificial creature. Firstly we introduce the theoretical foundations of this approach for the development of a conscious agent. Then we explain the architecture of our agent and at the end we discuss the results and first impressions of this approach.

Believable agents are intelligent agents designed to emulate characteristics such as personality, emotions and relatioships in order to exhibit an ilusion of life to human observers. Hence, designers should not only cater for the individual behaviour, but also consider their social interactions. In this light, this paper describes a model for interaction and relationships in groups of believable agents. The model proposed, X-BARIM, was based on consolidated Psychology studies and aims at enhancing the social simulation credibility. Experiments performed with the model have shown that it is possible to simulate well known phenomena such as Leadership Emergence and Coalition Formation even for larger groups of agents.

Norms have become one of the most promising mechanisms of social control to ensure a desirable social order in open multi-agent systems where autonomous, heterogeneous and independently designed entities can work towards similar or different ends. Norms regulate the behaviour of agents by defining permissions, obligations and prohibitions, and by stating stimulus to their fulfilment while defining rewards and discouraging their violation while pointing out punishments. Since goal-oriented agents’ priority is the satisfaction of their own desires, they must evaluate the positive and negative effects of the fulfilment or violation of the norms before choosing to comply or not with them. In this context, we present the new functions of the Jason platform defined to support normative reasoning, i.e, to build agents able to deal with desires and norms. Agents are then able to check if they should adopt or not the norm, evaluate the effects of the fulfilment or violation of the norm on their desires, detect and solve conflicts among norms, and select desires and plans according to their choices of fulfilling or not a norm. We demonstrate the applicability of such new functions through a non-combatant evacuation scenario.

Reinforcement learning is an efficient, widely used machine learning technique that performs well in problems that are characterized by a small number of states and actions. This is rarely the case in multiagent learning problems. For the multiagent case, standard approaches may not be adequate. As an alternative, it is possible to use techniques that generalize the state space to allow agents to learn through the use of abstractions. Thus, the focus of this work is to combine multiagent learning with a generalization technique, namely

tile coding

. This kind of method is key in scenarios where agents have a high number of states to explore. In the scenarios used to test and validate this approach, our results indicate that the proposed representation outperforms the tabular one and is then an effective alternative.

Factored translation is an extension of the state-of-the-art phrase-based statistical machine translation (PB-SMT). The main difference in factored translation approach is that a word is not only a token (its surface form) but a vector composed of different information such as lemma, part-of-speech or morphologic/syntactic tags. In this paper we present some experiments carried out to train and test factored translation models on Brazilian Portuguese and English texts. Using part-of-speech and morphological information, the factored models showed better results than the baseline (a PB-SMT), but the same gain in performance was not reached when flat syntactic tags were considered.

The task of a Question Answering (QA) system is to automatically answer a question in natural language, searching for information in a given data source, such as structured databases or unstructured natural language documents. In this paper we investigate how much is needed in terms of tools and resources for a QA system for Brazilian Portuguese. In particular we assess the impact of shallow and deep methods and the contribution of different tools and resources in terms of the performance of the system in the task. We argue that a combination of deep and shallow strategies results in optimal performance, but that shallow methods alone may already give adequate results.

This paper will present a cooperative multi-robot localization model with planning support. Models of communication and transmission of pose estimates are constantly explored, however how the robots act on the environment is generally defined by random actions (from the localization task’s point of view). Random actions generate observations that can be useless for improving the estimate. This work describes a proposal for multi-robot localization with planning of actions. The objective is to describe a model where policies define the best action to performed by robots. The proposed model, called Model of Planned Localization - MPL, uses POMDPs to model the problems of location and specific algorithms to generate policies. We compared the MPL to a model that does not make use of planning actions. The results showed that MPL is able to estimate the positions of robots with lower number of steps, being more efficient than model compared.

Real-time dynamic programming (RTDP) solves Markov decision processes (MDPs) when the initial state is restricted. By visiting (and updating) only a fraction of the state space, this approach can be used to solve problems with intractably large state space. In order to improve the performance of RTDP, a variant based on symbolic representation was proposed, named sRTDP. Traditional RTDP approaches work best on problems with sparse transition matrices where they can often efficiently achieve

ε

-convergence without visiting all states; however, on problems with dense transition matrices where most states are reachable in one step, the sRTDP approach shows an advantage over traditional RTDP by up to three orders of magnitude, as we demonstrate in this paper. We also specify a new variant of sRTDP based on BRTDP, named sBRTDP, which converges quickly when compared to RTDP variants, since it does less updating by making a better choice of the next state to be visited.

This paper deals with the Single Machine Scheduling Problem with Earliness and Tardiness Penalties, considering distinct due windows and sequence-dependent setup time. Due to its complexity, an adaptive genetic algorithm is proposed for solving it. Many search operators are used to explore the solution space where the choice probability for each operator depends on the success in a previous search. The initial population is generated by the combination between construct methods based on greedy, random and GRASP techniques. For each job sequence generated, a polynomial time algorithm is used for determining the processing initial optimal date to each job. During the evaluation process, the best individuals produced are added to a special group, called elite group. The individuals of this group are submitted to refinement, aiming to improve their quality. Three variations of this algorithm are submitted to computational test. The results show the effectiveness of the proposed algorithm.

The automatic motion or trajectory planning is essential for several tasks that lead to the autonomy increase of Unmanned Aerial Vehicles (UAVs). This work proposes a Dijkstra algorithm for fixed-wing UAVs trajectory planning. The navigation environments are represented by sets of visibility graphs constructed through the terrain elevations of these environments. Digital elevation models are used to represent the terrain elevations. A heuristics to verify if a trajectory is collision-free is also proposed in this work. This heuristics is a method of grid-based local search which presents linear computational time

O(n

p

)

, where

n

p

is the number of verification steps. This heuristics is compared with another method for collision verification. Results are presented in this work.

With the growing in the use of UAVs (Unmanned Aerial Vehicles), it is necessary to develop techniques that allow the generation of feasible paths for these vehicles. These paths take into account the nonholonomic constraints intrinsic to UAVs, such as minimum curvature, minimum torsion and maximum climb (or dive) angle. Thus, this paper proposes the use of genetic algorithms to generate paths for these vehicles in the three-dimensional space, using Bézier curves with several advantages. We consider all these three constraints in order to generate a feasible path for a small fixed-wing aircraft with severe limitations. We show results for this vehicle.

Most of modern constraint modeling languages combine rich constraint languages with mathematical notations to tackle combinatorial optimization problems. Our purpose is to introduce new component-oriented language constructs to manipulate hierarchical problems, for instance for modeling engineering system architectures with conditional sub-problems. To this end, an object-oriented modeling language is associated with a powerful constraint language. It offers the possibility of defining conditional components to be activated at solving time, declaring polymorphic components whose concrete types have to be determined, and overriding model elements. We illustrate the benefits of this new approach in the modeling process of a difficult embodiment design problem having several architectural alternatives.

Distributed Constraint Optimization Problem (DCOP) has emerged as one of most important formalisms for distributed reasoning in multiagent systems. Nevertheless, there are few real world applications based on methods for solving DCOP, due to their inefficiency in some scenarios. This paper introduces the use of Social Network Analysis (SNA) techniques to improve the performance in pseudo-tree-based DCOP algorithms. We investigate when the SNA is useful and which techniques can be applied in some DCOP instances. To evaluate our proposal, we use the two most popular complete and optimal DCOP algorithms, named ADOPT and DPOP, and compare the obtained results with others well-known pre-processing techniques. The experimental results show that SNA techniques can speed up ADOPT and DPOP algorithms.

A* (

a-star

) is a well known best-first search algorithm that has been applied to the solution of different problems. In recent years, several extensions have been proposed to adapt it and improve its performance in different application scenarios. In this paper, we present a survey and classification of the main extensions to the A* algorithm that have been proposed in the literature. We organize them into five classes according to their objectives and characteristics:

incremental

,

memory-concerned

,

parallel

,

anytime

, and

real-time

. For each class, we discuss its main characteristics and applications and present the most representative algorithms.

A central issue for spatial reasoning in practice is to formalize reasoning about 3-dimensional space. In this paper, a spatial logic called 3-dimensional spatial logic (3SL), which can appropriately represent the 3-Cartesian product

ω

3

of the set

ω

of natural numbers, is introduced as a Gentzen-type sequent calculus. 3SL is an extension and generalization of the linear-time temporal logic LTL in which the time domain is

ω

. The completeness and cut-elimination theorems for 3SL are proved.

Fuzzy Probabilities are an extension of the concept of probabilities with application in several practical problems. The former are probabilities represented through fuzzy numbers, to indicate the uncertainty in the value assigned to a probability. Moreover, Krassimir Atanassov in 1983 added an extra degree of uncertainty to classic fuzzy sets for modeling the hesitation and uncertainty about the degree of membership. This new theory of fuzzy sets is known today as intuitionistic fuzzy set theory.

This work will extend the notion of fuzzy probabilities by representing probabilities through the intuitionistic fuzzy numbers, in the sense of Atanassov, instead of fuzzy numbers.

A new logic, sequence-indexed linear-time temporal logic (SLTL), is obtained semantically from the standard linear-time temporal logic LTL by adding a sequence modal operator which represents a sequence of symbols. By the sequence modal operator of SLTL, we can appropriately express “sequential information” in temporal reasoning. A Gentzen-type sequent calculus for SLTL is introduced, and the completeness and cut-elimination theorems for this calculus are proved. SLTL is also shown to be PSPACE-complete and embeddable into LTL.

In this paper, we investigate the Probabilistic Satisfiability Problem, and its relation with the classical Satisfiability Problem, looking for a possible polynomial-time reduction. For this, we present an Atomic Normal Form to the probabilistic satisfiability problem and then we define a Probabilistic Entailment relation, showing its inherent properties. At the end, we enunciate and refute a conjecture that could lead to the desired polynomial-time reduction.

We propose a proof-theoretical way of obtaining detailed and precise information on conceptual hierarchies. The notion of concept finding proof, which represents a hierarchy of concepts, is introduced based on a substructural logic with mingle and strong negation. Mingle, which is a structural inference rule, is used to represent a process for finding a more general (or specific) concept than some given concepts. Strong negation, which is a negation connective, is used to represent a concept inverse operator. The problem for constructing a concept finding proof is shown to be decidable in PTIME.