Bipartite information space

Although a general efficient algorithm is good to have, it may not explore the full structure of a particular problem. One interesting property of our problem is that the distribution of targets in the shadows mimics network commodity flow. Another intrinsic and key property of our problem is that, in many cases, the relative order of component events does not affect the possible target distribution in the shadows. For example, the two sequences of component events from Fig. 9 are equivalent: the set of shadows at $t = t_f$ are basically the same.

Figure 9: Two sequences of component events that are equivalent for task of estimating lower and upper bounds on the number of targets in the shadows at time $t = t_f$ .

This allows us to safely discard the intermediate shadows to obtain a more compact information space $\mathcal I_{bip}$ , the bipartite information space. The basic idea behind compressing $\mathcal I_{ss}$ into $\mathcal I_{bip}$ is that, since the robots' sensors cannot obtain information from the shadows as the robots move around, the information that really matters is how shadows from the beginning and the current time are related, while discarding the shadows from intermediate times. By conservation of targets in the environment, the number of targets in the shadows at $t = t_0$ and appeared shadows must be equal that in the shadows at $t = t_f$ and disappeared shadows. This hints towards a bipartite graph structure, which is why we denote the space of such I-states the bipartite information space. To do the filtering, the component events are processed individually according to the procedure shown in Fig. 10. By the construction of $\mathcal I_{ss}$ and $\mathcal I_{bip}$ , we have shown that $\mathcal I_{hist}$ , $\mathcal I_{ss}$ , and $\mathcal I_{bip}$ describe the same ILP problem:

Proposition 5   Given that targets move nondeterministically, information from $\mathcal I_{hist}$ and the corresponding $\mathcal I_{ss}$ , $\mathcal I_{bip}$ describe the same ILP problem of the form (6).

PROOF. The invariance from Observation 2 gives us that $\mathcal I_{hist}$ and $\mathcal I_{ss}$ are equivalent in capturing the distribution of hidden targets. To see that $\mathcal I_{ss}$ and $\mathcal I_{bip}$ are equivalent, we may consider each hidden target individually: Any flow of a target along a shadow sequence is possible in the corresponding bipartite structure, by construction. 

Figure 10: Incrementally computing I-states in $\mathcal I_{bip}$ : a) An appear component event in which $a$ targets goes into shadow $s_i$ adds two vertices and an edge, with $a$ associated with the left vertex. b) A split event splits a vertex and all edges pointing to that vertex. c) A merge event collapses two vertices into one and collapses their ingoing edges. d) A disappear event in which $s_i$ is revealed to have $a$ targets in it only associates $a$ with the vertex on the right side.