Agents and Artificial Intelligence

This paper briefly presents the research performed in the context of FC Portugal project concerning coordination methodologies applied to robotic soccer. FC Portugal’s research has been integrated in several teams that have participated with considerable success in distinct RoboCup leagues and competitions. The paper includes a brief description of the main RoboCup competitions in which FC Portugal (and associated teams) has participated with focus in the simulation leagues and related challenges. It also presents a complete state of the art concerning coordination methodologies applied to robotic soccer followed by FC Portugal main contributions on this area. The team contributions include methodologies for strategic reasoning, coaching, strategic positioning, dynamic role exchange and flexible setplay definition and execution. These methodologies compose a complete coordination framework that enable a robotic team to play soccer or execute similar tasks.

We introduce a novel hierarchical planning approach that extends previous approaches by additionally considering decompositions that are only applicable with respect to a consistent extension of the (open-ended) domain model at hand. The introduced planning approach is integrated into a plan-based control architecture that interleaves planning and execution automatically so that missing information can be acquired by means of active knowledge acquisition. If it is more reasonable, or even necessary, to acquire additional information prior to making the next planning decision, the planner postpones the overall planning process, and the execution of appropriate knowledge acquisition tasks is automatically integrated into the overall planning and execution process.

In this paper, we propose a flexible system for robust natural language interpretation of spoken commands on a mobile robot in domestic service robotics applications. Existing language processing for instructing a mobile robot is often restricted by using a simple grammar where precisely pre-defined utterances are directly mapped to system calls. These approaches do not regard fallibility of human users and they only allow for binary processing of an utterance; either a command is part of the grammar and hence understood correctly, or it is not part of the grammar and gets rejected. We model the language processing as an interpretation process where the utterance needs to be mapped to the robot’s capabilities. We do so by casting the processing as a (decision-theoretic) planning problem on interpretation actions. This allows for a flexible system that can resolve ambiguities and which is also capable of initiating steps to achieve clarification. We show how we evaluated several versions of the system with multiple utterances of different complexity as well as with incomplete and erroneous requests.

This paper discusses the development of fuzzy logic model for estimating the 85^th percentile speed of urban roads. Spot speed survey was conducted on four randomly selected urban road segments for a typical weekday and a weekend. The considered road segment attribute data are length of the road segment, number of access points/intersecting links, number of pedestrian crossings, number of lanes, hourly traffic volume, hourly pedestrian volume and current posted speed limits of the selected roads. Such attribute data were collected and used as input variables in the model. Two models for weekday and weekend were developed based on the field survey data. Both models were calibrated using the neuro-fuzzy technique for optimizing the fuzzy logic model (FLM) parameters. Analyses of estimated results show that the FLM can estimate the 85^th percentile speed to a reasonable level.

In this paper twenty language independent statistically-based metrics used for key term extraction from any document collection are compared. Some of those metrics are widely used for this purpose. The others were recently created. Two different document representations are considered in our experiments. One is based on words and multi-words and the other is based on word prefixes of fixed length (5 characters for the experiments made). Prefixes were used for studying how morphologically rich languages, namely Portuguese and Czech behave when applying this other kind of representation. English is also studied taking it, as a non-morphologically rich language. Results are manually evaluated and agreement between evaluators is assessed using k-Statistics. The metrics based on Tf-Idf and Phi-square proved to have higher precision and recall. The use of prefix-based representation of documents enabled a significant precision improvement for documents written in Portuguese. For Czech, recall also improved.

We present active object categorization experiments with a real humanoid robot. For this purpose, the training algorithm of a recurrent neural network with parametric bias has been extended with adaptive learning rates. This modification leads to an increase in training speed. Using this new training algorithm we conducted three experiments aiming at object categorization. While holding different objects in its hand, the robot executes a motor sequence that induces multi-modal sensory changes. During learning, these high-dimensional perceptions are ‘engraved’ in the network. Simultaneously, low-dimensional PB values emerge unsupervised. The geometrical relation of these PB vectors can then be exploited to infer relations between the original high dimensional time series characterizing different objects. Even sensations belonging to unknown objects can be discriminated from known (learned) ones and kept apart from each other reliably. Additionally, we show that the network tolerates noisy sensory signals very well.

