Designing teams of autonomous robots that can create target structures or repair damage to those structures on either a one-off or ongoing basis is an important problem in distributed robotics. However, it is not known if a team design algorithm for any of these tasks can both have low runtime and produce teams that will always perform their specified tasks quickly and correctly. In this paper, we give the first computational and parameterized complexity analyses of several robot team design problems associated with creating, repairing, and maintaining target structures in given environments. Our goals are to establish whether efficient design algorithms exist that operate reliably on all possible inputs and, if not, under which restrictions such algorithms are and are not possible. We prove that all of our design problems are not efficiently solvable in general for heterogeneous robot teams and remain so under a number of plausible restrictions on robot controllers, environments, and target structures. We also give the first restrictions relative to which some of these problems may be efficiently solvable and discuss how theoretical results like those derived here can be combined with physical experiments to derive the best possible algorithms for real-world robot team design.
Self-adaptation provides a principled way to deal with uncertainty of software systems during operation. As more systems with strict goals require self-adaptation, the need for guarantees in self-adaptive systems is becoming a high-priority concern. Designing adaptive software using principles from control theory has been identified as one of the approaches to provide guarantees. However, existing solutions can only handle requirements either in the form of setpoint values or values to be optimized, and they primarily focus on handling uncertainty in the environment. This paper presents SimCA* that makes two contributions to control-based self-adaptation: (a) it supports requirements that keep a value above/below a required threshold, in addition to setpoint and optimization requirements; and (b) it deals with uncertainty in system parameters, component interactions, system requirements, in addition to uncertainty in the environment. SimCA* provides guarantees for the three types of requirements of the system that is subject to different types of uncertainties. We evaluate SimCA* for two systems with strict goals from different domains: an Unmanned Underwater Vehicle system and an Internet of Things network. The test results confirm that SimCA* can satisfy the three types of requirements in the presence of different types of uncertainty.
We consider the challenges in designing self-governed socio-technical systems in which exists self-modification of the rules in order to satisfice a changeable set of values. Based on a study of classical Athenian democracy, we examine the propostion that processes of knowledge management can resolve the rule-restriction dilemma for self-governance. Taking a set design principles intended to make knowledge management processes open, inclusive, transparent and effective, we operationalise three of these principles in the context of a collective action situation, namely common-pool resource allocation. We describe a simulation using this operationalisation, and present results of a series of experiments showing how knowledge management processes can be used to obtain robust solutions for the perception of fairness, allocation decision and punishment mechanisms in a self-organised resource allocation scenario. We conclude by arguing that this approach to the design of socio-technical systems can provide a balance between restriction and un-restriction in the self-modification of conventional rules, and can thus provide the foundations for sustainable and democratic self-governance in socio-technical systems.
With the rapid development of cloud computing, various types of cloud services emerge. However, it remains a big challenge for cloud users to find suitable and cost-effective services for two major reasons. One is that it can be a possibility that providers dont provide services in accordance with their declared Service Level Agreements(SLA). The other is that it is difficult for customers to describe their requirements accurately. In order to help users select cloud services efficiently, this paper presents a Trust enabled Self-Learning Agent Model for service Matching (TSLAM). In the model, Agents represent cloud entities to take actions and the learning module embedded in broker agents help to capture the implicit demands and find the real service preferences of users. Along with the transactions, under the effect of the learning mechanism, services are classified into different types, and each type is managed by different broker agents, due to the randomness of customers needs faced by different brokers. Moreover, trust is introduced into the process to improve the security of cloud market against malicious behaviors. Extensive experiments prove that TSLAM is able to optimize the service market so that services can be matched to customers requirements efficiently.
The intuitive notion of added value in groups represents a fundamental property of biological, physical, and economic systems: how the interaction or cooperation of multiple entities, substances, or other agents can produce synergistic effects. However, despite the ubiquity of group formation, a well-founded measure of added value has remained elusive. Here, we propose such a measure inspired by the Shapley value?a fundamental solution concept from Cooperative Game Theory. To this end, we start by developing a solution concept that measures the average impact of each player in a coalitional game, and show how this measure uniquely satisfies a set of intuitive properties. Then, building upon our solution concept, we propose a measure of added value that not only analyzes the interactions of players inside their group, but also outside it, thereby reflecting otherwise-hidden information about how these individuals typically perform in various groups of the population.
Software systems are deployed in environments that keep changing over time. They should therefore adapt to changing conditions in order to meet their requirements. The satisfaction rate of these requirements depends on the rate at which adverse conditions prevent their satisfaction. Obstacle analysis is a goal-oriented form of risk analysis for requirements engineering (RE) whereby obstacles to system goals are identified, assessed, and resolved through countermeasures. The selection of effective countermeasures relies on environment assumptions and on the assessed obstacle likelihood and criticality. These various factors estimated at RE time may however evolve at system runtime. To meet the system's goals under changing conditions, the paper proposes to defer obstacle resolution to system runtime. Technique are presented for monitoring goal/obstacle satisfaction rates; deciding when adaptation should be triggered; and adapting the system on-the-fly to countermeasures that are more effective. The approach relies on a model where goals and obstacles are refined and specified in a probabilistic linear temporal logic. The techniques allow for monitoring the satisfaction rate of probabilistic leaf obstacles; determining the severity of their consequences; and shifting to countermeasures that better meet the goal required satisfaction rates. Our approach is evaluated on fragments of an ambulance dispatching system.
In disasters, many stationary tasks, such as saving survivors in debris, extinguishing fire of buildings, etc. need first responders to complete on site. In such circumstances, wireless mobile robots are usually employed to search for tasks and establish ad hoc networks to assist first responders. Due to the unknown and complexity of environments and limited capabilities of wireless mobile robots, searching and establishing ad hoc networks in disaster environments is a challenging issue in both theory and practice. To this end, a task-based wireless mobile robot deployment approach is proposed in this paper. The proposed approach consists of a search process and a deployment process. The search process can guide wireless mobile robots to efficiently find tasks in unknown and complex environments. The deployment process can find suitable deployment locations for wireless mobile robots to establish ad hoc networks. The established ad hoc networks can ensure the communication of wireless mobile robots in the network and can cover the maximum number of task locations and the maximum areas in a disaster environment. Experimental results demonstrate that based on the proposed approach, wireless mobile robots have better performance in terms of search and ad hoc network establishment in disaster environments.