東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Collaborating in Motion: Distributed...

Daymude, Joshua J.

Linked to FindBook

Google Book

Amazon

博客來

Collaborating in Motion: Distributed and Stochastic Algorithms for Emergent Behavior in Programmable Matter.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Collaborating in Motion: Distributed and Stochastic Algorithms for Emergent Behavior in Programmable Matter./
Author:	Daymude, Joshua J.
Published:	Ann Arbor : ProQuest Dissertations & Theses, : 2021,
Description:	454 p.
Notes:	Source: Dissertations Abstracts International, Volume: 82-11, Section: B.
Contained By:	Dissertations Abstracts International82-11B.
Subject:	Computer science. -
Online resource:	https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28323007
ISBN:	9798728267126

Collaborating in Motion: Distributed and Stochastic Algorithms for Emergent Behavior in Programmable Matter.
Daymude, Joshua J.

Collaborating in Motion: Distributed and Stochastic Algorithms for Emergent Behavior in Programmable Matter. - Ann Arbor : ProQuest Dissertations & Theses, 2021 - 454 p.

Source: Dissertations Abstracts International, Volume: 82-11, Section: B.

Thesis (Ph.D.)--Arizona State University, 2021.

This item must not be sold to any third party vendors.

The world is filled with systems of entities that collaborate in motion, both natural and engineered. These cooperative distributed systems are capable of sophisticated emergent behavior arising from the comparatively simple interactions of their members. A model system for emergent collective behavior is programmable matter, a physical substance capable of autonomously changing its properties in response to user input or environmental stimuli. This dissertation studies distributed and stochastic algorithms that control the local behaviors of individual modules of programmable matter to induce complex collective behavior at the macroscale. It consists of four parts.In the first, the canonical amoebot model of programmable matter is proposed. A key goal of this model is to bring algorithmic theory closer to the physical realities of programmable matter hardware, especially with respect to concurrency and energy distribution. Two protocols are presented that together extend sequential, energy-agnostic algorithms to the more realistic concurrent, energy-constrained setting without sacrificing correctness, assuming the original algorithms satisfy certain conventions.In the second part, stateful distributed algorithms using amoebot memory and communication are presented for leader election, object coating, convex hull formation, and hexagon formation. The first three algorithms are proven to have linear runtimes when assuming a simplified sequential setting. The final algorithm for hexagon formation is instead proven to be correct under unfair asynchronous adversarial activation, the most general of all adversarial activation models.In the third part, distributed algorithms are combined with ideas from statistical physics and Markov chain design to replace algorithm reliance on memory and communication with biased random decisions, gaining inherent self-stabilizing and fault-tolerant properties. Using this stochastic approach, algorithms for compression, shortcut bridging, and separation are designed and analyzed.Finally, a two-pronged approach to "programming" physical ensembles is presented. This approach leverages the physics of local interactions to pair theoretical abstractions of self-organizing particle systems with experimental robot systems of active granular matter that intentionally lack digital computation and communication. By physically embodying the salient features of an algorithm in robot design, the algorithm's theoretical analysis can predict the robot ensemble's behavior. This approach is applied to phototaxing, aggregation, dispersion, and object transport.

ISBN: 9798728267126Subjects--Topical Terms:

523869
Computer science.
Subjects--Index Terms:

Distributed algorithms

Collaborating in Motion: Distributed and Stochastic Algorithms for Emergent Behavior in Programmable Matter.
LDR:03866nmm a2200385 4500 001 2285182
005 20211129124000.5
008 220723s2021 ||||||||||||||||| ||eng d
020 $a 9798728267126
035 $a (MiAaPQ)AAI28323007
035 $a AAI28323007
040 $a MiAaPQ $c MiAaPQ
100 1 $a Daymude, Joshua J. $3 3564467
245 1 0 $a Collaborating in Motion: Distributed and Stochastic Algorithms for Emergent Behavior in Programmable Matter.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2021
300 $a 454 p.
500 $a Source: Dissertations Abstracts International, Volume: 82-11, Section: B.
500 $a Advisor: Richa, Andrea W.
502 $a Thesis (Ph.D.)--Arizona State University, 2021.
506 $a This item must not be sold to any third party vendors.
520 $a The world is filled with systems of entities that collaborate in motion, both natural and engineered. These cooperative distributed systems are capable of sophisticated emergent behavior arising from the comparatively simple interactions of their members. A model system for emergent collective behavior is programmable matter, a physical substance capable of autonomously changing its properties in response to user input or environmental stimuli. This dissertation studies distributed and stochastic algorithms that control the local behaviors of individual modules of programmable matter to induce complex collective behavior at the macroscale. It consists of four parts.In the first, the canonical amoebot model of programmable matter is proposed. A key goal of this model is to bring algorithmic theory closer to the physical realities of programmable matter hardware, especially with respect to concurrency and energy distribution. Two protocols are presented that together extend sequential, energy-agnostic algorithms to the more realistic concurrent, energy-constrained setting without sacrificing correctness, assuming the original algorithms satisfy certain conventions.In the second part, stateful distributed algorithms using amoebot memory and communication are presented for leader election, object coating, convex hull formation, and hexagon formation. The first three algorithms are proven to have linear runtimes when assuming a simplified sequential setting. The final algorithm for hexagon formation is instead proven to be correct under unfair asynchronous adversarial activation, the most general of all adversarial activation models.In the third part, distributed algorithms are combined with ideas from statistical physics and Markov chain design to replace algorithm reliance on memory and communication with biased random decisions, gaining inherent self-stabilizing and fault-tolerant properties. Using this stochastic approach, algorithms for compression, shortcut bridging, and separation are designed and analyzed.Finally, a two-pronged approach to "programming" physical ensembles is presented. This approach leverages the physics of local interactions to pair theoretical abstractions of self-organizing particle systems with experimental robot systems of active granular matter that intentionally lack digital computation and communication. By physically embodying the salient features of an algorithm in robot design, the algorithm's theoretical analysis can predict the robot ensemble's behavior. This approach is applied to phototaxing, aggregation, dispersion, and object transport.
590 $a School code: 0010.
650 4 $a Computer science. $3 523869
650 4 $a Robotics. $3 519753
650 4 $a Statistical physics. $3 536281
653 $a Distributed algorithms
653 $a Emergent behavior
653 $a Programmable matter
653 $a Randomized algorithms
653 $a Statistical physics
653 $a Swarm robotics
690 $a 0984
690 $a 0771
690 $a 0217
710 2 $a Arizona State University. $b Computer Science. $3 1676136
773 0 $t Dissertations Abstracts International $g 82-11B.
790 $a 0010
791 $a Ph.D.
792 $a 2021
793 $a English
856 4 0 $u https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28323007