The exploration/exploitation (E/E) dilemma arises naturally in many subfields of Science. Multi-armed bandit problems formalize this dilemma in its canonical form. Most current research in this field focuses on generic solutions that can be applied to a wide range of problems. However, in practice, it is often the case that a form of prior information is available about the specific class of target problems. Prior knowledge is rarely used in current solutions due to the lack of a systematic approach to incorporate it into the E/E strategy.

To address a specific class of E/E problems, we propose to proceed in three steps: (i) model prior knowledge in the form of a probability distribution over the target class of E/E problems; (ii) choose a large hypothesis space of candidate E/E strategies; and (iii), solve an optimization problem to find a candidate E/E strategy of maximal average performance over a sample of problems drawn from the prior distribution.

We illustrate this meta-learning approach with two different hypothesis spaces: one where E/E strategies are numerically parameterized and another where E/E strategies are represented as small symbolic formulas. We propose appropriate optimization algorithms for both cases. Our experiments, with two-armed “Bernoulli” bandit problems and various playing budgets, show that the meta-learnt E/E strategies outperform generic strategies of the literature (UCB1, UCB1-Tuned, UCB-V, KL-UCB and ε _n -Greedy); they also evaluate the robustness of the learnt E/E strategies, by tests carried out on arms whose rewards follow a truncated Gaussian distribution.

We present MobEx, a mobile touchable application for exploratory search on the mobile web. The system has been implemented for operation on a tablet computer, i.e. an Apple iPad, and on a mobile device, i.e. Apple iPhone or iPod touch. Starting from a topic issued by the user the system collects web snippets that have been determined by a standard search engine in a first step and extracts associated topics to the initial query in an unsupervised way on-demand and highly performant. This process is recursive in priciple as it furthermore determines other topics associated to the newly found ones and so forth. As a result MobEx creates a dense web of associated topics that is presented to the user as an interactive topic graph. We consider the extraction of topics as a specific empirical collocation extraction task where collocations are extracted between chunks combined with the cluster descriptions of an online clustering algorithm. Our measure of association strength is based on the pointwise mutual information between chunk pairs which explicitly takes their distance into account. These syntactically–oriented chunk pairs are then semantically ranked and filtered using the cluster descriptions created by a Singular Value Decomposition (SVD) approach. An initial user evaluation shows that this system is especially helpful for finding new interesting information on topics about which the user has only a vague idea or even no idea at all.

In order to determine the prevalence of the proposed set of anaphora relations we did a detailed analysis of a subset 20 newspaper articles. The results obtained from this also indicated that a majority (98%) of the relations could be described by the relations in the framework. The results from this analysis also showed the distribution of the relation types in the genre of news paper article discourses.

In emergency situations such as earthquake, typhoon, it is important to share people’s actions in real-time. Therefore, in this paper, we first design a timeline action network based on Web Ontology Language (OWL) in order to represent these actions in real-time. We then use our previous work to automatically collect data for the action network from Twitter. Finally, we propose a novel action-based collaborative filtering, which predicts missing activity data, in order to complement this timeline action network. Moreover, with a combination of collaborative filtering and natural language processing (NLP), our method can deal with minority actions such as successful actions. Based on evaluation of tweets which related to the massive Tohoku earthquake, we indicated that our timeline action network can share useful action patterns in real-time. Not only earthquake disaster, our research can also be applied to other disasters and business models, such as typhoon, travel, marketing, etc.

