Introduction

A Flying Light Speck, FLS, is a miniature sized drone equipped with one or more light sources to generate di"erent colors and textures with adjustable brightness. It is battery powered, network enabled, has processing capability to implement decentralized algorithms, and some storage. It uses the latter to store data pertaining to its lighting responsibility at certain coordinates as a function of time. Synchronized swarms of FLSs will illuminate virtual objects in a pre-speci!ed 3D volume, an FLS display [15,16]. An FLS display may be a cuboid that sits on a table or hangs on a wall, the dashboard of a self-driving vehicle, a room, etc. It will render (a) static 2D or 3D point clouds, (b) slide shows consisting of a sequence of 2D or 3D point clouds, and (c) motion illuminations consisting of a sequence of 2D or 3D point clouds with temporal constraints. Motion illuminations may render a !xed number of point clouds as a function of time, e.g., 24 point clouds per second.

An FLS display may be used by diverse applications ranging from entertainment to healthcare [33], education, and scienti!c devices (e.g., deep space telescopes) that produce 3D data, among others. With healthcare, an FLS display may illuminate 3D MRI scans of a patient and their organs, empowering a physician to separate the di"erent organs (illuminations) and examine them in real time. With entertainment, an FLS display may illuminate characters of multi-player games such as Minecraft and Fortnite to come alive and interact with one another on a tabletop. Visualization of 3D scienti!c data is a signi!cant challenge. An immersive FLS display [18] addresses the challenge by enabling a user to analyze the data from di"erent perspectives including stepping into the data, e.g., examining the 3D voxels of a hippocampus in an MRI scan.

An FLS is a mechanical device that fails [15,16]. It may encounter di"erent kinds of failures ranging from propeller damage [22] and rotor loss [20] that prevent it from #ying to hardware and software failures that prevent it from communicating and coordinating with other FLSs. An FLS that must leave its swarm to charge its battery may also be considered a form of failure. To (a) 95 𝐿𝑀 Percentile. (b) 99 𝐿𝑀 Percentile. elaborate, STAG [16] is an algorithm that constructs #ocks with staggered #ight times, allowing an FLS 𝑁 𝑁 with an almost depleted battery to leave its #ock to charge its battery while a new FLS 𝑁 𝑂 with a fully charged battery is deployed to substitute for it [34,35]. If 𝑁 𝑂 arrives either prior to or at approximately the same time as 𝑁 𝑁 's departure then they may switch places gracefully. Otherwise, 𝑁 𝑁 's absence may be considered as a form of failure that degrades the quality of an illumination.

An FLS failure causes a point in an illumination of a point cloud to go dark. Our objective is to minimize the duration of time for a replacement FLS to illuminate this dark point, i.e., the Mean Time to Illuminate a Dark point, MTID. One approach is for the display to deploy a replacement FLS. In this case, MTID is dictated by the distance from the display's dispatcher to the dark point, the speed of the FLS, and how fast it may localize [4][5][6]. An alternative is to deploy dark standby FLSs [16] in anticipation of a failure. These standbys are positioned in close proximity of an illuminating FLS. When an illuminating FLS fails, the standby FLS occupies its coordinates and resumes its lighting responsibility. By minimizing the standby's traveled distance, the MTID is improved.

We construct reliability groups, each with 𝑂 illuminating FLSs and 𝑃 standby FLSs [16]. The standbys are placed close to the center of the group. By minimizing the distance between the illuminating FLSs that constitute a group, the distance (time) traveled by a standby FLS to resume the lighting responsibility of a failed illuminating FLS is reduced. This enhances MTID as long as the display may deploy FLSs at a faster rate than the failure rate of FLSs.

Figure 2 shows thefoot_0 95th and the 99th percentile of the skateboard's MTID as a function of time with no reliability groups, and reliability groups of 𝑂=3 and 𝑂=20. With 𝑂=3 (20), the number of dark standby FLSs is approximately 30% (5%) of the number of points in a point cloud. This is the

(a) Dragon. (b) Skateboard. overhead of using reliability groups. The bene!t of the reliability groups is the signi!cant reduction in MTID, see Figure 2.

A standby is dark and may obstruct the user's Field of View, FoV. Figure 3 shows the illuminating and standby FLSs for the user's FoV from the bottom of the Dragon and the Skateboard. It shows the obstructing FLSs with 𝑂=3 and 𝑂=20. Obstructing dark standbys diminish the quality of an illumination. There are several possible approaches: Prevention, detection, and a hybrid. Prevention ensures standby FLSs are never in the user's !eld of view. Detection requires a standby to predict that it will obstruct the user's FoV and either illuminate the colors of its obstructing FLS or move behind it to prevent a degraded quality of illumination. Prevention may be possible for some standby FLSs but not all, motivating a hybrid technique.

The contributions of this paper include several detection techniques that require an obstructing FLS to change its location to conceal itself from the user's FoV. These include Transpose, Dissolve, and three variants of Suspend (Hangar, Closest, and Obstructing). An evaluation of these techniques highlights the following tradeo". While Suspend:Closest provides a superior MTID by maximizing the utilization of standby FLSs, Transpose minimizes the distance traveled by standby FLSs to conceal themselves. We open source our software implementations of these techniques and the 3D data used in this study for further use and investigation by the scienti!c community. See

Table 1. Notations and their definitions.

Notation De!nition 𝑄 Ratio of illumination cell to display cell. 𝑅 Total number of dispatchers. 𝑁 Total number of FLSs required by a point cloud. 𝑂 Number of FLSs per reliability group. 𝑃 Number of standby FLSs per reliability group. 𝑆 𝑃 Number of groups 𝑆 𝑃 = → 𝑄 𝑃 ↑. MTID Mean time to illuminate a dark point due to FLS failure. MTTF Average amount of time an FLS operates before it fails. 𝐿 Maximum lifetime of an FLS. 𝑀 Maximum rate of FLS deployment. 𝑇 Maximum rate of FLS failures, 𝑇 = 𝑄 𝑅 . https://github.com/#yinglightspeck/StandbyFLSs for details. This repository provides instructions on how to reproduce the experimental results reported in this paper.

Table 1 shows the notations used in this paper and their de!nitions. The rest of this paper is organized as follows. Section 2 provides related work. Section 3 presents an overview of a system and the terminology used in this paper. Section 4 describes a centralized and a decentralized technique to construct reliability groups. Section 5 describes the role of dispatchers in recovering from failures. Brief conclusions and future research directions are presented in Section 7.

