# Active Velocity Estimation using Light Curtains
via Self-Supervised Multi-Armed Bandits

Website: https://siddancha.github.io/projects/active-velocity-estimation1
Siddharth Ancha1 Gaurav Pathak2 Ji Zhang3 Srinivasa Narasimhan3 David Held3
1Massachusetts Institute of Technology, Cambridge, MA 02139, USA
2Adobe, San Jose, CA 95110, USA
3Carnegie Mellon University, Pittsburgh, PA 15213, USA

###### Abstract

To navigate in an environment safely and autonomously, robots must accurately
estimate where obstacles are and how they move. Instead of using expensive
traditional 3D sensors, we explore the use of a much cheaper, faster, and
higher resolution alternative: programmable light curtains. Light curtains are
a controllable depth sensor that sense only along a surface that the user
selects. We adapt a probabilistic method based on particle filters and
occupancy grids to explicitly estimate the position and velocity of 3D points
in the scene using partial measurements made by light curtains. The central
challenge is to decide where to place the light curtain to accurately perform
this task. We propose multiple curtain placement strategies guided by
maximizing information gain and verifying predicted object locations. Then, we
combine these strategies using an online learning framework. We propose a
novel self-supervised reward function that evaluates the accuracy of current
velocity estimates using future light curtain placements. We use a multi-armed
bandit framework to intelligently switch between placement policies in real
time, outperforming fixed policies. We develop a full-stack navigation system
that uses position and velocity estimates from light curtains for downstream
tasks such as localization, mapping, path-planning, and obstacle avoidance.
This work paves the way for controllable light curtains to accurately,
efficiently, and purposefully perceive and navigate complex and dynamic
environments.111Please see our project website for (1) the appendix, (2) an
overview video, (3) videos showing qualitative results of our method, and (4)
source code.

11footnotetext: 1Corresponding author. E-mail<EMAIL_ADDRESS>12This work was performed when SA and GP were affiliated with CMU.

(a) Light curtain working principle

(b) Bayes filter with self-supervised reward

Figure 1:  (a) Illustration of programmable light curtains adapted from [4].
An illumination plane (from the projector) and an imaging plane (of the
camera) intersect to produce a light curtain. A controllable galvanometer
mirror rotates synchronously with the camera’s rolling shutter and images the
points of intersection. See Sec. II-A for more details. (b) A Dynamic Bayes
network [65] for controllable sensing. At timestep $t$, $x_{t}$ corresponds to
the state of the world, $u_{t}$ corresponds to the action i.e. the location of
light curtain placement, $z_{t}$ corresponds to light curtain measurements,
and $\overline{bel}(x_{t})$ and $bel(x_{t})$ are the inferred distributions
over states before and after incorporating measurements $z_{t}$, respectively.
This is a slightly modified graphical model for controllable sensing where
actions $u_{t}$ don’t affect state $x_{t}$ but directly affect observations
$z_{t}$.

##  I Introduction

Robots in the real world must navigate in the presence of moving objects like
humans and vehicles whose motion is a priori unknown. This is a common
challenge in many applications like autonomous driving, indoor and outdoor
mobile robotics, and robot delivery. How should a robot sense and perceive
such dynamic environments? How can it accurately estimate the motion of
obstacles?

3D sensors such as LiDARs and depth cameras are conventionally used for robot
navigation. However, LiDARs are typically expensive and low-resolution.
Although cameras are cheaper and higher-resolution, depth estimates can be
noisy and inaccurate. An alternative paradigm is active perception [7, 8]
where a controllable sensor is actively guided to focus on only the relevant
parts of the environment. Programmable light curtains [69, 9, 4, 58, 5] are a
recently invented, lightweight 3D sensor that detects points intersecting any
user-specified 2D surface (“curtain”). Light curtains combine the best of
passive cameras (low cost, high resolution, and high speed) and LiDARs
(accurate depth estimation along the curtain, robustness to bright lighting
and scattered media like fog/smoke [69]). Compared to widely used commercial
LiDARs like the Ouster OS1-128 [43], a lab-built light curtain prototype is
relatively inexpensive ($1,000 v.s. $\sim$$20,000), higher vertical resolution
(1280 rows/$0.07^{\circ}$ v.s. 128 rows/$0.35^{\circ}$) and faster (45-60 Hz
v.s. 10-20 Hz). See App. E for benefits of light curtains over conventional
depth sensors. Because programmable light curtains are an active sensor,
realizing these benefits requires actively deciding where to place the curtain
at each timestep; this is the principal algorithmic challenge posed by
programmable light curtains.

Previously, light curtains have been used for object detection [4], depth
estimation [58], and estimating safety regions [5]. However, light curtains
have not been used to explicitly estimate velocities of dynamic objects.
Velocity estimation is crucial for many tasks in robotics such as trajectory
forecasting, obstacle avoidance, motion planning, and dynamic object removal
for SLAM [65].

The focus of this paper is to develop light curtain placement strategies that
improve velocity estimates. We use dynamic occupancy grids [23] to estimate
velocities and occupancies from points detected by light curtains without
requiring point cloud segmentation or explicit data association across frames.
First, we extend light curtain placement strategies from previous works [4, 5]
to integrate dynamic occupancy grids. Then, we propose a novel method to
switch between multiple light curtain placement strategies using a multi-armed
bandits approach. The feedback for the multi-armed bandits is obtained using a
novel self-supervised reward function that evaluates the current estimates of
occupancy and velocity using future light curtain placements, without
requiring ground truth or additional sensors. We obtain this supervision by
reusing intermediate quantities computed during recursive Bayes estimation of
dynamic occupancy grids; thus the self-supervised rewards do not require extra
light curtain placements or additional computations. We evaluate our approach
on challenging simulated and real-world environments with complex and fast
object motion. We integrate our method into a full-stack navigation pipeline
and show that the multi-armed bandits approach is able to outperform each
individual strategy.

Our contributions include:

  1. 1.

We re-derive the dynamic occupancy grid method [23] using a more rigorous
mathematical analysis grounded in Bayesian filtering [65] (Sec. IV, App. B).

  2. 2.

We design curtain placement strategies for dynamic occupancy grids to verify
predicted object locations (Sec. V-A) and maximize information gain in hybrid
discrete-continuous spaces (Sec. V-B, App. D).

  3. 3.

We propose a novel self-supervised reward function that evaluates current
velocity estimates using future light curtain placements without requiring
additional supervision. Using the self-supervised reward, we learn to combine
multiple curtain placement policies using a multi-armed bandit framework (Sec.
VI).

  4. 4.

We evaluate this approach in simulated and real-world environments with fast-
moving obstacles and demonstrate that it outperforms individual placement
strategies (Sec. VIII).

  5. 5.

We develop an efficient and parallelized pipeline where light curtain sensing,
grid estimation and computing curtain placement are tightly coupled and
continuously interact with each other at $\sim$45 Hz (Sec. VII, Fig. 4, App.
F).

  6. 6.

We integrate our method into a full-stack navigation pipeline that uses
position and velocity estimates to perform localization, mapping and obstacle
avoidance in real-world dynamic environments (App. K).

##  II Background

###  II-A Light curtain working principle

Programmable light curtains [69, 9, 4, 58, 5] are a recently developed
controllable depth sensor that image any user-specified vertically-ruled 2D
surface in the environment. The device contains two main components: a
rolling-shutter camera and a rotating light sheet laser (see illustration in
Fig. 1a). The camera activates one pixel column at a time, from left to right,
via the rolling shutter. We refer to the top-down projection of the imaging
plane corresponding to each pixel column as a “camera ray” (shown in Fig. 1a).
The shape of the light curtain is entirely specified by a 2D control point
selected on each camera ray (shown as gray and green circles). The set of
control points forms the input to the light curtain device. The laser is
vertically aligned and synchronized with the camera’s rolling shutter. A
controllable galvo-mirror rotates the light sheet to point it at the control
point corresponding to the currently active pixel column. Triangulated 3D
scene points that both (1) intersect the laser light sheet and (2) are visible
in the currently active pixel column, get detected by the device. If there
exists an object in the environment at the surface of this intersection, then
the point will have a large intensity in the camera reading; otherwise it will
not; thus the device outputs the subset of control points (shown as green
circles in Fig. 1a) that correspond to 3D object surfaces. Importantly, light
curtains form a partial observation on the scene, since only control points
can be detected. Please see [9, 69] for further details on the mechanism
behind a programmable light curtain.

###  II-B Bayes filtering

This section provides a brief background on Bayes filtering and introduces
notation used throughout the paper. A dynamic Bayes filter [65], also known as
a hidden Markov model or a state space model is represented by a probabilistic
graphical model shown in Fig. 1b. The state of the world at timestep $t$ is
denoted by $x_{t}$ (in our case, $x_{t}$ is the occupancy and velocity of a
set of cells arranged in a 2D grid from the top-down view; more details in
App. B-A). The control actions are denoted by $u_{t}$ (the locations where the
light curtain is placed). Observations obtained from the sensor are denoted by
$z_{t}$. Fig. 1b is a slight modification of the standard model for the task
of active perception, where actions don’t affect the state of the world
$x_{t}$ but directly affect the observations $z_{t}$.

The goal is to infer at each timestep $t$ the posterior distribution (a.k.a
“belief”) $bel(x_{t})=P(x_{t}\mid u_{1:t},z_{1:t})$ over the current state
$x_{t}$ from the sequence of sensor observations $z_{1:t}$ and the known
sequence of actions $u_{1:t}$. This is computed using recursive Bayesian
estimation [65] that alternates between two steps.

$\displaystyle\overline{bel}(x_{t})$
$\displaystyle=\int_{x_{t-1}}\leavevmode\nobreak\
bel(x_{t-1})\leavevmode\nobreak\ P(x_{t}\mid x_{t-1})\leavevmode\nobreak\
\mathrm{d}x_{t-1}$ (1) $\displaystyle bel(x_{t})$ $\displaystyle\propto
P(z_{t}\mid x_{t},u_{t})\leavevmode\nobreak\ \overline{bel}(x_{t})$ (2)

First, the motion update step computes an intermediate prior belief
$\overline{bel}(x_{t})$ by applying a motion model $P(x_{t}\mid x_{t-1})$ that
encodes the dynamics of the environment. Then, the measurement update step
computes the updated posterior belief $bel(x_{t})$ by incorporating sensor
observations from the current timestep. To make this paper self-contained, we
provide a detailed mathematical derivation of these steps in App. A.

(a) Dynamic occupancy grid: each cell contains occupancy and velocity
distributions

(b) Raycasting to compute freespace

(c) Raymarching to compute depth probs.

Figure 2:  (a) Dynamic occupancy grid. The 2D grid represents the top-down
view. Like conventional occupancy grids [29, 65], each cell contains an
occupancy probability $p\in[0,1]$. In addition, each cell also contains a set
of weighted particles where each particles stores a single 2D velocity. The
set of particles together represents a probability distribution of that cell’s
velocity. (b) Ray-casting to light curtain detections to extract freespace
information. Red cells contain detected points and are marked occupied. Blue
cells are freespace; they either lie undetected on the light curtain or lie on
rays cast from the sensor to the red cells. Gray denotes unknown occupancy.
Purple cells are outside the light curtain’s field of view. (c) Ray-marching
to compute the depth probabilities of cells along a camera ray. The depth
probability of the red cell is the product of the probability that the red
cell is occupied and the probabilities of each blue cell being unoccupied.

##  III Related Work

###  III-A Active perception and light curtains

Active perception involves actively controlling a sensor such as camera
parameters [7], moving a camera to look around occlusions [19], and next-best
view planning [21] for object instance classification [76, 28, 26, 60] and 3D
reconstruction [44, 47, 67, 24]. Programmable light curtains [69, 9, 16] are a
controllable depth sensor that have been used for active perception tasks such
as active object detection [4], active depth estimation [58], and actively
estimating safety regions [5]. However, most prior light curtain work has only
focused on estimating object positions. They either place curtains with fixed
scan patterns [69, 16] or adaptive curtains for static scenes without taking
object motion into account [9, 4, 58]. Ancha et al. [5] track safety regions
by learning to forecast future locations; this could be interpreted as
implicit velocity estimation. However, we are the first to explicitly estimate
obstacle velocities which can be used for other downstream tasks like
trajectory forecasting, obstacle avoidance and motion planning. Furthermore,
we combine multiple adaptive strategies like random curtains [9, 5],
maximizing information gain [4], and verifying predicted object locations [5]
using a novel multi-armed bandit framework for estimating both object
positions and velocities.

###  III-B Velocity estimation from point clouds

Prior works on estimating scene flow [68, 70, 49, 32, 63] compute
correspondences between point clouds acquired at consecutive timesteps;
velocities can then be extracted from these correspondences. Furthermore,
self-supervised approaches [54, 75, 45, 48, 10, 35] can learn to estimate
scene flow without requiring ground truth annotations. However, these methods
are designed to compute flow between complete scans of the environment, such
as those obtained from a LiDAR sensor, where correspondences exist for most
points. In contrast, a single light curtain measurement is a partial point
cloud – a subset of visible points that intersect the curtain. Depending on
where they are placed, consecutive light curtains may not contain any
correspondences at all. Therefore, scene flow methods are not suited for point
clouds acquired by light curtains.

Another approach is to first segment the point cloud into a collection of
separate objects [38, 27, 46, 64, 78, 41], track each object, and finally
register each object’s segmented point cloud across frames using either
optimization-based [11, 59, 36, 79, 77, 51], probabilistic [37, 39, 34, 2], or
learning-based [71, 72, 6, 20] methods. However, errors in point cloud
segmentation can lead to incorrect velocity estimates. Instead, our method
uses particle-based occupancy grids and avoids the need to perform either
segmentation or explicit data association across frames.

###  III-C Self-tuning Bayes filters