Modeling real world agent-based systems is a complex endeavour. An ideal domain specific agent modeling language would be tailored to a certain application domain (e.g. agents in virtual worlds) as well as to the target execution environment (e.g. a virtual reality platform). This includes the use of specialized concepts of the application domain, software languages (e.g. query languages for reasoning about an agent’s knowledge), as well as custom views and diagrams for designing the system. This paper presents a model-driven framework for engineering multiagent systems, called Bochica. The framework is based on a platform independent modeling language which covers the core concepts of multiagent systems. In order to better close the gap between design and code, Bochica can be extended through several extension interfaces for custom application domains and execution environments. The framework is accompanied by an iterative adaptation process to gradually incorporate conceptual extensions. The approach has been evaluated at modeling agents in semantically-enriched virtual worlds.

Shortest-path problems on graphs have been studied in depth in Artificial Intelligence and Computer Science. Search on dynamic graphs, i.e. graphs that can change their layout while searching, receives plenty of attention today – mostly in the planning domain. Approaches often assume global knowledge on the dynamic graph, i.e. that topology and dynamic operations are known to the algorithm. There exist use-cases however, where this assumption cannot be made. In vehicular ad-hoc networks, for example, a vehicle is only able to recognize the topology of the graph within wireless network transmission range. In this paper, we propose a combined uniform and heuristic search algorithm, which maintains shortest paths in highly dynamic graphs under the premise that graph operations are not globally known.

A general game player is a program that is able to play arbitrary games well given only their rules. One of the main problems of general game playing is the automatic construction of a good evaluation function for these games. Distance features are an important aspect of such an evaluation function, measuring, e.g., the distance of a pawn towards the promotion rank in chess or the distance between Pac-Man and the ghosts.

However, current distance features for General Game Playing are often based on too specific detection patterns to be generally applicable, and they often apply a uniform Manhattan distance regardless of the move patterns of the objects involved. In addition, the existing distance features do not provide proven bounds on the actual distances.

In this paper, we present a method to automatically construct distance heuristics directly from the rules of an arbitrary game. The presented method is not limited to specific game structures, such as Cartesian boards, but applicable to all structures in a game. Constructing the distance heuristics from the game rules ensures that the construction does not depend on the size of the state space, but only on the size of the game description which is exponentially smaller in general. Furthermore, we prove that the constructed distance heuristics are admissible, i.e., provide proven lower bounds on the actual distances.

We demonstrate the effectiveness of our approach by integrating the distance heuristics in an evaluation function of a general game player and comparing the performance with a state-of-the-art player.

In the context of mobile robotics, it is crucial for the robot to have a consistent representation of the surrounding area. However, common grid maps used in robotics do not provide any evidence as to connectivity, making it harder to find appropriate paths to particular points on the site. Therefore, abstracting the environment where mobile robots carry out some mission can be of a great benefit.

In many real-world applications of knowledge representation and reasoning formalisms, one needs to cope with a number of spatial aspects in an integrated and efficient way. In this paper, we focus our attention on the so-called Rectangular Cardinal Direction calculus for qualitative spatial reasoning on cardinal relations between rectangles whose sides are parallel to the axes of a fixed reference system. We show how to extend its convex tractable fragment with metric constraints preserving tractability. The resulting formalism makes it possible to efficiently reason about spatial knowledge specified by one qualitative constraint network and two metric networks (one for each spatial dimension). In particular, it allows one to represent definite or imprecise knowledge on directional relations between rectangles and to derive additional information about them, as well as to deal with metric constraints on the height/width of a rectangle or on the vertical/horizontal distance between the sides of two rectangles. We believe that the formalism features a good combination of simplicity, efficiency, and expressive power, making it adequate for spatial applications like, for instance, web-document query processing and automatic layout generation.

The access to instruments that allow higher autonomy to people is increasing and the scientific community is giving special attention on designing and developing such systems. Intelligent Wheelchairs (IW) are an example of how the knowledge on robotics and artificial intelligence may be applied to this field. IWs can have different interfaces and multimodal interfaces enabling several inputs such as head movements, joystick, facial expressions and voice commands. This paper describes the foundations for creating a simple procedure for extracting user profiles, which can be used to adequately select the best IW command mode for each user. The methodology consists on an interactive wizard composed by a flexible set of simple tasks presented to the user, and a method for extracting and analyzing the user’s execution of those tasks. The results showed that it is possible to extract simple user profiles, using the proposed method.

