(Choset H.M.의 책 Principles of robot motion: theory, algorithms, and implementation 참조, Siegwart의 책 Introduction to Autonomous Mobile Robots 참조)
Bug1 Algorithm
Bug1 알고리즘은 Bug 알고리즘 중 가장 단순한 알고리즘이다. 알고리즘은 다음과 같이 동작한다.
1) 목표위치를 항해 전진한다.
2) 목표위치에 도달하면 종료.
3) 장애물을 만나면 장애물의 외곽을 따라 움직인다.
3-1) 움직이는 동안 현재위치와 목표위치의 거리를 계산한다.
3-2) 현재위치와 목표위치의 최소 거리가 되는 위치를 기억한다.
4) 장애물을 한 바퀴 돌아 장애물을 처음 만난 위치로 돌아오면 최소 거리가 되는 위치로 간다.
5) 최소 거리가 되는 위치에서 장애물을 탈출하여 1번 과정부터 반복한다.
Bug2 Algorithm
Bug1 장애물의 외곽을 한 바퀴 돌아 장애물을 탈출하기때문에 비효율적인 알고리즘이다. Bug2 알고리즘은 장애물을 한 바퀴 돌지 않고도 장애물을 탈출하도록 하였다. 알고리즘은 다음과 같이 동작한다.
1) 시작위치와 목표위치를 연결하는 직선을 따라 목표위치로 이동한다.
2) 목표위치에 도달하면 종료.
3) 장애물을 만나면 장애물의 외곽을 따라 움직인다.
3-1) 외곽을 따라가다가 직선과 교차점을 만나게 되면 1번 과정부터 반복한다.
이 알고리즘은 나선형 소용돌이와 같은 장애물을 만나게 되면 Bug1 알고리즘보다 더 비효율적으로 움직이는 경우가 발생한다.
Tangent Bug Algorithm
Tangent Bug 알고리즘은 로봇과 주변 장애물간의 거리 측정이 가능한 360도 전방향 센서를 기반으로 한다. 이 알고리즘은 Bug2 알고리즘과 달리 장애물을 따라 움직이는 도중에 최단 거리가 발견되면 바로 목표를 향해 이동하게 된다. 알고리즘은 다음과 같이 동작한다.
1) 목표위치를 향해 이동한다.
2) 목표위치에 도달하면 종료.
3) 장애물이 목표위치를 가리게 되면, 장애물의 양 끝점을 각각 지나는 두 경로 중 짧은 경로를 선택하여 이동한다.
4) 지역 극소점에 빠진 경우(경로의 거리가 감소하다가 커지는 시점) 지역 극소 값을 기억하고 장애물의 외각을 따라 움직인다.
4-1) 목표위치에 도달하기 위한 경로의 비용이 기억된 지역 극소 값보다 작은 경우 장애물을 떠나 1번 과정부터 반복한다.
아래는 이동로봇과 스캐닝 레이저 센서를 시뮬레이션 하는 시뮬레이션 서버와 Tangent Bug 알고리즘을 실행하는 클라이언트 프로그램입니다.
* mobile_robot_simulation_bug 프로그램을 먼저 실행한 후, tangent_bug_client 프로그램을 실행하여야 합니다. 두 프로그램은 DCOM(RPC)로 연결됩니다.
Simulation Server:
Tangent Bug Client:
실행 동영상을 보시기 바랍니다. 첫번째가 시뮬레이션 서버 화면이고 두번째가 Tangent bug 클라이언트 화면 입니다.