7,235 research outputs found
Optimal clearing algorithms for multi-unit single item and multi-unit combinatorial auctions with demand/supply function bidding
No full textThis paper presents new clearing algorithms for multi-unit single-item and multi-unit combinatorial auctions with piecewise linear demand/supply functions. We analyse the complexity of our algorithms and prove that they are guaranteed to find the optimal allocation
Coalition structure generation in task-based settings
No full textThe coalition formation process, in which a number of independent, autonomous agents come together to act as a collective, is an important form of interaction in multi-agent systems. However, one of the main problems that hinders the wide spread adoption of coalition formation technologies is the computational complexity of coalition structure generation. That is, once a group of agents has been identified, how can it be partitioned in order to maximise the social payoff To date, most work on this problem has concentrated on simple characteristic function games. However, this lacks the notion of tasks which makes it more difficult to apply it in many applications. Against this background, this paper studies coalition structure generation in a general task-based setting. Specifically, we show that this problem is NP-hard and that the minimum number of coalition structures that need to be searched through in order to establish a solution within a bound from the optimal is exponential to the number of agents. We then go onto develop an anytime algorithm that can establish a solution within a bound from the optimal with a minimal search and can reduce the bound further if time permits
Modeling And Control Battery Aging in Energy Harvesting Systems
No full textEnergy storage is a fundamental component for the development of sustainable and environment-aware technologies. One of the critical challenges that needs to be overcome is preserving the State of Health (SoH) in energy harvesting systems, where bursty arrival of energy and load may severely degrade the battery. Tools from Markov process and Dynamic Programming theory are becoming an increasingly popular choice to control dynamics of these systems due to their ability to seamlessly incorporate heterogeneous components and support a wide range of applications. Mapping aging rate measures to fit within the boundaries of these tools is non-trivial. In this paper, a framework for modeling and controlling the aging rate of batteries based on Markov process theory is presented. Numerical results illustrate the tradeoff between battery degradation and task completion delay enabled by the proposed framework
A Unified Stochastic Model for Energy Management in Solar-Powered Embedded Systems
No full textEnergy harvesting from environments such as solar energy are promising solutions to tackle energy sustainability in embedded systems. However, uncertainties in energy availability, non-ideal characteristics of harvesting circuits, energy storage (battery or supercapacitor), and application demand dynamics add more complexity in the system. We present a unified model based on discrete-time Finite State Markov Chain to capture the dynamicity and variations in both the energy supply from solar irradiance and the energy demand from the application. In this paper, we exploit the temporal and spatial characteristics of solar energy and propose a deterministic profile with stochastic process to reflect the fluctuation due to unexpected weather condition. Optimal policy to maximize expected total QoS is derived from the presented model using a probabilistic dynamic programming approach. Compared to a state-of-the-art deterministic energy management framework, our proposed approach outperforms in term of QoS and energy sustainability (with less shutdown time) of the system
Near-optimal anytime coalition structure generation
No full textForming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best set of agents that should participate in a given team. To this end, in this paper, we present a novel, anytime algorithms designed for this purpose. Our algorithm can generate solutions that either have a tight bound from the optimal or are optimal (depending on the objective) and works by partitioning the space in terms of a small set of elements that represent structures which contain coalitions of particular sizes. It then performs an online heuristic search that prunes the space and only considers valid and non-redundant coalition structures. We empirically show that we are able to find solutions that are, in the worst case, 99% efficient in 0.0043% of the time to find the optimal value by the state of the art dynamic programming (DP) algorithm (for 20 agents), using 33% less memory
Coalition Formation and Operation in Virtual Organisations
No full textThe concept of Virtual Organisations (VOs) or Virtual Enterprises (VEs) is rapidly emerging as an important topic in many areas of computing including e-commerce, grid computing and the semantic Web. One reason for this interest is that VOs provide a means of bringing together a number of autonomous stakeholders in a dynamic fashion in order to address a specific problem or niche. These agents then work together for some period of time and then disband when it is deemed appropriate to do so. There are, however, many technical, social and economic issues associated with this VO lifecycle (i.e. creation, operation, maintenance and dissolution) that need to be addressed before VOs can be considered to be practicable. While previous technical work on VOs has concentrated on providing tools to support different aspects of the VO lifecycle, comparatively little work has focused on the mechanisms for automated VO creation, operation and maintenance. To address this shortcoming, this research aims to study and design mechanisms for the VO creation, operation and maintenance phases. In this thesis, our approach is to use combinatorial auctions and coalition formation mechanisms. In particular, novel algorithms for clearing multi-unit single-item and multi-unit combinatorial auctions have been developed as a means of tackling VO creation and one part of VO maintenance. A novel algorithm for coalition structure generation has also been developed to address VO operation and another part of VO maintenance
Developing a website with user experience
No full textThe Internet has played an essential role in human life with its convenience, and it has been attached to people’s lives for several decades. Many people daily use the Internet on their own electronic devices for various purposes. In fact, through human habits and behavior that use electronic devices to access the Internet daily, user experience design has been created to enhance the Interaction of humans with the application and websites in their own devices.
The thesis idea was based on Bumi Asian Kitchen & Café, an Asian restaurant in Helsinki. Bumi is also no exception with the traditional business, which has served its regular food menu on the street corner since 2016. By combining technology and human behaviors, the thesis aims to research customer behavior and expectations and develop a website design for a restaurant to bring a convenient user experience and exemplary user interface to its customers. That website design helps the business attract customers, raise the reputation, and enhance customer connection in the smooth method.
In the thesis, the essential design knowledge will clarify the basis of user experience and user interface. The author then keeps researching the website’s basic knowledge to describe the importance of website design and website usability. The author uses the qualitative method and ex-plains the UX design methodology with persona, customer journey, heuristic evaluation, user inter-view, and usability testing before choosing a suitable methodology for the practical process of web-site development for Bumi Asian Kitchen & Cafe. After evaluation based on data collection, author can point out the advantages of website development that bring to a restaurant business
On the sensitivity of Von Neuman and Morgenstern abstract stable sets : the stable and the individual stable bargaining set
No full textThe D3-Triangulation for Simplicial Deformation Algorithms for Computing Solutions of Nonlinear Equations
No full textAnytime Optimal Coalition Structure Generation
No full textForming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining the best groups of agents to select to achieve some goal. To this end, in this paper, we present a novel, optimal anytime algorithm for this coalition structure generation problem that is significantly faster than previous algorithms designed for this purpose. Specifically, our algorithm can generate solutions by partitioning the space of all potential coalitions into sub-spaces that contain coalition structures that are similar, according to some criterion, such that these sub-spaces can be pruned by identifying their bounds. Using this representation, the algorithm then searches through only valid and unique coalition structures and selects the best among them using a branch-and-bound technique. We empirically show that we are able to find solutions that are optimal in 0.082% of the time taken by the state of the art dynamic programming algorithm (for 27 agents) using much less memory O(2n) instead of O(3n) for the set of n agents). Moreover, our algorithm is the first to be able to solve the coalition structure generation problem for numbers of agents bigger than 27 in reasonable time (less than 90 minutes for 27 agents as opposed to around 2 months for the best previous solution)
- …