Prior works have used innovation i.e. the difference between predicted and
observed measurements of a Kalman filter, to “self-tune” model parameters
without needing ground truth annotations. Earlier works use an autoregressive
moving average innovation model (ARMA) [33, 55, 30, 25, 80]. More recent works
use the normalized innovation squared (NIS) metric to optimize Kalman filter
noise models using downhill simplex methods [57], Bayesian optimization [17,
18], and evolutionary algorithms [56, 12]. Our self-supervised metric is
inspired by Kalman filter innovation, but is used to select a sensor control
strategy at each timestep using multi-armed bandits rather than tuning noise
models.

##  IV Dynamic occupancy grids

We now describe how we apply dynamic occupancy grids [23] for velocity
estimation with light curtains. A dynamic occupancy grid is a Bayes filter
that combines two conventional representations in robotics: occupancy grids
and particle filters. Occupancy grids [29, 65] are a standard tool for mapping
the location of static objects in the environment from the 2D top-down view.
Each cell in the grid contains an occupancy probability $p\in[0,1]$, denoting
the probability of the cell being occupied by an object. Dynamic occupancy
grids [23] are an extension of classical occupancy grids (see Fig. 2a). Each
cell in the grid contains both the occupancy probability $p$ as well as a
probability distribution over 2D velocities. The velocity distribution is
represented by a set of weighted particles, where each particles stores a
single 2D velocity. The set of weighted particles approximates the true
velocity distribution.

While Danescu et. al. [23] showed that dynamic occupancy grids can accurately
estimate occupancies and velocities, the precise role of particles and what
they represent remained unclear. Particles were described as representing a
cell’s velocity distribution; however, the movement of particles from one cell
to another is somewhat inconsistent with this interpretation. Elsewhere,
particles are described as being “physical building blocks of the world”, i.e.
parts of objects that can move; however, under this interpretation, it is
unclear what distribution a set of particles is supposed to represent, since
each particle represents a different part of an object. Furthermore, the
particles were not only used to represent velocities, but their count inside a
cell was proportional to the occupancy probability. In this work, we re-derive
dynamic occupancy grids using a more rigorous mathematical analysis found in
App. B, in which we explicitly state the assumptions made and provide a
precise, mathematically rigorous interpretation of particles.

Motion and measurement updates: In the motion update step, particles are
resampled from each cell in the grid and moved to another cell based on their
velocities and the motion model. We assume access to a depth sensor (e.g.
light curtains, LiDAR, depth cameras) that measures depth but does not
directly measure velocity. In the measurement update step, the sensor provides
(noisy) observations of occupancy for a subset of un-occluded cells in the
grid. These observations are used to update the occupancy probabilities;
velocities are inferred indirectly in the motion update step that are
consistent with observed occupancies. This method is able to estimate
velocities from depth measurements alone without requiring explicit data
association across frames.

Raycasting to extract freespace information: As explained in Section II-A, a
light curtain only returns whether there is a 3D object surface at the
location of the control points where the camera rays and the laser sheets
intersect; no depth information is returned for other locations in the
environment. Fig. 2b shows an observation grid from a light curtain placement
where cells directly measured to be occupied are shown in red and free cells
are shown in blue. From this figure, we see that all voxels in between the
light curtain source and a detected point must be unoccupied. Since 3D points
were detected in the occupied cells, light must have traveled along these rays
without obstruction; we mark cells along these rays to be free (shown in blue
in Fig. 2b). To take advantage of this information, we cast rays using an
efficient voxel traversal algorithm [3, 42] from the sensor to occupied cells
(shown in red). More details can be found in App. B-C. Thus by exploiting
visibility constraints, we are able to extract more information from the light
curtain.

(a)  (b)  (c)

Figure 3:  (a) Mobile light curtain robot platform: A light curtain device (in
blue) is mounted on top of a mobile robot. We use this setup to perform real-
world experiments. (b) Simulated environment: consists of differently shaped
objects (cuboids and cylinders) moving in (1) linear oscillatory/harmonic
motion along various directions, (2) curved sinusoidal motion, and (3) random
Brownian motion. (c) Real-world environment: consists of two pedestrians
walking in front of the sensor in multiple directions, at different speeds and
in complex trajectories.

##  V Curtain placement strategies

Using dynamic occupancy grids and Bayesian filtering, we have a method to
infer occupancies and velocities explicitly from light curtain measurements
(details in App. B). The main challenge that we address in this paper is to
compute the best curtain placement from the dynamic occupancy grid i.e. from
the current estimates of occupancy and velocity. The measurements from the
placed curtain will be input back to upgrade the grid, closing the loop.

In order to compute the best curtain placement, we must first predict the
occupancy when the next light curtain will be placed. To do so, we forecast
the current dynamic occupancy grid, using the currently estimated velocities,
to the next timestep via the motion update step (Eqn. 1, Eqn. 4 in App. B-B).
In this section, we propose various curtain placement strategies computed from
the forecasted grid. In Sec. VI, we will propose a novel method to combine
them and outperform each individual strategy.

###  V-A Maximizing depth probability

Strategy 1: Depth Probability: Following Ancha et al. [5], Strategy 1 places
curtains at the highest probability object locations. This strategy is
motivated by the fact that a light curtain only senses visible object surfaces
when it intersects them. Therefore, this approach can be used to verify
whether objects are indeed located at the forecasted object locations.

Since occupancy grids are probabilistic, this strategy places curtains at
locations of highest “depth probability”, which is the probability that a
control point at a given cell would return a depth reading. The depth
probability of a cell is the probability that the cell is occupied, and all
occluding cells (lying on the ray starting from the sensor and ending at the
target cell) are free (see Fig. 2c). We borrow the idea of “ray marching” from
the literature on volumetric rendering [66, 53] to compute depth probabilities
efficiently; see App. C for more details on the algorithm and computational
complexity. For each camera ray, we place the curtain on the cell with the
maximum depth probability.

###  V-B Maximizing information gain

Another placement strategy that was found useful in previous work on 3D object
detection [4] was to place curtains at the regions of highest “uncertainty”.
This is based on the principle of maximizing information gain for active
sensing.

Recall the dynamic Bayes network in Fig. 1b. Given a forecasted prior belief
$P(x_{t})=\overline{bel}(x_{t})$, the information gain framework prescribes
that the action $u_{t}$ should be taken that maximizes the information gain
$\mathrm{IG}(x_{t},z_{t}\mid u_{t})$ between the state $x_{t}$ and the
observations $z_{t}$ when using $u_{t}$. Information gain, which is a well-
studied quantity in information theory, is the expected reduction in entropy
(i.e. uncertainty) before and after sensing:
$\mathrm{H}(P(x_{t}))-\mathbb{E}_{z_{t}\mid
u_{t}}\big{[}\mathrm{H}(P(x_{t}\mid z_{t},u_{t}))\big{]}$.

While information gain for conventional occupancy grids is straightforward to
derive [4], it is not so for the case of dynamic occupancy grids. This is
because the underlying state space of dynamic occupancy grids is a ‘mixture’
of discrete and continuous spaces – a cell can either be unoccupied or
occupied with a continuous velocity. Unfortunately, the entropy of such mixed
discrete-continuous spaces is not well-defined [31]. We overcome this problem
using a more general definition of information gain based on the
“Radon–Nikodym” derivative [31] that doesn’t require explicitly calculating
the entropy. In App. D, we show that the formula for information gain for
dynamic occupancy grids (under certain assumptions) turns out to equal the
occupancy uncertainty, described next.

Strategy 2: Occupancy Uncertainty: Let $\omega^{i}_{t}$ be the occupancy
probability estimated for the $i$-th cell at the $t$-th timestep. Then, the
information gain is the sum of binary cross entropies
$\mathrm{H}_{\text{occ}}(\omega^{i}_{t})=-\omega^{i}_{t}\leavevmode\nobreak\
\log_{2}\omega^{i}_{t}-(1-\omega^{i}_{t})\leavevmode\nobreak\
\log_{2}(1-\omega^{i}_{t})$ of the cells that the curtain lies on.
Intuitively, since measurements from a depth sensor only provide information
about occupancy and not velocity, the overall information gain is equal to the
total occupancy uncertainty. A similar information gain computation was used
in Ancha et al. [4] for static occupancy grids; in App. D we prove that the
formula for information gain is the same as total occupancy uncertainty even
for the more complex case of mixed discrete-continuous distributions. Strategy
2 places a curtain that maximizes the occupancy uncertainty.

Strategy 3: Velocity Uncertainty: Each cell also contains a velocity
distribution $V^{i}_{t}=\\{(v^{i,m}_{t},p^{i,m}_{t})\mid 1\leq m\leq M\\}$
represented by a set of $M$ weighted particles with velocities $v^{i,m}_{t}$
and weights $p^{i,m}_{t}$ that sum to $1$. In this strategy, we maximize the
sum of velocity entropies. The discrete set of particles is used to
approximate what is inherently a continuous velocity distribution. Therefore,
we must compute the differential entropy of the continuous velocity
distribution by first estimating its probability density function. We fit a
multivariate Gaussian distribution to the set of weighted particles with mean
$\mu=\sum_{m=1}^{M}p^{i,m}_{t}v^{i,m}_{t}$ and covariance matrix
$\Sigma=\sum_{m=1}^{M}p^{i,m}_{t}(v^{i,m}_{t}-\mu)(v^{i,m}_{t}-\mu)^{T}$.
Then, we compute the differential entropy of the fitted Gaussian:
$\mathrm{H}_{\text{vel}}(V^{i}_{t})=\frac{1}{2}\log\det(2\pi e\Sigma)$. One
could alternatively use other families of continuous distributions, such as
kernel density estimators. Finally, we place a curtain that maximizes the sum
of velocity entropies $\mathrm{H}_{\mathrm{vel}}$ of the cells the curtain
lies on.

Strategy 4: Combined Uncertainty: In this strategy, we maximize a weighted
combination of occupancy and velocity entropies:
$\mathrm{H}_{\mathrm{cmb}}(\omega^{i}_{t},V^{i}_{t})=\mathrm{H}_{\mathrm{occ}}(\omega^{i}_{t})+\omega^{i}_{t}\leavevmode\nobreak\
\mathrm{H}_{\mathrm{vel}}(V^{i}_{t})$. The velocity uncertainty is weighted by
the occupancy probability. This captures the notion that if the occupancy
probability is very low, then the overall uncertainty should also be low even
if the velocity uncertainty is high, because the velocity uncertainty is not
relevant if the cell is unoccupied. This is a heuristic curtain placement
policy that performs well in practice.

Figure 4: Implementation of our method as a parallelized pipeline. Our methods
contains three components: (1) light curtain sensing, (2) Bayes estimation of
dynamic occupancy grids, and (3) computing curtain placement. Each process can
be run in parallel in a separate thread at its own independent speed. The
three processes are tightly coupled in a closed loop using three grids as
shared memory. Our implementation ensures that information flows between the
threads safely and continuously.

##  VI Self-supervised multi-armed bandits

Can we combine the various curtain placement strategies developed in Sec. V to
improve performance? In this section, we develop a multi-armed bandit method
to do so enabled by a novel self-supervised reward function.

###  VI-A Multi-armed bandit framework

A multi-armed bandit [61] is an online learning framework consisting of a set
of actions or “arms”, where each action is associated with an unknown reward
function. The agent only observe samples from the reward distribution when it
takes that action. The goal is to maximize the cumulative reward over time.
The agent maintains a running average of the rewards for each action, called
Q-values. We use $\epsilon$-greedy multi-armed bandits [61], that trades-off
exploration with exploitation. With probability $\epsilon$, the bandit
performs exploration and chooses an action at random. With probability
$1-\epsilon$, it performs exploitation and chooses the action that has the
highest Q-value. We use multi-armed bandits to intelligently switch between
the four curtain placement strategies at test time.

###  VI-B Self-supervised rewards

The bandit framework requires a reward function to evaluate actions. Our
eventual goal is to accurately estimate occupancy and velocity. How can we
design a function that rewards improvements in occupancy and velocity
estimates, but can also be computed at test-time using only light curtain
placements and measurements? This is challenging because light curtains cannot
directly measure velocities; they can only measure the occupancies of a small
set of locations where they are placed.

Let us revisit the dynamic Bayes network from Sec. II-B, shown in Fig. 1b.
Belief distributions are represented by dynamic occupancy grids. At timestep
$t-1$, the grid representing the belief $bel(x_{t-1})$ was forecasted by
applying the motion model to obtain the prior belief $\overline{bel}(x_{t})$
at timestep $t$ (Eqn. 1, Eqn. 4 in App. B). Then, in the measurement update
step, the current light curtain measurement $z_{t}$ obtained by placing a
curtain at locations $u_{t}$ is used to update the grid to $bel(x_{t})$ (Eqn.
2, Eqn. 5 in App. B). Therefore, we attribute the accuracy of $bel(x_{t})$ to
action $u_{t}$.

The forecasted occupancy at time $t+1$ is computed by using the current
velocity estimates to forecast the current occupancy by an interval $\Delta t$
using the motion update step (Eqn. 1, Eqn. 4 in App. B). The forecasted
occupancy will be accurate if both the current velocities and current
occupancies are accurate. Therefore, the accuracy of forecasted occupancy acts
as an appropriate reward function that captures both occupancy and velocity
accuracies.

How do we evaluate forecasted occupancy computed using $bel(x_{t})$, without
requiring ground truth, in a self-supervised way? This is possible by reusing
intermediate quantities output during recursive Bayesian updates.

First, note that the forecasted occupancy of $bel(x_{t})$ is
$\overline{bel}(x_{t+1})$ computed by the next motion update step. Our main
insight is that before applying the next measurement update step,
$\overline{bel}(x_{t+1})$ can be evaluated using the partial occupancy
observed by the next light curtain measurements $z_{t+1}$. We use the F1-score
between the forecasted occupancy grid and the partially observed occupancy
grid as a self-supervised reward for the previous light curtain placement
$u_{t}$ (See Fig. 1b). Specifically, we compute the self-supervised reward
$R_{t}=\text{F\textsubscript{1}}(\overline{bel}(x_{t+1}),z_{t+1})$, where
$\overline{bel}(x_{t+1})$ is computed using Eqn. 1 (more specifically, Eqn. 4
in App. B), and $z_{t+1}$ is the partial occupancy observed at time $t+1$. See
App. G for details on the F1-score.

