DISSERTATION DEFENSE Department of Computer Science and Engineering, University of South Carolina Candidate: Nicholas Stiffler Advisor: Dr. Jason O’Kane Abstract As technological advances further increase the amount of memory and computing power available to mobile robots we are seeing an unprecedented explosion in the utilization of deployable robots for various tasks. The speed at which robots begin to enter various domains is largely dependent on the availability of robust and efficient algorithms that are capable of solving the complex planning problems inherent to the given domain. One such domain which is experiencing unprecedented growth in recent years requires a robot to detect and/or track a mobile agent or group of agents. In these scenarios there are typically two-players with diametrically opposed goals. For matters of security, we have a guard and an intruder. The guard's goal is to ensure that if an intruder enters the premises they are caught in a timely manner. Analogously, the intruder wishes to evade detection for as long as possible. Search and rescue operations are often framed as a two-player game between rescuers and survivors. Though the survivors are unlikely to behave antagonistically, an agnostic model is useful for the rescuers to guarantee that the survivors are found, regardless of their movements. Both of these tasks are at their core pursuit-evasion problems. There are many variants of the pursuit-evasion problem, the common theme amongst them is that one group of agents, the ``pursuers'', attempts to track members of another group, the ``evaders''. The visibility-based pursuit-evasion problem requires a pursuer(s) to systematically search an environment to locate one or more evaders ensuring that all evaders will be found by the pursuer(s) in a finite time. This thesis contains four novel contributions that solve various visibility-based pursuit-evasion problems. The first contribution is an algorithm that computes the optimal (minimal path length) pursuer trajectory for a single pursuer. The second contribution is an algorithm that generates a joint motion strategy for multiple pursuers. Motivated by the result of the second contribution, the third result is a sampling-based algorithm for the multiple pursuer scenario. The fourth contribution is a complete algorithm that computes a trajectory for a pursuer that has a very limited sensor footprint.