Component events and shadows

Let a nonempty set of robots move along continuous trajectories in a workspace, $W = \mathbb{R}^2$ or $W = \mathbb{R}^3$ . Let the configuration space of the robots be $\mathcal C$ . At some time $t$ , there may be configuration space obstacles $\mathcal C_{obs}$ , leaving $\mathcal C_{free} := \mathcal C\backslash \mathcal C_{obs}$ as the free configuration space. Let $q \in \mathcal C_{free}$ be the configuration of the robots. Returning to workspace, there is a closed obstacle region $O(q) \subseteq W$ , leaving $F(q) := W \backslash O(q)$ as the free space. The robots are equipped with sensors that allow them to make shared observations in a joint field-of-view (FOV) or visible region $V(q) \subseteq F$ . For convenience, we take the closure of $V(q)$ and assume that the visible region is always closed. Let $S(q) := F \backslash V(q)$ be the shadow region, which may contain zero or more nonempty path connected components (path components for short). A path component is assumed to be nonempty unless otherwise specified. At any instant, $O(q), V(q),$ and $S(q)$ have disjoint interiors by definition and $W = O(q) \cup V(q) \cup S(q)$ . Fig. 3 shows $V(q), S(q)$ for a point robot holding a flashlight in $F \subset \mathbb{R}^2$ , $\mathcal C_{free} \subset SE(2)$ .

Figure 3: (a) Environment and free space $F$ . (b) The visible region. (c) The shadow region with two path components $s_1, s_2$ .

To observe how path components of the shadow region evolve over time, let the robots follow some path $\tau: [t_0, t_f] \to \mathcal C$ in which $[t_0, t_f] \subseteq T \subset \mathbb{R}$ is a time interval. Let $Z = W \times T$ . Since obstacles may vary over configuration and time, let

$$O: \mathcal C \times T \to Pow(Z)$$

be the map that yields the obstacle region with a time stamp attached. We may also view $V, S$ as varying over configuration and time:

$$V, S: \mathcal C \times T \to Pow(Z).$$

Since a path $\tau$ , parameterized over $t \in T$ , is always assumed in the paper, we abusively write $O(t), V(t), S(t)$ in place of $O(\tau(t), t), V(\tau(t), t), S(\tau(t), t)$ , respectively. For any interval $(t_a, t_b) \subset [t_0, t_f]$ , let

$$S(t_a, t_b) := \bigcup_{t \in (t_a, t_b)} S(t)$$

be called a slab, which is an open subset of $Z$ . For any subset $z$ of $Z$ , define its projection onto the time axis as

$$\begin{array}{l} \pi_t: Pow(Z) \to Pow(T), \\ z \mapsto \{ t \mid (p, t) \in z \mbox{ for some } p \in W \}. \end{array}$$

Let $s_{t, i} \subset S(t)$ denote the $i$ -th path component of $S(t)$ . Let $s_{i'}$ denote the $i'$ -th path component of a slab $S(t_a, t_b)$ . $S(t_a, t_b)$ is homogeneous if for all $t \in (t_a, t_b)$ and all $i$ for each $S(t)$ , there exists $i'$ such that

$$s_{t, i} = S(t) \cap s_{i'},$$

and separately,

$$\pi_t(s_{i'}) = (t_a, t_b)$$    for all $$i'.$$

A homogeneous slab is called maximal if it is not a proper subset of another homogeneous slab. The definition then partitions $S(t_0, t_f)$ into some $m$ disjoint maximally homogeneous slabs plus some slices

$$S(t_0, t_f) = S(t_0, t_1) \cup S(t_1) \cup \ldots \cup S(t_{m-1}, t_m = t_f).$$

That is, homogeneity of $S(t_0, t_f)$ is broken at $t_1, \ldots, t_{m-1}$ . What exactly happens at $t_i \in \{t_1, \ldots, t_{m-1}\}$ ? Let there be two homogeneous slabs $S(t_a, t_b)$ and $S(t_b, t_c)$ such that $t_{i-1} \le t_a < t_b = t_i < t_c \le t_{i + 1 }$ for some $t_i \in \{t_1, \ldots, t_{m-1}\}$ . Let $s_i$ be an arbitrary path component of $S(t_a, t_b)$ , at $t = t_b$ , $s_i$ may ( $\overline{s}$ denotes the closure of $s$ )

1)

live on, if there exists a path component $s_j \subset S(t_b, t_c)$ such that $\overline{s_i} \cap S(t_b) = \overline{s_j} \cap S(t_b) \ne \varnothing$ .

2)

disappear, if $\overline{s_i} \cap S(t_b) = \varnothing$ .

Similarly, a path component $s_j \subset S(t_b, t_c)$ may

3)

appear, if $\overline{s_j} \cap S(t_b) = \varnothing$ .

Finally, a nonempty set of path components $\{s_i\}$ of $S(t_a, t_b)$ may

4)