An advantage of our self-supervised reward is that it does not require any
extra computation. This is because (1) occupancy forecasting of $bel(x_{t})$
is performed anyway as part of the motion update step, and (2) the partial
occupancy information from $z_{t+1}$ is computed anyway in the next
measurement update step. By reusing quantities already computed during
recursive Bayes filtering, our self-supervised reward does not require any
extra forecasting steps nor any extra light curtain placements.

At each timestep, we use the $\epsilon$-greedy strategy to select one among
the four curtain placement strategies $a\in\\{a_{1},a_{2},a_{3},a_{4}\\}$.
Then we compute the curtain placement $u_{t}$ according to strategy $a$. When
the accuracy of the forecasted occupancy $R_{t}$ is obtained in the next
timestep, we update the Q-value of $a$ as $Q(a)\coloneqq
Q(a)+\alpha\leavevmode\nobreak\ [R_{t}-Q(a)]$. We use the non-stationary
reward formulation [61] of multi-armed bandits with smoothing parameter
$\alpha$ to account for the possibility that different strategies
$\\{a_{1},a_{2},a_{3},a_{4}\\}$ may be superior at different times. See App. I
for more details.

##  VII Parallelized pipeline

Fig. 4 shows our pipeline that has three processes: (1) light curtain sensing,
(2) Bayes filtering using dynamic occupancy grids, and (3) computing curtain
placement. The processes are run in parallel threads with shared memory, at
their own independent speeds.

1\. Light curtain imaging: This thread continuously places curtains at
locations determined by one of the four strategies described in Sec. V.
However, when waiting for the next curtain placement to be computed, it places
random curtains [5] (that are generated offline) to sense random locations in
the scene. This ensures that the device is always kept busy and runs at
approximately 45 Hz.

2\. Bayes filtering: This thread inputs light curtain measurements and updates
the dynamic occupancy grid. It alternates between motion and measurement
update steps (Eqns. 1, 2, Eqns. 4, 5 in App. B). The motion update step
requires two grids, each representing the current and next timesteps.
Particles are sampled from the current grid, perturbed according to the motion
model, and inserted into the next grid. The roles of the two grids are swapped
at every successive motion update to avoid copying data. This thread runs at
approximately 35 Hz.

3\. Computing curtain placement:  This uses the most recent dynamic occupancy
grid to compute the next curtain placement (Sec. V). It first forecasts the
grid, using the same motion update step (Eqn. 1, Eqn. 4 in App. B), to the
next timestep when the next curtain is expected to be imaged. The forecasted
occupancy is used to compute the curtain placement. In App. F, we describe how
an extra grid is used to ensure thread-safety and that no thread ever needs to
wait on another to finish processing. Finally, the control points of the
computed curtain are sent to the light curtain device. The three inter-
dependent processes are tightly coupled and continuously interact with each
other.

|  Simulated environment |  Real environment
---|---|---
11 |  |  |  |  |  |  |  |  |  |
|  Classification accuracy | Precision | Recall | F1-score | IOU  |  Classification accuracy | Precision | Recall | F1-score | IOU
| $\uparrow$ | $\uparrow$ | $\uparrow$ | $\uparrow$ |  $\uparrow$ | $\uparrow$ | $\uparrow$ | $\uparrow$ | $\uparrow$ |  $\uparrow$
Simulated LiDAR | 0.9584 | 0.2498 | 0.1073 | 0.1360 | 0.0787  | NA
Random curtains only | 0.9662 | 0.2698 | 0.0567 | 0.0850 | 0.0468  | 0.9852 | 0.6306 | 0.2357 | 0.2405 | 0.2136
Max. depth probability | 0.9610 | 0.2448 | 0.1146 | 0.1388 | 0.0792  | 0.9832 | 0.5943 | 0.2727 | 0.3047 | 0.2353
Max. occupancy uncertainty | 0.9609 | 0.2717 | 0.1266 | 0.1493 | 0.0857  | 0.9811 | 0.5733 | 0.3041 | 0.3319 | 0.2515
Max. velocity uncertainty | 0.9648 | 0.2728 | 0.0581 | 0.0838 | 0.0458  | 0.9864 | 0.6221 | 0.2615 | 0.2545 | 0.2232
Max. occupancy + velocity uncertainty | 0.9629 | 0.3026 | 0.1251 | 0.1544 | 0.0895  | 0.9822 | 0.5899 | 0.3175 | 0.3421 | 0.2727
Multi-armed bandits (Ours) | 0.9623 | 0.2814 | 0.1402 | 0.1690 | 0.0976 | 0.9854 | 0.6467 | 0.3647 | 0.3703 | 0.3053
|  |  |  |  |  |  |  |  |  |
Table I: Accuracy of occupancy and velocity estimation measured using
forecasted occupancy in (a) simulated, and (b) real environments.

##  VIII Experiments

Figure 5: Velocity estimation in simulation. (a) The environment with moving
blocks and curtain placement shown in blue. (b) Color-coding for visualizing
velocity from the top-down view. (c) Ground truth occupancy and velocity. (d)
Raw light curtain images; high intensities are good because it means that
object surfaces were found and intersected by the light curtain. (e) Partial
occupancy observations from light curtain measurements that are input to the
dynamic occupancy grid. (f) Velocity and occupancy estimated by the dynamic
occupancy grid. We advise the reader to view video examples on the project
website. Figure 6: Velocity estimation in the real world using multi-armed
bandits (MAB). Please refer to titles and Fig. 5 for descriptions of each
column. Our method only uses light curtains; RGB images are for visualization
only. The rightmost column shows the Q-values of each strategy. Higher Q-value
is better; the action with the highest Q-value is chosen during exploitation.
Top row: shows two pedestrians walking at relaxed speeds. The directions of
motion are correctly inferred for each person: the pedestrian walking to the
right is shown in greenish-blue and the person walking to the left is colored
in red. The current action selected maximizes occupancy uncertainty. The
bottom row shows a more challenging environment where where a lone pedestrian
performs fast motion: running and jumping. The direction of velocity is
correctly inferred as moving top-left (left and away from the sensor) i.e.
reddish pink. The color saturation is high indicating the larger magnitude of
velocity. The current action selected maximizes depth probability. We advise
the reader to view the video examples on the project website.

###  VIII-A Environments

Simulation environment: We use a simulated environment consisting of various
blocks moving in a variety of motions (see Fig. 3b). The environment contains
cylinders and cuboids, moving in (1) linear, harmonic (oscillatory) motion
along different directions, (2) curved sinusoidal motion, and (3) random
Brownian motion. We use an efficient light curtain simulator described in App.
J.

Real-world environment: Our real-world environment consists of a mobile robot
with a mounted light curtain device (Fig. 3a) navigating in the presence of
two pedestrians walking in multiple directions, at different speeds and in
complicated trajectories (see Fig. 3c).

###  VIII-B Evaluation metrics

Since we wish to evaluate the accuracy of both occupancy and velocity
estimates, we use the forecasted occupancy [50, 1] as our evaluation metric.
As noted in Sec. VI-B, the forecasted occupancy will be accurate if both
current velocities and current occupancies are accurate. The future occupancy
at time $t+\Delta t$ is computed by the motion update step (Eqn. 1, Eqn. 4 in
App. B) that uses the current velocity to forecast the current occupancy by an
interval $\Delta t$. This metric is particularly relevant for obstacle
avoidance where estimates of future obstacle locations must be accurately
computed to plan safe, collision-free paths.

Ideally, the accuracy of forecasted occupancy can be computed by comparing it
against ground truth occupancy at $t+\Delta t$. This is possible in simulated
environments where ground truth occupancy is available for all grid cells. In
real-world environments, true occupancy can only be measured for a subset of
cells by the light curtain; in this case, we use the “self-supervised” version
of the metric described in Sec. VI-B. We follow prior works [40, 52, 62] that
treat the evaluation of occupancy as a classification problem and compute
several metrics: (1) classification accuracy [40, 52], (2) precision, (3)
recall, (4) F1-score and (5) the IoU [62] between the predicted and ground
truth occupancy masks. For more details on these metrics, please see App. G.

###  VIII-C Quantitative analysis

Table I shows the performance of various light curtain placement strategies in
simulated and real-world environments, evaluated using multiple forecasted
occupancy metrics (see Sec. VIII-B, App. G). Since a large proportion of cells
are unoccupied, the classification accuracy of all methods is very similar.
Furthermore, precision and recall metrics can be deceived by mostly predicting
negative and positive labels respectively. However, the F1-score and IoU
metrics are discriminative and robust; they are high only when both precision
and recall are high. Therefore, we focus on these two metrics (shown in blue).
In both sets of experiments, multi-armed bandits that combine the four curtain
placement policies using our self-supervised reward outperform all other
methods. This shows that intelligently switching between multiple placement
strategies is more beneficial than using any one single strategy at all times.

Between the other four strategies, maximizing occupancy uncertainty and
maximizing a linear combination of occupancy and velocity uncertainty perform
comparably. Maximizing velocity uncertainty tends to perform the worst.
Fortunately, multi-armed bandits learn to downweight this under-performing
strategy (see Table II, rightmost column in Fig. 6). We also compare against
other baselines: using only random curtains (without placing any computed
curtains), and with a simulated LiDAR. Unsurprisingly, using random curtains
performs the worst. All non-random curtain policies except maximizing velocity
uncertainty are able to outperform LiDAR. This is because light curtains are
faster ($\sim$45 Hz) and can be placed intelligently to maximize the accuracy
of occupancy and velocity estimates.

Table II shows an analysis specific to the multi-armed bandit method. Please
see the caption for details. We find that the best performing policies in
Table I have the highest Q-values and are selected most frequently. The
following trend holds: the better the performance of an individual policy when
used in isolation (shown in Table I), the higher is its average Q-value and
its frequency of being chosen. However, a combination of all policies (MAB) is
better than any single one.

|  Frequency of selection |  Avg. Q-value function (IOU)
---|---|---
Max. depth probability | 22.9% |  0.261
Max. occupancy uncertainty | 31.1% |  0.276
Max. velocity uncertainty | 13.4% |  0.202
Max. occupancy + velocity uncertainty | 32.5% |  0.292
|  |
Table II: Quantitative analysis of the multi-armed bandit method. The first
column shows the percentage of times each action (i.e. curtain placement
policy) was chosen. The second column shows the average Q-value of each action
computed by the multi-armed bandit. Higher Q-value is better; the action with
the highest value is selected during exploitation.

###  VIII-D Qualitative analysis

Visualizing velocities and occupancies: We use the HSV colorwheel [73] shown
in Fig. 5 and 6, to jointly visualize velocities and occupancies. The color
‘value’ (from HSV) encodes the occupancy probability; dark is low occupancy
probability and bright is high occupancy probability. The ‘hue’ encodes the
direction of velocity from the top-down view. ‘Saturation’ encodes the
magnitude of velocity: white is stationary whereas colorful corresponds to
high speed. See App. H for more details.

Examples. Fig. 5 shows an example of velocity estimation in the simulated
environment and Fig. 6 shows qualitative results on the real-world environment
using our multi-armed bandits (MAB) curtain placement method. Please see
captions for explanation. We advise the reader to view the video examples on
the project website. In Fig. 5, we see that the estimated velocities appear to
be consistent with the ground truth, as shown by the corresponding colors that
indicate the estimated and ground-truth velocity directions.

Full-stack navigation. We integrate our system into a full-stack navigation
pipeline [15] that performs planning, control and obstacle avoidance. We mount
the light curtain device on a mobile robot (see Fig. 3a). We use ORB-SLAM3
[13] for localization and mapping that takes depth from light curtains as
input. Using position and velocity estimates, the robot is able to perform
dense mapping in an indoor environment and avoids static and dynamic
obstacles. Please see App. K for more details.

##  IX Conclusion

In this work, we develop a method using programmable light curtains, an
actively controllable resource-efficient sensor, to estimate the positions and
velocities of objects in complex, dynamic scenes. We use a probabilistic
framework based on particle filters and occupancy grids to estimate velocities
from partial light curtain measurements. We design curtain placement policies
that verify predicted object locations and maximize information gain.
Importantly, we combine the strengths of these policies using a novel multi-
armed bandits framework that switches between the placement strategies to
improve performance. This is enabled by our novel self-supervised reward
function that evaluates current velocity estimates using future light curtain
placements with only minimal computational overhead. We integrate our method
into a full-stack navigation system that performs localization, mapping and
obstacle avoidance using light curtains. We hope our work paves the way for
combining multiple sensor control strategies using self-supervised feedback
for perception and navigation in complex and dynamic environments.

## Acknowledgments

We thank Pulkit Grover for discussions on information-theoretic measures of
mixed discrete-continuous random variables. This material is based upon work
supported by the National Science Foundation under Grants No. IIS-1849154,
IIS-1900821, the United States Air Force and DARPA under Contract No.
FA8750-18-C-0092, and a grant from the Manufacturing Futures Institute at
Carnegie Mellon University.

