coverage path planning이란?

CCP

• coverage path planning은 '로봇이 주어진 영역 전체를 누락없이, 효율적으로 커버하도록 경로를 생성'하는 방법이다.
• 기본적인 목표
  • 1. 모든 영역을 커버
  • 2. 최소한의 중복되는 경로
  • 3. 최소한의 회전과 전환
  • 4. 장애물 회피
  • 5. 동작 시간 및 에너지 최소화
• ccp의 분류
  • 1. offline CPP : 지도와 장애물 정보가 미리 주어짐. 즉, 사전 경로 계획
  • 2. online CPP :  탐사하면서 지도 작성( SLAM ). 즉, 동적으로 경로 생성
• 주요 알고리즘들...
  • 1. Boustrophedon Cellular Decomposition
    • "소가 밭을 가는 방식"을 의미한다. 이는 장애물이 있는 공간을 세로 슬라이스로 나눈다. 셀이 나누어지는 경계에서 connectivity 변화를 기반으로 셀을 정의한다.
  • 2. Spiral - STC ( Spanning Tree Coverage )
    • 공간을 격자로 나누고 spanning tree를 구성. 트리를 따라가면서 한번만 방문. 회전을 최소화하고 효율적 커버가 가능
  • 3. wavefront coverage
    • 로봇이 중심에서 출발하여 퍼져나가는 물결처럼 셀을 커버. BFS기반으로 동작 
• 만약에 ros를 가지고 실제로 적용한다면?
  • 1. slam + cpp : 지도를 작성후 cpp수행
  • 2. nav2 + cpp 
  • 3. grid map 생성후에, opencv기반 마스킹 처리로 cpp영역을 정의. 그리고 커버 순서를 지정후에 a* or rrt 기반 이동 
• 구현시 고려 사항
  • 1. 로봇 모델의 회전 반경 및 센서 범위
  • 2, 격자에서 장애물 셀을 어떻게 표현할지
  • 3. 경로의 중복을 최소화. 회전수도 최소화
  • 4. 만약 멀티로봇이라면 분산 계획 및 충돌 방지 
  • 5. 동적환경이라면, online으로 계획 및 회피 혼합도 필요하다.

 

 

cpp의 수학적 정의

 

 

coverage 방법들..

• 1. cell decomposition 
  • 전체 작업 공간을 '작은 cell'로 나눈뒤, 각각의 cell 내부를 커버하고, cell간을 이동하면서, 전체 영역을 누락없이 커버하는 방식.
  • 1-1. exact cellular decomposition ( 정확 분해 )
    • 원리 : 공간을 수직 슬라이스로 쪼개면서, 연결성이 변하는 지점에서 cell을 나눔. ( 만약, 장애물 존재한다면 cell이 나뉘고, 없다면 같은 cell로 유지 )
    • 특징 : 비격자 환경에서도 가능하며, cell 내부는 zigzag으로 커버 가능
    • 대표 알고리즘: Boustrophedon Decomposition
    • 장점 : 커버 누락이 없으며 경로 중복이 적다.
    • 단점 : 구현이 복잡하며 연산량이 크다.
  • 1-2. Approximate Cellular Decomposition ( 근사 분해 )
    • 공간을 격자로 단순하게 나누며, 각 cell을 순차적으로 방문한다.
    • 특징 : SLAM으로 생성한 Occupancy Grid map에서 적용이 쉬우며, 장애물은 occupied cell로 처리.
    • 대표 알고리즘 : Grid-based Cell Decomposition
    • 장점 : 간단한 구현과 실시간 적용 가능.
    • 단점: 경로의 최적화가 부족할 수 있으며, 셀 크기에 따라서 세밀도를 조정해야 함.
• 2. spanning tree 기반의 cpp
  • grid map을 그래프로 보고, node( cell )간 연결로 그래프를 구성한다. 그리고 최소 신장 트리를 만들어서 해당 경로를 따라서 방문.
    즉, grid map 생성 -> 그래프 모델링 -> MST 생성 -> tree path를 따라가며 커버
  • 장점
    • 전체 cell을 중복없이 한번에 커버 가능하며 '스패닝 트리의 성질'을 활용하여 회전 횟수를 줄이기가 쉽다.
  • 단점 
    • 장애물이 많을 경우에는 트리 생성이 복잡하며, 트리 경로 최적화가 별도로 필요하다.
  • 2-1. spanning tree coverage 
  • 2-2. DFS coverage
• 3. grid-based cpp with a*
  • a*알고리즘을 활용해서 각 cell간의 최적의 경로를 찾아서 커버한다. 
    커버 순서를 미리 정하거나 탐색 방식으로 정한다.
  • 커버할 cell을 list로 정렬한다 -> a*로 현재 위치에서 다음 cell까지 경로 탐색 -> 커버한 cell은 방문 처리
  • 장점 : 장애물 우회가 가능하며, 백트래킹을 최소화한다.
  • 단점 : 계산복잡도가 높으며, 전체 순서를 잘 정하지 않으면 비효율이 발생
• 4, Zigzag ( Lawn Mower )
  • 가장 직관적인 방식이다. 한줄씩 커버하며 ( 좌->우 , 우->좌 반복 )
  • 이미지 스캔 or 잔디 깎기 방식처럼 동작
  • 장점 : 구현이 간단하며 열린 공간에서 효율적
  • 단점 : 복잡한 장애물이 많다면 비효율적이며, 복잡한 경계에서 빈틈 생김이 가능하다.