In this thesis we present an algorithm that is designed to improve the collaborative capabilities of agents that operate in real-time multi-agent systems. Furthermore, we study the coalition formation and task assignment problems in the context of real-time strategy games. More specifically, we design and present a novel anytime algorithm for multi-agent cooperation that efficiently solves the simultaneous coalition formation and assignment problem, in which disjoint coalitions are formed and assigned to independent tasks simultaneously. This problem, that we denote the problem of collaboration formation, is a combinatorial optimization problem that has many real-world applications, including assigning disjoint groups of workers to regions or tasks, and forming cross-functional teams aimed at solving specific problems. The algorithm's performance is evaluated using randomized artificial problems sets of varying complexity and distribution, and also using Europa Universalis 4 – a commercial strategy game in which agents need to cooperate in order to effectively achieve their goals. The agents in such games are expected to decide on actions in real-time, and it is a difficult task to coordinate them. Our algorithm, however, solves the coordination problem in a structured manner. The results from the artificial problem sets demonstrates that our algorithm efficiently solves the problem of collaboration formation, and does so by automatically discarding suboptimal parts of the search space. For instance, in the easiest artificial problem sets with 12 agents and 8 tasks, our algorithm managed to find optimal solutions after only evaluating approximately 0.000003% of the possible solutions. In the hardest of the problem sets with 12 agents and 8 tasks, our algorithm managed to find a 80% efficient solution after only evaluating approximately 0.000006% of the possible solutions. / I denna uppsats presenteras en ny algoritm som är designad för att förbättra samarbetsförmågan hos agenter som verkar i realtidssystem. Vi studerar även koalitionsbildnings- och uppgiftstilldelningsproblemen inom realtidsstrategispel, och löser dessa problem optimalt genom att utveckla en effektiv anytime-algoritm som löser det kombinerade koalitionsbildnings- och uppgiftstilldelningsproblemet, inom vilket disjunkta koalitioner formas och tilldelas uppgifter. Detta problem, som vi kallar samarbetsproblemet, är en typ av optimeringsproblem som har många viktiga motsvarigheter i verkligheten, exempelvis för skapandet av arbetsgrupper som skall lösa specifika problem, eller för att ta fram optimala tvärfunktionella team med tilldelade uppgifter. Den presenterade algoritmens prestanda utvärderas dels genom att använda simulerade problem av olika svårighetsgrad, men också genom att använda verkliga problembeskrivningar från det kommersiella strategispelet Europa Universalis 4, vilket är ett spel som agenter måste samarbeta i för att effektivt uppnå deras mål. Att koordinera agenter i sådana spel är svårt, men vår algoritm åstadkommer detta genom att systematiskt söka efter de optimala agentgrupperingarna för ett antal givna uppgifter. Resultaten från de simulerade problemen visar att vår algoritm effektivt löser samarbetsproblemet genom att systematiskt sålla bort suboptimala delar av sökrymden. I dessa tester lyckas vår algoritm generera högkvalitativa anytime-lösningar. Till exempel, i de enklaste problemen med 12 agenter och 8 uppgifter lyckas vår algoritm hitta den optimala lösningen efter det att den endast utvärderat 0.000003% av de möjliga lösningarna. I de svåraste problemen med 12 agenter och 8 uppgifter lyckas vår algoritm hitta en lösning som är 80% från den optimala lösningen efter det att den endast utvärderat 0.000006% av de möjliga samarbetsstrukturerna.

No description available.

Software development is a demanding task where developers face great challenges. Development tools are expected to be user-friendly. However, little research has been done to understand developers’ needs and priorities when it comes to such tools, so called Integrated Development Environments (IDEs). It is important to gain a better insight into developers’ prioritization of IDE qualities, in order to be able to make such tools more efficient and better tailored to their users’ real needs. The objective of this thesis is to gain a deeper understanding of software developers’ perspective regarding IDEs with the goal of facilitating further improvements of these tools. This thesis report presents the results of a quantitative survey, responded by twenty professional software developers, which focuses on developers’ prioritization of qualities in adopted IDEs and their perceived satisfaction with the qualities themselves and the IDEs overall. Moreover, we investigate whether limiting developers’ choice of IDE also affects their overall satisfaction of chosen IDEs. By analyzing the results, we conclude that developers perceive reliability, ease of use and efficiency as, on one hand the most important qualities of IDEs, and on the other hand those most in need of improvements. The results also suggest that developers’ satisfaction with their IDEs is not significantly affected by limiting their choice of development tools.

