No description available.

Diss. (sammanfattning) Uppsala : Uppsala universitet, 2006. / Härtill 4 uppsatser.

Existing QoS-aware Web Services discovery architectures tend to focus solely on fulfilling the requirements of either the client or the provider. However, the interests of the provider and client are not equivalent. The provider’s goal is to maximize the profit and consume the least amount of resources. On the other hand, the client’s selection is determined by their own requirements which do not always reflect the real resource overheads. This research aims to provide a novel mobile Web Services discovery and selection method based on utility functions to balance the requirements for clients and providers. In the mobile environment, it is critical to conserve resource consumption in addition to fulfilling user requirements, as resources such as wireless network bandwidth and mobile device power are precious. The proposed service selection strategy enables service providers to balance the cost/performance ratios and utilize the network bandwidth more effectively, while the clients can still attain the functional and quality levels specified in the service request.

Existing QoS-aware Web Services discovery architectures tend to focus solely on fulfilling the requirements of either the client or the provider. However, the interests of the provider and client are not equivalent. The provider’s goal is to maximize the profit and consume the least amount of resources. On the other hand, the client’s selection is determined by their own requirements which do not always reflect the real resource overheads. This research aims to provide a novel mobile Web Services discovery and selection method based on utility functions to balance the requirements for clients and providers. In the mobile environment, it is critical to conserve resource consumption in addition to fulfilling user requirements, as resources such as wireless network bandwidth and mobile device power are precious. The proposed service selection strategy enables service providers to balance the cost/performance ratios and utilize the network bandwidth more effectively, while the clients can still attain the functional and quality levels specified in the service request.

No description available.

Scheduling decisions in soft real-time environments are based on a utility function. The goal of such schedulers is to use a best-effort approach to maximize the utility function and ensure graceful degradation at overloads. Utility Accrual (UA) schedulers use heuristics to maximize the accrued utility. Heuristic-based scheduling do not always yield the optimal schedule even if there exists one because they do not explore the entire search space of task orderings. In distributed systems, local UA schedulers use the same heuristics along with deadline decomposition for task segments. At present, there has been no evaluation and analysis of the degree to which these polynomial-time, heuristic algorithms succeed in maximizing the total utility accrued. We implemented a preemptive, off-line static scheduling algorithm that performs an exhaustive search of all the possible task orderings to yield the optimal schedules. We simulated two important online dynamic UA schedulers, DASA-ND and LBESA for different system loads, task models, utility and load distribution patterns, and compared their performance with their corresponding optimal schedules. Our experimental analysis indicates that for most scenarios, both DASA-ND and LBESA create optimal schedules. When task utilities are equal or form a geometric sequence with an order of magnitude difference in their utility values, UA schedulers show more than 90% probability of being optimal for single-node workloads. Even though deadline decomposition substantially improves the optimality of both DASA-ND and LBESA under different scenarios for distributed workloads, it can adversely affect the scheduling decisions for some task sets we considered. / Master of Science

We present a utility accrual real-time scheduling algorithm called CIC-VCUA, for tasks whose execution times are functions of their starting times. We model such variable execution times employing variable cost functions (or VCFs). The algorithm considers application activities that are subject to time/utility function time constraints (or TUFs), execution times described using VCFs, and concurrent, mutually exclusive sharing of non-CPU resources. We consider the multi-criteria scheduling objective of (1) assuring that the maximum interval between any two consecutive, successful completions of jobs of a task must not exceed a specified upper bound, and (2) maximizing the system's total accrued utility, while satisfying mutual exclusion resource constraints. Since the scheduling problem is intractable, CIC-VCUA statically computes worst-case sojourn times of tasks, selects tasks for execution based on their potential utility density, and completes them at specific times, in polynomial-time. We establish that CIC-VCUA achieves optimal timeliness during under-loads. Further, we identify the conditions under which timeliness assurances hold. Our simulation experiments illustrate CIC-VCUA's effectiveness and superiority. / Master of Science

