In this study, we investigate the effectiveness of using the PID (Proportional - Integral - Derivative) control loop factors for modifying response thresholds in a decentralized, non-communicating, threshold-based swarm. Each agent in our swarm has a set of four thresholds, each corresponding to a task the agent is capable of performing. The agent will act on a particular task if the stimulus is higher than its corresponding threshold. The ability to modify their thresholds allows the agents to specialize dynamically in response to task demands. Current approaches to dynamic thresholds typically use a learning and forgetting process to adjust thresholds. These methods are able to effectively specialize once, but can have difficulty re-specializing if the task demands change. Our approach, inspired by the PID control loop, alters the threshold values based on the current task demand value, the change in task demand, and the cumulative sum of previous task demands. We show that our PID-inspired method is scalable and outperforms fixed and current learning and forgetting response thresholds with non-changing, constant, and abrupt changes in task demand. This superior performance is due to the ability of our method to re-specialize repeatedly in response to changing task demands.

In this work, we investigate the application of a multi-objective genetic algorithm to the problem of task allocation in a self-organizing, decentralized, threshold-based swarm. We use a multi-objective genetic algorithm to evolve response thresholds for a simulated swarm engaged in dynamic task allocation problems: two-dimensional and three-dimensional collective tracking. We show that evolved thresholds not only outperform uniformly distributed thresholds and dynamic thresholds but achieve nearly optimal performance on a variety of tracking problem instances (target paths). More importantly, we demonstrate that thresholds evolved for some problem instances generalize to all other problem instances, eliminating the need to evolve new thresholds for each problem instance to be solved. We analyze the properties that allow these paths to serve asuniversal training instancesand show that they are quite natural. Aftera priorievolution, the response thresholds in our system are static. The problem instances solved by the swarms are highly dynamic, with schedules of task demands that change over time with significant differences in rate and magnitude of change. That the swarm is able to achieve nearly optimal results refutes the common assumption that a swarm must be dynamic to perform well in a dynamic environment.

Mass extinction events have previously been shown to be a catalyst for accelerating the rate of evolution in genetic algorithms. This increased evolution rate combined with a destabilization of the dynamic equilibrium of the genetic algorithm can allow the algorithm to overcome local maxima in the solution space; however, most implementations of mass extinction squander the full benefit of the increased evolutionary rate by relying upon random chance to generate better solutions in the post-extinction generations. This paper examines the hypothesis that, by increasing variability and decreasing selection pressure immediately after an extinction event, the algorithm has a higher chance of yielding more fit individuals and overcoming local maxima in the post-extinction generations. We compare the performance of a genetic algorithm without extinction with the two approaches described above on a problem with a large search space containing many local optima, point scattering in the unit circle, and examine the effects of extinction methods on performance. The preliminary results presented here show that decreasing selection pressure and increasing variability help the genetic algorithm achieve higher success rates than with standard mass extinction.

The iterated prisoner's dilemma (IPD) has been studied in fields as diverse as economics, computer science, psychology, politics, and environmental studies. This is due, in part, to the intriguing property that its Nash equilibrium is not globally optimal. Typically treated as a single-objective problem, a player's goal is to maximize their own score. In some work, minimizing the opponent's score is an additional objective. In this article, we explore the role of explicitly optimizing for mutual cooperation in IPD player performance. We implement a genetic algorithm in which each member of the population evolves using one of four multiobjective fitness functions: selfish, communal, cooperative, and selfless, the last three of which use a cooperative metric as an objective. As a control, we also consider two single-objective fitness functions. We explore the role of representation in evolving cooperation by implementing four representations for evolving players. Finally, we evaluate the effect of noise on the evolution of cooperative behaviors. Testing our evolved players in tournaments in which a player's own score is the sole metric, we find that players evolved with mutual cooperation as an objective are very competitive. Thus, learning to play nicely with others is a successful strategy for maximizing personal reward.

Path planning, the task of finding an obstacle-avoiding, shortest-length route from source to destination is an interesting theoretical problem with numerous applications. We present an improved genetic algorithm for path planning in a continuous, largely unconstrained real-world environment. We introduce a new domain-specific crossover operator based on path intersections. We also implement a new path correction operator that eliminates obstacle collisions from a path, leading to a dramatic search improvement despite the conceptual simplicity of the correction. Finally, in place of a standard binary measure of obstacle collisions, we present a new optimization objective measuring the degree to which a path intersects obstacles. Due to these improvements, individually and in combination, our algorithm is able to solve scenarios that are considerably more complex and exist in a more general environment than those that appear in the literature. We demonstrate the utility of our system through testing onboard an autonomous micro aerial vehicle. Further, our approach demonstrates the utility of domain-specific genetic operators for path planning. We hypothesize that such operators may be beneficial in other domains.

Genetic algorithms are an often used tool for the problem of pathfinding. Their ability to find good solutions to multiobjective optimization problems makes them well suited to this task. Of course, genetic algorithms embody a broad range of techniques and strategies including crossover, mutation and mass extinction, each with multiple parameters and implementations. In this paper, we examine the effects of crossover and mass extinction on a genetic algorithm for planning a path through known obstacles in an unconstrained, continuous, static environment. Using a mutation-only genetic algorithm as a baseline, we study the effect of crossover with and without mass extinction events that occur at several different probabilities. We find that while both offer sometimes significant improvement in some cases, neither is universally beneficial.