Related Work

The concept of FLSs and FLS displays is presented in [2, 3, 7, 8, 11-13, 15-17, 26, 34, 35]. The idea of forming reliability groups and using standby FLS is introduced in [16]. It presents analytical models to demonstrate the bene!ts of using standby FLSs. However, it does not describe techniques to form reliability groups. In [8], we formally introduce and quantify the Quality of Illumination (QoI) and the duration of time a point is dark (MTID). This study introduces a centralized and a decentralized technique to form groups and quanti!es their tradeo"s. It introduces Dissolve and Suspend:Closest to change the location of standbys that obstruct the user's FoV. We extend [8] with three additional techniques, Transpose, Suspend:Hangar, and Suspend:Obstructed. In addition, we evaluate and compare these techniques. Obtained results show the superiority of Suspend:Closest in minimizing MTID. Transpose minimizes the distance traveled by standby FLSs to conceal themselves.

The concept of reliability groups and standbys dates back to arrays of memory modules and disks [19,28]. With disk subsystems such as RAID [25], the hardware infrastructure dictates the characteristics of the reliability groups. FLS displays are unique in that the data, represented as a point cloud, determines the characteristics of the reliability groups. The distance between the points that constitute a reliability group is important, as it dictates both MTID and QoI. Another di"erence is that an FLS display may use reliability groups selectivity to enhance MTID. As detailed in Section 5, a simple priority queue enables an FLS display to not deploy standby FLSs, disabling the concept of a reliability group when it is not bene!cial. Hardware and software RAIDs do not require this #exibility.

Terminology and Problem Statement

The concept of a display cell and an illumination cell are fundamental to this study. To render an illumination, an FLS display constructs a 3D mesh on the display volume. A cell of this mesh, a display cell [16], is dictated by the downwash of an FLS [9,10,14,27,32]. Assuming an FLS is a quadrotor, a cell may be an ellipsoid [9,10,27] or a cylinders [14,32] that results in a larger separation along the height dimension. Each display cell has a unique Length, Height, and Depth (L,H,D) coordinate [16]. We use the L, H, D coordinate system instead of X, Y, Z to identify a cell because there is no consensus on one de!nition of the Y and Z axes. While the picture industry uses the Z axis as the depth, mathematicians use the Y axis for the depth. It is trivial to map our L, H, D coordinate system to either de!nition without ambiguity.

The light emitted from an FLS !lls an illumination cell. We assume an illumination cell is either the same size or larger than a display cell, see Figure 4. Without loss of generality and to simplify the discussion, we assume a display cell and an illumination cell are cubes. We denote the ratio of an illumination cell to a display cell along a dimension as Q. Assuming the same Q value across L, H, and D, the number of display cells contained in an illumination cell is Q 3 . A maximum of Q 3 FLSs may occupy di"erent cells of an illumination cell with one FLS illuminating the cell. We assume the remaining Q 3 -1 FLSs remains invisible. This assumption is reasonable because these FLSs may render the same light and color as the illuminating FLS with lower intensity depending on the location of their occupied display cell.

An increase in the value of Q may be interpreted in two di"erent ways. One interpretation is that the display is increasing in size and the light source of each FLS is bright enough to illuminate an increasing number of display cells. For example, with Q=10, an FLS must illuminate 1000 display cells and the display is 10x larger along a dimension when compared with Q=1. The second interpretation is that the volume of downwash by an FLS has shrunk, enabling the display to hide a larger number of FLSs in an illumination cell. In this paper, we assume the !rst interpretation of Q. It is trivial to convert the results of this paper in the context of the second interpretationfoot_2 .

De!nition 1. Quality of an Illumination, QoI, for a point cloud is the percentage of its points illuminated by FLSs at an instance in time.

The best theoretical QoI value is 100%. The QoI of a rendering may be lower than 100% due to failure of the illuminating FLSs. The tolerable QoI is application dependent.

Mean Time To Failure [16,25,28], MTTF, quanti!es the average amount of time an FLS operates before it fails. A higher MTTF is desirable because it re#ects a longer FLS lifespan. We construct reliability groups consisting of 𝑂 illuminating FLSs and 𝑃 standby FLSs. A standby is a dark FLS assigned to a group of 𝑂 illuminating FLSs. The distance between the 𝑂 FLSs should be minimized to enable the standby to substitute for a failed FLS as fast as possible, minimizing the MTID.

De!nition 2. Mean Time to Illuminate a Dark point, MTID, is the average elapsed time from when a point of a point cloud goes dark due to the failure of its illuminating FLS and back to being illuminated by a replacement FLS.

De!nition 3. A group centroid is the coordinate that identi!es the center of a reliability group consisting of 𝑂 FLSs. It is computed using the coordinates of its 𝑂 FLSs: [

where [𝑈 𝑆 , 𝑉 𝑆 , 𝑅 𝑆 ] is the coordinate of the 𝑊 𝐿𝑀 FLS in the group. The Orchestrator assigns a standby to the group centroid as long as it is not occupied by an illuminating FLS, i.e., the coordinates of a point in a point cloud.

P!"#$%& D%'()(*(") 1. Minimize the MTID of an illumination given reliability groups with 𝑂 illuminating FLSs and 𝑃 standby FLSs without obstructing the user's FoV.

(a) Simple architecture [16].

(b) Dronevision [2].

Fig. 5. Two alternative architectures: (a) the yellow cylinders of the simple architecture [16] are dispatchers that deploy FLSs, (b) the Dronevision architecture [2] uses elevated pads that act as dispatchers to deploy FLSs. A dispatcher deploys FLSs at a rate 𝑀 and a display consists of 𝑅 dispatchers. With both architectures, failed FLSs fall on a conveyor belt that deposits them in a Terminus.

We assume the architectures of [2,16] consisting of a hub and one or more dispatchers to deploy FLSs. See Figure 5. The hub is comparable to today's server. It hosts an Orchestrator process that communicates with FLSs using wireless communication, detects failures, and coordinates the dispatchers to deploy FLSs. A dispatcher may be in the form of a cylinder on the sides of a display [16] or black tiles at the bottom of a display [2]. The rate at which an architecture deploys FLSs impacts the solution to the problem.

Failure types and recovery

