  Visual and scalar-field (e.g., chemical) sensing are two of the options robot
teams can use to perceive their environments when performing tasks. We give the
first comparison of the computational characteristic of visual and scalar-field
sensing, phrased in terms of the computational complexities of verifying and
designing teams of robots to efficiently and robustly perform distributed
construction tasks. This is done relative a basic model in which teams of
robots with deterministic finite-state controllers operate in a synchronous
error-free manner in 2D grid-based environments. Our results show that for both
types of sensing, all of our problems are polynomial-time intractable in
general and remain intractable under a variety of restrictions on parameters
characterizing robot controllers, teams, and environments. That being said,
these results also include restricted situations for each of our problems in
which those problems are effectively polynomial-time tractable. Though there
are some differences, our results suggest that (at least in this stage of our
investigation) verification and design problems relative to visual and
scalar-field sensing have roughly the same patterns and types of tractability
and intractability results.