In this paper, we propose a novel approach on merging the trust distributions of an explorer agent in its advisors with the trust distributions of the advisor agents in a target agent. These two sets of merged distributions represent the trust of different, yet connected, agents in a multi-agent system. The deduced distribution measures an approximation of the explorer agent’s trust in the target agent. The proposed approach can serve as a building block for estimating the trust distribution of an agent of interest in the multi-agent systems, who is accessible indirectly through a set of sequentially connected agents.

A common issue of modelling trust is the presence of uncertainty, which arises in scenarios where there is either lack of adequate information or variability in an agent’s level of trustworthiness. In order to represent uncertainty, possibility distributions are used to model trust of the agents.

In 1997, a minority game (MG) was proposed as a non-cooperative iterated game with an odd population of agents who make bids whether to buy or sell. Since then, many variants of the MG have been proposed. However, the common disadvantage in their characteristics is to ignore the past actions beyond a constant memory. So it is difficult to simulate actual payoffs of agents if the past price behavior has a significant influence on the current decision. In this paper we present a new variant of the MG, called an asset value game (AG), and its extension, called an extended asset value game (ExAG). In the AG, since every agent aims to decrease the mean acquisition cost of his asset, he automatically takes the past actions into consideration. The AG, however, is too simple to reproduce the complete market dynamics, that is, there may be some time lag between the price and his action. So we further consider the ExAG by using probabilistic actions, and compare them by simulation.

Several dialogue types, including inquiry, persuasion and deliberation, transfer information between agents so that their beliefs and opinions may be revised. The speech acts in different dialogue types have different pragmatic implications. For a representative sub-type of persuasion dialogues we consider how they can be conducted efficiently, in terms of minimising the expected transfer of information, and develop a strategy for efficient persuasion by exploiting the pragmatic implications. We demonstrate that our strategy is optimal for this sub-type.

The paper presents the Genoa Artificial Power Exchange, an agent-based framework for modeling and simulating power exchanges implemented in MATLAB. GAPEX allows creation of artificial power exchanges reproducing exact market clearing procedures of the most important European power-exchanges. In this paper we present results from a simulation performed on the Italian PEX where we have reproduced the Locational Marginal Price Algorithm based on the Italian high-voltage transmission network with its zonal subdivisions and we considered the Gencos in direct correspondence with the real ones. An enhanced version of the Roth-Erev algorithm is presented so to be able to consider the presence of affine total cost functions for the Gencos which results in payoff either positive, negative and null. A close agreement with historical real market data during both peak- and off-peak load hours of prices reproduced by GAPEX confirm its direct applicability to model and to simulate power exchanges.

We conduct an experimental study of the effects of manipulations (i.e., dishonest behaviors) including those of manipulation by annexation and merging in weighted voting games. These manipulations involve an agent or agents misrepresenting their identities in anticipation of gaining more power at the expense of other agents in a game. Using the well-known Shapley-Shubik and Banzhaf power indices, we first show that manipulators need to do only a polynomial amount of work to find a much improved power gain, and then present two enumeration-based pseudopolynomial algorithms that manipulators can use. Furthermore, we provide a careful investigation of heuristics for annexation which provide huge savings in computational efforts over the enumeration-based method. The benefits achievable by manipulating agents using these heuristics also compare with those of the enumeration-based method which serves as upper bound.

