Search

A group of birds in coordinated flight is - perhaps owing to its success - a commonly observed phenomenon. This ubiquity suggests that bird species which fly together can achieve substantial evolutionary benefit. The proposed benefits of group flight include enhanced predator avoidance, the use of social information or even aerodynamic advantages. However, we still have little understanding of how these benefits will differ across ecological context or taxa. In this thesis, I argue that a good answer to this question can be found by considering how four response mechanisms interact to govern the selective benefits. The importance of birds' responses to 1) risk, 2) environmental/navigational information, 3) the aerodynamic environment, and 4) the social environment are mapped out conceptually in the Introduction. I then provide five Chapters of question-led empirical research in collective-flight model species homing pigeons (Columba livia), to manipulate and explicitly test all of the above factors. This empirical work included, in each data Chapter, the use of miniaturised, animal attached biologgers, such as GPS, to determine how the birds respond to these manipulations. The observed response mechanisms are discussed in light of evolutionary theory (in particular a behavioural ecological perspective) and thus are linked to the function for which the mechanism involved.

The simple rules that govern the interactions between the different components of a complex system often lead to interesting behaviour that are unexpected, emergent or serendipitous. This thesis proposes a new approach using compression for the automatic discovery of interesting behaviour that occurs in complex systems. In order to evaluate the new approach, three different types of complex systems are examined experimentally:one dimensional cellular automata, flocking and a variation of Braitenberg Vehicles. In the first experiment, a novel approach has been developed to examine one dimensional cellular automata, where the output is compressed using the text compression scheme Prediction by Partial Matching (PPM) to generate the code length differences of the output with respect to time. Several clustering algorithms, such as k-means and Hierarchical Agglomerative Clustering, were then used to group cellular automata which show similar behaviour together into clusters, thus making interesting behaviours much more accessible in comparison to results produced in related studies. Various types of interesting behaviour were then found by analysing the graphs of the code length differences, where jagged peaks in the graphs, high variance in the data, and large gradients were good indicators of interesting patterns in cellular automata. Rare or unusual behaviour were also classed as being interesting, which could easily be found by examining for small clusters. In the second experiment, a similar strategy was taken when analysing a flocking behaviour model. By combining Run Length Encoding with PPM compression of the output produced over the course of the simulation, and using multi-stage clustering it was possible to cluster similar flocking behaviours together. To test the quality of these clusters, an innovative algorithm was devised to determine the distance between different behaviours. It was noticed that tightly bound flocks had much smaller compression code lengths (highly compressed) overall in the spatial domain. When examining the compressed trajectory data, it was noted that the highest compression code length (i.e.least compressed) values belonged to flocking behaviours with circling or a large number of twists and turns. A third experiment involved creating variations of traditional Braitenberg Vehicles,by placing sensors on ten different possible locations on the simulated vehicle, and incorporating Brooks' subsumption architecture, which resulted in different unusual behaviours being produced. The vehicle was allowed to explore a simulated environment with walls on the border which contained a single bright light in the centre. With a search space of over 10,000 simulations, by using PPM compression, clustering was able to effectively discover interesting emergent behaviour produced from a simple interaction of light and proximity sensors on a vehicle and a single light source. From the three sets of complex systems examined, it is evident that the novel compression-based algorithms created were capable of automatically clustering similar behaviours together and, from that, interesting behaviours were automatically retrieved from those systems. These novel algorithms and techniques have useful potential in the science of complex systems and modelling to help expedite the exploration of a substantial search space of simulations in order to automatically discover interesting behaviours.

Autonomous Multi-Agent Systems are increasingly being deployed in environments where winds and ocean currents can exert a significant influence on their dynamics. Recent work has developed powerful control policies for single agents that can leverage flows to achieve their objectives in dynamic environments. However, in the context of multi-agent systems, these flows can cause agents to collide or drift apart and lose direct inter-agent communications, especially when agents have low propulsion capabilities. To address these challenges, we propose a Hierarchical Multi-Agent Control approach that allows arbitrary single-agent performance policies that are unaware of other agents to be used in multi-agent systems, while ensuring safe operation. We first develop a safety controller solely dedicated to avoiding collisions and maintaining inter-agent communication. Subsequently, we design a low-interference safe interaction (LISIC) policy that trades off the performance policy and the safety controller to ensure safe and optimal operation. Specifically, when the agents are at an appropriate distance, LISIC prioritizes the performance policy, while smoothly increasing the safety controller when necessary. We prove that under mild assumptions on the flows experienced by the agents, our approach can guarantee safety. Additionally, we demonstrate the effectiveness of our method in realistic settings through an extensive empirical analysis with underactuated Autonomous Surface Vehicles (ASV) operating in dynamical ocean currents where the assumptions do not always hold.

