Differences

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

--- people:andres_ruiz:project [2014/10/13 19:41] – afruizc
+++ people:andres_ruiz:project [2014/12/09 06:07] (current) – afruizc
@@ Line 1: / Line 1: @@
-====== Achieving global communication ======
+====== Finding my place in the crowd: Group formation and localization in a virtual environment. ======
-=== Importance Of Communication: ===
+Final link of download: http://cs.unm.edu/~afruizc/file.zip
-The importance of communication has been discussed in class before, but essentially it comes down to three points:
-  * Spacial translation of entities composed by more than one element.
-  * Achieving of global objectives that are otherwise not possible without communication.
-  * The development of complex behavior is tightly coupled to the communication process.
-=== Design of the protocol: ===
+==Graphs:==
-{{:people:andres_ruiz:fsm.png?|}}
+{{:people:andres_ruiz:organization.pdf|}}
+{{:people:andres_ruiz:localization.pdf|}}
+{{:people:andres_ruiz:mixed.pdf|}}
+== Final DRAFT of the paper: ==
+http://cs.unm.edu/~afruizc/finding-place-crowd.pdf
-I have explored two different options so far. The one involving a third party seems more promising.
+== Abstract: ==
+In the Movable Feast Machine, direct interaction is limited to small regions of space, but many computations could benefit from larger scale structure. This paper presents a simple aggregation and localization strategy allowing individuals to form communicating groups and find their own absolute positions within the group
-__TP protocol (Third Party protocol):__
+== Model Description: ==
-The protocol incorporates a new element called the Organizer element. This element is in charge of sensing the environment, passing input arguments but more importantly, providing a global structure for the elements to follow. This is done by changing the states of the elements based on the things the Organizer element has seen.
+Figure 1: [[http://cs.unm.edu/~afruizc/ASDF_element.png|External Link]]
-The protocol is based on states. This means that every atom should be in one state, and such state determines what it is that the atom should be doing. The states can have external inputs, that are passed by the Organizer element. This external inputs are selected based on the sensing the Organizer element has been performing.
-The protocol is simple and flexible enough that every element can adapted without much changes, but at the same time provides an structure that makes different clusters of elements do either the same or separate things.
-= Advantages: =
+In order to understand the model, it is first important to give a couple of definitions that will help in the complete realization of the problem.
-  * Modularity.
+The density of the element means the amount of empty spaces that are allowed to exist between any pair of elements.
-  * Abstraction.
+The state of an element is basically a name that is given to the conditions that describe one element at an specific point of time.
-  * Simplification of design.
+The attractor state is the state in which an ASDF element moves elements that are around and brings them close to where the element is located. The process of how this movement is done is expanded in the next sub-sections.
-= Limitations: =
+There is a two stage process that will successfully achieve the desire result of localization of each one of the elements inside their blob.
-  * Overlapping states.
+These self-organization and localization stages are roughly described in section 3.1, and are given a more thorough treatment in section 3.2.
-  * Not unlimited behavior.
-=== Concreteness in the paper: ===
+Section 3.1: Model Overview.
-Illustrate the protocol, give several abstract examples and one (non-trivial) concrete example using this protocol. Implement a three-stage application in which the three elements of communications are shown. The first one is based on the movement, the second one on the achieving of some sort of objective and the third one on showing that the resulting entity is indeed a complex entity.
-So far I have almost finished the idea for movement, and have been toying around with the idea for achieving an objective. After the first movement stage is entirely completed, I will dedicate my time to the last and more influential part of the project: showing that the entity was indeed complex.
+As mentioned earlier, the ASDF elements will self-assemble in different blobs that will then start their localization process based on where they consider their global position in the blob is. After several iterations of the localization process, convergence will be achieved and all the elements will then have an idea of where their place in the blob is. This place will be determined by the amount of cells that one element is away from the boundary elements. A boundary element is an element that at a certain coordinate (north, south, west or east) doesn’t have any neighbors towards that direction, i.e. all the neighbouring cells in that direction are empty. After the localization process, if there is some sort of interruption (like a nuke or some elements are moved by dreg), the elements would go back to the self-organization stage and then the localization process will be repeated.
+We now briefly describe what an Event in the MfM architecture is because this will provide us with a useful framework to describe the behavior of the ASDF element in both, the organization and the localization stage. In its most essential case, an event is the means by which the mfm tells an atom that it is their turn to wake up, interact with the environment, change its internal and its neighbors’ state and go back to sleep, An event is assigned at random to each event, and there is no guarantee on the amount of events an atom is receiving however, because of probabilities and calculations it is true in practice that on average, all the elements will get an event after certain period of time.
+Section 3.2. Model detailed description
+We now give all the details on how both stages of the operations are performed, and we highlight the relevant points that allow our element to perform as expected.
+Section 3.2.1: Self-organization process
+The self-organization process is the basis that allows the final result to be achieved. The resulting state in which the elements are at the end of this stage, will determine how good or bad the localization process will turn out to be. The self-organization process occurs as follows, and it is summarized in algorithm 1.
+Algorithm 1:
+	function self_organization():
+		if (I become attractor):
+			A[] = empty elements in ew.
+			B[] = ASDF elements in ew.
+			i = j = 0
+			while (empty_spots && elements_to_relocate):
+				change pos of element B[i] to A[j]
+				turn B[i] into attractor
+				increment i and j
+In words, what the self-organizing procedure does is: at the beginning of an event, every element has some chances of becoming an attractor, if it turns out that the element does not become an attractor, the normal execution of the behavior function will continue; if on the contrary, the element does become an attractor, then it will gather information from it’s event window, this information includes all the elements that are empty, starting from radius 1 to radius 4, and other ADSF elements starting from radius 4 to radius 1. These two orderings of operations are important because they allow for the elements stay as close as “possible”. After having these two pieces of data, the element will start allocating the ASDF elements that were found on the outer layers into the inner layers of empty spaces, while also turning this elements into attractors creating some sort of a zombie effect.
+After this step is done some more work has to be done in the density blahh..
+Section 3.2.2: Localization process
+In order to carry out the Localization Process (locp from now on), it is important to have the elements as close together as possible, or at least, as least spread as possible, because this will provide a better sense of self-awareness of each element’s position on the blob they belong to.
+This second stage assumes that, in addition to determining whether an element is an attractor or not, the elements have to have some state stored in them. Each ASDF element has four counters for north, east, south and west which indicate their distance to the boundary of the enclosing square that is seen in the last lower square of figure 1. Algorithm 2 describes the process of localization.
+Algorithm 2
+	function self_organization():
+		if (has_converged?):
+			if (this should check again):
+				if (! has_converged?):
+					set convergence flag OFF
+					alert neighbors of discrepancy
+		else:
+			this.count_north = north_n.count_south + 1
+			this.count_south = north_n.count_north + 1
+			this.count_east  = north_n.count_west  + 1
+			this.count_west  = north_n.count_east  + 1
+			# Now for each direction check the two directions
+			# orthogonal to it in order to determine convergence
+			# and to fix discrepancies.
+			# For north I should then check east and west and
+			# compare my north counter with them.
+			this.count_north = max(this.count_north, east_n.count_north, west_n.count_north)
+			# and perform this for the other three counts.
+			# after all has been done, check for convergence.
+			if (has_converged?):
+				set convergence flag ON
+The locp can get confusing, which is why we will try to cover all the caveats that it brings along. It is helpful to look at figure 1 and understand this as a converge process, meaning all the elements in a blob will eventually have a correct value on each one of their counters, however throughout different iterations the values for some elements might be wrong. In fact, for the first iteration of each element, only the elements that adjoin with the enclosing rectangle will have the right value for only one coordinate, every other element will have their counters tweaked.
+Think about the best way to explain the crap out of this!
-=== Todo list: ===
-  * Make the Organizer element much more smarter:
-      * Tell the ASDF elements to go to a place such that the distance traveled is partially minimized.
-      * Move in a way that Organizer's event window captures as much elements as possible.
-  * Think up the experiment that will determine the complexity.