로봇신문사
> 오피니언 > 학생칼럼
최단경로 미로탐색, 그 해법은?
폰트키우기 폰트줄이기 프린트하기 메일보내기 신고하기
승인 2015.04.27  00:10:26
트위터 페이스북 구글+ 밴드

AP 수업과 최단경로 미로탐색?

2014년 9월부터 12월까지 10명의 경기북과학고 학생들은 정보과학 분야의 대학과정 선이수제(AP)를 수강하였다. 강좌명은 ‘응용 프로그래밍’이었는데 정보 교과 시간에 학습한 프로그래밍 언어를 로봇 제어에 응용하는 방법을 배우는 내용이었다. 특히 이 강좌의 최종 미션은 최단경로의 계산을 바탕으로 효율적인 미로를 주행하는 알고리즘을 설계하고, 실제 주행 로봇에 적용하는 방법을 탐구하는 과정이었다. 본 AP에 참여한 학생들은 두 명씩 짝을 이루어 미션을 수행하였다.

최단경로 미로탐색이란 말 그대로 미로의 탐색을 통해 이곳을 주행할 수 있는 다양한 경로 중 최단 경로를 알아내는 것을 뜻한다. 다만 계산 알고리즘을 수행할 컴퓨팅 시스템 이외에도 미션 수행에 적합한 로봇의 기계 구조까지 고민해야 하는 융합 미션이다. 미션 해결을 위해 로봇이 해야 하는 과정은 다음과 같다. 미로의 출발점에서 시작하여 도착점까지 주어진 임의의 경로를 탐색하며 주행한 후 최단 경로를 알아낸다. 그런 다음 알아낸 최단 경로를 이용하여 도착점에서 다시 출발점까지 주행해야 한다. 이를 위해 각 팀들은 마인드스톰 NXT를 이용하여 미로 탐색에 적합한 로봇 구조를 설계하고, 최단경로 미로탐색에 필요한 여러 행동들을 로봇이 수행할 수 있도록 하는 소프트웨어를 작성하게 되었다.

미션에 사용된 미로 맵은 출발점과 도착점이 검정색 정사각형 모양으로 표시되어 있으며 경로는 검은색 라인으로 표시되어 있다. 이때 출발점, 도착점 그리고 모든 경로는 임의 설정된 것이다. 따라서 이 문제는 단순하게 정해진 경로를 주행하는 미션이 아니라, 알 수 없는 미로를 주행하는 미션이다.

나중에 알게 된 사실이지만, 이 미션은 산업통상자원부가 주최하고 정보통신산업진흥원(NIPA), 한국전자통신연구원(ETRI), 그리고 임베디드소프트웨어·시스템산업협회(KESSIA)에서 주관하는 임베디드 소프트웨어 경진대회 주니어분야 고등부 미션 중 4단계와 5단계로서 제시된 적이 있다고 한다. 당시에도 많은 학생들이 어려워하면서도 재미있게 해결하고자 했던 미션이라는 소개를 받으니 더욱 새로운 동기와 의지가 생기기도 하였다.
▲ 미션에 사용된 미로 맵(좌) 및 필자가 미션수행을 위해 제작한 로봇(우)

미션 수행을 위해 해결해야 할 문제들

최단경로 미로탐색 미션 수행에 있어서 해결해야 할 문제들과 가능한 해결 방법은 다음과 같다.

1. 로봇이 미로의 출발점에서 도착점까지 어떻게 도달할 것인가?
미로를 탈출하는 방법 중 가장 대표적인 것이 우수법과 좌수법이다. 미로의 오른쪽 벽 또는 왼쪽 벽을 손으로 짚고 앞으로 나아가면 어떠한 미로든지 탈출할 수 있다는 아이디어이다. 따라서 최단경로 미로탐색의 첫 번째 문제인 로봇이 미로의 출발점에서 도착점까지 주행하는 방법은 우수법 또는 좌수법을 통해 해결할 수 있다. 여기에서는 우수법을 사용했다.

2. 로봇이 검은색 라인을 어떻게 따라가게 만들 것인가?
로봇이 우수법 또는 좌수법을 사용하여 미로 탈출을 하기 위해서는 미로 맵의 경로, 즉 검은색 라인을 따라갈 수 있어야 한다. 라인을 따라가는 보편적인 방법에는 빛 센서를 이용한 제어 기법이 있다. 이는 맵의 바탕과 경로의 검은 라인의 빛 센서 값이 다름을 이용한 제어 기법으로, 빛 센서 값에 따라 주행 방향을 바꾸면서 라인을 따라갈 수 있다. 여기에서는 빛 센서 하나만으로 라인을 따라가는 1-Light Sensor 기반의 On/Off Control 알고리즘을 사용하였다.

