미로찾기 라인트레이서 로봇 - 2편 맵을 탐색해보자!

 

미로찾기 라인트레이서 로봇 프로젝트! 이번엔 맵을 탐색하는 알고리즘을?

 

안녕하세요, 프매씨 입니다. 저번 1편에서는 프로젝트에 대한 간단한 설명과 라인트레이서 맵과 로봇에 대해 살펴보았습니다! 이번에는 본격적으로 프로그램의 알고리즘을 살펴보려고 합니다.

 

본 포스팅은 '프매씨의 프로젝트(http://pemassi.modoo.at)'에서 찾아볼 수 있습니다.

 

『미로찾기 알고리즘 어떻게 만들어야하지?』

 

로봇에서 사용할 알고리즘은 어떻게 프로그래밍 해야할까요?

 

먼저 컴퓨터에서 하던 미로찾기 알고리즘과 비교해보죠. 컴퓨터에서 생각하는 미로찾기는 오른쪽만 보면서 찾아가면 언젠가는 도착점에 도착할 수 있습니다. 그러면 최단거리를 알 수 있지요. 지금까지 왔던 길을 기록했기 때문에 돌아가면 되기 때문입니다. 다만 로봇에서는 벽을 보면서 찾아가는 것이 아니라, 아래에 있는 선을 따라 가기 때문에 오른쪽만 보고 갈 수는 있지만, 최단거리를 알 수 없는 문제가 있습니다. 아무리 지금까지 왔던 길을 기록했더라도 회전을 했느냐 안했느냐라는 정보밖에 없을 뿐, 잘못 된 길이였다는 여부는 모르기 때문이죠. 더욱 정확한 이유는 맵이라는 데이터가 로봇에는 없기 때문입니다. (컴퓨터에서 했던 알고리즘은 미리 미로의 전체경로 데이터를 입력합니다)

 

'컴퓨터, 로봇'의 알고리즘의 차이점

1. 컴퓨터는 벽을 보고 따라가지만, 로봇은 선을 보고 따라간다.

2. 컴퓨터는 맵에 대한 데이터를 미리 알고있지만 로봇은 모른다.

 

위 2가지의 차이점 때문에 로봇에서는 컴퓨터의 환경과 유사한 조건을 만들기 위해 맵에 대한 정보를 모아야만 합니다.

 

 

『어떠한 정보들이 필요할까?』

 

로봇에는 미로에 대한 정보가 없기 때문에 직접 탐색하면서 정보를 기록해야 합니다. 그럼 필요한 정보는 무엇이 있을까요?

맵에서 필요한 정보는 크게 교차로의 종류, 선의 끊어짐의 여부, 턴 지점의 여부 입니다.

 

'맵으로 부터 얻어야할 정보'

1. 교차로의 종류

2. 끊어짐의 여부

3. 턴 지점의 여부

 

교차로의 종류는 교차로가 왼쪽에만 있는지, 오른쪽에만 있는지, 양쪽에 있는지를 판단하여 기록되는 정보 입니다. 이 정보는 로봇이 어느 방향으로 회전해야하는지 판단하기 위해서 사용될 것이며, 만약 교차로가 없으면 선의 끊어졌다는 것을 알 수 있는 정보가 되죠.

이어서 선이 끊어졌다는 것을 알게되면, 미로에서 틀린 길을 찾아왔다는 것을 알게되죠. 그러면 이전의 위치로 이동하면 됩니다.

턴 지점의 여부 같은 경우 말 그대로 미로에서는 도착점에 도착했다고 판단되는 조건이 되는 정보입니다.

 

그러면, 알고리즘에서는 이 정보들을 어느 순서대로 얻어야 할까요? 프로그램에서는 아파트 형식으로 이벤트가 처리되고, if문(조건문)을 통해 순서대로 참인지 거짓인지 판단하기 때문에 처리 순위를 정해야 합니다. 저는 다음과 같이 정해보았습니다.

 

'맵으로 부터 얻은 정보 처리 순위'

1 순위 – 턴 지점의 여부

2 순위 - 끊어짐의 여부

3. 순위 – 교차로의 종류

 

가장 먼저, 로봇이 턴 지점에 도착했는지를 판단해야 합니다. 턴 지점에 도착했다면 이외의 정보가 필요없어지며, 최단거리를 계산하고 다시 시작점으로 돌아가면 되기 때문이죠.

두번째로, 턴 지점이 아니라면 선이 끊어졌음을 판단해야 합니다. 로봇이 선을 따라가면서 선이 끊어졌다면 앞서 말했듯이, 잘못된 길을 찾아왔기 때문에 다시 돌아가야 하기 때문이죠. 이외에 모든 경우에서는 교차로의 종류를 파악하고 어느 방향으로 회전할지 정해야 합니다.

 

『그럼, 맵을 탐색하는 동작을 만들어보자!』

[STEAM CUP(스팀컵)에서 제시된 라인트레이서 맵]

 

맵을 탐색하는 동작을 만들어보기 위해서는 간단한 맵이 있으면 생각하기 편해집니다. 저는 스팀컵에서 제시되는 라인트레이서 맵을 보면서 생각할려고 합니다. 그럼 맵을 탐색하기 위한 동작들을 단계별로 정리해보죠.

 

