國立高雄大學圖資館 |

Language: English

Back

Approximation algorithms for robotic motion planning.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Approximation algorithms for robotic motion planning.
Author:	Sun, Zheng.
Description:	190 p.
Notes:	Source: Dissertation Abstracts International, Volume: 64-08, Section: B, page: 3915.
Notes:	Supervisor: John H. Reif.
Contained By:	Dissertation Abstracts International64-08B.
Subject:	Computer Science.
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3102255
ISBN:	0496498258

Approximation algorithms for robotic motion planning.
Sun, Zheng.

Approximation algorithms for robotic motion planning. [electronic resource] - 190 p.

Source: Dissertation Abstracts International, Volume: 64-08, Section: B, page: 3915.

Thesis (Ph.D.)--Duke University, 2003.

Our first result is an approximation algorithm for the weighted region optimal path problem. In this problem, a point robot moves in a planar space composed of n triangular regions, each of which is associated with a positive unit weight. The objective is to find, for given source and destination points s and t, a path from s to t with the minimum weighted length. Our algorithm, BUSHWHACK, adopts a traditional approach that converts the original continuous geometric search space into a discrete graph G by placing representative points on boundary edges. However, exploiting geometric structures that we call intervals, BUSHWHACK computes an approximate optimal path more efficiently by accessing only a sparse subgraph of G . Combined with the logarithmic discretization scheme introduced by Aleksandrov et al. [14], BUSHWHACK can compute an epsilon-approximation in O( ne (log 1e + log n) log 1e ) time.

ISBN: 0496498258Subjects--Topical Terms:

212513
Computer Science.

Approximation algorithms for robotic motion planning.
LDR:03654nmm _2200289 _450 001 162083
005 20051017073408.5
008 230606s2003 eng d
020 $a 0496498258
035 $a 00148584
035 $a 162083
040 $a UnM $c UnM
100 0 $a Sun, Zheng. $3 227195
245 1 0 $a Approximation algorithms for robotic motion planning. $h [electronic resource]
300 $a 190 p.
500 $a Source: Dissertation Abstracts International, Volume: 64-08, Section: B, page: 3915.
500 $a Supervisor: John H. Reif.
502 $a Thesis (Ph.D.)--Duke University, 2003.
520 # $a Our first result is an approximation algorithm for the weighted region optimal path problem. In this problem, a point robot moves in a planar space composed of n triangular regions, each of which is associated with a positive unit weight. The objective is to find, for given source and destination points s and t, a path from s to t with the minimum weighted length. Our algorithm, BUSHWHACK, adopts a traditional approach that converts the original continuous geometric search space into a discrete graph G by placing representative points on boundary edges. However, exploiting geometric structures that we call intervals, BUSHWHACK computes an approximate optimal path more efficiently by accessing only a sparse subgraph of G . Combined with the logarithmic discretization scheme introduced by Aleksandrov et al. [14], BUSHWHACK can compute an epsilon-approximation in O( ne (log 1e + log n) log 1e ) time.
520 # $a Our third main result is a new sampling method for probabilistic roadmap (PRM) planners. The main idea of a PRM planner is to sample at random a robot's configuration space to construct a network, called a roadmap, that represents the geometry of the free space. Previous experimental results have shown that the existence of narrow passages in the configuration space creates significant difficulty for PRM planners to capture the connectivity of the free space. We present a hybrid sampling method in the PRM framework for finding paths through narrow passages. (Abstract shortened by UMI.)
520 # $a Robotic motion planning problems are some of the most fundamental problems in robotics research. Each problem computes for a robot paths or trajectories that are collision-free amid a specified set of obstacles and, in certain cases, cost-minimizing according to a user-defined cost function. This dissertation presents a number of results on several robotic motion planning problems.
520 # $a We also study two other optimal path problems, which can be regarded as generalizations of the weighted region optimal path problem. In the first problem, a point robot with a bounded control velocity moves through a set of polygonal regions of given translational flow velocities. The cost of any path is defined to be the time it takes for the robot to traverse the path. In the second problem, a robot travels on the surface of a terrain consisting of polygonal faces with defined friction coefficients. The cost of any path on the terrain is defined to be the energy loss due to both friction and gravity. This problem adds anisotropism to optimal path planning by taking into consideration impermissible traversal directions resulted from overturn danger or power limitations.
590 $a School code: 0066.
650 # 0 $a Computer Science. $3 212513
650 # 0 $a Engineering, Mechanical. $3 212470
710 0 # $a Duke University. $3 226880
773 0 # $g 64-08B. $t Dissertation Abstracts International
790 $a 0066
790 1 0 $a Reif, John H., $e advisor
791 $a Ph.D.
792 $a 2003
856 4 0 $u http://libsw.nuk.edu.tw/login?url=http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3102255 $z http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3102255