Repositório RCAAP

Real-time strategy Games (RTS) are an important field of research in artificial intelligence planning. In these games, we have to deal with characteristics that present challenges for the planning, such as time constraints, numerical effects and actions with many preconditions. RTS games are characterized by two important phases. The first, where is necessary gather resources and build an army via resource production. In the second, the resources produced in the first phase are used in battles involving defense and attack against the enemy. Thus, the first phase becomes vitally important for the success of the player within the game, and maximize the production of resources to elevate the maximum power of the army developed, reflects directly on the chances of victory. This research is focused on the first phase of the game. To maximize the amount of resources produced in the game is necessary to determine goals that produce resources such scale, considering quality goals. Large part of the works in planning for games not consider the search for goals that have quality or criteria that benefit planning for use within the game. Thus, to stipulate goals we propose an approach that maximizes the resource production using Simulated Annealing (SA) along with planning techniques. The approach uses stochastic search to maximize production of resources generating plans of action that produce such resources within the game and can be considered as goals with quality planning to be achieved. For the correct operation of this work, the SA was adapted to operate on the domain of real time, and have also been developed planners and consistency checkers to assist it in this task. As a result, the approach was efficient in its use within the environment of an RTS game, where the resource production was able to match with human players during testing. Thus, this research aims to fill a gap present in related works of planning for RTS games, in relation to the production of resources based on criteria.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior

The objective of this work is to present an approach based onWorkFlow net and Linear Logic for the design process of video games. The main idea consists of representing the scenarios existing at a quest level by a particular type of Petri net called WorkFlow net. A kind of qualitative analysis based on the proof trees of linear logic can then be performed in order to prove the correctness of the soundness property which corresponds to a consistent quest from the point of view of the game. The quantitative analysis is concerned with the planning of the gameplay time of a quest. It is base on version of t-time WorkFlow nets and symbolic date calculation derived from the sequent calculus of linear logic. An extended version of the WorkFlow nets which allows the inclusion of discrete resources permits representing in a formal way, the dierent items that the player can nd and use during the quests of the game. Parts of the game The Legend of Zelda: Oracle of Ages are used to illustrate the proposed approach.

The popularization of electronic devices to capture digital images, as well as the creation of several applications enabling exchange and sharing these images by communication channels has brought some inherent problems. Among these problems it can be cited the security violation and privacy in information systems. The use of cryptographic systems in such information transmission is required to solve these issues. The main goal of cryptography is to guarantee that the information will not be copied, modied or falsied. Many classic and modern encryption algorithms have been investigated to ensure secure exchange of information. However, when the message to be sent is an image, the conventional algorithms do not favor image structural features: the spatial arrangement and the massive amount of information. Thus, a new approach for this topic is the usage of cellular automata (CA) in image encryption. CA are being studied due to their implementation simplicity and also due to their capacity to process data in a fast parallel way. In this work a novel cryptographic model based on three-dimensional hybrid cellular automata was elaborated and named 3DHCA. This method employs pre-image calculus which represents CA backward evolution and two rules are used in the encryption process. The rst one is called major rule, and it is responsible for the eective encryption of the message. The second one is used only in boundary lattice cells to ensure the existence of pre-image for any lattice. This three-dimensional model is based on a precursor model called HCA, which uses one-dimensional CA. Initially, an analysis of one-dimensional model safety was performed using Graph Theory. The denition of the new three-dimensional cryptographic model, as well as experiments for its validation and renement are discussed in this dissertation. The resulting method has proved to be safe and appropriated for an implementation with a high-level of parallelism. Thus, it becomes a very interesting option for encryption using large volumes of data, especially digital color images.

Bag-of-visual-features is a well-known approach for pattern classication and contentbased image retrieval. The entire image is described by a normalized histogram of frequencies of visual words. In this case, objects of interest on large background area or on dierent background scenes, may not be correctly recognized. In this work we propose to extract the relevant scenes of the image (foreground) according to the human being visual perception using the saliency map approach. In our proposal, the histogram is built on weight visual words according to the saliency map on two approaches, fuzzy and binary, to incorporate a distinguish between information of background and foreground. Our method was tested on databases that contain images with dierent conditions of illumination, color, rigid and scale transformations, and changes of the background. The analysis of the results demonstrates that our proposal presents signicant improvements over other tested approaches.

Contemporary organizations use information technology to support activities and possibly automate processes due to its complexity and variety. Systems Business Process Management significantly influence the way companies organize work, besides forcing them to adjust their business processes to them, allowing the occurrence of various problems. One of the principal is the incompatibility between the preferred way of the work of company employees and the way the system process management organizes the sequencing of activities, forcing them to work very often "outside the system" by running business processes "inadequate" compared to the model set by the management system. The objective of this work is to propose a new model of the business process based on WorkFlow nets and on possibilistic Petri nets". The routing patterns in existing business processes are modeled by WorkFlow nets, and to express in a more realistic way the uncertainty attached to human activities, possibilistic Petri nets" with uncertainty on the marking and on the transition firing are considered. The proposed approach focuses on flexibility by deviation from the perspective of the control flow and is able to deal with the inconsistencies between the process model and the execution, generated by human actors. The process Service Complaint", where human actors are involved in the process activities, and two examples of deviations arising from the control flow are used to illustrate the approach. The markings and firings uncertain allow deviate so that no blockage occurs in the state of the process and the model is not changed. The advantage of this approach is the maintenance of good properties in the model of the process, because the "classical Petri nets" is not modified; therefore the classical methods for analyzing processes remain valid. Furthermore, through the defuzzification of knowledge, it is possible to formalize the deviation through the sequence of activities that have not been executed, but should have been.