3. 로봇이 교차로 구간 또는 출발점, 도착점을 어떻게 인식하게 할 것인가?
로봇이 교차로 구간과 출발점, 도착점을 인식할 때에도 빛 센서를 사용한다. 다만 교차로의 종류가 다양할 수 있기 때문에 로봇의 양쪽에 빛 센서를 장착함으로써 이것들의 차이를 인식하게 해야 한다. 교차로를 정확하게 인식한 후에는 로봇이 어떠한 방향으로 주행해야할 지가 결정되어야 한다. 앞서 언급하였듯이 미로 탈출을 위한 방법으로 우수법을 사용하였기 때문에 “우회전-직진-좌회전” 순으로 주행의 우선순위를 갖게 된다. 따라서 오른쪽으로 꺾인 경로가 포함된 모든 교차로에서 로봇은 우회전을 하게 된다.

하지만 시작점과 도착점 모두 검은 사각형으로 표시되어 있기 때문에 로봇이 이를 양방향으로 꺾인 경로로 인식하고 우회전을 할 수도 있다. 따라서 양방향으로 꺾인 경로의 경우 약간의 전진을 통해 전방에 출발점과 도착점을 알리는 사각형이 존재하는지 확인할 필요가 있다. 교차로를 구성하는 라인들의 두께를 확인한다고 생각하면 적절하다. 만일 전진한 뒤에도 양쪽 빛 센서가 검은 라인을 인식한다면, 라인의 두께가 매우 두껍다는 뜻이 된다. 따라서 이곳은 출발점 또는 도착점이기 때문에 멈추어야 한다. 만일 그렇지 않다면 이곳에서는 우회전을 해야 한다. 반면 오른쪽으로 꺾인 경로 없이, 왼쪽으로 꺾인 경로만이 포함된 교차로에서는 로봇 전방에 직진을 할 수 있는 경로가 있을 수 있기 때문에 약간의 전진을 통해 전방의 경로 유무를 확인해야 한다. 전방에 경로가 있다면 주행의 우선순위에 따라 로봇은 직진을 하게 되고, 그렇지 않다면 좌회전을 하게 된다.

마지막으로 로봇이 미로의 막다른 길에 다다르면 유턴을 해야 한다. 막다른 길의 경우 라인트레이싱을 하는 빛 센서와 꺾인 경로를 인식하는 좌우 빛 센서 모두 흰색 바탕을 지속적으로 인식하기 때문에 일정 시간 이상 모든 빛 센서가 흰색 바탕을 인식할 때 로봇을 유턴시키면 된다. 이러한 과정을 통해 우수법을 이용한 미로 탐색 및 탈출을 구현할 수 있다.
▲ 역삼각형 구조의 빛 센서 배치(좌)과 다양한 꺾인 경로(우)
4. 로봇이 도착점까지의 주행에 성공하였다면 최단경로는 어떻게 찾을 것인가?
최단경로를 계산하기 위해서는 우수법을 통해 미로를 탐색하는 과정에서 얻게 되는 정보를 저장하고 처리해야 한다. 따라서 로봇이 직진을 했는지, 우회전을 했는지 등을 저장할 수 있는 배열을 만들어 로봇이 교차로를 만날 때마다 실제 회전한 방향을 기록해야 한다. 로봇이 미로 탈출을 위해 주행한 경로 중 최단경로를 찾기 위해 제외되어야 할 경로는 막다른 길이다. 여기에서는 막다른 길을 쉽게 계산하기 위해 회전 방향마다 특정 숫자를 부여하였다. 예를 들어 우회전은 1, 직진은 2, 좌회전은 3, 유턴은 4를 부여하는 방식이다. 이를 위해서 간단한 비례 관계를 통해 유도한 방정식을 활용하였다.

구체적인 최단 경로의 계산 과정은 다음과 같다. 로봇이 막다른 길에 다다르면 유턴을 하게 되는데 이 때 여기에 해당되는 숫자 4가 배열에 저장된다. 이럴 경우 그 경로(숫자 4)를 배열에서 삭제하고, 이후에 저장되는 숫자를 배열의 삭제된 칸 이전 칸에 저장된 숫자에 더하게 된다. 만일 더한 수가 4가 된다면 이를 다시 삭제하고, 이후에 저장되는 숫자를 배열의 삭제된 칸 이전 칸에 저장된 숫자에 더하는 것을 반복한다. 이러한 과정을 통해 로봇은 새로운 경로, 즉 최단경로를 계산하고, 배열에 저장하게 된다. 이해를 돕기 위해 한 가지 예시를 제시한다.

'ㅏ'자 경로의 아래쪽은 로봇이 주행해 오는 방향, 오른쪽은 막다른 길, 위쪽은 도착점으로 가기 위한 경로라고 가정하자. 로봇은 우수법을 사용하기 때문에 교차로에서 우회전을 하고 배열의 첫 번째 칸에 1이 저장된다. 이후에 막다른 길을 만나 유턴을 하게 되어 배열의 두 번째 칸에 4가 저장된다. 이 때 저장된 수가 4이므로 이를 배열에서 삭제한다. 유턴을 한 뒤에 로봇은 다시 교차로에 위치하고 우회전을 하면서 배열에 1을 저장한다. 이때 바로 이전에 4를 배열에서 삭제하였으므로 배열의 첫 번째 칸에 1을 더하게 된다. 이 과정을 마치면 배열에 남는 수는 첫 번째 칸의 2로서 이는 교차로를 만날 경우 직진을 하라는 뜻이 된다.
▲ ‘ㅏ’자형 미로의 최단경로 계산 방법. 좌측 미로는 탐색 과정에서의 경로이고, 우측 미로는 이를 이용하여 계산한 최단경로이다. 오른쪽 표는 각 행동별 배열의 상태이다.
5. 다시 출발점으로 돌아갈 때 어떤 방법으로 최단경로로 돌아갈 것인가?
로봇이 미로를 탐색하고, 동시에 최단경로를 계산하면서 도착점에 도착하게 되면 이제는 계산한 최단경로로 출발점까지 돌아가야 한다. 따라서 교차로를 만날 때마다 배열에 저장된 최단경로를 불러올 필요가 있다. 이 때 로봇은 왔던 길을 돌아가야 하므로 최단경로를 저장하고 있는 배열 값을 역순으로 호출해야 하며, 배열에 저장된 우회전을 좌회전으로, 좌회전을 우회전으로 바꾸어주어야 한다.

이러한 과정을 모두 거치면 로봇은 미로를 탐색하며 도착점까지 도달한 뒤, 최단경로로 출발점까지 주행하게 된다.

값진 경험이 되어준 AP수업

지금까지의 내용은 필자가 소속된 팀이 미션을 해결한 구체적인 방법이다. AP에 참여했던 다른 팀들 중에서도 매우 재미있고 창의적인 아이디어로 문제를 해결한 친구들이 있었다. 라인의 경계(edge)를 따라가는 일반적인 라인트레이싱을 사용하지 않고, 라인의 중앙을 따라가는 라인트레이싱을 보여준 팀도 있었고, 미로를 한 좌표계로 취급하여 최단경로를 계산한 팀도 있었다. 이러한 친구들의 모습을 지켜보면서 어떠한 문제가 주어졌을 때 이를 해결할 수 있는 방법이 매우 다양할 수 있음을 몸소 느끼게 되었다.

공학자는 자연이 주는 문제를 푸는 것이 아닌 인간 스스로가 만들어내는 다양한 문제들을 해결하는 사람이다. 모든 문제가 그렇지만 특히 새롭게 만들어진 문제를 해결하는 것에는 왕도나 정석이 없다. 따라서 공학자는 문제 해결의 다양한 방법들을 두루 살필 수 있어야 한다고 생각한다. 본 AP 과정에 참여한 모든 친구들도 이와 같은 교훈을 얻을 수 있었을 것이다. 최단경로 미로탐색의 해결 방법을 찾아보고 미션을 해결한 것 자체가 가지는 의미뿐만 아니라, 다양한 생각을 함께 나눌 수 있게 해준 세달 간의 AP 수업은 미래의 공학도가 되고 싶은 우리에게 앞으로 나아가야 할 비전을 제시해주는 매우 값진 경험이 되었다고 생각한다.이찬호 ㆍ경기북과학고 2학년

로봇신문사  webmaster@irobotnews.com
로봇신문사의 다른기사 보기  
폰트키우기 폰트줄이기 프린트하기 메일보내기 신고하기
트위터 페이스북 구글+ 밴드 뒤로가기 위로가기
이 기사에 대한 댓글 이야기 (0)
자동등록방지용 코드를 입력하세요!   
확인
- 200자까지 쓰실 수 있습니다. (현재 0 byte / 최대 400byte)
- 욕설등 인신공격성 글은 삭제 합니다. [운영원칙]
이 기사에 대한 댓글 이야기 (0)
최근인기기사
1
코리아씨이오서밋, '미래는 규제할 수 없다'의 저자 구태언 변호사 초청 강연회 가져
2
요꼬가와전기, AI 활용 이미지 분석 기업 덴마크 '그라츠퍼' 인수
3
LG전자, 권봉석·배두용 대표이사 선임
4
'헴닷에이아이', 시드 머니 1300만 달러 확보
5
한국로봇융합연구원-뉴로메카, 첨단제조로봇 기술개발 협력
6
대만 타이난시, LILEE 시스템과 손잡고 자율주행 버스 전격 도입
7
일본 히타치, 커뮤니케이션 로봇 '에뮤' 사업 본격화
8
'2020년 대구 스마트시티 생활융합형 서비스 로봇 시범사업' 추진
9
미 일리노이대, 의료용 아바타 로봇 '아바트리나' 개발한다
10
아카라 로보틱스, 살균 로봇 '바이올렛(Violet)' 개발
로봇신문 소개기사제보광고문의불편신고개인정보취급방침이메일무단수집거부청소년보호정책    *국제표준간행물번호 ISSN 2636-0381 *본지는 인터넷신문위원회 자율심의 준수 서약사입니다
08298) 서울 구로구 공원로 41(구로동, 현대파크빌 427호)  |  대표전화 : 02)867-6200  |  팩스 : 02)867-6203
등록번호 : 서울 아 02659  |  등록일자 : 2013.5.21  |  발행인·편집인 : 조규남  |  청소년보호책임자 : 박경일
Copyright © 2013 로봇신문사. All rights reserved. mail to editor@irobotnews.com