Pattern formations with discrete waves and broadcasting sequences


Nickson, Thomas Pattern formations with discrete waves and broadcasting sequences. Doctor of Philosophy thesis, University of Liverpool.

[img] PDF
Thesis.pdf - Submitted version
Access to this file is embargoed until Unspecified.
Available under License Creative Commons Attribution No Derivatives.
Download (1MB)
[img] PDF
NicksonTho_Feb2013_9817.pdf - Author Accepted Manuscript
Available under License Creative Commons Attribution No Derivatives.
Download (1MB)

Abstract

This thesis defines the Broadcasting Automata model as an intuitive and complete method of distributed pattern formation, partitioning and distributed geometric computation. The system is examined within the context of Swarm Robotics whereby large numbers of minimally complex robots may be deployed in a variety of circumstances and settings with goals as diverse as from toxic spill containment to geological survey. Accomplishing these tasks with such simplistic machines is complex and has been deconstructed in to sub-problems considered to be signif- icant because, when composed, they are able to solve much more complex tasks. Sub-problems have been identified, and studied as pattern formation, leader elec- tion, aggregation, chain formation, hole avoidance, foraging, path formation, etc. The Broadcasting Automata draws inspiration from a variety of sources such as Ad-Hoc radio networks, cellular automata, neighbourhood sequences and nature, employing many of the same pattern forming methods that can be seen in the superposition of waves and resonance. To this end the thesis gives an in depth analysis of the primitive tools of the Broadcasting Automata model, nodal patterns, where waves from a variety of transmitters can in linear time construct partitions and patterns with results per- taining to the numbers of different patterns and partitions, along with the number of those that differ, are given. Using these primitives of the model a variety of algorithms are given including leader election, through the location of the centre of a discrete disc, and a solution to the Firing Squad Synchronisation problem. These problems are solved linearly.An exploration of the ability to vary the broadcasting radius of each node leads to results of categorisations of digital discs, their form, composition, encodings and generation. Results pertaining to the nodal patterns generated by arbitrary transmission radii on the plane are explored with a connection to broadcasting sequences and approximation of discrete metrics of which results are given for the approximation of astroids, a previously unachievable concave metric, through a novel application of the aggregation of waves via a number of explored functions. Broadcasting Automata aims to place itself as a robust and complete linear time and large scale system for the construction of patterns, partitions and geometric computation. Algorithms and methodologies are given for the solution of problems within Swarm Robotics and an extension to neighbourhood sequences. It is also hoped that it opens up a new area of research that can expand many older and more mature works.

Item Type: Thesis (Doctor of Philosophy)
Additional Information: Date: 2013-02 (completed)
Subjects: ?? QA75 ??
Divisions: Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User: Symplectic Admin
Date Deposited: 28 Aug 2013 15:49
Last Modified: 16 Dec 2022 04:38
DOI: 10.17638/00009817
Supervisors:
URI: https://livrepository.liverpool.ac.uk/id/eprint/9817
Dimensions
Altmetric
CORE (COnnecting REpositories)