서지주요정보
2-D Path planning for weighted-regions by weighted-quadtree method = 가중 Quad Tree를 이용한 가중치 지역에 대한 최적 경로선정
서명 / 저자 2-D Path planning for weighted-regions by weighted-quadtree method = 가중 Quad Tree를 이용한 가중치 지역에 대한 최적 경로선정 / Ki-Cheon Yoon.
저자명 Yoon, Ki-Cheon ; 윤기천
발행사항 [대전 : 한국과학기술원, 1996].
Online Access 원문보기 원문인쇄

소장정보

등록번호

8006928

소장위치/청구기호

학술문화관(문화관) 보존서고

DEE 96043

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

Path planning is one of the most important research areas of robotics, operations research, artificial intelligence and other optimization fields. Much research has been focused on developing theories and algorithms needed for the planning of a path. Most of approaches posit a binary view of the environment, either traversable or impassable, and find the non-colliding shortest path based on the Euclidean-distance metrics. However, a real workspace is an environment which consists of many different media, such as terrains, hazard regions, threats, obstacles and etc.. It is natural to allow a path to pass through them at extra costs. The extra costs are represented by the weights that means the 'cost per unit distance' of moving through that particular region. In this weighted environment, the shortest path of Euclidean-distance metrics does not imply the least cost path. If we assign the weight as infinity or 1 depending on the existence of obstacles or not, the path planning in the weighted workspace becomes the binary workspace. Therefore path planning in the weighted workspace is a generalized shortest path problem. Until recently, efficient methods representing the weighted regions and the feasible path planning algorithms in the weighted workspace are not yet sufficiently developed. In this thesis, our novel weighted quadtree (WQT) as a new representation method and a path planning approach based on the weighted quadtree are described. The WQT is a hierarchical multiresolution cell decomposition technique. All leaves of the tree have a restricted cost and each leaf has a different area depending on the weight of that area. Without loss of generality, the most important heuristics for the space representation for the path planning is to avoid excess details and spending time on the parts of the space that does not affect the planning operation. The more weighted risk cost region is, the more detail path planning is required for more safety. The coarse discretization on the low weighted region speed up the overall process. The novel WQT-based cell decomposition method naturally provides such description of workspace. The novel WQT-based path planning method and the related algorithms such as neighbor finding, antialiased path cost and path relaxation are described in detail. Also dynamic discrete events-based route evaluation method is shown for the selected path. This evaluation method is very effective to verify the route safeness if the workspace have some active agents that operate dynamically with some interactive events. Finally, an integrated framework for the path planning is implemented in the weight workspace. The complete map of the workspace including the risk costs as well as obstacle locations is assumed to be known a priori.

서지기타정보

서지기타정보
청구기호 {DEE 96043
형태사항 x, 101 p. : 삽도 ; 26 cm
언어 영어
일반주기 저자명의 한글표기 : 윤기천
지도교수의 영문표기 : Kyu-Ho Park
지도교수의 한글표기 : 박규호
학위논문 학위논문(박사) - 한국과학기술원 : 전기및전자공학과,
서지주기 Reference : p. 94-101
주제 Shortest path search
Path planning
Mission planning
Weighted region problem
Navigation
Motion planning
Area decomposition
Computational geometry
Discrete events simulation
Dynamic path planning
QR CODE qr code