Active sensors, such as radar, lidar and sonar, emit a signal into the environment and gather information from its reflection. In contrast, passive sensors such as cameras and microphones rely on the signals emitted from the environment. In the current application of active sensors in multi-agent autonomous systems, agents only rely on their own active sensing and filter out any information available passively. However, fusing passive and active sensing information may improve the accuracy of the agents. Also, there is evidence that bats who use biosonar eavesdrop on a conspecific's echolocation sound, which shows a successful example of implementing active and passive sonar sensor fusion in nature. We studied the effect of such information fusion in the framework of two problems: the collective behavior in a multi-agent system using the Vicsek model and the canonical robotics problem of Simultaneous Localization And Mapping (SLAM). Collective behavior refers to emergence of a complex behavior in a group of individuals through local interaction. The Vicsek model is a well-established flocking model based on alignment of individuals with their neighbors in the presence of noise. We studied the aligned motion in a group in which the agents employ both active and passive sensing. Our study shows that the group behavior is less sensitive to measurement accuracy compared to modeling precision. Therefore, using measurement values of the noisier passive sonar can be beneficial. In addition, the group alignment is improved when the passive measurements are not dramatically noisier than active measurements. In the SLAM problem, a robot scans an unknown environment building a map and simultaneously localizing itself within that map. We studied a landmark-based SLAM problem in which the robot uses active and passive sensing strategies. The information provided passively can improve the accuracy of the active sensing measurements and compensate for its blind spot. We developed an estimation algorithm using Extended Kalman Filter and employed Monte Carlo simulation to find a parameter region in which fusing passive and active sonar information improves the performance of the robot. Our analysis shows this region is aligned within the common range of active sonar parameters.

As robots become more affordable, they will begin to exist in the world in greater quantities. Some of these robots will likely be designed to act as components in specific teams. These teams could work on tasks that are too large or complex for a single robot - or that are merely more efficiently accomplished by a team - such as surveillance in a large building or product delivery to packers in a warehouse. Multiagent systems research studies how these teams are formed and how they work together. Ad hoc teamwork, a newer area of multiagent systems research, studies how new robots can join these pre-existing teams and assist the team in accomplishing its goal. This dissertation extends and applies research in ad hoc teamwork towards the general area of flocking, which is an emergent swarm behavior. In particular, the work in this dissertation considers how ad hoc agents - called influencing agents in this dissertation - can join a flock, be recognized by the rest of the flock as part of the flock, influence the flock towards particular behaviors through their own behavior, and then separate from the flock. Specifically, the primary research question addressed in this dissertation is How can influencing agents be utilized in various types of flocks to influence the flock towards a particular behavior? In order to address this research question, this dissertation makes six main types of contributions. First, this dissertation formalizes the problem of using influencing agents to influence a flock. Second, this dissertation contributes and analyzes algorithms for influencing a flock to a desired orientation. Third, this dissertation presents methods for determining how to best add influencing agents to a flock. Fourth, this dissertation provides methods by which influencing agents can join and then leave a flock in motion. Fifth, this dissertation evaluates some of the influencing agent algorithms on a robot platform. Sixth, although the majority of this dissertation assumes the influencing agents will join a flock that behaves similarly to European starlings, this dissertation also provides insight into when and how its algorithms are generalizable to other types of flocks as well as to general teamwork and coordination research. All of the methods presented in this dissertation are empirically evaluated using a simulator that can support large flocks.

We present multi-agent control methods that address flocking in continuous-time and discrete-time settings. The method is decentralized, that is, each agents controller relies on local sensing to determine the relative positions and velocities of nearby agents. In the continuous-time setting, each agent has double-integrator dynamics. In the discrete-time setting, each agent has the discrete-time double-integrator dynamics obtained by sampling the continuous-time double integrator and applying a zero-order hold on the control input. We demonstrate using analysis, numerical simulations, and experimental demonstrations that agents using the flocking methods converge to flocking formations and follow the centralized leader (if applicable).

