Advanced
A Study on the Parallel Escape Maze through Cooperative Activities of Humanoid Robots
A Study on the Parallel Escape Maze through Cooperative Activities of Humanoid Robots
Journal of the Korea Institute of Information and Communication Engineering. 2014. Jun, 18(6): 1441-1446
Copyright © 2014, The Korea Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : May 01, 2014
  • Accepted : June 09, 2014
  • Published : June 30, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
봉기 전
bgjun@silla.ac.kr

Abstract
본 논문에서는 로봇군집이 미로 탈출을 위해 협력하는 방법에 대해 제안되었다. 로봇은 센서를 통해 필수적인 데이터를 수집하고 판단하여 자율적으로 움직일 수 있다. 하지만 미로 탈출을 위해 협력하기 위해서는 중앙 시스템이 여러 로봇들을 제어할 필요가 있다. 로봇들은 보이지 않는 미로를 탐색하며, 탈출 경로를 위한 분석과 지도를 만들기 위해 이동과 같은 정보를 중앙제어시스템에 전송한다. 여러 대의 로봇들이 미로를 효과적으로 탈출하기 위해서, 이 논문에서는 다음과 같은 문제를 고려하였다. 첫째, 로봇들이 미로 영역을 나누어서 탐색하기. 둘째, 벽으로 막혀 있는 막다른 골목을 찾아서 다른 로봇이 진입하지 못하도록 하기. 셋째, 목적지에 먼저 도착한 로봇이 최단 경로를 만들어 다른 로봇이 빨리 탈출할 수 있도록 하기. 위의 3가지를 고려하여 미로 동시 탈출을 위한 알고리즘을 구현하여 다양한 미로 크기별로 실험하였다.
Keywords
Ⅰ. 서 론
지능형 로봇을 간략하게 정의하면 외부환경을 인식하고, 스스로 판단하여, 자율적으로 동작하는 로봇을 지칭한다 [1] . 로봇에 탑재된 여러 가지 센서로 부터 현재의 로봇상태 및 주위환경에 대한 상황을 판단하고 자율적으로 동작하는 기능이 추가된 것이다.
본 논문에서 사용한 인간형 로봇은 자이로 센서로 보행 중 자세 보정을 할 수 있으며, 절대 거리 센서를 3개 부착하여 벽을 인지한다 [2] . 노트북으로 구현한 중앙제어 시스템과 ZigBee 통신을 이용하여 여러 대의 로봇에 동시에 명령을 주는 방식으로 로봇들이 서로 협력하여 과제를 수행한다.
본 논문에서의 응용 대상은 군집로봇의 미로 탈출이다. 기존의 관련연구 [3 , 4] 와 달리 본 논문에서는 직립 보행하는 인간형 로봇의 특징을 고려한 협력작업을 연구하였다. 연구는 단계별로 진행하였으며 우선 하나의 로봇이 미로를 탈출하는 알고리즘을 개발하여 로봇의 센서 활용과 지능 부여에 대한 지식을 습득 후, 여러 로봇들이 동시에 미로에 들어가서 서로 협력하여 미로를 탈출하는 방법을 찾았다.
로봇은 센서를 통해 미로의 벽을 인지할 수 있으며, 자율적으로 벽에 부딪히지 않게 보행할 수 있도록 프로그래밍 하였다. 하지만 GPS 등의 측위기능이 없기 때문에 위치를 판단할 수 없다. 또한 자신의 이동경로나 상대의 이동경로를 비교분석하기에 로봇의 연산기능이 부족하여 서로 협력할 수 없다.
이러한 문제점을 해결하기 위하여 중앙제어 컴퓨터가 ZigBee 통신을 이용하여 여러 대의 로봇을 제어하도록 하였다. 이를 위해 로봇은 일정한 시간간격 마다 중앙제어 시스템으로 자신의 습득한 정보를 보내고, 이동에 대한 명령을 받는다.
본 논문의 목표는 여러 대의 로봇들이 협업을 통해 최대한 빨리 미로를 탈출하는 것이다. 로봇들은 미로의 구조를 알 수 없기 때문에, 서로 다른 경로로 탐색하도록 하여 동시에 여러 경로를 탐색하도록 하였다. 2장에서 로봇들이 경로를 나누어서 탐색하는 방법을 기술하였다. 3장에서 서로 탐색한 경로를 다시 방문하지 않도록 Dead-End 개념을 도입하여 알고리즘을 개선하였다. 4장에서는 먼저 도착한 로봇이 계산한 최단경로를 다른 로봇들에게 제공하도록 알고리즘을 수정하여 성능을 비교하였다. 그리고 로봇들의 회전비용과 마주침 현상에 대해 기술하였다. 마지막으로 5장에서 결론 및 향후 연구를 기술한다.
Ⅱ. 군집 로봇의 협업 문제
군집로봇의 미로 탈출 알고리즘은 크게 출구를 빨리 찾아가기 위한 탐색 주행 알고리즘과 집단 탈출을 위한 최단 경로를 찾는 알고리즘이 있다.
로봇의 협력 탐색 주행 알고리즘은 기존의 마이크로 마우스 주행 알고리즘과 비슷하지만 서로 협력하여 목표점을 찾아야 한다. 본 논문에서는 여러 대의 로봇이 동시에 미로를 탐색하는 방법을 구현하여 실험 하였다. 그림 1 은 구현된 미로 탈출 시뮬레이터 화면으로 1대의 로봇이 미로를 탈출하는 경로를 화면에 표시하였다.
PPT Slide
Lager Image
미로 탈출 시뮬레이터 화면 Fig. 1 A screen shot of the escape maze simulator
본 논문에서는 다양한 크기의 미로들 [5] 을 대상으로 여러 대의 로봇이 협업하였을 때의 성능을 비교하였다. 로봇들이 미로를 탐색하고 탈출할 때 다음과 같은 문제들을 해결해야 한다. 첫째, 로봇들이 미로 영역을 나누어서 탐색하기. 둘째, 벽으로 막혀 있는 막다른 골목을 찾아서 다른 로봇이 진입하지 못하도록 하기. 셋째, 목적지에 먼저 도착한 로봇이 최단 경로를 만들어 다른 로봇이 빨리 탈출할 수 있도록 하기.
본 논문에서 해결해야 할 문제 사항은 여러 대의 로봇이 미로에 진입하여 모두 출구로 탈출하는 것이다. 로봇들은 서로 충돌하지 않도록 차례대로 입구를 통해 미로에 진입하며 출구 및 미로에 대한 정보를 알지 못한다.
미로 탐색은 되추적(Backtracking) 깊이 우선 검색 [6] 알고리즘을 사용하였으며, 다른 로봇들과 이동경로에 대한 정보를 공유해야하기 때문에 스택(Stack)을 이용하여 구현하였다.
미로에서 로봇은 한 블록씩 이동을 한다. 그림 2 에서와 같이 직진을 하는 로봇이 교차로를 만나면 진행방향을 선택해야 한다. 미로에서 동서남북으로 방향을 정하였을 때, 그림 2 에서 로봇은 직진, 좌회전, 우회전을 선택할 수 있다. 이 논문에서는 입구가 북쪽에 있고, 출구가 남쪽에 있어 남, 동, 서, 북 순서로 진입한다.
PPT Slide
Lager Image
교차로에서 진입 선택 Fig. 2 Choice the entry at the intersection
여러 대의 로봇이 미로를 탐색하면 다른 로봇이 진입한 방향을 제외한 다른 경로를 탐색해야 한다. 표 1 은 한 블록에서 다음 블록으로 이동할 때, 벽의 위치와 다른 로봇의 경로를 고려한 진입 방향 선택 알고리즘이다. 다른 로봇이 지나간 방향은 낮은 우선순위로 저장함으로서 로봇들이 영역을 나누어서 탐색할 수 있게 된다.
진행 방향 선택 알고리즘Table. 1The direction choice algorithm
PPT Slide
Lager Image
진행 방향 선택 알고리즘 Table. 1 The direction choice algorithm
표 2 표 1 의 진행 방향 알고리즘을 적용하여 3대의 로봇이 크기별 미로를 탈출하기 위해 지나간 블록의 개수를 보여준다. 표 2 의 왼쪽에는 하나의 로봇으로 탈출하기 위해 탐색 경로의 블록 수를 보여준다. 표 2 의 오른쪽에는 로봇 별로 방문한 블록 수를 보여준다. 여러대의 로봇으로 영역을 나누어 탐색하지만 서로 겹치는 경로가 많다는 문제가 있다.
진행 방향 선택 알고리즘의 성능 비교Table. 2The performance comparison of the simple direction choice algorithm
PPT Slide
Lager Image
진행 방향 선택 알고리즘의 성능 비교 Table. 2 The performance comparison of the simple direction choice algorithm
Ⅲ. 협력 탐색에서 경로 정보 공유
- 3.1. 탈출 경로가 있는 미로
하나의 로봇이 탐색을 하면 한번 지나간 경로를 다시 지나가지는 않는다. 하지만 여러 대의 로봇이 미로를 주행하면 같은 경로를 지나가게 된다. 하지만 막다른 골목으로 판단된 경로는 다른 로봇들이 방문을 할 필요가 없다.
본 논문에서는 그림 3 에서와 같이 A 1 , B, C 1 , D 1 블록에서 벽으로 둘러싸여 진입할 방향이 없는 경우를 Dead-End 블록으로 인지하여 다른 경로가 있는 교차로까지 돌아온다. 이때 그림 3 과 같이 A 0 , B, C 0 , D 0 블록을 Dead-End 블록으로 지정하여 다른 로봇이 진입하지 못하게 한다.
PPT Slide
Lager Image
막다른 골목이 있는 경로 Fig. 3 Dead-end Paths
그림 4 는 가로x세로의 크기가 각각 15인 미로에서 2개의 로봇이 지나간 경로를 표시한 것이다. 그림 4 에서 어두운 색(붉은색)이 Dead-End 경로의 시작점과 끝점이다. 입구와 출구의 최단경로를 제외하면 대부분이 Dead-End 경로임을 알 수 있다.
PPT Slide
Lager Image
막다른 골목 표시 Fig. 4 Display of Dead-end Paths
표 3 은 로봇들이 찾아낸 막다른 골목을 표시하여 다른 로봇이 골목으로 진입하지 못하도록 알고리즘을 수정하여 성능 평가를 한 것이다.
막다른 골목 처리 알고리즘의 성능 비교Table. 3The performance comparison of the dead-end paths algorithm
PPT Slide
Lager Image
막다른 골목 처리 알고리즘의 성능 비교 Table. 3 The performance comparison of the dead-end paths algorithm
그림 5 표 1 의 진행 방향 선택 알고리즘과 막다른 골목 처리 알고리즘의 성능을 비교한 것이다. 단순 진행 방향 알고리즘에서 발생한 로봇들이 따라다니는 문제점을 막다른 골목으로 표시하여 진입하지 못하도록 함으로써 해결한 것을 알 수 있다.
PPT Slide
Lager Image
진행방향 선택 알고리즘과 막다른 골목 처리 알고리즘의 성능 비교 Fig. 5 The performance comparison of the simple direction choice & the dead-end path algorithms
- 3.2. 탈출경로가 없는 미로
그림 6 은 출구까지 가는 경로가 없는 막힌 미로의 예 이다. 이와 같은 경우에 로봇은 입구에서 가능한 모든 길을 탐색한 후 출구에 도달할 수 없음을 보고한다.
PPT Slide
Lager Image
탈출경로가 없는 미로 Fig. 6 Maze with no escape route
그림 6 과 같이 탈출 경로가 없는 미로에서는 여러대의 로봇이 우선순위를 조절하여 미로를 나누어서 탐색하여도 단순 진행방향 선택 알고리즘에서는 표 3 과 같이 모든 로봇이 같은 경로를 탐색해야 출구에 도달 할 수 없음을 알 수 있다. 하지만 막다른 골목 처리 알고리즘을 사용함으로써 다른 로봇이 표시한 막다른 골목에 진입하지 않음으로서 같은 경로를 탐색할 필요가 없기 때문에 표 3 과 같이 절반 이하의 시간으로 처리할 수 있다.
Ⅳ. 인간형 로봇의 특성 고려
본 논문에서 사용된 인간형 로봇은 통신이 가능하고 직립보행을 한다. 이러한 특징을 고려하여 미로 탈출 알고리즘에 적용하였다. 구현된 협업 알고리즘은 미로를 나누어서 병렬 처리하는 연구 [7 , 8 , 9] 와는 로봇의 특성들을 고려해야하기 때문에 차이가 있다.
- 4.1. 탈출경로의 전파
출구를 찾아가는 알고리즘에서 스택(Stack)를 이용한 되추적(Backtracking) 깊이 우선 검색[5]을 사용하였다. 본 논문에서는 3대의 로봇이 동시에 미로를 탐색하기 때문에 깊이 우선 탐색(DFS)을 너비 우선 탐색(BFS)과 비슷하게 수정하였다.
스택을 이용하는 이유 중에 하나가 제일 먼저 출구를 찾은 로봇의 이동경로를 이용하여 최단경로를 계산하기 위해서다. 다음과 같은 단계로 다른 로봇들이 출구로 유도된다.
  • ①제일 먼저 출구에 도착하면 다른 로봇의 탐색을 중지시킨다.
  • ② 스택에 저장된 이동경로를 이용하여 최단경로를 계산하여 공유한다.
  • ③ 탐색을 중지된 다른 로봇들은 하고 되추적 (Backtracking)하여 최단경로에 포함된 블록으로 돌아온다.
  • ④ 해당 로봇이 위치한 블록에서 출구까지의 최단경로를 복사하여 탈출을 유도한다.