We assume FLS failures are either mechanical, lighting related, or both. These prevent an FLS from either #ying, rendering its illumination responsibilities, or both. In addition, we assume an FLS may detect these failures and use its wireless communication interface to notify its neighboring FLSs and the Orchestrator of its failure. We defer the failure of electronics that prevent an FLS from communicating to future work.

When an illuminating FLS fails, its assigned point (coordinate) goes dark. The display may illuminate this point by either requiring a dispatcher to deploy a new FLS to the coordinates of the dark point or use a nearby standby to #y to the coordinates of the dark point (failed FLS) to resume its lighting responsibilities. The latter minimizes MTID, motivating 𝑆𝑂 reliability groups with 𝑃 standby FLSs per group.

With reliability groups, we assume an illuminating and a standby FLS are identical with the same MTTF. A reliability group may be in either the normal or a degraded mode of operation. In the normal mode, the group consists of 𝑂 illuminating FLSs and 𝑃 standbys. In degraded mode, either one or more illuminating FLSs have failed, one or more standby FLSs have failed or are missing (because they substituted for a failed illuminating FLS), or a combination of these possibilities.

When an illuminating FLS fails, it noti!es its group members and the Orchestrator of its failure. Its message identi!es the group that experienced the failure, 𝑂 𝑂 . If 𝑂 𝑂 has an idle standby FLS, this FLS changes its status to illuminating and #ies to the coordinate of the failed FLS to assume its lighting responsibility. The Orchestrator dispatches a new standby to 𝑂 𝑂 . The coordinates of this standby is 𝑂 𝑂 's centroid.

When a standby FLS fails, it noti!es the 𝑂 illuminating FLSs, the 𝑃 ↓ 1 standbys in its group, and the Orchestrator of its failure. The illuminating FLSs maintain the absence of a standby and switch to the degraded mode of operation. The Orchestrator dispatches a new FLS to the coordinates identi!ed by the group centroid as the replacement standby. In case the replacement standby (a) QoI, higher is be!er.

(b) MTID, lower is be!er. (c) "euing Delay, lower is be!er. fails mid-#ight, it noti!es the Orchestrator to deploy a new replacement FLS. Once a replacement standby is dispatched, it noti!es the illuminating FLSs in its group of presence. The illuminating FLSs record the presence of the standby and switch to normal mode of operation.

If 𝑂 𝑂 has no standby FLS and one of its illuminating FLSs fails, either the Orchestrator or the failed FLS may notify a mid-#ight replacement standby for the group to change its destination to the coordinates of the failed illuminating FLS and resume its lighting responsibility. Next, the Orchestrator deploys a new standby for 𝑂 𝑂 . The coordinates of this standby is 𝑂 𝑂 's group centroid.

The number of dispatchers and the rate at which they deploy FLSs are important considerations. With fully utilized dispatchers, standby FLSs may degrade both QoI and MTID. This is because standby FLSs fail in the same manner as illuminating FLSs. Deployment of standby FLSs taxes the dispatchers and prevents them from deploying FLSs to illuminate points that improve QoI/MTID. Below, we formalize these concepts and highlight their interrelationships.

Failure Model

We assume a simple failure model where FLSs fail independently of each other. This model selects a time to live (TTL) between 1 second and a !xed constant 𝐿. The life time of an FLS may not exceed 𝐿, TTL ↔ 𝐿. Once this TTL expires, an FLS fails.

The distribution used to pick a TTL has an impact on QoI. We considered a uniform (RandTTL) and a Beta (BetaTTL) distribution. With RandTTL, an FLS selects a random value between 1 and 𝐿 and approximates a mean of the distribution close to 𝑅+1 2 . BetaTTL selects a random value between 1 and 𝐿 conditioned based on a distribution mean close to 𝑇 ↗𝑈𝑈 𝑉 𝑇+𝑊 . The values of 𝑋 and 𝑌 model di"erent degrees of skew. In our study, we used 𝑋=10 and 𝑌=0.8. The mean of this distribution is 𝑇 𝑇+𝑊 , approximately 92% of 𝐿. It models an FLS that fails with a higher probability as its operation time approximates the end of its life, 𝐿.

The Mean Time To Failure (MTTF) of an FLS approximates the mean of the distribution and is bounded by 𝐿, 𝑍𝑎𝑎 𝑁 ↔ 𝐿. A failed FLS is recovered using the discussion of Section 3.1. The QoI is superior with BetaTTL when compared with RandTTL. See Figure 6a. This is because the MTID is shorter with the BetaTTL, see Figure 6b. When the dispatch rate is approximately the same as the rate of failure, the MTID of BetaTTL is superior because of a lower queuing delay at the dispatcher; see Figure 6c. BetaTTL causes the failure of FLSs to get staggered in time after their !rst failure. RandTTL is not able to do the same because FLSs fail randomly. With RandTTL, a large number of FLSs may fail concurrently, resulting in a longer delay in the dispatcher queue. This is re#ected by the number of failures as a function of time with a higher maximum for RandTTL, see Figure 7a. When the dispatch rate exceeds the failure rate, the staggering of failures with BetaTTL is visible, see Figure 7b. These results were obtained from the implementation described in Appendix A.

(a) FLS dispatch rate is lower than failure rate.

(b) FLS dispatch rate is higher than failure rate. 4 Group Construction P!"#$%& D%'()(*(") 2. Given a point cloud with 𝑁 points (coordinates) with each point assigned to a di"erent FLS and a required group size 𝑂, maximize the number of groups consisting of approximately 𝑂 FLSs such that (1) an FLS participates in exclusively one group and all FLSs agree on participation in the same group, and (2) the Euclidean distance between the group members is minimized.

In this paper, the symmetry constraint that all 𝑂 FLSs in a group agree to be a member of the same group is fundamental. In [8], we describe a popular centralized group formation technique named 𝑏-means [21] and a decentralized technique named Closest Available Neighbor First, CANF [3] to form groups. With both, the number of groups 𝑆𝑂 is bounded by ↘ 𝑄 𝑃 ≃. At the same time, the two techniques are fundamentally di"erent. While 𝑏-means constructs 𝑆𝑂 groups consisting of a variable number of illuminating FLSs, CANF constructs 𝑆𝑂 groups each with 𝑂 FLSs 3 .

