Home
Resource
Stochastic maze solving under the geometric amoebot model
PDF
PDF format is widely accepted and good for printing.
Plug-in required
PDF-1(2.66 MB)
Citation & Export
View Usage Statistics
Staff View

Citation & Export
Hide

Simple citation

Yadav, Aayush. Stochastic maze solving under the geometric amoebot model. Retrieved from https://doi.org/doi:10.7282/t3-mnk7-xe10

Export

Click here for information about Citation Management Tools at Rutgers.

Statistics
Hide

Description

TitleStochastic maze solving under the geometric amoebot model
NameYadav, Aayush (author); Shende, Sunil (chair); Birget, Jean-Camille (internal member); Lun, Desmond (internal member); Rutgers University; Camden Graduate School
Date Created2021
Other Date2021-05 (degree)
SubjectProgrammable matter, Computer Science
Extent1 online resource (vi, 44 pages)
DescriptionA self-organizing particle system (SOPS) is a collection of programmable units called particles with fixed computational capabilities. Within a particle system, individual particles execute fully distributed, local, asynchronous algorithms to achieve collective movement, configuration and co-ordination.

Leveraging recent developments in stochastic algorithm design for such systems, we propose a Markov chain based algorithm for collective maze-solving under the geometric amoebot model of SOPS for certain types of mazes. The inspiration for our algorithm comes from the algorithm for phototaxing, which uses external stimuli to create asymmetries in particle activity levels, thereby causing displacement of the particle system away from the stimuli.

Phototaxing has been proven for systems of two and three particles. We give an algorithm to verify phototaxing in arbitrarily large systems given the set of possible configurations are known. Using this algorithm, we verify that phototaxing also occurs in particle systems of size four.
systems of size four.
NoteM.S.
NoteIncludes bibliographical references
Genretheses, ETD graduate
Persistent URLhttps://doi.org/doi:10.7282/t3-mnk7-xe10
LanguageEnglish
CollectionCamden Graduate School Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.
Version 8.5.5
Rutgers University Libraries - Copyright ©2024