## References

  * way [2022] Waymo Occupancy and Flow Prediction Challenge.  2022\.  [Online; accessed 22-December-2022].
  * Agamennoni et al. [2016] Gabriel Agamennoni, Simone Fontana, Roland Y Siegwart, and Domenico G Sorrenti.  Point clouds registration with probabilistic data association.  In _2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , pages 4092–4098. IEEE, 2016.
  * Amanatides et al. [1987] John Amanatides, Andrew Woo, et al.  A fast voxel traversal algorithm for ray tracing. In _Eurographics_ , volume 87, pages 3–10, 1987.
  * Ancha et al. [2020] Siddharth Ancha, Yaadhav Raaj, Peiyun Hu, Srinivasa G. Narasimhan, and David Held.  Active Perception Using Light Curtains for Autonomous Driving.  In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm, editors, _Computer Vision – ECCV 2020_ , pages 751–766, Cham, 2020. Springer International Publishing.  ISBN 978-3-030-58558-7.
  * Ancha et al. [2021] Siddharth Ancha, Gaurav Pathak, Srinivasa Narasimhan, and David Held.  Active Safety Envelopes using Light Curtains with Probabilistic Guarantees.  In _Proceedings of Robotics: Science and Systems_ , Virtual, July 2021\.  doi: 10.15607/rss.2021.xvii.045.
  * Aoki et al. [2019] Yasuhiro Aoki, Hunter Goforth, Rangaprasad Arun Srivatsan, and Simon Lucey.  PointNetLK: Robust & efficient point cloud registration using PointNet.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 7163–7172, 2019.
  * Bajcsy [1988] Ruzena Bajcsy.  Active perception.  _Proceedings of the IEEE_ , 76(8):966–1005, 1988\.
  * Bajcsy et al. [2018] Ruzena Bajcsy, Yiannis Aloimonos, and John K Tsotsos.  Revisiting active perception.  _Autonomous Robots_ , 42(2):177–196, 2018.
  * Bartels et al. [2019] Joseph R Bartels, Jian Wang, William Whittaker, Srinivasa G Narasimhan, et al.  Agile depth sensing using triangulation light curtains.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 7900–7908, 2019.
  * Baur et al. [2021] Stefan Andreas Baur, David Josef Emmerichs, Frank Moosmann, Peter Pinggera, Björn Ommer, and Andreas Geiger.  SLIM: Self-supervised LiDAR scene flow and motion segmentation.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 13126–13136, 2021.
  * Besl and McKay [1992] P.J. Besl and Neil D. McKay.  A method for registration of 3-D shapes.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 14(2):239–256, 1992.  doi: 10.1109/34.121791.
  * Cai et al. [2019] Levi Cai, Burak Boyacıoğlu, Sarah E Webster, Lora Van Uffelen, and Kristi Morgansen.  Towards auto-tuning of Kalman filters for underwater gliders based on consistency metrics.  In _OCEANS 2019 MTS/IEEE Seattle_ , pages 1–6. IEEE, 2019.
  * Campos et al. [2021] Carlos Campos, Richard Elvira, Juan J Gómez Rodríguez, José MM Montiel, and Juan D Tardós.  ORB-SLAM3: An accurate open-source library for visual, visual–inertial, and multimap SLAM.  _IEEE Transactions on Robotics_ , 37(6):1874–1890, 2021.
  * Cao et al. [2021] Chao Cao, Hongbiao Zhu, Howie Choset, and Ji Zhang.  Tare: A hierarchical framework for efficiently exploring complex 3d environments.  In _Robotics: Science and Systems Conference (RSS), Virtual_ , 2021\.
  * Cao et al. [2022] Chao Cao, Hongbiao Zhu, Fan Yang, Yukun Xia, Howie Choset, Jean Oh, and Ji Zhang.  Autonomous exploration development environment and the planning algorithms.  In _2022 International Conference on Robotics and Automation (ICRA)_ , pages 8921–8928. IEEE, 2022.  URL https://www.cmu-exploration.com/development-environment.
  * Chan et al. [2022] Dorian Chan, Srinivasa Narasimhan, and Matthew O’Toole.  Holocurtains: Programming Light Curtains via Binary Holography.  _Computer Vision and Pattern Recognition_ , 2022.
  * Chen et al. [2018] Zhaozhong Chen, Christoffer Heckman, Simon Julier, and Nisar Ahmed.  Weak in the NEES?: Auto-tuning Kalman filters with Bayesian optimization.  In _2018 21st International Conference on Information Fusion (FUSION)_ , pages 1072–1079. IEEE, 2018.
  * Chen et al. [2019] Zhaozhong Chen, Nisar Ahmed, Simon Julier, and Christoffer Heckman.  Kalman filter tuning with Bayesian optimization.  _arXiv preprint arXiv:1912.08601_ , 2019.
  * Cheng et al. [2018] Ricson Cheng, Arpit Agarwal, and Katerina Fragkiadaki.  Reinforcement learning of active vision for manipulating objects under occlusions.  In _Conference on Robot Learning_ , pages 422–431. PMLR, 2018.
  * Choy et al. [2020] Christopher Choy, Wei Dong, and Vladlen Koltun.  Deep global registration.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 2514–2523, 2020.
  * Connolly [1985] Cl Connolly.  The determination of next best views.  In _Proceedings. 1985 IEEE international conference on robotics and automation_ , volume 2, pages 432–435. IEEE, 1985.
  * Cover and Thomas [2006] Thomas M. Cover and Joy A. Thomas.  _Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing)_.  Wiley-Interscience, USA, 2006.  ISBN 0471241954.
  * Danescu et al. [2011] Radu Danescu, Florin Oniga, and Sergiu Nedevschi.  Modeling and tracking the driving environment with a particle-based occupancy grid.  _IEEE Transactions on Intelligent Transportation Systems_ , 12(4):1331–1342, 2011.
  * Daudelin and Campbell [2017] Jonathan Daudelin and Mark Campbell.  An adaptable, probabilistic, next-best view algorithm for reconstruction of unknown 3-d objects.  _IEEE Robotics and Automation Letters_ , 2(3):1540–1547, 2017.
  * Deng et al. [2008] Zi-Li Deng, Yuan Gao, Chun-Bo Li, and Gang Hao.  Self-tuning decoupled information fusion Wiener state component filters and their convergence.  _Automatica_ , 44(3):685–695, 2008.
  * Denzler and Brown [2002] Joachim Denzler and Christopher M Brown.  Information theoretic sensor data selection for active object recognition and state estimation.  _IEEE Transactions on pattern analysis and machine intelligence_ , 24(2):145–157, 2002.
  * Douillard et al. [2011] Bertrand Douillard, James Underwood, Noah Kuntz, Vsevolod Vlaskine, Alastair Quadros, Peter Morton, and Alon Frenkel.  On the segmentation of 3D LIDAR point clouds.  In _2011 IEEE International Conference on Robotics and Automation_ , pages 2798–2805. IEEE, 2011.
  * Doumanoglou et al. [2016] Andreas Doumanoglou, Rigas Kouskouridas, Sotiris Malassiotis, and Tae-Kyun Kim.  Recovering 6D object pose and predicting next-best-view in the crowd.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 3583–3592, 2016.
  * Elfes [1989] Alberto Elfes.  Using occupancy grids for mobile robot perception and navigation.  _Computer_ , 22(6):46–57, 1989.
  * Fung and Grimble [1983] Patrick Fung and Mike Grimble.  Dynamic ship positioning using a self-tuning Kalman filter.  _IEEE Transactions on Automatic Control_ , 28(3):339–350, 1983.
  * Gao et al. [2017] Weihao Gao, Sreeram Kannan, Sewoong Oh, and Pramod Viswanath.  Estimating mutual information for discrete-continuous mixtures.  _Advances in neural information processing systems_ , 30, 2017.
  * Gu et al. [2019] Xiuye Gu, Yijie Wang, Chongruo Wu, Yong Jae Lee, and Panqu Wang.  HPLFlowNet: Hierarchical permutohedral lattice flownet for scene flow estimation on large-scale point clouds.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 3254–3263, 2019.
  * Hagander and Wittenmark [1977] Per Hagander and Björn Wittenmark.  A self-tuning filter for fixed-lag smoothing.  _IEEE Transactions on Information Theory_ , 23(3):377–384, 1977.
  * Hähnel and Burgard [2002] Dirk Hähnel and Wolfram Burgard.  Probabilistic matching for 3D scan registration.  In _Proc. of the VDI-Conference Robotik_ , volume 2002. Citeseer, 2002\.
  * He et al. [2022] Pan He, Patrick Emami, Sanjay Ranka, and Anand Rangarajan.  Self-Supervised Robust Scene Flow Estimation via the Alignment of Probability Density Functions.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 36(1):861–869, Jun. 2022.  doi: 10.1609/aaai.v36i1.19968.
  * Held et al. [2013] David Held, Jesse Levinson, and Sebastian Thrun.  Precision tracking with sparse 3D and dense color 2D data.  In _2013 IEEE International Conference on Robotics and Automation_ , pages 1138–1145. IEEE, 2013.
  * Held et al. [2014] David Held, Jesse Levinson, Sebastian Thrun, and Silvio Savarese.  Combining 3D Shape, Color, and Motion for Robust Anytime Tracking.  In _Robotics: science and systems_ , volume 1. Citeseer, 2014.
  * Held et al. [2016a] David Held, Devin Guillory, Brice Rebsamen, Sebastian Thrun, and Silvio Savarese.  A Probabilistic Framework for Real-time 3D Segmentation using Spatial, Temporal, and Semantic Cues. In _Robotics: Science and Systems_ , volume 12, 2016a.
  * Held et al. [2016b] David Held, Jesse Levinson, Sebastian Thrun, and Silvio Savarese.  Robust real-time tracking combining 3D shape, color, and motion.  _The International Journal of Robotics Research_ , 35(1-3):30–49, 2016b.
  * Hornung et al. [2013] Armin Hornung, Kai M Wurm, Maren Bennewitz, Cyrill Stachniss, and Wolfram Burgard.  OctoMap: An efficient probabilistic 3D mapping framework based on octrees.  _Autonomous robots_ , 34(3):189–206, 2013.
  * Hu et al. [2020a] Peiyun Hu, David Held, and Deva Ramanan.  Learning to optimally segment point clouds.  _IEEE Robotics and Automation Letters_ , 5(2):875–882, 2020a.
  * Hu et al. [2020b] Peiyun Hu, Jason Ziglar, David Held, and Deva Ramanan.  What you see is what you get: Exploiting visibility for 3D object detection.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 11001–11009, 2020b.
  * Inc. [2021] Ouster Inc.  Ouster OS1 Hardware Specification Sheet.  2021\.  URL https://data.ouster.io/downloads/datasheets/datasheet-revd-v2p0-os1.pdf.
  * Isler et al. [2016] Stefan Isler, Reza Sabzevari, Jeffrey Delmerico, and Davide Scaramuzza.  An information gain formulation for active volumetric 3D reconstruction.  In _2016 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 3477–3484. IEEE, 2016.
  * Kittenplon et al. [2021] Yair Kittenplon, Yonina C Eldar, and Dan Raviv.  Flowstep3d: Model unrolling for self-supervised scene flow estimation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 4114–4123, 2021.
  * Klasing et al. [2008] Klaas Klasing, Dirk Wollherr, and Martin Buss.  A clustering method for efficient segmentation of 3D laser data.  In _2008 IEEE international conference on robotics and automation_ , pages 4043–4048. IEEE, 2008.
  * Kriegel et al. [2015] Simon Kriegel, Christian Rink, Tim Bodenmüller, and Michael Suppa.  Efficient next-best-scan planning for autonomous 3D surface reconstruction of unknown objects.  _Journal of Real-Time Image Processing_ , 10(4):611–631, 2015.
  * Li et al. [2021] Ruibo Li, Guosheng Lin, and Lihua Xie.  Self-point-flow: Self-supervised scene flow estimation from point clouds with optimal transport and random walk.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 15577–15586, 2021.
  * Liu et al. [2019] Xingyu Liu, Charles R Qi, and Leonidas J Guibas.  Flownet3D: Learning scene flow in 3D point clouds.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 529–537, 2019.
  * Mahjourian et al. [2022] Reza Mahjourian, Jinkyu Kim, Yuning Chai, Mingxing Tan, Ben Sapp, and Dragomir Anguelov.  Occupancy flow fields for motion forecasting in autonomous driving.  _IEEE Robotics and Automation Letters_ , 7(2):5639–5646, 2022.
  * Makadia et al. [2006] Ameesh Makadia, Alexander Patterson, and Kostas Daniilidis.  Fully automatic registration of 3D point clouds.  In _2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’06)_ , volume 1, pages 1297–1304. IEEE, 2006.
  * Meyer-Delius et al. [2012] Daniel Meyer-Delius, Maximilian Beinhofer, and Wolfram Burgard.  Occupancy grid models for robot mapping in changing environments.  In _Twenty-Sixth AAAI Conference on Artificial Intelligence_ , 2012\.
  * Mildenhall et al. [2020] Ben Mildenhall, Pratul P Srinivasan, Matthew Tancik, Jonathan T Barron, Ravi Ramamoorthi, and Ren Ng.  NeRF: Representing scenes as neural radiance fields for view synthesis.  In _European conference on computer vision_ , pages 405–421. Springer, 2020.
  * Mittal et al. [2020] Himangi Mittal, Brian Okorn, and David Held.  Just go with the flow: Self-supervised scene flow estimation.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 11177–11185, 2020.
  * Moir and Grimble [1984] T Moir and M Grimble.  Optimal self-tuning filtering, prediction, and smoothing for discrete multivariable processes.  _IEEE Transactions on Automatic control_ , 29(2):128–137, 1984.
  * Oshman and Shaviv [2000] Yaakov Oshman and Ilan Shaviv.  Optimal tuning of a Kalman filter using genetic algorithms.  In _AIAA Guidance, Navigation, and Control Conference and Exhibit_ , page 4558, 2000.
  * Powell [2002] Thomas D Powell.  Automated tuning of an extended Kalman filter using the downhill simplex algorithm.  _Journal of Guidance, Control, and Dynamics_ , 25(5):901–908, 2002.
  * Raaj et al. [2021] Yaadhav Raaj, Siddharth Ancha, Robert Tamburo, David Held, and Srinivasa Narasimhan.  Exploiting and Refining Depth Distributions with Triangulation Light Curtains.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021.
  * Rusu et al. [2009] Radu Bogdan Rusu, Nico Blodow, and Michael Beetz.  Fast point feature histograms (FPFH) for 3D registration.  In _2009 IEEE international conference on robotics and automation_ , pages 3212–3217. IEEE, 2009.
  * Scott et al. [2003] William R Scott, Gerhard Roth, and Jean-François Rivest.  View planning for automated three-dimensional object reconstruction and inspection.  _ACM Computing Surveys (CSUR)_ , 35(1):64–96, 2003.
  * Sutton and Barto [2018] Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Tatarchenko et al. [2017] Maxim Tatarchenko, Alexey Dosovitskiy, and Thomas Brox.  Octree generating networks: Efficient convolutional architectures for high-resolution 3D outputs.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2088–2096, 2017.
  * Teed and Deng [2021] Zachary Teed and Jia Deng.  RAFT-3D: Scene flow using rigid-motion embeddings.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 8375–8384, 2021.
  * Teichman et al. [2011] Alex Teichman, Jesse Levinson, and Sebastian Thrun.  Towards 3D object recognition via classification of arbitrary object tracks.  In _2011 IEEE International Conference on Robotics and Automation_ , pages 4034–4041. IEEE, 2011.
  * Thrun [2002] Sebastian Thrun.  Probabilistic robotics.  _Communications of the ACM_ , 45(3):52–57, 2002\.
  * Tulsiani et al. [2017] Shubham Tulsiani, Tinghui Zhou, Alexei A Efros, and Jitendra Malik.  Multi-view supervision for single-view reconstruction via differentiable ray consistency.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 2626–2634, 2017.
  * Vasquez-Gomez et al. [2014] J Irving Vasquez-Gomez, L Enrique Sucar, Rafael Murrieta-Cid, and Efrain Lopez-Damian.  Volumetric next-best-view planning for 3D object reconstruction with positioning error.  _International Journal of Advanced Robotic Systems_ , 11(10):159, 2014.
  * Vedula et al. [1999] Sundar Vedula, Simon Baker, Peter Rander, Robert Collins, and Takeo Kanade.  Three-dimensional scene flow.  In _Proceedings of the Seventh IEEE International Conference on Computer Vision_ , volume 2, pages 722–729. IEEE, 1999.
  * Wang et al. [2018a] Jian Wang, Joseph Bartels, William Whittaker, Aswin C Sankaranarayanan, and Srinivasa G Narasimhan.  Programmable triangulation light curtains.  In _Proceedings of the European Conference on Computer Vision (ECCV)_ , pages 19–34, 2018a.
  * Wang et al. [2018b] Shenlong Wang, Simon Suo, Wei-Chiu Ma, Andrei Pokrovsky, and Raquel Urtasun.  Deep parametric continuous convolutional neural networks.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 2589–2597, 2018b.
  * Wang and Solomon [2019a] Yue Wang and Justin M. Solomon.  Deep closest point: Learning representations for point cloud registration.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pages 3523–3532, 2019a.
  * Wang and Solomon [2019b] Yue Wang and Justin M. Solomon.  PRNet: Self-supervised learning for partial-to-partial registration.  _Advances in neural information processing systems_ , 32, 2019b.
  * Wikipedia contributors [2022a] Wikipedia contributors.  HSL and HSV — Wikipedia, The Free Encyclopedia, 2022a.  [Online; accessed 30-November-2022].
  * Wikipedia contributors [2022b] Wikipedia contributors.  F-score — Wikipedia, The Free Encyclopedia, 2022b.  [Online; accessed 05-December-2022].
  * Wu et al. [2020] Wenxuan Wu, Zhi Yuan Wang, Zhuwen Li, Wei Liu, and Li Fuxin.  PointPWC-Net: Cost Volume on Point Clouds for (Self-) Supervised Scene Flow Estimation.  In _European Conference on Computer Vision_ , pages 88–107. Springer, 2020.
  * Wu et al. [2015] Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao.  3D shapenets: A deep representation for volumetric shapes.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 1912–1920, 2015.
  * Yang et al. [2020] Heng Yang, Jingnan Shi, and Luca Carlone.  TEASER: Fast and certifiable point cloud registration.  _IEEE Transactions on Robotics_ , 37(2):314–333, 2020.
  * Zhao et al. [2022] Yiming Zhao, Xiao Zhang, and Xinming Huang.  A divide-and-merge point cloud clustering algorithm for LiDAR panoptic segmentation.  In _2022 International Conference on Robotics and Automation (ICRA)_ , pages 7029–7035. IEEE, 2022.
  * Zhou et al. [2016] Qian-Yi Zhou, Jaesik Park, and Vladlen Koltun.  Fast global registration.  In _European conference on computer vision_ , pages 766–782. Springer, 2016.
  * Zi-Li and Chun-Bo [2007] Deng Zi-Li and Li Chun-Bo.  Self-tuning information fusion Kalman predictor weighted by diagonal matrices and its convergence analysis.  _Acta Automatica Sinica_ , 33(2):156–163, 2007\.