A key advantage of CANF is that it is decentralized, enabling FLSs to compute their groups dynamically. A quantitative analysis reported in [8] shows k-means is superior to CANF along several dimensions. First, it constructs groups orders of magnitude faster than CANF. Second, it enhances the overall quality of illuminations by minimizing MTID. It realizes this by minimizing the distance between the FLSs that constitute a group.

k-means enhances MTID by constructing 𝑆𝑂 groups without requiring all groups to have the same size 𝑂. For example, with the Dragon and 𝑂=20, it constructs groups as small as 6 FLSs and as large as 40 FLSs. Most groups consist of 15 FLSs, 𝑂=15. This #exibility enables k-means to construct groups with both sparse (Dragon, see Figure 1a) and dense (Skateboard) point clouds e"ectively such that the FLSs that constitute a group are in close proximity of one another. In turn, a standby FLS substitutes for a failed illuminating FLS quickly to enhance QoI.

CANF execution time is orders of magnitude slower than k-means because of its message passing between FLSs. In our implementation, FLSs communicate using the UDP protocol. k-means does not have this overhead.

k-means becomes slower with large point clouds. The same is not true with CANF. The topology of the point cloud dictates its speed. For example, CANF constructs groups faster with the Skateboard when compared with the Dragon (13x) and the Chess piece (2.5x) with 𝑂=5 even though it has more than 2x and 3x points than each, respectively.

QoI of k-means and CANF is the same when the dispatcher is the bottleneck. In this case, the standby FLSs do not provide a bene!t (see Section 5 for details), and the distance from the dispatcher to the individual illuminating FLSs (i.e., points of a point cloud) dictates the MTID. This distance is

Techniques to Conceal Dark Standby Flying Light Specks 1:9

approximately the same with both k-means and CANF. Hence, their identical QoI. For example, with a dispatch rate of 30 FLSs per second with an MTTF of 30 seconds, the QoI of the Skateboard is approximately 50% with both CANF and k-means. Their MTID is 28.82 Seconds.

When the dispatcher is not the bottleneck, k-means is superior to CANF as it results in a lower MTID 4 with all group sizes and shapes. With all shapes, k-means minimizes the distance between the centroid of a group and each FLS that constitutes the group.

QoI is also impacted by the time for the dispatcher to deploy an FLS to replace a failed standby. During this time, a second illuminating FLS may fail. In this case, there is no standby and the replacement FLS must arrive from the dispatcher. In our experiments with the skateboard, the average distance from a dispatcher to a group is approximately 57 display cells with both k-means and CANF. Hence, its impact is negligible. We observe similar results with other shapes.

We refer the interested reader to [8] for the details of k-means, CANF and its pseudo-code, and a comparison of these two techniques for constructing reliability groups.

Dispatchers

The rate at which dispatchers deploy FLSs (𝑀) relative to the failure rate of FLSs (𝑇 ) dictates the QoI improvements observed with reliability groups. When 𝑀 ↔ 𝑇 , reliability groups may degrade QoI as they require the dispatcher to deploy replacement FLSs for the failed standbys. QoI is enhanced when dispatchers deploy replacements for a failed illuminating FLS.

To illustrate, consider an architecture with 1 dispatcher and 𝑀=35 FLSs/Second. With no reliability groups, its QoI is 57.24% and MTID is 21 Seconds. With 𝑂=3, QoI is reduced to 49.10% and the MTID increases to 30 Seconds. The replacements for the failed standby FLSs are 33% of the FLSs deployed by the dispatcher. They prevent the dispatcher from deploying replacement FLSs for the illuminating FLSs, resulting in a lower QoI.

We address this limitation using priority queues. We assign a higher priority to replacement FLSs that illuminate a point, moving them to the head of the queue. The replacement standby FLSs may be logical in a data structure maintained by the Orchestrator instead of physical FLSs in a queue. In our example, the use of priority queues enhances QoI to 57.67% and reduces MTID to 21.3 Seconds. These numbers are comparable to those with no reliability groups. For the remainder of this paper, we assume dispatchers use priority queues.

Multiple Dispatchers

One may use 𝑅 dispatchers to increase the overall rate of FLS deployment to 𝑅↗𝑀. A challenge is how the Orchestrator should select a dispatcher to deploy an FLS. We considered four policies: Random, Round-Robin (RR), Power-of-2 [23], and Shortest Distance (SD). With Random, the Orchestrator selects a dispatcher randomly. With RR, the Orchestrator uses a simple mod function by maintaining a monotonically increasing counter 𝑃. It selects the dispatcher with id (𝑃 𝑐𝑑𝑒 𝑅) and increments 𝑃 by one. With Power-of-2 [23], the Orchestrator samples the queue of two randomly chosen dispatchers and selects the one with the shortest queue. With SD, the Hub computes the distance from a dispatcher to the coordinates of the FLS to be deployed, selecting the one with the shortest distance. It is possible to combine two or more techniques. For example, a hybrid may require the Hub to select a dispatcher closest to an FLS's coordinates and, if it has a queue then, use power-of-2 to select a dispatcher.

We evaluated these policies with alternative shapes. The obtained results show the following lessons. When 𝑀 ↔ 𝑇 , SD is inferior to the other techniques. It may result in the formation of a queue at a dispatcher while other dispatchers sit idle waiting for work. When 𝑀 > 𝑇 and with no reliability group, the example hybrid technique provides a slightly better QoI (⇐ 1%), MTID (⇐ 1%), and a lower traveled distance (1 to 2 display cells) when compared with the other techniques. When 𝑀 > 𝑇 and with reliability groups, except for SD, other techniques provide comparable QoI and MTID. In most experiments, RR is slightly superior. In all experiments, SD provided a signi!cantly lower QoI and MTID.

Below, we present results from the Skateboard and the Dragon to highlight the above lessons. We assume an architecture with 𝑅=3 dispatchers. Each dispatcher may deploy 𝑀=10 FLSs/Sec and FLS speed is 6.11 Meters/Second. With the Dragon, the failure rate is 12 FLSs/Sec and there are no reliability groups. In this experiment, the hybrid technique provides the best QoI (95.39%) and MTID (1.46). SD provides the worst QoI (41.84%) and MTID (37.96). SD is inferior because it results in formation of a queue for one dispatcher. This dispatcher is closest to the coordinates assigned to a high number of concurrently dispatched FLSs. The queuing delay increases MTID and reduces QoI. In this experiment, the average queuing delay for SD is 36.79 seconds, while other techniques have an average delay of approximately 0.3 seconds.

