Masteroppgaven presenterer en litteraturstudie på sammenligning mellom globale og lokale inverterte filer, samt alternative metoder som samlebåndsbaserte prosessering av globale inverterte filer og hybride inverterte filer. Arbeidet ble videreført med en simuleringsmodel som ble brukt til å utføre en rekke eksperimenter for metodene beskrevet i oppgaven. En virkelig dokumentsamling og en virkelig lastsamling ble brukt under eksperimenter. Resultater fra simuleringsmodellen ble diskutert mot de mest sentrale resultatene som presentert i litteraturstudiet.

This paper is a master thesis for the Department of Computer and Information Science at the Norwegian University of Science and Technology, spring 2008. It is a study of hole filling in three dimensional surface models obtained from scanned real world objects. The goal of this project is to find solutions that are capable of filling an incomplete model in a plausible and visually pleasing manner. To reach this goal both theoretical studies and practical testing were performed. This paper presents a theoretical foundation, needed to gain a greater understanding of the problem, and the results from the testing phase. This knowledge and experience is then used to present a possible solution to the hole filling problem. The conclusions of this project is that automatic procedures, that are thoroughly documented in the literature, fails to perform in a satisfactory manner when the data set becomes too complicated. The Nidaros Cathedral is such a difficult data set, and will require a customized and user guided solution to met the goals of this project.

Visualization of porous media is of great importance to several scientific fields, including the petroleum technology. The topic of this thesis arises from our collaborations with The Center for Integrated Operations in the Petroleum Industry. By being able to quickly analyze properties of porous rocks, they can get a better understanding of how to efficiently harvest oil since oil is typically held and stored within rock pores. The petroleum industry typically uses Computed Tomography (CT) technology to scan rock samples for their internal structures. The resulting data is loaded into a computer program that generates 3D models of the rocks describing the 3D nature of its' internal structure. The scan data created from these scans will in most case contain inaccuracies due to artifacts created while scanning. In this thesis, we develop an application that interactively helps the user localizes the rock and pores in the CT scan data, allowing the user to create an image with a more accurate representation of the pores. We use digital image processing techniques to do an initial localization of the elements in the scan. The artifacts are then reduced by allowing the user to drag and pull on the line-data specifying the pores. Our implementation then uses this new representation to construct a 3D volume image that can be used in geophysical applications, like Schlumberger Petrel, for further analysis and simulation. The volume rendering part of our implementations builds directly on the authors project work with Eirik Ola Aksnes on GPU Techniques for Porous Rock Visualization completed last fall (2008).

In this thesis, we develop a meta-reasoning system based on CBR which solves sliding-block puzzles. The meta-reasoning system is built on top of a search-based sliding-block puzzle solving program which was developed as part of the specialization project at NTNU. As part of the thesis work, we study existing literature on automatic puzzle solving methods and state space search, as well as the use of reasoning and meta-level reasoning applied to puzzles and games. The literature study forms the theoretical foundation for the development of the meta-reasoning system. The meta-reasoning system is further enhanced by adding a meta-control cycle which uses randomized search to generate new cases to apply to puzzles. In addition, we explore several ways of improving the underlying solver program by trying to solve hard puzzles by using the solution for easier variants, and by developing a more memory-efficient way of representing puzzle configurations. We evaluate the results of our system, and shows that it offers a slight improvement compared to solving the puzzles with a set of general cases, as well as showing vast improvement for a few isolated test cases, but the performance is slightly behind the hand-tuned parameters we found in the specialization project. We conclude our work by identifying parts of our system where improvement can be done, as well as suggesting other promising areas for further research.

This report will explore behavior-based robotics and relevant AI techniques. A system for autonomous control of mobile robots inspired by behavior-based robotics, in particular Rodney Brooks' subsumption architecture, have been implemented, adapted for use in a multiagent environment. The system is modular and flexible, allowing for easy addition and removal of system parts. A weight-based command fusion approach is taken to action selection, making it possible to satisfy multiple behaviors simultaneously.

This project report describes a hybrid genetic algorithm that works as a schedule generator for a complex robotic harvesting task. The task is set to a dynamic environment with a robotic opponent, making responsiveness of the planning algorithm particularly important. To solve this task, many previous scheduling algorithms were studied. Genetic algorithms have successfully been used in many dynamic scheduling tasks, due to their ability to incrementally adapt and optimize solutions when changes are made to the environment. Many of the previous approaches also used a separate heuristic to quicly adapt solutions to the new environment, making the algorithm more responsive. In addition, the study of previous work revealed the importance of population diversity when making a responsive genetic algorithm. Implementation was based on a genetic algorithm made as the author's fifth year specialization project for solving a static version of the same task. This algorithm was hybridized with a powerful local search technique that proved essential in generating good solutions for the complex harvesting task. When extending the algorithm to also work in a dynamically changing environment, several adaptations and extensions needed to be made, to make it more responsive. The extensions and adaptations include a fast-response heuristic for immediate adaptation to environmental changes, a decrease in genotype size to speed up local searches and a contingency planning module intending to solve problems before they arise. Experiments proved that the implemented dynamic planner successfully adapted its plans to a changing environment, clearly showing improvements compared to running a static plan. Further experiments also proved that the dynamic planner was able to deal with erroneous time estimates in its simulator module in a good way. Experiments on contingency planning gave no clear results, but indicated that using computational resources for planning ahead may be a good choice, if the contingency to plan for is carefully selected. As no unequivocal results were obtained, further studies of combining genetic algorithms and contingency planning may be an interesting task for future efforts.

