Bug Algorithms

Bug Algorithms

• 이동 로봇이 장애물을 피하면서 목표 지점으로 이동하는 간단한 local path planning이다.
• 주로 sensor data를 활용해서 환경을 직접 탐색 및 이동하니, 환경의 전체적인 맵을 미리 알 필요는 없다.
  • 이는 온보드 센서( LiDAR , 초음파 센서 , 거리센서 )를 사용해서 장애물을 감지하고, 기본적인 이동 규칙에 따라서 목표지점까지 도달하는 방식이다.
• 알고리즘의 특징
  • 1. local planning : 환경의 전체적인 정보를 미리 알지 못하며, 센서 데이터를 기반으로 즉각적인 경로를 결정
  • 2. simple rule-based : 장애물을 만나면 특정한 규칙에 따라서 움직인다.
  • 3. low computational cost : a* , d*같은 경로 탐색 알고리즘보다 계산량이 적어서 h/w 요구 사항이 낮다.
  • 4. 비효율적일지도? : 최적 경로를 보장하지 않음.

 

Bug Algorithms의 주요 유형

• 버그 알고리즘은 가장 대표적인게 2가지이며, 이후 다양한 변형 알고리즘들이 연구됨
• 1. 첫번째 유형
  • 원리...
    • 1. 로봇은 목표 방향으로 직진한다.
    • 2. 장애물 감지시, 해당 장애물의 가장자리를 따라 이동하면서, 전체 장애물의 경계를 탐색.
    • 3. 장애물의 전체 경계를 따라가며 '가장 목표 지점에 가까운 점'을 찾는다.
    • 4. 해당 점에 도달하면 다시 목표 방향으로 직진
    • 5. 위의 과정을 반복
  • 장점
    • 장애물의 전체 경계를 탐색하여 출구를 찾기 때문에, 장애물이 있는 복잡한 환경에서도 작동 가능
  • 단점
    • 장애물을 완전히 탐색해야하니, 비효율적이며 시간이 오래걸릴수도 있음

1번째 유형에 대한 설명

• 2. 두번째 유형
  • 원리...
    • 1. 로봇은 목표 방향으로 직진한다.
    • 2. 장애물을 만나면 장애물의 경계를 따라가면서, 목표로 향하는 직선(goal line)을 다시 만날때 까지 이동.
    • 3. goal line을 만나면, 장애물을 떠나서 다시 목표 방향으로 직진한다.
    • 4. 목표 도달할때까지 반복
  • 장점
    • 1번째 보다 효율적이다.
  • 단점
    • 나선형 같은 특정한 패턴을 가진 장애물이라면 비효율적으로 탐색할 수도 있음.

두번째 유형에 대한 설명

 

• 3. Tangent bug 알고리즘
  • 이는 2번째 알고리즘을 개선한 방식이며, 로봇이 이돌할때 센서 범위 내에서 장애물의 경계를 따라가면서 최단 거리를 선택한다.
    • 즉, 장애물을 회피하면서도 목표지점까지의 거리를 줄이도록 설계되었다.
  • 원리...
    • 1. 로봇은 목표 방향으로 직진한다.
    • 2. 장애물을 만나면 센서를 사용해서 장애물의 형상을 파악하고, 목표까지 가는 최단 경로를 탐색한다.
    • 3. 장애물의 경계를 따라가되, 더 빠르게 목표 방향으로 이동할 수 있는 방향이 있으면 해당 방향으로 진행
    • 4. 위의 과정 반복
  • 장점
    • 1,2번째 보다 효율적이며 센서를 활용해서 동적인 환경에서도 가능
  • 단점
    • 실시간으로 센서 데이터를 처리해야하니 계산량이 늘어남