선두 로봇이 찾아낸 최단경로 정보를 다른 로봇이 탈출하도록 사용함으로써 표 4 에서 두 번째, 세 번째 탈출 로봇보다 좋은 결과를 표 5 에서 보여주고 있다.
탈출경로가 없는 경우의 진행방향 선택 알고리즘과 막다른 골목 처리 알고리즘의 성능 비교Table. 4The performance comparison of the simple direction choice & the dead-end path algorithms in the case of a maze with no escape route
PPT Slide
Lager Image
탈출경로가 없는 경우의 진행방향 선택 알고리즘과 막다른 골목 처리 알고리즘의 성능 비교 Table. 4 The performance comparison of the simple direction choice & the dead-end path algorithms in the case of a maze with no escape route
최단 탈출경로 전파 알고리즘의 성능 비교Table. 5The performance comparison of the propagation of a optimal escape route algorithm
PPT Slide
Lager Image
최단 탈출경로 전파 알고리즘의 성능 비교 Table. 5 The performance comparison of the propagation of a optimal escape route algorithm
- 4.2. 로봇의 회전과 마주침 현상
직립보행을 하는 로봇은 바퀴로 움직이는 마이크로 마우스에 비해 회전비용이 많다. 로봇의 회전 비용은 좌회전, 우회전인 경우에 직진의 약 2~3배이다. 벽을 인지하여 회전하기 위해 중앙으로 뒷걸음으로 이동해야 하고 제자리에서 90도 회전해야 한다. U턴인 경우에는 약 4배 정도이다. 로봇의 협력 작업에서 중요하게 고려된 문제는 주행 중에 로봇들이 서로 만나는 것이다. 로봇이 만나는 이유는 2가지이다. 첫째는 그림 7(a)(b) 와 같이 블록별 회전 비용 차이 때문이다. 그림 7(a) 경우에는 앞선 로봇이 블록을 벗어날 때까지 뒤따르는 로봇이 대기한다. 그림 7(b) 경우에는 회전비용이 같기 때문에 2대의 로봇이 같이 회전한다.
PPT Slide
Lager Image
로봇의 이동 중에 발생하는 충돌 현상 Fig. 7 Collisions that occur during the movement of the robots
그림 7(c) 와 같이 로봇들이 서로 마주보고 만나게 되면 블록 내에서 서로 지나갈 수 없다. 이런 경우에는 루프(Loop)가 발생한 것으로 모두 돌아간다. 만약 돌아가서 선택될 경로가 남아있지 않는 경우에는 직진한다. 만약 둘 다 이런 경우에는 출구를 찾을 수 없는 미로이다. 본 논문에서 사용한 미로에서는 루프가 발생하지 않는다. 루프가 없는 미로에서 출구를 찾아갈 때에는 방향이 서로 같기 때문에 문제가 되지 않는다.
Ⅴ. 결 론
로봇은 벽 사이를 충돌 없이 걷기 위해 얼굴, 양쪽 어깨에 하나씩, 총 3개의 절대 거리 센서를 부착하였다. 어깨에 부착된 센서를 통해 자율적으로 향상 벽 사이의 가운데로 걷도록 프로그래밍 되었다. 로봇의 모션제어는 논문의 주제에서 벗어나 서술하지 않았다.
지능형 로봇의 협동 작업을 통해 미로를 효과적으로 탈출하기 위한 환경을 구축하고 중앙제어 시스템의 프로그램을 구현하였다.
여러 대의 로봇들이 협력하여 출구를 찾는 방법에 대해 연구하였으며, 알고리즘들을 적용하여 기존 방법과 성능 비교를 하였다.
추후연구로 탈출 경로를 찾는 방법에 A * 탐색과 같은 다양한 알고리즘을 적용하여 기존 방법과 성능 비교를 할 것이다.
BIO
전봉기(Bong-Gi Jun)
1991년 2월 : 부산대학교 컴퓨터공학과(공학사) 1993년 2월 : 부산대학교 컴퓨터공학과(공학석사)
1993년 3월 ~ 1998년 3월 KT연구소 전임연구원
2003년 8월 : 부산대학교 컴퓨터공학과(공학박사)
2003년 9월 ~ 현재 : 신라대학교 컴퓨터공학과 교수
※관심분야 : 알고리즘, 데이터베이스, 빅데이타, 스마트융합
References
Eom W. S. , Kim Y. K. , Lee J. H. , Choi G. H. , Sim E. S. 2013 “Development Trend of Intelligent Robots,” Current Industrial and Technological Trends in Aerospace 11 (1) 150 - 160
Jun B. 2013 "The cooperative work of Humanoid robots to escape from maze," the 3rd International Conference on Convergence Technology 1928 - 1929
Nuno S. 2011 "Implementation of Autonomous Robotic Cooperative Exploration and Goal Navigation," DSIE’11-6th Doctoral Symposium on Informatics Engineering
Hong K. C. 2010 "A Study of Solving Maze Escape Problem through Robots' Cooperation," Journal of the Korea AcademiaIndustrial cooperation Society http://dx.doi.org/10.5762/KAIS.2010.11.11.4167 11 (11) 4167 - 4173    DOI : 10.5762/KAIS.2010.11.11.4167
Foltin M. 2011 "Automated Maze Generation and Human Interaction," Diploma Thesis Maskryk University Faculty of Informatics 1 - 76
"Backtracking Algorithms," Stanford Computer Science 237 - 247
2012 "Parallel graph algorithms: Maze generator and solver," 1 - 5
Liu Y. , Xiao Y. 2013 "Parallel solution of maze optimal path based on ant colony algorithm," Proceedings of the 2nd International Conference on Computer Science and Electronics Engineering 1826 - 1829
Pershin Y. V. , Ventra M. D. 2011 "Solving mazes with memristors: a massively-parallel approach," Physical Review E http://dx.doi.org/10.1103/PhysRevE.84.046703 84 046703 -    DOI : 10.1103/PhysRevE.84.046703