| 1 |
1
복수의 이동 로봇 간의 충돌 회피를 위한 경로 생성 방법에 있어서,(a) 상기 복수의 이동 로봇이 주행하는 주행 지도가 등록되는 단계와;(b) 각각의 상기 이동 로봇에 대해 초기 우선 순위, 출발지 및 목적지가 등록되는 단계와;(c) 각각의 상기 이동 로봇의 출발지로부터 목적지까지의 경로가 상기 주행 지도에 기초하여 생성되되, 상기 초기 우선 순위 순으로 순차적으로 생성되어 상기 이동 로봇의 경로 간의 충돌이 회피되어 생성되는 단계와;(d) 상기 (c) 단계에서 생성된 경로에 따라 각각의 상기 이동 로봇이 주행하는 단계와;(e) 상기 이동 로봇들의 주행 과정에서 상기 이동 로봇 간의 충돌을 예측하는 단계와;(f) 상기 (e) 단계에서 상기 이동 로봇 간의 충돌이 예측되는 경우, 충돌이 예측되는 한 쌍의 이동 로봇 간의 주행 우선 순위에 기초하여 상기 주행 우선 순위가 낮은 이동 로봇의 경로가 재생성되는 단계를 포함하며,상기 주행 우선 순위는현재 상기 이동 로봇의 위치로부터 충돌이 예측되는 노드 또는 에지까지의 경로 비용이 반영된 비용 기반 우선 순위와,상기 이동 로봇의 임무 중요도가 반영되는 임무 기반 우선 순위와,현재 상기 이동 로봇의 위치로부터 충돌이 예측되는 노드를 제외하고 재생성될 경로의 경로 비용이 반영된 재생성 경로 기반 우선 순위와,상기 초기 우선 수위, 상기 비용 기반 우선 순위, 임무 기반 우선 순위 및 상기 재생성 경로 기반 우선 순위 중 적어도 둘 이상의 조합에 기반한 조합 우선 순위 중 어느 하나를 포함하는 것을 특징으로 하는 복수의 이동 로봇의 충돌 회피를 위한 경로 생성 방법
|
| 2 |
2
제1항에 있어서,상기 (a) 단계에서 상기 주행 지도는 복수의 노드와 상기 노드 간을 연결하는 에지로 구성되는 것을 특징으로 하는 복수의 이동 로봇 간의 충돌 회피를 위한 경로 생성 방법
|
| 3 |
3
제2항에 있어서,상기 (c) 단계에서 생성되는 경로는 다익스트라(Djikstra) 알고리즘, A* 알고리즘, D* 알고리즘 중 어느 하나에 기초하여 생성되고;상기 (c) 단계에서 생성되는 경로는 경로 상의 노드 및 에지의 점유 시간에 대한 정보를 포함하며;상기 (c) 단계에서는 상기 초기 우선 순위에 따라 먼저 생성된 경로 상의 노드 및 에지의 상기 점유 시간에 따른 점유 여부가 저장되어, 이후의 경로 생성시 해당 점유 시간에서 점유된 노드 및 에지는 경로 생성에서 배제되는 것을 특징으로 하는 복수의 이동 로봇 간의 충돌 회피를 위한 경로 생성 방법
|
| 4 |
4
제3항에 있어서,상기 (c) 단계에서 상기 복수의 이동 로봇 중 충돌의 회피가 가능한 경로가 존재하지 않는 이동 로봇이 존재하는 경우, 해당 이동 로봇은 주행 대기 상태로 유지되는 것을 특징으로 하는 복수의 이동 로봇 간의 충돌 회피를 위한 경로 생성 방법
|
| 5 |
5
제2항에 있어서,상기 (e) 단계에서는 상기 복수의 이동 로봇 중 어느 하나의 이동 로봇과 나머지 이동 로봇 간의 충돌이 순차적으로 예측되며;상기 (f) 단계는(f1) 상기 (e) 단계의 수행 과정 중 상기 어느 하나의 이동 로봇과 충돌이 예측되는 경우, 해당 두 이동 로봇 간의 상기 주행 우선 순위가 비교되는 단계와,(f2) 상기 (f1) 단계에서 상기 어느 하나의 이동 로봇의 상기 주행 우선 순위가 낮은 경우, 상기 어느 하나의 이동 로봇의 경로가 재생성되는 단계를 포함하며;모든 이동 로봇에 대해 상기 (e) 단계, (f1) 단계 및 상기 (f2) 단계가 순차적으로 수행되는 것을 특징으로 하는 복수의 이동 로봇 간의 충돌 회피를 위한 경로 생성 방법
|
| 6 |
6
제5항에 있어서,상기 (f1) 단계에서 상기 어느 하나의 이동 로봇의 상기 주행 우선 순위가 높은 경우, 다음 순서의 이동 로봇에 대해 상기 (e) 단계, (f1) 단계 및 상기 (f2) 단계가 수행되는 것을 특징으로 하는 복수의 이동 로봇 간의 충돌 회피를 위한 경로 생성 방법
|
| 7 |
7
제5항에 있어서,상기 (c) 단계에서 생성되는 경로와 상기 (f) 단계에서 재생성되는 경로는 다익스트라(Djikstra) 알고리즘, A* 알고리즘, D* 알고리즘 중 어느 하나에 기초하여 생성되고;상기 (c) 단계 및 상기 (f) 단계에서 생성 및 재생성되는 경로는 해당 경로 상의 노드 및 에지의 점유 시간에 대한 정보를 포함하며;상기 (f) 단계에서는 상기 복수의 이동 로봇에 대해 기 생성된 경로 상의 노드 및 에지의 상기 점유 시간에 따른 점유 여부가 저장되어, 경로 재생성시 해당 점유 시간에서 점유된 노드 및 에지는 경로 생성에서 배제되는 것을 특징으로 하는 복수의 이동 로봇 간의 충돌 회피를 위한 경로 생성 방법
|
| 8 |
8
제7항에 있어서,상기 (f) 단계에서 재생성되는 경로가 기 등록된 대기 조건을 만족하는 경우, 해당 이동 로봇의 주행이 대기 상태로 전환되는 것을 특징으로 하는 복수의 이동 로봇의 충돌 회피를 위한 경로 생성 방법
|