The specication, analysis and design of real-time systems (RTS) are activities that are highly dependent on an eective understanding of the application domain and on the completeness of the representation of their primordial requirements. The use of modelbased approaches for the development of RTS systems tend to contribute to minimizing the complexity of the system development process. The UML has been strongly used in recent years for modeling real-time software. However, UML alone does not represent with completeness important characteristics of these systems, such as timing requirements. UML is a language that has several extensions capabilities enabling the creation of specic proles. This work will explore the use of UML proles SysML and MARTE to modeling software requirements of RTS for the control of road trac. The main objective is to demonstrate the application of SysML with MARTE stereotypes, which enables the modeling, representation, classication, documentation and, also, for dened criteria of traceability of real-time software requirements. The proposed approach was shown to be relevant in the context of the specication, analysis, classication and modeling requirements for real-time systems. The SysML Requirements diagram shows explicitly the various types of relationships between dierent requirements, increasing the spectrum of understanding and dening the requirements of a real-time system. The MARTE prole complemented the precision of scenario with functional non annotations well formed, in general timing requirements. The concepts of SysML and MARTE, articulated in the SysML Requirements diagram are highly complementary covering many of the purposes of specifying requirements for real-time systems.

Conselho Nacional de Desenvolvimento Científico e Tecnológico

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior

The objective behind this study is the proposal of a Draughts learning system, D-MA-Draughts (Distributed Multi-agent Draughts): a multi-agent Draughts player that operates in high performance environments. D-MA-Draughts is based on the integration and refinement of two other successful automatic Draughts architectures: MP-Draughts and D-VisionDraughts. The first is a multi-agent system, which does not operate in a high performance environment, and the second is a mono-agent system, which operates in a high performance environment. The D-MA-Draughts player, in particular aided in enhancing the MP-Draughts player with respect to the dynamics of the interaction between the agents. Similarly, it increases the performance of D-VisionDraughts by augmenting the accuracy with which it represents the boards along with an increase in the number of processors pertaining to the environment. The D-MA-Draughts player is composed of 26 agents, with one denominated as IIGA (Initial Intermediate Game Agent), which is a specialist in initial and intermediary game states and 25 agents specializing in end game states. Each of these agents consists of a multi-layer neural network (MLP), which was trained through the use of Temporal Difference Methods (λ), in a distributed processing environment, in order to achieve a high performance level with the minimum of human intervention possible, unlike the automatic player of Draughts world champion, Chinook. The search for the best move is guided by the distributed search algorithm denominated as, Young Brothers Wait Concept (YBWC). The board states are represented by NET-FEATUREMAP mapping, which is composed of functions that describe features inherent to the game of Draughts. The specialist agents in the end game states were trained to deal with a specific type of board profile\" of end game states (cluster). These clusters were obtained through Kohonen-SOM networks from a data base with end game board states obtained from real life matches. Once trained, the D-MA-Draughts agents are able to operate in a match by following two dynamics of the game. In both of these dynamics the IIGA agent will start the match. From this point they will vary as follows: in the first, once the board state characterized as the end game has been reached the Kohonen-SOM network will appoint the agent (from within the end game agents), which represents the cluster whose profile\" is closest to the current board state. From here on, agents of this type will substitute the IIGA and conduct the match until the end. In the second dynamic, each time that the automatic system executes a movement in an end game situation, the Kohonen-SOM network will be activated to indicate, which of the end game agents has the most adequate profile\" for the current end game state. This study shows that by using the proposed architecture D-MA-Draughts managed to improve the performance achieved by its predecessors. Such improvements are due to the greater accuracy with which the board states are perceived by the agents allowing them to make more precise decisions. On the other hand, improving the board representation leads to an increase in the system\'s processing load. In this context, the increase in the number of processors circumvented this situation besides contributing to a deeper player future vision or look-ahead during the search, which made it more suitable in choosing the best moves.

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior

