The capacity to adapt can greatly influence the success of systems that need to compensate for damaged parts, learn how to achieve robust performance in new environments, or exploit novel opportunities that originate from new technological interfaces or emerging markets. Many of the conditions in which technology is required to adapt cannot be anticipated during its design stage, creating a significant challenge for the designer. Inspired by the study of a range of biological systems, we propose that degeneracy - the realization of multiple, functionally versatile components with contextually overlapping functional redundancy - will support adaptation in technologies because it effects pervasive flexibility, evolutionary innovation, and homeostatic robustness. We provide examples of degeneracy in a number of rudimentary living technologies from military socio-technical systems to swarm robotics and we present design principles - including protocols, loose regulatory coupling, and functional versatility - that allow degeneracy to arise in both biological and man-made systems.

We consider the problem of manipulating elections by cloning candidates. In our model, a manipulator can replace each candidate c by several clones, i.e., new candidates that are so similar to c that each voter simply replaces c in his vote with a block of these new candidates, ranked consecutively. The outcome of the resulting election may then depend on the number of clones as well as on how each voter orders the clones within the block. We formalize what it means for a cloning manipulation to be successful (which turns out to be a surprisingly delicate issue), and, for a number of common voting rules, characterize the preference profiles for which a successful cloning manipulation exists. We also consider the model where there is a cost associated with producing each clone, and study the complexity of finding a minimum-cost cloning manipulation. Finally, we compare cloning with two related problems: the problem of control by adding candidates and the problem of possible (co)winners when new alternatives can join.

We identify principles characterizing Solomonoff Induction by demands on an agent's external behaviour. Key concepts are rationality, computability, indifference and time consistency. Furthermore, we discuss extensions to the full AI case to derive AIXI.

We propose a theory of abstraction of discrete-event systems (DES) formulated at the semantic level, i.e., as a function that maps event traces at the original (ground) level to traces at the abstract level. We study how diagnosis of DES can be performed using an abstract model, and under which conditions this process leads to a correct solution (i.e., a set of alternative diagnoses that include the real status of the system). Finally, we study how the use of an abstract model can affect the precision of diagnosis, i.e., the presence of spurious system states in the solution. To this end, we introduce the notion of diagnosability with abstract models, which ensures the precision of abstract diagnoses, and we discuss a practical way to test it.

Moreover, all of the of a system and, after detection, to determine the location faults that occurred within the (possibly extended) time interval and/or the type of system faults that caused the abnormal during which the system has been observed must be behaviour. A diagnosis hypothesis indicates which fault(s) accounted for in the diagnosis. Considering again the diagnosis occurred in the system, and the diagnosis is the set of alternative of a car, for each component we could be interested hypotheses that explain (i.e., are compatible) with in knowing whether a fault has occurred to it during the last the observed system behaviour. In this paper, we focus on week; in such a case, it is difficult to perform a drastic abstraction Model-Based Diagnosis (MBD) of Discrete-Event Systems of the model without losing any precision in the (DESs, see (Cassandras and Lafortune 1999)), where the diagnosis discrimination among different hypotheses. is computed by comparing a complete DES model In this article, we study a novel approach to reduce the of the system behaviour with a (partial) observation of the complexity of DES diagnosis, based on a reformulation of actual system behaviour (Sampath et al. 1995).

Learning to use an object as a tool requires understanding what goals it helps to achieve, the properties of the tool that make it useful and how the tool must be manipulated to achieve the goal. We present a method that allows a robot to learn about objects in this way and thereby employ them as tools. An initial hypothesis for an action model of tool use is created by observing another agent accomplishing a task using a tool. The robot then refines its hypothesis by active learning, generating new experiments and observing the outcomes. Hypotheses are updated using Inductive Logic Programming. One of the novel aspects of this work is the method used to select experiments so that the search through the hypothesis space is minimised.

Model checking is a promising technology, which has been applied for verification of many hardware and software systems. In this paper, we introduce the concept of model update towards the development of an automatic system modification tool that extends model checking functions. We define primitive update operations on the models of Computation Tree Logic (CTL) and formalize the principle of minimal change for CTL model update. These primitive update operations, together with the underlying minimal change principle, serve as the foundation for CTL model update. Essential semantic and computational characterizations are provided for our CTL model update approach. We then describe a formal algorithm that implements this approach. We also illustrate two case studies of CTL model updates for the well-known microwave oven example and the Andrew File System 1, from which we further propose a method to optimize the update results in complex system modifications.

In many professional sports leagues, teams from opposing leagues/conferences compete against one another, playing inter-league games. This is an example of a bipartite tournament. In this paper, we consider the problem of reducing the total travel distance of bipartite tournaments, by analyzing inter-league scheduling from the perspective of discrete optimization. This research has natural applications to sports scheduling, especially for leagues such as the National Basketball Association (NBA) where teams must travel long distances across North America to play all their games, thus consuming much time, money, and greenhouse gas emissions. We introduce the Bipartite Traveling Tournament Problem (BTTP), the inter-league variant of the well-studied Traveling Tournament Problem. We prove that the 2n-team BTTP is NP-complete, but for small values of n, a distance-optimal inter-league schedule can be generated from an algorithm based on minimum-weight 4-cycle-covers. We apply our theoretical results to the 12-team Nippon Professional Baseball (NPB) league in Japan, producing a provably-optimal schedule requiring 42950 kilometres of total team travel, a 16% reduction compared to the actual distance traveled by these teams during the 2010 NPB season. We also develop a nearly-optimal inter-league tournament for the 30-team NBA league, just 3.8% higher than the trivial theoretical lower bound.

Characters are a critical part of storytelling and emotion is a vital part of character. Readers generally credit characters with human emotions, and it is these emotions which bring meaning to stories. To computationally construct interesting and meaningful stories we need a model of emotion which allows us to predict characters’ reactions to events in the world. There are many different psychological theories of emotion; the most popular to date for computational applications is the OCC theory. This paper describes a Discrete Event Calculus implementation of the OCC Theory of Emotion. To evaluate our system, we apply it to a selection of Aesop’s fables, and compare the output to the emotions readers expect in the same situations based on a survey.

Multi-agent path planning is a challenging problem with numerous real-life applications. Running a centralized search such as A* in the combined state space of all units is complete and cost-optimal, but scales poorly, as the state space size is exponential in the number of mobile units. Traditional decentralized approaches, such as FAR and WHCA*, are faster and more scalable, being based on problem decomposition. However, such methods are incomplete and provide no guarantees with respect to the running time or the solution quality. They are not necessarily able to tell in a reasonable time whether they would succeed in finding a solution to a given instance. We introduce MAPP, a tractable algorithm for multi-agent path planning on undirected graphs. We present a basic version and several extensions. They have low-polynomial worst-case upper bounds for the running time, the memory requirements, and the length of solutions. Even though all algorithmic versions are incomplete in the general case, each provides formal guarantees on problems it can solve. For each version, we discuss the algorithm's completeness with respect to clearly defined subclasses of instances. Experiments were run on realistic game grid maps. MAPP solved 99.86% of all mobile units, which is 18--22% better than the percentage of FAR and WHCA*. MAPP marked 98.82% of all units as provably solvable during the first stage of plan computation. Parts of MAPP's computation can be re-used across instances on the same map. Speed-wise, MAPP is competitive or significantly faster than WHCA*, depending on whether MAPP performs all computations from scratch. When data that MAPP can re-use are preprocessed offline and readily available, MAPP is slower than the very fast FAR algorithm by a factor of 2.18 on average. MAPP's solutions are on average 20% longer than FAR's solutions and 7--31% longer than WHCA*'s solutions.