Appendix
Active Velocity Estimation using Light Curtains
via Self-Supervised Multi-Armed Bandits

##  Appendix A Derivation of recursive Bayesian estimation

The goal is to infer at each timestep $t$ a distribution
$bel(x_{t})=P(x_{t}\mid u_{1:t},z_{1:t})$ over the current state $x_{t}$ from
the sequence of sensor observations $z_{1:t}$ and the known sequence of
actions $u_{1:t}$. $bel(x_{t})$ is computed using recursive Bayesian
estimation [65]. Combining the definition of $bel(x_{t})$ and the Markov
property of the dynamic Bayes network, we can derive the following recursive
relationship [65]:

$\displaystyle bel(x_{t})=P(x_{t}\mid u_{1:t},z_{1:t})$ $\displaystyle\hskip
20.00003pt\propto P(x_{t},z_{t}\mid u_{1:t},z_{1:{t-1}})$ $\displaystyle\hskip
20.00003pt=P(z_{t}\mid x_{t},u_{1:t},z_{1:{t-1}})\leavevmode\nobreak\
P(x_{t}\mid u_{1:t},z_{1:{t-1}})$ $\displaystyle\hskip 20.00003pt=P(z_{t}\mid
x_{t},u_{t})\leavevmode\nobreak\ P(x_{t}\mid u_{1:{t-1}},z_{1:{t-1}})$
$\displaystyle\hskip 20.00003pt=P(z_{t}\mid x_{t},u_{t})\leavevmode\nobreak\
\int_{x_{t-1}}P(x_{t-1},x_{t}\mid u_{1:{t-1}},z_{1:{t-1}})\leavevmode\nobreak\
\mathrm{d}x_{t-1}$ $\displaystyle\hskip 20.00003pt=P(z_{t}\mid
x_{t},u_{t})\leavevmode\nobreak\ \int_{x_{t-1}}P(x_{t-1}\mid
u_{1:{t-1}},z_{1:{t-1}})$ $\displaystyle\hskip 20.00003pt\phantom{=P(z_{t}\mid
x_{t},u_{t})\leavevmode\nobreak\ \int_{x_{t-1}}}\cdot P(x_{t}\mid
x_{t-1},u_{1:{t-1}},z_{1:{t-1}})\leavevmode\nobreak\ \mathrm{d}x_{t-1}$
$\displaystyle\hskip 20.00003pt=P(z_{t}\mid x_{t},u_{t})\leavevmode\nobreak\
\int_{x_{t-1}}\underbrace{P(x_{t-1}\mid
u_{1:{t-1}},z_{1:{t-1}})}_{bel(x_{t-1})}$ $\displaystyle\hskip
20.00003pt\phantom{=P(z_{t}\mid x_{t},u_{t})\leavevmode\nobreak\
\int_{x_{t-1}}}\cdot P(x_{t}\mid x_{t-1})\leavevmode\nobreak\
\mathrm{d}x_{t-1}$ $\displaystyle\hskip 20.00003pt=P(z_{t}\mid
x_{t},u_{t})\leavevmode\nobreak\
\int_{x_{t-1}}bel(x_{t-1})\leavevmode\nobreak\ P(x_{t}\mid
x_{t-1})\leavevmode\nobreak\ \mathrm{d}x_{t-1}$ $\displaystyle\hskip
20.00003pt=P(z_{t}\mid x_{t},u_{t})\leavevmode\nobreak\
\overline{bel}(x_{t})\text{\
\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(Measurement
update)}\text{,\ where}$
$\displaystyle\overline{bel}(x_{t})=\int_{x_{t-1}}bel(x_{t-1})\leavevmode\nobreak\
P(x_{t}\mid x_{t-1})\leavevmode\nobreak\ \mathrm{d}x_{t-1}\text{\
\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}(Motion
update)}$

Based on the above recursive equations, recursive Bayesian estimation
alternates between the following two steps:

  1. 1.

Motion update step: This step accounts for the dynamics of the environment. It
first computes an intermediate quantity defined above:
$\overline{bel}(x_{t})=\int_{x_{t-1}}bel(x_{t-1})\leavevmode\nobreak\
P(x_{t}\mid x_{t-1})\leavevmode\nobreak\ \mathrm{d}x_{t-1}$. This is the
result of “applying” a known or assumed motion model $P(x_{t}\mid x_{t-1})$ to
the previous belief $bel(x_{t-1})$. In dynamic occupancy grids, this step
accounts for the motion of scene points based on their current 2D velocities.
The occupancies and velocities of the next timestep are computed based on the
occupancies and velocities in the previous timestep. We use a constant
velocity motion model with Gaussian noise in both velocity and position. When
the motion model is applied to Fig. 7a, it is updated to Fig. 7b (illustration
only). This correction step usually increases the uncertainty in occupancies
and velocities.

  2. 2.

Measurement update step: This step incorporates measurements from a sensor. It
updates the prior belief $\overline{bel}(x_{t})$ to $bel(x_{t})\propto
P(z_{t}\mid x_{t},u_{t})\leavevmode\nobreak\ \overline{bel}(x_{t})$ by
weighting $\overline{bel}(x_{t})$ by the likelihood of the observed
measurements $P(z_{t}\mid x_{t},u_{t})$. This step usually reduces uncertainty
in the state. In dynamic occupancy grids, occupancies are updated using the
measurements from the light curtain. Since light curtains (or any depth
sensor) only measure the locations of objects, this step does not update
velocities. The velocity estimates are automatically refined in subsequent
motion update steps. The measurement update reduced the probability of one of
the positions of an object in Fig. 7b to Fig. 7c (illustration only).

##  Appendix B Dynamic occupancy grids

(a) Dynamic occupancy grid before the motion update step.

(b) After the motion update step.

(c) After the measurement update step.

Figure 7: Dynamic occupancy grid. Grid structure: The 2D grid represents the
top-down view and is made up of cells. Like conventional static occupancy
grids [29, 65], each cell contains an occupancy probability $p\in[0,1]$. Dark
indicates low occupancy probability and bright indicates high occupancy
probability. In addition, each cell also contains a set of weighted particles
where each particles stores a single 2D velocity. The set of particles
together represents a probability distribution of that cell’s velocity. Grid
updates: The grid is a Bayes filter [65] that consists of two steps: the
motion update step and the measurement update step. (a) The grid before
performing any update. (b) Motion update step: the occupancies and velocities
of the next timestep are computed based on the grid in the previous timestep,
increasing uncertainty. (c) Measurement update step: the occupancies are
updated using the measurements from the light curtain, decreasing uncertainty.
This will refine the velocity estimates.

The dynamic occupancy grid, like conventional occupancy grids [29, 65], is an
instance of Bayes filters. Occupancy grids [29, 65] are a standard tool in
robotics for mapping the location of static objects in the environment. 2D
occupancy grids that map objects from the top-down view are commonly used for
mapping and SLAM in robot navigation. Each cell in the grid contains an
occupancy probability $p\in[0,1]$, denoting the probability of the cell being
occupied by an object. Dynamic occupancy grids [23] are an extension of
classical occupancy grids (see Figure 7a). Each cell in the grid contains both
(1) the occupany probability $p\in[0,1]$, as well as (2) a probability
distribution over 2D velocities. The velocity distribution is represented by a
set of weighted particles, where each particles stores a single 2D velocity.
The set of weighted particles approximates the true velocity distribution.

###  B-A Mathematical framework

Our method is built upon dynamic occupancy grids introduced by Danescu. et.
al. [23]. The authors describe particles as both representing a velocity
distribution (i.e. weighted velocity hypotheses), as well as being “physical
building blocks of the world”. The former interpretation suggests that
particles together represent the probability distribution of the velocity of a
single physical scene point, whereas the latter suggests that each particle
corresponds to its own scene point. Furthermore, the particles not only
represent velocities, but their count represents the probability of occupancy.
While the method is shown to be very promising, the precise role of particles
and what they represent remains unclear. In this work, we re-derive dynamic
occupancy grids using a more rigorous mathematical analysis. We explicitly
state the assumptions made and provide a precise interpretation of particles.
Our framework can be derived from three reasonably mild assumptions:

Assumption 1: There are no collisions Each cell can be occupied by at most one
physical scene point with a single velocity. Cells are sufficiently small that
multiple objects with different velocities cannot exist (“collide”) within a
cell.

This assumption is required for a single velocity of a cell to be well-
defined. Assumption 1 paves the way for a straightforward interpretation
particles: all particles belonging to a cell represent a probability
distribution over the single velocity of that cell. Assumption 1 allows us to
define the state space of occupancies and velocities.

Representing the state space: Each cell is indexed by $i\in\mathcal{I}$ from
an index set $\mathcal{I}$ of all cell in the grid. At timestep $t$, the state
of the $i$-th cell is denoted by $x^{i}_{t}=(o^{i}_{t},v^{i}_{t})$. It
contains two variables. The first is a binary occupancy variable
$o^{i}_{t}\in\\{0,1\\}$ which denotes whether the cell is occupied or not. The
second is a 2D velocity variable $v^{i}_{t}\in\mathbb{R}^{2}$ representing the
continuous velocity of the cell (if it is occupied) from the top-down view.
The overall state of the dynamic occupancy grid $x_{t}$ is a concantenation of
the states of all cells in the grid, i.e.
$x_{t}=\\{x^{i}_{t}=(o^{i}_{t},v^{i}_{t})\mid i\in\mathcal{I}\\}$. Note that
the variable $v^{i}_{t}$ is “conditional”: it is only defined when the cell is
occpied i.e. $o^{i}_{t}=1$.

Assumption 2: Constant velocity motion model Each scene point moves with a
constant velocity, with added Gaussian noise.

Any motion can be approximated by a constant velocity motion model as long as
the time interval is sufficiently small. Therefore, this assumption is
reasonable in our setting since light curtains operate at very high speeds
(45-60 Hz). Note that although we use the constant velocity motion model in
this work following [23], the dynamic occupancy grid framework can still be
used by swapping it with any other motion model of choice.