The game of Go is very ancient, with more than 4000 years of history and it is still popular nowadays, representing a big challenge to the Articial Intelligence. Despite its simple rules, the techniques which obtained success in other games like chess and draughts cannot handle satisfactorily the complex patterns and behaviours that emerge during a match of Go. The present work implements the SDM-Go, a competitive agent for Go that seeks to reduce the usage of supervision in the search process for the best move. The SDMGo utilizes the sparse distributed memory model as an additional resource to the Monte- Carlo tree search, which is used by many of the best automatic Go players nowadays. Based upon the open-source player Fuego, the use of the sparse distributed by SDM-Go has the purpose of being an alternative to the strong supervised process used by Fuego. The Monte-Carlo tree search executed by agent Fuego uses a set of heuristics codied by human professionals to guide the simulations and also to evaluate new nodes found in the tree. In a dierent way, SDM-Go implements a non-supervised and domain independent approach, where the history of the values of board states previously visited during the search are used to evaluate new boards (nodes of the search tree). In this way, SDM-Go reduces the supervision of Fuego, substituting its heuristics by the sparse distributed memory, which works as a repository for the information from the history of visited board states. Thus, the contributions of SDM-Go consist of: (1) the utilization of a sparse distributed memory to substitute the supervised approach of Fuego to evaluate new nodes found in the search tree; (2) the implementation of a board state representation based on bit vectors, in order to not compromise the performance of the system due to the boards stored in the memory; (3) the extension of the usage of the Monte-Carlo simulation results to update the values of the board states stored in the memory. Distinctly from many other existing agents, the use of the sparse distributed memory represents an approach independent of domain. The results obtained in tournaments against the well known open-source agent Fuego show that SDM-Go can perform successfully the task of providing a non-supervised and independent of domain approach to evaluate new nodes found in the search tree. Despite the longer runtime required by the use of the sparse distributed memory, the core of the agent performance, SDM-Go can keep a competitive level of play, especially at the 9X9 board.

Conselho Nacional de Desenvolvimento Científico e Tecnológico

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior

The huge amount of information available on the web has bothered users to select items that meet their needs . The Recommender Systems emerged as indispensable tools in this information overload scenario in order to lter out what is of interest to the user and allow him to have a dierentiated experience with existing information systems. We present a methodology for developing recommendation systems, using mining algorithms preferences: PrefRec. We aim at building Recommender Systems that have good values of accuracy and allowing a more satisfying interaction to the user, from the validation measures of accuracy, coverage, novelty and serendipity. The use of algorithms for mining preferences objectively understand the user\'s preferences about the characteristics of the items, achieving more accurate recommendations. In the case study implemented, the Recommendation System XPrefRec, we apply a mining algorithm from a special type of contextual preferences in order to dene the user preferences on a certain context. We also analyzed what are the factors that inuence the methodology proposed in the Recommendation System performance and presents the comparison of the performance of this system with the state of the art regarding Hybrid Recommender Systems.

The traditional preference mining setting, referred to here as the batch setting, has been widely studied in the literature in recent years. However, the dynamic nature of the problem of mining preferences increasingly requires solutions that quickly adapt to change. The main reason for this is that frequently user\'s preferences are not static and can evolve over time. In the work described in this master\'s thesis, we address the problem of mining contextual preferences in the data stream setting. Contextual Preferences have been recently treated in the literature and some methods for mining this special kind of preferences have been proposed in the batch setting. As main contributions of the work described in this master\'s thesis, we formalize the contextual preference mining problem in the data stream setting and propose three algorithms for solving this problem. In addition, we also propose a formalism about concept drift in contextual preferences. We have implemented two of the proposed algorithms and showed their eciency through an extensive set of experiments over real and synthetic data (with and without concept drift).

For decades, several planning systems have been proposed in order to nd solutions to many of the dierent problems encountered in everyday life. However, only in recent years, have planning systems started to obtain satisfactory results through the use of search methods for building plans. As a successful planner, Fast Forward combines the execution of two search methods, Enforced Hill Climbing and Best First Search. Techniques introduced by Fast Forward have also been applied in many other recent planners. Although Fast Forward strategy presents an enhanced performance when compared to alternative methods, it shows some weaknesses. For some planning problems Enforced Hill Climbing cannot escape from local maxima/minima, which means it might get stuck at dead ends, thus leading to a failure. In the event of such occurrences, a complete search is performed by Best First Search, which may fail due to lack of memory space. Note that these troubles could aect any search algorithm. This paper describes the development of a planner, called SLPlan, based on optmized versions of the algorithms Enforced Hill Climbing and Learning Real-Time A* that aim to reduce the impact of the troubles cited before in order to build plans more eciently. Besides, the application of planning techniques in solving relevant problems is of particular concern for the planning community. The generation of business processes ( work- ow) is one of the areas that can benet from the use of planning. This dissertation also species how SLPlan was applied to the automatic generation of business processes models.

Presently doctors and medical professionals are having the aid of support systems for diagnosis which include in their data base expertise knowledge, acquired mainly through empirical observation of heuristics applied to their diagnosis which translate partially, to the technical application used. In the systems which aid diagnosis, more specifically in electrocardiograms, the methods of pattern recognition simulate the skills of the cardiologist, when, from a set of characteristics extracted from the signal, it is possible to infer a determined heart condition, indicated by some cardiopathy. The electrocardiogram signal constitutes the measurement of the electrical activity associated with the heart and this process uses the algorithm which presents some difficulties: the variation of wave morphology, physiological conditions and the presence of noise. The utilization of wavelet transforms may represent a valuable tool for analyzing ECG, once they allow by means of the function mother wavelet, to enhance of the wave forms which integrate the electrocardiogram register. This research proposes the utilization of continuous wavelet transforms to detect the occurrence of waves which are part of an electrocardiogram, more specifically the QRS and waves P and T.