Generating Expected-Time Efficient Trajectories for Rapidly Finding an Object in Known Environments

Sarmiento, Alejandro

Permalink

https://hdl.handle.net/2142/10924 Copy

Description

Title

Generating Expected-Time Efficient Trajectories for Rapidly Finding an Object in Known Environments

Author(s)

Sarmiento, Alejandro

Issue Date

2004-12

Keyword(s)

• machine learning
• robotics
• artificial intelligence

Abstract

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.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/10924

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections