In many environments the problem arises of generating motion strategies for real and virtual robotic systems with visibility- based sensing capabilities. This last term refers to the ability of a sensor (e.g., a video camera or a range sensor) to detect objects along one or several line-of-sight rays through free space. Both a new conceptual framework and a collection of specific new algorithms are needed to perform motion planning under visibility constraints, in addition to the classical collision avoidance constraints dealt with by previous planners. The output of these algorithms will be motion strategies that integrate motion commands with visibility-based sensing operations. While robotics has extensively studied the motion planling problem for robots operating in fully known environments with little or no sensing ability, and active vision has studied the problem of local camera motion/control in order to acquire needed data, the integration of visibility sensing with motion planning has remained relatively unexplored. Yet a variety of important tasks for a robot can be expressed in the language of visibility. `Plan a tour so as to see all of the region of interest,' `move to the desired location while keeping sight of a target,' `keep a moving target into sight despite view- obstructing mobile objects' are just some examples of such tasks. As visibility-based sensing allows robots to operate in partially unknown environments, these techniques allow on-line planning applicable to dynamic environments. Both manufacturing and medicine can benefit from application of such methods, especially in those operations (e.g., part delivery, assembly, monitoring) that occur in heavily occluded and dynamic work environments.