(a) 작업 공간 상에서 임의의 신규 포인트를 샘플링하는 단계와;(b) 상기 신규 포인트에 대응하는 신규 작업 공간 노드와, 상기 신규 포인트에 인접한 인접 작업 공간 노드를 추출하는 단계와;(c) 상기 인접 작업 공간 노드의 부모 노드에 대응하는 적어도 하나의 상태 노드와 상기 인접 작업 공간 노드에 대응하는 상태 노드를 상태 트리로부터 추출하여 후보 상태 노드로 등록하는 단계와;(d) 상기 후보 상태 노드와 상기 신규 포인트 간의 경로 비용을 포함한 후보 경로 비용을 산출하여, 상기 후보 상태 노드 중 최소의 상기 후보 경로 비용을 갖는 후보 상태 노드를 최소 비용 부모 상태 노드로 추출하는 단계와;(e) 상기 신규 작업 공간 노드와 상기 인접 작업 공간 노드를 상기 작업 공간 트리에 등록하고, 상기 최소 비용 부모 상태 노드와 상기 신규 작업 공간 노드에 대응하는 신규 상태 노드를 각각 부모 노드 및 자식 노드로 상기 상태 트리에 등록하는 단계를 포함하는 것을 특징으로 하는 RRT 기반의 듀얼 트리 구조를 이용한 이동 로봇의 궤적 계획 방법.

제1항에 있어서,상기 (d) 단계에서는 기 등록된 궤적 생성 알고리즘에 기초하여 상기 후보 상태 노드와 상기 신규 포인트 간의 상기 후보 경로 비용을 산출하는 것을 특징으로 하는 RRT 기반의 듀얼 트리 구조를 이용한 이동 로봇의 궤적 계획 방법.

제2항에 있어서,상기 후보 경로 비용은 상기 후보 상태 노드로부터 기 설정된 깊이의 부모 노드까지의 경로 비용이 포함되어 산출되는 것을 특징으로 하는 RRT 기반의 듀얼 트리 구조를 이용한 이동 로봇의 궤적 계획 방법.

제3항에 있어서,상기 (d) 단계는(d1) 상기 각 후보 상태 노드와 상기 신규 포인트를 상기 궤적 생성 알고리즘에 적용하여 상기 각 후보 상태 노드에 대한 후보 신규 상태 노드를 추출하고, 상기 각 후보 상태 노드와 상기 신규 포인트 간의 상기 후보 경로 비용을 산출하는 단계와,(d2) 상기 후보 상태 노드 중 최소의 상기 후보 경로 비용을 갖는 후보 상태 노드를 상기 최소 비용 부모 상태 노드로 추출하는 단계를 포함하며;상기 최소 비용 부모 상태 노드에 대응하는 상기 후보 신규 상태 노드가 상기 신규 작업 공간 노드에 대응하는 상기 신규 상태 노드로 등록되는 것을 특징으로 하는 RRT 기반의 듀얼 트리 구조를 이용한 이동 로봇의 궤적 계획 방법.

제4항에 있어서,상기 (d2) 단계에서 상기 후보 신규 상태 노드가 상기 신규 포인트를 중심으로 기 설정된 오차 범위 내에 위치하지 않는 경우, 해당 후보 상태 노드는 상기 최소 비용 부모 상태 노드의 후보에서 제외되는 것을 특징으로 하는 RRT 기반의 듀얼 트리 구조를 이용한 이동 로봇의 궤적 계획 방법.

제1항에 있어서,(f) 상기 신규 작업 공간 노드와 상기 신규 상태 노드에 기초하여 노드를 재연결하는 단계를 더 포함하는 것을 특징으로 하는 RRT 기반의 듀얼 트리 구조를 이용한 이동 로봇의 궤적 계획 방법.

제6항에 있어서,상기 (f) 단계는(f1) 상기 신규 작업 공간 노드를 중심으로 기 설정된 경계 범위 내의 복수의 작업 공간 노드 각각이 예비 작업 공간 노드로 등록되는 단계와;(f2) 상기 신규 작업 공간 노드로부터 상기 각 예비 작업 공간 노드로의 확장을 통해, 상기 복수의 예비 작업 공간 노드 중 최소의 경로 비용을 형성하는 어느 하나가 최소 비용 작업 공간 노드로 추출되고, 상기 신규 작업 공간 노드에 대응하는 상태 노드와 상기 신규 작업 공간 노드의 부모 노드에 대응하는 적어도 하나의 상태 노드 중 최소의 경로 비용을 형성하는 어느 하나가 최소 비용 상태 노드로 추출되는 단계와;(f3) 상기 신규 작업 공간 노드와 상기 최소 비용 작업 공간 노드와 연결하는 단계와;(f4) 상기 최소 비용 상태 노드와 상기 최소 비용 작업 공간 노드에 대응하는 상태 노드를 연결하는 단계와;(f5) 상기 최소 비용 상태 노드와 연결된 상태 노드의 부모 상태 노드와 자식 상태 노드를 연결하는 단계를 포함하는 것을 특징으로 하는 RRT 기반의 듀얼 트리 구조를 이용한 이동 로봇의 궤적 계획 방법.

제7항에 있어서,상기 (f1) 단계에서 상기 신규 작업 공간 노드의 부모 노드는 상기 예비 작업 공간 노드의 추출에서 제외되는 것을 특징으로 하는 RRT 기반의 듀얼 트리 구조를 이용한 이동 로봇의 궤적 계획 방법.

제8항에 있어서,상기 (f2) 단계는(f21) 상기 복수의 예비 작업 공간 노드 중 어느 하나를 추출하는 단계와,(f22) 상기 신규 작업 공간 노드의 부모 노드에 대응하는 적어도 하나의 상태 노드와, 상기 신규 작업 공간 노드에 대응하는 상태 노드가 상태 트리로부터 추출되어 재연결 후보 상태 노드로 등록되는 단계와,(f23) 상기 각 재연결 후보 상태 노드와 상기 추출된 예비 작업 공간 노드를 기 설정된 궤적 생성 알고리즘에 적용하여 상기 각 재연결 후보 상태 노드에 대한 재연결 후보 신규 상태 노드를 추출하고, 상기 각 재연결 후보 상태 노드와 상기 신규 작업 공간 노드에 대응하는 상태 노드 간의 재연결 후보 경로 비용을 산출하는 단계와,(f24) 상기 재연결 후보 상태 노드 중 최소의 재연결 후보 경로 비용을 갖는 어느 하나를 상기 최소 비용 상태 노드로 추출하는 단계를 포함하며;상기 각 예비 작업 공간 노드에 대해 상기 (f21) 단계 내지 (f24) 단계를 수행하여, 상기 최소 비용 작업 공간 노드 및 상기 최소 비용 상태 노드를 추출하는 것을 특징으로 하는 RRT 기반의 듀얼 트리 구조를 이용한 이동 로봇의 궤적 계획 방법.

제1항 내지 제9항 중 어느 한 항에 있어서,(h1) 상기 이동 로봇의 주행을 불가능하게 하는 주행 불능 작업 공간 노드를 검출하는 단계와;(h2) 상기 주행 불능 작업 공간 노드를 삭제하는 단계와;(h3) 상기 주행 불능 작업 공간 노드의 삭제에 따라 발생하는 고아 작업 공간 노드를 해당 고아 작업 공간 노드에 대응하는 상태 노드의 부모 노드에 해당하는 작업 공간 트리에 연결하는 단계를 더 포함하는 것을 특징으로 하는 RRT 기반의 듀얼 트리 구조를 이용한 이동 로봇의 궤적 계획 방법.