A multi-agent system is defined as a collection of autonomous agents which are able to interact with each other or with their environments to solve problems that are difficult or impossible for an individual agent. Coordination in multi-agent systems attracts significant interest in the realm of engineering. Examples of cooperative tasks include mobile sensor networks, automated parallel delivery of payloads, region following formation control and coordinated path planning. One common feature for these systems is acting the agents in a distributed manner (using only local information from their neighbors) to complete global tasks cooperatively so as to increase flexibility and robustness. In this work, two distributed tracking issues in multi-agent systems are investigated in detail: leader-follower flocking with a moving leader for Lagrange networks and distributed average tracking of physical agents.Flocking of multi-agent systems is the motion of a group of agents cohesively to maintain connectivity and avoid collisions. This dissertation proposes novel distributed tracking algorithms to solve the leader-follower flocking problem with a moving leader. The problem is investigated for networked Lagrange systems with parametric uncertainties under a proximity graph. Two cases are considered: i) the leader moves with a constant velocity, and ii) the leader moves with a varying velocity. In the first case, a distributed continuous adaptive control algorithm accounting for unknown parameters is proposed in combination with a distributed continuous estimator for each follower. In the second case, a distributed discontinuous adaptive control algorithm and estimator are proposed to track the varying leader, where only a group of followers have access to the leader. However, in the proposed algorithm the agents use the two-hope neighbors' information and need some global information to determine the control gains. Thus, the algorithm is improved in the next step to use one-hop neighbors' information and to be fully distributed with the introduction of gain adaptation laws. In all proposed algorithms, flocking is achieved as long as the connectivity and collision avoidance are ensured at the initial time and the control gains are designed properly.In the distributed average tracking problem, each agent uses local information to calculate the average of individual varying input signals, one per agent. In this dissertation, two distributed average tracking problems for physical second-order agents are investigated. First, distributed average tracking problem is studied for double-integrator agents with reduced requirement on velocity measurements and in the absence of correct position and velocity initialization. Two algorithms are introduced, where in both algorithms a distributed discontinuous control input and a filter are proposed. In the first algorithm, the requirement for either absolute or relative velocity measurements is removed. The algorithm is robust to initialization errors and can deal with a wide class of input signals with bounded deviations in input signals, input velocities, and input accelerations. In the second algorithm, the requirement for communication. However, the algorithm can deal with a smaller group of input signals. Second, distributed average tracking problem of physical second-order agents with heterogeneous nonlinear dynamics is investigated, where there is no constraint on input signals. The agents' dynamics satisfy a Lipschitz-like condition that will be defined later and is more general than the Lipschitz-type condition. In the proposed algorithm, a control input and a filter are designed for each agent. Since the input signals are arbitrary and the nonlinear terms in agents' dynamics can be unbounded, novel state-dependent time varying gains are employed in agents' filters and control inputs to overcome these unboundedness effects.The dissertation provides a rigorous stability analysis of the introduced control algorithms for both issues and presents simulations that validate the effectiveness of the proposed algorithms.

In this dissertation, we first study the effect of jumps on a stochastic flocking model and discuss characteristics of this model. We investigate its application to understand systemic risk by proposing an interbank lending model with jump diffusions and further show that there will be a higher systemic risk with jumps (i.e., sudden increases or decreases in reserves) in our model. Then, to examine how the systemic risk will be affected when each bank is acting toward their best self-interest, we integrate a game feature with jumps where each bank controls its rate of borrowing/lending to a central bank. We then solve Nash equilibria with finitely many players in this game with jumps, within which the central bank acts as a clearing house and adds liquidity to the system. The result indicates that the linear growth contributed by jumps to the system does not affect the systemic risk in the model. Finally, we propose another model with a central bank as well as peripheral banks and investigate the impact of interaction between all banks on systemic risk. The systemic risk might be reduced if the central bank is allowed to monitor liquidity by solving an optimal control problem. We also provide a mean-field game approach to approximate the equilibria for finitely many players.

Linkages between Complex Adaptive Systems (CAS) thinking and efficiency analysis remain in their infancy. This research associates the basic building blocks of the CAS 'flocking' metaphor with the essential building block concepts of Data Envelopment Analysis (DEA). Within a proposed framework DEA "decision-making units" (DMUs) are represented as agents in the agent-based modeling (ABM) paradigm. Guided by simple rules, agent DMUs representing business units of a larger management system, 'align' with one another to achieve mutual protection/risk reduction and 'cohere' with the most efficient DMUs among them to achieve the greatest possible efficiency in the least possible time. Analysis of the resulting patterns of behavior can provide policy insights that are both evidence-based and intuitive. This research introduces a consistent methodology that will be called here the Complex Adaptive Productive Efficiency Method (CAPEM) and employs it to bridge these domains. This research formalizes CAPEM mathematically and graphically. It then conducts experimentation employing using the resulting CAPEM simulation using data of a sample of electric power plants obtained from Rungsuriyawiboon and Stefanou (2003). Guided by rules, individual agent DMUs (power plants) representing business units of a larger management system,'align' with one another to achieve mutual protection/risk reduction and 'cohere' with the most efficient DMUs among them to achieve the greatest possible efficiency in the least possible time. Using a CAS ABM simulation, it is found that the flocking rules (alignment, cohesion and separation), taken individually and in selected combinations, increased the mean technical efficiency of the power plant population and conversely decreased the time to reach the frontier. It is found however that these effects were limited to a smaller than expected sub-set of these combinations of the flocking factors. Having been successful in finding even a limited sub-set of flocking rules that increased efficiency was sufficient to support the hypotheses and conclude that employing the flocking metaphor offers useful options to decision-makers for increasing the efficiency of management systems.