evolve, if there is a nonempty set of path components $\{s_j\}$ of $S(t_b, t_c)$ such that $\vert\{s_i\}\vert + \vert\{s_j\}\vert \ge 3$ and $\bigcup_i \overline{s_i} \cap S(t_b) = \bigcup_j \overline{s_j} \cap S(t_b) \ne \varnothing$ is a single path component of $S(t_b)$ .

By definition, appear, disappear, and evolve are critical changes that only (and at least one of which must) happen between two adjacent maximally homogeneous slabs. Let these changes be called component events. With component events, homogeneity and maximality readily extend to path components of slabs. A path component $s_i \subset S(t_a, t_b)$ is called homogeneous if no component events happen to a subset of $s_i$ in $(t_a, t_b)$ ; $s_i$ is called maximal if it is not a proper subset of another homogeneous path component.

In this paper, a type of general position is assumed to avoid two cumbersome cases: 1) Four or more path components cannot be involved in an evolve event, and 2) Two or more component events cannot occur at the same time. With such an assumption, exactly one component event happens between two maximally homogeneous slabs. Moreover, the evolve event can be divided into two sub events: split if $\vert\{s_i\}\vert = 1, \vert\{s_j\}\vert = 2$ and merge if $\vert\{s_i\}\vert = 2, \vert\{s_j\}\vert = 1$ . The appear, disappear, split and merge events, as they happen in $Z$ , are illustrated in Fig. 2: For the slab $S(t_0, t_f)$ , there are two shaded path components, five maximally homogeneous slabs (between dotted vertical lines), and six maximally homogeneous path components $s_1, \ldots, s_6$ . Each vertical slice along $t \in (t_0, t_f)$ corresponds to $S(t)$ . There are four component events. For convenience, it is assumed that $t = t_0$ is not a critical time in the sense that for each path component $s_{t_0,i} \subset S(t_0)$ , $s_{t_0,i} = \overline{s_{i'}} \cap S(t_0)$ for some path component $s_{i'} \subset S(t_0, t_1)$ . A similar assumption is made for $t = t_f$ .

It is easy to see that maximally homogeneous path components are pairwise disjoint. Let such a path component be called a shadow component. Let $\{s_i\}$ be the set of shadow components of $S(t_0, t_f)$ ; note that $S(t_0, t_f)$ is contained in the closure of $\cup_i s_i$ . For some $t \in (t_0, t_f)$ , let a path component of $S(t)$ be labeled as $s_{t,i}$ if it is a slice (cross section) of a shadow component $s_i$ . More precisely, $s_{t, i} = s_i \cap \{(p, t) \mid p \in W\}$ . For $t = t_0$ , $s_{t_0, i}$ is labeled such if $s_{t_0, i} = \overline{s_i} \cap S(t_0)$ for some path component $s_i \subset S(t_0, t_1)$ . Same applies to the labeling of $s_{t_f, i}$ . A path component of $S(t)$ has no label exactly when it is the border of two or more shadow components of a slab. Since such labeling is unique, we drop time subscript of $s_{t,i}$ if $t$ is fixed. In the rest of the paper, we use the set $\{s_i\}$ to denote both shadow components and slices of shadow components; we simply call both types of path components shadows when no confusion will arise from the context. When we do need to distinguish, the former will be called workspace-time shadows and the later workspace shadows.