Students often voice that the programming assignments are hard and that they spend a lot of time on solving them. Is this true; are we giving them too hard assignments and how much and what do they spend the time on? This is what we want to gain insight to. We constructed a tool that records programming sessions with finer granularity than the existing solutions. The tool has recorded 2643 programming sessions from students. Using that data we found that students spend only 15% of their time writing code, and that on average 40% of their programming effort is spent reading and navigating. We also estimate the time spent outside of the tool to be almost 20%. The increased detail in the recordings can be used to measure the effect of programming source code comments, and we found that the effect of both helpful and redundant comments increases the reading time but did not help to reduce the students writing effort. Finally, we used the tool to examine the effects of an improved programming assignment and found that the total effort was not reduced.

As computers are developing rapidly and become more available to the modern information society, the possibility and ability to handle large data sets in database applications increases. The demand for efficient algorithmic solutions to process huge amounts of information increases as the data sets become larger. In this thesis, we study the efficient implementation of aggregate operations on the data cube, a modern and flexible model for data warehouses. In particular, the problem of computing the k largest sum subsequences of a given sequence is investigated. An efficient algorithm for the problem is developed. Our algorithm is optimal for large values of the user-specified parameter k. Moreover, a fast in-place algorithm with good trade-off between update- and query-time, for the multidimensional orthogonal range sum problem, is presented. The problem studied is to compute the sum of the data over an orthogonal range in a multidimensional data cube. Furthermore, a fast algorithmic solution to the problem of maintaining a data structure for computing the k largest values in a requested orthogonal range of the data cube is also proposed. / <p>Godkänd; 2004; 20070131 (ysko)</p>

<p>Godkänd; 1990; 20080410 (ysko)</p>

One of the many challenges with interface design concerns how to present and retrieve information on a display. The smaller the display is, the bigger the challenge. A typical task that requires a lot of screen space is image browsing. Several studies have been conducted in the past, but with conflicting results. This thesis includes a literature survey on browsing techniques, two user studies comparing image-browsing techniques on an electronic bulletin board, an analysis of visual factors affecting the usability of image browsing, and a user study on mobile phone interfaces. The image-browser comparisons involved three types of browsers (iconic, bifocal, and zoom-and-pan). The first experiment was conducted on a regular 19" desktop display. For the second user study, the browsers were modified and run on a 50" plasma display with a 3D input device. Results from both studies showed that an iconic interface was most efficient. Observations made during the user experiments resulted in an analysis of layout and presentation factors that have an impact on usability of image-browsers, in particular task completion time. The main purpose was to identify unwanted confounding factors in image-browser tests, but the analysis could also be used for setting up future experiments and explaining results from such tests. The mobile phone study is a comparison of interfaces of two different mobile brands. Displays and user interfaces for mobile phones have developed a lot since this study was conducted, but design for small displays is still a highly relevant topic. / <p>Godkänd; 2007; 20071201 (ysko)</p>