There are many kinds of scientific applications that run on high throughput computational (HTC) grids. HTC may utilize clusters opportunistically, only running on a given cluster when it is otherwise idle. These widely dispersed HTC clusters are heterogeneous in terms of capability and availability, but can provide significant computing power in aggregate. The scientific algorithms run on them also vary greatly. Some scientific algorithms might use high rates of disk I/O and some might need large amounts of RAM. Most schedulers only consider cpu availability, but unchecked demand on these associated resources that aren’t managed by resource managers may give rise to several issues on the cluster. On the grid there could be different schedulers on different sites and we cannot rely upon features of one kind of scheduler to characterize the nature and features of every job. Most state of the art schedulers do not take into account resources like RAM, Disk I/O or Network I/O. This is as true for the local schedulers as much it is for the grid. Often there is a need to extend these schedulers to solve situations arising from new and/or complex use cases either by writing a plugin for existing schedulers or by CoScheduling. A key issue is when resources like RAM, Disk I/O or Network I/O are used in an unchecked manner and performance degrades as a result of it. Further scheduling jobs that claim the degraded resources could overwhelm the resource to an extent that the resource will finally stop responding or theWe solve system will crash. We schedule based on minimum turnaround time of the sites which will help increase the throughput of the overall workload for the Co-Scheduler, which also is a good load- balancer in itself. The Co-Scheduler is driven by the fact that turnaround time increases when concurrent jobs accessing these resources reach a threshold value which in-turn causes degradation and this is the basis for this work. With an increase in the number of entities concurrently using the resource, there is a need to monitor and schedule concurrent and unmanaged access to any given resource to prevent degradation. These issues that we encounter in real life at the Holland Computing Center are the basis and motivation for tackling this problem and for developing an adaptive approach for scheduling. This co-scheduler must be aware of multi-resource degradation, balance load across multiple sites and run clusters at high efficiency and share resources fluidly. An initial implementation tested at HCC will be evaluated and presented. Adviser: David Swanson

Behavioral animation is a category of computer animation that enables objects to determine their own actions. This saves an animator from having to determine every detail of movement for each object in the animation. As the number of objects within an animation increases, specifying the position of each object becomes increasingly difficult. Flocking is an example of behavioral animation. Some examples of flocking can be seen in movies, such as the stampede of the antelopes in The Lion King, the herds of dinosaurs in Jurassic Park, and the massive battle scenes in The Lord of the Rings. In this project, I have enhanced flocking to convey emotion. This is achieved using only the movement of objects in relationship to one another. The effectiveness of the flock s motion in conveying a given emotion is judged by human observers via an on-line flocking system. This system allows users to rate how well an emotion is conveyed by the flock. User feedback is used to further adjust motion parameters with the goal of obtaining the best representative motion for each emotion.

The purpose of this research has been to develop methods of improving the generalization capabilities of artificial neural networks. Tools for examining the influence of individual training set patterns on the learning abilities of individual neurons are put forth and utilized in the implementation of new network learning algorithms. Algorithms are based largely on the supervised training algorithm: backpropagation, and all experiments use the standard backpropagation algorithm for comparison of results. The focus of the new learning algorithms revolve around the addition of two main components. The first addition is that of an unsupervised learning algorithm called flocking. Flocking attempts to provide network hyperplane divisions that are evenly influenced by examples on either side of the hyperplane. The second addition is that of a multi-tasking approach called convergence training. Convergence training uses the information provided by a clustering algorithm in order to create subtasks that represent the divisions between clusters. These subtasks are then trained in unison in order to promote hyperplane sharing within the problem space. Generalization was improved in most cases and the solutions produced by the new learning algorithms are demonstrated to be very robust against different random weight initializations. This research is not only a search for better generalizing ANN learning algorithms, but also a search for better understanding when dealing with the complexities involved in ANN generalization.