With both the Dragon and the Skateboard and no reliability groups, the hybrid of SD with power-of-2 provided a slightly better QoI and MTID. For example, with the Skateboard, the hybrid provided a QoI (MTID) of 97.64% (1.30) versus power-of-2 with a QoI (MTID) of 95.37% (1.33). In addition, its average traveled distance was lower, 32.69 with hybrid versus 34.45 with power-of-2. This di"erence does not exist with the use of reliability groups.

Obstructing FLS

A dark standby may obstruct the user's Field of View, FoV, see Figure 10.a. The number of obstructing FLSs is impacted by 𝑄, i.e., the ratio of an illumination cell to a display cell. (See discussions of Figure 4 in Section 3.) Figure 9 shows the number of obstructing FLSs with G=3 and G=20 for di"erent Q values for the top view of the Skateboard. A higher 𝑄 value increases the likelihood of a dark standby being placed in an illumination cell, preventing it from obstructing. Figure 11 highlights the obstructing FLSs with a red square for the di"erent shapes from their right side with

(a) Dragon, G=3, 19 Obstructing FLSs. (b) Hat, G=3, 62 Obstructing FLSs. (c) Skateboard, G=3, 17 Obstructing FLSs. (d) Dragon, G=20, 3 Obstructing FLSs. (e) Hat, G=20, 17 Obstructing FLSs. (f) Skateboard, G=20, 7 Obstructing FLSs. 𝑄=10. The number of obstructing FLSs is higher with 𝑂=3 when compared with 𝑂=20 because it has approximately 7x more standby FLSs.

An FLS display may track the human gaze using cameras [1,31], computing the coordinates of the user's gaze 𝑓 . Ray tracing [30] computes a vector 𝑔 from 𝑓 to an illuminating FLS 𝑆 , see Figure 10.a. A dark standby that intersects 𝑔 and falls in-between 𝑓 and 𝑆 is an obstructing FLS as long as it is not in a display cell of an illumination cell.

The Orchestrator may monitor the user's movement to compute a set of future locations {𝑓 𝑂 } relative to their current coordinate 𝑓 . It may use di"erent approaches to prevent the standby FLSs from obstructing. First, the Orchestrator may dissolve the reliability group of an obstructing standby and require the standby to #y to a hangar for permanent storage. Second, the Orchestrator may suspend the reliability group of an obstructing FLS and reactivate it once the user moves such that the standby is no longer obstructing. Third, the obstructing standby may prepare to illuminate the light and color of the illuminating FLS that it is obstructing. We defer the third approach to future work as the lighting details of an FLS is our in-progress work at the time of this writing.

The !rst two approaches increase MTID. Below, we describe three techniques: Transpose, Dissolve, and Suspend. All use Algorithm 1 to detect an obstructing FLS. While Dissolve implements the !rst approach, Transpose implements the second approach. We present Transpose in Section 6.1. Subsequently, we present Dissolve in Section 6.2. With small displays, 𝑄=1, obtained results motivate Dissolve (the !rst approach), dissolving reliability groups permanently. Suspend is an improvement on Transpose and Dissolve with 𝑄 ⇒ 2. It is similar to Transpose with one key di"erence: An obstructing standby moves to a vacant display cell of the closest illuminating FLS. This is one of the reliability groups known to the standby. We compare Transpose, Dissolve, and Suspend in Section 6.4. Obtained results show the superiority of Suspend with 𝑄 ⇒ 2. Transpose is superior to Dissolve with small displays 𝑄=1. 1: RayBoxIntersection (𝑖, 𝑅, 𝑗 𝑋𝑆𝑌 , 𝑗 𝑋𝑍𝑎 ) 1 𝑘 min ⇑ ↓⇓ 2 𝑘 max ⇑ +⇓ 3 for 𝑊 ⇔ {𝑙, 𝑚, 𝑛} do 4 if 𝑅 𝑆 ω 0 then 5 𝑘 entry 𝑁 ⇑ (𝑗 min 𝑁 ↓ 𝑖 𝑆 )/𝑅 𝑆 6 𝑘 exit 𝑁 ⇑ (𝑗 max 𝑁 ↓ 𝑖 𝑆 )/𝑅 𝑆 7 if 𝑘 entry 𝑁 > 𝑘 exit 𝑁 then 8 swap(𝑘 entry 𝑁 , 𝑘 exit 𝑁 ) 9 end 10 𝑘 min ⇑ max(𝑘 min , 𝑘 entry 𝑁 ) 11 𝑘 max ⇑ min(𝑘 max , 𝑘 exit 𝑁 ) 12 end 13 else if 𝑖 𝑆 < 𝑗 min 𝑁 or 𝑖 𝑆 > 𝑗 max 𝑁 then 14 return false 15 end 16 end 17 if 𝑘 min > 𝑘 max or 𝑘 max < 0 then 18 return false 19 end 20 return true

Transpose: Move Obstructing Standby FLS

Transpose requires the anticipated obstructing standby FLSs to #y to the coordinates of the illuminating FLSs that they are obstructing. While the standby assumes the lighting responsibility of the illuminating FLS, the original illuminating FLS goes dark and becomes the standby. See Figure 10.b.

Figure 12a shows the average number of display cells moved by an illuminating FLS to enable an obstructing standby FLS to substitute for it. With Q ⇒ 3, this distance is typically 1 display cell. There are scenarios in which the illuminating FLS may move two display cells because the next display cell along the vector 𝑔 may be occupied by a standby FLS. The probability of this is higher with small values of G. With the front view of the Skateboard, we noticed one scenario where the illuminating FLS is forced to move 4 display cells with 𝑂=3. This is due to two obstructing standby FLSs, 𝑖 1 and 𝑖 2 , blocking the same illuminating FLS 𝑜 1 . 𝑖 1 moves back !rst, occupying the coordinates of 𝑜 1 , while 𝑜 1 moves behind it. Subsequently, 𝑖 2 moves back, replacing the illuminating FLS 𝑜 1 (old 𝑖 1 ) and becomes the new illuminating FLS, while requiring 𝑖 1 and 𝑜 1 to move. In both of these steps, 𝑜 1 has encountered another FLS and moved 1 more display cell back, resulting in a total movement of 4 display cells.

Figure 12b shows the average number of display cells moved by an obstructing dark standby FLS to occupy the display cell of an illuminating FLS. This number is considerably higher than the number of display cells moved by an illuminating FLS (compare Figure 12a with 12b) because

