  The problem of searching a polygonal region for an unpredictably moving
intruder by a set of stationary guards, each carrying an orientable laser, is
known as the Searchlight Scheduling Problem. Determining the computational
complexity of deciding if the polygon can be searched by a given set of guards
is a long-standing open problem.
  Here we propose a generalization called the Partial Searchlight Scheduling
Problem, in which only a given subregion of the environment has to be searched,
as opposed to the entire area. We prove that the corresponding decision problem
is strongly PSPACE-complete, both in general and restricted to orthogonal
polygons where the region to be searched is a rectangle.
  Our technique is to reduce from the "edge-to-edge" problem for
nondeterministic constraint logic machines, after showing that the
computational power of such machines does not change if we allow "asynchronous"
edge reversals (as opposed to "sequential").