This thesis deals firstly with ways to solve the problem of limited resource reservations over time, and secondly, handling conforming traffic in routers. At first glance these topics seem a bit unrelated, they are both related to quality of service (QoS) on the Internet and are cases of Algorithm Engineering applied in the field of Computer Networking. In order to provide Quality of Service (QoS) for the users of mainly real time applications on the Internet, the need to make a reservation of bandwidth over the Internet has arisen. The idea of QoS is to provide the same quality of the service on the Internet as it is provided in the ordinary circuit switched telephone network. This means that an opened connection will never be disturbed by another connections no matter how many users there are using the phone network at the same time. Internet on the other hand is a packet switched network. That is a network in which small packets with address tags are transported from the source to the destination by several connected subnetworks. On the Internet there are no guarantees regarding unchangeable quality of service; packets may be dropped, delayed or reordered depending on the current load. This is undesirable for users of real time applications. One solution to achieve QoS on the Internet can be to reserve sufficient amount of bandwidth for a time period of resource use --- for instance, the time of a phone call. Olov Schelén et.al. used the differentiated services approach to design a new architecture to provide QoS called "bandwidth brokers". In this architecture they provide virtual leased lines using the differentiated services to perform admission control through a system of bandwidth brokers. The bandwidth brokers work on per-hop basis and each bandwidth broker needs to maintain a database of the reservations made on its hop. It must be quick to: insert more reservations in the database remove reservations already made to query the amount of reserved bandwidth during a given interval in order to see if another reservation can be made so that not more bandwidth are reserved than the link capacity can carry. We talk about a "Bandwidth Reservation Problem" ("BRP"). Our solution to the problem is more general than just to be used with the bandwidth brokers. In the thesis I present two different solutions to the BRP; one static data structure using constant space and O(log n) worst case time for all operations, and a dynamic solution using Theta(n) space and Theta(log n) time for all operations, where n is the number of leaves in the tree. Note that the running time of the operations are not depending on the number of reservations, connections, or amount of reserved bandwidth. I also present an application of the dynamic solution in the field of chemistry where it is used to analysis of large spectral data sets. I also present a paper where a new set of forwarding behaviors is presented. That is a set of packet scheduling principles that can be used on the Internet to better achieve QoS. / Godkänd; 2004; 20070128 (ysko)

Wireless ad-hoc networks differs in many aspects compared to traditional infrastructured networks. Among other things, individual nodes cannot be expected to know the topology of the entire network. Also, since nodes typically are powered by batteries and eventually will run out of energy, it is imperative for algorithms to minimize the energy cost while distributing it as fairly as possible over all nodes in the network. This thesis covers different types of distributed algorithms for wireless networks, where all of them in some way creates or maintains a topology in order to facilitate communication in the network. The thesis comprises three scientific papers. The first paper concerns clustering, dividing the set of nodes in a network into subsets based on the network's connectivity graph. We propose a new clustering algorithm which uses the novel idea to maintain an existing clustering structure rather than creating a new structure from scratch, in order to minimize the changes in the structure as well as the communication overhead. The second paper covers interference reduction through topology control. We discuss previous work in how to measure interference, and present new metrics that aims to measure the average interference of the network rather than just the worst path. We also propose a new topology control algorithm and compare its performance to previous topology control algorithms, using our as well as previous interference models. In the third paper, we present a power-aware routing algorithm for Bluetooth networks. Unless similar previous work, our algorithm does not require the nodes to have any knowledge of the network except for their neighbors. By collecting path information in the routing messages, individual nodes can still make routing decisions in order to avoid nodes that are close to being depleted of energy. We also present a simplified version of the algorithm for general wireless ad-hoc networks. / Godkänd; 2006; 20061115 (ysko)

Intermediate structures such as lists and higher-order functions are very common in most styles of functional programming. While allowing the programmer to write clear and concise programs, the creation and destruction of these structures impose a run time overhead which is not negligible. Deforestation algorithms is a family of program transformations that remove these intermediate structures in an automated fashion, thereby improving program performance. While there has been plenty of work on deforestation-like transformations that remove intermediate structures for languages with call-by-name semantics, no investigations have been performed or call-by-value languages. It has been suggested that existing call-by-name algorithms could be applied to call-by-value programs, possibly introducing termination in the program. This hides looping bugs from the programmer, and changes the behaviour of a program depending on whether it is optimized or not. We present a transformation, positive supercompilation, for a higher-order call-by-value language that preserves termination properties of the programs it is applied to. We prove the algorithm correct and compare it to existing call-by-name transformations. Our results show that deforestation-like transformations are both possible and useful for call-by-value languages, with speedups up to an order of magnitude for certain benchmarks. Our algorithm is particularly important in the context of embedded systems where resources are scarce. By both removing intermediate structures and performing program specialization the footprint of programs can shrink considerably without any manual intervention by the programmer. / Godkänd; 2008; 20080520 (ysko)