Techniques to Conceal Dark Standby Flying Light Specks 1:13 Algorithm 2: DetectObstructingFLS ([𝑝 𝑆𝑏𝑏𝑐𝑋 ], [𝑝 𝑑𝐿𝑁𝑒𝑓 ], 𝑞 𝑐𝑑𝑔 ) 1 Sort [𝑝 𝑆𝑏𝑏𝑐𝑋 ] in increasing order of distance to 𝑞 𝑐𝑑𝑔 2 𝑖𝑟𝑠𝑘𝑡𝑢𝑣𝑘𝑊𝑆𝑤 ⇑ [] /* Initialize an empty array */ 3 for Coordinate 𝑞 𝑑𝐿𝑒𝑁𝑓 in [𝑝 𝑑𝐿𝑁𝑒𝑓 ] do 4 𝑊𝑠_𝑑𝑟𝑠𝑘𝑡𝑢𝑣𝑘𝑊𝑆𝑤 ⇑ 𝑁𝑥𝑦𝑠𝑧 5 [𝑔 ] ⇑ coordinates of 8 vertices and the center of the display cell 6 for Coordinate 𝛥 in [𝑔 ] do 7 𝑂𝑥𝑛𝑧𝑔 𝑧𝑣 ⇑ 𝑆𝑑𝑡𝑐𝑥𝑦𝑊𝑛𝑧𝑒 (𝛥 ↓ 𝑞 𝑐𝑑𝑔 ) 8 for Coordinate 𝑞 𝑆𝑏𝑏𝑐𝑋 in [𝑝 𝑆𝑏𝑏𝑐𝑋 ] do 9 𝑂𝑥𝑛𝑧𝑔 𝑧𝑣 ⇑ 𝑆𝑑𝑡𝑐𝑥𝑦𝑊𝑛𝑧𝑒 (𝛥 ↓ 𝑞 𝑐𝑑𝑔 ) 10 𝑗 𝑋𝑆𝑌 ⇑ the coordinate in [𝑔 ] with smallest [𝑙, 𝑚, 𝑛] value 11 𝑗 𝑋𝑍𝑎 ⇑ the coordinate in [𝑔 ] with largest [𝑙, 𝑚, 𝑛] value 12 if RayBoxIntersection(𝑞 𝑐𝑑𝑔 , 𝑂𝑥𝑛𝑧𝑔 𝑧𝑣, 𝑗 𝑋𝑆𝑌 , 𝑗 𝑋𝑍𝑎 ) then 13 𝑒 𝑆𝑏𝑏𝑐𝑋 ⇑ distance from 𝑞 𝑐𝑑𝑔 to 𝑞 𝑆𝑏𝑏𝑐𝑋 14 𝑒 𝑑𝐿𝑁𝑒𝑓 ⇑ distance from 𝑞 𝑐𝑑𝑔 to 𝑞 𝑑𝐿𝑁𝑒𝑓 15 if 𝑒 𝑆𝑏𝑏𝑐𝑋 > 𝑒 𝑑𝐿𝑁𝑒𝑓 and 𝑞 𝑑𝐿𝑁𝑒𝑓 not in illumination cell then 16 𝑊𝑠_𝑑𝑟𝑠𝑘𝑡𝑢𝑣𝑘𝑊𝑆𝑤 ⇑ 𝑎𝑡𝑢𝑧 17 end 18 end 19 end 20 end 21 A++%),(𝑖𝑟𝑠𝑘𝑡𝑢𝑣𝑘𝑊𝑆𝑤, 𝑊𝑠_𝑑𝑟𝑠𝑘𝑡𝑢𝑣𝑘𝑊𝑆𝑤) 22 end 23 return 𝑖𝑟𝑠𝑘𝑡𝑢𝑣𝑘𝑊𝑆𝑤 Algorithm 3: Dissolve([𝑝 𝑆𝑏𝑏𝑐𝑋 ], [𝑝 𝑑𝐿𝑁𝑒𝑓 ], 𝑣𝑧𝑆𝑘𝑧𝑡 ) 1 𝑒𝑊𝑠𝑘 ⇑ the distance between the user and the 𝑣𝑧𝑆𝑘𝑧𝑡 of the shape 2 𝛩 ⇑ the granularity of the angle steps 3 𝑞𝑡𝑧𝛥_𝑑𝑟𝑠𝑘𝑡𝑢𝑣𝑘𝑊𝑆𝑤 ⇑ [𝑁𝑥𝑦𝑠𝑧] 4 for Index 𝑊 ⇔ [1, 2 𝑖 ] do 5 𝑞 𝑐𝑑𝑗𝑔 ⇑ [𝑒𝑊𝑠𝑘 ↖ cos (𝑊𝛩 ), 𝑒𝑊𝑠𝑘 ↖ sin (𝑊𝛩 ), 0] 6 𝑑𝑟𝑠𝑘𝑡𝑢𝑣𝑘𝑊𝑆𝑤 ⇑ DetectObstructingFLS([𝑝 𝑆𝑏𝑏𝑐𝑋 ], [𝑝 𝑑𝐿𝑁𝑒𝑓 ], 𝑞 𝑐𝑑𝑔 ) 7 for 𝛬 ⇔ [1, total number of standby FLSs -1] do 8 if (!𝑞𝑡𝑧𝛥_𝑑𝑟𝑠𝑘𝑡𝑢𝑣𝑘𝑊𝑆𝑤[ 𝛬] and 𝑑𝑟𝑠𝑘𝑡𝑢𝑣𝑘𝑊𝑆𝑤[ 𝛬] then 9 R%&"-%(𝛬) 10 end 11 end 12 end

standby FLSs occupy the centroid of their group. Their movement causes the average distance from a standby FLS to its assigned group members to increase. In turn, this causes the MTID to increase. Figure 13 shows the percentage change in the MTID as a function of Q for G=3 and 20.

The percentage change is highest with a low Q value because it has a higher number of standby FLSs obstructing the user's FoV. 1 𝑒𝑊𝑠𝑘 ⇑ the distance between the user and the 𝑣𝑧𝑆𝑘𝑧𝑡 of the shape 2 𝛩 ⇑ the granularity of the degree check Once an obstructing FLS #ies to a new location, it may either stay at that location permanently or #y back to its original coordinates once it no longer obstructs the user's current and future FoV. Consider each in turn. The advantage of the !rst technique is that it may reduce the number of obstructing FLSs the next time the user looks at the shape from the same FoV. We analyzed this by considering a scenario where the user looks at a shape from the top, bottom, left, right, front and back. Subsequently, we analyzed the number of obstructing FLSs from each direction a second time.

The number of obstructing FLSs is shown in Figure 14. Their number is signi!cantly lower when compared with the !rst viewing, compare Figure 14 with 9. The percentage change is more than 60% with both 𝑂=3 and 20, see Figure 15. Similarly, the percentage change in the average number of display cells moved by an obstructed illuminating FLS and the dark standby FLS is signi!cantly reduced, see Figure 16.

The new placement of an obstructing standby FLS may diminish its bene!ts for failure handling. Its distance to its group members is no longer minimized. In certain cases, its distance to its group members may be greater than the dispatcher's distance to the group members. If the dispatcher is able to deploy FLSs at a very high rate, then it may be best to have no standby FLSs for some of the groups. This is trivial to implement and becomes a variant of Dissolve that requires an obstructing FLS to compute the average MTID to its group members using its new position. It also computes the average MTID for the dispatcher to deploy a replacement FLS for each of its group members. If its MTID is higher, then it dissolves its reliability group and #ies back to a hangar.

Figure 17 shows the MTID for the di"erent shapes and 𝑄 values with 𝑂=3 and a speedfoot_5 of 6.11 Meters/Second. The x-axis of this !gure is the distance from the centroid of a group to a dispatcher. The y-axis is MTID. It increases as a function of 𝑄 (compare 17.a with 17.c) because the display is larger 6 . The green line is the MTID without standbys. It is dictated by the distance of a failed FLS from a dispatcher. The blue line is the MTID provided using standbys. It is almost #at because the standbys are at the group centroid and the MTID of a failed illuminating FLS is independent of the distance from the dispatcher. The orange line is the MTID after the standby FLSs are adjusted so as not to obstruct the user's FoV. Every time the orange line exceeds the green line, the standby FLS does not provide a bene!t.

Figure 17 highlights the signi!cance of 𝑄 and the geometry of a shape. Consider each in turn. The number of orange points above the green line decreases as we increase 𝑄 (compare 17.a with 17.b and 17.c). This means the number of displaced standby FLSs that do not provide a bene!t decreases as the movement of standby FLSs is greater with small 𝑄 values, see Figure 12b. The geometry of a shape plays an important role. The hat is most sensitive to the user's FoV. Even with 𝑄=10, it has a few displaced FLSs that do not provide a bene!t, see the middle line chart of Figure 17.c. The displaced standbys provide the highest bene!t with the dragon and 𝑄>1, see the !rst line chart of Figure 17.b and 17.c. The observed trends with 𝑂=20 is the same as those with 𝑂=3, see Figure 18. A key di"erence is a lower density of the points in the line charts due to fewer standby FLSs. Approximately 7x fewer with 𝑂=20.

Dissolve the Reliability Group of the Obstructing Standby FLS

Dissolve is a technique that deactivates the reliability group of a standby FLS that obstructs the user's FoV, requiring the standby to #y to a hanger for permanent storage.

The geometry of a shape and the value of 𝑄 have a signi!cant impact on Dissolve and its number of impacted reliability groups. Figure 19a shows the percentage of reliability groups dissolved as a user walks around the Skateboard with the !eld of view changing 10 degrees at a time, see Figure 8. Almost all reliability groups are dissolved with Q=1, leaving only a handful of reliability groups once the user makes a full circle around the shape. The percentage of dissolved reliability groups is lower with Q=5 and 10 because there is a higher probability of a dark standby either occupying a display cell of an illumination cell or being eclipsed by an illumination cell from all angles. With Dissolve, a failed illuminating FLS in a deactivated reliability group must be restored using a dispatcher. This increases MTID signi!cantly. Figure 20a shows the percentage increase 7 as a function of the user walking around the Skateboard. With Q values 5 and 10, the percentage increase is higher because the display is larger, i.e., consists of Q 3 more display cells than Q=1. This requires a replacement FLS to travel a longer distance, i.e., display cells, from a dispatcher.

Suspend the Reliability Group of the Obstructing Standby FLS

Suspend improves on Dissolve by suspending reliability groups pertaining to an obstructing standby instead of deactivating them permanently. Once the user moves such that the standby is no longer obstructing or anticipated to obstruct, the standby #ies back to its original coordinates to re-activate its reliability group. The advantage of this technique is that it maintains a large number of reliability groups activated even with Q=1, see Figure 19b. This enables it to provide a superior MTID when compared with Dissolve.

This section presents two variants of Suspend, Suspend:Hangar and Suspend:Closest. While Suspend:Hangar requires the obstructing FLSs to travel back to a hangar similar to Dissolve, Suspend:Closest requires these FLS to move to a display cell of a close by illuminating FLS. The closest is a member of the reliability group of the standby FLS. Once the user moves such that the standby is no longer obstructing, Suspend:Hangar requires a dispatcher to deploy a standby FLS to restore the reliability group. However, Suspend:Closest requires the standby to travel from a close by illumination cell to its original location. Suspend:Closest maintains the reliability group intact. Should an FLS in the group fail, the standby is in close proximity of the failed FLS and #ies to resume the lighting responsibility of the failed FLS. Suspend:Closest works with 𝑄 ⇒ 2. With 𝑄 = 1, it may default to either Suspend:Hangar or Transpose 8 . Suspend:Closest is advantageous when dispatchers have a limited deployment rate. Moreover, it may minimize the traveled distance by a standby to re-activate its reliability group, enhancing MTID.

Figure 21 shows the average traveled distance with Dissolve and Suspend:Hangar. With Suspend:Hangar, we separate the distance traveled by standby FLSs to a hangar (Figure 21.b) from the distance traveled by a deployed standby to reactivate the reliability group (Figure 21.c). The total is signi!cantly higher than Dissolve. Some of the standbys restored by Suspend:Hangar after the user moves (say from 20 to 30 degrees) may become obstructing in a later movement of the user (say from 40 to 50 degrees), forcing the standby to #y back to the hangar again.

Figure 22 shows the average MTID with Suspend:Closest, i.e., hide the standby in the closest illuminating FLS. As a comparison yardstick, it shows the average MTID with the obstructing standby FLS. These results show hiding the standby in one of its group members provides a MTID (a) Q=3. (b) Q=5. (c) Q=10. comparable to having the obstructing standby in its original coordinates. In essence, for any x-axis value, only a few standby FLSs change location. And, the average is almost identical to having these standbys at their original coordinates.

A comparison of Transpose, Dissolve, and Suspend

Figure 23 shows the percentage increase in MTID with the alternative techniques. The MTID with Suspend:Closest is less than 4 Seconds, see Figure 22. It provides the best MTID when compared with the other techniques. MTID with Transpose and 𝑄 ⇒ 3 is also competitive. This is especially true with the Dragon. We include a variant of Suspend that hides the obstructing FLS in the obstructed illumination cell, restoring it to its original location once the user moves such that the standby is not obstructing. This technique, Suspend:Obstructed, provides a superior MTID when compared with Suspend:Hanger. However, it is inferior to Suspend:Closest. With 𝑄=1, Suspend:Closest does not apply. This is because an illumination cell consists of one display cell and it is occupied by the illuminating FLS. In this case, one may use either Transpose, Suspend:Hangar, or Suspend:Obstructed. The choice between these two techniques depends on a shape and its geometry. For example, Transpose is superior with the Dragon. However, Suspend:Hanger is superior with the Skateboard.

Figure 24 shows the average distance traveled by an obstructing standby FLS with the di"erent techniques. Dissolve and Suspend:Hangar result in a higher traveled distance when compared with the other techniques. With 𝑄 ⇒ 3, Transpose minimizes the distance traveled by standby FLSs. Once a standby FLS hides in an illumination cell, it remains there permanently. While this results in an inferior MTID, it does minimize the traveled distance. Suspend:Closest is not as competitive as Transpose. It requires the standby to move back to its original location once the user moves. This reduces MTID close to zero. However, it requires standby FLSs to travel a higher distance, see Figure 24.d and 24.e.

Conclusions and Future Research

This paper describes the use of reliability groups with standby FLSs to enhance the quality of illumination in the presence of FLSs failing. It strives to minimize the distance traveled by a replacement (standby) FLS to substitute for a failed FLS. This distance impacts the time to illuminate a dark point due to an FLS failure, MTID. We introduced several techniques to prevent a dark standby FLS from obstructing a user's !eld of view. Table 2 shows these techniques and how they di"er. Suspend:Closest provides the best MTID. We are currently investigating the lighting of FLSs to render illuminations. This includes exploring whether an obstructing standby may conceal itself by matching the light and the color of the blocked illuminating FLS. Such a technique will minimize MTID without requiring the obstructing standby FLS to move.

noti!ed of the failure, the standby changes its destination to the coordinates of the failed illuminating FLS to illuminate the dark point sooner, i.e., minimize MTID. The MOVE event is used to update the current location of the FLS. It is an internal event generated using a timer. This event is used to implement the velocity model and the amount of time required by an FLS to #y a !xed distance, e.g., from a dispatcher to the coordinates of a failed FLS, from the group centroid to the location of a failed FLS, etc. We describe the velocity model in Section A.1.

The STOP event is generated at the end of an experiment, causing all FLS processes to generate log records and terminate. Each FLS generates a unique log !le in a shared directory known to the Orchestrator. The Orchestrator processes these log !les to generate reports containing a value for the metrics of interest. Initiating an Illumination: A large number of FLSs must be deployed when an illumination is !rst initiated. We assume the Hub has a large number of multi-core processes and uses a divide-and-conquer approach to this challenge. This approach employs one Orchestrator and 𝛯 secondary processes. The Orchestrator launches the secondary processes and waits for them to join by generating the STOP message. The Orchestrator and secondary processes run on di"erent processors (servers). The secondary process launches the processes corresponding to FLSs that will utilize the cores of its processor (server). We use a network !le system with a well known directory visible to all the processes. An FLS constructs a unique log !le name using its FID and writes its monitored metrics in this !le once it receives the STOP message.

The Orchestrator maintains a !xed number of dispatchers, 𝑅. Each dispatcher has a priority queue for deploying FLSs, see Section 5. When the Orchestrator receives a REPLICA_REQ_HUB event from an FLS, it constructs a queue element with a new FID, the coordinates of its destination, its GID (group id), and the role of this FLS (illuminating or standby). Next, it selects a dispatcher using a policy (see Section 5.1 and places this element in the queue of the selected dispatcher. The dispatcher is a thread that waits on its queue, processes an element, and sleeps a !xed amount of time dictated by its dispatch rate. Processing an element means the dispatcher thread issues a message to the secondary process to launch an FLS process. The Orchestrator uses a simple mod function to assign these requests to the secondary processes in a round-robin manner.

A.1 Velocity Model

We assume an FLS has a velocity model that may optimize for either the time required or the energy consumed to arrive at its destination. The latter may maximize the #ight time of an FLS on a fully charged battery. The velocity model describes a maximum acceleration 𝑥 ↙ , a maximum deceleration 𝑥 ∝ , and a maximum speed 𝛯 𝑋𝑍𝑎 that an FLS may use to travel distance d. This is the distance from the FLS's current coordinate A to its destination coordinate B, d=|𝛱𝑗|. We assume the starting velocity of the FLS is zero. Factors such as gravity may cause 𝑥 ↙ to not equal 𝑥 ∝ . P!"#$%& D%'()(*(") 3. Minimize the time to travel distance 𝑒 from A to B without exceeding the maximum speed 𝛯 𝑋𝑍𝑎 , or exceeding either the maximum acceleration 𝑥 ↙ or maximum deceleration 𝑥 ∝ .

Three scenarios constitute the solution to this problem:

(1) d requires the FLS to accelerate at rate 𝑥 ↙ to reach 𝛯 𝑋𝑍𝑎 , travel at speed 𝛯 𝑋𝑍𝑎 until a well de!ned point, and decelerate at rate 𝑥 ∝ to come to a halt at B. (2) 𝑒 requires the FLS to accelerate at rate 𝑥 ↙ to reach 𝛯 𝑋𝑍𝑎 . However, the FLS must decelerate immediately at the rate 𝑥 ∝ to come to a halt at B. (3) d requires the FLS to accelerate to arrive at a well de!ned point. Prior to reaching 𝛯 𝑋𝑍𝑎 , the FLS must decelerate to come to a halt at B.