For the escape from a maze, the cooperative method by robot swarm was proposed in this paper. The robots can freely move by collecting essential data and making a decision in the use of sensors; however, a central control system is required to organize all robots for the escape from the maze. The robots explore new mazes and then send the information to the system for analyzing and mapping the escaping route. Three issues were considered as follows for the effective escape by multiple robots from the mazes in this paper. In the first, the mazes began to divide and secondly, dead-ends should be blocked. Finally, after the first arrivals at the destination, a shortcut should be provided for rapid escaping from the maze. The parallel-escape algorithms were applied to the different size of mazes, so that robot swarm can effectively get away the mazes.
지능형 로봇을 간략하게 정의하면 외부환경을 인식하고, 스스로 판단하여, 자율적으로 동작하는 로봇을 지칭한다[1]. 로봇에 탑재된 여러 가지 센서로 부터 현재의 로봇상태 및 주위환경에 대한 상황을 판단하고 자율적으로 동작하는 기능이 추가된 것이다.
본 논문에서 사용한 인간형 로봇은 자이로 센서로 보행 중 자세 보정을 할 수 있으며, 절대 거리 센서를 3개 부착하여 벽을 인지한다[2]. 노트북으로 구현한 중앙제어 시스템과 ZigBee 통신을 이용하여 여러 대의 로봇에 동시에 명령을 주는 방식으로 로봇들이 서로 협력하여 과제를 수행한다.
본 논문에서의 응용 대상은 군집로봇의 미로 탈출이다. 기존의 관련연구 [3, 4]와 달리 본 논문에서는 직립 보행하는 인간형 로봇의 특징을 고려한 협력작업을 연구하였다. 연구는 단계별로 진행하였으며 우선 하나의 로봇이 미로를 탈출하는 알고리즘을 개발하여 로봇의 센서 활용과 지능 부여에 대한 지식을 습득 후, 여러 로봇들이 동시에 미로에 들어가서 서로 협력하여 미로를 탈출하는 방법을 찾았다.
로봇은 센서를 통해 미로의 벽을 인지할 수 있으며, 자율적으로 벽에 부딪히지 않게 보행할 수 있도록 프로그래밍 하였다. 하지만 GPS 등의 측위기능이 없기 때문에 위치를 판단할 수 없다. 또한 자신의 이동경로나 상대의 이동경로를 비교분석하기에 로봇의 연산기능이 부족하여 서로 협력할 수 없다.
이러한 문제점을 해결하기 위하여 중앙제어 컴퓨터가 ZigBee 통신을 이용하여 여러 대의 로봇을 제어하도록 하였다. 이를 위해 로봇은 일정한 시간간격 마다 중앙제어 시스템으로 자신의 습득한 정보를 보내고, 이동에 대한 명령을 받는다.
본 논문의 목표는 여러 대의 로봇들이 협업을 통해 최대한 빨리 미로를 탈출하는 것이다. 로봇들은 미로의 구조를 알 수 없기 때문에, 서로 다른 경로로 탐색하도록 하여 동시에 여러 경로를 탐색하도록 하였다. 2장에서 로봇들이 경로를 나누어서 탐색하는 방법을 기술하였다. 3장에서 서로 탐색한 경로를 다시 방문하지 않도록 Dead-End 개념을 도입하여 알고리즘을 개선하였다. 4장에서는 먼저 도착한 로봇이 계산한 최단경로를 다른 로봇들에게 제공하도록 알고리즘을 수정하여 성능을 비교하였다. 그리고 로봇들의 회전비용과 마주침 현상에 대해 기술하였다. 마지막으로 5장에서 결론 및 향후 연구를 기술한다.
군집로봇의 미로 탈출 알고리즘은 크게 출구를 빨리 찾아가기 위한 탐색 주행 알고리즘과 집단 탈출을 위한 최단 경로를 찾는 알고리즘이 있다.
로봇의 협력 탐색 주행 알고리즘은 기존의 마이크로 마우스 주행 알고리즘과 비슷하지만 서로 협력하여 목표점을 찾아야 한다. 본 논문에서는 여러 대의 로봇이 동시에 미로를 탐색하는 방법을 구현하여 실험 하였다. 그림 1은 구현된 미로 탈출 시뮬레이터 화면으로 1대의 로봇이 미로를 탈출하는 경로를 화면에 표시하였다.
본 논문에서는 다양한 크기의 미로들[5]을 대상으로 여러 대의 로봇이 협업하였을 때의 성능을 비교하였다. 로봇들이 미로를 탐색하고 탈출할 때 다음과 같은 문제들을 해결해야 한다. 첫째, 로봇들이 미로 영역을 나누어서 탐색하기. 둘째, 벽으로 막혀 있는 막다른 골목을 찾아서 다른 로봇이 진입하지 못하도록 하기. 셋째, 목적지에 먼저 도착한 로봇이 최단 경로를 만들어 다른 로봇이 빨리 탈출할 수 있도록 하기.
본 논문에서 해결해야 할 문제 사항은 여러 대의 로봇이 미로에 진입하여 모두 출구로 탈출하는 것이다. 로봇들은 서로 충돌하지 않도록 차례대로 입구를 통해 미로에 진입하며 출구 및 미로에 대한 정보를 알지 못한다.
미로 탐색은 되추적(Backtracking) 깊이 우선 검색[6] 알고리즘을 사용하였으며, 다른 로봇들과 이동경로에 대한 정보를 공유해야하기 때문에 스택(Stack)을 이용하여 구현하였다.
미로에서 로봇은 한 블록씩 이동을 한다. 그림 2에서와 같이 직진을 하는 로봇이 교차로를 만나면 진행방향을 선택해야 한다. 미로에서 동서남북으로 방향을 정하였을 때, 그림 2에서 로봇은 직진, 좌회전, 우회전을 선택할 수 있다. 이 논문에서는 입구가 북쪽에 있고, 출구가 남쪽에 있어 남, 동, 서, 북 순서로 진입한다.
여러 대의 로봇이 미로를 탐색하면 다른 로봇이 진입한 방향을 제외한 다른 경로를 탐색해야 한다. 표 1은 한 블록에서 다음 블록으로 이동할 때, 벽의 위치와 다른 로봇의 경로를 고려한 진입 방향 선택 알고리즘이다. 다른 로봇이 지나간 방향은 낮은 우선순위로 저장함으로서 로봇들이 영역을 나누어서 탐색할 수 있게 된다.
진행 방향 선택 알고리즘
표 2는 표 1의 진행 방향 알고리즘을 적용하여 3대의 로봇이 크기별 미로를 탈출하기 위해 지나간 블록의 개수를 보여준다. 표 2의 왼쪽에는 하나의 로봇으로 탈출하기 위해 탐색 경로의 블록 수를 보여준다. 표 2의 오른쪽에는 로봇 별로 방문한 블록 수를 보여준다. 여러대의 로봇으로 영역을 나누어 탐색하지만 서로 겹치는 경로가 많다는 문제가 있다.
진행 방향 선택 알고리즘의 성능 비교
하나의 로봇이 탐색을 하면 한번 지나간 경로를 다시 지나가지는 않는다. 하지만 여러 대의 로봇이 미로를 주행하면 같은 경로를 지나가게 된다. 하지만 막다른 골목으로 판단된 경로는 다른 로봇들이 방문을 할 필요가 없다.
본 논문에서는 그림 3에서와 같이 A1, B, C1, D1 블록에서 벽으로 둘러싸여 진입할 방향이 없는 경우를 Dead-End 블록으로 인지하여 다른 경로가 있는 교차로까지 돌아온다. 이때 그림 3과 같이 A0, B, C0, D0 블록을 Dead-End 블록으로 지정하여 다른 로봇이 진입하지 못하게 한다.
그림 4는 가로x세로의 크기가 각각 15인 미로에서 2개의 로봇이 지나간 경로를 표시한 것이다. 그림 4에서 어두운 색(붉은색)이 Dead-End 경로의 시작점과 끝점이다. 입구와 출구의 최단경로를 제외하면 대부분이 Dead-End 경로임을 알 수 있다.
표 3은 로봇들이 찾아낸 막다른 골목을 표시하여 다른 로봇이 골목으로 진입하지 못하도록 알고리즘을 수정하여 성능 평가를 한 것이다.
막다른 골목 처리 알고리즘의 성능 비교
그림 5는 표 1의 진행 방향 선택 알고리즘과 막다른 골목 처리 알고리즘의 성능을 비교한 것이다. 단순 진행 방향 알고리즘에서 발생한 로봇들이 따라다니는 문제점을 막다른 골목으로 표시하여 진입하지 못하도록 함으로써 해결한 것을 알 수 있다.
그림 6은 출구까지 가는 경로가 없는 막힌 미로의 예 이다. 이와 같은 경우에 로봇은 입구에서 가능한 모든 길을 탐색한 후 출구에 도달할 수 없음을 보고한다.
그림 6과 같이 탈출 경로가 없는 미로에서는 여러대의 로봇이 우선순위를 조절하여 미로를 나누어서 탐색하여도 단순 진행방향 선택 알고리즘에서는 표 3과 같이 모든 로봇이 같은 경로를 탐색해야 출구에 도달 할 수 없음을 알 수 있다. 하지만 막다른 골목 처리 알고리즘을 사용함으로써 다른 로봇이 표시한 막다른 골목에 진입하지 않음으로서 같은 경로를 탐색할 필요가 없기 때문에 표 3과 같이 절반 이하의 시간으로 처리할 수 있다.
본 논문에서 사용된 인간형 로봇은 통신이 가능하고 직립보행을 한다. 이러한 특징을 고려하여 미로 탈출 알고리즘에 적용하였다. 구현된 협업 알고리즘은 미로를 나누어서 병렬 처리하는 연구 [7, 8, 9] 와는 로봇의 특성들을 고려해야하기 때문에 차이가 있다.
출구를 찾아가는 알고리즘에서 스택(Stack)를 이용한 되추적(Backtracking) 깊이 우선 검색[5]을 사용하였다. 본 논문에서는 3대의 로봇이 동시에 미로를 탐색하기 때문에 깊이 우선 탐색(DFS)을 너비 우선 탐색(BFS)과 비슷하게 수정하였다.
스택을 이용하는 이유 중에 하나가 제일 먼저 출구를 찾은 로봇의 이동경로를 이용하여 최단경로를 계산하기 위해서다. 다음과 같은 단계로 다른 로봇들이 출구로 유도된다.
①제일 먼저 출구에 도착하면 다른 로봇의 탐색을 중지시킨다.② 스택에 저장된 이동경로를 이용하여 최단경로를 계산하여 공유한다.③ 탐색을 중지된 다른 로봇들은 하고 되추적 (Backtracking)하여 최단경로에 포함된 블록으로 돌아온다.④ 해당 로봇이 위치한 블록에서 출구까지의 최단경로를 복사하여 탈출을 유도한다.
선두 로봇이 찾아낸 최단경로 정보를 다른 로봇이 탈출하도록 사용함으로써 표 4에서 두 번째, 세 번째 탈출 로봇보다 좋은 결과를 표 5에서 보여주고 있다.
[표 4.] 탈출경로가 없는 경우의 진행방향 선택 알고리즘과 막다른 골목 처리 알고리즘의 성능 비교
탈출경로가 없는 경우의 진행방향 선택 알고리즘과 막다른 골목 처리 알고리즘의 성능 비교
최단 탈출경로 전파 알고리즘의 성능 비교
직립보행을 하는 로봇은 바퀴로 움직이는 마이크로 마우스에 비해 회전비용이 많다. 로봇의 회전 비용은 좌회전, 우회전인 경우에 직진의 약 2~3배이다. 벽을 인지하여 회전하기 위해 중앙으로 뒷걸음으로 이동해야 하고 제자리에서 90도 회전해야 한다. U턴인 경우에는 약 4배 정도이다. 로봇의 협력 작업에서 중요하게 고려된 문제는 주행 중에 로봇들이 서로 만나는 것이다. 로봇이 만나는 이유는 2가지이다. 첫째는 그림 7(a)(b)와 같이 블록별 회전 비용 차이 때문이다. 그림 7(a) 경우에는 앞선 로봇이 블록을 벗어날 때까지 뒤따르는 로봇이 대기한다. 그림 7(b) 경우에는 회전비용이 같기 때문에 2대의 로봇이 같이 회전한다.
그림 7(c)와 같이 로봇들이 서로 마주보고 만나게 되면 블록 내에서 서로 지나갈 수 없다. 이런 경우에는 루프(Loop)가 발생한 것으로 모두 돌아간다. 만약 돌아가서 선택될 경로가 남아있지 않는 경우에는 직진한다. 만약 둘 다 이런 경우에는 출구를 찾을 수 없는 미로이다. 본 논문에서 사용한 미로에서는 루프가 발생하지 않는다. 루프가 없는 미로에서 출구를 찾아갈 때에는 방향이 서로 같기 때문에 문제가 되지 않는다.
로봇은 벽 사이를 충돌 없이 걷기 위해 얼굴, 양쪽 어깨에 하나씩, 총 3개의 절대 거리 센서를 부착하였다. 어깨에 부착된 센서를 통해 자율적으로 향상 벽 사이의 가운데로 걷도록 프로그래밍 되었다. 로봇의 모션제어는 논문의 주제에서 벗어나 서술하지 않았다.
지능형 로봇의 협동 작업을 통해 미로를 효과적으로 탈출하기 위한 환경을 구축하고 중앙제어 시스템의 프로그램을 구현하였다.
여러 대의 로봇들이 협력하여 출구를 찾는 방법에 대해 연구하였으며, 알고리즘들을 적용하여 기존 방법과 성능 비교를 하였다.
추후연구로 탈출 경로를 찾는 방법에 A* 탐색과 같은 다양한 알고리즘을 적용하여 기존 방법과 성능 비교를 할 것이다.
