The coalition formation problem for task allocation is a difficult and increasingly studied problem (e.g., [1-3]); however, less studied is the notion of task preemption in multi-robot systems. A previously proposed ascending auction based task allocation protocol, RACHNA, is one of the few algorithms that explicitly allows task preemption. This paper demonstrates that the manner in which RACHNA permits task preemption has an undesirable side effect in which RACHNA needlessly changes the coalition assigned to a given task, even when the original coalition can still complete the task. A simultaneous descending auction based approach to task allocation is introduced that allows task preemption and never exhibits the unnecessary task reassignments exhibited by RACHNA.

Coalition formation is a fundamental problem in multi-agent systems. In characteristic function games (CFGs), each coalition C of agents is assigned a value indicating the joint utility those agents will receive if C is formed. CFGs are an important class of cooperative games; however, determining the optimal coalition structure, partitioning of the agents into a set of coalitions that maximizes the social welfare, currently requires O(3n) time for n agents. In light of the high computational complexity of the coalition structure generation problem, a natural approach is to relax the optimality requirement and attempt to find an approximate solution that is guaranteed to be close to optimal. Unfortunately, it has been shown that guaranteeing a solution within any factor of the optimal requires Ω(2n) time. Thus, the best that can be hoped for is to find an algorithm that returns solutions that are guaranteed to be as close to the optimal as possible, in as close to O(2n) time as possible. This paper contributes to the state-of-the-art by presenting an algorithm that achieves better quality guarantees with lower worst case running times than all currently existing algorithms. Our approach is also the first algorithm to guarantee a constant factor approximation ratio, 1/8, in the optimal time of O(2n. The previous best ratio obtainable in O(2n) was 2/n.

Recent work in test based coevolution has focused on employing ideas from multi-objective optimization in coevolutionary domains. So called Pareto coevolution treats the coevolving set of test cases as objectives to be optimized in the sense of multi-objective optimization. Pareto coevolution can be seen as a relaxation of traditional multi-objective evolutionary optimization. Rather than being forced to determine the outcome of a particular individual on every objective, pareto coevolution allows the examination of an individual's outcome on a particular objective.

The No-Free-Lunch theorem is a fundamental result in the field of black-box function optimization. Recent work has shown that coevolution can exhibit free lunches. The question as to which classes of coevolution exhibit free lunches is still open. In this paper we present a novel framework for analyzing No-Free-Lunch like results for classes of coevolutionary algorithms. Our framework has the advantage of analyzing No-Free-Lunch like inquiries in terms of solution concepts and isomorphisms on the weak preference relation on solution configurations. This allows coevolutionary algorithms to be naturally classified by the type of solution they seek. Using the weak preference relation also permits us to present a simpler definition of performance metrics than that used in previous coevolutionary No-Free-Lunch work, more akin to the definition used in the original No-Free-Lunch theorem.

While coevolution has many parallels to natural evolution, methods other than those based on evolutionary principles may be used in the interactive fitness setting. In this paper we present a generalization of coevolution to co-optimization which allows arbitrary black-box function optimization techniques to be used in a coevolutionary like manner.

The world is increasingly dependent on critical infrastructures such as the electric power grid, water, gas, and oil transport systems, which are susceptible to cascading failures that can result from a few faults. Due to the combinatorial complexity in the search spaces involved, most traditional search techniques are inappropriate for identifying these faults and potential protections against them. This paper provides a computational methodology employing competitive coevolution to simultaneously identify low-effort, high-impact faults and corresponding means of hardening infrastructures against them. A power system case study provides empirical evidence that our proposed methodology is capable of identifying cost effective modifications to substantially improve the fault tolerance of critical infrastructures.