Applications of biological or biologically inspired multi-agent systems (MAS) often assume a certain level of reliability and robustness, which is not always straightforward. Formal modelling and verification of MAS may present many interesting challenges. For instance, formal verification may be cumbersome or even impossible to be applied on models with increased complexity. On the other hand, the behaviour of MAS consists of communities evolving in space and time (such as social insects, tissues, colonies of bacteria, etc.) which are characterised with a highly dynamic structure. In order to provide a neat and effective way to modelling and verification of these systems, we focus on their spatial characteristics. Spatial agents (i.e. agents distributed and moving through a physical space) can be modelled with X-machines – one of the most prominent formalisms for modelling the behaviour of biological colonies. However, it will be demonstrated that there are certain problems in the X-machines models, common to every spatial MAS. To overcome these disadvantages, we introduce an X-machines variation that besides facilitating formal modelling, will provide grounds towards visual animation of these systems. This approach resulted into a novel progression, Spatial X-machines ( ^sp XM), without retracting the legacy characteristics of X-machines such as testing and verification strategies. Finally, we present a supporting framework to modelling and verification of spatial multi-agent system, by utilizing the Spatial X-machines approach.

During dialog, humans are able to track ongoing topics, to detect topical shifts, to refer to topics via labels, and to decide on the appropriateness of potential dialog topics. As a result, they interactionally produce coherent sequences of spoken utterances assigning a thematic structure to the whole conversation. Accordingly, an artificial agent that is intended to engage in natural and sophisticated human-agent dialogs should be endowed with similar conversational abilities. This paper presents how to enable topically coherent conversations between humans and interactive systems by emulating humanlike topic awareness in the virtual agent Max. Therefore, we firstly realized automatic topic detection and tracking on the basis of contextual knowledge provided by Wikipedia and secondly adapted the agent’s conversational behavior by means of the gained topic information. As a result, we contribute to improve human-agent dialogs by enabling topical talk between human and artificial interlocutors. This paper is a revised and extended version of [1].

During the past years, the cloud vision at distributed systems progressively became the new trend for the next generation platforms. The advance in the technology, both with the broadband availability and the explosion of mobile computing, make the massive migration to cloud solution next to be a fact. The Cloud model assures a new technologic and business environment for services and applications where competitiveness, scalability and sustainability converge. On the other hand, next generation applications have to be able to pervasively meet the needs and requirements deeply different among them. Applications involving complex virtual organizations require a higher level of flexibility. An effective approach is based on the convergence between migration and virtualization. The resource-centric model assumes file systems, DBs, services and any other class of resources available in the "cloud" as Virtual Resources. These heterogeneous resources can be managed in a unique virtual context regardless by the infrastructures on which they are deployed. Semantics play a critical role in order to assure advanced and open solutions in a technologic context featured by a fundamental lack of standardization.

We propose an alternative approach to find each robot’s unique communication strategies. In this approach, the human manipulator behaves as if she/he becomes the robot and finds the optimal communication strategies using attachable and detachable robot’s shapes and modalities. We implement the system including a reconfigurable body robot, an easier manipulation system, and a recording system to evaluate the validity of our method. We evaluate a block-assembling task by the system by turning on and off the modality of the robot’s head. Subsequently, the robot’s motion during player’s motion significantly increases whereas the ratio of confirmatory behavior significantly decreases in the head-fixed design. In this case, the robot leads the users and the user follows the robot as in the turn-taking communication style of the Head-free condition.

Most robotic systems are usually used and evaluated in laboratory setting for a limited period of time. The limitation of lab evaluation is that it does not take into account the different challenges imposed by the fielding of robotic solutions into real contexts. Our current work evaluates a robotic telepresence platform to be used with elderly people. This paper describes our effort toward a comprehensive, ecological and longitudinal evaluation of such robots. Specifically, the paper highlights open points related to the transition from laboratory to real world settings. It first discusses some results from a short term evaluation performed in Italy, obtained by interviewing 44 healthcare workers as possible clients (people connecting to the robot) and 10 older adults as possible end users (people receiving visits through the robot). It then describes a complete evaluation plan designed for a long term assessment also dwelling on the initial application of such methodology to test sites, finally it introduces some technical features that could enable a more robust real world deployment.