[로보티즈의 7채널 적외선 센서]

 

[SHARP PSD센서]

 

저는 턴 지점을 PSD센서로 인식하고 7개의 적외선 센서를 사용하고 있습니다.

7개의 센서 중 1번이나 7번이 만나면 교차로를 만났다고 판단합니다.

7개의 센서 중 모든 센서가 선을 인식하지 못한다면 선이 없다고 판단합니다.

 

"맵 탐색 동작 단계"

 

0. 턴의 우선방향을 정합니다.

탐색 시 양쪽에 교차로가 있을 경우 어느 방향으로 턴을 할지 정하는 기준이 됩니다. 설명에서는 우선방향을 "왼쪽"으로 정하겠습니다.

 

1. 다음 교차로를 만날 때 까지 로봇을 라인트레이싱 한다. (교차로를 만나면 선을 넘어가지 않습니다.)

가장 기초적인 동적이 되겠습니다. 다음 교차로의 선을 넘어가지 않는 이유는 아래에서 확인.

 

2-A. 턴 지점이라고 판단되는 물체를 PSD센서가 인식한다면 탐색을 끝낸다.

PSD센서로 턴 지점을 인식했다면 지금까지 얻은 정보로 최단거리를 계산할 수 있을 것 입니다.

2-B. 모든 센서가 일정시간동안 선을 인식하지 못한다면 선이 없다고 판단하고 이 길은 오류라고 기록하면서, 이전에 있던 교차로로 돌아간다.

선을 인식하지 못했다면 로봇이 지금까지 왔던 길이 틀렸다는 것 입니다. 이전에 있던 교차로 위치로 다시 돌아갑니다.

2-C. 교차로를 인식했다면, 교차로에 있는 선을 넘어가면서 교차로의 종류를 파악한 후 정보를 기록합니다.

교차로에 있는 선을 넘어가면서 교차로의 종류를 파악한다는 동작을 이해못하시는 분들이 계실 것 같습니다. 아래 이미지를 보시면 이해할 수 있습니다.

[2-C 단계 설명]

교차로를 만나자 마자 멈추기 때문에 교차로에 있는 선을 넘어가면서 교차로의 종류를 파악할 수 있는 것 입니다.

 

3-B-1. 만약 이전에 있던 교차로가 양쪽인데, 이미 양쪽 교차로 모두 확인한 경우 또 다시 이전에 있던 교차로로 돌아가면서 이 교차로는 오류라고 기록한다.

이미 양쪽 교차로를 확인하면서도 턴지점을 만나지 못했기 때문에 이 교차로는 오류라는 것을 확인할 수 있습니다.

3-B-2. 만약 이전에 있던 교차로가 양쪽이라면, 우선방향에 의해 왼쪽을 이미 확인했으므로, 반대쪽인 오른쪽으로 턴을 한다.

우선방향을 오른쪽으로 한다면 왼쪽방향으로 턴하겠죠. 반대쪽에 있는 교차로에 도착점이 있을 수 도 있기 때문에 그 방향으로 턴을 합니다.

3-C. 왼쪽에만 교차로가 있다면 왼쪽으로 턴, 오른쪽에만 교차로가 있다면 왼쪽으로 턴, 양쪽에 교차로가 있다면 우선방향인 왼쪽으로 턴을 한다.

 

4-B. (1)번 단계로 이동합니다.

4-C. (1)번 단계로 이동합니다.

 

 

이 모든 과정을 프로그램으로 작성해보면 탐색 알고리즘은 완성됩니다. 과정 중에 기록해야하는 정보들은 [어떠한 정보들이 필요할까?]에서 말했듯이, 맵의 교차로 종류 입니다. 추가적으로 해당 교차로의 오류 여부와 양쪽 교차로 확인 여부가 되겠습니다.

 

'프로그램에서 기록해야할 정보들'

1. 교차로의 종류

2. 교차로의 오류 여부

3. 양쪽 교차로 확인 여부

 

위 정보들을 일일이 변수명을 선언해서 기록하는 것이 아니라 프로그램에서는 배열과 구조체를 사용하면 편하게 정보를 기록해둘 수 있습니다. C++언어에서는 다음과 같이 작성하시면 됩니다.

 

 

Map이라는 구조체를 만들었는데요? 그 구조체의 이름은 Mapping이며 총 101개의 1차원 배열을 생성하였습니다. error는 교차로의 오류 여부, checked는 양쪽 교차로 확인 여부, cross는 교차로의 종류가 되겠죠.

 

잘 모르시겠나요? 그래서 다음 편에서는 알고리즘을 만들기 위한 프로그래밍을 배워보려고 합니다. 실제로 제가 프로젝트를 진행하면서 필요하여 배웠던 부분이기 때문에 도움이 되실 거라고 생각합니다.

 

그럼 다음 편에서 뵈요~

 

본 포스팅은 원문을 수정하지 않고 가져가는 것 이외에는 허용하지 않으며,

'프매씨의 프로젝트(http://pemassi.modoo.at)'에서 이어서 볼 수 있습니다.