Differences

This shows you the differences between two versions of the page.

--- papers:ezra_stallings [2014/11/03 21:01] – vyross
+++ papers:ezra_stallings [2014/12/01 21:45] (current) – vyross
@@ Line 1: / Line 1: @@
-====== Active Sensing in an Indefinitely Scalable Machine ======
+====== Resource Finding and Distribution in an Indefinitely Scalable Machine ======
+{{:papers:alife_paper_ezra_stallings.pdf|}}
+{{:papers:cs491_presentation.pdf|}}
-===== Abstract =====
-Working in a spatially oriented system, creating a large network for communication or resource sharing is complicated by the difficulty of implementing useful data structures. We propose a node-based pathfinding system for use in a simulation where a number of central nodes attempt to engage in need-based resource allocation. We found that using spatially linked lists and a brownian search method made for a highly effective means of discovering routes and building a network organically in a chaotic environment.
-===== Description of Model =====
-The model was built to address some of the limitations of the MFM, and to attempt an architecture for overcoming these shortcomings for large-scale organized, stigmergic behavior. The primary limitation in question is the small event window for each element - a radius of 4 sites, manhattan distance, for a total of 49 elements visible. Two direct consequences of this size are speed of simulation (less processing per-site) at the expense of scope, and a slow “speed of light”. Nothing can move farther than the event window, so the maximum attainable speed in the machine is the size of the event window - 4 sites-per-update.
-As a framework for solving this problem in a simple yet possibly useful manner, we proposed a method for routing resources in the form of Res atoms, while trying to consume as little of space as possible with the routing mechanism itself, and without altering the Res. As a metric for evaluating the performance of the model, we used a Depot element. The Depot element is stationary, and will with some probability randomly go into a state of high Res demand. While in this state, it will consume any Res it encounters. Normally, it will occasionally go into a state of low Res demand, and consume an available single Res to satisfy the demand. A system where Depots stay in high demand for a long period of time can be estimated as performing more poorly than a system where their demand gets satisfied quickly. The low-demand state exists primarily to provide low-level signal noise.
-In order to form an actual network, a means of connecting Depots and passing messages/routing Res between them is required. In order to accomplish this, the following elements were employed; the Scout and the Breadcrumb. Scouts are occasionally, randomly created by Depots, and will wander around using Brownian motion until they either find another Depot or die of “old age”. Upon finding another Depot, they will determine how many connections that Depot has. If it has fewer than some number of maximum connections, the scout will determine that it is available, and will form a semi-permanent path between its origin and the Depot it discovered.
-The exact movement formula of Scouts is to move at speed S in direction vector D, with a one-in-[stutter_chance] odds of altering their final position by 1 in a randomly selected direction, and a one-in-[change_direction_chance] of changing D after each move. [stutter_chance] and [change_direction_chance] are global element parameters, and cannot change during run-time.
-Breadcrumbs are laid out behind Scouts, dropped in every site the Scout visits as it wanders around. Each breadcrumb knows what Scout it belongs to (a random 10-bit ID, chosen on creation time of the Scout), as well as the ID of it’s predecessor and successor in what amounts to a spatial linked-list. Breadcrumbs are therefore aware of a gradient direction (high-to-low). Although the Breadcrumb IDs are also 10-bits, they start with 0 at scout-creation-time, increase by 1 at each creation, and Scouts are set to die of old age before reaching age 2^10; thus, it is impossible to encounter wrap-around issues in the scope of this simulation, and the gradient will be preserved.
-Breadcrumbs engage in a self-optimizing behavior to compensate for noise in the Scout’s movement. Each time a Breadcrumb gets an update, it scans the event window for it’s predecessor pred and successor succ Breadcrumbs. If it is somewhere in the middle of a trail, it will attempt to move to a random valid point halfway between pred and succ, as determined with manhattan distance. If pred and succ are within 3 sites of each other, the Breadcrumb atom will tell pred and succ to “point to” each other, and remove itself.
-Once a Scout finds an available Depot, a signal is passed along it’s trail of Breadcrumbs, telling them to become active. Once they are active, any Res they encounter is passed down the gradient (towards the 0-indexed Breadcrumb) by default. If a Scout’s internal timer expires and it dies of old age, a kill signal is passed along the Breadcrumb trail, and they remove themselves from the simulation.
-The vital routing behavior is provided by Breadcrumbs, which are able to pass messages and Res according to their gradient. Each Breadcrumb knows whether Res should be passed high-to-low or low-to-high. Additionally, Breadcrumbs have two 10-bit message fields; an upstream and a downstream message. Each message also has a four-bit field to indicate its strength, and another to represent a cooldown. Each time a message is relayed, the strength is decremented, and a message with strength zero will not be relayed. Message cooldown is used to allow a signal to traverse a network without causing feedback. In our model, messages were used to tell Breadcrumbs to change the gradient direction for Res transportation, though they could be used for other purposes outside of the scope of this paper.
-Message relaying is Breadcrumb-to-Breadcrumb. During a Breadcrumb’s behavior update, it will first check if the up/downstream message has a strength greater than zero, and that the up/downstream message has a cooldown of exactly zero. If both conditions pass, it sets the cooldown to 16 (configurable), the signal strength to 0, and copies the message and signal strength into the predecessor/successor atom, as applicable. When exchanging hands from stream to stream, end-node Breadcrumbs will decrement the strength of the signal before copying it into a neighboring end-node Breadcrumb. When an end-node Breadcrumb updates, it checks if it has something in either the up or downstream message field that does not belong there (if it has index zero, it can’t pass things to a predecessor). If it finds such a message, it simply moves it into the correct field, and does message passing as described above. This could result in messages being overwritten before they are passed, but the system needs to be robust to such perturbations regardless.
-We compared three scenarios to determine the viability of this technique for resource management in the MFM. In Scenario A, we have no network, just isolated, stationary Depots. In Scenario B, we have a network, but no message passing in order to alter the flow of resources - all Res goes in the default direction. And in Scenario C, a message can be passed to change the flow of Res. In order to make this message work, it is altered whenever transmitted to another trail’s end-node Breadcrumb with respect to that trail’s direction.
-===== Conclusion =====
-////////REDO//////////
-This method for pathfinding works well for sparse structures, demonstrating both an ability for the concept to work with a clear goal in the context of a more complex system (the conflict) and an ideal density level for the system to allow pathfinding to work well. If the machine is too sparsely populated, it can take scouts far too long to find their adversaries, while in a densely populated system the optimization (and eventually, the movement of the scouts) is severely limited. Additionally, when breadcrumbs persist too long, they can contribute to system clutter; I found that giving them a built-in maximum age of [X] helped mitigate this, as well as causing them to die after they are finished functioning for a single alert cycle.