The current dominate layered networking architecture, in which each layer is designed and operated independently, results in inefficient and inflexible resource use in wireless networks due to the nature of the wireless medium, such as time-varying channel fading, mutual interference, and topology variations. In this thesis, we focus on resource allocation and scheduling in wireless orthogonal frequency division multiplexing (OFDM) networks based on joint physical and medium access control (MAC) layer optimization. To achieve orders of magnitude gains in system performance, we use two major mechanisms in resource management: exploiting the time variance and frequency selectivity of wireless channels through adaptive modulation, coding, as well as packet scheduling and regulating resource allocation through network economics. With the help of utility functions that capture the satisfaction level of users for a given resource assignment, we establish a utility optimization framework for resource allocation in OFDM networks, in which the network utility at the level of applications is maximized subject to the current channel conditions and the modulation and coding techniques employed in the network. Although the nonlinear and combinatorial nature of the cross-layer optimization challenges algorithm development, we propose novel efficient dynamic subcarrier assignment (DSA) and adaptive power allocation (APA) algorithms that are proven to achieve the optimal or near-optimal performance with very low complexity. Based on a holistic design principle, we design max-delay-utility (MDU) scheduling, which senses both channel and queue information. The MDU scheduling can simultaneously improve the spectral efficiency and provide right incentives to ensure that all applications can receive their different required quality of service (QoS). To facilitate the cross-layer design, we also deeply investigate the mechanisms of channel-aware scheduling, such as efficiency, fairness, and stability. First, using extreme value theory, we analyze the impact of multiuser diversity on throughput and packet delay. Second, we reveal a generic relationship between a specific convex utility function and a type of fairness. Third, with rigorous proofs, we provide a method to design cross-layer scheduling algorithms that allow the queueing stability region at the network layer to approach the ergodic capacity region at the physical layer.

This thesis investigates how to train the increasingly large cast of characters in modern commercial computer games. Modern computer games can contain hundreds or sometimes thousands of non-player characters that each should act coherently in complex dynamic worlds, and engage appropriately with other non-player characters and human players. Too often, it is obvious that computer controlled characters are brainless zombies portraying the same repetitive hand-coded behaviour. Commercial computer games would seem a natural domain for reinforcement learning and, as the trend for selling games based on better graphics is peaking with the saturation of game shelves with excellent graphics, it seems that better artificial intelligence is the next big thing. The main contribution of this thesis is a novel style of utility function, group utility functions, for reinforcement learning that could provide automated behaviour specification for large numbers of computer game characters. Group utility functions allow arbitrary functions of the characters’ performance to represent relationships between characters and groups of characters. These qualitative relationships are learned alongside the main quantitative goal of the characters. Group utility functions can be considered a multi-agent extension of the existing programming by reward method and, an extension of the team utility function to be more generic by replacing the sum function with potentially any other function. Hierarchical group utility functions, which are group utility functions arranged in a tree structure, allow character group relationships to be learned. For illustration, the empirical work shown uses the negative standard deviation function to create balanced (or equal performance) behaviours. This balanced behaviour can be learned between characters, groups and also, between groups and single characters. Empirical experiments show that a balancing group utility function can be used to engender an equal performance between characters, groups, and groups and single characters. It is shown that it is possible to trade some amount of quantitatively measured performance for some qualitative behaviour using group utility functions. Further experiments show how the results degrade as expected when the number of characters and groups is increased. Further experimentation shows that using function approximation to approximate the learners’ value functions is one possible way to overcome the issues of scale. All the experiments are undertaken in a commercially available computer game engine. In summary, this thesis contributes a novel type of utility function potentially suitable for training many computer game characters and, empirical work on reinforcement learning used in a modern computer game engine.

The aim of this work is to show that even people who outwardly demonstrate irrational behaviour are actually rational. The only reason why their actions deviate from theoretical rational behaviour is given by different utility functions. Ultimatum game with its easy rules represents a great way to show deviations between human and rational behaviours. The model described in the thesis focuses on Responder's decision making, which is influenced not only by maximization of pure economical profit but also by many other factors, which are summed in the model in one variable -- attitude to fairness. It is shown how this variable can be predicted using decisions obtained from a multi-round Ultimatum game. To prove that humans behave in accordance with their own preferences, the modelled game does not only estimate players' attitudes to fairness but also predicts players' following actions using knowledge of estimated values.