Embedded Files
In my thesis I investigated if an idealized model of a complex system is capable of solving non-trivial tasks by an emergent system behavior, and if so, how does such a model solve these tasks. First, I proposed several problems that are difficult to solve by a system without a global counter, where the systems components communicate only with locally adjacent components, and each component updates its state based on the state of its local neighbors. In general, such tasks are difficult for these decentralized and locally communicating systems, because the solution to a problem is represented by a global configurations of the entire systems. While the result is represented by the configuration of the entire component network, the information based on which the individual components update their state comes only from locally connected components. Next, I used genetic algorithms to evolve solutions to these problems. Although the algorithms were looking for increasingly better solutions, I was not interested in finding the best solutions for given problems. Instead, my research focused on analysis of the solutions found by genetic algorithms and an explanation of how does a system solve the proposed problem.
Let's look at an example that might explain the above paragraph. Let's assume the simplest form of such architecture: a network consists of a two-dimensional regular lattice of identical binary-state components that are connected to locally adjacent components within given radius. Starting from some initial configuration of component states, at each time step each component updates its state, computing its new state as a function of the components that it is connected to (the neighborhood components). For example, for a network with component connectivity radius r=1,
the neighborhood of a components will consist of the component itself and its two nearest neighbors; in a two-dimensional regular lattice each components with r=1 will have a neighborhood of 9 components (8+1: 8 neighboring components plus itself). Component updates occur synchronously: at each time step all components update their states simultaneously using the current values of their own and their neighbors' states to compute their new states for the next time step. (see Figure 1 for illustration of component network)
Figure 1:
Illustration of a complex system model. Model has a regular component connectivity with radius r=1, binary state components (white/black), and synchronous updates. The lattice regularity is simulated by a toroidal boundaries: components on the right border are connected to components on the left border etc.
The so-called density classification (or majorityclassification) task for the above described network has been widely studied in a context of complex systems. The goal is to design a network that decides whether or not the initial configuration (IC) contains a majority of 1s (i.e., has high density). If it does, the whole lattice should iterate---within fixed number of time steps---to the fixed-point configuration of all 1s (i.e., all cells in state 1 for all subsequent iterations); otherwise it should similarly iterate to the fixed-point configuration of all 0s. Designing an algorithm to perform the density classification task is trivial for a system with a central controller or central storage of some kind, such as a standard computer with a counter register or a neural network in which all input units are connected to one or more hidden units. However, the task is nontrivial for a network with small component connectivity radius r (r=1). Figure 2 shows behavior of three rules evolved by genetic algorithms on solving the density classification task on randomly generated initial configuration. The same initial configuration was used for all three rules.
Figure 2: Animation of Rule 1 by Wolz and deOliveira, Rule 2 by Manuel Marques-Pita, and Rule 3 found by me, on 39 x 39 lattice. The first time step represents the initial configuration and all three rules eventually converge to the correct configuration of all black.
Given this problem (or a goal for the network to converge to), an alternative approach to computation in such network is to use the complex dynamics and pattern formation behavior of a network to perform collective, genuinely parallel computations (see Figure 2). This approach has been exemplified in work on applying evolutionary computing methods to design models of complex systems (such as cellular automata, RBN, etc) to perform computations. In this case, the network update rules -- using the configuration of local neighborhood -- plays the role of ``program'', the initial configuration plays the role of "input", and a later configuration or configurations play the role of "output".
One contribution of my work was in analysis of how a two-dimensional model of a complex system processes information in order to solve a problem - the density classification task in this case. Figure 2 shows that all rules have a space-time behavior that can be described by a formation of lattice-wide patters that move and interact with each other. The hypothesis is that the formation of such patterns, their motion and interactions with each other are the mechanism of computation in such system. One goal of my work was to identify these patterns, by outlining these cohesive patterns in the space time behavior with a border line, in order to better understand the nature of computation in these systems.Figure 2 second row shows the output of one of the techniques I designed and implemented.
Broad research context.
For a theoretical research area (such as the emergent computation in complex systems) to gain traction, I have to show its usefulness as an application. To do so, I will relax the constraint definition of a complex system model to resemble a real-world network and implement it as a physical architecture. The application might resemble a sensor network as described earlier or a novel communication environment for a network of mobile devices. My study of general network properties might reveal links between network architecture attributes and their capability as a "computational substrate". Better understanding of network architectures might lead to novel learning and analytical tools for a variety of applications that include multi-agent environments, social networks, integrated circuits design etc. Please see research prospectus for a concrete example.
Autonomous Emergent Anomaly Detection in Sensor Networks
The overall goal of this proposed research is to assess the feasibility of detecting anomalies by emergent system behavior in massively parallel, decentralized, locally connected, asynchronous sensor networks. In particular, I aim to design, build, and implement an architecture model that would simulate how to utilize millions of small unreliable sensors that can communicate only with spatially adjacent units without a central controller or existence of a system-wide clock. If such architecture design proves “computationally-capable” (or able to solve various problems) it will allow for robust anomaly detention by repairing lost information where devices and connectivities fail, energy-efficient use by powering-off inactive asynchronously communicating devices, and adaptable network deployment by utilizing network self-assembly and emergent task completion. I foresee utilization of this approach in several areas where sensor network deployment and data collection is difficult, including more accurate environmental modeling for coastal regions, better monitoring of remote oceanic regions, or contributing to the urban shield program by spontaneously detecting threshold levels of hazardous air conditions.
Consider the following scenario: a desired task is to detect a disturbance in the ocean's floor in an area with high underwater volcanic activity. Conventional approaches to solve this problem might include use of sonar from a boat or dispatching a submersible. Both methods are costly, timely, and yield results with poor accuracy. Detection and alert of such an anomaly might be useful for planning of transcontinental communication networks, shipping routes, etc. An alternative solution to this problem would be to place several thousands of low-powered pressure sensors on the sea floor. These simple devices could be dropped from an airplane or a boat that covers the area of interest in a grid pattern. Once the sensors rest in place they self-assemble into a network through each sensor establishing a connection with spatially adjacent (reachable) sensors. In the next step, each sensor would broadcast its state to the locally connected neighbors, and set its state to “normal” (representing no anomaly detected, as supposed to “active” that denominates that a sensor detected an anomaly). Once such network topology is established, the system state can be read out from a limited number of randomly selected sensors rather than collecting information from every sensor or aggregating information by special purpose network-nodes. Establishing connection with a fixed – usually a square root or logarithmic – number of sensors constitutes the only cost of reading the network's output. The final mode of network operation would be for each sensor to record an unexpected change of pressure that might signify change in depth due to lift in ocean floor, an interference with marine life, the passing of a tidal wave, a device failure etc. A sensor would then change its state to “active” and make its state available to the neighboring sensors. Each neighbor would then update its state to either “active” or “normal” state based on a simple “rule-book” that network was programmed to use as an update schema. One such “rule-book” might be a simple threshold-rule: if the number of neighboring “active” sensors is above a desired threshold, then set the sensor's state to “active,” otherwise set its state to “normal.” A solution to the anomaly detection task would be a convergence of all sensors to “active” state if a threshold number of sensors were activated, and all sensors would remain in “normal” state if the total number of activated sensors is below a desired count. Recall that a readout from a linear number of sensors is used to determine if the network converged or not.
This simple example illustrates the advantages of treating a sensor network as a complex system. These include: architecture is robust to errors (either environmental, communication, or a device failure), sensors are locally connected which minimizes the network's communication overhead, costly synchronization protocols are not needed due to asynchronous sensor updates and there is no need for a central processing unit or collecting state information from all sensors in the network. The most powerful feature of this architecture is the way it computes the answer to a given task: by an emergent system behavior. In other words, each sensor updates its state based solely on information from locally connected sensors, even though the task is to decide if a number of “active” sensors in the entire network exceeds a threshold value (recall, the network does not have a global counter which would make this task trivial).
The challenges of deploying such networks in a field are in architecture design and programming such architectures to perform desired tasks (see Figure 0 for illustrations). In particular:
- Asynchronous update schemes: the order in which the sensors are being updated is determined at random. I propose updating sensors in random order (with given distribution), only updating a selected subset of sensors, and using a machine learning algorithm(s) to evolve timing schemas to combine more than one “rule-book” to compute a task solution.
- Error prone lattice: a subset of sensors in the lattice does not update, updates incorrectly, or contains faulty connections to the neighboring sites. Deployment of a sensor network does not guarantee a perfect two-dimensional grid placement nor reliable operation of all sensors. In my experimentation, I plan to analyze how a sensor architecture model generates faulty information signals, how these signals propagate though the lattice, and if the solutions are robust enough to repair the errors automatically.
- Non-local connectivity: a subset of sensors has a limited number of neighbors can communicate their state to distant sensors. It is unknown under what conditions these non-local connections can improve or hinder the ability of the system to perform a given task. A ”rule-book” that was designed to use non-local connections might show different information processing behavior than a “rule-book” for a lattice where sensors with local connectivity.
- “Rule-book” design: the update schema used by each sensor to update its state based on information from its neighboring sensors. Number of states permutations for locally connected sensors is very large, making the “rule-book” design difficult. In my previous research I successfully used stochastic search algorithms to design “rule-book” solutions for given problems. I intend on using this approach in addition to exploring additional ways of designing solutions. These include artificial neural networks and genetic programming.
Figure 0: Illustration of sensor network's alternative connectivity topologies and timing schemas
Previous and Current Research
In my doctoral thesis, I analyzed a mechanism of information processing used by a two-dimensional model of a complex system, namely a two-dimensional cellular automata (2DCA), to solve given tasks. One of the tasks I analyzed was the density classification task that is very similar to the earlier described threshold anomaly detection task. In my thesis I reported that the found solutions to this task are robust to error-prone “rule-books” and the dependency of a “rule-book's” accuracy to increasing number of system components. The main contribution of my work was in analysis of how a model of complex system processes information in order to solve a problem. I did this by designing statistically-based methods that identify system-wide patterns that contribute to task completion.
In addition to analyzing how a model of a complex system “computes” a given problem, I also proposed and found solutions for novel tasks that are solved by emergent system behavior. These tasks include: (1) the global synchronization task that coordinates all network components to assume the same state and in the next time-step all components change their state to the opposite one, (2) the leader selection task that first synchronizes all components to an inactive state and then selects one system component to be activated as a leader, (3) the bounding task that outlines a group of active network components by an outside perimeter and activates all components inside of such perimeter, and finally (4) the niching task (or a foreground vs. background contrasting task) that activates the network components if they belong to an area with density distribution (foreground) other than the ambient density distribution (background) (see Figure 1 for illustrations). To solve all these tasks requires collective computation beyond the component's local connectivity, but more importantly, the solutions to these tasks illustrate the versatility of a complex system model to solve tasks with different character. The fact that the solutions to these tasks have very different behavior contributes to the evidence that the system is flexible and capable of solving problems in a variety of ways.
(a)
(b)
(c)
Figure 1: Sample tasks solved by a two-dimensional model of complex system where each site (black or white) represents a system component arranged in a regular grid pattern. All components communicate synchronously. Black sites represent network components in “active” state while white sites represent “inactive” or “normal” components. Each set of images shows the initial configuration on the left and an ideal solution to the task on the right. (a) density classification (or threshold detection) task shows all white configuration for initial configuration with starting configuration under the threshold value and all black for the initial configuration with greater density than threshold, (b) bounding task shows the sparse variant of the task on the top and dense task variant on the bottom, and (c) niching task also has two variants – a positive showed in the images on the top and the negative on the bottom.
My previous experimentation used models with synchronous communication. Currently, I study if a two-dimensional array of components with asynchronous communication can also solve the previously defined tasks. The preliminary results show that although the patterns of local information updates in asynchronous networks are different then those in synchronous lattices, networks with asynchronous communication do indeed successfully solve the density classification and leader selection tasks.
The goal of my research is to determine the necessary configurations of component connectivity, the error rates of system components, and the timing requirements for a complex system approach to solve problems by cooperative collective behavior. One of my future goals is to search for additional tasks and find solutions for particular sensor network applications. I intend to apply my research as a real life application of a complex system approach to anomaly detection in sensor networks. My studies of the theoretical aspects of complex systems in combination with the architecture of deployed sensor networks provides strong enough evidence for a feasible application of anomaly detection in sensor networks by emergent system behavior.
Google Sites
Report abuse