Sosial interaksjon er en nødvendig ting i dagens samfunn, og folk vi gjerne vite hvor vennene deres er. Denne oppgaven beskriver et system som kan motta lokasjonsinformasjon fra brukere og sender den ut til ønskede parter. Systemet er inndelt i forskjellige soner hvor hver er knyttet opp mot et fysisk område. En bruker har en hjemme-sone som har ansvar for alltid å holde den nyeste informasjonen til brukeren, sånn som hvem det er som skal ha lokasjonsoppdateringene han sender inn. Når en bruker beveger seg på tvers av soner vil den nødvendige informasjonen til brukeren blir sendt med til den nye sonen han går inn i for at den nye sonen kan være ansvarlig for å sende ut all informasjon. Men hjemmesonen har fortsatt oversikt over hvor brukeren er, og er ansvarlig i en situasjon hvor en bruker beveger seg på tvers av to soner så den nye sonen får riktig informasjon og passer på at den gamle sonen blir fortalt at brukere har forlatt den.

A summary is a shortened version of a text that contains the main points of the original content. Automatic summarization is the task of generating a summary by a computer. For example, given a collection of news articles for the last week an automatic summarizer is able to create a concise overview of the important events. This summary can be used as the replacement for the original content or help to identify the events that a person is particularly interested in. Potentially, automatic summarization can save a lot of time for people that deal with a large amount of textual information. The straightforward way to generate a summary is to select several sentences from the original text and organize them in way to create a coherent text. This approach is called extraction-based summarization and is the topic of this thesis. Extraction-based summarization is a complex task that consists of several challenging subtasks. The essential part of the extraction-based approach is identification of sentences that contain important information. It can be done using graph-based representations and centrality measures that exploit similarities between sentences to identify the most central sentences. This thesis provide a comprehensive overview of methods used in extraction-based automatic summarization. In addition, several general natural language processing issues such as feature selection and text representation models are discussed with regard to automatic summarization. Part of the thesis is dedicated to graph-based representations and centrality measures used in extraction-based summarization. Theoretical analysis is reinforced with the experiments using the summarization framework implemented for this thesis. The task for the experiments is query-focused multi-document extraction-based summarization, that is, summarization of several documents according to a user query. The experiments investigate several approaches to this task as well as the use of different representation models, similarity and centrality measures. The obtained results indicate that use of graph centrality measures significantly improves the quality of generated summaries. Among the variety of centrality measure the degree-based ones perform better than path-based measures. The best performance is achieved when centralities are combined with redundancy removal techniques that prevent inclusion of similar sentences in a summary. Experiments with representation models reveal that a simple local term count representation performs better than the distributed representation based on latent semantic analysis, which indicates that further investigation of distributed representations in regard to automatic summarization is necessary. The implemented system performs quite good compared with the systems that participated in DUC 2007 summarization competition. Nevertheless, manual inspection of the generated summaries demonstrate some of the flaws of the implemented summarization mechanism that can be addressed by introducing advanced algorithms for sentence simplification and sentence ordering.

This thesis investigates the application of artificial neural networks (ANNs) for forecasting financial time series (e.g. stock prices).The theory of technical analysis dictates that there are repeating patterns that occur in the historic prices of stocks, and that identifying these patterns can be of help in forecasting future price developments. A system was therefore developed which contains several ``agents'', each producing recommendations on the stock price based on some aspect of technical analysis theory. It was then tested if ANNs, using these recommendations as inputs, could be trained to forecast stock price fluctuations with some degree of precision and reliability.The predictions of the ANNs were evaluated by calculating the Pearson correlation between the predicted and actual price changes, and the ``hit rate'' (how often the predicted and the actual change had the same sign). Although somewhat mixed overall, the empirical results seem to indicate that at least some of the ANNs were able to learn enough useful features to have significant predictive power. Tests were performed with ANNs forecasting over different time frames, including intraday. The predictive performance was seen to decline on the shorter time scales.

Abstract. This master thesis presents the results from investigating usage patterns on portable devices and finding gamers attitudes towards different pervasive game elements.The main motivation of this project is to help developers create a better game experience with the use of pervasive elements and mobile technology, finding some pointers as to what players are likely to enjoy (or not). At the same time, the usage patterns will help us understand how players currently use games, which is important information creating games tailored to the players usage patterns. The results for usage patterns shows that game sessions are usually very short. We found that most people do not utilize multiplayer functionality in games on portable platforms. Investigating why players play games on portable devices, we found that quite many only use games as a secondary activity. Often, playing on portable devices are a result of some other main activity, like for example waiting for some form of transport in real life. To better understand what types of pervasive games users would be interested in, we proposed four concepts and asked the participants for their opinions of these concepts. Of the concepts proposed, the most popular concepts were one in which the game used the users geographic location to create questions from the nearby area and a concept where the game used proximity to other players as a part of the gameplay. Generally, we saw that players liked the idea of playing games with others in teams, and often as a planned event where people meet up to play.To understand what elements are likely to be successful, we studied attitudes towards the different categories of game elements. Some elements, like visual and sound feedback are staples of modern games, and therefore a necessity. Another popular output method is force feedback, in which the game shakes the controller or in other ways provide tactile feedback. Social elements were the most popular, competitive and cooperative game styles along with chat/communication abilities are important to players. Players also wish to be able to play anywhere and be able to start and stop playing at any time.