IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

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

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/10924

Files in this item

File Description Format
PDF Generating Expe ... in Known Environments.pdf (2MB) (no description provided) PDF
Title: Generating Expected-Time Efficient Trajectories for Rapidly Finding an Object in Known Environments
Author(s): Sarmiento, Alejandro
Subject(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.
Issue Date: 2004-12
Genre: Technical Report
Type: Text
URI: http://hdl.handle.net/2142/10924
Other Identifier(s): UIUCDCS-R-2004-2491
Rights 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).
Date Available in IDEALS: 2009-04-17
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 163
  • Downloads this Month: 0
  • Downloads Today: 0

Browse

My Account

Information

Access Key