Let $\epsilon^{i}_{t}\sim\mathcal{N}(0,R_{\epsilon})$ and
$\delta^{i}_{t}\sim\mathcal{N}(0,R_{\delta})$ be the Gaussian noise in
velocity and position respectively for the $i$-th cell in the grid at time
$t$. And let $\mathrm{pos}^{i}$ denote the 2D location of the center of the
$i$-th cell. The constant velocity motion model can be expressed
mathematically as

$\displaystyle o^{j}_{t+1},v^{j}_{t+1}=\begin{cases}1,\
v^{i}_{t}+\epsilon^{i}_{t}\ \ \ \mathrm{if\ }\exists i\in\mathcal{I}\text{
such that }o^{i}_{t}=1\text{ and}\\\ \phantom{1,\ v^{i}_{t}+\epsilon^{i}_{t}\
\ \ \mathrm{if\ }\exists
i}\mathrm{pos}^{j}\approx\mathrm{pos}^{i}+v^{i}_{t}\leavevmode\nobreak\ \Delta
t+\delta^{i}_{t}\\\ 0\phantom{,\ v^{i}_{t}+\epsilon^{i}_{t}\ \ \
}\text{otherwise}\end{cases}$ (3)

In other words, a cell $j$ will be occupied in the next timestep if and only
if there exists another cell $i$ in the previous timestep which moves to $j$
under the constant velocity motion model. In that case, the velocity of cell
$j$ will be equal to that of cell $i$ modulo the Gaussian noise. The equality
is approximate taking into account the finite size of the cell.

Representing the belief distribution: A dynamic occupancy grid represent the
current belief over velocities and occupancies of the environment. It is a
probability distribution over states $x_{t}$ described above. The state space
is extremely large. Dynamic occupancy grids represent the belief compactly by
making the following assumption:

Assumption 3: Cells are mutually independent The probability distributions of
all cells are mutually independent. This is a standard assumption made for
occupancy grids for computational tractability.

Each cell contains two distributions:

  * •

Occupancy distribution ($\omega^{i}_{t}$): $o^{i}_{t}$ is a Bernoulli random
variable over $\\{0,1\\}$ with probability $\omega^{i}_{t}\in[0,1]$.

  * •

Velocity distribution ($V^{i}_{t}$): $v^{i}_{t}$ is a random variable over
$\mathbb{R}^{2}$. It is represented by a set of $M$ weighted particles
$V^{i}_{t}=\\{(v^{i,m}_{t},p^{i,m}_{t})\mid 1\leq m\leq M\\}$. The $m$-th
particle has a velocity $v^{i,m}_{t}$ and weight $p^{i,m}_{t}$ that add up to
1 i.e. $\sum_{m=1}^{M}p^{i,m}_{t}=1$. The larger the number of particles used,
the better is the particle approximation to the true continuous velocity
distribution.

The velocity distribution acts like a “conditional” distribution. The
probability that cell $i$ is occupied with velocity $v^{i,m}_{t}$ is the
product $\omega^{i}_{t}\leavevmode\nobreak\ p^{i,m}_{t}$ of the probability of
being occupied ($\omega^{i}_{t}$) and the probability of having the velocity
$v^{i,m}_{t}$ given that it is occupied ($p^{i,m}_{t}$). The probability of
being unoccupied is simply $1-\omega^{i}_{t}$. Since cells are assumed to be
mutually independent, the probability of the entire grid is the product of
probabilities of individual cells in the grid.

###  B-B Motion update step

Figure 8: Applying the motion model to update occupancies and velocities of
cells in the motion update step. $\omega$’s are occupancy probabilities of
cells, $v$’s and $p$’s are velocities and weights of the individual particles
respectively.

We will now derive the motion update equations of the dynamic probability
grid. These equations govern how particles will move across the grid and be
reweighted. Consider a simplified grid shown in Fig. 8a. Assume that there are
only three cells in the grid, and only cells 1 and 2 are occupied at time $t$.
The occupancy and velocity distributions are illustrated in the figure, and
particles $(v^{1,m_{1}}_{t},p^{1,m_{1}}_{t})$ from cell 1 and
$(v^{2,m_{2}}_{t},p^{2,m_{2}}_{t})$ from cells 2 move to cell 3 in the next
timestep $t+1$ (assuming that noise has been incorporated in
$v^{1,m_{1}}_{t},v^{2,m_{2}}_{t}$). What should be the occupancy and velocity
distribution of cell 3?

Let $E_{1}$ be the event that the particle from cell 1 enters cell 3.
Similarly, let $E_{2}$ be the event that the particle from cell 2 enters cell
3. We have that $P(E_{1})=\omega^{1}_{t}\leavevmode\nobreak\ p^{1,m_{1}}_{t}$
and $P(E_{2})=\omega^{2}_{t}\leavevmode\nobreak\ p^{2,m_{2}}_{t}$. Cell 3 will
be occupied when either $E_{1}$ or $E_{2}$ happens (from Eqn. 3). Its
occupancy probability after the motion update is
$\overline{\omega}^{3}_{t+1}=P(E_{1}\cup E_{2})$. Now, from assumption 1 (the
no collision assumption), objects of different velocities cannot occupy the
same cell. Therefore events $E_{1}$ and $E_{2}$ must be disjoint. From the law
of total probability, if $E_{1}$ and $E_{2}$ are disjoint, then $P(E_{1}\cup
E_{2})=P(E_{1})+P(E_{2})$. Therefore, the occupancy probability of cell 3
after the motion update
$\overline{\omega}^{3}_{t+1}=\omega^{1}_{t}\leavevmode\nobreak\
p^{1,m_{1}}_{t}+\omega^{2}_{t}\leavevmode\nobreak\ p^{2,m_{2}}_{t}$. The
conditional velocity distribution of cell 3 will comprise of $v^{1,m_{1}}_{t}$
and $v^{2,m_{2}}_{t}$, with weights proportional to $P(E_{1})$ and $P(E_{2})$
respectively. This leads us to the general motion update of dynamic occupancy
grids:

Motion update step for dynamic occupancy grids (4)
$\displaystyle\overline{\omega}^{j}_{t+1}$
$\displaystyle=\sum_{i\in\mathcal{I}}\omega^{i}_{t}\sum_{m=1}^{M_{i}}p^{i,m}_{t}\leavevmode\nobreak\
\mathbb{I}\big{[}\mathrm{pos}^{j}\approx\mathrm{pos}^{i}+v^{i,m}_{t}\leavevmode\nobreak\
\Delta t+\delta^{i,m}_{t}\big{]}$ $\displaystyle\overline{V}^{j}_{t+1}$
$\displaystyle=\Big{\\{}\big{(}v^{i,m}_{t}+\epsilon^{i,m}_{t},\frac{\omega^{i}_{t}\leavevmode\nobreak\
p^{i,m}_{t}}{\overline{\omega}^{j}_{t+1}}\big{)}\leavevmode\nobreak\
\Big{|}\leavevmode\nobreak\
i,m:\mathrm{pos}^{j}\approx\mathrm{pos}^{i}+v^{i,m}_{t}\leavevmode\nobreak\
\Delta t+\delta^{i,m}_{t}\Big{\\}}$

Note that the above derivation does not require assumption 3; the law of total
probability applies even when the distributions of incoming cells are not
independent! Therefore, the motion update is exact even if we treat
$\omega^{i}_{t}$ and $V^{i}_{t}$ as marginal distributions of potentially
correlated cells. Assumption 3 is however required for the measurement update
step (see App. B-C).

When adding the $\omega^{i}_{t}\leavevmode\nobreak\ p^{i,m}_{t}$ terms from
incoming particles to compute $\overline{\omega}^{j}_{t+1}$, the sum should
not exceed 1 under the no collision assumption (assumption 1). However, in
practice, this may be violated. In such cases, we truncate the occupancy
probability to 1 following [23]. However, this happens rarely; we needed to
perform truncation only 0.35% times on average.

###  B-C Measurement update step

Sensors such as light curtains and LiDARs provide depth information, from
which the current occupancy of cells can be inferred. We use a post-processing
algorithm described in [42] to process sensor data and output a detection
variable $z^{i}_{t}\in\\{\texttt{OCCUPIED},\texttt{FREE},\texttt{UNKNOWN}\\}$
for each cell $i$ in the grid. $z^{i}_{t}$ indicates the presence, absence or
lack of knowledge about objects inside cell $i$.

For LiDAR scans, Hu et al. [42] marks each cell that contains LiDAR points as
OCCUPIED. Then, it uses the fact that if a 3D point was detected, light must
have traveled between the sensor and the detected point in a straight line
without obstruction. Therefore, rays are cast starting from the sensor to the
OCCUPIED cells using an efficient voxel traversal algorithm [3]. Cells lying
along these rays are marked FREE. Any cells that remain unclassified are
marked as UNKNOWN. This method exploits visibility constraints of light to
extract the maximum possible information from a 3D scan. We use the same
processing method customized for light curtains. When a light curtain is
placed on a set of cells in the grid, the cells are classified as OCCUPIED or
FREE based on whether points were detected inside the cell. Raycasting to
occupied cells is also performed to discover additional FREE cells. Figure 2b
visualizes an example of visibility classification. Cells detected as OCCUPIED
are shown in red. Cells shown in blue are inferred as FREE because they either
lie undetected on the curtain or lie on rays cast to red cells. UNKNOWN cells
are shown in gray.

The measurement update step takes the visibility classification as input. Our
observation model treats this classification as a noisy observation of true
occupancy. We do not update the occupancy of UNKNOWN cells. For known cells,
we assume a false positive rate $\alpha_{\mathrm{fp}}\in[0,1]$ and a false
negative rate $\alpha_{\mathrm{fn}}\in[0,1]$. The observation model is:

$\displaystyle P(z^{i}_{t}=\texttt{OCCUPIED}\mid o^{i}_{t}=1)$
$\displaystyle=1-\alpha_{\mathrm{fn}}$ $\displaystyle
P(z^{i}_{t}=\texttt{FREE}\mid o^{i}_{t}=1)$
$\displaystyle=\alpha_{\mathrm{fn}}$ $\displaystyle
P(z^{i}_{t}=\texttt{OCCUPIED}\mid o^{i}_{t}=0)$
$\displaystyle=\alpha_{\mathrm{fp}}$ $\displaystyle
P(z^{i}_{t}=\texttt{FREE}\mid o^{i}_{t}=0)$
$\displaystyle=1-\alpha_{\mathrm{fp}}$

We first use the assumption that all cells are mutually independent
(assumption 3) to write the belief of the overall grid
$\overline{bel}(x_{t})=\prod_{i\in\mathcal{I}}\overline{bel}(x^{i}_{t})$ as a
product of belief distributions of each cell in the grid. Since the likelihood
function $P(z_{t}\mid x_{t})=\prod_{i\in\mathcal{I}}P(z^{i}_{t}\mid
o^{i}_{t})$ is also independent for each cell, the updated posterior belief
$bel(x_{t}\mid z_{t})\propto\overline{bel}(x_{t})\leavevmode\nobreak\
P(z_{t}\mid x_{t})$ can be computed independently for each cell. Given the
prior occupancy distribution $\overline{\omega^{i}_{t}}$ and an observation
$z^{i}_{t}$ for cell $i$, its occupancy distribution after the measurement
update can be computed using the Bayes rule:

Measurement update step for dynamic occupancy grids (5)
$\displaystyle\omega^{i}_{t}=\frac{\overline{\omega^{i}_{t}}\leavevmode\nobreak\
P(z^{i}_{t}\mid o^{i}_{t}=1)}{\overline{\omega^{i}_{t}}\leavevmode\nobreak\
P(z^{i}_{t}\mid o^{i}_{t}=1)+(1-\overline{\omega^{i}_{t}})\leavevmode\nobreak\
P(z^{i}_{t}\mid o^{i}_{t}=0)}$

Depth sensors only provide information about the occupancy of cells; they do
not directly measure object velocities. Velocities are inferred indirectly by
a combination of measurement- and motion- update steps. The measurement update
incorporates information about occupancy and the motion update infers
velocities that are consistent with occupancy across timesteps in a principled
probabilistic manner. Therefore, our method estimates velocities from depth
measurements without requiring explicit data association across frames!

##  Appendix C Computing depth probabilities using raymarching

The depth probability of a cell in the grid is the probability that the depth
of the scene along the cell’s direction is the cell’s location. In other
words, it is the probability that a visible surface exists in the cell i.e.
the cell is occupied and all other occluding cells are empty. Once we compute
the depth probability of each cell in the grid, we can place a curtain that
lies on the cells with the highest depth probability.

How do we compute the depth probability in a probabilistic occupancy grid? We
borrow the idea of “ray marching” from the literature on volumetric rendering
[66, 53]. In order to reconstruct the implicit depth surface from a
probabilistic volume, ray marching travels along a ray originating from the
sensor and computes the probability of visibility and occlusion at each point.
Tulsiani et al. [66] performs this for discretized 3D grids (similar to our
case) whereas NeRFs [53] perform this in a continuous space using neural
radiance fields. Consider an example of raymarching in Fig. 2c. Let the
sequence of cells on a ray be indexed as $1,2,\dots,n,\dots N$. Recall from
App. B that $\omega^{i}_{t}$ is the occupancy probability of the $i$-th cell
at timestep $t$. The depth probability of the $n$-th cell
$P^{\mathrm{D}}_{t}(n)=\omega^{n}_{t}\leavevmode\nobreak\
\prod_{i=1}^{n-1}(1-\omega^{i}_{t})$ is product of the probabilities that the
$n$-th cell is occupied ($\omega^{n}_{t}$) and the probabilities that each
$i$-th cell on the ray before the $n$-th cell is unoccupied
($1-\omega^{i}_{t}$) so that light can reach the $n$-th cell unoccluded. Let
us define the “visibility” probability
$P^{\mathrm{V}}_{t}(n)=\prod_{i=1}^{n}(1-\omega^{i}_{t})$ that all cells are
visible upto the $n$-th cell. Then, we have the following recursive equations:

$\displaystyle P^{\mathrm{V}}_{t}(i)$
$\displaystyle=P^{\mathrm{V}}_{t}(i-1)\leavevmode\nobreak\ (1-\omega^{i}_{t})$
$\displaystyle P^{\mathrm{D}}_{t}(i)$
$\displaystyle=P^{\mathrm{V}}_{t}(i-1)\leavevmode\nobreak\ \omega^{i}_{t}$

These recursive equations can be used to compute the depth probability of each
cell along a ray efficiently in time $O(N)$ linear in the number of cells on
that ray. This strategy is implemented as follows. For each camera ray, we
perform the ray-marching procedure and compute the depth probability of each
cell along that ray. Then, for each camera ray, we place the curtain at the
cell with the maximum depth probability.

##  Appendix D Maximizing information gain

Consider the dynamic Bayes network shown in Fig. 1b. Given a forecasted prior
belief $P(x_{t})=\overline{bel}(x_{t})$, the information gain framework
prescribes that the action $u_{t}$ should be taken that maximizes the
information gain $\mathrm{IG}(x_{t},z_{t}\mid u_{t})$ between the state
$x_{t}$ and the observations $z_{t}$ when taking an action $u_{t}$.
Information gain is a well-studied quantity in information theory and is
usually defined as:

$\mathrm{IG}(x_{t},z_{t}\mid
u_{t})=\underbrace{\mathrm{H}(P(x_{t}))\vphantom{\big{[}\big{]}}}_{\text{entropy
of $x_{t}$}}-\underbrace{\mathbb{E}_{z_{t}\mid
u_{t}}\big{[}\mathrm{H}(P(x_{t}\mid z_{t},u_{t}))\big{]}}_{\text{conditional
entropy of $x_{t}\mid z_{t}$ under $u_{t}$}}$ (6)

The information gain is the expected reduction in entropy (i.e. uncertainty)
in $x_{t}$ before and after taking the action $u_{t}$. Ancha et al. [4] showed
that under certain assumptions, the information gain of conventional occupancy
grids on placing light curtains is equal to the sum of binary entropies of the
occupancy probabilities of the cells that the curtain lies on.

While information gain for conventional occupancy grids is straightforward to
derive, it is not so for the case of dynamic occupancy grids. This is because
the underlying state space of dynamic occupancy grids is a ‘mixture’ of
discrete and continuous spaces. Consider the state $x^{i}_{t}$ of the $i$-th
cell in the grid. The space of the state $x^{i}_{t}$ is:

$x^{i}_{t}\in\underbrace{\\{\mathrm{unoccupied}\\}}_{\text{discrete
space}}\leavevmode\nobreak\ \cup\leavevmode\nobreak\
\underbrace{\\{\mathrm{occupied\ with\ }v^{i}_{t}\mid
v^{i}_{t}\in\mathbb{R}^{2}\\}}_{\text{continuous space}}$

The cell can either be unoccupied, or be occupied with a continuous velocity.
Unfortunately, the entropy of such mixed discrete-continuous spaces is not
well-defined [31]. Therefore the “2H-estimator” in Eqn. 6 (named so because it
contains two entropy terms) cannot be used to calculate information gain since
the individual terms on the right hand side are not well-defined.

Fortunately, information gain (unlike entropy) is well-defined for most
distributions, including discrete-continuous mixtures [31]. This is possible
by using a more general definition of information gain given by the
“Radon–Nikodym” derivative [31]:

$\mathrm{IG}(x_{t},z_{t}\mid
u_{t})=\int_{x_{t},z_{t}}\underbrace{\log\frac{dP_{x,z}}{dP_{x}P_{z}}}_{\text{Radon–Nikodym
derivative}}dP_{x,z}$ (7)

The Radon–Nikodym is well-defined for discrete-continuous mixtures [31]. When
the individual entropy terms of Eqn. 6 (the 2H-estimator) are well-defined,
the more general definition of Eqn. 7 reduces to Eqn. 6. In other words, the
two definitions are consistent.

We will now derive the information gain of dynamic occupancy grids using the
more general Radon–Nikodym definition. Here, we derive the information gain of
a single $i$-th cell. Let $\omega$ be the occupancy probability of the cell.
Let the continuous velocity distribution of the cell be denoted by $P(v)$.
Assume that we place a curtain on this cell, and we obtain an observation
$z^{i}_{t}\in\\{0,1\\}$ to be a noisy measurement of the cell’s occupancy.
This is assuming that we are using a depth sensor that can only partially
observe occupancy but cannot directly observe velocities. Let
$\alpha_{\mathrm{fp}}$ and $\alpha_{\mathrm{fn}}$ be the false-positive and
false-negative rates of the sensor respectively. Then,

$\displaystyle\mathrm{IG}(x^{i}_{t}\mid z^{i}_{t})$
$\displaystyle=\int_{x,z}dP_{x,z}\leavevmode\nobreak\
\log\frac{dP_{x,z}}{dP_{x}P_{z}}\text{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\
\ (Radon-Nikodym formulation)}$
$\displaystyle=\underbrace{(1-\omega)(1-\alpha_{\mathrm{fp}})\log\frac{(1-\omega)(1-\alpha_{\mathrm{fp}})}{(1-\omega)P(z^{i}_{t}=0)}}_{\text{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}unoccupied
and undetected}}+$
$\displaystyle\phantom{==}\underbrace{(1-\omega)\leavevmode\nobreak\
\alpha_{\mathrm{fp}}\log\frac{(1-\omega)\leavevmode\nobreak\
\alpha_{\mathrm{fp}}}{(1-\omega)P(z^{i}_{t}=1)}}_{\text{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}unoccupied
and detected}}+$
$\displaystyle\phantom{==}\int_{v}\underbrace{\omega\leavevmode\nobreak\
P(v)dv\leavevmode\nobreak\
(1-\alpha_{\mathrm{fn}})\log\frac{\omega\leavevmode\nobreak\
P(v)dv\leavevmode\nobreak\
(1-\alpha_{\mathrm{fn}})}{\omega\leavevmode\nobreak\
P(v)dv\leavevmode\nobreak\
P(z^{i}_{t}=1)}}_{\text{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}velocity
v and detected}}+$
$\displaystyle\phantom{==}\int_{v}\underbrace{\omega\leavevmode\nobreak\
P(v)dv\leavevmode\nobreak\
\alpha_{\mathrm{fn}}\log\frac{\omega\leavevmode\nobreak\
P(v)dv\leavevmode\nobreak\ \alpha_{\mathrm{fn}}}{\omega\leavevmode\nobreak\
P(v)dv\leavevmode\nobreak\
P(z^{i}_{t}=0)}}_{\text{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}velocity
v and undetected}}$
$\displaystyle=(1-\omega)(1-\alpha_{\mathrm{fp}})\log\frac{(1-\alpha_{\mathrm{fp}})}{P(z^{i}_{t}=0)}+(1-\omega)\leavevmode\nobreak\
\alpha_{\mathrm{fp}}\log\frac{\alpha_{\mathrm{fp}}}{P(z^{i}_{t}=1)}$
$\displaystyle\phantom{=}+\omega\leavevmode\nobreak\
(1-\alpha_{\mathrm{fn}})\log\frac{(1-\alpha_{\mathrm{fn}})}{P(z^{i}_{t}=1)}+\omega\leavevmode\nobreak\
\alpha_{\mathrm{fn}}\log\frac{\alpha_{\mathrm{fn}}}{P(z^{i}_{t}=0)}$
$\displaystyle=-\big{[}(1-\omega)(1-\alpha_{\mathrm{fp}})+\omega\leavevmode\nobreak\
\alpha_{\mathrm{fn}}\big{]}\log P(z^{i}_{t}=0)$
$\displaystyle\phantom{==}-\big{[}(1-\omega)\leavevmode\nobreak\
\alpha_{\mathrm{fp}}+\omega(1-\alpha_{\mathrm{fn}})\big{]}\log P(z^{i}_{t}=1)$
$\displaystyle\phantom{==}-\omega\leavevmode\nobreak\
\mathrm{H}(\alpha_{\mathrm{fn}})-(1-\omega)\leavevmode\nobreak\
\mathrm{H}(\alpha_{\mathrm{fp}})$ $\displaystyle=-P(z^{i}_{t}=0)\log
P(z^{i}_{t}=0)-P(z^{i}_{t}=1)\log P(z^{i}_{t}=1)$
$\displaystyle\phantom{==}-\omega\leavevmode\nobreak\
\mathrm{H}(\alpha_{\mathrm{fn}})-(1-\omega)\leavevmode\nobreak\
\mathrm{H}(\alpha_{\mathrm{fp}})$
$\displaystyle=\mathrm{H}(z)-\omega\leavevmode\nobreak\
\mathrm{H}(\alpha_{\mathrm{fn}})-(1-\omega)\leavevmode\nobreak\
\mathrm{H}(\alpha_{\mathrm{fp}})$ $\displaystyle=\mathrm{H}(\omega){\text{\ \
\ \ (assuming that\ }\alpha_{\mathrm{fp}}=\alpha_{\mathrm{fn}}=0)}$

Assumption 1: We assume that the sensor is accurate (i.e. the false positive
rate $\alpha_{\mathrm{fp}}$ and the false negative rate $\alpha_{\mathrm{fn}}$
are both close to zero). Then, the information gain of a single cell due to
placing a light curtain on that cell is equal to its binary occupancy entropy
$\mathrm{H}_{\mathrm{occ}}(\omega)=-\omega\leavevmode\nobreak\
\log_{2}\omega-(1-\omega)\leavevmode\nobreak\ \log_{2}(1-\omega)$.

Assumption 2: We assume that all cells are independently distributed. Since
the information gain of independently distributed random variables is the sum
of information gain of individual variables [22], the total information gain
is the sum of binary cross entropies
$\mathrm{H}_{\mathrm{occ}}(\omega^{i}_{t})$ of the cells that the curtain lies
on. This is similar to the information gain in Ancha et al. [4]. However, we
have been able to prove this mathematically in the more complex case of mixed
discrete-continuous distributions.

This theoretical result is also intuitive – since the depth sensor
measurements only provide information about occupancy and not velocity, it is
not surprising that the information gain is equal to the total occupancy
uncertainty.

##  Appendix E Advantages of light curtains over conventional depth sensors

LiDARs have long range and high accuracy under strong ambient light. However,
compared to light curtains, they have poor vertical resolution ($\leq$128
rows), low frame rate (5-20Hz), and are very expensive ($>$$20K). Table III
compares LiDARs and light curtains.

LiDAR Light Curtains Resolution  128 rows 1280 rows Cost  $\sim$$20,000
$\sim$$1,000 Frame rate  10-20 Hz 45-60 Hz

Table III: Comparison between a modern Ouster OS1 [43] LiDAR, and Programmable
Light Curtains [9].

Passive RGBD sensors (stereo sensors that do not project light) have high
spatial and temporal resolution and are inexpensive. However, their accuracy
is poor in non-textured regions due to inaccuracies in stereo feature
matching.

Active RGBD sensors (like the Kinect sensor that projects light) inherit the
benefits of stereo sensors but also work in texture-less regions. However,
they have virtually no range outdoors.

Light curtains combine the best of these sensors. They have a long range
(nearly 35-50m) both outdoors and indoors, high spatial resolution (1280 rows)
and temporal resolution (45-60 Hz), work for textured and texture-less
regions, and are inexpensive ($<$1$K). These advantages have been demonstrated
in previous works on programmable light curtains [9, 58].

##  Appendix F Using an extra grid for thread-safety and efficiency

Our parallelized pipeline contains three threads: (1) light curtain sensing,
(2) Bayes filtering using dynamic occupancy grids, and (3) computing curtain
placements. How many grids are required to run these threads in parallel,
especially threads 2 and 3?

The motion update step (Eqns. 1, 4) moves particles across the grid according
to the motion model. The particles cannot be moved in place inside the same
grid since it may cause the same particle to be erroneously moved more than
once. Therefore, the motion update step requires two grids: a “source/current”
grid and a “destination/next” grid. Particles from the current grid are
copied, moved and placed in the next grid. After the motion update is
complete, the roles of the current and next grids are swapped. The next grid
is now assigned to be the new “current” grid since it is now the most up-to-
date, incorporating the latest measurements. In the next motion update step,
particles move from this grid to the older current grid (now taking the role
of the “next” grid).

The curtain computation thread also performs a motion update when it needs to
forecast the current grid to a future timestep (when the next curtain is
expected to be imaged). It uses the current grid of the Bayes filtering thread
as the source, but requires a third, ”forecasting” grid as a destination grid.

Although three grids are sufficient to implement parallelization, the pipeline
can be made more efficient. Specifically, consider the situation where two
motion updates take place simultaneously from “current” to “next” grids in the
Bayes filtering thread and “current” to ”forecasting” grid in the curtain
computation thread. Once the motion update in the Bayes filtering thread is
complete, it cannot immediately perform the next motion update step. It must
wait for the curtain computation thread to finish forecasting using the
“current” grid before the “current” and “next” grids can be swapped and the
next motion update dirties the “current” grid. If we use an additional “extra”
grid, the Bayes filtering thread can use this as the destination grid for its
next motion update step without needing to wait on the curtain computation
thread to finish the latter’s forecasting step.

Our parallelized pipeline tightly integrates the three inter-dependent
processes in a closed loop. We use a total of four grids to simultaneously
guarantee the following two properties: (1) grids in use are never mistakenly
overwritten, and (2) no thread ever needs to wait on another to finish
processing.

(a) HSV colorwheel used to visualize velocities.

(b) Colorwheel from the top-down view

(c) GT velocities of the simulated environment.