We present an efficient algorithm for PAC-learning a very general class of geometric concepts over ℛ d for fixed d . More specifically, let 𝒯 be any set of s halfspaces. Let x =(x 1 , …, x d ) be an arbitrary point in ℛ d . With each t ∈ 𝒯 we associate a boolean indicator function I t (x) which is 1 if and only if x is in the halfspace t . The concept class, 𝒞 d s , that we study consists of all concepts formed by any Boolean function over I t1 , …, I ts for t i ∈ 𝒯. This class is much more general than any geometric concept class known to be PAC-learnable. Our results can be extended easily to learn efficiently any Boolean combination of a polynomial number of concepts selected from any concept class 𝒞 over ℛ d given that the VC-dimension of 𝒞 has dependence only on d and there is a polynomial time algorithm to determine if there is a concept from 𝒞 consistent with a given set of labeled examples. We also present a statistical query version of our algorithm that can tolerate random classification noise. Finally we present a generalization of the standard ε-net result of Haussler and Welzl [1987] and apply it to give an alternative noise-tolerant algorithm for d = 2 based on geometric subdivisions.

We first present an algorithm that uses membership and equivalence queries to exactly identify a discretized geometric concept defined by the union of m axis-parallel boxes in d-dimensional discretized Euclidean space where each coordinate can have n discrete values. This algorithm receives at most md counterexamples and uses time and membership queries polynomial in m and log n for any constant d. Furthermore, all equivalence queries can be formulated as the union of O(md log m) axis-parallel boxes. Next, we show how to extend our algorithm to efficiently learn, from only equivalence queries, any discretized geometric concept generated from any number of halfspaces with any number of known (to the learner) slopes in a constant dimensional space. In particular, our algorithm exactly learns (from equivalence queries only) unions of discretized axis-parallel boxes in constant dimensional space in polynomial time. Furthermore, this equivalence query only algorithm can be modified to handle a polynomial number of lies in the counterexamples provided by the environment. Finally, we introduce a new complexity measure that better captures the complexity of the union of m boxes than simply the number of boxes and the dimension. Our new measure, $\sigma$, is the number of segments in the target, where a segment is a maximum portion of one of the sides of the target that lies entirely inside or entirely outside each of the other halfspaces defining the target. We present a modification of our first algorithm that uses time and queries polynomial in $\sigma$ and log n. In fact, the time and queries (both membership and equivalence) used by this single algorithm are polynomial for eitherm or d constant.

We present an efficient algorithm for PAC-learning a very general class of geometric concepts over Rd for fixed d.

We present several efficient parallel algorithms for PAC-learning geometric concepts in a constantdimensional space that are robust even against malicious misclassification noise of any rate less than 1/2.In particular we consider the class of geometric concepts defined by a polynomial number of (d -1)-dimensional hyperplanes against an arbitrary distributionwhere each hyperplane has a slope from a set of known slopes, and the class of geometric concepts defined by a polynomial number of (d -1)-dimensional hyperplanes (of unrestricted slopes) against a product distribution.Next we define a complexity measure of any set S of (d-1)-dimensional surfaces that we call the variant of S and prove that the class of geometric concepts defined by surfaces of polynomial variant can be efficiently learned in parallel under a product distribution (even under malicious misclassification noise).Finally, we describe how boosting techniques can be used so that our algorithms' dependence one and 6 does not depend on d.

Article Free Access Share on DNF—if you can't learn'em, teach'em: an interactive model of teaching Author: H. David Mathias Department of Computer Science, Washington University, St. Louis, MO Department of Computer Science, Washington University, St. Louis, MOView Profile Authors Info & Claims COLT '95: Proceedings of the eighth annual conference on Computational learning theoryJuly 1995 Pages 222–229https://doi.org/10.1145/225298.225325Published:05 July 1995Publication History 6citation335DownloadsMetricsTotal Citations6Total Downloads335Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present two algorithms that use membership and equivalence queries to exactly identify the concepts given by the union of s discretized axis-parallel boxes in d-dimensional discretized Euclidean space where there are n discrete values that each coordinate can have. The first algorithm receives at most sd counterexamples and uses time and membership queries polynomial in s and logn for any d constant. Further, all equivalence queries made can be formulated as the union of O(sdlogs) axis parallel boxes.

We introduce a formal model of teaching in which the teacher is tailored to a particular learner, yet the teaching protocol is designed so that no collusion is possible.Not surprisingly, such a model remedies the nonintuitive aspects of other models in which the teacher must successfully teach any consistent learner.We prove that any class that can be exactly identified by a polynomial-time algorithm with access to a very rich set of examplebased queries is teachable by a computationally unbounded teacher and a polynomial-time learner.In addition, we present other general results relating this model of teaching to various previous results.We also consider the problem of designing teacher/learner pairs in which both the teacher and learner are polynomial-time algorithms and describe teacher/learner pairs for the classes of decision lists and Horn sentences.

We consider the problem of learning k-term DNF formulas using equivalence queries and incomplete membership queries as defined by Angluin and Slonim. We demonstrate that this model can be applied to non-monotone classes. Namely, we describe a polynomial-time algorithm that constructs a k-term DNF formula representationally equivalent to the target using incomplete membership queries and equivalence queries from the class of DNF formulas.