Generating expected-time efficient trajectories for rapidly finding an object in known environments

This work addresses the problem of generating a motion strategy for solving a visibility-based task with a mobile robot equipped with sensors. In particular, the problem is to find a static object---modeled with a probability density function---in a completely known environment.; Given a starting position for the robot, the problem is to generate a trajectory that minimizes the expected value of the time to see the object for the first time along that route. The problem is shown to be NP-hard and efficient algorithms that perform well in practice are presented.; Several versions of this problem are addressed. The first one is the case of a point robot moving in a polygonal workspace. The robot is restricted to sense the world only at predefined locations arranged in a graph. The proposed solution uses an utility function to drive a greedy search algorithm in a reduced space, able to explore several steps ahead without incurring too high a computational cost. This approach is also extended to coordinate a team of robots searching in parallel to further reduce the search time without an increase in the computational complexity of the algorithm.; The second version assumes the robot is able to sense the environment continuously. In this case, the proposed approach partitions the polygonal workspace into regions separated by critical curves. Then, the calculus of variations and numerical integration are applied to compute locally optimal trajectories within each individual region. Finally, the resulting sub-paths are concatenated to generate a complete path.; In the final version, the robot is no longer a point but a mobile manipulator moving in a 3-D environment. The proposed solution builds on previous results and also introduces a sample-based convex cover to estimate the size and shape of visibility regions in 3-D. The resulting convex regions are exploited to generate trajectories that compromise between moving the base and moving the robotic arm.