Robot motion planning problem has been actively studied since 1970`s and has many applications, such as part disassembly, autonomous vehicle and computer graphics. Sampling-based algorithms have been successfully used to give a probabilistically complete solution for a variety of types of robots and constraints. Sampling-based algorithms, however, suffer when narrow passages are included in an environment. This phenomenon become worse as more constraints are related such as kinematic and dynamics constraints, because of its high degrees-of-freedom and complexity of extensions. In this thesis, we present novel sampling-based planners to efficiently handle various environments that have different characteristics and constraints. We first present a bridge line-test that can identify narrow passage regions in the configuration space, and then selectively performs an optimization-based retraction only at those regions. We also propose a non-colliding line-test, a dual operator to the bridge line-test, as a culling method to avoid generating samples near wide-open free spaces. These two line-tests are performed with a small computational overhead. As a result, proposed planner shows better performance than recent works for a variety of environments that have or do not have narrow passages. For a hyper-redundant robot manipulator, we define productive regions in the task space as a set of states that can lead effectively to a goal state. To check whether a node of a random tree is in productive regions or not, we construct a maximum reachable area (MRA) for a node in the task space, where a manipulator can reach from the node by using an employed local planner. When the MRA of a node contains the goal state, we call it promising and bias our sampling to cover promising MRAs. When the MRA does not contain the goal state, we call it unpromising and construct a detour sampling domain for detouring operations from obstacles constraining the manipulator. The union of promising MRAs and detour sampling domains approximates our productive regions, and we bias sampling regions to cover these domains more. Finally, we present a novel kinodynamic motion planner designed for complex dynamics environments with many obstacles. We define a motion database that is constructed as a preprocessing and can replace time-consuming propagation function integration of kinodynamic sampling-based planners. Motion interpolation is applied for retrieving large set of motions in the continuous state space. During iterations, interpolated motions are selectively validated by the employed simulator in order to increase the efficiency of the planner. Constructed motion database can be also used for other problems such as different composition of obstacles or different start/goal state. Overall, proposed methods achieve several times improvement over the state-of-the-art planning algorithms.
로봇 모션 플래닝은 부품 조립, 무인자동차, 컴퓨터 그래픽스 등 많은 분야에서 널리 사용되는 문제로 1970년대 이래로 활발하게 연구가 된 분야이다. 그중에서도 확률적 완전성(probabilistically complete) 특징을 갖는 샘플링 기반 알고리즘이 다양한 종류의 로봇과 제약조건에 대해 많이 사용되어 왔다. 그러나, 샘플링 기반 알고리즘은 문제 환경 내에 좁은 길이 포함되는 경우에 성능이 저하되는 문제점을 가지고 있다. 이러한 경향은 운동학적 동역학적 제약조건들이 추가되거나, 로봇 매니퓰레이터(robot manipulator) 처럼 로봇의 자유도가 높아지는 경우 더욱 악화된다. 본 학위논문에서 자유비행 강체로봇(free-flying rigid robot)의 경로를 다양한 특성을 가진 환경에 대해 효율적으로 수행하는 알고리즘과 로봇 매니퓰레이터를 위한 새로운 작업공간(task-space) 기반 알고리즘을 제안한다. 강체로봇을 위한 알고리즘에서 새롭게 제안하는 브리지 라인테스트를 이용해 환경에서 좁은길의 존재여부를 탐색하여 필요한 영역에서만 리트렉션 방법을 선택적으로 수행한다. 또한 넓은 오픈 프리 스페이스(open free-space) 영역에서의 불필요한 샘플링을 제외시키는 방법으로 비충돌 라인테스트를 제안한다. 제안된 두개의 라인테스트는 계산량이 적으며, 이를 이용해 좁은길을 포함한 경우나 그렇지 않은 경우 모두 기존에 알려진 방법보다 더 빠른 속도로 문제를 해결할 수 있다. 로봇 매니퓰레이터를 위한 효율적인 알고리즘을 위해, 먼저 작업공간 내에서 로봇을 목적하는 지점까지 옮기기 위한 효율적인 위치의 집합을 생산적 구역(productive regions)으로 정의한다. 생산적 구역 내에 샘플이 포함되는지를 알기위해 해당 샘플 위치에서의 최대도달가능지역을 계산한다. 최대도달가능지역에 목적지가 포함되는 경우에는 이를 유망한 지역으로 정의하고 유망한 최대도달가능지역들에서 샘플링을 집중한다. 반면에 목적지가 포함되지 않는 경우에는 비유망 지역으로 이를 정의하고 우회경로 구역을 계산하여 이곳에서 샘플링을 집중한다. 우회경로 구역과 유망한 최대도달가능지역에 편향된 샘플링을 통해 더 효율적으로 경로를 계산해 낼 수 있다.
