Nondeterministically moving targets

For the nondeterministic case, we implemented and tested the algorithms for a single robot that moves in a simply connected polygonal region in $\mathbb{R}^2$ using an omnidirectional visibility sensor. For such environment, the shadows are completely characterized by bitangents and inflections. When the environment is known and the robot can localize itself, efficient 2D cell decomposition algorithms can be readily applied to obtain the sequence of shadows for each location of the robot, allowing the shadows to be continuously tracked. This setup also enables us to construct an oracle (not available to the algorithm) for distributing targets inside the free space to simulate their nondeterministic behavior. For max-flow, we implemented the $O(VE^2)$ -time Edmonds-Karp max-flow algorithm [8], in which $V$ and $E$ are the numbers of vertices and edges in the flow graph, respectively.

Figure 15: Complicated examples that were used to test our approach. The given robot trajectories are shown as green lines in the direction of the arrow.

For the environment in Figure 15(a), the trajectory generates $85$ component events. Our oracle randomly distributed $100$ targets in the free space as the component events occur. This setting yields a bipartite graph that has $41$ vertices and $60$ edges. Calculating the lower and upper bounds for the $18$ final shadow components for a single team took $0.1$ seconds. The second free space, shown in Figure 15(b), has $385$ component events, $491$ total shadow components, $124$ vertices in the bipartite graph with $339$ edges. The example involves a million targets with $5$ teams that intersperse. The bounds on the $12$ final shadow components for all $5$ teams were computed under one second.

The inputs to the base algorithm (single attribute, no FOV events) are: 1) A sequence of $n$ shadows, and 2) The initial condition which takes the form of a pair of lower and upper bounds for each shadow at $t = t_0$ . In the worst case, there are $O(n)$ vertices and $O(n^2)$ edges in the bipartite graph. Edmonds-Karp max-flow then gives us $O(n^5)$ running time in the worst case. Applying push-relabel algorithm with FIFO vertex selection rule will cut the running time to $O(n^3)$ [11]. Adding FOV events does not increase time complexity asymptotically, as discussed in subsection V-E. Adding partial distinguishability, on the other hand, will introduce another input parameter $m$ , the number of teams, that contributes linearly to time complexity. The typical worst case running time for the nondeterministic case is then $O(n^3m)$ . The number of targets in the system does not directly affect the performance.