In this paper we address the problem of generating a motion strategy to find an object in a known 3-D environment as quickly as possible on average. We use a sampling scheme that generates an initial set of sensing locations for the robot and then we propose a convex cover algorithm based on this sampling. Our algorithm tries to reduce the cardinality of the resulting set and has the main advantage of scaling well with the dimensionality of the environment. We then use the resulting convex covering to generate a graph that captures the connectivity of the workspace. Finally, we search this graph to generate trajectories that try to minimize the expected value of the time to find the object.

In this paper we consider the problem of maintaining surveillance of a moving the target by a nonholonomic mobile observer. The observer's goal is to maintain visibility of the target from a predefined, fixed distance, l. The target escapes if (a) it moves behind an obstacle to occlude the observer's view, (b) it causes the observer to collide with an obstacle, or (c) it exploits the nonholonomic constraints on the observer motion to increase its distance from the observer beyond the surveillance distance l. We deal specifically with the situation in which the only constraint on the target's velocity is a bound on speed (i.e., there are no nonholonomic constraints on the target's motion), and the observer is a nonholonomic, differential drive system having bounded speed. We develop the system model, from which we derive a lower bound for the required observer speed. Finally, we consider the effect of obstacles on the observer's ability to successfully track the target.

This work addresses the problem of computing the motions of a robot observer in order to maintain visibility of a moving target at a fixed surveillance distance. In this paper, we deal specifically with the situation in which the observer has bounded velocity. We give necessary conditions for the existence of a surveillance strategy and give an algorithm that generates surveillance strategies.

In this paper we address the problem of finding time optimal search paths in known environments. In particular, the task is to search a known environment for an object whose unknown location is characterized by a known probability density function (pdf). With this formulation, the time required to find the object is a random variable induced by the choice of search path together with the pdf for the object's location. The optimization problem is to find the path that yields the minimum expected value of the time required to find the object. We propose a two layered approach. Our algorithm first determines an efficient ordering of visiting regions in a decomposition that is defined by critical curves that are related to the aspect graph of the space to be searched. It then generates locally optimal trajectories within each of these regions to construct a complete continuous path. We have implemented this algorithm and present results.

This paper deals with the problem of computing the motions of a robot observer in order to maintain visibility of a moving target. The target moves unpredictably, and the distribution of obstacles in the workspace is known in advance. Our algorithm computes a motion strategy based on partitioning the configuration space and the workspace in non-critical regions separated by critical curves. In this work, the existence of a solution for a given polygon and delay are determined.

In this paper, we propose an approach to solve the problem of finding an object in a polygon which may contain holes. We define an optimal solution as the route that minimizes the expected time it takes to find said object. The object search problem is shown to be NP-hard by reduction, therefore, we propose the heuristic of an utility function, defined as the ratio of a gain over a cost and a greedy algorithm in a reduced search space that is able to explore several steps ahead without incurring in too high computational cost. This approach was implemented and simulation results are shown.