Figure 9: (a) The HSV (hue-saturation-value) colorwheel [73] used to visualize
2D velocities and occupancies. Value corresponds to the occupancy probability.
The hue corresponds to the direction of the velocity. Saturation corresponds
the magnitude of velocity. (b) The HSV colorwheel in the top-down view,
denoting the direction of velocity. (c) Ground truth velocities and
occupancies in the simulated environment. The grid shows a stationary wall to
the left and two objects. The bluish-purple square is moving upwards in 2D
(i.e. farther away from the sensor in 3D) whereas the other objects in white
are stationary.

##  Appendix G Evaluation Metrics

As mentioned in Sec. VIII-B, forecasted occupancy [50, 1] simultaneously
captures both the accuracy of occupancy estimates as well as velocity
estimates. This metric is especially pertinent for obstacle avoidance where
future occupancy of obstacles is needed to plan paths that avoid collisions.

We will use the notation for dynamic occupancy grids introduced in Sec. B-A.
The current dynamic occupancy grid at timestep $t$ is represented by
$G_{t}=\\{\omega^{i}_{t},V^{i}_{t}\mid i\in\mathcal{I}\\}$, where
$\omega^{i}_{t}$ is the Bernoulli occupancy probability of the $i$-th cell,
and $V^{i}_{t}=\\{(v^{i,m}_{t},p^{i,m}_{t})\mid 1\leq m\leq M\\}$ is the set
of $M$ weighted particles that represents the velocity distribution of the
$i$-th cell.

To evaluate $G_{t}$, we first apply the motion update step (Eqns. 1, 4) to
forecast it by a time $\Delta t$ and obtain the dynamic occupancy grid
$G_{t+\Delta t}$ at time $t+\Delta t$. Then, the forecasted occupancy
probabilities $\\{\omega^{i}_{t+\Delta t}\mid i\in\mathcal{I}\\}$ are
evaluated against the ground truth occupancies $\\{o^{i}_{t+\Delta t}\mid
i\in\mathcal{I}\\}$. We follow prior works [40, 52, 62] that treat the
evaluation of occupancy as a classification problem and compute binary
occupancies $\widetilde{o}^{\hskip 1.39998pti}_{t+\Delta
t}=\mathbb{I}(\omega^{i}_{t+\Delta t}\geq 0.5)$ thresholded at 0.5
probability.

We use the following metrics to evaluate the quality of predicted occupancy.
We ignore cells that are occluded (in the ground truth) since (1) they cannot
be observed by optical sensors, and (2) they are not the closest object to the
robot making them less relevant for obstacle avoidance. Let
$\mathcal{I}_{\mathrm{LOS}}$ be the subset of cells that are in the sensor’s
line-of-sight (LOS). Note that $\widetilde{o}^{\hskip 1.39998pti}_{t+\Delta
t},o^{i}_{t+\Delta t}\in\\{0,1\\}$.

  1. 1.

Classification accuracy: The fraction of cells whose occupancy is correctly
predicted.

$\texttt{Accuracy}=\frac{\sum_{i\in\mathcal{I}_{\mathrm{LOS}}}\mathbb{I}\\{\widetilde{o}^{\hskip
1.39998pti}_{t+\Delta t}=o^{i}_{t+\Delta t}\\}}{|\mathcal{I}_{\mathrm{LOS}}|}$

  2. 2.

Precision: The fraction of cells predicted to be occupied that were actually
occupied.

$\texttt{Precision}=\frac{\sum_{i\in\mathcal{I}_{\mathrm{LOS}}}\mathbb{I}\\{\widetilde{o}^{\hskip
1.39998pti}_{t+\Delta t}=1\\}\leavevmode\nobreak\ \mathbb{I}\\{o^{i}_{t+\Delta
t}=1\\}}{\sum_{i\in\mathcal{I}_{\mathrm{LOS}}}\mathbb{I}\\{\widetilde{o}^{\hskip
1.39998pti}_{t+\Delta t}=1\\}}$

  3. 3.

Recall: The fraction of occupied cells that were also predicted to be
occupied.

$\texttt{Recall}=\frac{\sum_{i\in\mathcal{I}_{\mathrm{LOS}}}\mathbb{I}\\{\widetilde{o}^{\hskip
1.39998pti}_{t+\Delta t}=1\\}\leavevmode\nobreak\ \mathbb{I}\\{o^{i}_{t+\Delta
t}=1\\}}{\sum_{i\in\mathcal{I}_{\mathrm{LOS}}}\mathbb{I}\\{o^{i}_{t+\Delta
t}=1\\}}$

  4. 4.

F1-Score: A combination (harmonic mean) of precision and recall that is a
commonly used for binary classification [74]. The F1 score is robust to class
imbalance; unlike precision and recall, it cannot be trivially improved by
predicting mostly negative labels and mostly positive labels.

$\texttt{F\textsubscript{1}-Score}=\frac{2\cdot\texttt{Precision}\cdot\texttt{Recall}}{\texttt{Precision}+\texttt{Recall}}$

  5. 5.

IoU: The intersection-over-union between cells that are occupied (in ground
truth) and cells that are predicted to be occupied.

$\texttt{IoU}=\frac{\sum_{i\in\mathcal{I}_{\mathrm{LOS}}}\mathbb{I}(\widetilde{o}^{\hskip
1.39998pti}_{t+\Delta t}=1)\leavevmode\nobreak\ \mathbb{I}(o^{i}_{t+\Delta
t}=1)}{\sum_{i\in\mathcal{I}_{\mathrm{LOS}}}\mathbb{I}(\widetilde{o}^{\hskip
1.39998pti}_{t+\Delta t}=1\text{\ or\ }o^{i}_{t+\Delta t}=1)}$

For all metrics, a higher numerical score is better.

##  Appendix H Visualizing velocities and occupancies

Fig. 9 shows how we visualize 2D velocities and occupancies (both ground truth
and estimated velocities and occupancies). The visualization of an example
ground truth grid is shown in Fig. 9c. We use the three-dimensional HSV
colorwheel shown in Fig. 9a to jointly visualize velocities (two-dimensional)
and occupancies (one-dimensional). The ‘value’ encodes the occupancy
probability; dark means low occupancy probability and bright means high
occupancy probability. The ‘hue’ encodes the direction of velocity. We show a
top-down view of the HSV colorwheel in Fig. 9b for clarity. For example, the
bluish-purple hue of the cuboid in Fig. 9c means that the cuboid is moving
upwards in 2D i.e. away from the sensor in 3D. ‘Saturation’ encodes the
magnitude of velocity. This means that white is stationary (e.g. the walls of
the environment shown as parallel white lines) whereas colorful regions
corresponds to high speed.

##  Appendix I Non-stationary rewards

Vanilla multi-armed bandits assume that the reward distribution for each
action is stationary. The Q-value of an action after it was been performed $n$
times is computed as $Q_{n}=\frac{1}{n}\sum_{i=1}^{n}R_{i}$, where $R_{i}$ is
the reward obtained in the $i$-th trial. This is equivalent to the following
recursive update rule: $Q_{n+1}=Q_{n}+\frac{1}{n}[R_{n}-Q_{n}]$, where the
Q-value is incremented by the error scaled by a decaying factor $\frac{1}{n}$.

However, in our case, a single placement strategy may not be superior to the
rest at all times and in all situations. The reward distribution for each
strategy (action) may change with time. Hence, we assume that our rewards are
non-stationary. For non-stationary rewards, we wish to give more weight to
recent rewards than to older rewards. Therefore, the decaying parameter is
replaced by a constant step-size parameter $\alpha$:
$Q_{n+1}=Q_{n}+\alpha\leavevmode\nobreak\ [R_{n}-Q_{n}]$. This weights newer
rewards exponentially more than older rewards according to the expression:
$Q_{n}=(1-\alpha)^{n-1}\leavevmode\nobreak\
R_{1}+\sum_{i=2}^{n}\alpha\leavevmode\nobreak\
(1-\alpha)^{n-i}\leavevmode\nobreak\ R_{i}$.

##  Appendix J Efficient Light Curtain Simulation

Figure 10: Efficient light curtain simulation using a virtual laser. A light
curtain consists of a fixed laser source that emits a light beam, and a
rotating galvo-mirror that reflects and redirects the light in any desired
direction. The laser beam is collimated to a thin rectangular sheet; however,
in reality it is a prismatic slab containing a small divergence. The pixel
intensity of an object (shown by a green circle ) imaged by the light curtain
depends on the radiant intensity of the laser ray that is incident on the
object (shown by the green ray $\rightarrow$). A ray at the center of the beam
has the highest intensity whereas a ray at the boundary of the beam (shown by
orange rays $\rightarrow$) has the lowest intensity. In order to simulate
light curtain pixel intensities for a given object, we must compute its
incident ray i.e. compute its “laser angle” shown by . This computation can be
expensive since (1) it involves tracing rays between the source and the object
through a reflection at the mirror, and (2) it must be performed for each
pixel. Our insight is to construct a “virtual” laser source by reflecting the
real source about the mirror plane. Due to the laws of reflection, the
reflected beam is equivalent to originating from the virtual source behind the
mirror. This allows the laser angle to be computed efficiently by projecting
the object point in the virtual source’s frame. Furthermore, the virtual
source needs to be reflected only once for each mirror configuration; all
pixel points in the currently active camera column can be efficiently
projected into the same virtual laser source.

Fig. 10 shows the working principle behind the illumination module of a
programmable light curtain. It consists of a fixed laser source that emits a
light beam, and a rotating galvo-mirror that reflects and redirects the light
in any desired direction. The laser beam is collimated to a thin rectangular
sheet; however, in reality it is a prismatic slab containing a small
divergence. The pixel intensity of an object (shown by a green circle ) imaged
by the light curtain depends on the radiant intensity of the laser ray that is
incident on the object (shown by the green ray $\rightarrow$). A ray at the
center of the beam has the highest intensity whereas a ray at the boundary of
the beam (shown by orange rays $\rightarrow$) has the lowest intensity. In
order to simulate light curtain pixel intensities for a given object, we must
compute its incident ray i.e. compute its “laser angle” shown by .

Computing the laser ray incident to the object is expensive because (1) it
involves tracing rays between the source and the object through a reflection
at the mirror, and (2) it must be performed for each pixel. Our insight is to
construct a “virtual” laser source by reflecting the real source about the
mirror plane. Due to the laws of reflection, the reflected beam is equivalent
to originating from the virtual source behind the mirror. This allows an
object point’s laser angle to be computed efficiently by projecting it in the
virtual source’s frame. Furthermore, the virtual source needs to be reflected
only once for each mirror configuration; all pixel points in the currently
active camera column can be efficiently projected into the same virtual
source.

##  Appendix K Full-stack navigation

Figure 11: Dense indoor reconstruction and mapping using our integrated
system. The light curtain was mounted on a mobile robot (Fig. 3a) and operated
in an indoor hallway environment. Detected depth points from light curtains
were input to ORB-SLAM3 [13], an RGB-D based localization and mapping system
that estimates the robot’s pose. The pose estimates are fed back into our
pipeline to perform ego-motion subtraction in the motion update step. The
robot trajectory is shown as a white line. (a) Sideways perspective view:
showing dense reconstruction of walls, the floor and other objects. (b) Top-
down orthographic view: showing the accuracy of localization (white line) and
loop-closure. Please find the full video on the project website. This
experiment serves to demonstrate our full-stack navigation pipeline using
light curtains. Figure 12: Real-time obstacle avoidance using our integrated
system. The robot is represented by a green vehicle. The yellow curves show a
library of dynamically feasible paths of the robot [14]. Points detected by
the light curtain on the static (chair) and dynamic (person) objects are show
in blue. The feasible paths that are expected to collide with objects are
removed, and a safe path (shown in red) is chosen by the planner. Please find
the full video on the project website.

We integrate our system into a full-stack navigation pipeline based on the
Autonomous Exploration Development Environment [15]. We mount the light
curtain device on a mobile robot (see Fig. 3a). Our tightly integrated
pipeline performs localization, mapping, planning, control and obstacle
avoidance. We use ORB-SLAM3 [13] for localization and mapping that takes depth
from light curtains as input while the planning and control capabilities are
provided by Cao et al. [15]. The pipeline described in Sec. VII combines light
curtain placement strategies using self-supervised multi-armed bandits with
recursive Bayes estimation of dynamic occupancy grids. The output of this
pipeline i.e. position and velocity estimates are used by the autonomy stack
to perform dense mapping in an indoor environment and obstacle avoidance.
Furthermore, the localization from ORB-SLAM3 [13] is fed back into our
pipeline for ego-motion subtraction in the motion update step (Eqns. 1, 4). We
show two demonstrations of our fully integrated autonomy stack:

###  K-A Real-time dense mapping

Light curtains sense objects that intersect its surface at a high resolution.
This ability can be leveraged to perform dense mapping and reconstruction of
an environment. Please see a video of dense real-time reconstruction of an
indoor hallway environment using our system on the project website. Fig. 11
shows a sideways and top-down projection of the same. The robot was operated
in the indoor hallway environment, and 3D points detected by light curtains
were input to ORB-SLAM3 [13], an RGB-D based localization and mapping system
that estimates the robot’s pose. The pose estimates are fed back into our
pipeline to perform ego-motion subtraction in the motion update step. The
robot trajectory is shown as a white line. Fig. 11a shows that the floor,
walls and other objects are reconstructed densely and accurately. Fig. 11b
contains a top-down orthographic view which shows the accuracy of our system’s
localization – the robot’s trajectory was correctly determined to be an
(approximately) closed loop around the building floor. This experiment serves
to demonstrate our full-stack navigation pipeline using light curtains.

###  K-B Real-time obstacle avoidance

Light curtains are a fast sensor ($\sim$45 Hz) whose speed is leveraged by our
system to produce position and velocity estimates at a high frequency
($\sim$35 Hz). We use these estimates for real-time obstacle avoidance, shown
in Fig. 12. The robot is represented by a green vehicle. The yellow curves
show a library of dynamically feasible paths of the robot [14]. Points
detected by the light curtain are shown in blue. There are two objects in the
scene: a static chair, and a moving person. Using the position estimates of
obstacles, feasible paths that are expected to collide with objects are
rejected, and a safe path (shown in red) is chosen by a local planner [14].
Please find the full video of real-time obstacle avoidance on the project
website.