Computer Science Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/2756
Browse
Search Results
Item The Influence of Collective Working Memory Strategies on Agent Teams(2007-08-03) Winder, Ransom Kershaw; Reggia, James A.; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Past self-organizing models of collectively moving "particles" (simulated bird flocks, fish schools, etc.) typically have been based on purely reflexive agents that have no significant memory of past movements or environmental obstacles. These agent collectives usually operate in abstract environments, but as these domains take on a greater realism, the collective requires behaviors use not only presently observed stimuli but also remembered information. It is hypothesized that the addition of a limited working memory of the environment, distributed among the collective's individuals can improve efficiency in performing tasks. This is first approached in a more traditional particle system in an abstract environment. Then it is explored for a single agent, and finally a team of agents, operating in a simulated 3-dimensional environment of greater realism. In the abstract environment, a limited distributed working memory produced a significant improvement in travel between locations, in some cases improving performance over time, while in others surprisingly achieving an immediate benefit from the influence of memory. When strategies for accumulating and manipulating memory were subsequently explored for a more realistic single agent in the 3-dimensional environment, if the agent kept a local or a cumulative working memory, its performance improved on different tasks, both when navigating nearby obstacles and, in the case of cumulative memory, when covering previously traversed terrain. When investigating a team of these agents engaged in a pursuit scenario, it was determined that a communicating and coordinating team still benefited from a working memory of the environment distributed among the agents, even with limited memory capacity. This demonstrates that a limited distributed working memory in a multi-agent system improves performance on tasks in domains of increasing complexity. This is true even though individual agents know only a fraction of the collective's entire memory, using this partial memory and interactions with others in the team to perform tasks. These results may prove useful in improving existing methodologies for control of collective movements for robotic teams, computer graphics, particle swarm optimization, and computer games, and in interpreting future experimental research on group movements in biological populations.Item Adapting Swarm Intelligence for the Self-Assembly of Prespecified Artificial Structures(2007-04-25) Grushin, Alexander; Reggia, James A; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The self-assembly problem involves designing individual behaviors that a collection of agents can follow in order to form a given target structure. An effective solution would potentially allow self-assembly to be used as an automated construction tool, for example, in dangerous or inaccessible environments. However, existing methodologies are generally limited in that they are either only capable of assembling a very limited range of simple structures, or only applicable in an idealized environment having few or no constraints on the agents' motion. The research presented here seeks to overcome these limitations by studying the self-assembly of a diverse class of non-trivial structures (building, bridge, etc.) from different-sized blocks, whose motion in a continuous, three-dimensional environment is constrained by gravity and block impenetrability. These constraints impose ordering restrictions on the self-assembly process, and necessitate the assembly and disassembly of temporary structures such as staircases. It is shown that self-assembly under these conditions can be accomplished through an integration of several techniques from the field of swarm intelligence. Specifically, this work extends and incorporates computational models of distributed construction, collective motion, and communication via local signaling. These mechanisms enable blocks to determine where to deposit themselves, to effectively move through continuous space, and to coordinate their behavior over time, while using only local information. Further, an algorithm is presented that, given a target structure, automatically generates distributed control rules that encode individual block behaviors. It is formally proved that under reasonable assumptions, these rules will lead to the emergence of correct system-level coordination that allows self-assembly to complete in spite of environmental constraints. The methodology is also verified experimentally by generating rules for a diverse set of structures, and testing them via simulations. Finally, it is shown that for some structures, the generated rules are able to parsimoniously capture the necessary behaviors. This work yields a better understanding of the complex relationship between local behaviors and global structures in non-trivial self-assembly processes, and presents a step towards their use in the real world.