BUG 알고리즘 (예전자료)

 

네이버 블로그에 있는 글들을 하나씩 옮기고 있다. (2008.12월 작성)

모바일로봇 길찾기를 위한 매우 단순하고 기초적인 알고리즘이다. 그만큼 구현하기 쉽고 많이 쓰고있다.

단순하고 뇌(지능) 없이도 태스크를 수행할 수 있어서 버그알고리즘이라고 명명한것같다.

---

 

1. 가정, 로봇은...

(1) 맵상의 시작지점과 목표지점의 좌표를 알고있다.
(2) 맵상의 장애물의 범위, 즉,크기와 위치는 알 수 없다.
(3) 센서를 사용하여 유한한 범위내에서 장애물을 감지할 수 있다.
(4) 맵상(global)에서 자기위치를 알 수 있다. 즉,self-localization이 가능하다.

 

 

2. Bug 알고리즘 

 

(1) 시작위치와 목표위치를 연결한 직선 A를 따라 움직인다. 
(2) 장애물을 만나면 장애물의 외곽을 따라간다. 이때 외곽을 도는 방향은 임의로 선택.
(3) 외곽을 따라가다가 선 A를 만나게 되면 다시 (1)번 과정으로 되돌아간다.

(4) 장애물이 아닌 목표지점을 만나면 성공.

 

 

3. Bug 알고리즘 실행동영상

 

 

실행동영상을 보면 알겠지만 아직까지 프로그램에 버그(?)가 많다. 벽과 일정한 간격을 두지 못하고 벽에 완전히 붙게 가는 것과 코너를 돌거나 장애물이 감지되었을경우 방향을 급격히 틀면서 궤적이 약간 벗어나는 것 등 고쳐야 할 부분이 많다. 이 부분에 대해서 변명을 하자면 최대한 단순한 코드를 만들기 위한 어쩔수없는 선택이라고 해야 되나... 하지만 로봇의 Step 회전각도와 Step 이동정도, 센서범위를 적절히 튜닝한다면 분명히 이 문제를 해결할 수 있을 것이다.

 

 

4. 실패할 경우

 

 

다음으로 완전히 목표지점에 도달할 수 없는 경우가 있는데 위의 동영상이 그 예이다. 알고리즘이 단순히 외곽을 따라가다가 처음의 최단거리직선을 만나게 되면 무조건 직선을 따라가기 때문에 위의 동영상같은 경우에는 무한루프를 돌게 된다. 이것도 마찬가지로 내부 코드상에 직선을 만나게 되는 조건문을 약간 변경해주면 (최단거리 직선을 시작점 A와 끝점 B사이의 유한한 직선으로 설정한다면...) 해결이 가능하다.

 

마침.