  Whether a robot can perform some specific task depends on several aspects,
including the robot's sensors and the plans it possesses. We are interested in
search algorithms that treat plans and sensor designs jointly, yielding
solutions---i.e., plan and sensor characterization pairs---if and only if they
exist. Such algorithms can help roboticists explore the space of sensors to aid
in making design trade-offs. Generalizing prior work where sensors are modeled
abstractly as sensor maps on p-graphs, the present paper increases the
potential sensors which can be sought significantly. But doing so enlarges a
problem currently on the outer limits of being considered tractable. Toward
taming this complexity, two contributions are made: (1) we show how to
represent the search space for this more general problem and describe data
structures that enable whole sets of sensors to be summarized via a single
special representative; (2) we give a means by which other structure (either
task domain knowledge, sensor technology or fabrication constraints) can be
incorporated to reduce the sets to be enumerated. These lead to algorithms that
we have implemented and which suffice to solve particular problem instances,
albeit only of small scale. Nevertheless, the algorithm aids in helping
understand what attributes sensors must possess and what information they must
provide in order to ensure a robot can achieve its goals despite
non-determinism.
