An Evaluation of Decentralized Group Formation Techniques for Flying Light Specks Conference: USC FLS Lab; flslab.org; Private Copy Conference: ACM Multimedia Asia 2023; December 6–8, 2023; Tainan, Taiwan ACM Multimedia Asia 2023 (MMAsia ’23), December 6–8, 2023, Tainan, Taiwan DOI: 10.1145/3595916.3626460 ISBN: 979-8-4007-0205-1/23/12 Conference: Multimedia Asia 2023; Tainan, Taiwan; Dec 6-8

Hamed Alimohammadzadeh, Heather Culbertson, Shahram Ghandeharizadeh · 2026

Read An Evaluation of Decentralized Group Formation Techniques for Flying Light Specks Conference: USC FLS Lab; flslab.org; Private Copy Conference: ACM Multimedia Asia 2023; December 6–8, 2023; Tainan, Taiwan ACM Multimedia Asia 2023 (MMAsia ’23), December 6–8, 2023, Tainan, Taiwan DOI: 10.1145/3595916.3626460 ISBN: 979-8-4007-0205-1/23/12 Conference: Multimedia Asia 2023; Tainan, Taiwan; Dec 6-8 by Hamed Alimohammadzadeh, Heather Culbertson, Shahram Ghandeharizadeh (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26645.txt.

Introduction

Hamed Alimohammadzadeh, Heather Culbertson, and Shahram Ghandeharizadeh evaluate group formation for Flying Light Specks. A Flying Light Speck is a tiny drone carrying lights. Swarms of them can draw three-dimensional shapes in the air. Users can even touch the shapes for feedback through the skin. Groups of specks support backup when some fail and divide rendering work.

Four decentralised techniques are compared. Each speck decides on its own, messaging neighbours without a shared clock. Tests used synthetic point clouds, where the best grouping is known, plus real point clouds. A point cloud is a set of points outlining a shape. One technique, Random Subset, won for small groups of five or fewer. Another, Closest Available Neighbor First, won for groups of ten or more.

Catalog record

CREATORHamed Alimohammadzadeh, Heather Culbertson, Shahram Ghandeharizadeh
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.26645

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Evaluation of Decentralized Group Formation Techniques for Flying Light Specks Conference: USC FLS Lab; flslab.org; Private Copy Conference: ACM Multimedia Asia 2023; December 6–8, 2023; Tainan, Taiwan ACM Multimedia Asia 2023 (MMAsia ’23), December 6–8, 2023, Tainan, Taiwan DOI: 10.1145/3595916.3626460 ISBN: 979-8-4007-0205-1/23/12 Conference: Multimedia Asia 2023; Tainan, Taiwan; Dec 6-8 Hamed Alimohammadzadeh, Heather Culbertson, Shahram Ghandeharizadeh Abstract . Group formation is fundamental for 3D displays that use Flying Light Specks, FLSs, to illuminate shapes and provide haptic interactions. An FLS is a drone with light sources that illuminates a shape. Groups of G G FLSs may implement reliability techniques to tolerate FLS failures, provide kinesthetic haptic feedback in response to a user’s touch, and facilitate a divide and conquer approach to challenges such as localizing FLSs to render a shape. This paper evaluates four decentralized techniques to form groups. An FLS implements a technique autonomously using asynchronous communication and without a global clock. We evaluate these techniques using synthetic point clouds with known optimal solutions and real point clouds. Obtained results show a technique named Random Subset (RS) is superior when constructing small groups (G ≤ \leq 5) while a different technique named Closest Available Neighbor First (CANF) is superior when constructing large groups (G ≥ \geq 10). 1. Introduction Figure 1 . Four different point clouds. A Flying Light Speck (FLS) is a miniature sized drone configured with light sources, processing, storage, and networking capabilities. Swarms of cooperating FLSs will illuminate complex 2D and 3D shapes in a fixed volume, an FLS display ( 12 ; 13 ; 1 ) . They will provide a user with encounter-type haptic interactions ( 21 ) by detecting their disposition due to the user’s exerted force (e.g., poking). In response, they provide the appropriate behavior (e.g., the shape moves away), and exert force back if necessary (e.g., emulate surface friction or hardness). Applications of an FLS display are diverse ranging from entertainment to health care. With entertainment, an FLS display will illuminate characters of a multi player game such as Minecraft and Street Fighter, enabling a user to experience them from different angles. With health care, a physician can examine a patient’s MRI scans in real time by separating and analyzing the different organs (illuminations). The physician will be able to evaluate the softness of tissue emulated by FLSs using the density readings of a scan. An illumination is a rendering of a point cloud with an FLS assigned the coordinates of a point in the point cloud. The illumination may require a large number (thousands if not millions) of FLSs. Group formation is important to develop effective divide and conquer techniques for FLS displays. Its objective is to minimize the distance between the FLSs that constitute each group. A solution to this problem may either be centralized or decentralized. This paper implements and evaluates several known decentralized group formation techniques ( 5 ) . We focus on decentralized techniques because they enable FLSs to synergize in an online manner. Below, we describe three use cases of such an algorithm. With each, the time to identify groups should be minimized. Three use cases of a decentralized group formation technique: With a haptic interaction such as poking, groups of FLSs may exert force at different parts of a fingertip. To illustrate, consider a physician manipulating an organ (illumination). The location of physician’s fingertip will be detected by one or more FLSs. The required stiffness dictates a value for F and G . Ideally, F FLSs in the form of nG groups (each with G FLSs) will exert force back, enabling the physician to experience the stiffness of the tissue. A decentralized technique that constructs these groups using the closest number of FLSs will enable formation of nG groups quickly. Second, with FLS failure handling, one may construct nG reliability groups. Each consists of G+C FLSs. G FLSs illuminate a point cloud. C FLSs are dark standbys ( 13 ) . This is similar to RAID ( 23 ) for mass storage devices. Every time an FLS fails, an available standby substitutes for its lighting responsibility at its assigned coordinate. The G FLSs must be in close proximity to one another, enabling a standby to quickly substitute for a failed FLS. This highlights the importance of minimizing distance between the FLSs in a group. Finally, relative localization will enable a group of FLSs to position themselves to illuminate a 2D or 3D multimedia shape. The relative distance and angle between the FLSs will match those of the points in a point cloud. There are a many techniques using different kinds of sensors such as UWB, IMU, optical, and their hybrids. To illuminate a large point cloud, one may partition it into groups, each with G FLSs. The G FLSs in each group may localize independent of the FLSs in the other groups. Subsequently, the different groups may localize relative to one another. By reducing the distance between G FLSs in a group, the likelihood of FLSs in different groups blocking one another is minimized. We evaluate the group formation techniques along three dimensions: 1) Speed, how fast a technique computes groups, 2) Quality of formed groups, the number of groups and the average distance between the FLSs in a group, and 3) Amount of work performed. We quantify the first using the response time of a technique. It is defined from the time a swarm of FLSs starts to execute a technique until they converge on a solution. With the quality of formed groups, we focus on the number of constructed groups consisting of G FLSs. We do not consider smaller group sizes as usable, deferring an investigation of this topic to future work, see Section 7 . The work performed by a group is quantified using the network bandwidth consumed by an FLS and its CPU processing. The latter is quantified by computing the average number of times an FLS executes a technique to converge on a solution. The techniques require an FLS to consume network bandwidth in a bursty manner. Moreover, while they may require a similar transmission rate from an FLS, the rate at which they require an FLS to receive data may be different. Hence, we report the average transmission rate (Xmt BW) and receive rate (Rec BW) separately. An ideal technique must provide a response time that meets the requirements of its target application, maximize the number of groups consisting of a pre-specified G value, minimize the distance between the FLSs that constitute a group, and minimize the amount of network bandwidth and processing demanded from the individual FLSs. The contributions of this paper include: • A scalable technique to construct synthetic point clouds with known optimal grouping of FLSs and G values. It is used as a yardstick for the metrics of interest. (Section 2 ) • An implementation and evaluation of several known decentralized group formation heuristics: Random Subset (RS) ( 4 ; 5 ) , and Variable Neighborhood Search (VNS) ( 3 ) . (Section 3 .) • Two new decentralized heuristic, Simple Random, SimpleR, and Closest Available Neighbor First, CANF. (Sections 3.1.1 and 3.1.4 .) • A discovery protocol to enable an FLS to

Read the complete text